The Tail at Scale
2013 · Communications of the ACM · ~11 min read
Read the original paperIf one server in a hundred is slow one per cent of the time, a request that touches all hundred is slow most of the time. This paper names that problem and gives the techniques that tame it.
The problem: the slowest one per cent is the user experience
Suppose a server answers 99 per cent of requests in ten milliseconds and one per cent in a second. Ask it once and the odds are fine. Now suppose a user request has to touch a hundred such servers, as a web search does when it consults a hundred index shards and waits for all of them. The chance that none of the hundred hits its slow case is 0.99 to the hundredth power, about 37 per cent. Nearly two-thirds of users wait a second. No server is misbehaving; the slow one is a different server each time; there is nothing to fix, and the system is slow.
Dean and Barroso catalogue where the one per cent comes from, and it is everywhere: a shared CPU, a background daemon, a garbage collector, a disk compaction, a queue that briefly filled, a machine throttling itself for heat. Some can be reduced. None can be eliminated, and at scale there are always enough of them that some request is hitting one. The paper’s thesis is that variability is a property of large systems and that latency has to be engineered the way availability is: by assuming components will misbehave and arranging for the system to tolerate it.
The idea: tail-tolerant design
The analogy the authors draw is with fault tolerance. We do not build reliable systems from components that never fail; we build them from redundant components and detect and route around failure. A slow response is a kind of failure, and the same move applies: have more than one place to get the answer, notice when one is taking too long, and ask another.
How it works
The simplest technique is the hedged request: send the request to one replica, and if no answer arrives within the 95th-percentile latency, send it to a second; use whichever answers first and cancel the other. Only the slowest five per cent of requests ever send a backup, so the extra load is small, but the tail collapses because a request must now be unlucky twice. In the paper’s Bigtable benchmark, hedging cut the 99.9th percentile of a 100-server fan-out from 1,800 milliseconds to 74, with about two per cent more requests.
Set how often a single server is slow and how many servers one user request fans out to. The chart shows the chance that the request waits for a slow one.
At 100 servers, a one-in-a-hundred hiccup becomes the typical experience: most requests wait for someone's garbage collector, disk scrub or background compaction. The paper's answer is not to eliminate variability, which is impossible, but to stop one slow server from deciding the outcome.
Tied requests go one step further: send to two servers at once, each told about the other, and have whichever starts the work first cancel the other’s copy, so the work is rarely done twice and the request never sits in one long queue. Then come the techniques that shape the system rather than the request: micro-partitions, many more shards than machines, so load can be moved in small pieces; selective replication of hot shards; latency-induced probation, temporarily routing around a server that has been slow; and good-enough results, answering a search once 95 per cent of shards have replied rather than waiting for the last one. Canary requests protect against a different tail: a query that crashes every server it touches is tried on one or two first.
| technique | what it costs | what it buys |
|---|---|---|
| hedged request | a few per cent extra load | the tail needs two unlucky replicas |
| tied request | a cancellation message | no queueing behind a long request |
| micro-partitions | more metadata | fine-grained load balancing and recovery |
| good-enough results | a slightly incomplete answer | never waiting for the slowest shard |
What it changed
The article made the 99th percentile the number engineers argue about. Latency objectives moved from averages to tails; load balancers, RPC frameworks and databases grew hedging and speculative retries as first-class features (gRPC, Envoy and Cassandra all have them); and the vocabulary of “tail latency” and “tail-tolerant” entered everyday use. The deeper shift was in attitude: slowness stopped being a bug to be found and became a condition to be designed for.
Where you meet it today
- p99 dashboards and SLOs. If you are paged on a percentile, you are living in this paper.
- Hedging policies in gRPC, Envoy and service meshes; speculative execution in Cassandra and Spark.
- Fan-out budgets. The reason microservice architectures with deep call graphs are hard to make fast is the arithmetic above.
- Timeouts with fallbacks. Returning partial results, cached results or a degraded page after a deadline is “good-enough results” in product form.
The original. Read it after this page; the explainer above is a map, not a substitute.
The article itself is short, free and readable in a sitting; this page is a warm-up for it.
The hedging policy in a widely used RPC framework, lifted straight from the paper.