Tail at Scale

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 7 — Patterns and problems

Layer 7 · Post 4 of 5

← Previous: Strangler Fig → Next: Gossip Protocol

Layer 7 — Patterns and problems · Post 118 of 119

If one request fans out to 50 backends, the slowest of those 50 is your user-visible latency.

What you'll learn

Why p99 of a microservice is not p99 of the product
Hedged requests, cross-request cancellation, and "do not wait for the straggler"
How this ties to Little's Law, HOL blocking, and SLO latency budgets

The idea in one minute

The tail at scale (Dean & Barroso, 2013): rare slow calls are common once you fan out.

If each backend has a 1% chance of a slow request (GC, packed disk, noisy neighbor), then a request that waits for all 100 shards sees:

P(at least one slow) ≈ 1 − 0.99^100 ≈ 63%

Your user p50 starts looking like the backends' p99. SLO latency is a fan-out tax, not an average of averages.

User request
   |-- shard 1   8 ms
   |-- ...
   |-- shard 87  180 ms   <-- you waited for this
   +-- merge
User latency ≈ 180 ms + merge

Amdahl: the max of parallel RPCs is serial for the user. Little's Law: those 180 ms hold your concurrency while a straggler holds a thread.

Why it matters

This is why "every service is p99 < 50 ms" can still yield a 300 ms app. Interviews: hedged requests (send a duplicate to another replica after a short wait) and cancel the slow one; degrade optional widgets; do not put 80 sequential calls on the path (fallacies, BFF aggregation with a budget).

Cells and bulkheads limit who you fan out to. SLO error budgets (Post 114) should measure the user, not the median shard.

How it works

Reduce fan-out. Cache, BFF batch, don't call 20 services if 3 are for a below-the-fold panel — async or skip.

Hedge. After 10 ms with no reply, send the same read to a second replica; take the first success; cancel the other (otherwise you double load — the paper warns). Works for idempotent reads. Dangerous for non-idempotent writes.

Tied requests / replica selection. Prefer replicas that are not currently slow (load, queue depth) — the "good" tail of the farm.

Time-bound optional work. Reviews widget: 20 ms budget, then empty. Better a hole than a 2 s spinner (product call).

Canary / partitioned tail. One bad host should not sit on every request: least-loaded, hedge, outlier ejection (mesh). HOL (Post 97) on one connection is a tail source; HTTP/2 + timeouts.

Queueing. A server at 90% utilization makes its tail ugly (Little). Headroom is a latency feature.

A simple example

Search: 32 index shards, all required. Each shard p99 = 40 ms, p50 = 8 ms. User p50 ≈ not 8 ms; it tracks max of 32. You measure ~35–50 ms even when "the cluster is fine."

Mitigations: hedge the slowest 5% of shard calls; speculative retry on a second replica; smaller fan-out with a two-level index; deadline 80 ms and return partial results (product must agree).

A mesh that retries all 32 on the first timeout without hedging policy can amplify load (retry storm) and worsen the tail. Hedge narrowly.

Common mistakes

Reporting service p99 as UX p99. Measure at the edge (BFF, gateway, RUM).

Hedging writes. Double charge. Only hedge what is safe.

Unlimited fan-out as "microservices purity." That is a tail machine.

No cancellation. Hedged twins both run to completion; you paid 2× for the privilege.

Fixing tail only with more RAM. Sometimes it is fan-out and utilization, not a missing index (though indexes help that shard's tail).

How this shows up in real systems

Google / Bigtable / search papers: the original.
Tail latency in LMAX, AWS, Netflix talks: hedging, chaos, load shedding.
gRPC deadlines propagating down the tree — the end (Post 115) still must honor them.
Kafka / Spark: straggler tasks; speculative execution is the batch cousin.

Recap

Fan-out multiplies the chance you hit a slow replica; user latency ≈ slowest needed child.
Fewer calls, hedges, deadlines, cancel, degrade.
Last named pattern: how clusters spread facts without a boss — gossip.