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 m and k, and counting/scalable variants, with worked numbers.
• Interview — Staff/Principal Q&A: sizing, tuning false-positive rates, and comparisons to other sketches.