Bloom filters explained
A deep dive on Bloom filters: how bits and hash functions give "definitely not" or "probably yes", sizing with the false positive formula, choosing the number of hashes, deletions with counting filters, cuckoo and xor filters, distributed and scalable variants, and where they appear in databases, caches, crawlers and CDNs.
Reading is half of it. See this used in a real interview: walk through Design a Web Crawler →
A Bloom filter answers "have I seen this before?" using a tiny fraction of the memory a set would need, at the cost of occasional false positives. Databases use it to skip disk reads, crawlers to avoid refetching URLs, caches to avoid storing one-hit wonders, and CDNs to avoid useless lookups. It is one of the most frequently mentioned data structures in system design interviews, so it is worth knowing in detail.
How it works
- Start with an array of m bits, all zero, and k independent hash functions.
- Add an item: compute its k hashes, each giving a position in the array, and set those bits to 1.
- Query an item: compute the same k positions. If any bit is 0, the item was definitely never added. If all are 1, it was probably added: those bits might have been set by other items.
No false negatives, a tunable rate of false positives, and memory independent of item size (URLs of 100 bytes cost the same as 8-byte ids).
Sizing
For n expected items and a target false positive rate p:
- Bits needed: m ≈ −n × ln(p) / (ln 2)², which is about 9.6 bits per item for 1 %, 14.4 for 0.1 %, and 19.2 for 0.01 %.
- Best number of hash functions: k ≈ (m / n) × ln 2, about 7 for 1 %.
Examples:
| Items | False positive rate | Memory |
|---|---|---|
| 1 million | 1 % | about 1.2 MB |
| 100 million | 1 % | about 120 MB |
| 1 billion | 0.1 % | about 1.8 GB |
| 10 billion URLs | 1 % | about 12 GB |
Compare with storing 10 billion URLs at about 100 bytes each: about 1 TB. If more items than planned are added, the false positive rate rises quickly, so size for growth or rebuild periodically.
In practice, two hash values combined (h1 + i × h2) simulate k hash functions cheaply, using a fast non-cryptographic hash. See hashing and encoding.
What they cannot do
- Delete: clearing bits could remove other items. Use a counting Bloom filter or a cuckoo filter instead.
- List or count members.
- Avoid false positives: callers must tolerate or double-check a "probably yes".
Variants
| Variant | Adds | Cost |
|---|---|---|
| Counting Bloom filter | deletions, via small counters instead of bits | 3 to 4 times the memory |
| Scalable Bloom filter | growth, by adding new filters as the old fill | slightly higher false positive rate |
| Cuckoo filter | deletions, better locality; stores fingerprints in buckets | similar or less memory at low false positive rates |
| Xor and ribbon filters | smaller static filters | built once from a known set; no inserts afterwards |
| Partitioned or blocked Bloom | cache-friendly lookups (all bits in one cache line) | slightly worse false positive rate |
Where they appear
- LSM-tree databases: each SSTable has a Bloom filter so a read skips files that cannot contain the key, saving disk reads (Cassandra, RocksDB, HBase). See storage engines and Design a Key-Value Store.
- Web crawlers: the "seen URL" check in front of a disk-backed store; a false positive skips a new URL occasionally, which is acceptable. See web crawling at scale and Design a Web Crawler.
- Caches and CDNs: cache an object only on its second request (a Bloom filter remembers the first), keeping one-hit wonders out of the cache. See Design a Distributed Cache.
- Short code generation: quickly check whether a random code is probably taken before hitting the database. See Design a URL Shortener.
- Security and safety: check URLs or passwords against large known-bad lists locally, then confirm positives with a server.
- Distributed joins: send a Bloom filter of one side's keys to filter the other side before shuffling. See MapReduce and Spark.
- Recommendations: avoid showing items a user has already seen.
Distributed use
- Filters are small enough to replicate to every server or ship to clients.
- Two filters with the same size and hashes can be merged by OR-ing bits (union).
- Redis offers Bloom and cuckoo filters as modules; many databases build them internally.
- For time-bounded "seen recently" checks, rotate filters by time window (a new filter per hour, check the last few).
In the interview
"A Bloom filter of about 12 GB for 10 billion URLs at 1 % false positives sits in front of the seen-URL store; a negative means definitely new, a positive is checked against the store or skipped." Give the bits-per-item rule (about 10 bits for 1 %) and say what a false positive costs in your design.
Checklist
- Bit array plus k hashes; no false negatives, tunable false positives.
- About 10 bits per item for 1 %; k ≈ 0.7 × bits per item.
- Size for growth; rebuild or use scalable filters.
- Counting or cuckoo filters when deletions are needed.
- State the cost of a false positive and how it is handled.