Means add: the expected time of two stages in series is the sum of their expected times, exactly. Percentiles do not. The distribution of the sum is the convolution of the two stage distributions, and on the lab’s stages its p99 is 78 ms while the two stage p99s add to 110 ms. The naive sum is not a bound and it is not conservative — it is a percentile of nothing.
Core ideas
The hard idea is that a percentile is a rank and ranks do not compose. The arithmetic that replaces the addition is the convolution, and it is enumeration rather than algebra.
If stage A takes a with probability P(a) and stage B takes b with probability Q(b), independently, then the total takes a + b with probability P(a)·Q(b). Enumerate every pair, add up the probabilities that land on the same total, and you have the distribution of the sum. Seven outcomes each give forty-nine pairs and 43 distinct totals.
E[A + B] = E[A] + E[B] needs no independence and holds exactly: on the preset, 881/125 + 2414/125 = 659/25, which the lab prints as three exact fractions. There is no corresponding law for percentiles, because a percentile is a position in a sorted list and positions do not add.
p99(A) + p99(B) is the time taken when stage A is at its p99 and stage B is at its p99 in the same request. Independently that happens with probability 7/25000, about 0.028% — roughly three requests in ten thousand, not one in a hundred. The naive sum is a percentile of the joint worst case, which is a far rarer event than the one being asked about.
The material
Two stages, forty-nine pairs, and two numbers that differ by a third.
The lab holds two stages, each given as a list of milliseconds:weight pairs. Stage A is mostly fast — 4 ms on more than half of calls — with a thin tail out to 70 ms. Stage B is slower and steadier, centred near 17 ms with a tail to 130 ms. They run one after the other, so the request takes the sum.
For independent A and B taking values with probabilities P(a) and Q(b), the convolution is the distribution of A + B: the probability of a total t is the sum of P(a)·Q(b) over every pair with a + b = t. With finitely many outcomes it is computed by enumerating all the pairs, so it is exact and needs no approximation at all.
Take the two stages’ own percentiles first, by the rank rule of “Percentiles from a Sample”. Stage A has a p99 of 38 ms; stage B has a p99 of 72 ms. Add them and you get 110 ms, and that number appears in a great many latency budgets. Now compute the distribution of the sum and read its p99 off the same rank rule.
The true p99 of the two stages together is 78 ms. The sum of the p99s is 110 ms, which overstates it by 32 ms — 41.0%. Budgeting the pair at 110 ms reserves a third more time than the percentile being promised actually needs, and if that budget is what sizes a timeout or a machine count, the overstatement is paid for in capacity.
Read the two mean columns while you are here. 881/125 + 2414/125 is 3295/125, which is 659/25 — and 659/25 is exactly the mean of the convolved distribution. The added row and the true row agree to the last digit for means and disagree by a third for the p99. That is the whole lesson in one table: linearity of expectation is a theorem, and there is no theorem next to it for percentiles.
The natural repair is to keep adding the percentiles and call the result conservative. Look at the p95 row of the same table. The stage p95s are 14 ms and 34 ms, which add to 48 ms; the true p95 of the sum is 52 ms. Here the naive arithmetic understates by four milliseconds, on the very same pair of stages, at a percentile one step away.
So the sum of the percentiles is not an upper bound, not a lower bound, and not conservative. It is a number obtained by adding two quantities that were never addends. Whether it comes out high or low depends on how the mass beyond each stage’s percentile is arranged: when each stage’s tail is thin and far out, a single rare spike carries the pair over the line on its own and the true percentile can sit above the naive sum.
For the total to reach 110 ms by both stages being at their p99 together, stage A must exceed 37 ms — probability 1/50 — and stage B must exceed 71 ms — probability 7/500. Independently that is 7/25000, or 0.0280%. The question asked was about the worst one percent of requests; the number returned describes the worst three in ten thousand. They are different questions with a factor of thirty-five between them.
What to do instead is in the lab. Convolve: enumerate the pairs, accumulate the probabilities onto their totals, and read the percentile of the result by rank. For two stages of seven outcomes that is forty-nine multiplications, every probability an exact fraction, and the answer is the percentile of the thing that was actually asked about.
Interactive
The sum by convolution, beside the sum of the p99s that is not it
Method
Four steps, and the first is a decision about which question you are answering.
For total work, capacity and cost, add the means: that is exact and needs no independence. For a latency objective stated as a percentile, the addition is not available and the next three steps are the method.
Each pair contributes its two times added together, with probability the product of the two probabilities. Keep the probabilities as fractions; with integer weights they stay exact and the final comparison needs no rounding argument.
Different pairs land on the same total, so add their probabilities together. Then walk the totals in order, accumulating, and take the first value whose cumulative probability reaches q. That is the percentile of the sum.
Report both numbers and their difference. The gap is what the naive arithmetic was about to cost, in either direction, and it is the only thing that will persuade anyone to do the convolution next time.
The stages are small enough to enumerate and the arithmetic is exact, so the comparison at the end rests on nothing but counting.
The tick on the last line is not decoration. The means were computed two ways — added, and taken from the convolved distribution — and they agree exactly. That is a check on the convolution itself: if those two disagreed, the enumeration would have a bug in it, and the p99 it produced would be worth nothing.
The 41.0% gap is not a general figure. It depends entirely on the shapes: two stages with fat, nearby tails give a smaller gap, and the p95 row of the same pair gives a gap of the opposite sign. What is general is that the two numbers are answers to different questions, and that only one of them was asked.
For a faded rehearsal, replace stage B with 10:900, 100:100 — a stage that is fast nine times in ten and takes 100 ms otherwise. The supplied first move is B’s own p99, which by rank is 100 ms. Predict whether the true p99 of the sum will be above or below 38 + 100 = 138 ms before you compute anything, then type the stage into the lab and see. Write down which way you guessed and why before opening the quiz.
You should be able to convolve two small distributions by enumerating pairs, read the percentile of the result by rank, compare it with the sum of the stage percentiles, and state the probability of the joint event the naive sum actually describes.
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.