Percentiles do not compose; HDR histograms
Why can percentiles never be averaged, and what recording structure keeps the tail?
Percentiles do not compose
A percentile is not a linear function of the data. This means you cannot average percentiles across shards (partitions of the data), across time windows, or across anything else. The average of ten shards' p99 values is not the fleet p99. It is not an estimate of anything. It can be far below the true value when one shard is bad, or above it when load is spread unevenly. Yuki's "average of shard p99s = 60 ms" is exactly this mistake.
The only valid operations are these. Merge the underlying distributions (histograms add together; percentiles do not). Or record the raw samples and compute the percentile once, at the end.
A fan-out makes it worse in the other direction: a request that waits for 100 backends, each meeting its own p99, sees at least one slow node about 63% of the time, so the fan-out's p99 is worse than any node's. For measurement the point is the same: only the merged distribution can show it.
This decides the architecture of measurement: store mergeable structures (histograms or sketches) at the edges, merge them centrally, and compute percentiles last.
HDR histograms and recording structures
You cannot keep every sample at high request rates, and you must choose the compression before you know the question. There are three options, and each fails in a different way.
| Option | Strength | Failure |
|---|---|---|
| Raw samples | Exact; can answer any later question | Memory and storage cost O(n); impractical above modest rates |
| Pre-aggregated means | Very cheap | Destroys everything: the irreversible case |
| Histograms and quantile sketches | Bounded memory; mergeable; exact to a declared error bound | You must know where the error sits |
A sketch is a small data structure that answers one kind of question approximately, with a known error bound. Bloom filters, HyperLogLog, t-digest and KLL are all sketches. Here they appear as measurement tools, with the same trade: bounded space and mergeability, paid for with bounded error.
The design detail that matters is where the error lives. An HDR histogram (High Dynamic Range histogram) uses buckets whose size grows logarithmically. This gives constant relative precision over a wide range: a 1 ms observation and a 10 s observation are both recorded to the same percentage accuracy (for example, within 1%). Linear buckets give constant absolute precision instead. They waste resolution at the fast end and lose it at the slow end, where the tail is. The t-digest sketch goes further and concentrates accuracy at the extreme quantiles, which is usually what you want from a latency sketch.
Small code sketch (Python, using the hdrhistogram package idea).
from hdrh.histogram import HdrHistogram
h = HdrHistogram(1, 60_000_000, 3) # 1 us .. 60 s, 3 significant digits
h.record_value(latency_us) # on every request
# later, on each node: merged.add(h) <- histograms add
# only at the end: merged.get_value_at_percentile(99.9)The failure to avoid in practice is a recording structure with a clipped maximum. Observations above the top bucket are silently set to the top value. This is censoring (the real values are hidden), and it hides the worst cases, so it errs in the optimistic direction. This is the same "instrument and subject share fate" problem as coordinated omission. If the histogram caps at 1 s, a 30 s stall looks like 1 s.