LESSON 23.1
Bloom filters
Answer "have I seen this before?" in a few bits per item, with no false negatives and a tunable false positive rate. How they work, the math to size them, and where real systems use them.
7 min read
Many systems need to ask "is this item in a huge set?" millions of times a second: has the crawler seen this URL, is this username taken, could this key be in this file on disk? Storing every item exactly takes a lot of memory. A Bloom filter answers the question approximately in a fraction of the space, with one useful guarantee: it never says no when the answer is yes.
Insert and query items to compare the filter with an exact reference set.
How it works
A Bloom filter is an array of m bits, all 0, and k hash functions, each mapping an item to a position in the array.
- Insert: hash the item with all k functions and set those k bits to 1.
- Query: hash the item and check its k bits. If any is 0, the item is definitely not in the set. If all are 1, it's probably in the set.
- False positives happen when other items happened to set all k of the query's bits.
- Insert 'cat'bits 2, 7 set
- hashes to 2 and 7
- Insert 'dog'bits 4, 7 set
- hashes to 4 and 7
- Query 'cow'bit 5 is 0 → definitely absent
- hashes to 2 and 5
- Query 'fox'both set → 'probably present', a false positive
- hashes to 4 and 2
In practice you don't need k independent hash functions: compute two hashes h1 and h2 and use h1 + i × h2 for i = 0…k−1.
Sizing one
For n items and a target false positive rate p:
- False positive rate
- p ≈ (1 − e^(−kn/m))^k
- Optimal hash count
- k = (m/n) × ln 2
- Bits per item
- m/n ≈ 1.44 × log2(1/p)
- p = 1%k = 7
- ~9.6 bits per item
- p = 0.1%k = 10
- ~14.4 bits per item
- 1 billion URLs at 1%versus tens of GB to store the URLs
- ~1.2 GB
Each 10× improvement in false positive rate costs about 4.8 more bits per item. The rate also climbs fast if you insert more than the n you sized for, so size for the expected maximum.
Where they're used
Avoiding disk reads
- Skip files that can't contain the key
- Memory per file
Pick it when: LSM-tree stores (Cassandra, RocksDB, HBase) keep one per SSTable.
Deduplication
- Cheap 'seen before?' checks
- A false positive skips something new
Pick it when: Web crawlers skipping known URLs; feeds hiding already-shown posts.
Cache filtering
- Avoid caching one-hit wonders
- Second request still misses
Pick it when: CDNs caching an object only on its second request.
Cheap negative checks
- Answer 'definitely not' without a lookup
- Positives still need the real check
Pick it when: Username availability, malicious URL lists.
The common shape: the filter is a fast pre-check in front of an expensive exact lookup. A "no" saves the lookup; a "maybe" pays for it. False positives cost a little extra work, never a wrong answer.
Variants
- Counting Bloom filters replace each bit with a small counter, so items can be removed, at about 4× the memory.
- Cuckoo filters store small fingerprints in a hash table; they support deletion and use less space than Bloom filters below about 3% false positives.
- Scalable Bloom filters add new, larger filters as items grow, keeping the overall rate bounded.
- Redis offers Bloom and cuckoo filters through its RedisBloom module:
BF.ADD,BF.EXISTS.
Try it
Web Crawler HLD
Deduplicate billions of URLs in a crawler.