The shape one structure will not fold

A monitoring deployment that shards its stream usually holds two kinds of summary side by side: a counter table for the heavy hitters and a quantile summary for the latencies. They come from the same arrivals, they are sharded by the same partition, and at the end of the window they are folded by the same coordinator in the same order, because there is one coordinator and it does one thing.

That last decision is free, and it is not.

The two columns #

Under hashing at thirty-two shards, the counter tables’ worst error over the sixteen heaviest keys runs: chain 323, balanced tree 148, size-ordered 183, largest-first 403. The tree wins by 2.7 times over the loser.

The quantile summaries’ tuple counts on the same shards run: chain 2,807, balanced tree 3,211, size-ordered 3,278, largest-first 2,556. Largest-first wins, by 1.28 times over the loser — and the loser is size-ordered with the tree just behind it.

So the counter tables’ best shape is the quantile summaries’ second-worst, and the quantile summaries’ best shape is the counter tables’ worst by a factor of 2.7. A coordinator picking the tree costs the quantile summaries 26% of their space; a coordinator picking largest-first costs the counter tables 172% of their error.

Why they pull apart #

The two structures pay for a merge in different currencies and the currencies respond to imbalance in opposite ways.

A counter table pays a cut, and the cut at a node is the $(k+1)$-th largest count in the union of the two tables. Merging a large accumulator into a small arrival takes a cut sized by the large side, and doing it thirty-one times in a row — which is what largest-first amounts to once the first few merges have built one dominant accumulator — takes thirty-one such cuts. Balanced merges keep every node’s mass as small as it can be for its level, so the cuts stay small until the last one or two.

A quantile summary pays tuples, and merging a large summary with a small one is cheaper than merging two equals. The small side’s tuples land inside the large side’s existing gaps, inherit the uncertainty of those gaps, and compress away immediately. Two equal summaries interleave and each tuple lands in a gap of its own size, so far fewer of them can merge.

The shape that moves the bill established the second half of that already — thirty-two summaries folded pairwise keep 3,637 tuples and folded in a chain keep 2,616 — and read it as chain-against-tree. With two more shapes on the plate the pattern is clearer than a two-point comparison could show: what the quantile summaries reward is imbalance at every merge, and largest-first produces more of it than a chain does.

It is worth checking that reading against the heights, because “largest-first amounts to a chain” is an assertion about a tree and trees can be looked at. Largest-first has height 31 over thirty-two shards, which is the height of a chain exactly. The two largest shards merge; their union is now the largest thing in the pool; it merges with the next largest; and so on. The construction that sounds like the mirror of Huffman’s is a chain in disguise, and it differs from the plain left-to-right chain only in the order the shards enter it.

That difference is worth 251 tuples on the quantile side — 2,556 against the chain’s 2,807 — and it is worth eighty counts on the counter side in the wrong direction, 403 against 323. Entering the shards biggest-first builds the dominant accumulator faster, which deepens the imbalance every subsequent merge sees. So the two structures read the same structural fact in opposite directions twice over: first chain against tree, then, within the chains, sorted against unsorted.

The answer does not move, and that is what makes it a trade #

If the shape moved the quantile summaries’ answers, this would be a correctness question with an obvious resolution. It does not.

The four shapes’ worst rank errors are 31, 17, 23 and 19 — a spread of fourteen ranks against a promise a hundred wide at the median. All four are inside the guarantee at every quantile scored, which is what the guarantee is for and what makes the merge associative in the sense that matters.

So the coordinator is not choosing between right and wrong. It is choosing which of two structures pays, in two units that do not convert, and there is no reading of the numbers under which one shape dominates.

What the counter tables’ loss actually is #

It is worth being concrete about the 403, because “error” is doing a lot of work in a sentence like “largest-first costs 2.7 times the error”.

The heaviest key in this stream arrives 6,362 times. A tree-folded Misra-Gries table reports it 148 low; a largest-first fold reports it 403 low. Those are 2.3% and 6.3% of the true count. Whether a factor of 2.7 on a quantity of that size matters is a deployment’s question and not this essay’s, and the honest framing is that it matters exactly as much as the difference between a 2% and a 6% understatement of a heavy hitter matters — which for an alerting threshold set near the count is a great deal and for a dashboard is nothing.

The quantile side’s 26% is easier to price because it is memory, and memory is what somebody provisions.

The same disagreement, in one number #

There is a compact way to state the whole finding, and it is the pair of ratios the plate is normalised by.

The shape the counter tables want costs the quantile summaries 1.26 times their best space. The shape the quantile summaries want costs the counter tables 2.72 times their best error. Both are above one, which is what makes this a trade rather than a preference — if either had come out at one, the two structures would simply agree and there would be nothing to write down.

That is also the form the check takes. A test that only asserted the two favourites differ would pass on a pair of structures whose disagreement cost a tenth of a per cent, which is a disagreement nobody should act on. Requiring both crossing costs to exceed a stated factor is what makes the claim a deployment can use: not “these differ” but “these differ by enough that choosing wrongly is measurable”.

There is a fourth exit that applies only to some deployments and is set out at the end of this essay: hold summaries whose merge does not care about the shape at all, in which case there is nothing here to decide.

Three ways out, and what each costs #

Fold twice. The coordinator holds both sets of summaries and folds each in its own shape. This is correct, it costs nothing but code, and it is the answer whenever the two sets are independent objects. The reason it is not automatic is that a coordinator usually folds a record — one object per shard containing both summaries — and separating them means walking the shard list twice with two different orders.

Fold once and accept the loss. Pick the shape whose loss is cheaper in the deployment’s own units. Given the numbers here that is usually the tree, because 26% of a quantile summary’s tuples is a smaller absolute cost than 2.7 times a heavy hitter’s error is a risk. It is a decision, and the point of this essay is that it should be one.

Even out the partition. Under round-robin all four shapes agree to within a fifth of a per cent on the counter side, and the trade disappears entirely — which is a parameter that waits for another and is the cleanest of the three exits when it is available. It is often not: hashing is what gives a heavy hitter’s arrivals to one shard, and that is the property the counter tables are sharded for. The partition the analysis did not mention is where that choice was first priced, and it is not free to reverse.

The mirror inside the quantile family #

There is a smaller version of the same disagreement inside the quantile structures alone, and it is worth flagging because it means “fold twice” can become “fold three times”.

A high-biased summary and an unbiased one have different cap functions, so they compress differently under the same merge, and the cheap tail and the expensive merge measured the biased family costing 6.3 times the unbiased one at two shards and 3.7 at sixty-four. Their responses to fold shape are not identical either — the imbalance that helps a summary compress helps it more when the cap is uniform, because a uniform cap makes every gap comparable and a biased one makes the gaps at the interesting end tiny.

The effect is smaller than the counter-against-quantile gap and it points the same way for both biases, so it does not produce a second reversal. It does mean that a number measured on one bias should not be quoted for another, which is the standing rule for that whole family.

What it would take to want largest-first #

Since the essay’s framing is that neither shape dominates, it is worth constructing the deployment that genuinely prefers the shape the counter tables refuse.

It is a deployment whose quantile summaries are the large object and whose counter tables are small and not load-bearing. Latency percentiles at a tight tolerance across many endpoints are hundreds of tuples each; a heavy-hitter table at $k = 32$ is thirty-two counters. If the quantile state is the thing filling the coordinator’s memory and the heavy hitters are a diagnostic nobody alerts on, then 26% off the large object for 2.7 times the error on the small one is straightforwardly the right trade.

That deployment is not unusual. It is roughly what a service-level dashboard is. And the point is that it is the opposite of the recommendation the counter-table numbers alone would produce, which is what makes “measure both bills” the actual advice rather than “use the tree”.

There is also a case where neither shape is available, which is a coordinator that folds as shards report rather than waiting for all of them. That is a chain whose order is decided by the network, and it is the arrangement the order nobody fixed is about. It cannot sort by size because it has not seen the sizes yet, and it cannot balance because it does not know how many are coming. What it can do is buffer — hold the arriving summaries and fold at the end — which converts a network’s ordering into a choice and costs the memory to hold them all.

The structures with no bill at all #

The essay compares two structures and there is a third kind on the same shards, which pays nothing under any shape — and the reason it pays nothing turns the whole finding into a statement about mergeability rather than about folds.

A cardinality estimator merges by taking the register-wise maximum. That operation is associative, commutative and idempotent, so the merged registers are the same whichever tree the coordinator builds. A frequency sketch merges by cellwise addition, which is associative and commutative, so its merged cells are the same too. A bottom-$k$ summary merges by union and truncation, and the $k$ smallest of a union do not care how the union was assembled.

Those three structures have a fold bill of exactly zero, and the two in this essay do not. Line the five up and the correspondence is complete:

The three that are indifferent are exactly the three that are exactly mergeable — the ones whose merged state equals the state a single machine would have produced. The two that pay are the two whose merge is only bound-preserving.

That is not a coincidence and it is one line of argument. If the merged state equals the direct state, then it equals it for every tree, so every tree gives the same state and there is nothing for a shape to move. If it does not, the merge is discarding something at each node, what it discards depends on what it is given, and the shape decides what it is given.

So a fold bill exists exactly where exact mergeability fails, and the size of the bill is a measure of how far short of exact the merge falls. That reframes the coordinator’s decision usefully: before measuring anything, the question is which of the summaries on the shards are exactly mergeable, and only the others need a shape chosen for them.

It also bounds how bad this can get in a deployment. A coordinator folding a record of five summaries has a shape decision affecting two of them, and the two are the ones this essay measures. A deployment holding only exactly-mergeable structures has no decision to make at all — which is one more entry on the list of things exact mergeability buys, alongside the caching, the replay and the delivery guarantee, and the one that only becomes visible once somebody folds two kinds of summary in one loop.

The disagreement, three ways #

The claim is that two structures want opposite fold shapes, and it is a claim about a pair — so it is drawn once for each half and once for the pair.

The third reading halves the shard count instead, because a disagreement that only appears at one depth of fold is a property of the depth.

What is general here #

Two structures that are merged together, by the same code, in the same order, because merging is associative for both of them — and associativity is exactly the property that makes the order look like it does not matter.

It does not matter for the answer. It matters for the bill, in both structures, in opposite directions, by factors of 1.3 and 2.7. Associativity is a statement about a value and the bill is not a value.

The general form worth carrying: when one piece of code makes a choice on behalf of two structures, check whether the two structures agree about the choice. Nothing warns about this. Both merges are correct, both are associative, both are tested, and the coordinator’s loop is four lines. The only way to find it is to measure both bills under both shapes, which takes one afternoon and had not been done because nobody had a reason to think the shapes differed at all.

One reason this stayed hidden until now is worth naming, because it is a shape of measurement error rather than a shape of code.

Both halves of it had been measured. The shape that moves the bill measured the quantile side and found the chain cheaper than the tree. What a fold charges per level measured the counter side and found the tree cheaper than the chain. Both essays are correct, both arrived here together, and the reversal between them was never stated, because each was about its own structure and neither had a reason to quote the other’s direction.

Two correct measurements that contradict each other in a way neither reports is a failure mode this site has hit before — one run, two counts is the version where the two counts are of the same run, and this is the version where they are of two structures nobody put on the same page. The repair in both cases is the same and it is a page rather than a check: put the numbers in one table and the disagreement stops being invisible.

The honest limit is that the quantile column is a tuple count and the counter column is an error, and nothing here converts between them. A Pareto statement — this shape dominates that one — is available inside each column and not across the pair, and the essay deliberately stops short of proposing an exchange rate. The frontier between time and space is where this site does construct such a frontier, and it does so because both axes are resources; here one axis is a resource and the other is an error, and a deployment’s own tolerance is the only thing that relates them.