Tail at scale, and why percentiles do not combine

Why does fan-out turn a healthy per-node p99 into a bad system p99, and why can't you average percentiles?

Tail at scale

(From Dean and Barroso's paper "The Tail at Scale".)

The arithmetic is short and the consequence large. Send a request to N independent nodes and wait for all. If each node is slow with probability p, then P(all fast) = (1 − p)^N.

Example: per-node p99 means p = 0.01. With N = 100: 1 − 0.99¹⁰⁰ = 1 − 0.366 = 63% of requests meet at least one slow node. Your p99 became your p63.

Equivalently, the p99 of a 100-way fan-out is about the per-node p99.99. To get two nines from the system you need four nines from the parts. The more nodes you fan out to, the stricter the tail requirement, which makes the tail a distributed-systems problem, not a single-service problem.

Independence makes this estimate too optimistic. Correlated slowness (GC pauses, a shared hot resource, a bad rack, the SLC-cache cliff from Storage media — a consumer SSD that writes fast into a small fast buffer and slows suddenly when it fills) makes real behavior worse than the formula.

Mitigations all reduce variance, and trade resources for predictability:

• Hedged requests: send a copy to another replica after the p95 time has passed. A few percent more load, a tail improvement of about 10×.
• Tied requests: send to two replicas at once, each able to cancel the other.
• Micro-partitioning: make work units small, so a slow one costs little.
• Selective replication of hot data.
• Partial results with a deadline: answer with what you have at time T.

This is the branchless-code trade from CPU and memory: pay a small guaranteed cost to remove a large variable one.

Design conclusion: reduce your fan-out where you can. N is in the exponent. Reducing fan-out from 100 to 20 helps your tail more than making every node 2× faster.

---

Percentiles do not combine

The core mistake: p99 is not a quantity. It is a position in a distribution. Averaging positions has no meaning. Averaging ten servers' p99 values tells you nothing about the p99 of the fleet; you need the merged distribution.

Three common failures in real dashboards:

1. Across servers. Merge distributions (histograms, t-digest, HDR histogram — compact structures that store the shape of a latency distribution), do not average summaries. This is why Prometheus histograms can be aggregated and Prometheus summaries cannot.
2. Across time. Averaging 1-minute p99 values to get an hourly p99 is wrong. Store the buckets and compute the percentile when you query.
3. Across sequential stages. p99(A) + p99(B) ≠ p99(A + B). If A and B are independent, the p99 of the sum is lower than the sum of p99s (both being slow together is rarer). If they are correlated, it can be higher. The simple sum is wrong in an unknown direction, which is worse than being wrong in a known one.

Most monitoring stacks average percentiles somewhere in the pipeline, silently. "We monitor p99" is a claim worth checking against your own dashboards (Check percentile aggregation in your monitoring).

---

What the performance laws forbid

What this article adds: the earlier parts explained why costs exist. This article explains why systems fail in a non-linear way. The queue hyperbola, the USL's N² term and the tail's exponent are all non-linear. Systems do not get worse in proportion. They are fine, fine, fine, and then fail suddenly. This is the most important operational fact across the platform.

And about averages: every law here is invisible in average-based monitoring. A system at 80% utilization looks fine on a dashboard and is one spike from collapse. A 100-way fan-out with healthy per-node p99 has a bad user-facing p99. Averaged p99 across a fleet can look flat while the real p99 doubles. The mathematics of this article is exactly the mathematics that averages destroy.