How does a metrics backend estimate a p99 latency from histogram bucket counts, and how large is the error?

## What a histogram keeps, and what it throws away A latency histogram is not a list of measurements. When the instrument is created a set of **bucket boundaries** is fixed — say 5 ms, 10 ms, 25 ms, 50 ms, 100 ms, 250 ms and 1 s — and every observation increments exactly one counter: the counter for the bucket its value falls into. Some formats store a **cumulative** count against each boundary (how many observations were at or below it); others store the count **inside** each bucket. The two carry the same information, a running sum in one direction and a difference in the other. Alongside the buckets the instrument keeps a **total count** and usually a **running sum** of every value observed. That is the entire record. The individual durations are gone the moment they are counted. Two windows in which the same 4,653 requests landed between 100 ms and 250 ms — one where they all took 104 ms, one where they all took 249 ms — are identical on the wire. ## Locating the rank Estimating a quantile from that record is a two-step procedure. 1. **Compute the target rank.** For the 99th percentile of `N` observations the rank is `0.99 x N`. 2. **Walk the boundaries** in ascending order, accumulating counts, until the running total first reaches that rank. The bucket you stopped in is the bucket that contains the value you want. At that point you know something exact and something unknowable. Exact: the answer is greater than the previous boundary and no greater than this one. Unknowable: where inside that interval it sits, because the histogram never recorded it. ## The interpolation, worked Take the billing API of a district-heating system over one window. It served 503,118 requests, with 496,802 completing at or below 100 ms and 501,455 at or below 250 ms. - Target rank: `0.99 x 503,118 = 498,086.82`. - 496,802 is below that and 501,455 is above it, so the p99 falls in the 100 ms–250 ms bucket. - That bucket holds `501,455 - 496,802 = 4,653` observations, and the rank sits `498,086.82 - 496,802 = 1,284.82` of them in — about 27.6% of the way through. - **Linear interpolation** assumes those 4,653 observations are spread evenly across the interval, so the estimate is `100 + 0.276 x (250 - 100)`, roughly **141 ms**. 141 ms looks like a measurement. It is the midpoint of an assumption. ## Why the error is exactly the bucket width The interpolation assumes a uniform distribution inside the bucket — precisely the shape the histogram discarded. Real latency inside a tail bucket is rarely uniform: it is often clustered near the lower edge, which biases the interpolated value high, or piled up against a timeout, which biases it low. Neither can be detected from counts alone. So the honest statement about that 141 ms is: **the true p99 is above 100 ms and at most 250 ms.** Nothing in the data narrows it further. More traffic does not help — it stabilises the *rank* but leaves the resolution untouched. Collecting more often does not help. Only narrower boundaries where the quantile lands do. | Question you ask of the histogram | How good the answer is | | --- | --- | | How many requests were at or below 250 ms? | Exact — it is a counted value | | What fraction finished under 250 ms? | Exact — a ratio of two counted values | | What is the p99? | Estimated — interpolated inside one bucket | | What was the slowest request? | Unanswerable — the top bucket is open-ended | | What is the mean? | Exact — the running sum divided by the count | ## The practical consequence The table suggests the move experienced engineers make: **when a number has to be defensible, ask a question the histogram can answer exactly.** Place a boundary exactly at the threshold you care about, and "what fraction of requests finished under the threshold" becomes a ratio of two counters with no estimation in it at all — a far better basis for an objective than an interpolated quantile whose uncertainty is the width of a bucket somebody chose months ago. Use the interpolated quantile for what it is good at — trend, shape, and comparison between two similar windows — and be explicit that its resolution is bounded by the bucket grid. When someone on a three-person on-call rotation is arguing at 02:00 about whether the p99 moved from 141 ms to 158 ms, the useful answer is usually that both numbers came out of the same bucket and the histogram cannot tell them apart.