A filter past its design size

Every Bloom filter is sized for a number. A filter is chosen by deciding how many keys it will hold and what false-positive rate is acceptable, and those two numbers fix the bits and the number of hash functions. The formula everybody sizes filters with measured how well the standard formula predicts the rate of a filter that holds the number of keys it was sized for, and found it predicts well.

The number is a forecast. A filter over a user table is sized for the users there will be; a filter over a cache is sized for the entries the cache will hold; a filter in a distributed join is sized before either side knows how many keys it contributes. The intersection two filters cannot report found one filter’s error set by another filter’s load, which makes the question of what happens when a load is wrong more pressing than it looks.

A Bloom filter has no capacity in the sense a hash table does. It never refuses a key, never fails an insertion and never runs out of room. So it has no way to say that it has been given too many keys. This page measures what it does instead, and measures a structure built so that the question never arises.

One filter, filled past its forecast #

The filter is sized for 2,000 keys at a false-positive rate of one per cent, which gives 19,171 bits and seven hash functions — the standard optimum for that rate. It is then filled to four times its design size, and at each stage it is queried with 20,000 keys that were never inserted.

Three things are on this plate, and the first is the one that makes the other two dangerous.

Nothing fails. At four times its design size the filter still inserts every key, still answers every query, and still never denies a key it holds. Its one guarantee — no false negatives — survives any load, because a key’s bits are set when it arrives and nothing ever clears them.

The rate is a factor, not a margin. At twice the design size the rate is 15.6%, not two per cent. At three times it is 42.9%. A filter that was sized for a one-per-cent error and is fifty per cent over its forecast is about six times worse than its design, and a filter at double its forecast is sixteen times worse.

The formula predicts all of it. The measured points lie on the curve $(1 - e^{-kn/m})^k$ at every stage. This is not a filter failing to meet its analysis; it is a filter meeting its analysis exactly, at an $n$ nobody planned for.

The shape comes straight from the formula. The fraction of bits set is $1 - e^{-kn/m}$, and a false positive needs $k$ of them. At the design size that fraction is a half — the optimum is precisely the point where half the bits are set — and $0.5^7$ is about one per cent. At twice the design size the fraction is three quarters, and $0.75^7$ is thirteen per cent. Raising a fraction to the seventh power turns a moderate change in the fraction into a large change in the rate, and the seventh power is a consequence of having asked for a low rate in the first place.

A tighter design degrades faster #

The tighter filter is better at every load in absolute terms — it has more bits — and worse in relative terms. At double its forecast it is forty times its designed rate, against sixteen for the looser one. The reason is the exponent again: a design rate of 0.1% needs ten hash functions, and ten is a higher power to raise a growing fraction to.

That inverts a natural piece of caution. A designer uncertain about the number of keys might ask for a tighter rate, reasoning that a margin in the rate will absorb an error in the forecast. It absorbs some of it — 5.5% at double is better than 15.6% — but the tighter design is more sensitive to the forecast, not less, and the extra bits would have done more good spent on a larger design size at the original rate. Sized for 4,000 keys at one per cent, the filter would need about 38,000 bits and hold one per cent at 4,000; the 0.1% filter spends 28,756 and holds 5.5% there.

Eight times the forecast #

The far end of the curve is where the filter stops being useful and still does not say so. At eight times its forecast it answers yes to 97.8% of absent keys. Every read it was meant to prevent is now performed, plus the cost of consulting the filter first. A system relying on it has quietly become slower than one without it, and the filter’s own behaviour gives no signal.

The signal is available, which is the frustrating part. A filter’s fraction of set bits is a direct estimate of its load, and a filter at more than half set is past its design; a filter at three quarters set is at double. Counting set bits costs one pass over the filter. A filter that is allowed to be wrong measured the rate from the bits and found it agrees with the rate from the load, so the check a filter would need to warn about itself is the same computation that sizes it. Nothing in the standard interface performs it.

Why a hash table does not have this problem #

The contrast with a hash table is instructive, because a hash table is also sized in advance and also degrades as it fills, and nobody treats its forecast as a trap.

A hash table knows its load. It counts its entries, compares the count with its capacity on every insertion, and when the ratio passes a threshold it allocates a larger table and moves every entry into it. Choosing a growth factor measured the trade in that decision, and the probe formula nobody checks measured what the load costs in probes as it rises. Both assume the resize is possible, and it is possible because a hash table keeps its keys: moving an entry to a new table means rehashing a key the table still has.

A Bloom filter keeps no keys. Its bits are the only record that a key was inserted, and a bit set by one key in a filter of $m$ bits says nothing about which bit that key would set in a filter of $2m$. So the filter cannot move its contents into a larger filter; the only resize available is to build a new filter from the original keys, which the filter was usually deployed precisely so as not to keep. It could count its insertions and warn, and nothing prevents that, but it could not act on the warning. That is the gap the stack below fills: it never moves anything, and it grows by adding rather than by copying.

A stack of filters that does not degrade #

The structure that removes the problem gives up the idea that a filter has one size. It starts with a small filter, sized for a few hundred keys at some rate. When that filter has received as many keys as it was sized for, it is frozen and a new, larger filter is started on top of it, sized for more keys at a tighter rate. A query asks every layer and answers yes if any layer does.

Two parameters define the stack: the growth factor $s$, how much larger each layer’s capacity is than the one before, and the tightening ratio $r$, how much each layer’s rate is multiplied by. With a first-layer rate $\varepsilon$, the layers’ rates are $\varepsilon, \varepsilon r, \varepsilon r^2, \dots$, and since an absent key passes the stack if it passes any layer, the stack’s rate is at most their sum:

$$\varepsilon\,(1 + r + r^2 + \cdots) \;\le\; \frac{\varepsilon}{1 - r}.$$

That bound does not depend on how many layers there are. However many keys arrive, the stack’s rate stays below $\varepsilon/(1-r)$, which at $\varepsilon = 1\%$ and $r = \tfrac12$ is two per cent.

The stack’s curve is flat where the single filter’s climbs. It measures 2.0% at 8,000 keys, sitting at its bound rather than under it, because the rates of its first layers add up to nearly the whole geometric series — and the site’s check requires it to stay within a small tolerance of the bound at every size measured.

The price is on the plate as a number, and it needs to be read against the right comparison. Against the filter that was sized for 2,000 keys, the stack uses more than eleven times the bits — but that filter is at 68%, so the comparison is between a working structure and a broken one. The fair comparison is a single filter sized correctly for 8,000 keys at 1% from the start: 76,681 bits. The stack uses 2.9 times that.

Some of that factor is structural and some is timing. The structural part is that later layers are sized for tighter rates, and a tighter rate costs more bits per key: the fifth layer’s rate is a sixteenth of the first’s, and a Bloom filter needs about 1.44 bits a key for every halving of its rate, so each fifth-layer key costs about six bits more than a first-layer key. The timing part is that the stack at 8,000 keys has just started its fifth layer — sized for 8,000 keys on its own — and holds almost nothing in it yet. A stack measured just before a layer boundary looks far cheaper than one measured just after.

That is the same accounting choosing a growth factor found for a dynamic array: capacity allocated ahead of need is space that looks wasted at the instant after a resize and is exactly what makes the next many insertions cheap. What amortised means is the long version of why the instant after a resize is the wrong instant to measure.

There is a structure on this ladder’s neighbour that is a stack of filters by construction, and it is worth noticing because it shows the stack is not an exotic idea. The filter each run carries measured a log-structured store in which every sorted run carries its own Bloom filter, built when the run is written, at exactly the run’s size. The store never has a filter past its design size, because a run’s size is known at the moment its filter is built, and new data goes into new runs with new filters. A lookup consults the filters newest first, exactly as a query here consults layers. What that store does and a scalable filter does not is merge: runs are periodically combined and their filters rebuilt from the merged keys, which the store can do because it keeps the keys. The stack on this page is the same structure for a caller who cannot.

The two dials #

The tightening ratio trades the bound against the bits directly. At $r = 0.9$ each layer’s rate barely falls, so later layers need barely more bits per key and the stack is cheaper; but the geometric series now sums to ten times the first rate, so the guarantee is ten per cent rather than two. The measured rate of 3.6% is well under the bound because only five layers exist yet — a series that converges slowly has most of its sum in terms that have not arrived.

A slowly tightening stack therefore looks good early and gets worse as it grows, approaching a bound that is a poor guarantee. A quickly tightening one is expensive early and holds its guarantee from the start. Which is right depends on whether the stack will stay small, and that is the forecast the stack was built to avoid needing.

Growing faster means fewer layers for the same number of keys, so fewer tightening steps and fewer queries per lookup — three layers to consult rather than five. It costs bits in the other place: each new layer is a larger allocation made before the keys that fill it arrive, so the stack’s overhead just after a layer boundary is larger. On this plate the stack happens to be measured at a point where that cost has been partly earned, and it is the cheapest of the three stacks at 1.7 times the ideal.

Both dials move the same trade. Tighten fast and grow slowly, and the guarantee is strong and the lookups visit many layers. Tighten slowly and grow fast, and lookups are quick and the guarantee is weak. Nothing moves the fact that the stack’s guarantee is paid for in bits beyond what a correct forecast would have cost.

What a guarantee names #

The two structures on this page make different kinds of promise, and the difference is worth stating in this collection’s terms.

The single filter promises a rate at its design size. Beyond that size the formula still describes it perfectly and the promise no longer applies. A guarantee names its model: the model here includes the number of keys, and a user who supplies a different number is outside it without being told.

The stack promises a rate at every size, and its model does not include the number of keys at all — which is exactly why it costs more. A guarantee that holds for inputs the designer did not foresee has to be paid for in resources held against those inputs, and 2.9 times the bits is that payment on this instance.

The choice between them is therefore not a choice between a good structure and a bad one. It is a choice about how good the forecast is. Sized for a rate that does not hold still is the collection’s measurement of what happens when a structure is sized for a rate that later changes, and the answer here is the same: if the forecast is reliable, the single filter is several times cheaper; if it is not, the single filter’s failure is silent and unbounded, and the stack’s cost is the price of hearing about it never.

What the measurement leaves out #

Deletions. Neither structure supports them. The evidence a filter cannot remove measured why a Bloom filter cannot, and a stack of Bloom filters inherits the inability layer by layer.

Query cost. A stack’s lookup consults every layer, and five layers is five filters’ worth of hashing and memory access where a single filter needs one. The plates count bits and rates and not the time a lookup takes, and a stack whose layers do not fit in one cache line pays for the guarantee in latency too.

Rebuilding. A system with the keys still available can simply build a correctly sized filter when the old one passes its design — a single filter at the right size, at a one-off cost proportional to the keys. The stack exists for the case where the keys are not retained, which is the case where a filter is most often used.

Where this ladder goes next: a filter that can be resized #

A Bloom filter cannot be resized because its bits are positions computed modulo its length: a key’s bit in a filter of $m$ bits says nothing about where that key’s bit belongs in a filter of $2m$. That is why the stack keeps old layers rather than growing them, and why it pays to consult every layer on every lookup.

A filter that stores fingerprints in slots — a quotient filter or a cuckoo filter — does not have this problem in the same form. A fingerprint carries some of the bits of the key’s hash, and a table of fingerprints can be doubled by spending one of those bits to decide which half of the larger table each fingerprint moves to. The filter then grows as one structure, with one lookup, at the cost of a fingerprint one bit shorter — which raises its false-positive rate by a factor of two at each doubling. The next rung measures that trade against the stack on this page: same keys, same starting rate, and the rate and bits of each as the keys pass eight times the forecast.