Trade a small, bounded amount of accuracy for an enormous amount of memory. At scale, “roughly right in 12 KB” beats “exactly right in 4 GB” surprisingly often.
Prerequisites: Caching, Latency Numbers Time to read: ~20 minutes
A web crawler has visited 10 billion URLs. Before fetching one, it must ask: “have I seen this before?”
The exact answer requires a set containing all 10 billion URLs.
📐 At ~80 bytes per URL, that’s 800 GB of RAM. Distributed across machines, it means a network call on every single check — for a system doing millions of checks per second. It’s not affordable.
But look at what you actually need. You need to avoid re-crawling. If you occasionally skip a URL you haven’t seen because the structure was slightly wrong, you lose one page out of ten billion. Nobody notices.
A Bloom filter answers the same question in 12 GB — or, with a 1% error rate, in about 12 GB for 10 billion items versus 800 GB exact. For a million items it’s 1.2 MB versus 80 MB.
That trade — bounded error for enormous space savings — is what this whole family of structures is about.
A bit array plus k hash functions.
Adding an item: hash it k times, set those k bits to 1. Checking an item: hash it k times. If any of those bits is 0, the item is definitely not present. If all are 1, it’s probably present.
Bit array (m = 16 bits), k = 3 hash functions
add("apple") → hashes to 2, 7, 11
[0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0]
add("banana") → hashes to 4, 7, 13
[0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0]
↑ position 7 shared — that's fine
check("apple") → 2✓ 7✓ 11✓ → probably present ✅
check("cherry") → 3✗ → definitely absent ✅ (one zero is proof)
check("durian") → 2✓ 4✓ 13✓ → probably present ❌ FALSE POSITIVE
(never added, but its bits happen to be set by others)
🚨 The asymmetry is the whole point:
So a Bloom filter is only useful when a false positive is cheap and a false negative would be expensive. That’s exactly the shape of a cache-miss check: a false positive costs you one unnecessary database query; a false negative would cost you correctness.
m = -(n × ln p) / (ln 2)² bits needed
k = (m / n) × ln 2 optimal number of hash functions
📐 The rule of thumb worth memorizing: about 10 bits per item for a 1% false positive rate.
| Items | 1% FP rate | 0.1% FP rate | Exact set |
|---|---|---|---|
| 1 million | 1.2 MB | 1.8 MB | ~80 MB |
| 100 million | 120 MB | 180 MB | ~8 GB |
| 10 billion | 12 GB | 18 GB | ~800 GB |
Note the shape: the space is proportional to the item count and only logarithmically sensitive to the error rate. Going from 1% to 0.1% costs only 50% more memory. That’s why these are so effective.
❌ You cannot delete. Clearing bits would create false negatives for other items sharing those bits. (Counting Bloom filters use counters instead of bits to allow deletion, at 4× the space.) ❌ You cannot enumerate what’s in it. ❌ You must size it in advance. Exceeding the planned item count degrades the false positive rate badly — at 2× capacity a “1%” filter might be at 10%. (Scalable Bloom filters chain multiple filters to grow.)
This is what makes the concept stick — it’s in systems you already use.
1. Cache penetration defence. Requests for keys that exist nowhere miss the cache and the database. A Bloom filter of all valid keys rejects them before either. → Caching
if not bloom.might_contain(user_id):
return None # definitely doesn't exist — no DB query
return db.get(user_id) # might exist — check for real
2. LSM-tree storage engines. 🚨 The most important real use. Cassandra, RocksDB, LevelDB, and HBase keep a Bloom filter per SSTable. A read must check many SSTables; the filter says “this key is definitely not in this file,” so most files are skipped without any disk I/O. → Storage Engines
3. Web crawlers. The opening example — have I seen this URL?
4. CDN caching decisions. “Has this object been requested before?” — only cache on the second request, so one-hit-wonders don’t evict useful content.
5. Chrome’s malicious URL check (historically). Ship a compact filter of known-bad URLs to every browser; only if it says “probably bad” does the browser make a network call to verify. Privacy plus speed.
6. Databases avoiding pointless joins. A Bloom filter on the join key skips rows that can’t possibly match.
🎙️ “I’d put a Bloom filter in front of the cache. Requests for IDs that don’t exist currently miss the cache and hit the database — the filter rejects those in memory for about 12 MB, and a false positive just means one unnecessary database lookup.”
The problem: how many unique visitors did the site have today? Exact counting means storing every visitor ID — 100 million IDs is ~1.6 GB per day, per dimension you want to count.
HyperLogLog estimates cardinality in ~12 KB, with ~2% error.
🧠 The intuition (which is genuinely elegant): hash each item and look at the number of leading zeros in the hash. In random data, a hash starting with 10 zeros appears roughly once every 2¹⁰ items. So if the maximum leading-zero count you’ve seen is 10, you’ve probably seen about 1,024 distinct items. Averaging this estimate across many independent buckets (harmonic mean) tames the variance.
📐 12 KB for any cardinality, from 100 to 100 billion. The size doesn’t grow with the count.
redis> PFADD visitors:2026-07-22 user1 user2 user3
redis> PFCOUNT visitors:2026-07-22
(integer) 3
redis> PFMERGE visitors:week visitors:2026-07-22 visitors:2026-07-21 ...
🚨 The killer feature is mergeability. You can compute unique visitors per server independently and merge the sketches to get the global unique count — which is impossible with simple counters (you can’t add up per-server unique counts, because visitors overlap). This makes distributed cardinality counting practical.
Use for: unique visitors, unique search terms, distinct IPs, cardinality in analytics dashboards. Don’t use for: anything requiring an exact number — billing, compliance, or “you have exactly 47 followers.”
The problem: which items are trending right now? Which keys are hot? Which IPs are attacking?
Exact counting means a counter per item — unbounded memory when the item space is unbounded (every search query ever typed).
Count-Min Sketch is a 2D array of counters with a hash function per row. To increment, hash the item once per row and increment that cell. To query, take the minimum across rows.
col0 col1 col2 col3
row0 : 12 [5] 3 8 ← hash0("shoes") → col1 → 5
row1 : [7] 2 9 4 ← hash1("shoes") → col0 → 7
row2 : 1 6 [5] 2 ← hash2("shoes") → col2 → 5
estimate("shoes") = min(5, 7, 5) = 5
Collisions only ever inflate a count, so taking the minimum gives the least-contaminated estimate. It never underestimates — the true count is always ≤ the estimate.
Use for: heavy hitters (top-K), trending topics, per-key traffic in a rate limiter, hot key detection. → Hot Keys
🚨 It’s biased toward overestimating, and rare items suffer most (their counts get polluted by frequent items). It’s excellent for finding the top items, poor for accurately counting the tail.
| Structure | Answers | Memory | Note |
|---|---|---|---|
| Bloom filter | Membership | ~10 bits/item | No deletes; no false negatives |
| Counting Bloom | Membership + delete | ~40 bits/item | 4× the space for deletion |
| Cuckoo filter | Membership + delete | Similar to Bloom | Supports deletion, often better FP rate; more complex |
| HyperLogLog | Cardinality | ~12 KB fixed | Mergeable — the key property |
| Count-Min Sketch | Frequency | Fixed grid | Never underestimates |
| t-digest / HDR histogram | Percentiles | KBs | Mergeable percentiles — this is how monitoring computes fleet-wide p99 → Performance Metrics |
| MinHash | Set similarity | Fixed | Near-duplicate detection |
🚨 The t-digest row is worth noting — it’s the answer to “why can’t you average percentiles?” Monitoring systems store mergeable sketches per host precisely so a correct fleet-wide p99 can be computed. If you covered percentiles and wondered how Prometheus actually does it, this is the answer.
Use when all of these hold:
Don’t use when:
That third point is the one to be careful about, and it’s a good interview discriminator: why is a false positive acceptable here, specifically?
| Gain | Cost | |
|---|---|---|
| Bloom filter | 50–100× less memory than an exact set | False positives; no deletion; no enumeration; fixed sizing |
| HyperLogLog | Constant 12 KB for any cardinality; mergeable | ~2% error; can’t list the items |
| Count-Min Sketch | Bounded memory for unbounded key space | Overestimates, worst for rare items |
| Exact structures | Correct | Memory proportional to data; often infeasible at scale |
APPROX_COUNT_DISTINCT. On a billion-row table,
exact distinct counting requires a shuffle and gigabytes of state; the approximation returns in
seconds. The 2% error is irrelevant for a dashboard.PFADD/PFCOUNT/PFMERGE) precisely because unique-visitor
counting is such a universal need — and the PFMERGE operation is what makes per-shard counting
work.1. Build a Bloom filter. Thirty lines, and it makes the concept permanent:
import hashlib, math
class BloomFilter:
def __init__(self, n, p=0.01):
self.m = int(-(n * math.log(p)) / (math.log(2) ** 2))
self.k = max(1, int((self.m / n) * math.log(2)))
self.bits = bytearray((self.m + 7) // 8)
def _positions(self, item):
h = hashlib.sha256(item.encode()).digest()
h1, h2 = int.from_bytes(h[:8], 'big'), int.from_bytes(h[8:16], 'big')
return [(h1 + i * h2) % self.m for i in range(self.k)] # double hashing
def add(self, item):
for pos in self._positions(item):
self.bits[pos // 8] |= 1 << (pos % 8)
def might_contain(self, item):
return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))
bf = BloomFilter(n=100_000, p=0.01)
for i in range(100_000):
bf.add(f"user:{i}")
# Measure the actual false positive rate
fps = sum(bf.might_contain(f"absent:{i}") for i in range(100_000))
print(f"false positive rate: {fps / 100_000:.2%}") # ≈ 1%
print(f"memory: {len(bf.bits) / 1024:.0f} KB vs ~{100_000 * 80 / 1024 / 1024:.0f} MB exact")
2. Watch it degrade. Size the filter for 100,000 items, then insert 500,000. Measure the false positive rate again. It’ll be dramatically worse — that’s why sizing matters.
3. Try HyperLogLog in Redis. Add 10 million items and compare PFCOUNT to the true count and to
MEMORY USAGE of a real set with the same items. The memory ratio is startling.
4. Use it for real. Add a Bloom filter in front of a cache and generate traffic for non-existent keys. Measure database QPS with and without it.