Bloom Filters

Back in LSM Trees & SSTables, we waved a small magic wand. Every SSTable on disk, we said, "carries a Bloom filter" — a little structure that lives in RAM and answers one question, is this key definitely NOT in this file?, so a read can skip files it can't possibly find the key in. We used it as a black box and moved on. Time to open the box, because it's one of the most beautiful ideas in all of systems, and it opens the second half of this section.

Here's the question it answers, stated plainly: you have a huge set — every key in an SSTable, every known-malicious URL, every object already in a cache — and you want to test "is X in this set?" using almost no memory. Not the ~800 bits per element it takes to actually store a nine-character string in a hash set; something like ten bits per element, total, no matter how long the keys are. That sounds impossible. Storing a set usually means storing its members.

The trick is to stop trying to store the members at all. A Bloom filter keeps no keys — you cannot ask it to list what's inside, and you cannot pull a value back out. It answers exactly one kind of question, membership, and it buys its tiny size by allowing itself to be wrong — but only ever in one safe direction. That single, carefully-chosen compromise is the whole invention (Burton Bloom, 1970), and once you see how the one-sidedness works, the rest of the sketches — the second escape route that When Ordinary Indexes Fail promised, the one that trades exactness for space — all follow the same bargain: give up a little accuracy, gain an enormous amount of space.

Start with a row of m bits, all set to 0 — that's the entire data structure. Then pick k independent hash functions, each of which maps any key to a position somewhere in that row (0 to m−1). Two operations, and only two:

• Add x: run x through all k hash functions to get k positions, and set those k bits to 1. (Already 1? Leave it — bits only ever go up.)
• Test x: run x through the same k hash functions to get the same k positions, and look at those k bits. If any of them is 0, x was definitely never added — because adding x would have set that bit. If all k are 1, x is probably in the set.

That's it. Adding "apple" might light bits 4, 13, and 21. Testing "apple" later checks 4, 13, 21 — all 1 — so, maybe. Testing "zebra" checks its three positions and finds one of them still 0 — so, definitely not. The filter never stored the letters a-p-p-l-e; it stored a fingerprint smeared across k bits, and a fingerprint is enough to rule things out.

Notice what's doing the work. A single bit doesn't belong to any one key — bit 22 might be set by "apple," and later also by "mango," and later also by "cherry." The bit has no idea who set it. That sharing is exactly why the structure is so small (elements pile onto the same bits instead of each needing its own slot) and, as we're about to see, exactly why it can be fooled.

Everything that makes a Bloom filter useful comes from a single asymmetry, so it's worth being precise about it.

There are no false negatives. Ever. If you added x, then all k of x's bits were set to 1 at that moment — and bits are never cleared. So when you test x later, its k bits are still 1, and the filter says "maybe." A real member can never slip through as a "no." This isn't a probability; it's a structural guarantee, true for every filter at every fill level. A "definitely not" is always the truth.

But there are false positives. Test a word you never added, and its k bits might all happen to be 1 — not because you added it, but because other elements set those bits. Add "cat," "dog," and "fish" to a small filter and they light up, say, eight bits between them. Now test "owl," which you never added: if owl's three hash positions all landed on bits that cat, dog, and fish already turned on, the filter says maybe for a word it has never seen. The bits collided. The filter can't tell "set by owl" from "set by someone else" — a bit is just a 1.

So the two verdicts mean genuinely different things: "no" is a fact; "maybe" is a hint. And that asymmetry is precisely what makes the whole thing safe in practice. A Bloom filter is never used as the source of truth — it's placed in front of one, as a cheap accelerator. When it says "definitely not," you skip the expensive lookup entirely, and you're never wrong to. When it says "maybe," you go do the expensive lookup and confirm. A false positive costs you one wasted lookup that finds nothing — annoying, bounded, harmless. A false negative would cost you correctness — and those never happen. You get to trade a little wasted work for an enormous amount of saved memory, and the trade is always in your favor.

How wrong is "maybe"? That's a knob you set, and the math behind it is one of the most satisfying in the field. With m bits, n elements added, and k hash functions, the false-positive rate is very close to:

FPR ≈ ( 1 − e^(−kn/m) )^k

There are two dials. The obvious one is m — more bits, fewer collisions, lower error. The subtle one is k, the number of hashes, and it cuts both ways: too few hashes under-uses the bits you've paid for, but too many hashes set so many bits per element that the array fills up and everything starts colliding. There's a sweet spot — the optimal k ≈ 0.69 · (m/n) — and at that setting the array ends up almost exactly half full, which is the tell-tale sign a Bloom filter is tuned right. For a filter sized at about 9.6 bits per element, that's 7 hash functions; a real run sweeping k confirmed it — the false-positive rate bottomed out at k=7 (about 1.0%) and got worse on either side (10% at k=1, 1.75% at k=12).

Now the beautiful part. Plug in the optimal k and ask how many bits per element you need for a target error rate. The answer is a straight line: every additional ~4.8 bits per element divides the false-positive rate by ten. About 9.6 bits per element (≈ 1.2 bytes) buys 1%; 14.4 bits buys 0.1%; 19.2 bits buys 0.01%. And — this is the astonishing part — that ratio doesn't depend on n at all. One percent membership testing costs ~1.2 bytes per element whether your set has a thousand keys or a billion. The filter grows linearly with the set, but the accuracy per bit is a universal constant. Compare that to actually storing the keys: in a real measurement, a 1%-error Bloom filter over ten thousand nine-character strings used 9.59 bits per element, while a genuine hash set of the same strings used 819 bits per element — the set was 85× larger, and it could enumerate its members while the filter cannot. That's the deal: give up enumeration and a 1% error, shrink by nearly two orders of magnitude.

The lab below makes both dials real. Add words and watch bits light up; test words and read the verdict; then manufacture a false positive with your own hands by testing words you never added until one collides. Push m and k around and watch the measured error track the formula — then overfill the array and watch the false-positive rate march toward 100%.

There's a catch hiding in "bits are never cleared," and it's the honest limitation of a plain Bloom filter: you cannot remove an element.

Say you want to delete "cat." The obvious move is to clear cat's k bits back to 0. But remember that bits are shared — one of cat's bits is very likely also one of "lion's" bits. Clear it, and now when you test "lion," one of its bits is 0, and the filter confidently reports definitely not for a word that's genuinely in the set. You've just created a false negative — the one kind of error the whole design promised would never happen. A plain Bloom filter has no record of which element set a bit, so it can never safely turn one off. It is add-only.

The standard fix is the counting Bloom filter: replace each single bit with a small counter (4 bits is the usual choice — it holds values 0 to 15, which is plenty in practice). Adding an element increments its k counters; deleting decrements them; a slot is "set" whenever its counter is above zero. Now deleting "cat" just decrements its counters, and "lion's" shared slot stays above zero because lion still contributes to it. Deletes work — but you've paid for them: a 4-bit counter is 4× the space of a single bit, so your 9.6-bits-per-element filter becomes ~38 bits per element. That's the recurring theme of this section showing up again — you don't remove a limitation, you pay to move it. (If deletes and tight space both matter, the very next lesson's Cuckoo filter does better than paying 4×; that's its whole reason to exist.)

Bloom filters are not a curiosity — they are quietly holding up systems you use every day, and they always show up in the same shape: a small, fast Bloom filter sitting in front of a big, slow source of truth, cheaply eliminating the "definitely not there" cases so the expensive path only runs when it might actually succeed.

• LSM stores (the payoff of our black box): Google's Bigtable paper (2006, §7) put a Bloom filter on every SSTable so a read for an absent row could skip the disk seek — and every LSM engine since does the same. Cassandra ships one per SSTable, persisted as the on-disk Filter component, with a tunable bloom_filter_fp_chance that defaults to 0.01 (1%). RocksDB defaults to 10 bits per key — almost exactly our 1% design point — and its newer Ribbon filter trades a little CPU for ~30% less space at the same error. In a measured run, reads for absent keys across eight SSTables would have taken 160,000 disk reads without filters; with them, 1,636 — the Bloom filters eliminated 98.98% of the disk reads on the miss path. That's the magic wand from LSM Trees & SSTables, finally un-waved.
• Chrome Safe Browsing: the browser needs to know if a URL you're about to visit is on a list of millions of known-malicious sites — without phoning Google on every click. The classic solution was a Bloom filter: around one million bad URLs packed into an 18 MB filter shipped to your machine. Chrome checks each URL locally; a "definitely not" (the overwhelming common case) is free and private, and only a "maybe" triggers a confirming lookup to the server. A false positive costs one round-trip; a false negative would let malware through — and the one-sided guarantee makes sure that never happens. (Modern Chrome has since moved to hash-prefix sets and real-time checks, but the Bloom era is the textbook example for a reason.)
• CDN cache admission: most objects a CDN sees are requested exactly once ("one-hit wonders"). Caching them is pure waste — they evict genuinely hot objects. So CDNs keep a Bloom filter of URLs seen before and refuse to cache an object until its second request. A cheap membership test protects the whole cache.

The same idea also ships inside databases — PostgreSQL has a bloom extension for multi-column signature indexes — and in dedup pipelines, spell-checkers (Bloom's own 1970 example), and more. Once you see the pattern — a cheap gate in front of an expensive truth — you start noticing it everywhere.

A Bloom filter is a sharp, specialized tool, and the whole art of using one well is knowing its edges.

Reach for a Bloom filter when the set is large, memory is tight, and a false positive is cheap because something backstops it — there's a real source of truth behind the gate to catch the rare "maybe" that's actually a "no." That's the SSTable, the Safe Browsing server, the cache. It's the perfect front door.

Don't reach for one when any of its costs bite: if the set is small, just use a real hash set — it's exact, supports deletes and enumeration, and the 85× space win only matters at scale (a Bloom filter guarding a ten-thousand-row table is a party trick, not engineering). If you need to list the members, delete freely, or get an exact yes/no with nothing behind it to double-check, a Bloom filter is the wrong shape. And there's a subtle one: because a Bloom filter reveals what you're asking about, using one to gate access to private data can leak information — Bitcoin's early SPV wallets (BIP37) learned this the hard way and deprecated it for privacy.

That framing — what question am I willing to answer approximately, to fit the structure in RAM? — is the thread through the rest of §8. Bloom answers "is it in the set?" The next lessons answer the rest of the family: "is it in the set, and can I delete it?" → a Cuckoo filter (next). "how many distinct things have I seen?" → HyperLogLog. "how often does each thing occur?" → a Count-Min sketch. "how similar are these two sets?" → MinHash. Every one of them makes the same trade you just learned — a bounded, one-directional wrongness in exchange for a structure hundreds of times smaller than the exact answer. You now know the first, and the deepest, of the sketches.