The bill a partition only divides

Two structures that are the same structure under a stream prefer opposite partitions when they are merged. The partition the analysis did not mention measured that and gave the mechanism in words: one merge charges a floor per key absent on one side, the other takes one cut from every survivor. What it did not have was a way to say how much, in advance, for a partition nobody had run.

That is available now, because the floor a histogram already knows supplies the one number both mechanisms are built from. And putting the two mechanisms side by side in the same arithmetic produces something neither of them looked like it contained.

Two rules, written against the same table #

Take the shard histograms and their floors. For a given key, each shard is in one of two states: the key’s frequency there is above that shard’s floor, in which case the shard’s summary is holding it, or it is below, in which case it is not.

Space-Saving’s merge adds, for every shard that is not holding the key, that shard’s floor. It has to: absence from a summary means arrived at most floor-many times, not arrived zero times, and a merge that assumed zero would produce counts that are no longer an upper bracket — the property a count that is never under is entirely about. So the overcount is the sum, over the shards where the key sits under the floor, of the gap between its frequency there and that floor.

Misra-Gries’s merge loses, for every shard that is holding the key, that shard’s decrement count — which is the same floor, since the two structures differ by exactly that subtraction. And it loses the key’s arrivals outright on every shard that is not holding it, because those arrivals were decremented away and the table has no record of them.

Write the two out for one key and the frequencies cancel:

$$\text{Space-Saving} \;+\; \text{Misra-Gries} \;=\; \sum_{j} \varphi_j$$

The sum of the shard floors. Not per key — the same total for every key, and the same total under every partition of the same stream into the same number of shards, as long as the floors are what they are.

What that means and what it does not #

It means the two structures split one bill. The partition decides where the line falls between them and does not change the amount.

On the stream drawn above, the eight shard floors sum to 967 arrivals under round-robin. The heaviest key is held by all eight shards, so Space-Saving pays nothing for it and Misra-Gries pays all 967. The eighth-heaviest key is held by none of them, so Space-Saving pays 311 and Misra-Gries pays 656 — its own arrivals on the shards that dropped it. Different rows, same total.

It does not mean that the two structures are equally good under a given partition. They plainly are not, and the whole practical content of the result is that the split is extreme in both directions.

Under round-robin every heavy key is on every shard, so every shard is holding it, so Misra-Gries pays the whole bill and Space-Saving pays almost none of it. Under hashing every heavy key is on one shard, so seven shards are not holding it, so Space-Saving pays seven eighths of the bill and Misra-Gries pays one eighth.

Between the two lies the partition a real deployment most often has, which is neither: consecutive blocks of the stream, one per shard. A key that is popular throughout is on every shard as it is under round-robin, and a key that arrives in one stretch is on one shard as it is under hashing, so the split lands in different places on different rows of the same plate.

The prediction against the run #

None of the above is worth anything if the arithmetic does not land on the measurement, and the arithmetic is a model with two approximations in it — that a key above its shard’s floor is held with no error of its own, and that a key below it is not held at all.

Under hashing at eight shards the predictions are 537 and 154 against measurements of 536 and 152.

Under round-robin they are 311 and 967 against 313 and 927. The Misra-Gries prediction is 4% high, and the direction is expected: a key held by a shard is assumed to have been held throughout, which slightly overstates the rounds it sat through.

Why concentration ordered one structure and not the other #

The measure offered previously for this was concentration — the mean share of a heavy key’s arrivals held by any single shard, which is $1/m$ for a perfectly spread key and 1 for a key confined to one machine. It orders the Space-Saving results correctly and does nothing at all for Misra-Gries.

The reason is now visible rather than plausible. Concentration is a statement about where the key’s arrivals went, so it is a proxy for how many shards are not holding it — which is exactly the multiplier on Space-Saving’s term. Misra-Gries’s term is multiplied by the complementary count, the shards that are holding it, and a single number that rises with one falls with the other. A statistic pointed at one column of a two-column table will always misread the other column, and it will misread it by pointing the wrong way rather than by being imprecise.

The replacement is not a better scalar. It is the observation that there are two counts and one bill, and that the useful summary is which of the two counts a given structure multiplies.

The conservation is arithmetic, and it is checked as arithmetic #

A result of the form these two quantities always sum to that one invites a particular kind of failure. Both columns are computed by the same code from the same table, so a sign error in one of them can produce two plausible numbers that still add up, and a plate drawing both would look right.

So the identity is asserted rather than admired, per key and per partition: the two predicted damages are required to sum to the sum of the shard floors to within a part in a million, and the check runs over all three partitions and all eight of the heaviest keys. It is the same discipline counting instead of timing established for the operation counts — a quantity that is supposed to be exact is compared exactly, and a quantity that is supposed to be approximate gets a stated tolerance.

The check has a direction it can fail in, which is the part that matters. If the Space-Saving term were computed as the floor rather than as the gap up to the floor, every row would come out longer than the bill and the assertion would say so. If the Misra-Gries term forgot the arrivals on the shards that dropped the key, the rows would come out short. Neither would change the shape of any plate.

The two multipliers, stated as a design rule #

The useful form of all this is short enough to state in a sentence, and it is not a sentence either structure’s documentation contains.

Space-Saving’s merge damage is the number of shards a key is missing from, times a floor. Misra-Gries’s is the number of shards it is present on, times the same floor. Everything else in this essay is the consequence.

So the design rule falls out. If the routing puts every arrival of a key on one machine — which is what a system holding per-key state does, and what a hash is a family not a function is about the machinery of — then a key is present on one shard and missing from the rest, and Misra-Gries is the structure to merge. If the routing spreads arrivals evenly, a key is present everywhere and Space-Saving is.

That is the opposite of the intuition either structure’s usual description supports. Space-Saving is described as the one that never underestimates and Misra-Gries as the one that never overestimates, and neither description mentions a deployment. The choice between them is normally made on which direction of error the application can tolerate — and on a sharded deployment the size of the error moves by six times on the same decision, which will dominate its sign.

There is a wider version of the point. The model a bound was quoted in is about bounds that are correct in one computational model and quoted in another; this is about bounds that are correct for one stream and quoted for a deployment that partitions it. Neither statement is false. Both are answers to a question nobody asked.

The term the bill does not contain #

There is one addition, and it belongs to Misra-Gries alone.

A Misra-Gries merge adds two tables, keeps the $k$ largest entries and subtracts the $(k+1)$-th largest from everything that survives. If the two tables hold at most $k$ keys between them, there is nothing to discard and the subtraction is zero. If they hold more, every surviving key pays the cut.

So the cut is a function of how disjoint the tables are, which is a property of the partition and the stream and no structure at all.

Under round-robin the tables hold six distinct keys above their floors between all eight of them, the union fits in thirty-two slots, every cut is zero, and the bill is the whole of the damage. That is the cardinality question the items that survive k counters asks of one table, asked of eight at once. Under hashing the union is fifty-five keys, the last merge in the tree takes a cut of 57, and that 57 is added to the Misra-Gries column — taking the prediction from 97 to 154 and onto the measured 152.

The cut is where the merge tree gets into the arithmetic, and it is the only place it does. The rest of the bill is a sum over shards and does not care in what order they were combined. That distinction is the subject of what a fold charges per level, and it explains why the answer moves with the tree shape for one structure and not the other.

More machines, again #

The finding that started this line of work was that adding shards does not help: from two machines to thirty-two the state held across a deployment rises sixteenfold and the merged error barely moves. It was measured and it was not explained.

The explanation is the bill. Space-Saving’s damage under hashing is $(m-1)$ shard floors, and each shard floor is roughly the shard’s tail mass divided by $k$. Doubling $m$ doubles the number of terms and halves each of them, because each shard now sees half the arrivals. The product is flat.

The bill itself tells the same story from the other end: 851 arrivals at two shards, 606 at eight, 363 at thirty-two. It falls, slowly, and the fraction of it that Space-Saving pays rises from a half to nearly all — so the two effects cancel and the error sits between 455 and 571 across the whole sweep.

Nothing about that is a property of Space-Saving. It is a property of a sum whose length and whose terms move in opposite directions, and it would be true of any merge rule charged per absent shard. Which is the sort of statement that only becomes available once the damage has been written down as arithmetic instead of measured as an outcome.

Three partitions, and only one of them is a choice #

The three routings drawn here are not three options a system picks between, and it is worth being clear about which of them a deployment actually controls.

Hashing by key is what any system holding per-key state does. If a shard is going to keep a counter for a key, every arrival of that key has to reach the same shard, so the routing is forced by the structure rather than chosen alongside it. This is the common case and it is the one under which Space-Saving pays most of the bill.

Round-robin is what a load balancer in front of a stateless pool does, and a summary running on such a pool is summarising a substream that has no per-key structure at all. It is available when the summaries are being computed as a side effect of processing that was already spread that way.

Consecutive blocks is what a batch pipeline does: shard $j$ is the $j$-th stretch of the stream in time. On a stationary stream it behaves almost exactly like round-robin, because every heavy key appears in every stretch — the bill is 967 against round-robin’s 967, and the split falls in the same place.

So the practical form of this essay’s result is narrower than choose the partition that suits the structure. It is the partition is usually already decided, and it decides which of the two structures to merge.

The two columns invert down the frequency ranking #

The design rule is stated for a key, and the identity says which key. Since the two columns sum to a constant, the key that is cheapest for one structure is the dearest for the other, and moving down the frequency ranking slides the split from one end to the other.

Write it out. For a key held by $h$ of $m$ shards with floors near a common $\varphi$, Space-Saving pays the gaps up to the floor on the $m - h$ shards that dropped it, and Misra-Gries pays $h\varphi$ plus the key’s arrivals on those same $m - h$ shards. With few arrivals below the floor those are $(m-h)\varphi$ and $h\varphi$, and they cross at

$$h = m/2.$$

So the two structures are equally damaged on the key held by half the shards, and the ordering between them reverses on either side of it. The measured rows say the same: under round-robin the heaviest key is held by all eight shards, so Space-Saving pays nothing and Misra-Gries pays the whole 967; the eighth-heaviest is held by none, so Space-Saving pays 311 and Misra-Gries 656. One column runs down the ranking as the other runs up.

That sharpens the design rule rather than contradicting it, and the sharpening is worth having because it names the rule’s scope. The rule is about heavy keys, and heavy keys are the ones a heavy-hitter query is about, so for that query the rule is exactly right — under round-robin every heavy key is everywhere and Space-Saving pays nothing for precisely the keys being asked about.

Where it stops being right is a query about anything else. A threshold query near the boundary, an error bar on a mid-frequency key, a report that lists the top hundred rather than the top eight — all of those reach keys held by some shards and not others, and for a key held by fewer than half of them the recommended structure is the worse one. A deployment reading “round-robin, therefore Space-Saving” and applying it to a report that goes a hundred keys deep has applied a rule derived at $h = m$ to keys at $h = 2$.

Two things follow.

The useful summary is $h$, not the partition. The partition decides $h$ for a heavy key — $m$ under round-robin, one under hashing — and the frequency ranking decides it for everything else. A system that knows how many shards hold a given key knows which structure is cheaper for it, exactly, with no measurement.

And a system choosing per key could pay $\min$ of the two columns, which is at most half the bill for every key at once. That is not an implementable structure — the two merges produce different tables and a deployment runs one of them — but it bounds what any single choice gives up: on the keys where the chosen structure is the wrong one, the loss is the difference between the columns, and near $h = m/2$ that difference is zero while at the ends it is the whole bill.

Which is the items that survive k counters becoming the parameter that decides an unrelated question. Whether a key is above a shard’s floor was a question about membership; here the number of shards it is above the floor on is the whole of the merge arithmetic, and a count that is never under is why one of the two columns exists at all.

What the split is for #

A deployment does not usually get to choose its partition freely — hashing by key is what a system wanting per-key state does, and round-robin is what a load balancer does — but it does get to choose its structure, and the two choices interact in a way that no statement of either structure’s guarantee mentions.

Both bounds are honest. A merged Space-Saving counter is still never below the truth and a merged Misra-Gries counter is still never above it, on every stream drawn here. A guarantee is not a result has been the refrain since the summaries field opened, and this is a clean instance: two structures with equally valid guarantees, running on the same stream at the same width, are six times apart in realised accuracy, and which one wins is decided by a routing rule chosen for an unrelated reason.

The arithmetic here settles that argument before the code is written. It needs a histogram, a width and a partition, and it returns both answers. What it does not do is survive a stream whose favourites move, which the histogram that cannot see the order takes up next — and which comes with a statistic that says which case is in hand.