The bits given to the wrong keys

A filter that grows by moving a bit measured a filter that can be resized. A fingerprint table splits each key’s hash into a quotient — the slot index — and a remainder stored in that slot, and doubling the table moves one bit from the remainder into the quotient. The table grows in place, as one structure with one lookup, and the price is that each key’s stored remainder is one bit shorter, so the false-positive rate doubles at every doubling: 0.69% at the forecast and 5.7% at eight times it.

That page ended on a proposal. The rate doubles because every key’s fingerprint is the length it was given at the start. Keys arriving after a doubling could be given fingerprints one bit longer than the keys before, so that each generation’s contribution to the rate halves as the generation’s size doubles — the same geometric arrangement a stack of tightening filters uses, but inside one table and one lookup, with each slot recording which generation its fingerprint belongs to. No bits would be spent in advance and nothing could run out.

The design works, in the sense that it does what the proposal said it would do to the rate. It does not do what the proposal assumed about everything else, and the reason is one sentence long.

What lengthening buys #

A forecast of 2,000 keys at a target rate of 1% gives a fingerprint of 18 bits and a table of 4,096 slots. Grown to 64,000 keys — thirty-two times the forecast, five doublings — the designs separate.

Lengthening does slow the rate’s growth, and the two settings do it in two different ways. One bit a doubling takes the rate from 21.1% to 3.6% — a factor of six — and the curve is still rising. Two bits a doubling takes it to 1.6%, and the curve has visibly stopped: 1.5% at sixteen times the forecast, 1.6% at thirty-two.

The difference between rising and flat is an arithmetic the plate of generations makes plain.

The middle generations contribute the same amount each — 0.58%, four times over. That is not a coincidence: a generation holds twice the keys of the one before and has a fingerprint one bit longer, so its contribution is twice a half, which is one. One bit a doubling holds each generation’s contribution constant, so the total grows with the number of doublings rather than with the keys — logarithmically rather than linearly, which is the factor of six. Two bits a doubling halves each generation’s contribution and the total converges to a bounded sum, which is the flat curve.

So the proposal’s arithmetic was one bit out, and correcting it gives a design whose rate genuinely does not run away. A table that can grow without bound and hold its rate near 1.6% is worth having.

The two plates together also say something about where a lengthening table’s rate lives, which matters for the rest of this page. Under either rule the first generation is the largest single contributor — 32% of the total under one bit a doubling and 68% under two, on 4.8% of the keys. It is the generation with the shortest fingerprint, and shortest fingerprints are where a table’s rate comes from. That will turn out to be where its life comes from too.

What it costs #

A reserved table is cheaper than either lengthening rule. That is the first thing worth explaining, because it looks backwards: reserving five bits means carrying five extra bits in every slot from the very first key, against a growth that may never arrive, and lengthening spends nothing in advance.

The explanation is that a reserve is not carried for long. A reserved table’s slot width is the fingerprint minus the quotient, and the quotient grows with every doubling, so the reserve is spent down as the table grows — five extra bits at the forecast, four after one doubling, none after five. A lengthening table’s slot width, by contrast, must be wide enough for the newest generation’s remainder, which at one bit a doubling is exactly the original remainder and never shrinks. And on top of that every slot carries a length field: three bits, at five generations, to record which of six fingerprint lengths a slot holds.

Two bits a doubling is dearer again, and for a reason the design cannot avoid. Each doubling adds a bit to the newest fingerprint and one bit of it goes to the quotient, so the remainder grows by one bit every doubling — five extra bits per slot at 64,000 keys, in 131,072 slots. A bounded rate costs the same bits a reserve would have cost, paid as the growth happens instead of at the start.

That is the honest summary of the cost side: lengthening is a reserve paid in instalments, plus a length field. It is not a way of avoiding the reserve. It is a way of avoiding having to forecast it.

What it does not buy, which is the whole point #

A filter is a structure that is allowed to be wrong at a rate its caller chose, and a reserve is a forecast of how many keys that rate will have to cover. The reason to want a design without one is that a forecast can be wrong. A filter past its design size is the whole argument for caring: a filter given more keys than it was built for does not fail, it quietly stops meaning what its caller thinks it means. A design with no reserve to run out looks like the answer.

It is not, and the measurement is unambiguous.

Every lengthening table dies at thirty-two times the forecast, which is exactly where the table that reserved nothing dies, on exactly the same key — 98,304 of them, at the doubling that takes the quotient to eighteen bits.

The reason is the sentence the proposal did not have. A quotient filter’s quotient is the top bits of the fingerprint, and every generation in the table shares one quotient. A generation whose fingerprint is no longer than the quotient has nothing left over to store, so its keys cannot be placed at all — and they cannot be given longer fingerprints instead, because a filter does not keep its keys. The life of the table is therefore set by its shortest fingerprint, which belongs to the generation that arrived first.

Lengthening gives its extra bits to the newest generation. The newest generation is the one that will be asked to survive the fewest further doublings. So the design spends its whole budget on the keys that need it least, and the keys that decide when the table dies — the ones inserted before any doubling at all — get nothing.

The life is a subtraction, and it can be written down #

The point at which any of these tables dies is not measured so much as read off. A table built for a forecast of $n$ keys at a rate $\varepsilon$ takes a fingerprint of $p = \lceil \log_2 (n/\varepsilon) \rceil$ bits and a quotient of $q = \lceil \log_2 (n/\lambda) \rceil$ for a load factor $\lambda$, and each doubling adds one to $q$. The oldest fingerprint is exhausted when $q$ reaches $p$, so the number of doublings available is $p - q$, and the growth survived is $2^{p-q}$.

Here $p = 18$, $q = 12$, and $2^6 = 64$ — which is where the table with nothing reserved fails, at the doubling that would take $q$ to 18. The measurement reports 32 times the forecast rather than 64 because the last doubling happens when the load reaches three quarters, a little before the key count reaches the next power of two.

Written that way, the whole design space is visible at once. $p - q$ is the life; $p$ alone is the rate; and $q$ is fixed by the forecast and the load factor and is not a free parameter at all. Reserving $b$ bits means raising $p$ by $b$, which raises the life by a factor of $2^b$ and lowers the starting rate by the same factor. Lengthening raises $p$ for some keys and not others, and the life takes the minimum while the rate takes a weighted sum — so lengthening improves the quantity that averages and leaves the quantity that minimises exactly where it was. That sentence is the whole result, and the plate is its demonstration rather than its source.

It also explains why the reserve measured earlier worked as well as it did. A filter that grows by moving a bit found that $\log_2(\text{growth})$ reserved bits hold 0.66% in exactly a correctly built table’s 294,912 bits, and fail past the reserve. That is $p - q$ being raised by exactly the growth, applied to every key, which is the only arrangement in which the minimum and the average move together.

Why a stack does not have this problem #

The stack of tightening filters measured alongside these tables is the design the proposal was borrowing its geometry from, and it is worth being precise about why the borrowing failed.

A stack’s layers are separate filters. Each has its own bits, its own hash functions, and its own addressing, and a lookup consults every layer. Making a later layer’s rate tighter costs that layer more bits and affects no other layer, because nothing is shared. The layers are independent, and a geometric series over independent terms is exactly what the design wants.

A lengthening fingerprint table shares the one thing that matters: the slot array, and therefore the quotient. Its “generations” are not layers; they are subsets of one addressing scheme, and they are coupled through the quantity that decides the table’s life. The stack pays for its independence with a lookup per layer — the cost the resizable table was built to remove — and the coupling is what the removal buys and what it costs.

Sized for a rate that does not hold still is the third arrangement of the same trade, and the three of them close the space: a filter can be independent and pay per layer, shared and bounded by its shortest fingerprint, or resized by rebuilding and pay for the rebuild.

The numbers bear the comparison out. At 64,000 keys the stack holds 1.03% in 2,133,931 bits and the two-bit lengthening table holds 1.6% in 2,228,224 — within a few per cent of each other on both axes, which is what two designs implementing the same geometric series should look like. The difference is entirely what happens next: the stack adds a seventh layer and carries on, and the lengthening table stops. One lookup was bought at the price of a hard ceiling, and the ceiling is not visible anywhere in the rate.

That is the shape of every comparison on this page. The designs are close on the axes that are plotted and far apart on the one that is not, and the one that is not is the reason any of them exists — a filter is resized because its forecast was wrong, so the question a resizing scheme has to answer is how wrong the forecast may be.

What a designer should take from this #

A resizable fingerprint table has one parameter and it is the fingerprint length. The formula everybody sizes filters with is the static version of the same point, and the dynamic version is stricter: there is one number, it is bought once, and every scheme that tries to buy it in pieces is buying it for the wrong keys. Everything tried on these tables — reserving, lengthening, tightening — is a way of choosing it, and the life of the table is set by the smallest value present. The arrangement in which no generation is the weak one is the arrangement in which every fingerprint is the same length, which is a reserve.

So choose the reserve by how far the forecast could be wrong, not by how far it is expected to be wrong. Seven bits reserved reaches 256 times the forecast at 1.5%, for 8,388,608 bits; five reaches the same 256 times at 5.8% for 6,291,456. Both survive a forecast wrong by two orders of magnitude, which lengthening does not, and the extra two bits buy a factor of four in rate rather than any extra life. The life a reserve buys is $2^{p-q}$ and it is bought by $p$; the rate is bought by the same bits and is the thing that degrades gracefully.

And if the growth is genuinely unbounded, no single table will do. A table whose quotient grows without bound exhausts any fingerprint length eventually. The designs that survive unbounded growth are the ones that add structure rather than bits: a stack, which adds a layer, or a rebuild, which starts again with a new length. Lengthening is neither — it adds bits to one table — so it inherits that table’s limit.

The general form is worth carrying past filters. A structure with one shared addressing scheme and several classes of entry has a life set by its weakest class and a cost set by the average, and any scheme that improves the average without raising the minimum is buying the visible axis and leaving the invisible one alone. The evidence a filter cannot remove is the same asymmetry in a different quantity, and an insertion that can fail is what the failure looks like from the caller’s side: a structure that has been correct on every operation so far and then refuses one. The rate this page plots is a number a caller watches; the life is a number it discovers.

What is not measured here #

One growth pattern. Keys arrive steadily and the table doubles when its load reaches three quarters, so the generations are of doubling size. A stream that grew and then stopped would leave a table whose newest generation is small, and the rate would be dominated by the old generations for a different reason than the one measured here.

Bits, not runs and shifts. The model counts slots times stored bits, exactly as the earlier measurement’s did. A quotient filter’s real cost includes the runs and shifts of its linear probing and the metadata bits that delimit them; three metadata bits a slot are charged here and the time is not charged at all.

A length field, charged at its information content. Every slot is given $\lceil \log_2 (G+1) \rceil$ bits to record which of $G+1$ generations it belongs to, which is the least a fixed-width field can be. A real implementation might encode it more cheaply — most slots belong to the newest generations — or more expensively, aligned to a byte. Charging the minimum is the choice that is hardest on the reserve, and lengthening still loses.

Thirty-two bits of hash. Two bits a doubling at 128 times the forecast wants a 32-bit fingerprint, which is the whole hash this model has. That is a limit of the measurement rather than of the design, and it is why the two-bit rule is drawn only to 32 times.

One forecast and one target. The 18-bit fingerprint and the 12-bit quotient come from 2,000 keys at 1%, and their difference — six — is what sets the five-doubling life. A design with a longer fingerprint lives proportionally longer, and the relation is the one stated above rather than a measured sweep.

Still open: what a table should do the day it can no longer grow #

Every design here dies the same way and none of them says what happens next. A table that cannot place a key has to rebuild — a new table with a longer fingerprint, and every key re-inserted, which needs the keys and a filter does not have them. In practice the keys are somewhere: the store the filter is a filter for.

The measurement that follows prices that rebuild against the two designs that avoid it. It reads the keys back from a store at a stated cost per key, rebuilds at a fingerprint chosen for the size now reached, and compares the total — bits held and keys re-read — against a stack that never rebuilds and against a reserve large enough never to need to, over a growth of a thousandfold. The prediction from this page is that the rebuild wins on bits by a wide margin and that the question is entirely how much a key costs to read back, which is a number the filter’s own design cannot see and its caller always can.