Notesfoundations๐ฑ seedling
Tail Latency Amplification
Also: Tail at Scale ยท Fan-Out Latency ยท Hedged Requests ยท Tail-Tolerant Systems
When one user request fans out to many servers and waits for all of them, the slowest one sets the response time, so rare per-server slowness becomes common user-facing slowness. With 100 servers each slow 1% of the time, about 63% of requests are slow.
Why it exists
Scatter-gather is everywhere: search over shards, pages built from dozens of service calls, queries across partitions. Each extra parallel call is another draw from a distribution with a tail.
How it works
- P(at least one slow) = 1 โ (1 โ p)โฟ. For p = 1% and n = 100 that's โ 63%; for p = 0.01% and n = 2,000 it's โ 18%.
- Google measured it at the root of a large fan-out tree: p99 for one random leaf was 10 ms, for 95% of leaves 70 ms, for all leaves 140 ms.
- You can't remove variability (GC, shared machines, background work), so build tail-tolerant systems:
- Hedged requests: after ~p95 with no reply, send a copy to another replica; use the first answer and cancel the rest. Extra load โ 5%.
- Tied requests: enqueue on two replicas; whichever starts first cancels the other.
- Micro-partitions, extra replicas of hot partitions, excluding slow machines temporarily, and "good enough" partial results.
Trade-offs
| Gains | Costs |
|---|---|
| short tails without overprovisioning every server | extra requests and duplicate work |
| reuses replicas that exist for fault tolerance | only safe for idempotent reads (or with care) |
In practice
- BigTable benchmark: reading 1,000 keys across 100 servers, hedging after 10 ms cut p99.9 from 1,800 ms to 74 ms with 2% more requests.
Pitfalls
- Benchmarking a single server and extrapolating to a fan-out.
- Hedging immediately rather than after a delay: that doubles load and can tip the system into overload.
Connections
Recall
These cards are also in your review deck, scheduled with spaced repetition.