Commentary: metrics-aggregator

The sampler locates the p99 slot 3.59× more precisely than the p50 slot — and reports a 35.50× spread anyway. The same memory spent on counters gets 1.000×. A study guide for aggregator.py.

cd metrics-aggregator
python3 demo.py            # the aha (§6), ~2 seconds
python3 test_aggregator.py # pins every number this page quotes, ~11 seconds

1. Orientation

Your service handles a million requests. Your metrics agent cannot keep a million latencies, so it keeps a hundred numbers and reports a p50 and a p99 from those. Everybody knows the p99 out of such a thing is noisy. This toy exists because everybody also knows why, and what everybody knows is wrong.

Here is the same trace, unchanged, read by a hundred-slot reservoir two thousand times. Nothing varies but the sampler's seed:

The universal explanation is "the tail is sampled sloppily — only one slot lands out there." That explanation is false, and one line of arithmetic falsifies it: the sampler locates the p99 slot 3.59× more precisely than it locates the p50 slot, and the p99 answer is 6.5× less stable anyway. The imprecision is not in the sampler. It is in the distance the distribution travels while the slot drifts.

The payoff is that the fix is not "more memory". Spend the identical 100 units on counters instead of samples and you get 200.26ms — 1.000× true, deterministically, on every run. It was never the O(1) that cost you. Randomised O(1) costs you; counted O(1) doesn't.

By the end you should be able to:

• say where the j-th slot of a k-slot sample actually sits, in numbers (Beta(j, k+1−j)), and why the p99 slot sits there more tightly than the p50 slot;
• predict a reservoir's reported percentile distribution from the trace's quantile function before running it, and get within 2%;
• name the one knob that moves the instability 30×, and the two obvious candidates that move it by nothing;
• state the condition under which a reservoir's p99 is trustworthy, and see why that condition means you didn't need a p99;
• prove that a plausible-sounding fleet failure — every host reporting p99 X while the true fleet p99 is above every X — cannot happen.

2. The problem this mechanism exists to solve

A counter is easy. A sum is easy. Both are incrementally computable: hold one number, fold each new sample into it, and the state you keep does not grow with the stream. A percentile is not like that. The exact p99 of a stream is a function of the whole multiset, and the only algorithm that computes it exactly needs the whole multiset.

So every metrics system in production is solving the same problem: report a tail percentile out of state that does not grow with traffic. The two classical answers are the two in this toy.

• Keep a bounded random sample and compute the percentile of the sample. This is the sampling family — Dropwizard Metrics' Timer keeps an exponentially-decaying reservoir; a Prometheus Summary keeps a streaming quantile summary. It needs no configuration, it adapts to any range of values automatically, and it can answer any quantile you ask for after the fact.
• Keep a bounded set of counters — "how many requests were ≤ 5ms, ≤ 10ms, ≤ 25ms" — and interpolate. This is a Prometheus Histogram. It needs you to pick the bucket boundaries before you see the data, and it can only answer quantiles to bucket resolution.

The competing goals that make both defensible:

• Memory, which both bound, and which is the entire point.
• Accuracy where it matters, which is the far tail, which is exactly where data is scarcest.
• Mergeability. A hundred hosts each report their state; something has to fan them in. Counters add. Samples… also merge, but the merged sample is not the sample you would have taken from the merged stream, and a percentile of a sample does not merge at all.
• Configuration-freedom. Buckets must be chosen in advance by a human who has to guess the shape of a distribution that does not exist yet. A sample needs no such guess. This is the histogram's real cost, and it is why sampling summaries keep getting built.

The toy's claim is about the first two. At equal memory, and on the same stream, the two designs do not fail in proportionate ways — they fail in completely different ways, and the sampling one fails much worse than its reputation suggests.

3. Background you need

None of it is deep, but the page leans on all of it.

The two that carry the result are the third and fourth. The Beta distribution of the slot's position is what turns "the tail is noisy" into a number you can compute in one line, and it is what makes the usual explanation falsifiable. The quantile function is where the damage actually happens: the slot drifts a little and Q(u) amplifies the drift enormously, because near u = 0.99 it is nearly vertical. Everything in §6 is those two facts multiplied together.

If you take one thing from the table: a reservoir does not estimate "the p99". It reads one order statistic, whose position is a random variable, and reports whatever the distribution happens to have parked at that position.

4. The mental model

Before any code. One stream, two ways to spend a hundred numbers.

(DefBuckets is shown because its bounds are readable; the equal-memory comparison in §6.5 gives the histogram a full 100 counters.)

Now the part that decides everything. Slot 99's position is a random variable, and it is a tight one — but the trace's quantile function Q(u) is what converts a position into a millisecond reading, and Q is nearly flat at the median and nearly vertical in the tail:

Three consequences fall straight out of the picture, and they are the toy:

• The sampler is more careful about the tail, not less. Slot 99's position has sd 0.0138 in quantile units; slot 50's has sd 0.0495. The tail slot is pinned down 3.59× more tightly, because a Beta(99, 2) is squashed against the top of the interval and a Beta(50, 51) is spread across the middle.
• The damage is done by Q, not by the sampler. The median slot wanders over a 16.30 percentile-point window and the answer moves 1.23×. The p99 slot wanders over 4.30 points — a quarter as far — and the answer moves 8.02×.
• Therefore the instability is a property of your latency distribution, not of your estimator. Flatten the tail and it vanishes; steepen the tail and it explodes, with k, n and the true answer all held fixed. §6.6 and §6.7 are that sentence, measured.

5. Reading the source

202 lines, raw wc -l. Read them in this order.

5.1 The determinism decision, made in the docstring

Determinism: every source of randomness is an explicit `random.Random(seed)`
handed in by the caller. No wall clock, no builtin `hash()`, no module-level
RNG -- so a named number on the commentary page reproduces byte for byte, and
"only the sampler's seed changed" is a statement you can actually make.

This is the most consequential decision in the toy and it is not in any function. The headline is a comparison between runs that differ in exactly one thing, and there is no way to make that claim if the trace is regenerated, the clock is consulted, or a module-level RNG carries state from one sweep into the next.

Concretely: Reservoir.__init__ takes a seed, not an RNG that somebody else has been drawing from; uniform_subset takes an rng argument; latency_trace takes an rng argument. The demo builds the trace once from TRACE_SEED = 20260803 and then only ever varies random.Random(1000 + s). Two runs of demo.py are byte-identical — I diffed them.

5.2 exact_pct — and the off-by-one that decides everything

def exact_pct(sorted_xs, q):
    """Nearest-rank percentile: the ceil(q*n)-th smallest value.

    No interpolation, deliberately. The obvious worry is that `ceil` is what
    makes the tail jumpy; the commentary measures the linear-interpolation
    variant and gets 30.80x against 30.96x, so the choice is decorative.
    """
    n = len(sorted_xs)
    if n == 0:
        return float("nan")
    r = max(1, math.ceil(q * n))
    return sorted_xs[min(r, n) - 1]

Twelve lines, and one of them is the whole toy's setup. exact_pct is the truth function — run over the full million-sample trace it gives the real answer — but it is also what the reservoir uses on its 100-slot buffer, and there it does something quietly different.

ceil(0.99 × 100) = 99. So the p99 of a 100-slot sample is slot 99 of 100, and the j-th of k sorted uniforms has expected position j/(k+1) = 99/101 = 0.980198. Ask a 100-slot reservoir for the p99 and it hands you, on average, the p98.02. That is a bias, it is knowable in advance, and it is not the subject of this page — the spread is. But it explains why the reported values cluster low: the swept median reading is 97.47ms against a true p99 of 200.22ms, and 0.487× is far too big to be explained by 0.98 versus 0.99 alone. The rest is §6.4.

The docstring makes a claim, so I ran it. Swapping nearest-rank for numpy's default linear interpolation, 3000 sampler seeds over a 200,000-sample trace:

30.96× against 30.80×. The percentile definition — the thing every discussion of this topic argues about — is worth half a percent. It is decorative. test_the_percentile_definition_is_decorative pins both numbers.

5.3 latency_trace — the knob that turns out to be the answer

def latency_trace(rng, n, median=0.020, sigma=0.5,
                  p_tail=0.02, tail_median=0.200, tail_sigma=0.8):
    """A lognormal body plus a lognormal slow path. Seconds.

    `tail_sigma` is the load-bearing knob of the whole toy: it changes the
    SLOPE of the quantile function past u=0.95 while barely moving the true
    p99, and the reservoir's reported spread moves 30x with it.
    """
    mu_body, mu_tail = math.log(median), math.log(tail_median)
    out = []
    for _ in range(n):
        if rng.random() < p_tail:
            out.append(rng.lognormvariate(mu_tail, tail_sigma))
        else:
            out.append(rng.lognormvariate(mu_body, sigma))
    return out

A two-component mixture, not a single lognormal, and the reason is that real latency is a mixture: a fast path that hits cache and a slow path that doesn't. p_tail = 0.02 puts the mixture boundary right where the p99 lives, which is what makes the p99 the interesting question rather than an afterthought.

The parameter that matters is tail_sigma, and the reason it matters is worth stating in advance because it is unintuitive. tail_sigma barely changes the p99 — the slow path's median is still 200ms whatever its spread — but it changes the slope of Q(u) past u = 0.95 enormously. §6.6 sweeps it and the reported spread moves 29.6× while the true answer moves 2.6%.

5.4 Reservoir.add — Algorithm R, and a + 1 that is correct and inert

    def add(self, x):
        if len(self.buf) < self.k:
            self.buf.append(x)
        else:
            # Keep x with probability k/(n+1) -- the invariant that makes the
            # buffer uniform. The +1 is what counts x itself as a candidate;
            # `randrange(self.n)` would bias the sample towards early arrivals.
            j = self.rng.randrange(self.n + 1)
            if j < self.k:
                self.buf[j] = x
        self.n += 1

Eleven lines and one invariant: after n items, every one of them is in the buffer with probability exactly k/n. The first k go in unconditionally; after that, item number n+1 is kept with probability k/(n+1) and, if kept, evicts a uniformly chosen incumbent. The randrange does both jobs at once — j < self.k is the coin flip and j is the victim.

The comment claims the + 1 is load-bearing, so I built the variant. Feed both an ascending stream 0..n-1, where any drift toward late arrivals shows up immediately as a mean rank above (n-1)/2:

The comment is right and the effect is negligible at this toy's scale. At n = 200 the biased version drifts late by 0.40%, and at 40,000 draws that is a 5.25-sigma difference — real, not noise. By n = 1,000 it is under two sigma and by n = 20,000 it is exactly zero. That is what you would expect from a bias of order 1/n: correct code, invisible consequence, at any stream length a metrics agent will ever see. Worth knowing before writing a paragraph claiming that line is where the behaviour lives. It isn't; §6.6 is.

5.5 uniform_subset — the shortcut, and why it is not a cheat

def uniform_subset(rng, sorted_xs, k):
    """Draw what `Reservoir`'s final buffer IS -- a uniform k-subset -- in
    O(k) rather than O(n). Returns it sorted.

    This is not an approximation of Algorithm R; it is the theorem Algorithm R
    exists to satisfy, sampled directly. A 2000-seed sweep over a million-
    sample trace is 2e9 `add` calls the long way round and 2e5 the short way.
    `test_aggregator.py` pins the two against each other.
    """
    n = len(sorted_xs)
    if k >= n:
        return list(sorted_xs)
    return [sorted_xs[i] for i in sorted(rng.sample(range(n), k))]

This is a teaching moment disguised as an optimisation, and it deserves the paragraph because a reader is right to be suspicious of it.

The sweeps on this page run a k-slot reservoir 2000 times over a 1,000,000-sample trace. Done honestly with Algorithm R that is 2×10&sup9; add calls, which is minutes of Python per figure and would have made half the experiments on this page unaffordable. uniform_subset does it in 2×10⁵ operations by drawing the answer directly: rng.sample(range(n), k) is a uniform k-subset of the positions, and "the final buffer is a uniform k-subset of the stream" is precisely the theorem Algorithm R exists to establish. Using it is not approximating the reservoir; it is asserting the reservoir's own correctness proof and taking the shortcut that proof licenses.

Since that is an argument rather than a measurement, the toy measures it too. 3000 seeds each over the same 20,000-sample stream:

A 0.91-sigma difference of means, which is what agreement looks like when you measure it honestly rather than hoping for exact equality on 3000 draws of a wildly heavy-tailed statistic. test_algorithm_r_buffer_is_a_uniform_k_subset runs the same comparison with 2000 seeds and asserts under 2.5 sigma; demo.py runs real Algorithm R three times over all million samples and prints whether the results land inside the swept range (they do); and test_algorithm_r_lands_inside_the_swept_range asserts it. Algorithm R is shipped, used, and checked; the shortcut is what makes the page affordable.

5.6 Histogram — le semantics, and the clamp that says nothing

    def add(self, x):
        # `le` semantics: bucket i counts x <= bounds[i], so bisect_left.
        self.counts[bisect.bisect_left(self.bounds, x)] += 1

    def quantile(self, q):
        total = self.total
        if total == 0:
            return float("nan")
        rank = q * total
        cum = 0
        for i, c in enumerate(self.counts):
            cum += c
            if cum >= rank:
                break
        if i == len(self.bounds):              # the rank fell in +Inf
            return self.bounds[-1]             # <-- the silent clamp
        lo = 0.0 if i == 0 else self.bounds[i - 1]
        prev = cum - self.counts[i]
        frac = (rank - prev) / self.counts[i] if self.counts[i] else 0.0
        return lo + (self.bounds[i] - lo) * frac

Three things to stop on.

add has no coin flip in it. That is the whole difference between the two estimators, and it is why the histogram gives the same answer on every run, in any arrival order. test_the_same_memory_spent_on_buckets_is_right_and_deterministic feeds one histogram the trace forwards and another the same trace backwards and asserts first.counts == second.counts.

The interpolation assumes each bucket is uniformly filled, which is false for every latency distribution ever measured — inside a bucket the density falls off, so linear interpolation reads high. That error is small and, more importantly, fixed: with Prometheus's default buckets on this trace,

1.03×, 1.14×, 1.06×, 1.01×. Wrong by a knowable factor, the same factor every time, in a known direction. Compare with a factor drawn fresh from a 35.50× range every flush.

The clamp is the load-bearing line, and it is return self.bounds[-1]. When the requested rank lands in the +Inf bucket there is no upper bound to interpolate towards, so histogram_quantile returns the highest finite bound. Prometheus does this too, and it is the one failure a reader will guess correctly, so it gets §7.5 and a paragraph rather than an act of the demo.

5.7 beta_inv and beta_sd — the arithmetic that makes this a derivation

def beta_inv(p, j, k):
    """The p-quantile of slot j's POSITION, by bisection on `beta_cdf`.

    Nearest-rank pQ of a k-slot sample reads slot j = ceil(Q*k), and that slot
    sits not at quantile Q of the true distribution but at a RANDOM quantile
    U_(j) ~ Beta(j, k+1-j). Feed these positions to the trace's own quantile
    function and you predict the reported percentile before measuring it.
    """
    lo, hi = 0.0, 1.0
    for _ in range(200):
        mid = (lo + hi) / 2
        if beta_cdf(mid, j, k) < p:
            lo = mid
        else:
            hi = mid
    return (lo + hi) / 2

def beta_sd(j, k):
    """sd of U_(j) ~ Beta(j, k+1-j), in units of quantile.

    The one number that falsifies "the tail slot is sampled sloppily": at
    k=100 this is 0.0138 for slot 99 against 0.0495 for slot 50.
    """
    return math.sqrt(j * (k + 1 - j) / ((k + 1) ** 2 * (k + 2)))

These two functions are why this page can say "derived" instead of "observed", and they are the only part of the toy that is mathematics rather than plumbing.

The fact underneath both: if you draw k independent uniforms on [0, 1] and sort them, the j-th one is distributed Beta(j, k+1−j), with mean j/(k+1) and variance j(k+1−j)/((k+1)²(k+2)). A uniform k-subset of a sorted stream is exactly that, rescaled — so slot j of the reservoir sits at true-quantile U_(j). beta_sd is the closed form of the sd; beta_inv inverts the CDF by 200 rounds of bisection, which is crude, exact enough at any precision you can print, and eight lines.

beta_cdf deserves a word, because the identity it uses is the one worth remembering: P(U_(j) ≤ x) is the probability that at least j of the k uniforms land below x, which is a binomial tail, Σ_{i=j..k} C(k,i) x^i (1−x)^(k−i). No special functions, no scipy, math.comb and a sum.

Put a number to it, the number that breaks the reader's model:

The j(k+1−j) factor is a parabola: it is maximised in the middle and it collapses at the ends. Slot 99 of 100 has j(k+1−j) = 99 × 2 = 198; slot 50 has 50 × 51 = 2550, nearly thirteen times more, and the sd is the square root of that ratio. The estimator is most sure about where its extreme slots sit and least sure about where its middle slot sits — the exact opposite of the folk explanation. And it is not an artifact of the closed form; §6.3 measures it over 20,000 draws.

6. The demo, and what it proves

demo.py builds one trace — 1,000,000 samples, TRACE_SEED = 20260803, true p50 20.25ms, true p99 200.22ms — and runs five acts on it in about two seconds. Every swept figure below is over 2000 sampler seeds unless it says otherwise.

6.1 Act 1: the same trace, read two thousand times

for s in range(SEEDS):
    samp = uniform_subset(random.Random(1000 + s), srt, K)
    reported["p50"].append(exact_pct(samp, 0.50))
    reported["p99"].append(exact_pct(samp, 0.99))
for lab, true in (("p50", true_p50), ("p99", true_p99)):
    v = sorted(reported[lab])
    reported[lab] = v
    print(f"  reported {lab}: {ms(v[0])} .. {ms(v[-1])}   "
          f"spread {v[-1] / v[0]:6.2f}x   median {ms(exact_pct(v, 0.5))} "
          f"({exact_pct(v, 0.5) / true:5.3f}x true)")

srt never changes. K never changes. The only thing that varies across the 2000 iterations is random.Random(1000 + s). So every difference in the output is the sampler's coin flips and nothing else — which is the condition that makes the rest of the page a controlled experiment rather than an anecdote.

Read the two rows against each other:

• p50: 16.53ms – 25.45ms, spread 1.54×, median reading 20.14ms = 0.995× true. A dashboard built on this is fine. It is unbiased and it is tight.
• p99: 38.14ms – 1353.92ms, spread 35.50×, median reading 97.47ms = 0.487× true.

Two separate problems live in that second row and it is worth keeping them apart. The spread is 35.50×: pick a window at random and your p99 could be 38ms or 1.4 seconds. The centre is 0.487×: the typical window reports less than half the truth. The second is arguably worse, because a spread that big is at least visible as jitter on a graph. A median reading of 97.47ms is not jitter. It is a number that looks calm and is wrong by a factor of two.

The last line of act 1 is the honesty check: real Algorithm R, three seeds, one pass each over all 1,000,000 samples, giving 234.65ms, 144.48ms and 67.96ms — three readings spanning 3.45× from three runs, and all three inside the swept range. The shortcut is not what produces the effect.

6.2 The arithmetic behind 35.50×

Do not take the transcript's word for it; the spread is derivable from the two endpoints of the sweep. 1353.92 / 38.14 = 35.50. And the ratio between the two rows is the thing to hold on to: 35.50 / 1.54 = 23.05. The same estimator, on the same data, with the same memory, is twenty-three times less reproducible about the p99 than about the p50.

The natural next question is which of the two rows is anomalous, and the answer is neither: they are the same phenomenon evaluated at two points of the same curve. §6.4 produces both from one formula.

6.3 Act 2: the explanation everybody gives, falsified

The standard account of act 1 is that the reservoir has ~1 sample out past the p99, so of course it can't see the tail. It is a satisfying story and it is wrong. Slot 99 of 100 is Beta(99, 2):

sqrt(50·51 / (101²·102)) = 0.049505 against sqrt(99·2 / (101²·102)) = 0.013795, a ratio of 3.59. In the units that matter — where on the true distribution the thing you read is sitting — the sampler is three and a half times more precise about the p99 than about the p50, and the p99 answer is worse anyway. Whatever is destroying the p99, it is not sampling precision.

Since that is a closed form, the natural attack is that it is an artifact of the algebra or of the choice of units, so both were checked. 20,000 empirical draws of a 100-subset from a 200,000-sample stream:

Measured 0.049451 and 0.013700 against predicted 0.049505 and 0.013795 — the closed form is right to three digits. And the claim survives restating: the p99 slot is tighter in absolute percentile-points (1.38 vs 4.95) and tighter relative to its own mean (1.40% vs 10.00%). The only normalisation that flips the sign is sd / (1 − mean) — sd as a fraction of the tail that remains — which is 0.69 against 0.10. That is a real and interesting quantity, and it is already the next section's point in disguise: it is large precisely because there is so little probability mass left up there for the slot to move through, which is another way of saying Q is steep.

6.4 Act 3: where the damage actually comes from, derived

for j, lab in ((50, "p50"), (99, "p99")):
    lo_u, hi_u = beta_inv(0.05, j, K), beta_inv(0.95, j, K)
    print(f"  {lab}: slot roams u={lo_u:.4f}..{hi_u:.4f} "
          f"({(hi_u - lo_u) * 100:5.2f} pct-points) -> value "
          f"{ms(Q(lo_u))}..{ms(Q(hi_u))} = {Q(hi_u) / Q(lo_u):5.2f}x")

Take each slot's 5th-to-95th-percentile position window and push both ends through Q, the trace's own quantile function:

The median slot roams 3.79× further in percentile-space (16.30 against 4.30) and the answer moves 6.5× less (1.23× against 8.02×). That is a factor of roughly 25 in Q's local steepness, and it is the entire explanation. Between u = 0.9534 and u = 0.9964 this trace goes from 51.86ms to 415.75ms; between u = 0.4136 and u = 0.5766 it goes from 18.12ms to 22.33ms. The sampler is doing the same job in both cases. The distribution is not.

And this is not a story fitted after the fact. Predict the reported percentile distribution from Beta(j, k+1−j) alone, before looking at the sweep, and compare:

Six predictions, worst error 1.8%, and the p50 row is right to a tenth of a percent. test_beta_pushed_through_Q_predicts_the_measurement asserts every one of the six is within 2%. The headline number is not an observation about reservoirs; it is a consequence of two facts you can compute on paper — Beta(j, k+1−j) and the shape of your own latency curve.

6.5 Act 4: the same hundred numbers, spent on counters

Identical memory budget. 200.26ms against a true 200.22ms — 1.000× — and the same number every run, forever. And the fourteen-counter Prometheus default, using a seventh of the memory, still gets 1.064×, which is better than any individual reservoir reading is likely to be.

The obvious objection is that I picked friendly buckets, so I swept the layout at a fixed 100-bucket budget:

Every log-spaced layout that spans the data lands within 1% on both percentiles, including one covering a nine-order-of-magnitude range from 1µs to 1000s. Two layouts fail, and the failures are the point: linear 0..100ms clamps the p99 to 0.50× because the data runs past its last bucket, and linear 0..10s gets the p50 wrong by 2.51× because its first bucket is 100ms wide and the entire body of the distribution falls inside it.

Both failures are constant, repeatable, and diagnosable — the same wrong number every run, in a known direction, from a cause you can read off the bucket list. in_inf_bucket even tells you when the first one is happening. A reservoir gives you a different wrong number every flush and no way to tell. That is the trade this act is really about: the histogram's errors are ones you can find and fix; the reservoir's are ones you cannot even detect.

6.6 The load-bearing knob is not in the estimator

Everything so far could be read as an argument about k. It isn't. Hold k, n, the sampler and the true answer fixed and change only the shape of the far tail:

The true p99 goes 200.34ms → 205.48ms, a 2.6% move. The reported spread goes 6.39× → 188.98×, a 29.6× move. Same estimator, same k, same n, same question, same answer — only Q's slope past u = 0.95 changed. That is §6.4's thesis in five rows, and test_tail_shape_is_the_load_bearing_knob pins the two ends.

Two knobs a reader will reach for first, and both are inert.

Stream length. The intuition is that a million samples must be better than five thousand. k = 100 throughout, pure lognormal sigma = 1.0:

100× more data takes the spread from 9.05× to 11.24× — the wrong way, and by a margin that is mostly the larger sample having a longer true tail to reach into. More traffic does not make your p99 more trustworthy. It cannot: Beta(99, 2) does not know how long the stream was.

The percentile definition. Already dealt with in §5.2: 30.96× nearest-rank against 30.80× interpolated.

One knob is partially load-bearing, and it is the expensive one. k does buy the spread back, slowly, on a pure lognormal sigma = 1.0 trace:

256× the memory takes 9.27× to 1.13× — and 25,600 slots is not a bounded summary any more, it is a quarter of the stream. You are buying back accuracy with the exact resource the technique exists to save, at a rate of roughly 1/sqrt(k), while §6.5 got 1.000× out of 100 counters. That comparison is the toy's actual recommendation.

6.7 The boundary: where the effect vanishes completely

A result you cannot switch off is a result you do not understand. Act 5 switches it off:

On a constant trace the spread is exactly 1.00× across all 2000 seeds — test_the_boundary_a_flat_tail_kills_the_effect_entirely asserts v[0] == v[-1] == 0.020, not a rounded ratio. On a uniform 10–30ms trace it is 1.08×. The reservoir is not broken and then fixed; it is doing precisely the same thing, and there is simply nothing at the far end of Q for it to be wrong about.

And the quantity that predicts the spread throughout is the one §6.4 named: Q(0.996435) / Q(0.953440), the trace's own value ratio across the p99 slot's 5–95 position window.

The Q-ratio and the spread move together across seven orders of tail steepness, from 1.020× / 1.05× to 7.569× / 85.88×. The spread grows faster than the ratio because the full min-to-max of 2000 draws reaches further out than the 5–95 window — but the ordering is exact and the driver is unambiguous.

So, the sentence a reader should carry to their own system:

Compute Q(0.9964)/Q(0.9534) on a day of your own real latencies. That number, not your sample size and not your quantile algorithm, tells you how much to trust the p99 your agent reports.

The pathological corner sits at the other end of the same rule. A two-point distribution — 98% at 20ms, 2% at 500ms, a Q-ratio of exactly 25 — gives a 25.00× spread with only two possible readings:

802 windows say 20.00ms and 1198 say 500.00ms. Nothing in between is ever reported, and the average reading of 307.52ms is a value the system has never once produced and never will.

6.8 The numbers are pinned by tests

test_the_headline_spread_on_one_unchanging_trace asserts 38.14, 1353.92 and 35.50× to the hundredth of a millisecond, so §6.1 cannot rot. test_the_p99_slot_is_located_more_tightly_than_the_p50_slot asserts 0.049505, 0.013795 and 3.59. test_tail_shape_is_the_load_bearing_knob pins 6.39× and 188.98× and asserts the true p99 moved only 1.026× between them, which is the comparison that makes the knob load-bearing rather than merely influential.

7. Design decisions and roads not taken

7.1 Two estimators, not one

The toy could have shipped the reservoir alone and asserted that a histogram does better. Shipping both turns the central claim from an assertion into a measurement that runs in the same process, on the same trace, in the same two seconds — and it is what converts "the tail is noisy, that's sampling for you" into "you spent your memory on the wrong thing." It costs about fifty lines.

It also gives the page a control. When act 4 reports 1.000× deterministic, the reader knows the trace is not pathological and 200.22ms is genuinely recoverable from a hundred numbers. Without that, 35.50× could be read as an unavoidable cost of bounded memory, which is exactly the misreading the toy exists to prevent.

7.2 Counters and gauges were dropped

The backlog entry said "counter/gauge/histogram aggregator". A counter is += and a gauge is =; between them they are about eight lines with no design problem in sight, no failure mode, and nothing to be surprised by. They would have been eight lines of budget spent teaching nothing.

The interesting observation is why they are trivial and the timer isn't: counters and gauges are incrementally computable and percentiles are not (§2). The third of StatsD that has a design problem is the only third worth a toy.

7.3 The fleet failure mode that cannot exist

The design brief for this toy asked for a specific, plausible-sounding scenario: a fleet where every host reports a p99 of X and the true fleet p99 is well above every reported X. It does not exist, and proving that is worth more than another example of something going wrong.

The bound is two lines of counting. For each host i, at most 0.01·nᵢ of its samples exceed its own p99, and therefore at most 0.01·nᵢ exceed maxᵢ p99ᵢ, which is at least as large. Sum over hosts: at most Σ 0.01·nᵢ = 0.01·N of the pooled samples exceed maxᵢ p99ᵢ. But the pooled p99 is by definition the value with at most 1% of pooled samples above it — so the pooled p99 sits at or below the largest per-host p99. Always. For any host weighting, any traffic skew, any distribution.

Measured, over 120 fleets of 20 hosts × 500 requests, with 0, 1 and 7 sick hosts:

Zero violations, and the closest approach was 0.7992 — not even close to the bound. test_pooled_p99_can_never_exceed_the_largest_per_host_p99 pins it.

So a dashboard showing the max of per-host p99s is pessimistic but never fabricates: it is a genuine upper bound on the pooled truth. A dashboard showing the mean understates badly, which reproduces here (one sick host in a hundred: true fleet p99 409.72ms against a mean-of-p99 of 217.44ms) and belongs to a separate mechanism — merge semantics, not estimation — and so to a separate toy.

7.4 Histogram.merge ships; Reservoir.merge does not

Three lines of merge are in the toy because they are the histogram's other argument. Counters compose exactly: merging per-host bucket counts gives literally the bucket counts of the pooled stream, and test_counters_merge_but_summaries_do_not asserts a.counts == whole.counts after merging two disjoint traces. On the 100-host fleet the merged histogram reports 432.13ms against a true pooled 409.72ms (1.055×) — just the interpolation error of §5.6, nothing new.

There is no Reservoir.merge, and the omission is deliberate. Merging two uniform k-subsets into a uniform k-subset of the union is possible but requires weighting each buffer by its stream length, and a wrong implementation looks right. More importantly it would add a mechanism — distributed summary composition — to a toy already carrying one.

7.5 The +Inf clamp gets a paragraph, not an act

The Prometheus histogram's most famous failure is what happens when the data runs past your last bucket. histogram_quantile returns the highest finite bound and says nothing about having done so. Walking a trace's slow path from 200ms out to 1000s under the default buckets:

A true p99 of 1,013,571ms reported as exactly 10,000.00ms — 0.01× — flat, confident and unhedged. It gets a paragraph rather than a section because it is the predicted failure: a reader who knows what a bucket is will guess it, and a toy earns its place by breaking models, not confirming them. Note that in_inf_bucket computes the answer in seven lines, so the information is available and simply not surfaced; that is a reporting choice in Prometheus, not a limitation of the data structure.

7.6 Why not t-digest, HDR histogram, GK or DDSketch

All four are the real answers to this problem and none is here.

t-digest keeps variable-width centroids that are deliberately tiny near the tails and fat near the median — which is precisely the fix for §6.4, since it puts resolution where Q is steep. It is also a genuine toy of its own: the scale function, the merging algorithm and the accuracy argument together are well past 300 lines.

HdrHistogram is a histogram with automatically generated constant-relative-error buckets, which removes §6.5's configuration problem without changing the mechanism this page is about.

Greenwald–Khanna gives a hard εN rank-error guarantee in O((1/ε) log(εN)) space — the theoretically right answer, and its summary maintenance is the mechanism, not the percentile.

DDSketch gets a relative-value error guarantee rather than a rank one, which is what you actually want from a latency metric.

Each swaps in a different data structure for the same slot in the same argument. The toy's job is to make the argument visible with the two designs people are actually running today.

7.7 Percentiles are nearest-rank

Free choice, and proved free rather than assumed (§5.2): 30.96× against 30.80×. Nearest-rank is two lines instead of five and never invents a value that was not in the data, which matters when the demo is printing the sample's own contents back at you.

8. What's simplified vs. the real thing

• No time windows and no flush cycle. A real StatsD or Prometheus client aggregates into a window, ships it, and resets. Every "window" on this page is a whole 1,000,000-sample trace, which makes the effect smaller than in production: a real 10-second window holds far fewer samples and, per §6.6, the spread does not shrink with n. The reset also matters for a reason the toy cannot show — a reservoir that is reset every flush has a cold buffer for the first k requests of each window, so the first k samples of every window are kept with probability 1.
• No concurrency. Reservoir.add is a read-modify-write over a list with no lock. Real agents either shard per thread and merge, or take a lock on the hot path. Sharding a reservoir is the part that is genuinely subtle: m independent k-slot reservoirs are not a mk-slot reservoir of the union unless the shards saw equal traffic.
• No wire protocol. No UDP, no metric:120|ms parsing, no packet loss — and packet loss is its own sampling layer sitting underneath everything on this page.
• No labels, no cardinality. The single most expensive thing about production histograms is that they are per label-set: 100 buckets × 200 endpoints × 20 status codes is 400,000 counters, and cardinality, not bucket count, is what actually kills Prometheus. The toy has one series.
• No sparse or native histograms. Prometheus's native histograms use exponential buckets generated on demand at a configured relative resolution, which makes the layout problem of §6.5 mostly disappear. That is the direction the real ecosystem has gone.
• No counters, no gauges (§7.2), no Reservoir.merge (§7.4).
• Floats, not integers, and no storage accounting. The toy holds the full 1,000,000-sample trace in memory to compute the truth, which is the exact thing the mechanism exists to avoid. The estimators never see more than k values at a time; the reference does.
• No coordinated omission. Every sample in the trace is an independent draw. In a real system, a stalled server stops generating requests, so the slow period is under-sampled by the very thing being measured — an error that lands on top of everything on this page and in the same direction.

9. Check yourself

Answer before expanding. Each answer is derivable from the source.

Q1. Your metrics agent uses a 100-slot reservoir. Someone proposes moving to 1000 slots to fix the noisy p99 — ten times the memory across every service in the fleet. Using the numbers on this page, what do they get, and what should they do instead?

Q2. A colleague says the reservoir's p99 is unstable "because with only 100 samples you get about one sample past the p99, so the tail is basically a coin flip." Using beta_sd, show they are wrong, and say what is actually happening.

Q3. You have a p99 dashboard fed by 200 hosts, each running a 100-slot reservoir. Every host reports a p99 between 80ms and 120ms. Can the true fleet p99 be 400ms?

Q4. Histogram.quantile interpolates linearly inside the chosen bucket. Real latency density falls off inside a bucket rather than being flat. Does that make the histogram's p99 too high or too low, and by how much — and does it matter next to §6.1's 35.50×?

Q5. You switch from exact_pct to linear interpolation, from nearest-rank to the "exclusive" definition, and from k = 100 to k = 128, all at once. Which of these three changes the answer most, and what would you have had to change to actually fix anything?

Q6. Your service's latency is almost perfectly flat — every request takes between 19 and 21ms, no slow path at all. Your reservoir's p99 is rock solid across every flush. Is that good news?

10. Further reading

Every link below was fetched and confirmed live when this was written (2026-08-04).

• Vitter, "Random Sampling with a Reservoir" (1985, PDF) — the source of Reservoir.add. Algorithm R is the first page and the rest of the paper is about how to go faster by skipping — sampling the number of records to discard rather than flipping a coin per record, which is what makes reservoir sampling practical at line rate. A scan from the author's own page; there is no text layer.
• Prometheus: histograms and summaries — the official statement of exactly the trade-off in §2, written by the people who had to pick a default. Read the "Errors of quantile estimation" section: it documents the +Inf clamp of §7.5 and the interpolation assumption of §5.6, and is unusually honest about both.
• histogram_quantile reference — the specification Histogram.quantile is imitating, including what happens when the rank lands in +Inf and why the function returns NaN in the cases this toy returns nan for.
• Prometheus native histograms — where the ecosystem went after §6.5's layout problem: exponential buckets generated on demand at a configured relative resolution, so nobody has to guess bounds in advance. The direct answer to the histogram's real cost.
• client_golang histogram.go — where DEF_BUCKETS comes from, verbatim. Worth opening to see that the famous default is a hand-picked list of thirteen numbers aimed at "typical web service" latencies, with a comment saying so.
• Order statistic § uniform distribution — the Beta(j, k+1−j) result that beta_sd and beta_inv implement, and the whole basis of §6.3 and §6.4. If you read one link here, read this one: everything on this page is downstream of that single distributional fact.
• Greenwald & Khanna, "Space-Efficient Online Computation of Quantile Summaries" (PDF) — the deterministic answer §7.6 declines to build: an εN rank-error guarantee in O((1/ε) log(εN)) space, with no randomness anywhere. A close relative — Cormode et al.'s biased quantiles — is what Prometheus's Go Summary runs on, via the beorn7/perks package.
• t-digest (Dunning), repository and paper — the practical modern answer, and the one that fixes §6.4 head-on by making centroids small exactly where Q is steep. The "Computing Extremely Accurate Quantiles Using t-Digests" paper is linked from the README.
• Masson, Rim & Lee, "DDSketch" (VLDB 2019, PDF) — the one that gets a relative-value error guarantee rather than a rank guarantee, which is what you actually want when the question is "is the p99 above 200ms". Fully mergeable, which §7.4 cares about. Datadog runs it.
• HdrHistogram — constant-relative-error buckets generated automatically, which removes §6.5's configuration problem without changing the mechanism. Also the origin of the phrase coordinated omission (§8), which is the error that sits on top of everything on this page.
• Gil Tene, "How NOT to Measure Latency" — the talk. Mostly about coordinated omission and about why the average of a percentile is meaningless, both of which this toy deliberately leaves to other pages. Watch it after you have internalised §6.1: it is the same argument aimed at a different part of the pipeline.