The shape that moves the bill

Nothing in a deployment says what shape the merge tree has. A coordinator folds shards in as they report, which is a chain. A parallel reduction combines them pairwise, which is a tree. A retry changes the order. All three are the same operation applied in a different association, and every published statement about these structures is written as though that does not matter.

The order nobody fixed established that for the counter tables it matters a great deal: at thirty-two shards, fifty-two keys carry a different count depending only on the shape, the largest gap being 950 arrivals, and every table is inside its guarantee. Every quantile number measured alongside it held the shape fixed at a balanced tree and said nothing.

The measurement #

Thirty-two summaries of twenty thousand values at a tolerance of one per cent, high-biased, folded as a chain, as a balanced tree, and as a chain in the reverse order.

The chain keeps 2,616 tuples. The tree keeps 3,637. The reversed chain keeps 2,615.

The worst rank error over the median, the ninetieth, the ninety-ninth and the 99.9th percentile is 17 for all three, against a promise of a hundred at the median. Not close — identical.

So the tree costs thirty-nine per cent more state than the chain and returns the same answer. That is a larger effect than doubling the shard count, and it is decided by an implementation detail nobody records.

Why the tree is the expensive one #

The rule is symmetric in its two arguments, so the asymmetry has to come from the sizes of the things being combined.

A balanced tree always merges equals. At the first level, two summaries of $n/32$ items each; at the second, two of $n/16$; and so on. Both sides are equally sparse, so each side’s tuples inherit gaps of about the same size as their own uncertainties, and the compression that follows folds about as much as it would have on either input alone.

A chain merges a large accumulator with a small arrival, every time. The accumulator holds most of the items; the incoming shard holds a thirty-second of them. The shard’s tuples inherit the accumulator’s gaps, which are large relative to the shard’s own uncertainties — and are compared against a cap set by the merged item count, which is nearly the accumulator’s. So the incoming tuples are cheap to absorb: their inherited uncertainty is large but so is the allowance, and they fold into the accumulator’s existing tuples rather than surviving beside them.

The chain’s small side is being resampled into the big side’s grid. The tree has no big side.

That also explains why the reversed chain matches the forward one to a tuple: reversing changes which shard is absorbed first and not the fact that every merge is lopsided.

The contrast that makes it interesting #

Two structures, one operation, opposite consequences.

For the counter tables, the shape moves the answer. A merged Misra-Gries table takes a cut at every merge, the cut depends on what the two tables held between them, and different associations take different cuts in different orders. The table’s width is fixed, so the damage cannot come out as space and has nowhere to go but accuracy.

For the quantile summaries, the shape moves the space. The tuple list grows, so a merge that cannot represent what it holds keeps more tuples; the answers stay inside the same bound throughout.

That is a clean instance of a rule worth carrying: a structure with a fixed allocation converts merge damage into error, and a structure that grows converts it into space. Neither is better. What is worse is not knowing which one a given structure does, because the axis that moves is the one nobody is watching.

Every fold gets its own copies #

A measurement of three folds over the same summaries has an obvious way to be wrong, and it is worth saying how it is avoided because the wrong version produces a plate that looks entirely plausible.

The merge builds a new summary and mutates neither input, so the three shapes could in principle be run over one set of per-shard summaries. They are not: each shape is given its own copies of all thirty-two. The reason is not the merge rule but everything around it — a summary carries counters for how many items it has seen and how many compressions it has run, and a shape that read another shape’s intermediate results would be measuring a fold that nobody performs.

This is the same discipline the counter-table version of the measurement uses, and for the same reason counting instead of timing gives: a comparison is only a comparison if the three arms differ in the one thing being varied. A shared-state bug here would show up as three numbers that are close together, which is precisely the result that would be reported as the shape does not matter and never questioned.

The spread across the sweep #

The effect is not a fixed percentage. It grows.

At four shards the three shapes keep 1,130, 1,151 and 1,136 tuples — a spread of two per cent, which is nothing. At eight, nine per cent. At sixteen, twenty. At thirty-two, thirty-nine. At sixty-four, thirty-eight.

The reason is the depth of the fold. A chain of four merges is barely lopsided — the accumulator after two shards is only twice the third shard — so the two shapes are nearly the same fold. A chain of thirty-two is lopsided in twenty-nine of its thirty-one merges.

So the difference is a property of scale, and the scale at which a deployment starts caring about merging at all is exactly the scale at which the shape starts costing a third of the state.

And it depends on the error function #

The spread is 1.39 for the high-biased summary at thirty-two shards, 1.41 for the low-biased one, and 1.80 for plain Greenwald–Khanna.

The flat-cap structure is the one most affected, which follows from the same argument the cheap tail and the expensive merge uses for its steeper exponent: it is sparse everywhere, so the gaps a lopsided merge asks its small side to inherit are large relative to its caps, and the difference between a lopsided merge and a balanced one is correspondingly larger.

Its rank errors are also the ones that move most across shapes — 69 ranks of spread against the biased structures’ 0 and 10 — which is the only place in these measurements where the shape does anything visible to a quantile answer. It is still inside the promise.

The answer is the same answer, checked as such #

The claim has two halves and a check on only one of them would pass on something uninteresting.

If the three shapes kept different numbers of tuples and also returned different answers, the finding would be the fold is a free parameter, which is true of the counter tables and is a weaker statement. If they kept the same tuples and returned the same answers, there would be nothing here at all.

So both halves are asserted, every time these figures are drawn: the tuple counts must differ by at least twenty per cent at thirty-two shards, and the worst rank errors must agree to inside the summary’s own promise. The first fails if the effect goes away; the second fails if the shape starts moving the answer, in which case the contrast this essay is built on would be wrong and the essay would have to say something else.

A related point about the second half. Inside the promise is doing real work in that sentence, and the promise is generous at the median — a hundred ranks out of twenty thousand. At the ninety-ninth percentile a high-biased summary at one per cent promises two ranks, and the three shapes deliver seventeen apiece: identical to each other and eight times the printed figure, for reasons the promise that does not survive the tree sets out and which have nothing to do with the shape.

What to do about it #

The finding has an unusually direct consequence, which is rare enough here to be worth flagging.

A parallel reduction is the obvious way to combine a hundred summaries and it is the expensive one, in the currency measuring what an algorithm keeps argues has to be instrumented rather than asserted. Folding them in sequence at a coordinator — the arrangement that looks less sophisticated and does not parallelise — keeps a third less state for the same answers, on every measurement here.

That is not a recommendation to serialise a reduction, because the reduction’s wall-clock time is a real quantity that none of these plates measures. It is a statement that the trade exists and has a size: a third of the merged state, against the parallelism of the fold. A system that does the tree because a tree is what a reduction is has made that trade without being told there was one.

There is a third option the measurements point at and do not test. A fold that merged in size order — smallest pair first, like building a Huffman tree — would be balanced early and lopsided late, and the arithmetic above suggests it would land between the two. The order is the algorithm collects cases where a schedule that looks like scaffolding turns out to be the substance, and this would be one; it is named here and not built.

The saving is real memory #

It is worth converting the thirty-nine per cent into the thing a system would notice, because a percentage of a tuple count is easy to read as bookkeeping.

A tuple holds a value and two counters, which is ninety-six bits at the widths used here — the accounting what a window costs in bits sets out for a windowed structure, applied to a tuple list. Thirty-two shards folded in a tree keep 3,637 of them — 349,152 bits, about forty-three kilobytes — and folded in a chain keep 2,616, about thirty-one kilobytes. Twelve kilobytes per merged summary.

That is small for one summary and is not what a monitoring system holds. A service keeping a latency distribution per endpoint per tenant, merged every minute across a fleet, holds thousands of them at once and holds each of them for as long as the query window it serves. The same twelve kilobytes multiplied by a few thousand is the difference between one machine and two, and it is decided by whether the reduction is written as a fold or as a tree.

The comparison also moves the right way as the deployment grows. At four shards the two folds differ by two per cent and nothing is at stake; at thirty-two, by a third. So the shape matters exactly where a system is large enough for the saving to be worth having, which is an unusually convenient shape for a trade and is worth stating because most of the trades in this collection are the other way round.

The spread stops growing, and that decides what the choice is worth #

The sweep runs 2%, 9%, 20%, 39%, 38% across four, eight, sixteen, thirty-two and sixty-four shards. The last step is the interesting one: the effect grows through four doublings and then stops.

That flattening follows from the mechanism. The chain’s advantage comes from merging a large accumulator with a small arrival, so the arrival’s tuples are absorbed into a grid much coarser than their own uncertainties. Once the accumulator is much larger than the arrival, making it larger still changes nothing — the arrival’s tuples were already being resampled into gaps that dwarf them, and a further doubling of the accumulator cannot absorb them twice. So each merge’s saving saturates early, and what grows with the shard count is only the fraction of merges in that regime, which tends to one. Past thirty-two shards nearly every merge is saturated and the ratio has nowhere left to go.

The consequence is worth stating in the units a deployment thinks in. The shape changes the constant and not the exponent. The tree’s tuple count grows as the single-pass count times the shard number to a power near 0.56; the chain’s grows the same way past thirty-two shards, one thirty-nine per cent lower. Folding in sequence is a one-time discount, applied once, and a system that doubles its fleet again pays the same growth it would have paid either way.

So the recommendation earlier on this page — fold as a chain, keep a third less state — is right and is bounded. It buys a third, once. It does not buy a better scaling, and a deployment whose merged summaries are growing uncomfortably has to attack the exponent rather than the association: fewer shards, a tighter tolerance at the leaves, or a structure whose merged size converges. The tuples a merge does not give back is the essay that finds the count does not converge, which is what makes the exponent the term that matters and the constant a discount rather than a fix.

It also sharpens the size-ordered fold named and not built above. If the saving per merge saturates once one side is much larger than the other, a fold that keeps its merges balanced early and lopsided late collects the saturated saving on its late merges and nothing on its early ones — so it should land between the tree and the chain, nearer the chain, and its advantage over the plain chain should be small. That is a prediction the arithmetic here makes and the plates do not test, and it is worth recording as a prediction rather than as a hope, because a measurement that came out otherwise would say the mechanism above is wrong.

And it explains the one structure that behaves differently. The flat-cap summary’s spread is 1.80 rather than 1.39, because it is sparse everywhere and so its small side inherits proportionally larger gaps at every merge — which is the cheap tail and the expensive merge’s argument arriving in the association rather than in the shard count, and which predicts that its spread saturates later.

What a retry does #

The last thing worth drawing out is that the shape is not always chosen.

A coordinator folding shards in as they report is running a chain whose order is decided by network timing. A reduction that loses a worker and retries it is running a tree with one arm re-attached somewhere else. Neither of those is a design decision and both change the association.

For the quantile summaries that is harmless in the only way that shows up at query time — the answers agree — and it means the merged state a system holds varies run to run by up to a third with nothing in the logs to explain it. A capacity alarm that fires on the merged summary’s size would fire on the day the shards happened to report in a different pattern.

For the counter tables it is worse, because the quantity that varies is the answer. The order nobody fixed has the number: fifty-two keys moving by up to 950 arrivals between associations of the same thirty-two shards, every one of them inside its guarantee, and no way for a consumer of the answer to know which fold produced it.

The general form is one this collection keeps arriving at from different directions. An operation described as combine these carries an unstated assumption of associativity, and a structure that discards information is almost never associative. A guarantee is not a result covers the consequence: all the answers are legal, and legality is not what a monitoring system is reporting.

What is now on the record #

Three quantities, and the third is the one that was missing.

The tuple growth is against a tree. Every count in this group of essays was measured with the shards combined pairwise, and a deployment folding them in a chain will see about a third fewer at thirty-two shards and up.

The shape does not move a quantile answer. Across three shapes, five shard counts and three error functions, the worst rank errors differ by less than the promise in every case, and by nothing at all in most of them.

The shape does move a counter table’s answer, which was already known, and the pairing is the finding. It is also a reason to distrust a merged number that arrives without its fold described, in the way the model a bound was quoted in is a reason to distrust a bound that arrives without its machine. Same operation, same lack of associativity, and the two structures pay it out on different axes because one of them can grow and the other cannot. What a fold charges per level works out what each of them is charged, per merge, and where the depth of the tree enters.