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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.