Percentile sketches

A food-ordering service runs its checkout API on 300 servers. Its target is that 99% of checkouts finish within 1 second, so the dashboard needs the fleet's p99, per minute, per region and per day. In one hour the fleet handles a million checkouts.

The exact p99 means keeping all million durations, sorting them, and reading the value 99% of the way up. Doing that for every minute, region and endpoint is expensive, and each server's own p99 is no shortcut: percentiles can't be averaged or added, because the fleet's slowest 1% may all sit on a few servers (Latency). What the service needs is a summary that is:

Such a summary is a quantile sketch. Four designs are common, and the first is one most teams already use without calling it a sketch: the histogram.

A histogram counts how many values fall in each of a set of ranges, its buckets. Prometheus's default buckets for request durations are 5, 10, 25, 50, 100, 250 and 500 ms, then 1, 2.5, 5 and 10 seconds. Merging is exact: add the counts bucket by bucket, across servers or minutes.

Reading a percentile is not exact. The histogram knows the p99 is in, say, the 500 ms to 1 s bucket, but not where. Prometheus's histogram_quantile assumes the values are spread evenly inside the bucket and interpolates. On a simulated hour of a million checkouts, the true p99 was 805 ms; the default buckets reported 863 ms, 7% high, and the p99.9 came out 2,409 ms against a true 2,158 ms.

Coarse buckets can mislead badly when values cluster. Suppose almost every request takes about 220 ms, there are bucket boundaries at 200 and 300 ms, and the target is a p95 under 300 ms. Interpolation puts the p95 at 200 + 0.95 × 100 = 295 ms, apparently on the edge of breaking the target, when it is really 220 ms.

Fixed buckets work well when you choose the boundaries for the question:

• Put a boundary exactly at each target, here 1 second. The share of checkouts over 1 s is then exact, and an alert can fire on it directly.
• Add boundaries where the interesting values live, dense around the target, sparse elsewhere.
• Never change boundaries casually: histograms with different boundaries can't be added.

Sketches promise one of two kinds of accuracy, and the difference matters most exactly where the dashboard looks:

• Rank error: the answer to "what is the p99?" is a value whose rank is within ±ε of the 99th percentile. With ε = 0.5%, any value between the p98.5 and the p99.5 is a correct answer.
• Relative error: the answer is within ±α of the true p99's value. With α = 1%, it is within 1% of 805 ms.

In the middle of a distribution, values are packed close together, so a small rank error is a small value error. In the tail they spread out. In the simulated hour:

Latency has a long tail, because a few requests hit a slow dependency, a retry or a garbage-collection pause. That is why sketches built for monitoring tend to promise relative error: the value at p99 is what alerts and targets compare against, so the value is what must be right.

The fix for coarse buckets is buckets whose width grows with the value: 2 ms wide near 100 ms, 16 ms wide near 800 ms. If each bucket's upper edge is a fixed ratio γ times its lower edge, every value lands in a bucket about the same share of itself wide, 2% for a 1% error. This is the idea behind DDSketch:

The arithmetic stays small. With α = 1%, covering everything from 1 ms to 60 seconds takes ⌈ln(60,000) ÷ ln(1.0202)⌉ = 551 buckets, and only buckets that received values need storing: the simulated hour used 311. The sketch's p99 was 811 ms, 0.7% from the truth, and its p50 and p99.9 were within 0.3%.

Merging is the same as for any histogram, because every sketch with the same γ has the same bucket edges: add the counts. Splitting the million checkouts across 300 simulated servers, sketching each and adding the sketches gave exactly the sketch of all of them. If a sketch must be capped in size, DDSketch merges its lowest buckets first, so the high percentiles keep their accuracy and only the very low end gets blurrier.

HdrHistogram's footprint is fixed by its range and precision, never by the number of values, and recording a value took 3 to 6 nanoseconds even on 2012-era CPUs. Prometheus's native histograms bring the same idea to monitoring: no bucket boundaries to choose, and histograms using the standard schemas can always be merged.

Two other families don't use fixed buckets at all. t-digest keeps a small set of centroids, each a mean value and a count. It deliberately keeps the centroids near the extremes small, so accuracy is relative to how close the percentile is to 0 or 100: p99.9 is resolved much more finely than p50. Its errors are a few parts per million at q ≤ 0.001 and q ≥ 0.999 while keeping only about 50 to 60 centroids (compression 100), and separately built digests can be combined.

KLL keeps a carefully thinned sample of the values. It guarantees rank error: every answer's rank is within ε × n of the requested one. Its size is asymptotically optimal for that guarantee, and it is mergeable. BigQuery's KLL functions use it.

For latency, the long tail favors value accuracy, so the checkout service picks log buckets. For a warehouse query such as "the median order value per city", where values are bounded and the middle matters, a rank guarantee is fine.

The rule that makes all of this work: keep sketches, not percentiles. Each server records a sketch per minute and sends it on. The monitoring system adds sketches into whatever the dashboard asks for, a region, an hour, the whole fleet, and only then reads off the percentile. A stored p99 is a dead end; a stored sketch can still answer next week's question about p99.9.

For the checkout service, the checklist:

• Never average or add percentiles; merge sketches, then compute.
• Prefer relative-error sketches for latency, such as native or exponential histograms or DDSketch.
• With fixed buckets, put a boundary at every target, and alert on the share above it.
• Use the same configuration everywhere: same buckets, γ or schema, or the sketches won't merge.
• Know the guarantee: rank error looks precise and can be far off in the tail.