Here is a sentence that has quietly lied inside many dashboards:

global p95 = average(service p95s)

Sometimes the lie is small. Sometimes it is enormous.

A percentile is not a scalar measurement like total bytes or request count. It is a rank statement about a population:

95% of the observations are at or below this value

If you split that population across shards, hosts, regions, tenants, or time windows, each local p95 answers a different question. Averaging those answers does not reconstruct the global order statistic. Even traffic-weighting the local p95s does not generally fix it.

The missing object is not a better mean. It is the line of people waiting to be counted.

A Rank Has an Address

For sorted observations

\[x_{(1)} \le x_{(2)} \le \cdots \le x_{(n)},\]

one common empirical (p)-quantile is the item at rank

\[\lceil pn \rceil.\]

That definition is already a warning. The quantile depends on the relative order of all observations. It is not a linear statistic:

\[q_p(A \cup B) \ne \frac{|A|q_p(A)+|B|q_p(B)}{|A|+|B|}\]

in general.

The counterexample can be tiny. Suppose shard A has 950 fast requests and 50 slow ones. Shard B has 10 very slow requests. The p95 of B is very slow, but B may contribute too few samples to move the global p95 much. Or the reverse can happen: a small shard can hide a concentrated tail that matters for a tenant but barely moves the service-level percentile.

The number is answering a population question. Change the crowd, change the answer.

The Dashboard Wants a Mean

Distributed systems love associative aggregates:

sum counts locally, then sum again globally
sum bytes locally, then sum again globally
sum errors locally, then sum again globally

Percentiles do not behave like that. A local p95 throws away almost everything about the local distribution except one threshold. Once the other ranks are gone, the central aggregator cannot know whether the local p95 was surrounded by a dense wall of samples or by a sparse tail.

This is the same reason histograms, sketches, and raw samples exist. They keep some shape.

Greenwald and Khanna’s 2001 paper framed the streaming quantile problem as maintaining a small summary that can answer any quantile query within rank error (\epsilon n), without storing the whole stream.1 That phrase is the key: the approximation is about rank, not directly about milliseconds or dollars or feature values.

Later work sharpened the space tradeoffs. Karnin, Lang, and Liberty’s KLL sketch resolved an important randomized version of the streaming quantile problem, giving a compact sketch with additive rank-error guarantees.2 Dunning and Ertl’s t-digest takes a different practical route, clustering samples so it can give especially good tail accuracy and support merging separately computed summaries.3

The algorithms differ. The shared bargain is:

preserve enough rank structure to answer quantile questions later

Let the Shards Mislead You

The lab below simulates latency streams split across shards. One shard may be small but hot-tailed; another may be large and boring. It compares:

  1. the true global percentile from all raw samples,
  2. the unweighted average of local shard percentiles,
  3. the traffic-weighted average of local shard percentiles,
  4. a small mergeable toy rank sketch.

The sketch in this article is deliberately simple: each shard sorts its samples, keeps weighted rank buckets, and the coordinator merges and recompresses those buckets. It is not GK, KLL, or t-digest. It is a pedagogical sketch so the invariant is visible: a mergeable summary carries weighted rank mass, not only a single local percentile.

True global percentile Average of shard percentiles Traffic-weighted average Merged sketch

Deterministic toy experiment. The sketch uses weighted rank buckets and merge/recompress; it is for visualization, not a production implementation or formal replacement for GK, KLL, DDSketch, HDR Histogram, or t-digest.

Start with the default. The true global p95 is 82.5 ms. The unweighted average of shard p95s says 211.4 ms, because it gives the tiny hot-tailed shard the same vote as the busy shard. Traffic-weighting is better at 102.4 ms, but it is still averaging thresholds rather than merging ranks. The toy merged sketch lands at 71.6 ms, with rank error around -0.73 percentage points.

I also swept 729 combinations of shard count, sample count, imbalance, tail severity, percentile, and sketch budget. The generated sample totals stayed consistent, and the worst averaging mistakes were hundreds of milliseconds off. The lab is intentionally synthetic, but the failure mode is real.

Now raise Percentile toward p99. Tail estimates become harder because there are fewer samples in the region that matters. The value error can jump even when rank error remains modest. This is why quantile sketch guarantees are usually phrased in rank space.

Finally lower Sketch budget. The blue estimate starts to wobble. A sketch is not magic; it is a controlled loss of rank information. More centroids buy more rank resolution.

Rank Error Wears Value Clothes

A one-percent rank mistake can be harmless near a flat part of a distribution and catastrophic in a steep tail.

Latency distributions often have exactly that shape. The median may live in a dense cluster of ordinary requests. The p99 may sit on a cliff where a tiny rank change moves the reported value from “slow” to “incident.”

That is why a sketch can have a clean rank guarantee and still surprise you in value units. The guarantee says something like:

the returned item has rank within epsilon n of the requested rank

It does not say:

the returned latency is within epsilon milliseconds

If the service distribution has a vertical wall in the tail, rank-accurate answers can have large value movement. This is not a failure of the guarantee. It is the shape of the data talking.

A Sketch Is an Interface

For a distributed observability system, a quantile sketch is not only a data structure. It is an interface contract between local collectors and central aggregation.

The collector promises:

I will send a compact object that preserves enough weighted rank mass

The coordinator promises:

I will merge those objects and answer rank queries from the merged population

That is a different contract from “send me p95.” Sending one percentile makes the upstream system choose the query before the population is even assembled. Sending a sketch delays that choice.

This matters operationally:

  • you can ask for p50, p95, p99, and p99.9 from the same summary;
  • you can merge regions, tenants, or time windows without raw samples;
  • you can inspect rank error instead of pretending local thresholds average;
  • you can choose different sketches depending on whether you care about tails, worst-case rank guarantees, merge cost, update speed, memory, or deletions.

The right sketch depends on the system. The wrong aggregator is easier to name: do not average percentiles and call the result global.

Bring the Population Back

The median of medians is not generally the median.

The average of p95s is not generally the p95.

The traffic-weighted average of p95s is still not generally the p95.

These facts feel annoying because dashboards want tidy merge functions. But the annoyance is the point. A percentile is not a scalar. It is a question about where a rank lands in a population. If the population is distributed, the evidence you merge has to preserve enough of the ordering.

The global p95 is not hiding inside the local p95s.

It is hiding inside the ranks they threw away.

Reading Trail

  1. Michael Greenwald and Sanjeev Khanna, “Space-Efficient Online Computation of Quantile Summaries,” SIGMOD, 2001. ACM, PDF. ↩

  2. Zohar S. Karnin, Kevin Lang, and Edo Liberty, “Optimal Quantile Approximation in Streams,” FOCS, 2016. arXiv, PDF. ↩

  3. Ted Dunning and Otmar Ertl, “Computing Extremely Accurate Quantiles Using t-Digests,” arXiv, 2019. arXiv, project, paper PDF. ↩