Probabilistic Data Structures
High Level Design·advanced·~35 min read
- bloom-filter
- cuckoo-filter
- hyperloglog
- count-min-sketch
- consistent-hashing
- scale
- patterns
- Bloom Filter - Counting Bloom Filter — Getting Delete Back - Cuckoo Filter — the Modern Alternative - HyperLogLog — Approximate Cardinality - Count-Min Sketch — Approximate Frequency - Where You Get These Off the Shelf - Rolling Your O…
What you'll learn
1. Bloom Filter
Imagine a wall of 400 million light switches, all OFF. To insert Charlie99: - Hash him through 3 predetermined functions. - Formula 1 says "flip switch #14." - Formula 2 says "flip switch #8 002." - Formula 3 says "flip switch #399 112."…
1a. Lookup
To check Alice123: - Run her through the same three hash functions. - If any of the three switches is OFF → definitely no. Alice was never inserted. - If all three are ON → probably yes. Bitwise-AND math, sub-microsecond.
1b. False Positives Are the Whole Trick
Multiple users share switches. Bob happens to flip #5, Dave happens to flip #99 000, Eve happens to flip #201 444. When you check Alice — who was never inserted — all three switches read ON. The filter falsely says "probably yes." The ma…
1c. Why That's Still a Massive Win
You verify only the "probably yes" positives against the DB. If you're checking whether the VIP viewer's 50 K friends follow a celebrity: - Bloom filter kills ~49 980 "definitely no"s in sub-ms. - DB does ~20 confirmation reads (15 real…
1d. Sizing the Filter
Two knobs: m (number of bits) and k (number of hash functions). Given n items and target false-positive rate p: - m = -(n · ln p) / (ln 2)² - k = (m / n) · ln 2 (ln = natural log, base e ≈ 2.718.) Worked example — n = 50 M, p = 0.01: - l…
1e. What Bloom Filters Can't Do
- Delete. Flipping a bit back to 0 would corrupt every other item that hashed to that bit. - Enumerate. The IDs are gone; the filter can only answer membership queries. - Return a false negative. Never happens; a "no" is authoritative. ---
2. Counting Bloom Filter — Getting Delete Back
Replace each bit with a small counter (typically 4 bits, range 0–15). - Insert — increment each of the k slots. - Delete — decrement each of the k slots. - Query — every slot > 0 means "probably yes." Alice and Charlie both hashed to slo…
3. Cuckoo Filter — the Modern Alternative
Bloom's "bits are shared" model is what breaks deletion. Cuckoo filter ditches shared bits entirely.
3a. Physical Layout
The wall becomes a grid of tiny lockers, each big enough for a short fingerprint (typically 8–12 bits). Every ID gets exactly two candidate lockers — computed by two hash functions. Insert Charlie99: 1. Compute his fingerprint: 11010010…
3b. The Cuckoo Kick
What if both of Charlie's lockers are full when he arrives? 1. Randomly evict the current occupant of locker #50 — say, Dave. 2. Put Charlie in #50. 3. Dave now needs his alternate locker. Move him there. 4. If Dave's alternate is also f…
3c. Infinite Loop Protection
Above ~90 % capacity the eviction chain can circle back (A kicks B kicks C kicks A). Three safeguards: 1. Kick limit — hard cap around 500 consecutive evictions. If hit, insertion fails. 2. Stash — a small side-buffer holds the stranded…
3d. Bloom vs Counting Bloom vs Cuckoo Cheat Sheet
| Feature | Bloom Filter | Counting Bloom | Cuckoo Filter | |----------------------|----------------------------|--------------------------------------|-------------------------------------| | Stored per item | k bits set | k 4-bit count…
3e. When to Pick Which (Bloom / Counting Bloom / Cuckoo)
Natural question: if Counting Bloom supports delete, why reach for Cuckoo at all? Short answer: Cuckoo gives you deletion at Bloom-level memory. Counting Bloom gives you deletion at 4× the memory. At any serious scale, Cuckoo wins. Three…
4. HyperLogLog — Approximate Cardinality
4a. The Problem
"How many distinct users hit the site today?" over billions of events. Exact approaches don't scale: - SELECT COUNT(DISTINCT userid) — must sort or hash every ID. Full table scan. - Redis SET of IDs — ~40 bytes per distinct ID. 100 M dis…
4b. The Coin-Flip Intuition
Flip a fair coin repeatedly. The chance of getting at least k heads in a row before any tails is 1 / 2^k. Flip it a bunch of times, and the longest head-run you ever see is tightly correlated with how many flips you did: - Longest run =…
4c. Why One Counter Isn't Enough — Buckets
A single unlucky hash with 25 leading zeros would scream "I've seen 33 million IDs" even if you've only seen three. So you don't keep one max — you keep many, and combine them. Split each hash into two chunks: - First p bits route the ha…
4d. HyperLogLog's Harmonic-Mean Trick
LogLog (2003) combined bucket maxes with the geometric mean — still too noisy. HyperLogLog (2007) swapped in the harmonic mean of 2^(bucket max), which dampens outlier buckets much harder. Variance drops to 1.04 / √m: | m (buckets) | p |…
4e. The Evolution — Why HLL Exists
HLL didn't appear fully-formed; it's the fourth or fifth refinement of a 1983 idea. Each generation chipped at the two numbers that matter: variance and bytes per bucket. | Year | Algorithm | What it added | What was still broken | |----…
4f. Mergeability — The Superpower
An HLL sketch is just a vector of m 5-bit values. To merge two sketches: element-wise max. That merged sketch, fed back through the harmonic-mean estimator, is a correct estimate of unique visitors across both days — no re-scan, no dupli…
4g. In Production
- Redis: PFADD visitors user123 / PFCOUNT visitors / PFMERGE combined visitors1 visitors2. - SQL warehouses: BigQuery APPROXCOUNTDISTINCT, Presto / Trino approxdistinct, Druid cardinality, ClickHouse uniq(). - Streaming: Flink Approximat…
4h. When NOT to Use HLL
- You need the actual IDs, not just the count — HLL discards them. - You need < 0.5 % error consistently — exact-over-partitioned-data wins there. - The set is small (< ~1,000 items). HLL's 12 KB fixed cost is more than a plain hash set…
5. Count-Min Sketch — Approximate Frequency
Question: how many times has this IP hit us in the last minute? (or product-page views, ad impressions, top-K trending terms.) A 2-D array d × w (say 5 × 2 048) of counters, plus d hash functions. - Insert(x): for each row i, hash x to a…
6. Where You Get These Off the Shelf
| Structure | Off-the-shelf | |-------------------|--------------------------------------------------------------------------------------------| | Bloom filter | RedisBloom (BF.ADD, BF.EXISTS), Cassandra (per-SSTable BF baked in), HBase,…
7. Rolling Your Own
You mostly won't need to, but it's a fair whiteboard exercise. Minimum viable Bloom filter: - Storage — a bit array. In-memory: [u64; m/64] in Rust, bitarray in Python, BitSet in Java. Persistent: mmap the array to disk. - Hash functions…
8. Honourable Mentions
Not covered in depth, but worth knowing they exist: - Skip list — probabilistic ordered set, O(log n) average, simpler to implement lock-free than a balanced tree. Used inside Redis sorted sets, LevelDB memtables. - Consistent hashing /…
Choose-Your-Structure Table
| Problem | Reach for | |--------------------------------------------------|----------------------| | "Have I seen this key?" — read-only | Bloom filter | | "Have I seen this key?" — mutable | Cuckoo filter | | "How many distinct X today…