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 3: System Design & Interview Mastery
maang.io System Design Series
What is this?
You now know the Bloom filter from the analogy down to the false-positive equation. This chapter is where that knowledge earns the offer. An interviewer doesn't want you to recite "a Bloom filter has no false negatives" — they want to watch you reach for it at the right moment in a design, size it with numbers, and defend the trade-offs when they push. That's the difference between a memorized fact and a senior signal.
We'll do two things: first see where Bloom filters actually show up in real systems (with diagrams), then run a mock interview — for each question: what they're really asking, a model answer, and the senior line that signals you've done this for real. Our bouncer with the stamped paper strip comes along one last time.
The one-line idea: interviewers use the Bloom filter to test whether you can spot a cheap probabilistic pre-filter in front of an expensive exact check — and then reason honestly about the one cost it imposes (false positives) and the one guarantee it gives you (never a false negative).
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