How rare latency hiccups become dominant performance killers in large distributed systems — and the ingenious techniques Google uses to tame them.
Just as fault-tolerant computing creates a reliable whole out of less-reliable parts, tail-tolerant systems create a predictably responsive whole out of less-predictable parts. You can't eliminate all variability — so you design around it.
Modern web services respond to a single user request by fanning it out across hundreds or thousands of servers in parallel. Every server must respond before the user gets a result. Even if each individual server is fast 99% of the time, the math works brutally against you at scale — the slowest server dictates your response time.
If each server has a 1% chance of being slow (>1 second), what happens when you fan out to many servers?
Probability of at least one server exceeding 1 second — with a per-server 99th-percentile latency of 1s.
Even a 0.01% outlier rate means that in a system with 2,000 servers, nearly 1 in 5 user requests hits at least one slow server. The tail is no longer "rare" — it's the dominant experience.
Shared resources, background daemons, garbage collection, power management, thermal throttling, network contention — there are too many sources of jitter to stamp out completely, especially in shared multi-tenant environments.
Instead of preventing every possible latency spike, design systems that produce predictable end-to-end performance from unpredictable components — "tail-tolerant" software, analogous to fault-tolerant hardware.
The paper catalogs the many sources of jitter that contribute to tail latency, spanning both software and hardware layers.
CPU cores, caches, memory bandwidth, and network bandwidth are contested by co-located applications and concurrent requests.
Background processes use few resources on average, but when they're scheduled they can cause multi-millisecond hiccups.
Distributed file system reconstruction, BigTable log compaction, and language-level garbage collection trigger periodic latency spikes.
Multiple layers of queues in servers and network switches multiply variability at each hop, compounding delays exponentially.
CPUs boost above average power temporarily, then thermally throttle — introducing unpredictable slowdowns under sustained load.
SSDs offer fast random reads, but periodic block garbage collection can inflate read latency by 100x, even with light write activity.
Power-saving modes save energy but add latency when devices wake from inactive to active states, introducing cold-start penalties.
Applications on different machines contend for shared global resources like network switches and distributed file systems.
Before applying tail-tolerant techniques, careful engineering can reduce the base level of variability. These are necessary but not sufficient at scale.
Prefer scheduling interactive user-facing requests over batch operations. Keep low-level OS disk queues shallow so higher-level priority policies take effect quickly. Google's storage servers maintain their own priority queues rather than relying on deep OS-level queues.
Break expensive, long-running requests into sequences of smaller operations. This allows cheap, fast queries to interleave and avoid being stuck behind a single heavy computation. Google Search uses time-slicing to prevent a few expensive queries from delaying thousands of cheap ones.
Rather than letting background tasks (log compaction, GC) run randomly across machines, synchronize them into brief coordinated bursts. This confines the latency impact to one short window instead of having a few slow machines at all times, constantly pushing out the tail for every request.
Note on caching: While caching is essential for performance, it does not directly address tail latency unless the entire working set fits in cache. A cache miss on the critical path is still subject to all the variability above.
Since eliminating all variability is impossible, Google developed techniques that mask or work around latency problems rather than trying to prevent them. These fall into two categories based on their response timescale.
These operate at the millisecond scale, reacting immediately before longer-term systems can kick in. They leverage the fact that most services already have data replicated for fault tolerance.
The simplest and most elegant technique. Instead of waiting for a single slow server, send the same request to multiple replicas and use whichever responds first.
Send the request to the primary replica believed to be most appropriate.
If no response arrives within the 95th-percentile expected latency, send a duplicate "hedge" to a second replica.
Use whichever response comes back first. Cancel the other request.
A more sophisticated evolution of hedged requests. The key insight: most latency variability comes from queueing delays before execution, not from execution itself. Tied requests attack queueing directly.
Send copies of the request to two servers simultaneously, each tagged with the identity of the other ("tied").
When either server begins executing the request, it immediately sends a cancellation to its tied counterpart.
The counterpart, if still queued, is immediately aborted or deprioritized. A tiny stagger (~1ms) between sends prevents both starting simultaneously when queues are empty.
These operate over seconds to minutes, addressing coarser-grain phenomena like load imbalance and machine-level performance degradation.
Instead of assigning one partition per machine (making rebalancing slow and coarse), create many more partitions than machines. Google typically uses ~20 partitions per machine. This enables:
Fine-grained load shedding: Move a single micro-partition (~5% of load) instead of all-or-nothing.
20x faster rebalancing: Shifting one micro-partition takes 1/20th the time of moving a full partition.
Faster failure recovery: When a machine dies, many machines each pick up one small unit of work in parallel.
Build on micro-partitioning by detecting or predicting hot items and proactively creating extra replicas. Load balancers then spread requests for popular data across more machines without physically moving partitions.
Continuously monitor each server's latency distribution. When a server becomes abnormally slow, temporarily exclude it from serving ("probation") while continuing to send shadow requests to track its recovery.
In large IR systems like Google Search, speed is itself a quality metric — returning good results quickly beats returning the best results slowly.
Once a sufficient fraction of leaf servers have responded, return slightly incomplete results rather than waiting for every last server. The chance that a specific slow server holds the best result is less than 1 in 1,000 — odds further reduced by replicating important documents across multiple servers.
Return results once an acceptable fraction of the corpus has been searched.
Non-essential subsystems (ads, spelling correction) can be gracefully skipped if they don't respond in time.
Carefully tuned to ensure "good enough" results are rare, preserving quality while protecting latency.
In high fan-out systems, a single bad request could crash or hang thousands of servers simultaneously (untested code path, malicious input). Canary requests provide a safety net.
Before fanning out to thousands of leaf servers, send the request to just 1–2 "canary" servers first.
Only proceed with full fan-out if the canary responds successfully within a reasonable time.
If the canary crashes or hangs, the request is flagged as dangerous and blocked from further execution.
State-mutating operations are easier to handle because:
The future makes these techniques more important and more effective:
The paper's enduring contribution is a paradigm shift: stop trying to prevent every latency spike, and instead build systems that are resilient to them.