The floor charged at every level

There is an arithmetic here that prices a merge from the shard histograms and never allocates a summary. It works — Space-Saving 537 predicted against 536 measured, Misra-Gries 154 against 152 — and it recorded one failure running the other way from all the others: at thirty-two shards under hashing the Space-Saving prediction comes out 22% low.

The guess attached to it was that a key above its shard’s floor stops being held with no error of its own. That guess is wrong, and it is wrong in a way that is easy to check: measure the error the held keys actually carry.

It falls as the shards get smaller. At two shards a held key carries 0.69 of the floor on average and 47% of the held mass carries some error; at sixty-four shards it carries 0.28 of the floor and 4% of the mass does. The assumption gets better exactly where the prediction gets worse.

What the fold charges #

Space-Saving’s merge rule is one line. For each key in the union of two tables, the merged count is the key’s count on each side where it is present, plus that side’s floor where it is not.

So a key present in one shard and absent from every other is charged, at each merge it passes through, the floor of the thing on the other side. The prediction charged it the floor of a shard. Above the first level the thing on the other side is not a shard — it is a merged summary of two shards, then four, then eight, and its floor is larger.

Trace it and the arithmetic closes. At sixty-four shards the mean floors by level are 2.8, 7.0, 17.3, 42.1, 101.3 and 241.5; the charges are 2, 8, 20, 43, 88 and 248; the total is 409 and the measured damage is 409.

At eight shards the floors are 74.8, 150.3 and 304.5, the charges are 64, 156 and 287, the total is 507 and the measured damage is 507. At thirty-two, 450 against 450.

There is nothing left over at any shard count. That is what makes this an account rather than a model, and it is the reason it is worth stating before anything is fitted.

Why the leaf model was right at eight shards #

This is the part worth slowing down for, because the failure has an unusual shape: the old model is not an approximation that degrades. It is an identity that has a condition, and the condition stops holding.

Charging $m - 1$ leaf floors and charging one floor per level are the same sum exactly when the floor doubles as the mass doubles. A balanced fold of $m$ shards puts a survivor through $\log_2 m$ merges, against subtrees of 1, 2, 4, … , $m/2$ shards. If the floor of a subtree of $s$ shards is $s\varphi$, the total is

$$\varphi(1 + 2 + 4 + \cdots + m/2) \;=\; \varphi(m-1)$$

which is exactly $m - 1$ leaf floors. Not approximately — identically.

At eight shards under hashing the level floors are 74.8, 150.3 and 304.5. The ratios are 2.01 and 2.03. The two models agree to two counts in five hundred, and they agree because of the doubling rather than by luck.

At sixty-four the ratios are 2.53, 2.45, 2.44, 2.40 and 2.39 — off doubling by 0.53 — and the models are a factor of 1.8 apart.

Checking the guess that was attached to it #

The note left beside that 22% offered an explanation for it, and it deserves a measurement rather than a dismissal, both because it is plausible and because it is the kind of thing that would otherwise be quietly dropped.

The claim was that the prediction assumes a key above its shard’s floor is held with no error of its own, and that this stops holding when the shards get small — a key only just above a small floor has been evicted and reinstated recently and carries the floor at its last entry.

Instrument it directly. For every shard, run the summary, take each held key’s counter and subtract its exact count, and average.

Every column moves the wrong way for the guess. At sixty-four shards the held keys are cleaner than at two by every measure — a smaller share of the floor, and a fifth as much of the held mass carrying any error at all — and sixty-four shards is where the prediction is worst.

The reason is visible once the numbers are on the page. A hashed shard at sixty-four holds one sixty-fourth of the universe, so a table of thirty-two counters covers a large fraction of the keys the shard ever sees, and the top of that table is not churning at all. Six of the thirty-two counters in a typical shard turn out never to be in play. A small shard is not a harder problem for the table; it is an easier one, and that is exactly why its floor is small and why the leaf model, which multiplies that small floor by $m-1$, comes out low. The partition the analysis did not mention is where the shard’s key space first became a parameter on this site, and it is the same parameter arriving here in a quantity nobody had connected to it.

So the guess is refuted, and refuting it is what pointed at the levels: if the leaves are fine, the error is not at the leaves.

An identity that has a condition is the worst kind of model to inherit #

An approximation announces itself. It comes with an error term, somebody quotes a tolerance, and when it degrades it degrades gradually and the residual grows in a way a plot shows.

An identity does not. It is exact, it is exact for a reason, and the reason is usually not written down beside it — because when a derivation reaches an exact answer the temptation is to stop. The older model was derived from the merge rule directly and validated against measurements at eight shards, where it is exact for the same reason it is derived: both roads pass through the assumption that a subtree’s floor is proportional to its mass, and neither of them says so out loud.

This is a general hazard rather than a local one. A limit is not a prediction is this site’s warning about asymptotic statements believed at sizes nobody ran; this is the same disease in a model rather than a bound. The measurements that validated it were all inside the regime, and the regime is invisible from inside itself.

Where the doubling comes from and where it goes #

The floor is a fixed point over the tail of a shard’s histogram: the mass of everything the table is not holding, divided by the slots that churn. The floor a histogram already knows is where that was built.

Whether it doubles when the mass doubles is therefore a question about the histogram’s shape, not about its total. Merge two shards under hashing and the union has twice the mass and twice the distinct keys — hashing splits the universe, so the shards are scaled copies of one another — and a table of thirty-two counters is now looking at twice as many keys with the same number of slots. It holds a smaller share, so more mass is tail, so the floor more than doubles.

That is the mechanism, and it says the departure from doubling should grow as the table’s share of the key space shrinks. Measured: 0.03 at eight shards, 0.32 at sixteen and thirty-two, 0.53 at sixty-four. A floor with two variables in it takes that apart properly, and it turns out not to be a power law at all.

The account has to hold at every fold depth or it is a coincidence of one, so it is run again on a fold four times shallower.

Reading the level charges #

The charges at sixty-four shards are worth looking at directly, because their shape says something the totals hide.

They are 2, 8, 20, 43, 88, 248. The last level charges more than the other five combined — 248 against 161 — and the last two account for 82% of the whole bill.

That is a general property of a balanced fold over floors that grow with mass, and it has a practical edge. Most of what a fold costs a heavy key happens in its last one or two merges, where the key’s own shard is being combined with half the stream. Everything below that is small change.

Which suggests a cheap defence that nothing here tests, and that is worth saying: fold everything except the shard holding the key, then merge the key’s own table in last against a summary whose floor is known and can be reported alongside the answer. That does not reduce the charge — the final merge is the expensive one either way — but it makes the charge a single named quantity rather than an accumulation, and a single named quantity can be subtracted. Whether it is subtractable in practice depends on knowing which shard held the key, which a deployment usually does.

At eight shards the same profile reads 64, 156, 287: the last level is 57% of the bill rather than 61%, so the shape is stable across shard counts even as the total moves.

What the account is worth #

It is exact and it needs a run, which is a step backwards from where the arithmetic stood.

The whole point of the previous arithmetic was that it prices a deployment from histograms — no summary allocated, no arrival replayed. The level floors above are read off an actual fold of actual summaries. As an account of what happened, it is complete; as a prediction, it is not one.

The repair is to compute the level floors from histograms too: merge the shard histograms pairwise, run the same fixed point on each merged one, charge that. It is straightforward and it over-predicts by up to 1.73, because a merged summary’s floor is not the floor a fresh summary settles at on the same arrivals. The floor a merge does not settle at is that discrepancy and the one measured constant that closes most of it.

The check, and why it is absolute rather than relative #

Almost every check on this site is relative, because almost every claim here is about a ratio: a fit’s residual, a prediction’s agreement, a spread between two conditions. assertRelClose exists on this site precisely because asserting that a measured 368 agrees with a predicted 384 “to within 0.35” is not a claim anybody meant.

This one is absolute, with a tolerance of one count. The charges are floors, the floors are integers, and a survivor pays a specific set of them at a specific set of merges. If the total came to 448 against a measured 450 the account would be incomplete — there would be two counts arriving from somewhere unnamed — rather than imprecise. Allowing a percentage there would allow exactly the kind of small unexplained residue that the whole exercise exists to eliminate.

A twenty per cent error per level is a hundred and thirty per cent at six #

The departure from doubling is stated above as 0.03 at eight shards and 0.53 at sixty-four, which reads as a moderate error growing into a large one. The arithmetic is worse than that, and it is worse in a way that explains why validating at four, eight and sixteen shards could not have caught it.

The two models differ by a product, not a sum. If each level’s floor is $r$ times the level below rather than exactly 2, then the top level is $(r/2)^{L-1}$ times what the leaf model charges it, where $L$ is the number of levels — and since the top level dominates the bill, that factor is very nearly the whole discrepancy.

Put the numbers in. At sixty-four shards the ratios are 2.53, 2.45, 2.44, 2.40 and 2.39, so $r/2 \approx 1.22$ over five steps: $1.22^5 = 2.7$. Doubling from a leaf floor of 2.8 would predict level charges of 2.8, 5.6, 11.2, 22.4, 44.8 and 89.6, summing to 176; the measured charges are 2.8, 7.0, 17.3, 42.1, 101.3 and 241.5, summing to 412. The top level alone accounts for 152 of the 236 that were missing.

At eight shards the ratios are 2.01 and 2.03, so $r/2 \approx 1.01$ over two steps and the compounding factor is 1.02. Seven leaf floors of 74.8 is 524 against a measured 507 — inside three per cent, which is what a one per cent per-level error does when it only has two levels to work in.

So the per-level error is mild at every shard count and the total error is not, because the levels multiply. That is the reason the failure appears suddenly rather than gradually: doubling the shard count does two things at once, adding a level to the exponent and raising the base, and their product moves far faster than either measured trend suggests. A curve fitted through four, eight and sixteen shards is fitting the flat part of an exponential.

It also says where to look first when a model of this shape is inherited. A model derived as an identity should be asked what quantity it is holding fixed — here, the ratio between a subtree’s floor and its children’s — and then asked whether that quantity appears in an exponent. If it does, the tolerance on it is not the tolerance on the answer: two per cent per level is three per cent over three levels and eighty per cent over thirty, and no amount of care about the per-level figure makes the second acceptable.

Which is the same shape of warning a limit is not a prediction gives about a class fitted over one range, sharpened by a mechanism: there the danger is a term that has not yet asserted itself, and here it is a term already visible and already small, whose smallness is the reason nobody multiplied it out. A floor with two variables in it is where the base itself is taken apart, and the compounding above is why getting that base right matters more than its size suggests.

What this changes about the earlier essays #

Nothing measured before this is wrong, and it is worth being precise about which sentences have to be read differently.

The bill a partition only divides shows the two structures’ predicted damages summing to the sum of the shard floors, for every key and every partition. That is a statement about the leaf-level arithmetic and it remains exactly true — the two columns of a leaf model still sum to the leaf model’s bill. What has changed is that the bill is no longer the whole charge above eight shards.

What a fold charges per level is about Misra-Gries’s cuts, which are a different quantity computed by a different rule, and its numbers stand. Whether its per-level term has the same regime dependence is a question this essay does not answer; the cut is the $(k+1)$-th largest count in a union, which is also a shape-dependent quantity, so the answer is probably yes and it is not measured.

The essays about the eight-shard case are all inside the regime and all correct. The one thing they should now say, and did not, is which regime.

What it took to see it #

The instrument is worth one paragraph because it is the reason this was findable at all.

A fold written as a reduction — summaries.reduce(merge) — produces a root and nothing else. Every quantity in this essay is a property of an internal node: the floor on the other side of a merge, the mass under it, the level it sat at. None of those survive a reduction, and none of them can be recovered from the root.

So the fold was rewritten to build the tree and hand it back, and the level charges fell out immediately. That is the same move the fold that minimises the wrong thing needed for its cut totals, made for a different reason alongside it, and the two together are the argument for keeping it: a fold is a computation with statistics on it, and a reducer throws them away by design.

The thing that made the account convincing rather than plausible was watching the running total meet the measurement. A model that predicted 405 against 409 would have needed defending. A running total that arrives at 409 exactly, at three different shard counts, does not.

The honest limit is that all of it is a balanced fold. A chain charges a survivor a different sequence — the floors of accumulators of one, two, three, … shards rather than one, two, four, eight — and the identity between the two models under a chain has a different condition, which is linearity rather than doubling. Nothing here computes it. What is robust is the account itself: the charge is the floor of the other side at every merge, whatever shape the merges are arranged in.