Tail latency amplification: when one request waits for the slowest of a hundred

What it is

A request that fans out to N backends in parallel (shards, microservices, tool calls) completes when the slowest of the N replies arrives. If each backend answers slowly with probability p, independently, the whole request is slow with probability 1 − (1 − p)^N. With p = 1% and N = 100 that is 1 − 0.99^100, about 63% (arithmetic). Dean and Barroso's "The Tail at Scale" states that temporary high-latency episodes which are unimportant in moderate-size systems may come to dominate overall service performance at large scale, and argues for building latency tail-tolerant systems in the way fault-tolerant systems are built from unreliable parts. The SRE book states the same effect from the monitoring side: the 99th percentile of one backend can easily become the median response of the frontend.

Why it matters

Improving each backend's median does nothing for the fan-out request. Any composition of parallel calls is exposed: a page that queries a dozen services, a search over shards, an agent that calls several tools before answering. Sequential chains add their latencies instead of taking the maximum, but a long chain of p99s is no better.

How to apply

• Measure the leaf p99 and the root p50 on the same graph; if the root median tracks the leaf tail, amplification is the cause, not the root's own code.
• Reduce N: larger partitions, fewer services per request, cached results for the leaves that rarely change.
• Hedge: after a delay equal to, say, the leaf's p95 latency, send the same request to a second replica and take the first answer. Hedging after the p95 duplicates at most 5% of requests (arithmetic). The paper also describes tied requests, where the second copy is cancelled as soon as the first begins execution.
• Set a deadline at the root and return a good-enough result from the leaves that answered in time, marked as partial, instead of waiting for the last one.
• Remove leaf tails at their source: garbage-collection pauses, background compaction, cold caches, noisy neighbours; stagger scheduled background work across replicas.
• Give every leaf call its own timeout and the root an overall budget so that one stuck leaf cannot hold the request.

Pitfalls

Hedging a non-idempotent operation duplicates its side effect. Hedging every request doubles load and worsens the tail under saturation; hedge only after a percentile delay and cap the hedge rate. Retries at every level of a fan-out multiply the load on an already slow backend. The formula assumes independent leaves; a shared database or shared host correlates their slowness, which makes the tail worse than the formula, not better.

Hedging safely

A hedge delay taken from live percentiles feeds back on itself: hedges add load, which raises the percentile, which moves the delay, and under saturation every hedge is work the leaf had no capacity for. Use a fixed delay chosen offline from a quiet period's percentile, cancel the losing copy as soon as one answer arrives (the paper's tied requests), and cap hedges at an explicit fraction of traffic with a budget that stops hedging when failures or queue time rise; gRPC's hedging policy (hedgingDelay, maxAttempts, retry throttling) and Envoy's per-try-timeout hedge policy implement exactly these controls. Hedge only idempotent calls, never at more than one level of a fan-out, and turn hedging off entirely when the leaf's queue time is climbing, because then the second copy waits in the same queue as the first.