Bloom filters
A Socratic walk-through of Bloom filters — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why is a lookup structure that sometimes says yes when it means no more useful than one that is always right?
Here is a structure that answers "is this item in the set?" and is sometimes wrong — though not in a random direction. It never fails to recognise a member, but occasionally claims membership for something never inserted. That sounds like a defect to be replaced with something simply correct.
Yet this thing sits in front of databases, caches, browsers and distributed storage. So the question is not how to remove the error but what it buys — and why one direction of error should be so much cheaper than the other.
Reasoning it through
REASONING #Start with the cost of being exactly right. To distinguish an arbitrary set of n items from every other such set drawn from a universe of size U takes about n times the logarithm of U over n bits. In practice exactness means keeping the members, or hashes long enough that no two collide — sixty-four bits apiece is the usual minimum. The cost scales with the identity of the members: longer keys, bigger universe, more bits.
Now relax in one direction only. Demand that every genuine member is reported present, but permit some fraction p of non-members to be reported present too. How many bits does that need?
Count what the structure must express. It carves the universe into a "yes" region and a "no" region, placing all n members in "yes" and about a p fraction of everything else there too. Working out how many such carvings must be distinguishable gives a floor of roughly log base two of one over p bits per element — and notice what has vanished: the size of the universe. Approximate membership costs bits proportional to how certain you want to be, and nothing for how long or various the keys are. At one percent that floor is about 6.6 bits per element, against sixty-four for a hash — an information-theoretic fact, not a property of any design.
Bloom's construction from 1970 reaches near that floor with almost nothing in it. Take m bits, all zero, and k hash functions. To insert, set the k bits the item hashes to; to query, check whether all k are set. A member's bits were set on insertion and bits are never cleared, so a member always answers yes — the one-sidedness is structural, not statistical. A non-member answers yes only when all k of its bits happen to have been set by other items.
That last sentence is the whole analysis. After n insertions each bit has had roughly kn chances to be set, so the chance it is still zero is about e to the minus kn over m, and the false positive rate is one minus that quantity, raised to the k. Minimising over k gives k equal to m over n times the natural log of two — the setting where the array is half full, the point of maximum information per bit. Substituting back gives a rate of two to the minus k, so the bits per element needed for rate p is about 1.44 times log base two of one over p: 9.6 bits for one percent, 14.4 for a tenth of a percent. That is a factor of 1 over ln 2 above the floor derived a moment ago — close enough to be worth the simplicity, far enough that later designs improved on it.
But compactness alone would not justify a wrong answer. The real reason is what a "yes" is used for. A Bloom filter is not an oracle; it is a gate in front of something authoritative and expensive — a disk read, a network round trip, a query. A "no" is final and free. A "yes" means go and look. So a false positive costs one wasted lookup and never a wrong result: the error is confined to the budget rather than the correctness.
That gives us the test. The value is claimed to come from one-sidedness plus a backing store, not from compactness — so where "yes" is acted on directly, with nothing behind it to correct the mistake, the filter should be worse than useless. It is, and that is a design error people do make. The second prediction is that the rate depends only on bits per element and hash count, not on the keys. The refuting observation would be a workload where the measured rate climbs with key length or structure at fixed bits per element — which would mean the hash functions are not behaving as independent uniform maps, invalidating every line of the derivation, all of which assumes they do.
The analogy
THE ANALOGY #Think of a dog trained to alert on a scent at a baggage belt. Every bag carrying the substance is alerted on — that is what the training guarantees — and some bags that merely smell similar are alerted on too. Every alert is followed by a human opening the bag. The dog is worth having because opening bags is slow, the dog is fast, and its mistakes are always in the direction that gets checked.
the dog's errors depend on what is in the bags and could be reduced by better training, whereas a filter's rate is fixed by arithmetic — bits per element and hash count, nothing else — and no care improves it once the size is chosen; worse, the dog does not degrade as more bags pass, while a filter's rate climbs steadily as it fills.
Clarifying the model
THE MODEL #Three refinements.
First, this is not the base-rate reasoning that governs a medical screening test, though the words overlap. There, errors run both ways and the question is what a positive should make you believe. Here the "positive" is not a belief at all but an instruction to go and check, and the belief comes from the check — an error correctable downstream is a different kind of object from one that is not.
Second, the structure cannot support deletion: clearing an item's bits might clear bits another item depends on, creating a false negative and destroying the one guarantee the whole thing rests on.
Third, and honestly: Bloom's is no longer the best construction. Cuckoo and quotient filters get closer to the floor, support deletion, and have better lookup locality. Bloom filters remain everywhere because they are trivial to implement, easy to reason about, and already embedded in a great deal of installed software — persistence by inertia and simplicity, not superiority.
A picture of it
THE PICTURE #How to readStart at the parallelogram with the key you are asking about and follow it through hashing into the bit array. The first diamond is the only test the filter itself performs, and its left branch is the valuable one: a single zero bit proves the item was never inserted, so the path ends there with certainty and no lookup. The right branch reaches the expensive store and splits again, the lower end state being the false positive, which cost a lookup and nothing else. Note that no path leads to a false negative — there is no such exit from this chart.
What became clearer
WHAT CLEARED #Exactness is expensive because it must encode which items are present. Bounded one-sided error is cheap because it need only encode how confident to be, at a cost per element that ignores the universe entirely. And the error is affordable not because it is small but because of its direction: a "no" is trusted, a "yes" is checked, so mistakes are spent in wasted work rather than wrong answers.
Where to go next
ONWARD #- Cuckoo and quotient filters, which approach the floor and permit deletion.
- How a filter is sized when the element count is not known in advance.
Key terms
TERMS #| Term | What it means |
|---|---|
| False positive rate | the fraction of non-members reported present; here set entirely by bits per element and hash count. |
| One-sided error | an error that can occur in only one direction, so one of the two answers is a guarantee. |
| Load factor | the fraction of the bit array set; the analysis' optimum is one half. |
Every term the collection defines is gathered in the glossary.