One Slow Task Sets the Pace for Everything

When a stage must complete before the next begins, the stage’s duration is the maximum over its tasks, not the average. That single substitution is why distributed jobs behave so differently from what an average-based intuition predicts. With a thousand tasks, you are sampling the tail of the duration distribution a thousand times, and whatever rare slowness exists in your infrastructure will be represented.

The arithmetic is unforgiving. If a task has a 1% chance of taking ten times as long — a disk retry, a garbage-collection storm, a noisy neighbour, a slow network path — then with 100 tasks you are more likely than not to have at least one, and with 1,000 you are essentially guaranteed several. Adding parallelism does not reduce this; it increases the number of chances for the rare event to occur. This is Fan Out to 100 and the Component’s Tail Becomes the System’s Median with a job as the request, and it is the reason tail latency is a first-class concern in compute and not just in serving.

The consequence worth internalising: improving the median task does almost nothing for a barrier-synchronised job. A change that makes every task 20% faster leaves the straggler roughly 20% faster too, which barely moves the maximum when the maximum is fifty times the median. The only changes that matter are ones that attack the maximum directly.

A slow task has three common causes, and the metric that separates them is input bytes per task.

Skew — the task has more data. Input bytes are far above the median, duration is proportional. Speculative execution does not help at all: the duplicate has the same input and takes the same time, and you have wasted a slot. The fix is to change the key or the partitioning, as in The Shuffle Is the Job and Hot Partitions: The Skew Hashing Cannot Fix.

A slow machine — the task has normal input and is running on a degraded host: a failing disk, a throttled CPU, a saturated network link, a noisy neighbour, an over-committed node. Input bytes are ordinary, duration is not. This is where speculative execution is exactly right, because the duplicate runs somewhere healthy.

Transient interference — a garbage-collection pause, a page-cache miss storm, a brief network problem. Indistinguishable from a slow machine at the moment of observation, and equally well handled by launching a duplicate.

So the diagnosis is a two-line check: if max input bytes is close to median input bytes, it is a machine problem and speculation helps. If max input bytes is far above median, it is skew and speculation is pure waste. Frameworks that launch speculative copies for skewed tasks are burning capacity, which is why speculation should be capped as a fraction of the stage.

The idea is deliberately wasteful and works well. When a task has been running substantially longer than its peers in the same stage, launch a second copy on a different machine and take whichever finishes first, killing the other. If the original was slow because of its host, the duplicate lands somewhere healthy and completes in normal time. The stage’s maximum collapses toward the median at the cost of a small amount of duplicated work — typically a few percent of the cluster, because only a few tasks are ever candidates.

The trade is capacity for tail latency, and the reason it is a good trade is that the last few tasks of a stage run in an otherwise idle cluster: the duplicate consumes a slot nobody else wanted. That is why speculation is normally enabled *late* in a stage and capped as a fraction of tasks, rather than applied to any task that happens to be slower than average.

The safety conditions are not optional. The task must be deterministic, or the winning attempt might produce a different answer from the losing one. It must be side-effect-free, or both attempts affect the outside world and the discard is meaningless — this is the same requirement MapReduce: The Model That Made the Trade-offs Visible imposes and the same trap teams fall into. And the output commit must be exclusive and atomic, so exactly one attempt’s result lands. Where those hold, speculation is free tail-latency insurance. Where they do not, it is a duplicate-execution generator that runs by default, and the first anyone hears of it is duplicate rows in a downstream table.

Note the relationship to Send a Second Request After p95 and Take Whichever Answers First: it is the same idea at a different scale. Send a second copy of the work, take the first answer, accept some duplicated effort for a much better tail. Both work for the same reason — the slow case is caused by something local to one machine, not by the work itself — and both fail for the same reason when applied to work whose slowness is intrinsic.

Speculation treats the symptom. Two structural changes attack the cause.

Remove or weaken the barrier. A barrier exists because a downstream task needs *all* upstream output. Where that is not truly required, pipelining lets downstream work begin on partial input and a slow producer delays only its own consumers rather than the whole stage. Streaming engines are built around this, and it is the largest available win — a job with no global barrier has no global straggler, only local ones.

Make tasks smaller and more numerous. With tasks much smaller than a worker’s capacity, a slow worker simply completes fewer of them and the rest of the cluster picks up the slack automatically. This is dynamic load balancing by task granularity, and it is the same instinct as work stealing inside a machine. The counter-pressure is real: more tasks means more scheduling overhead and, for a shuffle stage, more transfers — so the right size is a compromise, and "one task per core" is usually far too coarse.

There is also a cause worth naming and removing rather than tolerating: persistently degraded hosts. If speculation is regularly rescuing tasks from the same three machines, speculation is masking a hardware problem. Attribute speculative wins by host, and a pattern appears immediately. Fixing the machine is worth more than any amount of speculative work, and — like the retry attribution in Who Runs What, and What Happens When a Worker Goes Quiet — it is the automated mitigation that keeps the underlying fault invisible.