A filter that grows by moving a bit

A filter past its design size measured what a Bloom filter does when it is given more keys than it was sized for, and the answer was that it keeps working and gets steadily worse. Sized for 2,000 keys at one per cent, it answers yes to 15.6% of absent keys at 4,000 and 97.8% at 16,000, and nothing about it ever fails or warns. The same essay measured the standard repair — a stack of filters, each new layer larger and tighter than the last — which stays under a bound stated in advance at any size, and pays for it in bits and in a lookup that consults every layer.

It ended on the reason the stack has to keep its old layers. A Bloom filter’s bits are positions computed modulo its length, and a bit set in a filter of $m$ bits says nothing about where the same key’s bit would fall in a filter of $2m$. The filter keeps no keys, so it cannot recompute them. It can only be left as it is and have another filter put beside it.

A filter that stores fingerprints in slots is different, and that essay predicted how. A fingerprint carries some of the bits of a key’s hash, and a table of fingerprints can double by spending one of those bits to say which half of the larger table each fingerprint belongs in. The table then grows as one structure, at the cost of a fingerprint one bit shorter. This page builds that table, gives it the keys the stack was given, and measures the rate and the bits of each up to thirty-two times the forecast.

A fingerprint and the table it lives in #

The table here follows the design of a quotient filter. When a key arrives it is hashed once to a fingerprint of $p$ bits, and the key itself is discarded. The table has $2^q$ slots. The fingerprint’s top $q$ bits — its quotient — name the slot it belongs to, and the remaining $p - q$ bits — its remainder — are what is written there, beside three bits of bookkeeping that let neighbouring slots hold fingerprints whose home slot was taken.

A query hashes its key to $p$ bits in the same way and looks in the fingerprint’s home slot and its neighbours for the same remainder. So an absent key is reported present exactly when its $p$-bit fingerprint equals the fingerprint of some key that was stored. Nothing else can cause a false positive and nothing can cause a false negative.

Doubling is where the design pays off. When the table passes a load of three quarters, it moves to $2^{q+1}$ slots. Every stored fingerprint’s quotient gains one bit, taken from the top of its remainder, and its remainder loses that bit. The fingerprint itself — all $p$ bits, split differently — is unchanged, and it is moved to one of two slots in the new table, chosen by the bit it just gave up. No key is needed, because the table stored everything it needs to place each fingerprint again.

That is exactly the move a Bloom filter cannot make, and exactly the move the deletable filter measured earlier cannot make either. That filter keeps a fingerprint in one of two buckets, the second found from the first by combining it with a hash of the fingerprint modulo the table’s size. Doubling it would need to know which of two buckets in the larger table each fingerprint’s first bucket became, and the bit that decides it was never stored.

The measurement here counts what matters for the comparison and nothing more. The rate is measured exactly, by checking every absent key’s fingerprint against the set stored. The space is counted as slots times stored bits — remainder plus three. How long a lookup spends walking neighbouring slots, and how long a doubling takes, are not modelled.

Growing with nothing reserved #

A fingerprint table sized for 2,000 keys at one per cent needs fingerprints of $p = 18$ bits, since $2{,}000 / 2^{18}$ is 0.76%. It starts with 4,096 slots, each storing a remainder of six bits, and measures 0.69% at its forecast.

It then grows without complaint. It doubles at 3,073 keys, at 6,145 and at 12,289, moving 21,504 fingerprints in all, and at every size it remains one table answering every query with one lookup. And its rate doubles with its keys: 1.5% at 4,000, 2.9% at 8,000, 5.7% at 16,000.

The reason is in the definition of a false positive. The rate is the chance that a random 18-bit fingerprint equals one of the $n$ stored, which is about $n / 2^{18}$, and nothing about the table’s slots appears in that expression. Doubling the table changes where fingerprints are kept and does not change what they are. So the table’s promise at its forecast is exactly as much a function of the key count as a Bloom filter’s is. The difference is only in the shape of the failure: the Bloom filter’s rate rises as a seventh power of its fill, reaching 97.8% at eight times, while the fingerprint table’s rises in proportion to its keys, reaching 5.7%.

That is a far gentler failure, and it is still a failure. A filter sized for one per cent that answers yes to one absent key in eighteen is doing a sixth of the work it was deployed for.

Reserving bits for growth #

Since the rate depends only on the fingerprint’s length and the keys stored, the repair is to make the fingerprint longer before the keys arrive. Each extra bit halves the rate at every size. A table with three extra bits — 21-bit fingerprints — starts eight times below its target, at 0.090% for 2,000 keys, and reaches the target only when it holds eight times the forecast: 0.66% at 16,000.

The reserve is therefore a statement about growth rather than about size. Reserving $b$ bits holds the rate for up to $2^b$ times the forecast, whatever the forecast was. That is a more forgiving thing to have to know. A forecast of how many keys a filter will hold is a number with no margin in it; a forecast of how many doublings it may undergo tolerates an error of a factor of two in each direction per bit.

What a reserve costs #

A reserved bit is a bit in every slot, so it costs from the first key. At the forecast, the table with three bits reserved holds 49,152 bits against 36,864 with none reserved — a third more — and against 19,171 for a Bloom filter sized for 2,000 keys. For as long as the growth has not happened, the reserve is insurance that has not paid.

At the size the reserve was chosen for, it costs nothing extra at all. A fingerprint table built from the start for 16,000 keys at one per cent needs 21-bit fingerprints and 32,768 slots, with six bits of remainder and three of bookkeeping in each: 294,912 bits. The table that started at the forecast with three bits reserved, and doubled three times, holds 294,912 bits at 16,000 keys. It is not approximately the same table; it is bit for bit the same size, since its fingerprint length and its slot count have arrived at the same values. That equality is checked, not assumed. A table that grows by moving bits wastes nothing by having grown.

The stack’s space tells the opposite story. It starts cheap — 22,056 bits at 2,000 keys, close to a single filter — and at 16,000 keys holds 428,938, 2.8 times what a Bloom filter sized in hindsight would need and 1.45 times the reserved fingerprint table, for a rate of 0.93% against 0.66%. Its overhead is structural: each layer is sized for a tighter rate than the one before, and a Bloom filter needs about 1.44 more bits per key for every halving of its rate, so the stack’s newest keys are its most expensive.

What neither plate hides is that the fingerprint table is not the smaller structure per key. At its forecast it holds 18.4 bits per key where a Bloom filter at one per cent holds 9.6, because a quarter or more of its slots are empty at any time and each slot carries three bits of bookkeeping. A fingerprint table is not chosen to save space over a correctly sized Bloom filter. It is chosen because a correctly sized Bloom filter requires a correct forecast.

Past the reservation #

A reserve sized for eight times the forecast is a forecast, and the next plate gives the table what the forecast did not allow for. At 32,000 keys the table with three reserved bits is at 1.5% and at 64,000 at 3.1%, climbing in proportion to its keys exactly as the unreserved table did from the start. The site’s check includes this as a claim that must fail: that three reserved bits hold the target at thirty-two times the forecast.

The stack holds. Six layers deep at 64,000 keys it measures 1.0%, at its bound, and it would stay near that bound at any size, which is the whole of what it offers. A table with five bits reserved also holds at 64,000 keys, at 0.74%, because five bits is what thirty-two times asks for.

The space at thirty-two times makes the comparison sharper. The table with five reserved bits holds 1,179,648 bits at 64,000 keys, which is again exactly what a table built for 64,000 keys would hold, and 1.9 times a Bloom filter sized in hindsight. The stack holds 2,133,931 — 3.5 times the hindsight filter, up from 2.8 times at 16,000 keys — because every layer it adds is tighter than the last and each is paid for in bits per key that the previous layers did not need.

So a generous reserve is cheap insurance on this range. The table with five bits reserved holds 360,448 bits at 16,000 keys, more than the three-bit table’s 294,912 and still less than the stack’s 428,938, for a rate of 0.14% against the stack’s 0.93%. Over-reserving by two bits cost 22% in space where growth stopped early, and bought a rate six times better than the stack’s at a lower cost than the stack.

Bits per key, and the floor under them #

The two families’ space can be written down, and writing it down says where the fingerprint table’s extra bits go. The formula everybody sizes filters with gives a Bloom filter about $1.44 \log_2(1/\varepsilon)$ bits per key at its optimum, which at one per cent is 9.6. No structure answering membership with that rate can use fewer than $\log_2(1/\varepsilon)$ bits per key, 6.6, and a filter that is allowed to be wrong is the site’s account of why a Bloom filter sits forty-four per cent above that floor.

A fingerprint table stores, per slot, a remainder of about $\log_2(1/\varepsilon) + \log_2 \alpha$ bits plus three, where $\alpha$ is the share of slots in use, and it stores a slot for every $1/\alpha$ keys. Its bits per key are therefore about $(\log_2(1/\varepsilon) + \log_2\alpha + 3)/\alpha$. A table that doubles at three quarters full is three eighths full just afterwards, which at one per cent comes to about 22 bits per key, and three quarters full just before the next doubling, about 12.3. Averaged over the keys that arrive between two doublings it is about 16 bits per key, a little under twice a Bloom filter’s 9.6. The table on the plate holds 18.4 at its forecast, where it is half full, a little above the expression’s 17.6 because a fingerprint’s length is rounded up to a whole bit. Nearly all of the difference from a Bloom filter is the empty quarter to five eighths of the slots, and the three bits of bookkeeping in each.

The empty slots are the price of doubling in place, since a table that doubled only when completely full would have no room to place a fingerprint whose home slot was taken. So the comparison with a Bloom filter is not a close call that a better implementation might reverse. A fingerprint table spends bits on having somewhere to put the next key, and a Bloom filter spends none, because it has already decided that there will be no next key beyond its forecast.

Two kinds of promise #

A guarantee names its model, and these three structures name three different ones.

The Bloom filter’s rate holds at one size, the one it was built for. The fingerprint table’s holds over a range of sizes, $2^b$ wide, where $b$ was chosen at the start; within it the table is one structure with one lookup, and at the top of it the table costs exactly what a table built for that size would. The stack’s holds at every size and its model contains no number of keys at all — which is why its space grows faster than its keys, and why a lookup at 64,000 keys consults six filters.

Choosing a growth factor found that a dynamic array’s doubling is paid for by space allocated ahead of need, and what amortised means is why that is cheap when spread over the insertions it serves. The fingerprint table does both things at once. It doubles its slots like an array, moving every stored entry each time — 95,232 fingerprints moved over five doublings to reach 64,000 keys, about one and a half moves per key. And it allocates its reserved bits ahead of need, in every slot, from the first key. The first cost is spread over insertions and disappears into the average. The second is spread over the range of sizes the table can serve and disappears at its top.

What the measurement leaves out #

Time. A quotient filter’s lookup walks a run of neighbouring slots, which grows as the table fills, and its doubling moves every fingerprint at once — a pause proportional to the table, where a stack never moves anything. A lookup in neighbouring slots is also a cache-friendly lookup, one or two lines where each layer of a Bloom stack costs a line per hash; the bucket that fits a line is the site’s measurement of what that is worth, and none of it is measured here.

The load at which a table doubles. Every table here doubles at three quarters full. A table allowed to run to nine tenths holds fewer empty slots and fewer bits per key, at the price of longer runs; the rate is untouched by the choice, the space is not.

Deletion. A quotient filter can remove a fingerprint, with the precondition the evidence a filter cannot remove found for the site’s cuckoo-style filter: removing a key that was never inserted removes some other key’s fingerprint. Doubling does not change that.

Where the keys are kept. Every structure here assumes the keys are gone once inserted. A system that keeps them can rebuild a correctly sized filter whenever it likes, and the filter each run carries is the case where a store does exactly that, run by run. Sized for a rate that does not hold still measures the neighbouring problem, where the number that was forecast is the rate rather than the size.

A limit on doublings. Each doubling moves one bit from remainder to quotient, so a fingerprint of $p$ bits in a table of $2^q$ slots can double only until its remainder is gone. The tables here have eighteen to twenty-three bits and never come near it, but it is a hard edge rather than a slope: the table cannot grow past it at any rate.

Still open: fingerprints that lengthen as the table grows #

The reserve is the fingerprint table’s weakness in one number: it is spent at the start, on every slot, against a growth that may never come, and it runs out at a fixed multiple of the forecast. The stack’s strength is the opposite: each layer is sized for its own keys, at a rate chosen when it is created.

There is a design between them. Keys that arrive after a doubling can be given fingerprints one bit longer than the keys before, so that the rate each generation contributes halves, as a stack’s layers do — while all generations share one table and one lookup, since a slot can record how long its fingerprint is. The rate is then bounded by a geometric series in one structure, and no bits are reserved in advance. The measurement that follows builds that table, gives it the same keys to thirty-two times the forecast, and asks how its bits compare with the stack’s and with a correctly reserved table’s — and what the bookkeeping for fingerprints of several lengths costs in the slots.