Percentiles at scale: t-digest and mergeable summaries

The problem with averages and with averaging percentiles

Users feel the tail: the slowest one percent of requests. So teams track p95 and p99 latency. But percentiles do not combine the way sums do.

Imagine two hosts. Host A serves 9,000 requests a minute with p99 of 100 ms. Host B serves 1,000 requests with p99 of 900 ms. The average of the two p99s is 500 ms. The true fleet p99 is close to 100 ms or more, depending on how B's slow requests are spread: the answer depends on the whole distribution, not on the two summary numbers.

So to get a fleet percentile you must merge distributions, then read the percentile. Shipping every raw value is too heavy at scale, so we need a compact summary that merges.

100%

Figure SDA-SAG-07-1 · Why percentiles must be merged as distributions · © forcsguy.com

Options for summarising a distribution

• Fixed-bucket histogram. Count how many values fall in each bucket (for example 0 to 5 ms, 5 to 10 ms ...). Merging is adding counts. Simple and common, but accuracy depends on well-chosen buckets, and wide tail buckets hide detail.
• Log-scale histograms (HDR histogram, DDSketch). Buckets grow geometrically, giving a guaranteed relative error such as 1 percent across a huge range.
• t-digest. Keeps a limited number of centroids, each a mean and a count. Cluster sizes are limited so that they are tiny near the extremes and large in the middle. The tails stay accurate while memory stays small, typically a few hundred centroids.

100%

Figure SDA-SAG-07-2 · How a t-digest spends its clusters · © forcsguy.com

The compression parameter (often called delta) trades memory for accuracy. Larger values keep more centroids.

Putting it in a metrics pipeline

1. Each service instance records latencies into a digest per metric and time slice, such as 10 seconds.
2. It sends the digest (a few kilobytes) instead of raw measurements.
3. The collector merges digests across hosts for the fleet, and across slices for longer windows (a minute, an hour).
4. The dashboard reads p50, p95 and p99 from the merged digest.

Because merging works for any grouping, you can later ask for any slice: by endpoint, region or version, as long as you kept the digests per that label.

Honest limits

• Results are estimates with an error that is smallest in the tails. State the accuracy you need.
• Merging many times can slowly increase error; keep windows sensible.
• Do not alert on a percentile computed from too few requests; small windows are noisy for any method.
• If you can afford an exact computation for a small dataset, do that. Digests are for volume.

Real-world reading