Papers
The Tail at Scale
Jeffrey Dean, Luiz André Barroso · Communications of the ACM, Vol. 56, 2013
The problem: why tail latency matters when the system is large
The starting point of the paper is that users perceive a service as fluid when it responds in around 100 milliseconds, and that data-center-scale computing has made it possible to offer that experience even while querying multi-terabyte datasets spread across thousands of machines. The problem is that, when a single user request needs to query tens or hundreds of servers in parallel to assemble the response, the request's final latency is determined by the slowest component among all of them, not by the average latency. The authors show this with a numerical example: if each individual server has a 99th-percentile latency of 1 second (but normally responds in 10 milliseconds), and a request must wait for 100 of these servers in parallel, about 63% of user requests will end up taking more than 1 second, because a single slow server among the hundred is enough to delay the entire response. In a real Google system, a 10ms latency at the 99th percentile per leaf request becomes about 140ms at the aggregate 99th percentile, and the slowest 5% of requests account for half of all the latency observed at the 99th percentile. In other words, in systems with high fan-out, tail latency stops being a rare event and comes to dominate the experience of a good share of users.
Where latency variability comes from
The article argues that latency variability is not a rare defect of bad hardware, but a practically unavoidable characteristic of any shared machine in production. Among the sources of variability discussed are: contention for shared resources on the same machine (CPU, cache, network bandwidth, and disk contested among multiple processes or services running side by side); background maintenance activities and the system's own daemons, which occasionally steal processing cycles; garbage collection pauses in managed runtimes; power management mechanisms that lower the processor frequency to save energy and then need time to return to full performance; and queueing effects, in which a burst of concurrent requests piles up in internal queues of the operating system, the network middleware, or the application itself, delaying some requests even though the system's average capacity is sufficient. The practical conclusion is that, even with well-sized hardware and no real failure happening, a small but constant fraction of individual requests will be slow simply because of these normal system interactions — and that is precisely the fraction that gets amplified when many components must respond together.
The proposed techniques for tolerating the tail
Instead of trying to eliminate all individual variability — which the authors consider impractical —, the paper proposes techniques to make the system as a whole predictable even when its individual parts are unpredictable, in parallel with the classic fault-tolerance reasoning based on redundancy. Two techniques act within a single request: in 'hedged requests', the client sends the same request to a secondary replica if the first replica has not yet responded after a time close to the expected 95th percentile, and uses whichever response arrives first, canceling the other — this limits the extra load to a few percent while greatly reducing the tail. In 'tied requests', a more aggressive variation, the client enqueues the request on multiple servers at the same time from the start, but tells each one about the existence of the others, so that when one server starts processing (or finishes), it sends a cancellation for the copy in the other servers' queues; in a real Google system this technique reduced median latency by about 16% and 99.9th-percentile latency by about 40%. Two other techniques operate across requests over time: micro-partitioning, which keeps many more data partitions than physical machines so that load can be redistributed quickly in small increments; and canary requests, which send a small number of test requests against new code or configuration before a broad rollout, to keep a bug from causing correlated failures on many servers at once.
Legacy: tail tolerance in current systems
The paper's central contribution, treating tail latency as a systems engineering problem with its own techniques rather than a statistical detail to be passively tolerated, became a widely adopted design principle in distributed infrastructure after 2013. The idea of sending a redundant request to an alternate replica when the first one takes longer than expected has appeared, in variations of its own, in RPC frameworks widely used in the industry, which now offer configurable hedging policies as part of the service-to-service communication library itself, so the application developer does not have to reimplement the logic by hand. The reasoning that high-fan-out systems amplify the tail latency of individual components also influenced how operations teams evaluate internal SLOs: instead of looking only at the average latency of an isolated service, teams started monitoring high percentiles (p99, p999) precisely at the points where many parallel calls converge. The notion of canary requests, in turn, is now standard practice as gradual rollout (canary deployment) before exposing a code change to all production traffic. Together, these ideas helped consolidate the view that, in large-scale systems, controlling the tail of the latency distribution is as important as controlling the average, and that this can be done with specific engineering techniques, not just with more hardware.
See the ideas at work
Practice the designs that use this paper in the System Design school.