The warning that is silent for the right reason

A prediction that fails on some inputs and not others needs a statistic that says which. The one shipped for the merge arithmetic measures how much of a shard’s top $k$ changes between its first half and its second, and it works: on a drifting stream, where the histogram’s account of what was heavy has nothing to do with what was heavy at the time, it reads 0.909 and the prediction overshoots by up to 1.42.

The note attached to it said it does not catch a burst — that a key which floods the middle is heavy in both halves and the statistic reads the same as on the control — and asked for a second statistic that does.

It does not catch a burst. The reason is that on a burst there is nothing to catch, and a warning that fired there would be a false alarm.

The prediction does not fail on a burst #

This is a one-line check and it should have been the first thing anybody did with the complaint.

At eight shards under hashing, the leaf model’s prediction divided by the measured damage reads 1.00 on the stationary stream, 1.01 on the bursty one, 1.01 on the departing one and 0.82 on the drifting one.

The bursty stream is fine. It is fine to within a percentage point, which is tighter than the stationary control. So a statistic that fired on it would be warning about a prediction that is correct, and every deployment reading the warning would go and do something unnecessary.

Why a burst is easy and a drift is not #

The mechanism is worth spelling out, because “burst” and “drift” both sound like non-stationarity and only one of them breaks a histogram.

A histogram has no order in it. The prediction works when the keys that are heavy overall are the keys the structure was holding at the time, and it fails when they are not.

On a drifting stream the popular keys move. A key that was heavy in the first tenth of the stream and absent thereafter appears in the whole-shard histogram as a modest total, well down the tail — and while it was arriving it was at the top of the table, evicting things. The histogram counts as tail mass a great deal that the structure was holding, so the predicted floor comes out too high.

On a bursty stream one key floods a stretch and is otherwise absent. Its total over the shard is large — that is what a flood does — so the histogram puts it near the top, which is where it was. The other keys’ totals are unchanged. The histogram’s account and the structure’s experience agree, and the arithmetic works.

The distinction is not stationary against non-stationary. It is whether the ranking moved, and a burst that leaves one key heavy overall has not moved the ranking.

The histogram that cannot see the order is where that distinction was drawn and where the drifting failure was measured at 1.13, 1.35 and 1.42 times the measured floor at three widths. The essay stated the burst case as a limitation of the statistic. It is a limitation of the statistic and it is not a gap in the coverage, and the difference between those two readings is what this essay is correcting.

The statistic is measuring the right thing #

Once the failure is characterised as a moving ranking, the statistic’s design reads as exactly right rather than as a rough proxy.

It compares a shard’s top $k$ in its first half against its top $k$ in its second, and reports the share that changed. That is a direct measurement of whether the ranking moved. It reads 0.160, 0.172, 0.168 and 0.909 on the four streams, and the fourth is the one where the ranking moved. Note which stream sits third: the summary that has to forget’s departing case, where one key takes a third of the first half and then stops entirely. That is as non-stationary as a stream gets, the statistic reads 0.168, and the prediction is accurate to 1%. Stopping is not moving the ranking either — a key that was heavy and left is still heavy in the total.

The complaint against it — that it does not distinguish a burst from a control — is true and is the statistic behaving as designed. A burst and a control produce the same prediction quality, so a statistic predicting prediction quality should give them the same number.

Which turns the open question inside out. The request was for a second statistic that catches a burst. What the measurement says is that the first statistic is complete for the failure it was built for, and that the second statistic is needed for a different failure that had not been found yet.

The second failure, and its own detector #

The failure found here is at high shard counts, and it has nothing to do with arrival order.

At sixty-four shards under hashing the leaf model reads 0.54 of the measurement on the stationary stream — the control — and 0.54 on the bursty one, and 0.52 on the departing one. Every stream fails together, which is the signature of a modelling error rather than an input problem.

The floor charged at every level is what it is: the model charges each shard’s own floor, the fold charges the floor of whatever is on the other side of each merge, and the two are the same sum only when the floor doubles as the mass doubles.

So the detector is that condition, measured. Take the fold’s level floors, take the ratio between each level and the one below, and report how far the worst of them is from two.

• stationary: 0.53
• bursty: 0.59
• departing: 0.65
• drifting: 34.00

The first three are the second failure appearing on all three streams the order warning is silent on. The fourth is both failures at once on the stream that has both.

Two failures, two statistics, and neither is a refinement of the other #

The pair is worth setting out as a table because the whole point is that they are independent.

The two failures push the prediction in opposite directions, which is worse than it sounds. A deployment at high shard counts on a drifting stream has one error pushing high and one pushing low, and the sum can land anywhere including on the right answer. A prediction that is accidentally correct because two errors cancelled is the hardest kind to notice, and it is why both statistics have to be read rather than a single combined score.

How the second failure was found, since no statistic pointed at it #

Worth saying, because the moral is uncomfortable.

No warning found it. It was found by sweeping the shard count past where anybody had swept before and noticing a number going the wrong way — the Space-Saving prediction coming out 22% low at thirty-two shards, in the opposite direction to every other failure recorded. It was recorded as an anomaly with a guess attached and no statistic could have flagged it, because a statistic detects a failure somebody has already characterised.

That is the general shape and it is not fixable by better statistics. A warning covers the failures its author knew about, and the way to find the others is to sweep a parameter further than the regime the model was validated in and look at whether the residual has a trend. The leaf model’s residuals at 4, 8 and 16 shards are 1%, 0% and 10%, which is a trend to a reader looking for one and noise to a reader who is not. It became unambiguous only at 32 and 64.

A limit is not a prediction makes the case for extending a measurement range past where a claim was fitted, and this is the version where extending it broke a model rather than a complexity claim. The instrument that would have caught it earlier is not a statistic; it is the habit of plotting a residual against the sweep variable rather than reporting its worst value.

One more partition settles that the statistic is reading the stream rather than the routing. Cut the arrivals into consecutive blocks — which is neither round-robin’s even sample nor hashing’s one-shard-per-key — and the four streams should land in the same places, because none of the four has changed.

What makes a statistic a warning rather than a number #

Three properties, and the pair above has all three, which is why the exercise is worth generalising.

It is computed from the same inputs as the prediction. Both statistics read the shard histograms — the order one needs them split in half, the regime one needs them merged pairwise — and neither needs a structure allocated or an arrival replayed. A warning that cost a run would be a warning nobody could afford to consult before deciding whether to do the run.

It separates rather than describes. 0.16 against 0.91 is a gap of five and a half times, with nothing in between on any stream measured — the same property the boundary that hides the burst needed of its own spread measure, and for the same reason. A statistic that read 0.16, 0.31, 0.44 and 0.58 would be describing a continuum and would need a threshold somebody argued about.

It has a known blind spot, stated. The order warning is blind to the regime failure and the regime warning is blind to the order failure, and both blindnesses are exact rather than approximate. A limit is not a prediction is the general version: the value of an instrument is bounded by how well its limits are known, and an instrument with an unstated blind spot is worse than none because it is trusted.

The list below is what is known to be missing; the section after it is about the part that cannot be listed at all, which is everything nobody has thought of yet.

What is still not caught #

Honesty about the pair requires saying what a third failure would look like and admitting that nothing here detects it.

A stream whose ranking moves within each half of a shard and not between them defeats the order warning by construction — take the drifting stream and reverse its second half, and the two halves’ top $k$ agree while nothing was ever stably heavy. That is a constructed adversary rather than a stream anybody has, and constructing it and measuring it is a job nobody has done.

Splitting more finely is the obvious repair and it trades one blind spot for sampling noise: quarters give a shorter baseline over which a ranking can be seen to move, so a stationary stream’s own fluctuation starts to register. Where that trade balances is unmeasured, and the honest guess — recorded here as a guess — is that the answer is not a finer split but a statistic that compares each sub-block’s top $k$ against the shard’s overall top $k$ rather than against its neighbour’s.

The check, and the shape it has to have #

The claim this essay makes is that a warning is silent for the right reason, and that is a harder thing to check than a warning firing.

Firing is one clause: the drifting stream’s statistic must exceed a threshold. Silence needs two: the statistic must be low on the bursty stream, and the prediction must be accurate there. A check on the first alone would pass on a broken statistic that read zero everywhere. A check on the second alone would pass on a stream nobody warned about and nobody needed to.

So the assertion requires both, on both streams, plus the regime clause: at sixty-four shards the stationary stream’s leaf model must be more than 30% out while its order warning stays low. That last conjunction is the whole essay in one line — a large failure with a silent order warning is the thing that establishes the two failures are different objects.

The fifth quadrant #

The four-way reading below is complete over the failures that have been characterised, and there is a fifth case it cannot express: both statistics silent and the prediction wrong anyway.

That is not a hypothetical. It is the state the whole apparatus was in before the regime failure was found — the order warning silent, correctly, and the leaf model 46% out at a shard count nobody had swept to. A deployment reading the diagnostic at that moment would have seen two silences and concluded the prediction was good, and it would have been the fourth quadrant’s answer to a question in the fifth.

The general problem has no solution, because a statistic detects a failure somebody has already characterised and the fifth quadrant is by definition the failures nobody has. What is available is a residual, and the residual is affordable.

Run the structure occasionally and compare. A capacity plan is made from histograms and the plan is then executed; once the structure exists, its measured damage can be compared against what was predicted for it, and the difference is a direct reading of the fifth quadrant. It costs one comparison per deployment rather than one per query, it needs no new instrument, and it accumulates: a sequence of residuals plotted against whatever parameter is being swept is exactly the instrument that would have caught the regime failure at 4, 8 and 16 shards rather than at 32.

Two things make that worth doing rather than a counsel of perfection.

The residual is a trend rather than a value. One residual of 10% is inside anybody’s tolerance and says nothing. Three residuals of 1%, 0% and 10% across a doubling parameter is a trend, and reading it as one is the habit this essay is really about — the same habit the site’s fitting machinery formalises, applied to a model’s error rather than to an algorithm’s cost.

And it converts an unknown failure into a known one, once. The regime failure is now characterised, has a statistic, and is in the table. The next one will be found the same way or not at all, and the residual is the only thing that looks in the right direction.

So the honest form of the diagnostic is three readings rather than two: the order warning, the regime warning, and a running residual against whatever the deployment is varying. The first two are gates and the third is the thing that finds the next gate.

What a deployment reads #

Both statistics come off the shard histograms, so the whole diagnostic is: split each shard in half and compare the top $k$; merge the histograms pairwise up the fold and look at the floors. Neither needs a summary.

The reading is then four-way. Both silent: the prediction is good, which is the stationary case at eight shards. Order fires: expect an overshoot, of the size the histogram that cannot see the order measured. Regime fires: expect an undershoot, and use the level account with the merged-floor law from the floor a merge does not settle at rather than the leaf model. Both fire: the two errors have opposite signs, the sum is unpredictable, and the honest answer is to run the thing.

That last quadrant is where a deployment at high shard counts on a drifting stream sits, and it is the case the whole arithmetic was built to avoid having to run. Saying so is better than reporting a number from it.

The honest limit is that the regime warning is a threshold nobody has calibrated. “How far the level floors are from doubling” reads 0.03 where the model is exact and 0.53 where it is 46% out, which is a clean separation on the four streams and five shard counts measured — and there is no measurement here of what value corresponds to what error, so it says whether rather than how much. The order warning has the same limitation and has had it since it was written. Both are usable as gates and neither is usable as a correction.