When the stream takes it back

The property a Count-Min sketch is built around is that its answer is never too small. Not usually, not with high probability — never. It is a consequence of arithmetic rather than of chance: every cell is a sum of counts, all of them non-negative, and the cell a key lands in contains that key’s own count plus a non-negative pile of other keys’. The minimum over rows is the smallest such pile, and it is still a pile.

Here is the same structure on a stream of 60,000 updates over 2,048 keys where half the updates are decrements.

Three models, and only one of them is usually named #

The streaming literature has names for these and they are worth learning, because almost every published accuracy figure belongs to one of them and says which about as often as a benchmark says which machine.

Cash register. Every update adds. The frequency vector only ever grows. This is the model of every measurement in the previous phase of this field and of every one in the three essays before this.

Strict turnstile. Updates may be negative, but no key’s count is ever allowed to go below zero. A count of items currently in a set, or of sessions currently open, is in this model: things are removed only after having been added.

General turnstile. Updates may be negative and a count may end up negative. Streams of differences live here — the change in a metric between two feeds, a set of adjustments applied in whatever order they arrived, a reconciliation between two replicas.

The distinction between the second and the third is the one this essay turns on, and it is the one most often skipped. Count-Min’s one-sidedness holds in the strict turnstile exactly as it does in the cash register, and fails in the general one.

Why the proof survives one and not the other #

The proof is three lines and each line is worth setting out, because which line breaks is the whole content.

A cell holds $\sum_{y : h(y) = c} f_y$. The queried key $x$ is one of those $y$, so the cell is $f_x + \sum_{y \neq x, h(y)=c} f_y$. If every $f_y \ge 0$ then that second term is at least zero, so the cell is at least $f_x$, so the minimum over rows is at least $f_x$.

The condition is on the frequency vector at query time, not on the updates. A strict turnstile stream can subtract as much as it likes; every $f_y$ is still non-negative when the query arrives, the second term is still a sum of non-negative numbers, and the estimate is still an upper bound. A general turnstile stream can leave some $f_y$ negative, the second term can be negative, and the guarantee is gone.

The structure cannot check the condition. A Count-Min sketch has no way to know whether some key’s count went negative — that is exactly the sort of per-key fact it does not store. It will run, it will answer, and its answers will be below the truth without any indication that the model has changed.

Measured #

Over all 1,988 keys with a nonzero count, on a general turnstile stream with half the updates negative:

Two things in that table and the second is the sharper.

The one-sided structure is under the truth nine times in ten, which is not a degradation of the guarantee but its inversion: an estimate one could previously treat as an upper bound is now, in practice, a lower bound most of the time. And the structure that never promised a direction is both closer to the truth — a third of the error — and honest about which way it is wrong, because being wrong in both directions was always what it said it did.

More state does not help #

The natural response to a structure being wrong is to give it more room. Here is what that buys.

Thirty-two times the state and the share does not move. If anything it rises slightly, and the reason is worth following: a wider table means fewer keys per cell, so the positive mass that used to mask a negative neighbour is no longer there. The extra state removes the noise that was concealing the failure.

That is a genuinely uncomfortable shape. The usual relationship between state and quality — more bits, better answers — is intact for the magnitude of the error, which does fall. It is inverted for the property, which was never a matter of accuracy at all.

Before that list, one thing worth settling: whether a system is in the third model is a question about its sources rather than about its code, and it is therefore a question nobody looking at the sketch can answer. The updates arrive already signed, the structure adds them, and whether some key’s total is allowed below zero depends on whether every subtraction is guaranteed to follow an addition of the same key — a guarantee that lives in whichever service produced the stream, is rarely written down, and is exactly the kind of property that holds until a retry, a reordering or a second producer arrives. That is why the four situations below are worth enumerating: each is a perfectly ordinary way for that guarantee to lapse without anybody deciding to lapse it.

Where general turnstile streams come from #

It would be convenient if the third model were exotic. Four places it is not:

Differences between two feeds. Subscribe to two sources and sketch the difference: additions from one, subtractions from the other. Nothing constrains the result to be non-negative and the whole point is to find where the two disagree.

Adjustments applied out of order. A distributed system that emits corrections — “that event was double-counted, subtract two” — can deliver the correction before the event, and a sketch that processes them as they arrive is in the general model for as long as the reordering lasts.

Windows implemented by subtraction. The obvious way to maintain a summary of the last hour is to add each arrival and subtract it again an hour later. If the subtraction is driven by a separate timer or a separate feed, a key whose insertion was missed still gets its deletion, and the count goes negative.

Reconciliation. Two replicas exchange sketches to find where they differ. The difference of two frequency vectors is a general turnstile object almost by definition.

Each of those is a normal engineering situation and none of them looks, at the point of writing the code, like leaving a model behind.

The strict model is where most systems actually are #

It is worth dwelling on the middle case, because a reader who has followed this far may conclude that deletions are dangerous and they mostly are not.

A count of things currently present — sessions open, items in a cart, rows in a partition, files in a directory — is a strict turnstile quantity by construction: nothing is removed that was not first added, so no count can go below zero, and Count-Min’s theorem applies without a word of modification. The measurement above bears that out at every deletion rate the generator can produce while holding its own condition.

The middle row is the one to look at twice. That stream is in the general model — 216 of its keys end with a negative count — and Count-Min was above the truth on all 200 keys queried. The guarantee did not hold; it merely was not observed to fail, because the keys queried were the heavy ones and the heavy ones stayed comfortably positive.

So the symptom is a function of which keys are asked about, and the guarantee is a function of the model. Those are different things, and a test that queries the top hundred keys will find a violated model perfectly healthy for as long as the violation stays in the tail.

The distinction between refusing and warning is worth one sentence of its own, because it is the difference between a check that runs and a check that gets ignored.

The machinery, and why it refuses rather than warns #

The library behind these figures will not run a summary outside the model it declares. runUnder takes a structure, a sequence and a model name, and it throws twice: if the structure does not declare itself valid in that model, and — the more useful half — if the sequence is not actually in the model it was offered as.

The second check is computed from the updates rather than declared alongside them. A sequence generated with deletions and labelled cash-register is caught before anything is measured, which is a mistake nothing else here would notice: the estimates come back, they look reasonable, and the number on the plate is a measurement of something that was never claimed.

Every figure in this essay was drawn from a run that violated its model deliberately, and each one says so. That is the family’s own rule — { anyway: true } returns the violation rather than swallowing it, and the plate prints it — and it exists because a plate that quietly rendered an out-of-model run would be committing the exact error the essay is about.

This is the same device as the one-pass wrapper and the table that throws on a cell read before it is written: the model’s defining restriction, enforced by the machinery instead of remembered by the author.

What is left when the direction goes #

Count-Min in the general turnstile is not useless, and saying what remains is more useful than saying what is lost.

The magnitude bound survives, in the right norm. The error is still bounded by $\varepsilon \lVert f \rVert_1$ of the net vector, with $\varepsilon = e/w$ — it is now two-sided, that is all. The usual repair is to take the median of the $d$ cells rather than the minimum, which is unbiased in this model and gives a bound with the same shape. At which point the structure is Count-Sketch with worse signs, which is a fair summary of the situation.

Linearity survives everything. The table is the sum of the updates, so it can be merged, subtracted, and reconciled in the general model exactly as in the cash register. That property is what makes turnstile streams tractable at all, and it is the subject of the strangest measurement in this phase, which is in the next paragraph but one.

Nothing else does. The upper-bound reading, the confident filtering, the ability to say “at most”, the composition arguments — those were all consequences of the direction, and the direction is what went.

The bound is quoted against the wrong number #

One more measurement, and it is about a mistake the sketch does not make and its user easily does.

Build a stream of 19,027 updates in which nearly everything is added and then taken back: the net vector has an $L_1$ norm of 973 and the gross traffic is 19,027, so 94.9% of what went past has cancelled. Now build the same net vector directly, in 236 updates, one per key.

The two Count-Sketch tables are identical, cell for cell. Not close — identical, because a linear sketch’s state is the sum of its updates and the two sequences have the same sum. Every estimate is the same, every error is the same, and the structure has no way of knowing which sequence it saw.

The bound is $\varepsilon \lVert f \rVert_1$, and $\lVert f \rVert_1$ means the norm of the net vector, 973. Quote it instead against the number of updates — the natural reading of “the error is $\varepsilon$ times the length of the stream” — and the promised error is 19.6 times too large. On this stream the guarantee would be stated as ±808 when the structure’s actual guarantee is ±41.

The direction of that error is the merciful one: the quoted bound is too pessimistic rather than too optimistic. But it is a bound nobody can use, and it comes from the same habit as everything else in this essay — repeating a guarantee without its subject.

The repair that keeps the direction, and what it costs #

There is a construction that recovers a one-sided reading in the general turnstile, it needs no new theory, and its price turns out to be the quantity the previous section is about — which makes the two halves of this essay one thing rather than two.

Split the stream. Send every positive update to one Count-Min sketch and the absolute value of every negative update to a second. Each of those two streams is a cash-register stream by construction, so each sketch is exactly in the model its theorem was proved in, and each returns an over-estimate of its own half:

$$\hat{P}_x \ge f^+_x, \qquad \hat{N}_x \ge f^-_x$$

The estimate for the net count is $\hat{P}_x - \hat{N}_x$. It is no longer one-sided — one over-estimate minus another can land either way — but it now has a bound again, and the bound is the sum of the two: $\varepsilon(\lVert f^+\rVert_1 + \lVert f^-\rVert_1)$.

That norm is the gross traffic, not the net vector. On the cancelling stream measured above, the gross is 19,027 and the net is 973, so the repaired structure’s guarantee is 19.6 times weaker than the guarantee the single sketch has in the cash-register model — which is precisely the factor the last section identifies as the difference between quoting a bound against the stream and quoting it against the vector.

So the two findings are the same finding. A structure that keeps the positive and negative parts apart pays exactly the cancellation ratio, and a structure that adds them keeps the tight bound and loses the direction. Nothing recovers both, and the arithmetic says why: the direction is a statement about a sum of non-negative terms, and cancellation is what makes the sum stop being one.

Two things do survive the split and are worth having.

An upper bound on the positive part. $\hat{P}_x$ is a genuine one-sided over-estimate of how much was ever added for key $x$, whatever the deletions did. For a question like did this key ever exceed a threshold — which is what a great many alerting rules actually ask — that is the right quantity and the single merged sketch cannot supply it.

Twice the state. Two tables where there was one, which is the honest price beside the weaker bound, and which is why the split is a decision rather than a default.

The rule this leaves is narrow enough to apply mechanically: if the deletions are strict, use one sketch and keep the theorem; if they are not, either accept a two-sided estimate from one sketch or pay two sketches and the cancellation ratio for a bound whose subject is stated. What is not available is the reading everybody actually wants — a tight one-sided bound on a vector that cancels — and the arithmetic above is a short proof that it is not an implementation problem.

What to take from it #

The lesson is not that Count-Min is fragile. Its theorem is true, its proof is three lines, and both are unchanged by anything measured here.

The lesson is that a guarantee has a subject, and the subject is a model — a statement about what the input is allowed to do. The four dials this phase separates are whether updates may be negative, whether counts may end negative, whether items expire, and how independent the hashes are; the previous phase’s every measurement had all four set one way and none of its plates said so.

A structure cannot check its own model and a bound cannot carry one. What can is a declaration, checked against the data, at the point the two meet. That is what this field’s machinery now does, and this essay is what it was built for.