Bloom Filters

The One-Line Definition

A space-efficient probabilistic set answering one question: "is this element possibly in the set, or definitely not?" It can say "definitely not" or "probably yes" — never a false negative, sometimes a false positive. You reach for it whenever an exact set would be too big for memory and a small false-positive rate is acceptable.

This is the structure behind [[Web Crawler]]'s "have I seen this URL?", [[Storage Engines & Indexing]]'s per-SSTable "could this key be here?", and cache/dedup layers everywhere.

How It Works

• A bit array of m bits, all 0, plus k independent hash functions.
• Add(x): hash x with all k functions → k positions → set those bits to 1.
• Query(x): hash x the same way → if any of the k bits is 0 → definitely not in set. If all k are 1 → probably in set (they could all have been set by other elements — that's the false positive).

m = 16-bit array, k = 3 hashes
add("cat")  → bits {2, 7, 11} = 1
add("dog")  → bits {4, 7, 14} = 1     (7 already set — collisions are the point)
query("cat")→ 2,7,11 all 1 → "probably yes"  ✓
query("fox")→ hashes to {2, 5, 14}; bit 5 is 0 → "definitely NOT"  ✓ certain

Why no false negatives: bits are only ever set, never cleared. If you added x, its k bits are 1 forever, so a query for x can never see a 0. That asymmetry is the whole value.

The Tradeoff Knobs

False-positive rate depends on: array size m, number of hashes k, and elements inserted n.

• Bigger m (more memory) → fewer collisions → lower false-positive rate.
• Optimal k ≈ (m/n) · ln2.
• Rule of thumb worth remembering: ~10 bits per element → ~1% false-positive rate. So 1 billion URLs ≈ 10 Gbit ≈ ~1.25 GB for a 1% FPR — versus storing a billion full URLs (100s of GB). That ~100× compression is the pitch.

What You Give Up

• False positives: occasionally says "probably yes" for an absent element. Design so a false positive is cheap — e.g., in an LSM read it means one wasted disk seek, not a wrong answer; in a crawler it means one URL occasionally skipped.
• No deletion in the basic version (clearing bits would break other elements' membership). Fix: a Counting Bloom Filter — each slot is a small counter instead of a bit, incremented on add and decremented on delete, at the cost of more space.
• No enumeration / no counts: it can't list its members or say how many; it only answers membership.

Where It Shows Up (say a concrete one)

Interview Drills

1. Design "have I crawled this URL?" for 10B URLs with limited RAM. — A Bloom filter: ~10 bits/element → ~12 GB for 10B URLs at ~1% FPR, versus 100s of GB to store the URLs themselves. False positive = occasionally skip a page we hadn't actually crawled — acceptable for a crawler; false negatives (re-crawling) can't happen, which is what we care about.
2. A Bloom filter says "yes" — is the element in the set? — Not necessarily; it means "probably." All k bits being 1 can result from other elements' insertions (false positive). Only a "no" is certain. If you need certainty on a "yes," follow up with an authoritative lookup — the filter's job is to cheaply eliminate the "definitely not" majority first.
3. You need deletions from a Bloom filter. What changes? — Switch to a Counting Bloom Filter (per-slot counters, decrement on delete) — plain bit-clearing would corrupt membership for other elements that share a bit. Costs several bits per slot instead of one.
4. How does a Bloom filter reduce read amplification in an LSM tree? — Each SSTable carries a Bloom filter over its keys; on a read, the engine checks the filter first and skips any SSTable that "definitely" lacks the key, avoiding a wasted disk seek. Turns "check every level" into "check only levels that might have it."

Cross-links

[[Storage Engines & Indexing]] · [[Web Crawler]] · [[Caching & Redis]] · [[Back-of-Envelope Estimation]] · [[Merkle Trees]]