Aggregating Percentiles Across a Fleet Without Losing the Tail

A fleet of fifty hosts, each reporting its own p99, offers no direct way to compute the p99 of the fleet. The quantity that matters to a user is a property of the pooled population of requests, and the per-host summaries have already discarded the counts that would be needed to reconstruct the pool. The error this introduces is not a rounding error; it is a substitution of a different quantity.

The fix is to aggregate a structure that survives merging, and the oldest such structure is the cumulative histogram. Understanding why it works, and where it stops working, requires separating spatial aggregation from temporal aggregation, which behave differently for reasons that are easy to conflate.

The weighted-average fallacy

Suppose ten hosts each serve 1,000 requests per minute and report their p99 latency. Nine report 40 milliseconds and one reports 4,000 milliseconds. The average is $((9\cdot40) + 4000)/10 = 436$ milliseconds.

The fleet’s true p99 is much lower. The degraded host contributes 1,000 requests out of 10,000, which is 10 percent of the traffic. Its slow requests are a subset of that 10 percent, and the fleet p99 is the value below which 99 percent of the 10,000 requests fall. Only one percent of the fleet may exceed the fleet p99, which is 100 requests. If the degraded host has, say, 200 requests above 4,000 milliseconds, those 200 alone are 2 percent of the fleet, so the fleet p99 is above 4,000 milliseconds; if it has 50, the fleet p99 is below 4,000 and is set by the healthy hosts’ own tails.

The average of the per-host p99s gives 436 milliseconds in both cases. It cannot distinguish them, because the distinguishing information is a count and the average has none. The average of percentiles is not a percentile of anything, and it is not a mean of anything meaningful either; it is a statistic whose value changes discontinuously as hosts are added or removed, which is why a rolling restart can move a dashboard’s latency line without any change in user experience.

Merging cumulative histograms is exact

A cumulative histogram stores, for each of $k$ boundaries $b_1 < b_2 < \cdots < b_k$, the count of observations less than or equal to $b_i$. Its last bucket is an overflow count for everything above the highest boundary. Two histograms with identical boundaries merge by adding corresponding buckets elementwise, and the result is the histogram of the union of the observations. This is exact, has no error term, and costs $k$ additions per merge.

The exactness is what makes the structure the right one for a fleet. Each host keeps its own histogram, the aggregation layer sums them, and the percentile is derived from the sum. The percentile is then a genuine percentile of the pooled population, provided the boundaries agree across hosts.

# Cumulative histograms with a shared boundary list merge by elementwise addition.
BOUNDS = (0.005, 0.01, 0.025, 0.05, 0.1, 0.25, 0.5, 1.0)   # seconds

def merge(histograms):
    total = [0] * (len(BOUNDS) + 1)          # last slot is the overflow count
    for h in histograms:
        assert len(h) == len(total)
        for i, c in enumerate(h):
            total[i] += c
    return total

def quantile(total, q):
    n = total[-1]
    if n == 0:
        return None
    target = q * n
    for i, c in enumerate(total):
        if c >= target:
            return BOUNDS[i] if i < len(BOUNDS) else BOUNDS[-1]  # overflow: a floor
    return BOUNDS[-1]

The result is exact in the counts and bounded in the value: the quantile is reported as the first boundary whose cumulative count reaches the target, so the answer is within one bucket width of the truth and never below it.

The boundary-agreement requirement is the operational constraint that matters most. Two hosts with different boundary sets cannot be added elementwise, and the usual workaround, mapping each bucket to the nearest bucket of the other set, produces an error that is bounded by the boundary spacing in one direction and unbounded in the other, because a wide bucket can only be mapped to a narrow one by splitting it arbitrarily. This is the strongest argument for a single histogram layout configured centrally rather than chosen per service: the layout choice is not local, because it determines whether the data can be combined at all.

Quantile sketches as the finer-grained alternative

Histograms with explicit boundaries have a resolution that is uniform in absolute terms, or uniform in ratio if the boundaries are geometrically spaced, but always finite. A relative-error sketch stores a compact summary with a guarantee of the form “the reported quantile is within a factor of $1+\alpha$ of the true one”, with $\alpha$ typically in the range of a fraction of a percent. The relevant property for a fleet is that such sketches merge, and merge with the same guarantee: merging two summaries with relative error $1+\alpha$ yields a summary whose error is still bounded by $1+\alpha$ rather than accumulating.

The distinction from a histogram is what the guarantee means. A histogram’s error is an absolute interval, the width of the bucket the quantile fell into, so it is proportionally tiny near the median of a narrow distribution and could be several percent near the tail. A relative-error sketch holds the relative error constant across the whole range, which is what a latency report usually wants, since the interesting questions are about ratios: whether the p99.9 doubled, not whether it moved by 3 milliseconds.

The cost is that a sketch is not readable as raw counts. Its buckets are an implementation detail whose widths vary with the data, and a spending-downsampled or trimmed sketch can no longer be interpreted as a set of exceedance counts. When a report needs both the percentile and the count of requests above a fixed threshold, the histogram is the more honest structure, and the common deployment keeps both.

Temporal aggregation hides the tail

Merging across hosts is a merge across a population that was measured at the same time, and it preserves the tail exactly. Merging across time is different: a histogram covering five minutes holds the union of five one-minute populations, and a percentile of that union answers a question about the five-minute period as a whole.

The difference shows up with bursts. If a service has a healthy minute followed by a minute of extreme latency followed by three healthy minutes, the five-minute p99 is computed over the whole five-minute population. The one bad minute contributes a fifth of the samples, so a degradation that affects half of the requests in that minute constitutes 10 percent of the merged population, and the merged p99 is drawn from the degraded population. The same data reported as five separate minute-level p99s shows one spike and four flat minutes, and an alert that evaluates each minute independently with a threshold tuned to the merged statistic will miss it.

Neither view is wrong; they answer different questions. The one-minute series answers “did anything go wrong in this minute”, and the five-minute merge answers “what fraction of requests were affected in this window”. Choosing a merge window for an alert therefore fixes the smallest incident the alert can see. An incident shorter than the window is attenuated by the ratio of its duration to the window, so a five-minute window dilutes a ten-second stall by a factor of thirty, which is why tail alerting usually uses short windows and rate-based comparisons rather than a single long-window percentile.

Rate-based comparison sidesteps the dilution. Instead of asking whether the percentile crossed a threshold, it asks whether the count of requests above a fixed latency exceeded a rate, for example more than 100 requests per second above 500 milliseconds for five consecutive minutes. The count is unaffected by changes in traffic volume, so the same threshold means the same thing during peak and off-peak, which a percentile threshold does not.

Percentiles of percentiles in a hierarchy

Multi-tier aggregation, where each tier’s summary becomes an input to the next, reintroduces the weighted-average fallacy at every level unless each tier forwards a mergeable structure. A summary that forwards only a percentile is lossy at that hop, and the loss compounds.

The hierarchy also raises a consistency problem that counts do not have. Two tiers may window their data differently, so a top-level five-minute percentile may be assembled from second-tier summaries whose windows are offset, producing a figure that is a percentile of a population no single measurement ever observed. With cumulative counters this is harmless, because counters are monotone and differences across arbitrarily aligned snapshots are well defined; with precomputed percentiles the alignment determines the answer.

The practical consequence is that a latency figure that traverses a hierarchy of precomputed summaries should be reported with its sample count, so that a reader can tell whether the number rests on a population large enough to support the percentile requested; the sample-count arithmetic that governs a single host’s stability, treated in Means, Percentiles, and What a Tail Measurement Can Answer, applies unchanged to the merged population. The merged population is larger, which is the one advantage of aggregation: a fleet-wide p99.9 over a five-minute window at a million requests a minute rests on five million samples, of which five thousand are above the threshold.

When the fleet is not homogeneous

Aggregating across hosts with different hardware, different code versions, or different traffic mixes produces a valid pooled percentile and a misleading operational picture. A pooled p99 that is stable while half the fleet has regressed and half has improved is a real possibility when the fractions are chosen adversarially, and it is consistent with a deployment in which only half the hosts received a new version.

The remedy is not to abandon pooling but to keep the pooled figure alongside a per-group breakdown, since the pooled number is what a request experiences (requests are distributed across the whole fleet) and the breakdown is what identifies the cause. The breakdown requires that the group label be attached to the histogram rather than inferred later, because a per-host percentile has already lost the correspondence between its samples and their labels.

There is one case where pooling is not merely less diagnostic but actually wrong: when the traffic is partitioned such that a subset of the population can never reach certain hosts, as in a sharded service where each key maps to one shard. The fleet-wide percentile then mixes populations that are independent, and a single hot shard’s latency does not average away. In that arrangement the meaningful unit is the shard, and the fleet figure should be reported alongside the worst-shard figure, because the worst shard is what a fraction of the keys experience all of the time. That asymmetry, where a whole user request waits on the slowest member of a set of parallel calls, is the mechanism treated in Work Distribution, Join Barriers, and Idle Time at the End of a Stage.