The histogram that cannot see the order

The arithmetic that prices a merge takes a frequency table per shard and returns both structures’ damage. On a stationary stream it lands within four per cent. On a stream where a heavy key stops arriving halfway through, within four per cent. On a stream where one key floods a short stretch, within five per cent under one partition and 160 per cent out under another. On a stream whose popular keys drift, seven times out.

Every one of those runs used the same code and the same input format. What changed is a property of the stream that the input format cannot represent.

What a histogram throws away #

A frequency table says how many times each key arrived. It does not say when, and every quantity the prediction computes is defined in terms of when.

The floor a summary settles at is the arrivals that got evicted, and eviction happens at a moment. A key is safe from eviction if its counter is above the smallest one at the time — not if its whole-stream frequency is high. Those are the same condition only when the distribution holds still.

Take a stream whose favourites move: a block of keys is popular for a while and then a different block is. A key from an early block accumulated a large count during its window, sat in the table the whole time as one of the heaviest things in it, and then stopped arriving. In the whole-shard histogram it is a middling key — high total, but below the top thirty-two once the later blocks have had their turns — so the arithmetic classifies its arrivals as tail mass, mass that churned through the smallest slot. They did not churn. They went into a counter that was never the smallest.

So the tail mass is overstated, the fixed point divides an inflated numerator, and the predicted floor comes out high.

The size of it, and the direction #

The overshoot grows with the width of the table, which is the diagnostic.

At sixteen counters the prediction is 1.13 times the measured floor; at thirty-two, 1.35; at sixty-four, 1.42. A wider table holds more of the temporarily-heavy keys, so the histogram misclassifies more of them, so more mass is wrongly counted as churn.

That is worth contrasting with a merely noisy failure. Noise would not have a direction, would not scale with $k$, and would not be reproducible across every shard of every run — a distinction expected is not average draws for costs and which applies unchanged to a residual. This does all three, which means it is a term the model omits rather than a tolerance the model exceeds. The cliff where the data stops fitting makes the general case: a systematic residual is a finding, and the temptation to widen the error bars until it fits inside them is how a wrong model survives.

A statistic that says which case this is #

The failure has a cause, and the cause is measurable from the same input the prediction uses.

Split each shard’s arrivals in half. Rank the keys in the first half and in the second, take the top $k$ of each, and report the share of that set which does not appear in both. Zero if the favourites hold still, rising towards one as the distribution walks away from itself. It costs one more pass over the arrivals and no structure at all.

On the four streams above it reads 0.16, 0.20, 0.20 and 1.00 under round-robin, and 0.16, 0.17, 0.17 and 0.91 under hashing. The three streams the prediction handles sit together; the one it does not is separated by a factor of five.

The statistic is not calibrated and is not a threshold. What it does is separate the regime in which a whole-shard histogram is a description of what the structure held from the regime in which it is not, and separate them by enough that no fine judgement is involved.

What the warning does not see #

It fails on the bursty stream, and the failure is instructive enough to be worth as much as the success.

Under round-robin, the prediction on a stream where one key floods a short stretch is 202 against a measured 526 — two and a half times out, the second-worst result in the whole sweep. The statistic reads 0.195, which is where the well-behaved streams sit.

The reason is exactly the construction of the statistic. The burst is in the middle of the stream, so the flooding key is among the heaviest in both halves, so the top-$k$ sets of the two halves agree and the statistic reports that nothing has moved. What moved was within a half, at a timescale the split does not resolve.

So the honest statement is narrower than the plate at the head of this essay makes it look. The statistic detects drift, meaning a change in which keys are heavy between one stretch and another at the grain it samples. It does not detect bursts, meaning a key whose arrivals are concentrated in time without changing its rank. Both defeat a histogram, and only one of them is visible to a two-way split.

The obvious repair — split into more pieces and take the worst pair — trades one blind spot for another, because a fine enough split starts reporting sampling noise as movement on a perfectly stationary stream. A statistic that samples at one grain answers about that grain, which is the same problem the model has parameters keeps producing in other guises.

The two failures are one failure, at two timescales #

Setting the bursty case beside the drifting one makes the shape clearer than either does alone.

Both are streams on which a key’s rank changes over the run. The drifting stream changes rank slowly, over a scale comparable to the whole shard; the bursty one changes it abruptly, over a scale of a few hundred arrivals. A histogram of the whole shard integrates over both, and the integration is exactly the operation that destroys the information the fixed point needs.

That is worth dwelling on because it is the failure mode this collection has recorded most often and in the most different disguises. The count somebody chose is about a cost model that answers precisely a question nobody asked; the space the model does not see is about a resource a measurement was not instrumented for. Here the instrument is exact, the arithmetic is right, and the representation of the input is missing a dimension.

The tell in all three cases is the same: an answer that is confidently wrong, reproducibly, in one direction, with no internal sign of trouble. A method that failed loudly would need no essay.

Why not simply use the order #

There is a version of this that has no failure in it: replay the arrivals, maintain the top-$k$ set as it evolves, and compute the churn properly. That is a correct model of the structure. It is also a structure, and running it costs what running the summary costs.

The entire value of the arithmetic is that it is not a run. A capacity plan is made against a stream nobody has yet seen, from a frequency table sampled off last week’s traffic, for a width and a partition still under discussion. What is available in that setting is a histogram. What is not available is the arrival order of a stream that has not arrived.

So the choice is not between a good model and a better one. It is between an arithmetic that answers in the setting where the question is asked and a simulation that answers in a setting where the question has already been settled by having the data.

Given that, the useful thing is not to repair the failure but to bound it. And the bound has a shape: the prediction is high when the favourites move, on every case measured, at every width. It never came out low on a drifting stream. A quantity that errs in one direction is a quantity a capacity decision can use, because a floor predicted too high sizes a structure too generously rather than too meanly.

The large-shard regime, which is a different failure #

One more place the arithmetic runs out, and it is unrelated to order.

At thirty-two shards under hashing on a stationary stream, the Space-Saving prediction is 354 against a measured 455 — twenty-two per cent low, in the direction the drifting case never goes. The bill has fallen to 363 arrivals because each shard now sees twelve hundred arrivals and four hundred distinct keys, so its top thirty-two covers nearly everything and its floor is small.

What the model assumes there and should not is that a key above its shard’s floor is held with no error of its own. At small shard sizes the table is holding a large fraction of the distinct keys it has ever seen and the assumption is nearly exact. At thirty-two shards the table has been through fewer evictions, its counters carry inherited error from the ones it did make, and the model does not have a term for it.

This is the second precondition, then, and it is the more ordinary of the two: the prediction wants shards large enough that their summaries have reached a steady state. Both preconditions are of the same kind — a statement about the structure’s history that the input cannot carry — and both were found by pushing the sweep past the region anybody would have run. That is the argument for sweeping past it, and it is the same one two parameters one bound makes about a cost with two axes — the interesting behaviour is nearly always outside the box the default parameters draw.

What the failure costs a decision #

It is worth converting the error into the thing it would actually distort, which is a width.

A capacity plan uses the predicted floor backwards: choose $k$ so that the floor is under some tolerance. On a stationary stream the answer is right. On the drifting stream at $k = 64$ the prediction is 54.8 where the structure delivers 38.6, so a planner asking for a floor below fifty would be told sixty-four counters are not enough and would buy a hundred and twenty-eight — twice the memory, for a structure that already met the requirement.

That is the benign direction. The costly direction would be a prediction that came out low, promising a tolerance the structure does not deliver, and it is worth noting that nothing in the argument guarantees the sign — it is measured across the sweep and asserted, not proved. A floor that holds if something else does is the general form: a bound with an unstated precondition is a bound that will be quoted without it.

The last plate makes a point that is easy to miss about the whole apparatus. The bill conservation holds exactly on the drifting stream, because it is a consequence of how the two damages are defined rather than of anything about the structures. Every row is the same length and every row is wrong. An internal consistency check tells nothing about external validity, which is why the ratio against measurement is drawn on every plate in this group.

The grain the structure itself sets #

The two-way split is described above as sampling at one grain and therefore blind to anything finer, and the natural response — split more finely — is dismissed because a fine enough split reports noise. That dismissal is too quick, because there is a principled grain available and it is not arbitrary.

The right timescale is the structure’s own forgetting time. A counter-based summary evicts a key when the smallest counter climbs past what that key holds, so the interval over which a key can be absent and still survive is set by how fast the smallest counter climbs — which is a quantity the structure reports, and which the arithmetic in this family already computes as the floor divided by the stream length.

Sample the arrivals at that grain and the statistic is measuring exactly the thing the prediction depends on: whether a key’s rank held still for as long as the table remembers. A key that dominates for a hundred arrivals and vanishes matters if the table forgets in fifty and does not if it forgets in ten thousand.

Two things follow and both remove the arbitrariness the essay complains about.

The grain is derived rather than chosen. It is not a tuning parameter with a plausible default; it is a number the same arithmetic already produces, so the warning statistic and the prediction it qualifies are computed from one quantity.

And the noise objection dissolves. A split at the forgetting time is coarse when the table is wide and fine when it is narrow, which is precisely the direction that keeps the sample size per piece from collapsing — a wide table forgets slowly, so its pieces are long, so the top-$k$ sets in each are estimated from plenty of arrivals.

What this does not do is make the statistic detect the bursty stream as currently constructed, since the burst there is a rank change and the flooding key’s rank is high in every piece at any grain. Catching that needs a different quantity — the dispersion of a key’s arrivals rather than the movement of the top set — which is the measurement the arrival-processes plate above already draws and which nothing in this family currently feeds into the prediction.

Two statistics, one pass #

The honest summary of the diagnosis is therefore that a histogram is missing two things and one warning has been built.

Movement — whether the heavy set changes between stretches — is what the two-way split measures, and it is the failure that costs a factor of seven.

Concentration — whether a key’s arrivals are bunched within a stretch — is what the dispersion measures, and it is the failure that costs a factor of two and a half and currently goes unreported.

Both are computable in the same pass over the arrivals that builds the histogram, and neither needs a structure. The composite rule a capacity plan should use is therefore: compute the prediction, compute both statistics, and treat the prediction as an upper bound qualified by whichever of the two is large.

That is a weaker product than a prediction with an error bar, and it is what the measurements support. A method with two named failure modes and a detector for each is more useful than one with an error bar that covers neither, and the second detector is the piece of work this essay leaves undone rather than a limitation it has to accept.

The shape of a limit worth publishing #

Three essays here now rest on this arithmetic and the arithmetic has two documented failure regimes. That is the right ratio, and it is worth saying why rather than treating it as an embarrassment.

A method with no known failures is a method nobody has pushed. The habit is falsification rather than confirmation, and it is why every assertion this site ships is paired with an input it must refuse — the discipline counting instead of timing opened with and a limit is not a prediction states the general form of. The sorting work on this site refused two claims outright — on average is not a number and the fit that would not accept the popular story about nearly-sorted input — and both refusals are worth more than the claims they replaced, because they say what the instrument is entitled to conclude.

Here the entitlement is: a merge’s damage can be computed from shard histograms to within a few per cent when the shards’ favourites hold still and the shards are large enough for their summaries to have settled, and it is high by up to seven times when they do not. Both halves are measured across a sweep, both are asserted rather than described, and the assertion about the failure is written so that it fails if the failure stops happening — because a predictor that quietly started working on a drifting stream would mean the account of why it works is wrong.