The state a merge is standing in for

Every structure in this field is analysed as though one machine saw one stream. Almost none of them is run that way. The stream arrives at a hundred machines, each summarises its share, and the hundred summaries are combined into one — and the combining is an operation the analysis mentions, if at all, in a corollary.

The summaries that add measured that operation for the cardinality structures and got the cleanest result available: a merged HyperLogLog and a merged Count-Min are, register for register and cell for cell, the summary the concatenated stream would have produced. There is nothing to say about the deployment that was not already said about the stream.

This is about the structures where that is false, and it starts with a comparison that is almost always made the wrong way round.

The comparison that flatters #

Here is the natural thing to do. Take a stream. Run one summary over it. Then split the stream eight ways, run a summary over each part, merge the eight, and see how much worse the merge is.

On this stream that produces a pleasant surprise. One Space-Saving summary of thirty-two counters is wrong by up to 769 on the heaviest keys. The merge of eight such summaries is wrong by up to 536. The merge is not worse. It is better, by a third.

The conclusion sitting in front of anybody who stops there is that merging is free, or nearly so, and that distributing the work costs nothing. Both are wrong, and the reason is that the two things being compared are not the same size.

Eight summaries of thirty-two counters are two hundred and fifty-six counters. They exist simultaneously — that is what a deployment is — and they occupy 24,576 bits between them at the moment the merge is performed. The single summary they were compared against occupies 3,072. The comparison is between a structure and another structure eight times larger, and the larger one won.

So the honest comparison is against one summary of two hundred and fifty-six counters: the same total state, in one place, over the same stream. On this stream that summary’s worst error over the top eight keys is zero. It holds every heavy key exactly.

The merge gives up all of that.

What is actually being paid for #

The error is not a defect in the merge rule. Space-Saving’s merge is forced, and the forcing is worth following because it says exactly where the loss comes from.

A Space-Saving summary of $k$ counters holds an upper bracket on each key it keeps: the counter is never below the truth, and the amount by which it may be above is the key’s stored error. The property that makes this work is that a key not held by the summary has arrived at most as many times as the smallest counter reads — that is what the eviction rule enforces, and it is the whole of the guarantee.

Now merge two summaries. A key held by both takes the sum of its counts and the sum of its errors, and that is unarguable. A key held by only one is the problem. It is absent from the other summary, and absent means arrived at most that summary’s floor times — not arrived zero times. So its count must gain the other side’s floor, and so must its error.

Which means the merge performs Space-Saving’s own subtraction a second time, at a coarser grain: each key absent from the other side pays the full floor whether or not it was ever there. That is charged per key rather than per arrival, so it grows with the number of shards and not with the length of the stream, and it is the entire gap between the second and third bars above.

That plate is the finding of this essay in one picture. Between two shards and thirty-two, the state held across the deployment goes from 6,144 bits to 98,304 — a factor of sixteen — and the merge’s worst error goes from 497 to 455. A matched single summary over the same range goes from an error of one to an error of zero.

More machines is more state and the same answer. The extra counters are spent on holding, per shard, keys that are heavy only on that shard, and the merge throws almost all of them away at the cut.

The guarantee survives, which is the confusing part #

None of this breaks anything. A merged Space-Saving counter is still never below the truth — that is asserted on every build, over every key the merged summary holds, and it is a one-sided check on purpose. A merge that forgot to add the other side’s floor would produce smaller counts, better-looking numbers, and no guarantee at all.

So the structure keeps its promise and delivers an answer several hundred arrivals from the truth, while a summary of the same total size delivers the truth. That is not a contradiction; it is what a guarantee is. A guarantee is not a result has been this collection’s refrain since the sketch field opened, and the merge is its sharpest instance yet, because here the guarantee and the accuracy are being paid for out of two different budgets and only one of them appears in the specification.

Misra-Gries is worth putting beside it, because two structures that are one showed that Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting a single number. They stop being the same structure under a merge.

Misra-Gries merges by adding the tables, keeping the $k$ largest and subtracting the $(k+1)$-th largest from everything that survives. One cut, applied to every key. Space-Saving pays a floor per key absent on one side. The two rules are different arithmetic with different failure modes, and the plate above shows a case where the Misra-Gries merge is worth almost nothing: eight summaries, merged, are four arrivals better than one summary of a thirty-second of the state.

Why that happens, and why it reverses under a different partition, is the partition the analysis did not mention’s subject.

One number decides most of it #

There is a single quantity that predicts, better than anything else measured here, how badly a merge will do: how much of a heavy key’s mass sits on one machine.

Call it the concentration. For each of the heaviest keys, take the largest share any one shard holds of that key’s total arrivals, and average over the keys. A key spread perfectly evenly over $m$ shards scores $1/m$; a key confined to one machine scores 1. It is a property of the partition and the stream together, and it involves no structure at all — no counters, no merge rule, no $k$.

Under round-robin assignment, where arrival $i$ goes to shard $i \bmod m$, the concentration on this stream at eight shards is 0.14, close to the $1/8 = 0.125$ a perfectly even split would give. Under hashing by key, where every arrival of a key lands on one machine, it is 1.00 exactly, because that is what hashing by key means.

Those are the same forty thousand arrivals with the same totals, and the merged Space-Saving error moves from 313 to 536 between them.

The reason is not subtle once the number is in front of a reader. A Space-Saving summary keeps the $k$ largest keys it has seen. Under round-robin every shard sees the same distribution, so every shard keeps the same heavy keys and the merge finds them in both tables, where the arithmetic is exact and no floor is charged. Under hashing, a heavy key is present in one table and absent from the other seven, and it pays seven floors.

A partition chosen for locality is a partition chosen against the merge, and hashing by key is what any system wanting per-key state does.

What the merge is for, then #

It would be easy to read all this as an argument against merging. It is not, and the reason is that the matched comparison is available on this page and not available in a deployment.

A single summary of two hundred and fifty-six counters over the whole stream requires the whole stream to pass through one place. That is the thing the architecture exists to avoid, and it is not avoidable by being clever about counters. The merge is not competing with a matched single summary; it is competing with not being able to answer at all.

So the right way to read the three bars is as a price list. The top bar is what one machine’s worth of state buys. The middle bar is what the same state buys if it can all be in one place. The bottom bar is what it buys if it cannot, and the difference between the middle and the bottom is the cost of the architecture, stated in the currency the structure is measured in rather than in machines or in latency.

The third currency, which is merges #

Two resources have been counted so far: state, and error. There is a third, and it is the one an architecture actually pays.

A merge of $m$ summaries is $m-1$ merge operations, whatever the shape of the tree. Each of them, for these structures, is a sort of the union of two tables — $O(k \log k)$ for tables of $k$ — so the total work is $O(mk \log k)$ and does not depend on the length of the stream at all. That is the property that makes merging worth doing: the cost of combining is a function of the summaries and not of what they summarise, which is exactly the property a summary was built to have.

It is also why the shard sweep above is not an argument for fewer shards. Going from thirty-two machines to two would improve nothing in the merge — the errors are flat across that range — and would multiply the per-machine arrival rate by sixteen. The shard count is set by the ingest, and the merge’s error is very nearly independent of it, which is a convenient thing to be able to say and is not what anybody expects before measuring.

What the shard count does move is the state held at the moment of merging, and that is a real number: 196,608 bits across sixty-four machines of thirty-two counters, against 3,072 in the answer. A structure advertised by the size of its answer is being advertised by the smallest number in the arithmetic.

What is being estimated, and by what #

One more distinction, because it is the one that decides whether any of this matters to a particular system.

A merged summary is an estimator of a quantity over the union. It is not an estimator of the summary a single machine would have built, and the two questions have different answers. For HyperLogLog they coincide — the merged registers are the direct registers — and that coincidence is what makes a HyperLogLog summary a value: it can be compared for equality, cached, checkpointed and deduplicated, and a shard delivered twice changes nothing.

A merged Space-Saving summary is none of those things. It is a function of which shards were merged and, as the next essays measure, of the order in which they were. Two runs of the same pipeline over the same data can produce different tables, both correct, both inside the guarantee, and not equal to each other.

That is a property worth knowing about before a system is built on comparing summaries rather than on reading them.

Where the merged answer is smaller than what made it #

One last asymmetry, because it is the one that makes merging attractive despite everything above.

The merge of eight thirty-two-counter summaries occupies 3,072 bits when it is finished. The eight summaries occupied 24,576 while it was being computed. The answer is an eighth of the deployment, and it is that ratio — not the accuracy — that makes the operation worth performing at all: a coordinator receiving eight summaries and holding one is holding something it can afford to keep, forward, cache and query, and the eight are gone.

That asymmetry is also where a subtle error lives. It is tempting to merge incrementally — fold each shard in as it reports, keeping one summary and discarding each contributor. The state is then never more than two summaries at once, which sounds like a strict improvement.

It is not the same operation. Folding in one at a time is a particular shape of merge tree, it produces a different table from the pairwise one, and the difference is measurable. That is the order nobody fixed’s subject, and it is the reason this essay has been careful to name the shape — balanced, pairwise — every time it quoted a number.

Why the shard sweep is flat, and where it stops being flat #

More machines is more state and the same answer is the finding, and the flatness is left as an observation. It is not a coincidence, and working out why says where it ends.

The merge charges a heavy key one floor for every side it is absent from. Under hashing a key sits on one shard and is absent from $m-1$, so the bill is $(m-1)$ floors — a term rising almost linearly in the shard count. If the floor per shard fell in proportion to the shard’s mass, that product would rise by nearly a factor of two from two shards to thirty-two, and the sweep would slope upward.

It does not, because a Space-Saving floor is superlinear in the arrivals that produced it. Write the floor as proportional to $(n/m)^\alpha$ and the bill becomes $(m-1)/m^{\alpha}$ times a constant. Solve for the exponent that reproduces the measurement — 497 at two shards and 455 at thirty-two — and it comes out at

$$\alpha \approx 1.27.$$

That number is not fitted from this page. It is one of the local exponents measured directly for a hashed shard’s floor against its mass, in the middle of the same range of shard sizes, and it arrives here from two endpoints of a completely different sweep. A rising count of charges cancelling against a faster-than-linear fall in each charge is the whole of the flatness.

Which makes the flatness a property of a regime rather than of merging, and the regime has an edge. The floor’s local exponent is not constant: it climbs steeply as a shard gets small, reaching 5.17 at the finest split measured, because a table of thirty-two counters against a shard holding two dozen distinct keys stops being a summary and becomes an exact count. At that point the floor is essentially zero.

So the prediction is that past some shard count the merge error collapses rather than staying flat — $(m-1)$ cannot outrun a floor falling at the fifth power, and a fold whose leaves are exact charges nothing at its leaves. The sweep here stops at thirty-two shards, where every leaf is still a genuine summary; the collapse would be visible at a hundred and twenty-eight.

That does not rescue the essay’s conclusion so much as bound it. The extra counters are still being spent on shard-local keys the merge discards, and the exactness that eventually helps is exactness bought by giving each machine so little of the stream that a fixed table holds all of it — which is a statement about the shards being small, not about the merge being good. What it does mean is that more machines is the same answer holds over the range a deployment plausibly occupies and reverses beyond it, and a reader sweeping further should expect the curve to bend.

It also explains why the partition matters so much here and not at all for a maximum: the whole mechanism is a count of absences times a floor, and the partition the analysis did not mention sets the first factor while the shard mass sets the second. The summaries that add’s structures have neither term, which is why their sweep would be a horizontal line for a different reason entirely.

What this measurement cannot say #

Three limits, stated because the numbers above are specific and could be read as more general than they are.

The stream is one stream. All of it is a stationary Zipf draw over a universe of four thousand and ninety-six. A merge’s error depends on how the mass is distributed among keys, and a flatter stream makes every counter structure worse while a steeper one makes the heavy keys survive any partition. The shape of the curves here is a property of this exponent.

The error is measured over the top keys. Worst and mean error over the eight heaviest, because those are the keys a heavy-hitter structure exists to report. A structure can be badly wrong about a key nobody asked for and it does not appear in these numbers.

And a merge is not a cost model. Nothing here has a duration in it. The state is exact, the errors are exact, and the arithmetic of what a merge costs in bandwidth, in latency, or in the coordination that decides when the shards report is a different subject and is not measured by anything on this page.

What is established is narrower and, being exact, worth having: for these structures, on this stream, a merge of $m$ summaries of $k$ counters is substantially worse than one summary of $mk$ counters, and the gap does not close as $m$ grows. Anyone comparing a merge against a single small summary is measuring the difference between two sizes and reporting it as a property of merging.