Tail latency at scale
Read firstRetries, backoff and circuit breakers
A product search fans out to 100 index shards and merges their answers. Every shard's dashboard looks healthy: 10 ms at the median, and one request in a hundred takes a full second. The search team's dashboard looks terrible. Most searches take about a second.
Nobody is lying. Both dashboards are right, and the gap between them is one of the most useful things a senior engineer can explain in a design review.
Each of 100 servers answers in 10 ms 99% of the time and in 1 second 1% of the time. A request needs an answer from all 100. Roughly what share of requests take a second? What would you do about it?
Percentiles, quickly#
Latency is a distribution, not a number. The median (p50) is what half the requests beat. The p99 is what 99% of requests beat, so 1 request in 100 is slower. The tail is that slow end: p99, p99.9 and beyond.
Averages hide the tail completely. A service where 99 requests take 10 ms and one takes 1,000 ms has an average of about 20 ms, which describes none of them. And percentiles do not combine: you cannot average ten servers' p99s to get the system's p99. To know the p99 of what the user waited for, measure what the user waited for.
Fan-out turns rare into common#
When one request has to wait for many servers, it is as slow as the slowest of them. If each server is slow with probability p, the chance that at least one of N is slow is 1 − (1 − p)ᴺ. Try it.
With 100 servers each slow 1% of the time, 1 − 0.99¹⁰⁰ ≈ 63% of requests wait for a slow one. The servers' p99 has become the user's median. Jeff Dean and Luiz André Barroso made this argument in "The Tail at Scale" (2013), and it is why companies that run large fan-out systems care more about each server's p99.9 than its average.
Fan-out is everywhere once you look: a search across shards, a feed that pulls from 50 friends' timelines, a page that calls 30 microservices, a scatter-gather query in a sharded database.
Where slowness comes from#
You cannot make the tail disappear, because its causes are part of running real machines:
- Garbage collection pauses a process for tens or hundreds of milliseconds.
- Queueing behind one large request, or a burst that arrived at the same moment.
- Background work: an LSM compaction, a backup, a log rotation.
- Noisy neighbours: another tenant's job on the same machine using the same disk or cache.
- The network: a dropped packet waits for a TCP retransmit, often 200 ms or more.
At scale, some server is always doing one of these. The answer is to design so one slow server does not decide the user's latency.
Hedged requests#
The best known trick: send the request to one replica, and if it has not answered by about its p95, send the same request to a second replica. Use whichever answer arrives first and cancel the other.
A leaf is now slow only if both copies are slow, so p becomes roughly p². The paper reports a Bigtable benchmark where hedging after 10 ms cut the 99.9th percentile latency of a 1,000 key read from 1,800 ms to 74 ms, while sending just 2% more requests.
Two conditions. The request must be safe to send twice, so hedge reads and idempotent operations only. And hedge after a delay, never at once: sending every request twice doubles your load to fix a problem that affects 5% of requests.
Other tricks#
Partial results. A search across 100 shards can return results from the 98 that answered in time, and nobody notices the missing 2%. Decide per feature whether "good enough, now" beats "complete, late". For search and feeds it nearly always does. For a bank balance it never does.
A deadline per leaf. Give each shard call a timeout well under the user's budget, and drop the stragglers rather than waiting.
Smaller fan-out. Fewer, larger shards, or a two level tree (the root asks 10 aggregators, each asks 10 shards) so each wait covers fewer servers.
Take slow machines out. A server that is consistently slower than its peers can be removed from rotation for a while. Envoy's outlier detection does this for hosts that keep returning errors.
Measuring it right#
Two mistakes hide the tail from your dashboards.
Measuring at the server. The server's timer starts when it picks up the request, after any time spent queueing in front of it. Measure at the caller, and at the user, too.
Coordinated omission. A load test that waits for each response before sending the next request sends fewer requests exactly when the system is slow, so it under-samples the slow periods. Gil Tene named this problem. Tools that send at a fixed rate regardless of responses (wrk2 was written for this) and latency histograms such as HdrHistogram give you the honest tail.
"p99 under 100 ms" for a backend called 50 times per page view means about 40% of page views include at least one call slower than 100 ms. Set the SLO on what the user waits for, then work out what each backend needs to promise to make that true.
- EnvoyHedged requests on per-try timeout, outlier detection
- ElasticsearchScatter-gather across shards; adaptive replica selection
- CassandraSpeculative retry: a hedged read to another replica
- HdHdrHistogramLatency histograms that keep the tail
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Hedged requests after the p95 | The slow tail of each leaf almost disappears, for about 5% more load. | Only safe for reads and idempotent calls, and needs cancellation to avoid wasted work. | Fan-out reads against replicated data: search shards, key value lookups. |
| Partial results | Latency is set by your deadline, not by the slowest shard. | Answers are occasionally incomplete, and you must say where that is acceptable. | Search, feeds, recommendations. Never balances or orders. |
| Smaller fan-out | Fewer servers to wait for means fewer chances to hit a slow one. | Bigger shards, so each one does more work and rebalancing moves more data. | When fan-out has grown with the cluster rather than by design. |
Interview replay#
Checkpoint#
1. A request fans out to 100 servers, each slow 1% of the time. Roughly what share of requests wait for a slow server?
2. Why does a hedged request cost only about 5% more load when sent after the p95?
3. Ten backends report p99 of 40, 45, 50, 38, 60, 42, 55, 47, 41 and 52 ms. What is the p99 of a page that calls all ten?
- 1 − (1 − p)ᴺ: 100 servers at 1% slow means 63% of requests are slow.
- Hedge after the p95: about 5% more requests, leaf slowness goes from p to about p².
- 74 ms vs 1,800 ms p99.9 in the Tail at Scale Bigtable example, for 2% more requests.
- Percentiles do not average. Measure what the user waits for.
When a request fans out to many servers it is as slow as the slowest one, so rare slowness on each server becomes common for the user: with 100 servers each slow 1% of the time, 63% of requests hit a slow one. The causes, like GC pauses, queueing, compaction, noisy neighbours and packet loss, never go away at scale, so I design around them. Hedged requests send a second copy to another replica if the first has not answered by its p95, take the first answer and cancel the other, which costs about 5% more load and turns p into roughly p squared. I give each leaf a deadline and return partial results where the product allows, keep fan-out small, and take slow hosts out of rotation. And I measure at the caller, with histograms, avoiding coordinated omission, because percentiles do not average.