Bloom Filter
maang.io System Design Series
A bloom filter is a tiny bit array plus a handful of hash functions that answers one question fast: is this item possibly in the set? It can say "definitely not" (skip the expensive lookup entirely) or "maybe" (go check) — it never gives a false negative. That one-sided error is exactly why it guards the read path in Cassandra, RocksDB, CDNs, and safe-browsing lists.
This deep dive comes in three parts:
- Foundations & Core Concepts — bits, k hash functions, the one-sided error, and where it pays off.
- Internals — the false-positive formula, choosing
mandk, and counting/scalable variants, with worked numbers. - Interview — Staff/Principal Q&A: sizing, tuning false-positive rates, and comparisons to other sketches.
Bloom Filter — Part 2: Internals & The Math of Error
maang.io System Design Series
What is this?
Back to our bouncer with the stamped paper strip. In Part 1 we watched the strip work: stamp a few boxes per banned guest, peek at the same boxes to decide "definitely never banned" versus "probably banned." Now we open the hood and answer the questions a Staff engineer actually gets grilled on: exactly how the stamping works, precisely how likely a false alarm is (and how to control it), and how to fix plain Bloom's two big limitations — you can't delete, and you must guess the size up front.
The one-line idea: the false-positive rate is not luck — it's an equation you dial in with three numbers: how many bits you allocate (
m), how many hash functions you use (k), and how many items you insert (n). Master that equation and the tuning knobs, and the Bloom filter stops being magic and becomes an engineering budget.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson