The Tyranny of the Tail: Why Averages Lie
In distributed systems, the average response time (mean) is virtually meaningless. If a service has an average latency of 10ms but a 99th percentile (p99) latency of 2,000ms, one out of every 100 users experiences a 2-second stall. In fan-out architectures, tail latency is amplified: if each of N backends is slow 1% of the time, the chance a request hits at least one slow backend is 1 - 0.99^N.
Fan-Out Tail Latency Amplification
Mitigating Tail Latency: Dean and Barroso's "The Tail at Scale"
- Hedged Requests: If a request to a backend node does not return within the 95th percentile expected latency (e.g., after 50ms), immediately send an identical request to a replica server. Whichever server replies first provides the result, and the other request is canceled. Hedging at the 95th percentile caps the extra load at about 5%. In the paper's Bigtable benchmark, hedging after 10ms cut p99.9 latency from 1,800ms to 74ms (about 96%) while sending only about 2% more requests.
- Tied Requests: Submit the request simultaneously to two server queues with mutual cancellation tokens. When one server begins execution, it notifies the other to dequeue the request.
- Coordinated Omission: Benchmark tools often pause while waiting for a slow request, inadvertently omitting the queueing delays experienced by real users during that stall. Accurate tail measurement requires a constant-arrival-rate (open-model) load generator such as Gil Tene's wrk2; HdrHistogram records the full latency distribution and can optionally correct recorded data for an expected interval.
Worked example: fan-out amplification
Each leaf server answers within 10 ms 99% of the time, and its slow 1% takes about 1 s (a GC pause, a disk hiccup, a noisy neighbour).
| Leaves a request waits for | Chance all are fast (0.99 to the power N) | Requests that hit at least one slow leaf |
|---|---|---|
| 1 | 99% | 1% |
| 10 | about 90.4% | about 9.6% |
| 100 | about 36.6% | about 63.4% |
| 1,000 | about 0.004% | almost all |
This matches the example in Dean and Barroso's "The Tail at Scale" (CACM 2013): with 100 leaves, 63% of user requests take over 1 s. To keep the combined p99 at 10 ms with 100 leaves, each leaf would need to be fast 99.99% of the time (0.9999 to the power 100 is about 99%).
Hedged requests, with numbers
A hedged request sends a second copy to another replica only if the first has not answered within, say, the 95th percentile latency. At most about 5% extra load is added. In the paper's Bigtable benchmark, reading 1,000 keys spread over 100 servers, hedging after a 10 ms delay cut the 99.9th percentile latency from 1,800 ms to 74 ms while sending only about 2% more requests.
Tied requests go further: the request is enqueued on two servers at once, each copy knowing about the other; whichever starts first sends a cancellation to the other. This avoids the wait before hedging but needs server cooperation.
Techniques and trade-offs
| Technique | Helps with | Cost or risk |
|---|---|---|
| Hedged requests | Random slow replicas | Extra load; only for idempotent reads |
| Tied requests with cancellation | Queueing delay variation | Server-side coordination |
| Micro-partitioning (many small shards per server) | Rebalancing hot or slow servers quickly | More metadata |
| Good-enough results (return partial results after a deadline) | Search and feeds where completeness is optional | Slightly lower quality answers |
| Reducing variability (GC tuning, request prioritisation, background work throttling) | Root causes of slow tails | Engineering effort |
| Fewer sequential hops | Compounding tails in chains | Architecture change |
Measuring the tail correctly
- Record latencies into histograms (for example HdrHistogram, or Prometheus histograms with well-chosen buckets) and merge them; do not average percentiles.
- Use an open-model, constant-arrival-rate load generator (for example wrk2 or k6 constant-arrival-rate) so slow responses do not suppress the requests that would have been sent. HdrHistogram can also correct recorded data for an expected interval, but the correct fix is in the load generator.
- Include failures and timeouts as slow results, not as missing samples.