A histogram keeps counts per bucket and throws the values away, so a percentile read from it is known only to the width of the bucket it lands in. On logarithmic boundaries every bucket has the same relative width, ratio − 1, so the usual ratio of two means every percentile is known to within a factor of two — a hundred per cent relative error that does not shrink with more traffic, because it is not noise.
Core ideas
A histogram is a lossy compression with a known loss, which is a better object than it sounds. The three ideas are what is lost, how much, and why the loss does not respond to more data.
Each request increments the counter for the bucket its latency fell in, and the latency itself is gone. What survives is enough to say how many requests were below any boundary, which is enough to find which bucket a given rank falls in — and not enough to say where inside that bucket it fell. The percentile is therefore an interval: the bucket, reported as [lower, upper).
With edges in a geometric progression b, b·r, b·r², …, a bucket starting at x ends at r·x, so its width relative to its own position is (r·x − x)/x = r − 1 everywhere. At r = 2 that is 100% in every bucket, at the bottom of the range and at the top. The choice of r is a choice of precision, made once, and it applies uniformly.
The error bar of “SLIs as Ratios” shrinks as 1/√n; this one does not shrink at all. Ten times the requests put ten times the counts in the same buckets and the answer is still an interval of the same relative width. The two errors compose: a percentile from a histogram is uncertain by a rank that moves with the noise and by a bucket that does not move at all.
The material
How a rank is located in a table of counts, what the answer is an interval of, and why interpolating inside the bucket invents a digit.
A histogram over boundaries e₀ < e₁ < … < e_k stores, for each bucket [eᵢ, eᵢ₊₁), the count of observations falling in it, plus an underflow count below e₀ and an overflow count at or above e_k. The bucketed q-th percentile is the bucket containing rank ⌈q·n⌉ in the cumulative counts. Its value is that bucket, not a number inside it.
Boundaries are chosen once, before any data arrives, and they are chosen geometrically because latency spans orders of magnitude: a millisecond and a second belong in the same picture, and equal-width buckets that resolve the first give thousands of empty ones before the second. The lab’s preset starts at 25 ms and doubles.
The exact p99 of that sample is 137 ms: sort the hundred values and take the 99th. The histogram cannot say 137. It can say that the 99th value is at least 100 and less than 200, which is true, useful, and a hundred milliseconds wide.
Let the boundaries be eᵢ = b·rⁱ with r > 1. A value reported as lying in [eᵢ, eᵢ₊₁) is known to within an absolute width eᵢ₊₁ − eᵢ = eᵢ(r − 1), so relative to the smallest value it could be, the width is
(eᵢ₊₁ − eᵢ)/eᵢ = r − 1,
independent of i. At r = 2 every bucketed answer is known to within a factor of two — 100% — and at r = 5/4 to within 25%. The price of the smaller r is buckets: covering the same range needs ln 2 ÷ ln(5/4) ≈ 3.1 times as many.
That factor of 3.1 is not free, and the bill arrives in a different lesson. Every bucket is a time series with its own label value, so tripling the buckets triples the series count and the storage, which is the arithmetic of “Metric Cardinality”. Resolution in a histogram is bought with cardinality, and the exchange rate is known in advance.
On the sample above with r = 2, the p99 is [100, 200) — a width of 100 ms around a true value of 137. Refine to r = 5/4 starting at the same 25 ms and the boundaries near the answer become …, 119.21, 149.01, …; the same rank now lands in [119.21, 149.01), a width of about 30 ms. The true value did not move and no new requests were collected. The report got narrower because the boundaries did.
It is tempting, and most metrics systems do it: assume the observations are spread evenly across the bucket and read off a point. On the sample above, linear interpolation inside [100, 200) returns a confident 200 ms — the top of the bucket, since rank 99 is the last of the nine observations in it — against a true 137. The assumption of uniformity is wrong in the direction that matters, because latency inside a bucket is not uniform; it is concentrated near the bottom, which is why the bucket boundaries were geometric in the first place.
Interpolation does not add information. It converts an honest interval into a point whose error you can no longer see, and the point is not even guaranteed to be inside the range of the data. Report the interval; if it is too wide to act on, change the boundaries rather than the arithmetic.
Everything the previous page needed. Counts add, so histograms from many hosts merge exactly, and a percentile read from the merged histogram is a real fleet percentile with a known interval around it. That is a strictly better object than an averaged per-host percentile, which has no interval around it because it is not an estimate of anything.
It is also the right place to be honest about what a dashboard can promise. A p99 of “about 150 ms” from r = 2 buckets means somewhere in [100, 200); a regression from 137 ms to 195 ms would not move the reported bucket at all, and a regression from 199 to 201 would move it a whole bucket. Alerting on a bucketed percentile inherits both behaviours, and choosing boundaries so that the values you care about are not near an edge is part of the design.
Interactive
The interval a histogram can actually report, and the factor it is known to
Method
Four steps, and the last one is the difference between a measurement and a number.
⌈q·n⌉ where n is the total count across every bucket, including the underflow and the overflow. Getting n wrong by forgetting the overflow bucket moves the rank and can move the answer by a whole bucket.
Add the bucket counts from the bottom. The first bucket whose cumulative total reaches the rank is the containing bucket. If the rank is only reached in the overflow bucket, the honest answer is “at least e_k” and the boundaries are too low for this workload.
[100, 200), not 150 and not 137. The half-open interval matters when a boundary is also a common value — a 100 ms timeout piles requests exactly on an edge, and which side they land is a convention you should know rather than discover.
r − 1. It is the same number for every bucket and it is the honest precision of every percentile the histogram will ever report. If it is wider than the change you need to detect, the boundaries are wrong and no amount of traffic will fix them.
One hundred requests, boundaries starting at 25 ms and doubling. The exact answer and the reportable answer are computed from the same sample by the same rule, which is what makes the gap between them a property of the boundaries rather than of the method.
The last line is the one that separates this error from the one on the first page of the course. Sampling noise shrinks as 1/√n; bucket width does not shrink at all. A dashboard showing a bucketed p99 over a month of traffic is showing an interval exactly as wide as the one it showed after five minutes.
Notice the empty [200, 400) bucket and the single observation in [400, 800). That lone request is the p100, and the histogram places it within a factor of two as well: somewhere in [400, 800). If your maximum matters, r = 2 says it to one significant figure.
For faded practice, keep the sample and the base of 25 and set the ratio to 3/2. The supplied first move is that the boundaries become 25, 37.5, 56.25, 84.375, 126.5625, 189.84…. Predict which bucket rank 99 lands in and what the relative width becomes, then check both in the lab and count how many buckets it now takes to reach 800 ms.
You should be able to locate a rank in cumulative bucket counts, name the containing bucket with both ends, compute the relative width r − 1, say how many buckets a finer ratio costs over the same range, and explain why neither number moves when the traffic does.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.