skip to content

When a 99th percentile is computed from bucketed latency counts, what error do the bucket boundaries introduce?

level: seniorimportance: nice to knowfreq 22%

answer

  1. You located a bucket, not a value
  2. Interpolation assumes a spread that is absent
  3. Relative width fixed, absolute width grows
  4. An unbounded top bucket reports nothing
  5. Differences narrower than a bucket mean nothing

basics

~20 s

The read-out locates the bucket holding the ranked request, not its time, so the figure carries that bucket's width as uncertainty. Interpolating inside assumes a spread the slow end does not have, and an unbounded top bucket reports nothing at all.

solid answer

~50 s

Counting requests per latency bucket keeps the counts, not the times. Reading a percentile means walking the cumulative counts to the bucket that holds the target rank, so what you have located is **a bucket, not a value** — the true time is somewhere between that bucket's edges, and the figure inherits the bucket width as its uncertainty. Interpolating a point inside the bucket does not remove that; it assumes samples are spread evenly across the bucket, and at high percentiles the density is falling, so they pile towards the low edge and the interpolated point is biased. Layouts usually widen geometrically to hold *relative* error roughly constant, which means **absolute** error grows with the value — a few percent of 40 ms is nothing, a few percent of four seconds is hundreds of milliseconds. Report the figure as an interval, and never call a difference narrower than a bucket a change.

code

pseudocode · 17 lines
pseudocode
# reading a high percentile out of per-bucket counts
target_rank = 0.99 * total_count
running = 0

for b in buckets:              # ordered from the low edge upwards
    running = running + b.count
    if running >= target_rank:
        if b.is_overflow:
            return { above: b.low_edge }   # no figure exists
        return { low: b.low_edge, high: b.high_edge }

# a point estimate inside the bucket assumes an even spread
# that the slow end of the distribution does not have

# merging is legal only when the edges match
assert edges(left) == edges(right)
merged = [left.count[i] + right.count[i] for i in range(len(edges))]

go deeper

for a junior

Recall that counting requests per latency bucket keeps how many landed in each range, not the individual times, so any percentile read back from it is located to a range rather than to a value.

for a middle

Explain the read-out walk over cumulative counts and why the answer is the bucket that holds the rank. Be able to say why interpolating a point inside it does not add information.

for a senior

Show the operational consequences: an unbounded top bucket that makes a high percentile unreportable, counts that only merge when edges align, and a refusal to treat a difference narrower than a bucket as a change.

for a principal

Own the trade: bucket counts buy cheap, mergeable percentiles at fixed cost, and the price is a resolution error concentrated at the slow end. Decide where the estate pays for raw times instead, and standardise one layout.

## How a percentile is read out of bucket counts A count structure replaces the list of measured times with a list of buckets and a count of how many requests fell into each. Reading a percentile from it is a walk: 1. Multiply the total count by the level you want — 0.99 of the requests, say. 2. Walk the buckets from the low edge upwards, accumulating counts. 3. Stop at the first bucket where the running total reaches the target rank. 4. Report something about that bucket. Step four is where the honesty lives, because **what the walk located is a bucket, not a value.** The request at that rank took some time between the bucket's low and high edges, and the structure no longer knows which. Every reported figure inherits the width of the bucket it landed in as its uncertainty, before any other source of error is considered. ## Why interpolation does not remove it The usual response is to interpolate: if the target rank falls a third of the way through the bucket's count, report a time a third of the way between its edges. That produces a tidier number and no more information. Interpolation assumes the samples inside the bucket are spread **uniformly**, and at the slow end of a latency distribution the density is falling steeply, so samples pile up towards the low edge of each bucket. The interpolated point is therefore biased upwards relative to the truth, and the bias is largest exactly where the buckets are widest. Nothing is wrong with interpolating as long as the report does not present the result as more precise than the bucket allows. ## Constant relative width, growing absolute width Layouts are usually built so that each bucket is a fixed percentage wider than the last, which holds the relative error roughly constant across the whole range. That is a sensible design, and it has one consequence people forget: | Where the rank lands | Bucket edges under a 10% growth layout | Width | Meaning of the reported figure | |---|---|---|---| | Fast region | 100 ms - 110 ms | 10 ms | Precise enough that nobody notices | | Middle | 500 ms - 550 ms | 50 ms | Usually still fine | | Slow end | 2.00 s - 2.20 s | 200 ms | The uncertainty is now larger than many differences people argue about | Constant relative error means **absolute error grows in proportion to the value**, and high percentiles live where the values are largest. The resolution is worst precisely where the figure matters most. ## When the error decides the verdict Most of the time this is a footnote. It stops being one under specific, recognisable conditions: - **The figure sits within a bucket width of an agreed response-time limit.** The run is then genuinely indistinguishable from one that met the limit and one that missed it, and reporting a point conceals a coin flip. - **Two figures being compared differ by less than a bucket width.** That difference is not evidence of anything; it can be produced by one sample moving across an edge. - **The rank lands in an unbounded top bucket.** Many layouts end with an overflow bucket that catches everything above the last edge. A percentile landing there cannot be computed at all — the only honest statement is *"above the final edge"*. A run where two percent of requests overflow cannot report a 99th percentile. - **Two sets of counts came from different layouts.** Counts add bucket by bucket only when the edges align. Different layouts can be reconciled only by re-bucketing to the coarser of the two, which loses resolution and never recovers it, so a merged figure carries the worst layout's error. ## Reporting it honestly - Publish the bucket the rank landed in, or the figure with its resolution stated beside it, rather than a bare point to the millisecond. - Fix one layout across everything whose results will ever be merged, and choose the edges so the region around the agreed limit is finely divided. - Make the top bucket bounded high enough that overflow is a defect to investigate rather than a routine occurrence. - Refuse to call a difference smaller than a bucket a change, in either direction. The trade is worth stating plainly: bucket counts are what make a percentile mergeable across intervals and across machines at fixed cost, and the resolution error is the price. It is a good trade, and it is only a good trade when the report says out loud what the resolution is.

  • How would you choose bucket edges when you already know the response-time limit the run will be judged against?
    Divide the region around that limit finely and let resolution fall away elsewhere, so the one comparison that decides the outcome is not made inside a wide bucket. Then keep the layout fixed everywhere results will be merged, because counts add only when edges align, and hold the top bucket bounded well above anything expected so an overflow is a signal rather than routine.
  • Two runs report high percentiles differing by 30 ms and the layout's buckets are 200 ms wide there. What do you say?
    That the runs are indistinguishable at that resolution. A gap narrower than a bucket can be produced by a single sample crossing an edge, so it is not evidence of a change in either direction. Report the bucket rather than the point, and if the difference genuinely matters, keep raw times for that region instead of counts.

saying these in an interview costs you the question

  • Reports a bucketed percentile down to the millisecond
  • Thinks interpolation inside a bucket removes the error
  • Merges two count structures with different edges
  • Calls a difference narrower than a bucket a regression
  • Reports a percentile that landed in an unbounded top bucket