The day a filter cannot grow

The bits given to the wrong keys ended with a table that could not store its next key. A fingerprint table keeps the top bits of each key’s fingerprint as a slot number and stores the rest. Every time it doubles in place, one more bit moves into the slot number and one fewer is stored. When the slot number has taken every bit of the shortest fingerprint, that key has nothing left to store, and the table can go no further. Lengthening the fingerprints of later arrivals does not help, because the day of death is set by the keys that arrived first. The table cannot give them longer fingerprints, because a filter does not keep its keys.

That essay’s closing section pointed out that the keys are not lost. They are in the store the filter is a filter for — the database, the log-structured store, the set of URLs already crawled — and the whole point of the filter is to avoid reading that store when the answer is no. On the day the table cannot grow, it can read the keys back, choose a longer fingerprint for the size it has reached, and build a new table. The section proposed pricing that rebuild against the two designs that never need one: a reserve large enough for the whole growth, and a stack of filters that adds a layer instead. It predicted that the rebuild would win on bits by a wide margin, and that the choice would come down to what a key costs to read back.

The measurement confirms the second half and refutes the first. At the rate the reserve holds, the rebuild does not save bits at the end of the growth. It saves them in the middle, and whether that matters depends on a quantity neither design can see.

Four ways through a thousandfold growth #

Every table starts from a forecast of 2,000 keys at a target rate of 1%, which gives an 18-bit fingerprint and 4,096 slots. The growth runs to 2,000,000 keys, a thousand times the forecast, and at checkpoints six to a doubling each design is asked about 20,000 keys it does not hold. The table is the model of a filter that grows by moving a bit: a slot count doubled whenever the load passes three quarters, the rate exactly the chance that an absent key’s fingerprint equals a stored one, and bits counted as slots times stored bits, three of them metadata.

Four designs take the growth:

• Ten bits reserved. One table with a 28-bit fingerprint from the start: $2^{10}$ is the thousandfold, so its rate reaches the 1% target only at about 1,300 times the forecast. It never rebuilds.
• Rebuilt from the store. One bit reserved, and a rebuild whenever the table’s own rate passes 1%. The table can compute that from its count and its fingerprint length, as $n / 2^p$, without asking anything. A rebuild reads every key back from the store, charges one read each, and makes a new table with a fingerprint sized for the keys held now at 1%, plus the reserved bit.
• Rebuilt only when it cannot grow. No reserve and no rate ceiling: the table doubles in place until it dies, and only then reads the store. This is the literal reading of the earlier essay’s question.
• A stack of Bloom filters. The design a filter past its design size measured: a layer for the forecast at half the target rate, each new layer twice the capacity and half the rate of the one before, added when the top one fills.

The rate each one holds #

Rebuilding on the day of death is the wrong day. A table with nothing reserved doubles its rate every time it doubles its keys, because its fingerprint length is fixed and the keys competing to match it double. By the time it cannot grow it has doubled six times and is answering yes to 28.7% of absent keys. That is one lookup in three and a half going to the store for nothing, which is exactly what the filter exists to prevent. After the rebuild it starts again at a longer fingerprint and climbs again, to 11.2% by the end of the growth.

A rebuild triggered by the rate instead keeps the table between 0.35% and 1.05% for the whole thousandfold. It never needs to wait for the table to die, because the table’s own count says when the rate has passed its target. That count is the one number a fingerprint table always knows about itself. The day a filter cannot grow is several doublings after the day it stopped being the filter its caller asked for, and the second day is the one to act on.

The reserve and the stack both stay under the target without rebuilding, and in opposite ways. The reserve starts far better than it needs to be: not one of 20,000 absent keys is answered yes until the table holds eight times its forecast, because its 28-bit fingerprint was chosen for two million keys and holds only two thousand. It then worsens steadily to 0.68%. The stack starts near its layer’s half-target and creeps up as layers are added, towards the sum of its layers’ rates, 1.06% at the end.

Where the bits go #

At the end of the growth, the reserve and the rebuilt table hold exactly the same bits: 18.9 a key. That is not a coincidence of the measurement. At two million keys the rebuilt table has a fingerprint sized for two million keys at 1% plus one reserved bit, which is 28 bits. The reserve’s fingerprint is the forecast’s 18 plus 10 reserved, also 28. Both have the same slot count, the same stored bits and the same rate, 0.68%. They are the same table, reached by two routes.

The routes cost different amounts along the way. The reserve carries its ten extra bits from the first key, and every doubling moves one of them into the slot number, so its bits per key fall from 38.9 at the forecast to 18.9 at the end — a reserve spent down as the growth arrives, as the earlier essay put it. The rebuilt table carries one extra bit at any time and holds between 18.4 and 20.5 bits a key throughout. At four times the forecast the reserve holds 34.8 bits a key to the rebuilt table’s 18.4, nearly twice; at sixty-four times, 26.6 to 18.4.

So the prediction’s “wide margin” exists, but in the middle of the growth rather than at the end. And it is a margin in bits per key, which is not the same as a margin in bits. The reserve’s excess is largest when the table is smallest. At four times the forecast, 8,000 keys, its excess is about 130,000 bits, 16 KB. At the end, where the table is a thousand times larger, its excess is zero. A reserve is expensive in exactly the period when it is cheap in absolute terms.

The stack’s bits follow a different pattern. Each new layer is allocated at its full capacity, so bits per key jump when a layer is added and fall as it fills: 36.4 a key at sixty-four times, when a large new layer is nearly empty, and 23.1 at the end, when the tenth layer is mostly full. On average across the growth it holds more than either table. It also pays in another currency the tables do not: a lookup must consult every layer, ten of them by the end.

What the store is read for #

The rebuilt table’s price is reads, and the plate shows how many. Holding the rate under 1% with one bit reserved means a rebuild at every doubling. The rebuilt table starts each doubling at half the target and reaches the target after one doubling. Each rebuild reads every key held, so the total is the geometric series $n + n/2 + n/4 + \dots$, a little under two reads a key. It sits at 1.85 through most of the growth and 1.34 at the end, where the last rebuild happened well before the last key.

Loosening the ceiling to 2% halves the rebuilds and more. With one bit reserved and a 2% ceiling the table rebuilds every other doubling and ends at 0.45 reads a key, with a worst rate of 1.96% and 16.8 bits a key. The reserve and the ceiling are two dials on one trade: each reserved bit halves the starting rate and doubles the interval between rebuilds; each doubling of the ceiling does the same to the interval and doubles the worst rate. The formula everybody sizes filters with is the static version of this arithmetic; the growing version adds a third quantity, the reads, and the three trade against each other as $2^{-r}$.

Two reads a key over the life of a filter is a large or a small number depending entirely on what a read is. A filter in front of a disk-resident store rebuilds by scanning the store, sequentially, at the store’s full bandwidth. A filter in front of a remote service rebuilds by asking the service for every key it holds, which may not be possible at all. The filter’s own design sees neither case, and the caller always knows which one it is.

If the growth stops early #

The reserve and the rebuild reach the same table at the end of a thousandfold growth, so the question between them is what happens if the growth does not arrive. A reserve is sized for the worst case a designer can imagine. The growth that actually happens is usually smaller.

The plate is the exchange rate the earlier essay asked for, in the only units the two designs share. If the growth stops at three times the forecast, the reserve is holding 11.6 bits a key more than a rebuilt table would, and the rebuilt table has read the store 0.93 times over to get there: 12.5 bits held, for every key read. If it stops at twenty-two times, the exchange is 4.2 bits per key read; at a hundred and eighty times, 1.6. Past about seven hundred times the reserve has spent its excess entirely and the rebuilt table holds the same bits for its reads.

So the choice is between two numbers the designer knows and the filter does not: how sure the growth is, and what a read costs. A caller that expects the full thousandfold and cannot read its store cheaply should reserve. A caller whose forecast is a guess — which is the reason a filter past its design size is a page at all — pays for the reserve up front in proportion to how badly the guess might miss. At the start that is twice the bits of a table that can rebuild. A caller that can read its store sequentially at little cost should rebuild, and should do it on the rate rather than on the day the table dies.

The ledger at two million keys #

The ledger puts every cost side by side, and no design dominates. The reserve spends no reads and has the best rate at the end, and past about 1,300 times the forecast its rate would pass the target with nothing it could do about it — it can keep doubling in place for sixteen doublings, but only with a fingerprint chosen at the forecast. The rebuilt table spends reads to hold a steady rate and would survive any growth. Its rate is at the target at worst rather than well under it, which is what it was asked to do. Rebuilding only at death is cheapest in bits and reads by far, because it is barely a filter: at its worst it answers yes to more than a quarter of the keys it does not hold, and every one of those sends a lookup to the store for nothing. The stack needs no forecast, no reads and no rebuild, and pays for that in bits and in ten lookups where every table pays one.

That last column is the one the earlier essays kept returning to. A stack is the design that keeps its layers independent, so tightening one layer never touches another. It pays with a lookup per layer. Positions confined to one line priced a single Bloom lookup in cache lines, and a stack multiplies that price by its depth. A rebuilt table keeps a single lookup and a single addressing scheme, and pays with reads of a store instead.

Three arrangements, each paying in its own currency #

The earlier essay closed the design space in one sentence: a filter can be independent and pay per layer, shared and bounded by its shortest fingerprint, or rebuilt and pay for the rebuild. The ledger puts a price on the third and shows that the three currencies do not convert into each other without a number from outside.

A layer is paid in lookups, every lookup, forever. A reserve is paid in bits, most heavily at the start, and the bits are wasted exactly to the extent the forecast of growth was pessimistic. A rebuild is paid in reads of a store, once per doubling or less, and it is possible only when the store exists and can be read. None of the three can be declared best by the filter, because the exchange rates between lookups, bits and reads are properties of the system the filter sits in.

That is the same shape as the choice a filter allowed to be wrong began with. A filter’s rate is a number its caller chooses and the filter merely delivers. Here the caller chooses a second number, how the delivery is paid for, and the filter can only report what each option would cost. The most useful thing a growing filter can do is make that report possible: count its keys, know its own rate, and say how many reads a rebuild would take before it takes them. A filter that dies without warning — the failure an insertion that can fail describes from the caller’s side — has withheld the one piece of information that would have let its caller choose.

What was measured and what was not #

The table’s rate is exact and its layout is not simulated. A key is a false positive exactly when its fingerprint equals a stored one, so the rates are measured, not modelled. The runs and shifts a real quotient filter performs on insertion cost time, not bits, and are not simulated; the rebuild’s time is charged only as reads of the store.

A read is a key, not a block. A rebuild from a store that is itself sorted and blocked reads blocks, and a key’s share of a block can be a small fraction of a read. That would make every rebuild cheaper than the reads plate says, by as much as the keys a block holds. The plate counts keys because that is the unit the filter’s caller can count without knowing the store.

The store is assumed to hold exactly the filter’s keys. A filter over a store that has had keys deleted would rebuild over the store’s current keys and lose the deleted ones, which a filter usually cannot delete by itself — a real advantage of rebuilding that is not measured here. The evidence a filter cannot remove is the page on what a filter does with a key it should forget.

One growth, one seed. The keys arrive at an even pace through a thousandfold growth. A growth that stops, restarts or reverses would move the rebuilds, and the rate plate’s 1.05% is a worst case over checkpoints six to a doubling, not over every key.

The stack is the earlier essay’s. Its first layer holds the forecast at half the target and each layer doubles. A stack whose layers grew faster would need fewer lookups and more bits, and the design space of stacks was not swept.

Still open: a rebuild that does not stop the table #

Every rebuild here happens all at once. The table reads the whole store, builds the new table, and switches. While it reads, the old table goes on answering — at a rate that has just passed its target — and the store is being read at full speed alongside whatever else it serves. For a store of two million keys that is a pause. For a store of two billion it is an operation that takes hours, during which the old table keeps growing.

The measurement that follows spreads the rebuild across insertions: after each new key, it also reads $c$ old keys from the store into a new table under construction, and switches when the new table is complete. It asks how large $c$ must be for the new table to finish before the old one’s rate passes its ceiling, what the rate is during the overlap, and what the two tables together cost in bits while both exist. The prediction from the arithmetic here is that $c$ of about two suffices when the ceiling is twice the starting rate, because a doubling’s worth of new keys must arrive while the old ones are read back. The cost is holding both tables for a whole doubling, which would bring the rebuilt design’s bits a key up to roughly the reserve’s in the middle of the growth. If that holds, the incremental rebuild removes the pause and gives back most of the saving that made rebuilding worth measuring.