The Tail at Scale

Users feel a system is fluid when it responds within about 100 ms. Google's services answer interactively while consulting datasets spread across thousands of servers. Jeffrey Dean and Luiz André Barroso explain why keeping the slowest responses fast, the tail of the latency distribution, gets harder as systems grow, and what Google does about it.

Variability has many sources: machines shared among applications, background daemons, global resources such as network switches, maintenance work such as log compaction and garbage collection, multiple layers of queueing, CPUs throttling to stay within power limits, solid-state drives pausing for their own garbage collection (which can raise read latency a hundredfold), and power-saving modes.

Scale amplifies it. A request that fans out to many servers and must wait for all of them is as slow as the slowest. If each server answers in 10 ms but takes a second 1% of the time, a request touching one server is slow 1% of the time; touching 100 servers, 63% of the time. Even with one slow response in 10,000, a request touching 2,000 servers is slow almost one time in five.

Eliminating every source of variability is impractical, so the authors argue for tail-tolerant techniques, by analogy with fault tolerance. Hedged requests send a second copy to another replica if the first has not answered after a short delay, and use whichever answers first. Tied requests enqueue copies on two servers that cancel each other when one starts. Across requests, micro-partitions, selective replication of hot items and latency-induced probation of slow machines rebalance load. In search, good-enough results skip the slowest servers and canary requests try a query on one or two servers before sending it to thousands.

LLM systems are fan-out systems. A RAG answer waits on retrieval from several indexes, a reranker and a model; an agent step waits on several tool calls; a batch of model requests waits for the slowest one. The paper's arithmetic applies.

Measure percentiles, not averages. A system that is fast on average can be slow for most users once a request touches several services. Report p50, p95 and p99 per step and per request.

Each added dependency raises the tail. Ten parallel calls, each slow 1% of the time, make about one request in ten slow. Count dependencies before promising a latency target.

Hedge reads, not writes. Duplicating a retrieval or a cache lookup after its 95th-percentile time costs about 5% more calls. Duplicating model generations costs real money, and duplicating actions with side effects needs idempotency first.

Good enough often is. If one of five retrieval sources is slow, answering from four is usually better than making the user wait. Decide in advance which components are optional.