The promise that does not survive the tree

A quantile summary’s whole product is a promise. It does not return the right answer; it returns an answer whose rank is within a stated distance of the right one, and the distance is the parameter the operator sets. The error that is on the rank established what that promise is about, and an error measured against the answer established that a biased summary can make the promise proportional to the tail rather than to the stream, which is the version anybody watching latencies wants.

This is about what happens to the promise when the summaries are merged, which is how every one of them is deployed.

The promise, restated #

A high-biased summary at $\varepsilon$ promises that a query at quantile $q$ returns a value whose true rank is within $\varepsilon(n - r)$ of $qn$ — that is, within $\varepsilon$ times the mass above the quantile. At $q = 0.99$ over twenty thousand values that is $0.01 \times 200 = 2$ ranks. At $q = 0.999$ it is $0.01 \times 20 = 0.2$ ranks, which is to say exact.

A single summary keeps that promise here comfortably: measured rank error zero at $q = 0.99$ and one at $q = 0.999$, against promises of two and 0.2. The second of those is already over, by less than a rank, and that is the floor the implementation carries rather than a failure — a tuple whose uncertainty is under one item is exact, and one is the smallest cap the structure allows.

Now merge.

The merged bound is a sum #

Merging two quantile summaries is done by interleaving their tuple lists by value. A tuple from $A$ knows its rank among $A$’s items to within $A$’s uncertainty, and knows nothing about its rank among $B$’s items beyond which two of $B$’s tuples it falls between — which is $B$’s uncertainty wide.

So the merged summary’s uncertainty about that tuple is the sum of the two, and over the whole structure the merged rank error is bounded by

$$\varepsilon_A n_A + \varepsilon_B n_B$$

At equal sizes and equal $\varepsilon$ that is $\varepsilon(n_A + n_B)$ — which is $\varepsilon n$ again, and looks like nothing has happened. It looks like nothing has happened because the bound is stated relative to the total, and the total grew. The promise a reader cares about is in ranks, and in ranks the bound doubled.

Compound that up a tree of $m$ shards and the merged summary is entitled to an error of $\varepsilon n$ where $n$ is the whole stream, with no reference to how many machines contributed. A system that configured $\varepsilon$ per shard and quoted it as the system’s accuracy is quoting a number the answer does not have.

The measured progression at $q = 0.99$, against a single summary’s promise of two ranks:

That is very close to doubling per doubling of the shard count, which is what the sum-of-bounds says it should be, and it is the sort of agreement between a bound’s shape and a measurement that this collection is usually pleased to find. Here it is the bad news: the bound is not loose. The merge really does give up what the arithmetic says it gives up.

Why it is a sum and not a maximum #

The instinct on first meeting the merge rule is that the errors should combine like independent errors do — as a root-sum-square, or at worst as a maximum — and it is worth saying why neither is available, because the reason is structural rather than pessimistic.

A rank error here is not a random quantity with a distribution. It is a width: the summary knows the answer’s rank lies somewhere in an interval, and the interval’s size is what $\varepsilon n$ bounds. Merging two summaries means locating $A$’s tuples among $B$’s, and $B$ can only say which of its intervals a value falls into. The two widths therefore add, in the same way two rulers each marked to the nearest centimetre give a measurement good to two centimetres when laid end to end.

There is no averaging available because there is no randomness to average. A summary that had produced a sample of the stream would compose differently — sampling errors do combine as a root-sum-square — and that is a genuine alternative design with a genuinely different merge arithmetic. A deterministic interval summary composes by addition, and that is the price of the determinism.

This is the same distinction expected is not average draws in a different field, arriving here as a difference between two kinds of guarantee rather than two kinds of average.

The tail is where it bites #

The high-biased summary exists to make the deep tail accurate, and the deep tail is where the merged promise is weakest in relative terms.

At $q = 0.999$ the single summary’s promise is 0.2 ranks — twenty values out of twenty thousand are above the answer, and the summary is entitled to be wrong about which of them by a fifth of one. The merge of thirty-two shards is wrong by eleven. Eleven out of twenty is more than half the tail.

The rank error grew by the same factor as at $q = 0.99$. What changed is the denominator: the error names its denominator is this collection’s rule, and at the tail the denominator is small enough that an ordinary-looking rank error is most of the answer. A promise about the rank is not a promise about the value measured the value consequence of exactly this at a single summary, and everything it said applies here with the error multiplied.

The one place the merge is exact #

It is worth marking the case where none of this happens, because it locates the boundary.

If the shards partition the stream by value range — shard one takes the smallest fifth of the values, shard two the next fifth, and so on — then merging is concatenation. Every tuple of shard one is below every tuple of shard two, so no tuple has to be located among the other’s intervals, and no uncertainty is inherited. The merged summary’s error is the maximum of the shards’ errors rather than the sum, and the tuple count is the plain total.

That is a real arrangement — it is what a range-partitioned store does — and it is the only one under which a quantile merge is free. It is also the arrangement that requires knowing the value distribution in advance in order to choose the boundaries, which is very often the thing the quantile summary was being built to find out.

So the free merge is available exactly when the problem is already solved, and the paid merge is what a system that does not know its own distribution has to use. That is a sharper statement of the trade than “merging costs accuracy”, and it says what a system would have to give up to avoid the cost.

And the space does not come back #

There is a second cost, and it is the one that surprises an implementer rather than an analyst.

A merged quantile summary does not compress back down to the size of an unmerged one. The tuples arrive from the shards already compressed against each shard’s own cap; the merged summary’s cap is computed against the merged $n$, and a tuple that was at its cap in a summary of $n/m$ items is not at its cap in a summary of $n$ — but its neighbours have moved too, and the compression step can only merge adjacent tuples whose combined weight fits under the cap.

The measured result:

Seven times the tuples, for an answer that is eight times less accurate at the quantile it was configured for.

That growth is not unbounded — the caps do eventually bite, and a summary merged repeatedly with itself does converge — but it is well beyond the size the operator configured, and it grows in the direction nobody plans for. A coordinator sized for a summary of five hundred tuples receiving eight shards’ worth is holding three and a half thousand.

The unbiased summary is not better, it is differently wrong #

Running the same experiment with a plain Greenwald–Khanna summary — $\varepsilon n$ everywhere, no bias — gives a promise of two hundred ranks at every quantile, which nothing here comes close to violating: the merged errors range from nine to seventy-six.

That is not the unbiased summary doing better. It is the unbiased summary promising two hundred where the biased one promised two, and the biased one being wrong by seventeen. Seventeen is a better answer than seventy-six. The biased summary is more accurate and less trustworthy, and those are separate axes that a single number labelled ε does not separate.

The practical form of that is uncomfortable: the structure whose promise is easy to keep under merging is the structure whose promise was never worth much, and the structure worth deploying is the one whose promise quietly stops holding at four machines.

Where the merged summary is asked the question #

One more thing decides how much any of this matters, and it is not in the structure: where in the tree the query is answered.

A monitoring system that keeps a summary per machine per minute and answers a dashboard query by merging a thousand of them is at the far end of every curve above. One that keeps the same summaries and answers per-machine questions from the unmerged shard summaries, merging only for the rare fleet-wide view, is paying the merged error only on the rare view.

The second arrangement is common and is usually adopted for latency rather than accuracy — merging a thousand summaries at query time is slow — and it happens to be the arrangement that keeps the promise where it is most often read. It is worth knowing that the accuracy argument points the same way as the latency one, because the two are usually assumed to trade.

What does not help is pre-merging. A system that merges the thousand summaries once, keeps the result and answers every query from it has paid the full merged error on every query, and has done so to save work it would otherwise have repeated. The saving is real; the cost is the subject of this essay and is not usually counted against it.

What to do with a number that has stopped being true #

The repair is arithmetic rather than engineering, and it is a single line in a configuration.

Set ε at the shard so that the merged bound is the one wanted. If the tree is $m$ deep in the compounding sense and the target is $\varepsilon^{*}$ at the coordinator, the shards need $\varepsilon^{*}$ divided by whatever the tree costs — and the cost of the tree is exactly the sum-of-bounds above, so it is computable before anything is deployed.

What that costs is space at the shard, and it costs it superlinearly for the biased summaries, because a smaller $\varepsilon$ near the tail means smaller caps means more tuples in exactly the region that already holds most of them. It is a real price and it is payable; the alternative — quoting the shard’s ε as the system’s — is not a price at all, it is a mistake.

And measure the merged error rather than deriving it. The bound above is tight on this stream, which is not something that could be known without running it, and on a stream where the shards see very different distributions it may be loose by a lot. A merged quantile summary is cheap to score against a sorted copy of the input during development, and the number it gives is the one to quote.

What the repair costs, at thirty-two shards #

“Set ε at the shard so that the merged bound is the one wanted” is the right answer and it is worth pricing on this stream, because the price turns out to be a refusal rather than a bill.

The merged summary at thirty-two shards is wrong by seventeen ranks where the quoted promise was two. Recovering the promise means tightening the shard’s tolerance by that factor of eight or so. A quantile summary’s tuple count goes as $1/\varepsilon$ — that is the structure’s own bound and the measured constant is close to it — so each shard’s summary grows from 512 tuples to about four thousand.

Then merge them. The merged count grows as the single-pass count times the shard number to a power near 0.56, which at thirty-two shards is a factor of 7.1 — measured, in the table above, as 512 becoming 3,637. Applying the same factor to the tightened shards gives a merged summary of roughly twenty-nine thousand tuples.

The stream is twenty thousand values.

So the repaired structure holds more tuples than the stream holds items, and each tuple is a value and two counters where an item is a value. Keeping every number, sorted, would be smaller by a factor of four and exact. The repair is not expensive at thirty-two shards; it is unavailable, and the honest configuration is not a tighter ε but a different architecture.

That is worth stating as a condition rather than as a number, because it is the shape a deployment can check before building anything. The repair is affordable while

$$\frac{c}{\varepsilon^{*}} \cdot m^{0.56} \;\ll\; n,$$

with $\varepsilon^{*}$ the tolerance actually wanted at the coordinator and $c$ the structure’s tuple constant. Both sides are known in advance; the left grows with the shard count and the right does not. At eight shards on this stream the left side is about seven thousand tuples against twenty thousand values, which is a real saving; at thirty-two it has crossed over.

Which puts a boundary on the whole family. A quantile summary is bought because it is much smaller than the data, and merging spends that advantage twice — once on accuracy, which the tightened ε buys back, and once on tuples, which the tightening makes worse. Past some shard count the two spends exceed what the structure was saving, and the structure stops being a summary in the only sense that matters. An index larger than what it indexes is the same crossing in a different field, and it is the crossing worth checking first because it is arithmetic rather than a measurement.

The exponent in that condition is the load-bearing part and it is fitted rather than derived — 0.56 across the tolerances drawn here, on one stream, with a balanced merge. The tuples a merge does not give back is where it is taken seriously, and its finding that the count does not converge is what makes the inequality above a real boundary rather than a transient.

The number to put on a dashboard #

If one sentence survives this essay it should be the one that changes what gets written down.

A quantile summary’s ε is a property of a summary, not of a system. The system’s accuracy at the coordinator is the shards’ ε compounded up whatever tree the deployment builds, and that number is computable, is larger, and is almost never the one printed next to the percentile.

The version to quote is the merged bound at the depth the query is answered from, with the shard count that actually contributed. It is a longer sentence and it is the true one, and on this stream the difference between it and the short version is a factor of eight at the quantile the summary was configured for.

What is not established #

One stream, one distribution. All of it is a log-normal draw of twenty thousand values, partitioned round-robin so that every shard sees the same distribution. A partition that gives shards genuinely different distributions is the case where the merged bound might be loose or might be worse, and it is not measured here.

The bound is not proved tight. It is observed to be nearly attained on this stream. Nothing here establishes that a merge cannot do better, and the near-doubling per doubling could be a property of this compression schedule.

The merge shape is fixed at balanced. Every merged number above came from combining the shards pairwise in a tree. Quantile merging has the same order-sensitivity as the order nobody fixed measured for the counter tables, and separating the shape’s contribution from the shard count’s would take a second sweep this essay does not run.

And the tuple growth is not characterised. Seven times at thirty-two shards is a measurement, not a formula. What the merged tuple count converges to, as a function of $m$, $\varepsilon$ and the bias function, is answered in the tuples a merge does not give back, which fits it and finds that it does not converge.