Histogram Buckets, the +Inf Bucket, and How Quantiles Are Interpolated

A latency distribution is the thing operators actually want and the thing metrics formats are worst at carrying. A mean hides the tail; a maximum is a single sample and therefore noise; a percentile computed on the server from raw values requires storing every value. The histogram is the compromise: a fixed set of boundaries, a count per boundary, and an acceptance that the answer is an interval rather than a number.

The compromise is worth understanding in detail because the errors it introduces are not random. They are bounded, directional, and predictable from the bucket layout, which means a reader who knows the layout can state how wrong a reported percentile can be.

Counts per bucket, not values

A histogram instrument holds an array of counters, one per configured boundary, plus an overflow counter. Recording an observation of value $x$ increments the counter for the first boundary greater than or equal to $x$. Nothing about $x$ is retained beyond which interval it fell into. A histogram with twelve boundaries stores thirteen counters and can describe a distribution of millions of observations in a fixed, tiny amount of memory.

Two layout conventions exist and they differ in a way that matters for merging. In the non-cumulative form, each counter holds only the observations that fell strictly within its own interval, so the counters sum to the total count. In the cumulative form, each counter holds the number of observations less than or equal to its boundary, so the counters are monotonically non-decreasing and the last finite one plus the overflow equals the total.

Cumulative layout is what most exposition formats use, and the reason is merging. Two histograms of the same layout merge by adding corresponding counters, and the result is the histogram of the union of the observations, with no bookkeeping. Non-cumulative layout merges the same way, since addition is elementwise either way; the advantage of cumulative appears at query time, where the count in any interval is a single subtraction of adjacent counters rather than a sum over a range. That matters when the query engine is scanning millions of series and the difference between one subtraction and $k$ additions per series is a real cost.

The overflow bucket has no upper bound and is usually labelled +Inf. It exists because the boundary set is fixed at instrumentation time and the observed distribution is not. Without it, observations above the largest boundary would be silently discarded, and the total count would disagree with the sum of the buckets, which is the kind of inconsistency that turns into a support ticket.

Quantile estimation is interpolation between boundaries

To estimate the $q$-th quantile, the cumulative counts are scanned until the running count first reaches $q \cdot N$, where $N$ is the total. That identifies a bucket. The estimate then interpolates linearly inside the bucket:

$$ v \approx b_{\text{lower}} + (b_{\text{upper}} - b_{\text{lower}}) \cdot \frac{qN - c_{\text{lower}}}{c_{\text{upper}} - c_{\text{lower}}} $$

where $c$ is the cumulative count at each boundary. If the target bucket is the overflow bucket, the estimate is the lower boundary of that bucket, which is the best available statement: the value is at least this large and unbounded above.

The formula makes one substantive assumption: observations inside a bucket are uniformly distributed across its width. That assumption is false for latency, which is right-skewed and concentrates near the low end of any interval it occupies. The consequence is a systematic bias. When the true distribution within a bucket is denser near the lower boundary, linear interpolation places the quantile too high, because it assumes the mass is spread evenly rather than piled at the bottom. The error is bounded by the bucket width, so the reported value is always within one bucket width of the truth, but it is not centred on the truth.

That bound is the only guarantee available, and it is why bucket layout matters more than bucket count. Twenty boundaries spaced uniformly across 0 to 1000 milliseconds give a 50-millisecond resolution near the median and near the tail, which is fine for a median and useless for a 99th percentile in a service whose tail sits at 800 milliseconds. A layout with boundaries clustered at the high end gives the opposite. The relative error at a quantile is roughly the bucket width divided by the value, so equal relative spacing, with boundaries at 1, 2, 4, 8, 16, bounds relative error uniformly, at the cost of coarse resolution at small absolute values.

What aggregation does to a percentile

A single histogram answers a percentile honestly, within its bucket bound. A sum of histograms also answers a percentile honestly, provided the layouts are identical, because the sum is the histogram of the pooled observations. This is the property that makes histograms the right instrument for a fleet: per-instance histograms can be added in the query layer, and the 99th percentile of the sum is the 99th percentile of all requests across all instances.

The alternative, computing a percentile per instance and then averaging the percentiles, is not the same number and is not a percentile of anything. The mean of ten per-instance 99th percentiles is dominated by whichever instance happened to have the worst tail, and it changes discontinuously as instances are added or removed. There is no weighting that repairs this, because the operation discards the counts that would be needed to weight correctly.

Averaging histograms works only if the bucket boundaries match. Two histograms with different boundary sets cannot be added elementwise, and the usual fallback of assigning each bucket to the nearest bucket of the other layout loses accuracy in a way that is hard to bound. This is the operational argument for a single boundary set across a fleet, and it is also the argument for not letting individual services choose their own latency buckets: the choice is not local, because it determines whether the data can be aggregated at all. The general problem of operations that do not survive aggregation is treated in Aggregation Laws: Which Metric Operations Commute.

Bucket count is a cardinality decision

Each histogram series is not one series. It is one series per bucket, per label combination. A histogram with twelve boundaries and a method label with eight values produces $13 \times 8 = 104$ series for one logical instrument. Add a status label with five values and the same instrument becomes 520 series. This multiplicative growth is the single most common cause of metric storage problems, and it is invisible at instrumentation time because the code records one observation into one object.

The interaction with quantile queries is worth stating explicitly: a percentile computed over a histogram with too few buckets is precise but wrong, and a percentile over too many buckets is precise but unaffordable. The usual resolution is to bound the bucket count (ten to fifteen is typical for explicit layouts) and to accept the resulting error, or to move to a layout whose boundaries are generated rather than listed, which is what Exponential Histograms and the Mergeable Bucket Layout describes.

Failure modes at the edges

Zero observations in a bucket produce a division by zero in the interpolation formula when the target bucket is empty, which happens whenever the quantile falls exactly on a boundary and the scan lands on the next bucket. Implementations handle this by returning the boundary rather than interpolating, which is correct but produces a visible discontinuity in the graph as the quantile crosses a boundary.

The overflow bucket produces a different discontinuity. Any quantile above the fraction of observations that fit under the largest boundary returns exactly that boundary, so a graph of the 99.9th percentile flattens against the top boundary whenever more than 0.1 percent of observations overflow. The flat line looks like a stable tail and is actually a censored measurement.

Finally, histograms cannot be subtracted reliably. A histogram difference, used to compute the distribution over a window from two cumulative snapshots, is only valid if no bucket counter reset between the snapshots, and counters reset on restart. The result of subtracting across a restart is negative counts in some buckets, which propagate into the interpolation as a nonsense quantile. The reset handling that makes counters usable does not extend to histograms, because the per-bucket corrections would each need to know whether that bucket’s drop was a reset or a real decrease.