The partition the analysis did not mention

Two structures that are one established something that ought to make this essay impossible. Space-Saving and Misra-Gries, run over the same stream with the same number of counters, hold the same information: subtract the smallest Space-Saving counter from all of them and the result is the Misra-Gries table, at every prefix of the stream and not merely at the end. They are one structure with two readings.

Split the stream across eight machines and merge, and they behave nothing alike.

Three ways to split a stream, all of which occur #

A partition is an assignment of arrivals to machines, and there are three in ordinary use.

Round-robin. Arrival $i$ goes to shard $i \bmod m$. A load balancer with no affinity does this. Every shard sees a sample of the whole distribution, and a key with total frequency $f$ arrives about $f/m$ times on each machine.

Hashed by key. Key $x$ goes to shard $h(x) \bmod m$. Every arrival of a key lands on one machine, which is what any system wanting per-key state must do — a session store, a rate limiter, a per-user counter. It is by far the most common arrangement in practice, because it is the one that makes the state on each machine meaningful on its own.

Consecutive blocks. Shard $j$ gets the $j$-th stretch of the stream. This is what time-partitioned processing does: a summary per minute, merged at the hour.

None of these appears in any bound either structure carries. The analysis is about $n$ arrivals and $k$ counters, and how the arrivals were divided is not a parameter of it. It is, however, a parameter of the answer.

The number that predicts it #

Before the structures, the partitions themselves can be measured, and the measurement uses no structure at all.

For each of the heaviest keys, take the largest share any one shard holds of that key’s arrivals, and average over the keys. Call it the concentration. A key spread evenly over $m$ shards scores $1/m$; a key confined to one machine scores exactly 1.

On this stream at eight shards, round-robin gives 0.14 and consecutive blocks give 0.14 — both close to the 0.125 an even split would give. Hashing gives 1.00, which is not an approximation but the definition of hashing by key.

For Space-Saving, concentration is very nearly the whole story, and the mechanism is exactly the one the state a merge is standing in for set out. The merge charges a floor for every key absent from a summary. Under round-robin a heavy key is present in all eight tables, so it is charged nothing; under hashing it is present in one and absent from seven, and it pays seven floors.

That is the factor of 1.7 between 313 and 536, and it is entirely a property of how many tables the key was in.

And then the other structure does the opposite #

Misra-Gries merges differently. Add the tables, keep the $k$ largest, subtract the $(k+1)$-th largest value from every survivor. One cut, applied to everything, rather than a floor charged per absent key.

Under round-robin, the merged table’s $(k+1)$-th largest value is large. Every shard is holding roughly the same thirty-two keys with roughly the same counts, so the summed table has thirty-two big entries and a crowded shoulder just below them — and the cut is taken from that shoulder and subtracted from all thirty-two.

Under hashing, the eight tables hold nearly disjoint key sets. The summed table has up to two hundred and fifty-six distinct entries, and the $(k+1)$-th largest of that is a key that was heavy on its own machine but is thirty-third overall, which on a Zipf stream is much smaller than the shoulder in the round-robin case.

So Misra-Gries pays a large cut under the partition that suits Space-Saving, and a small one under the partition that hurts it.

The numbers side by side, on the same stream, at eight shards:

Six times, in opposite directions, for two structures that are the same structure when nothing is merged.

A third structure, to check the story rather than illustrate it #

Two structures agreeing with a story is weak evidence; two structures disagreeing with each other, each in the way its merge rule predicts, is stronger. The cardinality estimators are a third case and they settle the shape of the argument, because their answer is no effect at all.

A HyperLogLog merges by taking the larger of each pair of registers. A register holds a maximum over the keys that hashed to it, the maximum over a union is the maximum of the maxima, and nothing in that identity mentions how the union was divided. So a HyperLogLog sharded by hash, by round-robin or by minute produces the same merged registers, bit for bit, and the same estimate. The summaries that add measured exactly that.

The difference is not that one structure is better. It is that a maximum is insensitive to multiplicity and a counter is not. A cardinality estimator does not care how many times it saw a key, so splitting a key’s arrivals across machines costs it nothing; a frequency estimator’s entire content is how many times, and splitting that content is splitting the thing being measured.

Any structure whose merge is idempotent is partition-blind, and any structure whose merge is a sum is not. That is the rule the three cases together support, and it predicts the right answer for a Bloom filter, for a bottom-$k$ summary, and for the two counter tables here — which is as much generality as three measurements can carry.

Why “the same structure” was never a claim about merging #

It is worth being precise about what was established earlier and what was not, because the contradiction here is only apparent.

The claim was that the two structures’ states are related by a single subtraction, at every prefix. That is still true. Run both over any one shard here and the relation holds exactly, as the site’s gate checks on every build.

What does not follow is that operations on those states commute with the relation. Merging is a function of two tables, and the fact that $A$ and $B$ carry the same information does not make $f(A_1, A_2)$ carry the same information as $f(B_1, B_2)$ for an arbitrary $f$. The two merge rules are different functions, and the information a merge discards is chosen differently by each.

That is the general shape of it, and it is worth carrying beyond this pair: a bijection between two representations says nothing about how they behave under an operation defined on the representation. Space-Saving’s merge is defined in terms of its floors, which the Misra-Gries reading has subtracted away; Misra-Gries’s merge is defined in terms of a cut, which the Space-Saving reading has no name for.

What the shoulder is, and why it decides everything #

The word shoulder has been doing a lot of work above, and it is worth making concrete, because the whole reversal turns on it.

Take the eight tables, add them key by key, and sort the result descending. Misra-Gries’s merge keeps the first thirty-two and subtracts the thirty-third’s value from each of them. So the quantity that decides the damage is a single number: how large the thirty-third entry of the summed table is.

Under round-robin, each shard’s table holds the same thirty-two keys — the globally heavy ones — because each shard sees a scaled copy of the global distribution. The summed table therefore has about thirty-two entries and a thirty-third that is a genuine near-miss: a key that was thirty-third on every shard and is thirty-third overall. On a Zipf stream with exponent near one, the thirty-third key is not much smaller than the thirty-second, so the cut is large and it is taken off everything.

Under hashing, each shard’s table holds the thirty-two keys heavy on that shard, and those sets barely overlap. The summed table has closer to two hundred and fifty-six entries, and its thirty-third is the thirty-third globally — much further down the Zipf curve than the thirty-third-on-a-shard, and therefore much smaller.

That is the entire mechanism, and it explains a number that looks strange in the table above: Misra-Gries merged under round-robin is wrong by 927 where a single summary of a thirty-second of the state is wrong by 932. Eight machines bought four arrivals of accuracy. Everything the eight shards learned was subtracted away by one cut, because they had all learned the same thing.

Which partition a system actually has #

The practical reading is uncomfortable, because the partition is almost never chosen with the merge in mind.

Hashing by key is chosen for locality. It is what makes a per-key structure possible at all: a rate limiter needs every request for a user on the machine holding that user’s counter. Nobody picks it to make a merged heavy-hitter estimate more or less accurate, and yet it decides that estimate by a factor of six.

Round-robin is chosen for load. It is what a stateless balancer does, and it spreads a hot key across the fleet, which is exactly what a system wants when the hot key is a thundering herd.

Consecutive blocks are chosen by the clock. A summary per minute is a partition by time, and it behaves here like round-robin because this stream is stationary — the first minute looks like the ninth. On a stream whose distribution moves, it would not, and the measurement would need a different corpus to say anything about it.

So the partition is set by requirements that have nothing to do with summarisation, and the structure is then chosen from a literature that does not mention it. The pairing is arbitrary, and it is worth a factor of six.

What a system can do about it #

Three responses are available, and they cost different things.

Change nothing and quote the right structure. The cheapest, and on the evidence above it is worth a factor of six. A system already hashing by key and already summarising heavy hitters is running the wrong one of the two if it is running Space-Saving, and the change is a different merge function over the same counters.

Re-partition before merging. A shuffle that gives every shard a sample of the whole distribution turns the hashed case into the round-robin case. It costs a full redistribution of the arrivals, which is the thing the partition existed to avoid, so it is almost never worth it for a summary — but it is worth knowing that the accuracy difference has a price in bandwidth and that the price is enormous.

Merge hierarchically along the partition. If shards are grouped so that a group holds all of a key’s arrivals, the within-group merges are exact and only the between-group merge pays. This is what a rack-aware or region-aware aggregation does for other reasons, and it happens to be the arrangement that suits a counter merge.

None of these is a recommendation, because the right answer depends on what the summary is for. What all three share is that they are decisions somebody has to make, and the literature the structure came from does not signal that there is a decision.

The rule that falls out #

There is a usable statement here, and it is small enough to remember.

If every heavy key is on every shard, prefer the structure whose merge charges per absent key — Space-Saving. There are no absent keys to charge for, and the merge is nearly free.

If every heavy key is on one shard, prefer the structure whose merge takes one cut — Misra-Gries. The summed table is wide and shallow below the top, so the cut is small.

Both halves are measured rather than argued, and both are measured on one stream, which is the limit worth stating plainly. A flatter distribution than this Zipf would crowd both shoulders and narrow the gap; a steeper one would make the heavy keys survive any partition and narrow it from the other side. What the exponent does not change is the direction: the mechanisms are structural, and each structure’s merge is sensitive to precisely the thing the other’s is not.

The measurement that would settle it #

There is an experiment this essay does not run, and naming it is more useful than pretending the question is closed.

The concentration measured above is a property of the partition. What decides the Misra-Gries merge is a property of the summed table, and the two are related but not the same: a partition can concentrate keys without widening the summed table, if the shards happen to hold overlapping sets for another reason. A structure-free predictor for the second quantity — something like the expected number of distinct keys across $m$ tables of $k$, as a function of the distribution and the partition — would let both structures’ merged errors be predicted before either is run.

It is computable from the stream and the partition alone, it would take one figure, and it is not here. It is written down in the site’s own plan as work rather than left implied, because a phase that measures two mechanisms and unifies neither has found a pattern rather than a rule.

Half of the missing predictor is a closed form #

The experiment named above wants a structure-free way to predict the summed table’s width, and one of the three partitions gives it up without any experiment at all.

Under hashing the shards’ key sets are disjoint by construction. Every arrival of a key goes to one machine, so no key can appear in two tables, and the summed table has exactly $mk$ entries when the shards fill — 256 at eight shards of thirty-two, with no overlap to estimate. The global top thirty-two are spread across the eight machines by the same hash, so each of them is retained by its own shard, and the summed table’s ranking below them is the global ranking.

That makes the cut computable: it is $f(k+1)$, the global count of the thirty-third heaviest key, and nothing about the structure enters.

Evaluate it on this stream. The heaviest key holds 16% of the arrivals, which for a Zipf exponent of 1.1 fixes the normaliser, so key $i$ holds $0.16\,i^{-1.1}$ of them. At $i = 33$ that is 0.34%, and 0.34% of forty thousand arrivals is about 136.

The measured Misra-Gries error under hashing is 152. A prediction from three numbers — the exponent, the head’s share, and $k+1$ — landing within a tenth of a measurement taken from eight merged tables.

So half the predictor exists and it is the half a deployment is most likely to need, since hashing by key is what the essay names as by far the most common arrangement. A system that hashes can compute its merged Misra-Gries error from its own traffic profile before allocating a counter, and the same three numbers say what a wider table would buy: raising $k$ to 64 moves the cut to $f(65)$, which on this exponent is 65 rather than 136, so doubling the counters roughly halves the error.

The other half genuinely needs the measurement, and it is worth being clear about why rather than filing it as undone. Under round-robin the shards hold overlapping sets, so the summed table’s width is somewhere between $k$ and $mk$ and depends on how far down each shard’s own top-$k$ the global heavy keys sit. That is a question about $m$ independent samples of the same distribution agreeing on their top $k$ — answerable in principle, and not by the same one-line argument, because the disjointness that made the hashed case trivial is exactly what is absent.

Which sharpens the rule this page ends on into something with an arithmetic behind it. If every heavy key is on one shard, the merged cut is a global frequency and can be looked up. If every heavy key is on every shard, the cut is a property of how the samples overlap and has to be measured — and the measurement above says it is six times larger, which is two structures that are one’s bijection failing at exactly the point where the two merge rules stop discarding the same information.

It also explains why the concentration statistic orders the Space-Saving numbers and not the Misra-Gries ones, as this page reports without accounting for it. Concentration is about where a key’s mass sits, which is what the state a merge is standing in for’s per-absent-key floor charges for. The cut is about the summed table’s thirty-third entry, which concentration says nothing about — two quantities, one measured and one not, and the closed form above is the second one in the case where it has one.

What is not established #

Nothing here is a bound. Both structures’ guarantees hold in every cell of that table — the merged Space-Saving counters are never below the truth, and the site’s gate checks it on every build. What moves by a factor of six is the realised error, which no bound in the field is about.

The concentration is a predictor and not a formula. It orders the partitions correctly for Space-Saving and it does not, on its own, predict the Misra-Gries numbers, which depend on the shape of the summed table below the cut rather than on where a key’s mass sits. Two quantities are doing the work and only one of them has been isolated.

And a partition is not only an accuracy decision. Hashing by key gives every shard a self-contained answer about the keys it holds, which is often the thing actually wanted — and a merged estimate is then a secondary product rather than the point. This essay measures one axis of a choice that has several.