Bloom filters

The problem it solves

You need to answer “is this key here?” before doing something expensive — a disk read, a network call, a database query. Keeping the full set in memory answers it perfectly and costs the size of the set. For a billion keys of 20 bytes each, that is 20 GB, which is not a rounding error.

A Bloom filter answers the same question in about 10 bits per key — 1.25 GB for that billion — with one caveat: it can say “maybe” when the answer is “no”. It can never say “no” when the answer is “yes”. That asymmetry is the entire design, and it is what makes the structure useful rather than merely clever: a false positive costs one wasted lookup, and a false negative — which cannot happen — would cost correctness.

The mechanism

A bit array of m bits, all zero, and k independent hash functions. To insert a key, hash it k ways and set those k bits. To query, hash it k ways and check those k bits: if any is zero the key is definitely absent, and if all are set the key is probably present — probably, because those bits may have been set by other keys.

The false-positive rate follows directly. After inserting n keys, the probability that a given bit is still zero is (1 − 1/m)^(kn) ≈ e^(−kn/m), so the probability that all k bits of a query are set is

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

Minimising over k gives the optimal k = (m/n) × ln 2 ≈ 0.693 × bits per key, and substituting back gives p ≈ 0.6185^(m/n). At 10 bits per key that is about 1%, with the optimal k of 7. The memory required for a target rate is m/n = −log₂(p) / ln 2 ≈ 1.44 × log₂(1/p), which is the form worth remembering: every extra 4.8 bits per key divides the false-positive rate by ten.

What the simulation shows

The bit array above is real: really allocated, really inserted into, really queried, and the false-positive rate on screen is measured rather than computed. The theoretical curve is overlaid, and they agree — which is the point of building it this way, because a formula redrawn as a chart proves nothing.

Run the default — 10 bits per key, 7 hashes — and read the measured rate at about 1%. Then raise it to 15 bits per key and watch the rate fall by roughly an order of magnitude, exactly as the 4.8-bits rule predicts.

Now the counter-intuitive one. Set the hash count to 18 with memory unchanged. More hashes is worse: each insert sets more bits, the array saturates, and the false-positive rate climbs. The fill-level panel shows why — the optimum is exactly where the array is half full, and past it you are just turning bits on. This is the result that separates people who have implemented one from people who have read about one.

Finally, the practical payoff: the load-reaching-the-store panel. With 95% of queries for keys that do not exist, the filter removes nearly all of them before they reach the disk. That is the LSM tree’s read path, and it is why storage engines treat Bloom filters as structural rather than optional.

The numbers worth carrying

• 10 bits per key → ~1% false positives, at k = 7.
• Every +4.8 bits per key → 10× fewer false positives. So ~15 bits for 0.1%, ~20 bits for 0.01%.
• Optimal k = 0.693 × bits per key. Round to the nearest integer; the curve is flat near the optimum, so being one off costs almost nothing.
• The array is at its best when half the bits are set. That is a useful health check on a live filter: much more than half full means it is over-loaded for its size and the rate is worse than designed.

A concrete comparison to carry: one billion 20-byte keys as a hash set is roughly 20 GB plus overhead; as a Bloom filter at 1% it is 1.25 GB; at 0.1%, 1.9 GB.

Where it breaks down

No deletion. Clearing a key’s bits would clear bits shared with other keys and create false negatives, which destroys the guarantee. Counting Bloom filters use small counters instead of bits (4× the space) and support deletion; cuckoo filters do the same with better space efficiency and also support deletion, and are the modern default when you need it.

Sizing is up front. n is baked into the memory decision. Insert twice the planned keys and the false-positive rate rises sharply. Scalable Bloom filters chain progressively larger filters to handle unknown n, at the cost of querying several.

A false positive must be cheap. The whole design assumes the fallback is a check you were going to be able to do anyway. If a false positive triggers something expensive or irreversible, a probabilistic filter is the wrong structure.

Cache behaviour. k independent hashes mean k random memory accesses, which is k cache misses on a large array. Blocked Bloom filters confine a key’s bits to one cache line, trading a slightly worse theoretical rate for a large practical speed-up — and in real systems that trade usually wins.

Only k = 2 hash functions are actually needed. Kirsch and Mitzenmacher showed h_i(x) = h₁(x) + i·h₂(x) is asymptotically as good as k independent functions, which is what every production implementation does.

What people get wrong

“It can return false negatives.” It cannot, and that is the property that makes it safe to put in front of a lookup.

“More hash functions are more accurate.” Only up to the optimum. The simulation makes this one click away.

“You can delete from it.” Not from a standard Bloom filter. Say “counting Bloom filter” or “cuckoo filter” and you have answered the follow-up before it arrives.

“1% false positives means 1% wrong answers.” It means 1% of negative lookups do an unnecessary check and then return the right answer. The filter is never wrong to a caller; it is only occasionally wasteful.

In production

Every LSM-based store — RocksDB, Cassandra, HBase, LevelDB — keeps a Bloom filter per SSTable so a point lookup can skip files. Cassandra exposes bloom_filter_fp_chance per table, and lowering it is a direct memory-for-reads trade you can reason about with the arithmetic above. Postgres has BRIN and bloom index types. CDNs and browsers have used them for safe-browsing lists, and Bitcoin’s SPV clients used them for transaction filtering.

Where a filter would be too coarse, the same family offers alternatives worth naming: HyperLogLog for cardinality, count-min sketch for frequency, cuckoo filters for membership with deletion. They share the same bargain — a bounded, quantifiable error in exchange for an order of magnitude less memory — and knowing which error each one makes is the useful part.

The follow-up questions

“How much memory for a billion keys at 1%?” — 10 bits each, 1.25 GB. Then the formula, so it is clearly derived rather than memorised.

“Derive the false-positive rate.” — (1 − e^(−kn/m))^k, and explain each factor. This is the most commonly asked derivation in the whole probabilistic-structures family.

“What does a false positive cost you?” — One wasted lookup. Say what the fallback is, because the design is only sound if the fallback exists.

“Can you delete?” — No; counting Bloom or cuckoo filter if you must.