Histogram buckets and relative precision

7.4 Anatomy of a histogram

A histogram keeps the shape of a million samples in a few kilobytes by counting how many fall in each range of values, and how those ranges are drawn decides which percentiles it can still report and how exactly. The one this chapter uses keeps every value from 1 ns to 1 s to three significant figures in 170 KB, records in 10–30 ns, and never allocates after it is built.

Holding a million numbers

The exact way to hold a run’s latencies is to keep them all: a Vec<u64> of samples, 8 bytes each, sorted at the end and indexed, as the plain method earlier in the chapter did. It is exact and simple, and its memory grows with the run: 8 MB per million samples, 16 MB for the capstone’s two million messages, 80 MB for ten million, 23 GB for an eight-hour session at 100,000 a second. For an offline replay that is fine. For a loop that runs all day it is not, and neither is the sort, 0.3–1 s per ten million samples, to read one percentile.

A histogram trades exactness for fixed memory. It is an array of counters, one per bucket, a range of values; recording a sample means finding the bucket the value falls in and adding one to its counter. The memory depends on the number of buckets and not on the number of samples, so a billion samples cost what a thousand do. Reading the pX means walking the buckets from the lowest, summing their counts, until the sum reaches X% of the total; the answer is that bucket’s value. What is lost is position inside a bucket: the histogram knows a sample fell between 290 and 299 ns, not where. So the whole design of a histogram is one question: how wide is each bucket?

Linear buckets and what they miss

The obvious answer is to make every bucket the same width. Buckets 10 ns wide from 0 to 10 µs are 1,000 counters, 8 KB, and at the peak of the capstone’s distribution they are good: a p50 of 290 ns is known to within 5 ns, under 2%. Everything above 10 µs, though, falls into one overflow bucket, so a sample of 15 µs and one of 10 ms are the same to it, and the max, the one sample that names the worst event, is gone. Reaching 1 s at 10 ns needs 100 million counters, 800 MB. Reaching it in 1,000 counters makes each 1 ms wide, and then the whole common case, every sample from the floor to the p99.99, lands in bucket 0: the p50, p99 and p99.9 all read “under 1 ms”.

The fault is that the error that matters is relative. Ten nanoseconds is 3% of 290 ns and five millionths of 2 ms. Equal buckets spend nearly all their counters on precision that no one needs in the tail, or leave none for the peak, and no width serves both.

Log-scale buckets

The answer is to make buckets grow with the values they hold. If each bucket is twice as wide as the one before, [1, 2), [2, 4), [4, 8) and so on to [2²⁹, 2³⁰), thirty buckets cover 1 ns to 1.07 s. Finding a value’s bucket is one instruction: the bucket is the position of the value’s highest set bit, 63 minus leading_zeros, a bit-scan of the kind the data-structures chapter used on bitmaps. But a bucket a whole doubling wide is too coarse to use: 300 ns and 500 ns share [256, 512), and a p50 known to ±33% is not known.

So each doubling is divided again, into a fixed number of equal sub-buckets. With 1,024 sub-buckets in every doubling, a sub-bucket’s width is 1/1,024 of the value where its doubling starts, so every value is held to within 0.1% of itself, at 300 ns and at 3 ms alike. That is the relative-error promise: one precision, as a fraction of the value, across the whole range. Inside a doubling the buckets are linear; across doublings they are logarithmic.

This is the layout of HdrHistogram, the “high dynamic range” histogram. Asked for three significant figures, it takes 2,048 sub-buckets, the smallest power of two at least 2 × 10³. The first bucket covers 0 to 2,047 ns in steps of 1 ns. Each later bucket covers one doubling, from 1,024 × 2ᵏ to 2,048 × 2ᵏ − 1, in 1,024 steps of 2ᵏ ns, reusing the upper half of the sub-bucket range: 2,048–4,095 ns in steps of 2 ns, 4,096–8,191 ns in steps of 4 ns, and 1,048,576–2,097,151 ns, about 1–2 ms, in steps of 1,024 ns. Finding a value’s counter is a few integer operations:

// Where a value goes in a 1 ns .. 1 s histogram at 3 significant figures:
// 2,048 sub-buckets in bucket 0, then 1,024 more for each doubling.
const SUB_BITS: u32 = 11;                         // 2^11 = 2,048 >= 2 x 10^3
const HALF: usize = 1 << (SUB_BITS - 1);          // 1,024

pub fn index_for(v: u64) -> usize {
    let top = 63 - (v | 2047).leading_zeros();     // highest set bit, at least 10
    let bucket = top - (SUB_BITS - 1);             // 0 below 2,048; one more per doubling
    let sub = (v >> bucket) as usize;              // 1,024..2,047 (0..2,047 in bucket 0)
    ((bucket as usize + 1) << (SUB_BITS - 1)) + sub - HALF
}

The | 2047 makes every value below 2,048 land in bucket 0. For a sample of 1,234,567 ns, the highest set bit is bit 20, so the bucket is 10; shifting right by 10 gives sub-bucket 1,205; and the counter is number 11,445. That counter stands for every value from 1,233,920 to 1,234,943 ns, and the histogram reports a sample there as 1,234,943, the top of its range, so that a percentile is never understated; the error is under 0.09%. The library computes exactly this, with the constants worked out from its constructor’s arguments. Two significant figures mean 128 sub-buckets per doubling and an error under 1%; four mean 16,384 and under 0.01%.