Tail latency amplification

The problem it solves

A backend team reports p99 = 100 ms and considers the matter closed: 99% of calls are fast, one in a hundred is slow, and one in a hundred sounds like a rounding error. Then the product team reports that the page is slow for most users, and the two facts sit in the same room refusing to reconcile.

They reconcile immediately once you count the fan-out. If rendering the page requires 100 backend calls and the page waits for all of them, the probability that every call avoids the slow path is 0.99^100 ≈ 0.366. Roughly two in three user requests contain at least one call from the backend’s p99. The backend’s rare case is the user’s common case. Nothing is broken; the arithmetic simply was not done.

The mechanism

Fan-out with a wait-for-all barrier turns a percentile into a maximum, and maxima of many samples live far out in the tail. If each of n calls independently exceeds some threshold with probability p, the chance that at least one does is 1 − (1 − p)^n. For small p that is approximately n × p, which grows linearly in fan-out until it saturates near 1.

Turned around, the same relation tells you what percentile of the backend becomes the median of the user: with fan-out n, the user median corresponds to the backend’s 0.5^(1/n) quantile. At n = 100 that is the backend p99.3. So at a fan-out of a hundred, the number you should be tracking on the backend is not p99 — p99 is your median now — it is p99.9 or p99.99, and those are numbers most teams do not measure and cannot measure reliably without a great deal of traffic.

Two mechanisms fight back.

Hedging sends a second copy of any request still outstanding after some threshold — say the p95 — and takes whichever answer returns first. The extra load is small by construction (only the slowest 5% get duplicated) and the effect on the tail is large, because the second copy’s latency is an independent draw: for both to be slow, two independent unlikely events must occur.

Quorum changes the barrier. If a slightly incomplete answer is acceptable — 95 of 100 shards’ worth of search results, all of the recommendations that arrived in time — then return when the quorum is met and let the straggler finish into the void. This removes the straggler from the critical path entirely, and it is the more powerful of the two, because it costs no extra work at all.

What the simulation shows

The default is one backend with a realistic log-normal latency profile, fanned out to a hundred and waited on in full. Compare the two histograms: the backend’s distribution is unremarkable, with a long thin tail. The user’s distribution is shifted bodily to the right. The callout puts the number on it — the backend p99 has become the user median.

Then set fan-out to one to establish the counterfactual. The same backend, called once, is fine: the user p50 is the backend p50 and the p99 is genuinely rare. Nothing about the backend changed between these two runs. The fan-out is the entire story.

Now buy the tail back. Turn on hedging after 45 ms and watch the user p99 fall sharply for a few percent more backend work. Or accept a 95% quorum and watch the straggler leave the critical path with no extra work at all. Both are on the page because the right answer depends on whether an incomplete result is acceptable — a product question, not an engineering one.

The numbers worth carrying

• Fan-out 10, wait-for-all: about 10% of user requests hit the backend p99.
• Fan-out 100: about 63%.
• Fan-out 1000: essentially all of them; the backend p99.9 is now the interesting number.

And the inversion, which is the one to say in an interview: at fan-out n, the user median is the backend’s 1 − 0.7/n quantile, near enough. At n = 100, that is p99.3.

Where it breaks down

The independence assumption is doing a lot of work above, and in real systems it is often false — in the direction that makes things worse and in the direction that makes them better. Correlated slowness (a GC pause on a shared host, a saturated top-of-rack switch, a lock convoy in a shared dependency) means many calls are slow together, so the fan-out multiplier over-counts the number of distinct slow events but under-counts their severity. Conversely, if all n calls go to the same backend instance, hedging to the same instance buys you nothing, because the cause of slowness is shared.

Hedging has a failure mode of its own: it adds load precisely when the system is slow, which is the retry storm pattern in miniature. Bound it — a hedge budget capped at a few percent of requests — or a hedging client will happily double your traffic during an incident. See retry storms.

Quorum is not free either. Returning 95 of 100 shards means the answer is wrong in a way somebody has to be comfortable with, and “usually complete” needs to be an explicit product decision with a monitored completeness metric.

What people get wrong

“p99 is a 1% problem.” Only at fan-out one. Ask what the fan-out is before interpreting any percentile.

“Averages are fine for capacity, tails for user experience.” Fan-out converts the tail into the average experience. They are the same conversation.

“We will just make the p99 better.” Improving a backend p99 from 100 ms to 80 ms at fan-out 100 barely moves the user median, because the user median is set by the shape of the tail out at p99.3, not by the p99 value. Reducing fan-out, hedging, or relaxing the barrier all beat squeezing the backend.

“Add a timeout on each call.” A timeout converts slow into failed, which is only an improvement if a partial result is acceptable — in which case you wanted a quorum, and should say so. Otherwise you have made the user’s slow request into a user’s failed request. See timeout cascades.

In production

The canonical reference is Dean and Barroso’s The Tail at Scale, which introduced hedged requests, tied requests, micro-partitioning and selective replication as a coherent toolkit. The operational core of it: measure high percentiles at the user boundary, not only at each service; know your fan-out per endpoint; and treat “wait for all” as a design choice that must be justified rather than a default.

gRPC and Envoy both support hedging natively with budgets; Cassandra’s speculative retry is the same idea at the storage layer; most search systems have shipped a quorum barrier for a decade because their fan-out made it mandatory. If your architecture diagram has a node with a hundred arrows leaving it, this page is about that node.

The follow-up questions

“Your backend p99 is 100 ms and the page makes 50 calls. What is the user p99?” — Far worse than 100 ms, and about two in five user requests will contain a p99 call. Do the 1 − 0.99^50 arithmetic out loud.

“How would you fix it without touching the backend?” — Reduce fan-out, hedge, or accept a quorum. Name all three and pick one with a reason.

“What does hedging cost?” — A few percent of extra load, concentrated at the worst moment. Bound it.

“Which percentile should the backend team track?” — Whichever one your fan-out turns into the user median. Give them the number.