Your Average Latency Is Lying to You: The Tail at Scale

The problem

Here's a service that looks healthy. Median response time is 10ms. The dashboard shows an average around 20ms. Nobody's paging you.

Then you put it behind a request that fans out to 100 of these services in parallel — a search, a feed build, a page that queries 100 shards and needs every answer — and suddenly two-thirds of your users are waiting more than a second.

Nothing got slower. You just discovered that at scale, your p99 is the number that matters, and your average was hiding it.

Why it happens

Give that "healthy" service a fat tail: 99% of requests return in 10ms, but 1% take 1000ms (a GC pause, a cold cache, a lock, a TCP retransmit — pick your poison). The average is 0.99 × 10 + 0.01 × 1000 ≈ 20ms. Genuinely fine on one call.

Now fan out to N servers and wait for all of them, because you need every shard's answer before you can respond. The request is fast only if every server dodged its slow path. The probability that at least one server hits its 1% tail is:

P(slow request) = 1 − (0.99)^N

Watch it move:

N =   1  →   1.0%
N =  10  →   9.6%
N = 100  →  63.4%
N = 200  →  86.6%

At a fan-out of 100, the slow path that happens 1% of the time on a single server becomes the common case for the user. The tail didn't add up — it compounded. This is what Jeff Dean and Luiz Barroso named "the tail at scale": in fan-out systems, the 99th-percentile latency of a component is effectively the median latency of the whole request.

The trap is that every instinct points the wrong way. You optimize the average — shave p50 from 10ms to 8ms — and the user-facing number barely moves, because the user-facing number is built out of tails, not medians.

What to do about it

Attack the tail, not the average. Improve the per-server slow rate and the compounded number collapses. Take that 1% down to 0.1%:

N = 100, p = 1%    →  63.4%
N = 100, p = 0.1%  →   9.5%

A 10× improvement in the tail buys a ~6.6× improvement for the user. The same 10× on the median buys you nothing. So put your SLOs on p99/p99.9, not the average, and hunt the specific causes of tails: GC pauses, cold caches, head-of-line blocking, one slow disk in the fleet.

Send a backup request (hedging). You don't have to make every server fast — you have to stop waiting on the unlucky one. Fire the request to one replica; if it hasn't answered by, say, the 95th-percentile expected latency, fire a second copy to another replica and take whichever returns first. Because you only hedge the slow ~5%, you pay a few percent extra load and cut the high-percentile tail by roughly an order of magnitude. It's the highest-leverage trick in the tail-tolerance playbook.

Cancel the loser. Hedging without cancellation just doubles work under load and can push you into a spiral. "Tied requests" fix this: send to two replicas, tell each about the other, and whichever one starts executing cancels its twin. You get the latency win without paying double.

Reduce the fan-out. 1 − (1−p)^N is exponential in N. Fewer, fatter shards beat many thin ones for tail behavior. If you can answer from 10 servers instead of 100, you've moved from 63% to 10% for free — before any hedging.

Key takeaways

• The average latency of a component is nearly useless once you fan out. In a request that waits on N servers, the user experiences the tail, not the median.
• The math is 1 − (1−p)^N, and it compounds fast: a 1% per-server slow rate becomes 63% at a fan-out of 100.
• Optimizing p50 is mostly wasted effort for user-facing latency. Move your SLOs and your attention to p99/p99.9.
• Hedged requests (fire a backup after the 95th percentile, take the first answer) cut tail latency by ~10× for a few percent more load. Cancel the loser so you don't double the work.
• Fewer shards = smaller N = smaller tail. Reducing fan-out is the cheapest tail fix there is.