A job that waits for all of its partitions finishes when its slowest one does, so its running time is the maximum of N draws rather than the mean of them. The maximum's distribution is computed exactly here by enumeration, and it moves the wrong way as N grows: with the lab's distribution, 24 partitions average 111.63 ms against a single partition's 25.80 ms, and 32 partitions are slower still.
Core ideas
One substitution — the maximum where the mean was expected — and three consequences that all point the same way.
If a job is done when every partition is done, then P(job ≤ t) is the probability that all N partitions came in at or under t, which is P(one ≤ t)ᴺ under independence. That single line gives the whole distribution of the job time from the distribution of one partition, and the lab enumerates it exactly rather than sampling it.
Each partition's own time distribution does not change when you add partitions; what changes is how many draws the maximum is taken over. With the lab's distribution the job mean goes 25.80, 41.61, 88.73, 111.63, 130.62 ms at N = 1, 4, 16, 24, 32. The work per partition shrinking is a separate effect, and it is not what this arithmetic is measuring.
The 400 ms outcome has weight 5 in a thousand — half a per cent of partitions. P(no partition past 120 ms) = 0.995ᴺ, which is 0.990 at N = 2 and 0.985 at N = 3, so from three partitions on, 400 ms is the job's p99. The lab finds that crossing by exact search over N rather than from a logarithm.
The material
Where the maximum comes from, how to get its distribution exactly, what it does as N grows, and the separate effect that makes anybody believe partitions are free.
In a job that must wait for every partition, the straggler is the partition that finishes last. The job's completion time is that partition's completion time, so the job's running time is max(T₁, …, T_N) where Tᵢ is partition i's time. The straggler tax is the ratio of the job's mean time to one partition's mean time.
The distribution of the maximum follows from one observation, and the observation is about the complement. The maximum is at most t exactly when every one of the N partitions is at most t; there is no other way for the largest of them to be small. Under independence that probability is the product, and since the partitions are drawing from the same distribution it is a power.
Every figure above is exact. The distribution of the maximum over a finite set of outcomes is a finite object, so the lab enumerates it rather than simulating it — the 111.63 ms is a sum over outcomes, not an average over runs, and it will be the same number every time you open the page.
Two things happen when a job is spread over more partitions and they point in opposite directions. Each partition has less work, which shifts its own time distribution down; and the job takes a maximum over more draws, which pushes the job time up. The first effect is real, and it is why partitioning works at all. The second is what this lesson measures, and it is the one nobody budgets for.
The p99 column is the sharpest reading. One partition has a p99 of 120 ms; by N = 4 the job's p99 is 400 ms, the worst outcome in the distribution, and it stays there for every larger N. Nothing about the partitions got slower. The job simply takes enough draws that the rarest outcome is no longer rare.
P(job past 120 ms) is 0.50% at one partition and 47.36% at 128. If 120 ms is a timeout, the same code that succeeded 199 times in 200 as a single unit fails about half the time as a 128-way job — and every one of those failures is a retry, which “Retries and Request Amplification” prices. The partition count did not change any component's reliability; it changed how many components have to all be fast at once.
Three responses, in increasing order of what they cost. Reduce the tail of one partition, which moves the whole table at once and is almost always the best value. Stop waiting for every partition where the answer permits it — a job that can return on 95% of its partitions is taking a much lower quantile of the same distribution. Or send the slow partition somewhere else and take the first answer, which is “Hedged Requests” and costs duplicate work.
What does not help is adding partitions, and it is worth being precise about why that differs from the two previous lessons. A hot range and a hot key are skew: the work is unevenly distributed and the arithmetic is about where it lands. A straggler needs no skew at all. Every partition here draws from the same distribution and the job is still four times slower than one partition, because the maximum of many identical things is larger than any of them.
Interactive
The job's time is the maximum of N partition times, enumerated exactly
Method
Get one partition's distribution first. Everything else on this page is computed from it, and a mean alone is not enough to compute anything.
You need the outcomes and their weights. A mean of 25.80 ms is consistent with a job mean of 25.80 ms and with one of 250 ms, and which of those you get depends entirely on the tail that the mean hides.
For each candidate time, raise the single-partition cumulative probability to the power N. Over a finite set of outcomes this is a short table, and it gives the job's mean and every quantile at once.
The mean tells you throughput and the p99 tells you what a user or a timeout sees, and they move differently: at N = 24 the mean is 4.33 times one partition's and the p99 has jumped to the distribution's worst outcome. Quote both.
Halve the weight on the slowest outcome and recompute; then add partitions and recompute. On this distribution the first improves every row of the table and the second makes the job slower. Do that comparison before choosing a partition count, not after.
One partition first, exactly; then the job; then the question of where the job's p99 came from.
Three partitions. That is where a 0.5% outcome stops being a tail and becomes the number a p99 reports, and it is found by evaluating 0.995ᴺ rather than by any rule of thumb about long tails.
For a faded rehearsal, keep the same outcomes and take the weights to 20:940, 40:40, 120:15, 400:5 — a tighter middle with the same slow tail. The supplied first move is the new single-partition mean. Produce the job's mean and p99 at N = 24, then say whether the p99 moved and why, and then predict what would have happened instead if you had halved the weight on 400 and left the middle alone. Check both in the lab.
You should be able to compute a job's mean and quantiles from one partition's distribution and a count, find the N at which a rare outcome becomes the p99, and say which of tail reduction, partial results and hedging you would reach for first.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.