Distributed Systems Core · lesson 10 of 11 · about 26 min
How to answer 'have I seen this?', 'how often?' and 'how many different?' in kilobytes instead of gigabytes: Bloom filters and their tuning, why LSM databases use them, Count-Min sketches for popular items, HyperLogLog for distinct counts, and the two ways to break a Bloom filter. Tap any for a plain-language card.
Have I seen this?
The price of a false-positive rate p is about 1.44 × log₂(1/p) bits per item, whatever the key size: 1% costs about 9.6 bits per item, 0.1% about 14.4. A billion URLs at 1% fit in roughly 1.2 GB instead of 50+ GB. Use it when a wrong “yes” is cheap to double-check (one extra disk read) and a wrong “no” is impossible.
Make the keys bigger and the exact set grows while the Bloom filter does not move. Then make the error rate stricter and watch only the Bloom filter grow.
1,000,000,000 keys of 40 bytes need about 56.0 GB as an exact set. A Bloom filter that is wrong 1% of the time on absent keys needs 9.6 bits per key: 1.2 GB, 47 times smaller, and independent of how long the keys are.
Bits per item = −ln p ÷ (ln 2)². The exact-set figure assumes key bytes plus about 16 bytes of per-entry overhead (illustrative; real hash tables vary).
How it works
More bits per key makes false positives rarer. More hash functions help up to a point and then hurt, because each added key sets more bits and the array fills up: the best k is about 0.69 × bits per key, at which the array ends up about half full. The chart is a real filter built with your numbers and tested on 20,000 keys that were never added.
Leave 10 bits per key and move k from 1 to 12: the error is lowest around 7. Then lower the bits per key and watch the error climb.
With 10 bits per key and 7 hash functions, 0.805% of 20,000 keys that were never added were wrongly reported as present (theory predicts 0.819%); 50.33% of the bits are set. That is the best k for this size.
A real Bloom filter using double hashing over a seeded key set. A never gives a false negative, so keys that were added are always found.
Where it earns its keep
The same trick guards caches against requests for keys that do not exist (the cache-penetration problem) and web crawlers against re-fetching URLs. Here is the expected number of file reads per lookup, with and without the filters, for a mix of absent and present keys.
With 8 files and 40% of lookups for absent keys, reads fall from about 5.9 per lookup to about 0.6 (the one unavoidable read of the key that exists), for roughly 10 bits of memory per key.
With 8 files and 40% of lookups for absent keys, a read costs 5.90 file reads on average without filters and 0.64 with them (false-positive rate 0.82%): 89% of the disk reads disappear.
Expected reads: absent key = L × p; present key = 1 + ((L−1)/2) × p, assuming the key sits in a uniformly random file and the filters use the best k. Without filters absent = L, present = (L+1)/2.
Counting without a table
Guarantee: the overcount is at most (e ÷ w) × total events with probability 1 − e−d. It suits heavy-hitter problems (top URLs, trending hashtags, abusive IPs), because the biggest counts stand far above the noise. The sketch below counts a stream of 50,000 events over 5,000 keys with a Zipf-like popularity (a few keys dominate).
Narrow the grid to 50 columns and the small counts drown in noise, but the top few keys stay accurate. Widen it and the error shrinks.
| Key | True count | Sketch says | Over by |
|---|---|---|---|
| #1 | 7,864 | 7,925 | 0.8% |
| #2 | 3,624 | 3,716 | 2.5% |
| #3 | 2,444 | 2,473 | 1.2% |
| #4 | 1,744 | 1,774 | 1.7% |
| #5 | 1,336 | 1,383 | 3.5% |
| #6 | 1,098 | 1,200 | 9.3% |
| #7 | 927 | 984 | 6.1% |
| #8 | 794 | 850 | 7.1% |
A 200 × 4 sketch (3.1 KB) gives the top key 7,925 against a true 7,864. No key was undercounted (0); the average overcount is 61.9 events, within the 680 bound. The small keys are noise-dominated, which is why sketches are used to find the biggest ones.
A real Count-Min sketch over a seeded Zipf stream of 50,000 events and 5,000 keys; counters are 4 bytes each.
Counting distinct things
With 214 = 16,384 registers of 6 bits each (12 KB, which is what Redis uses) the error is about 0.8% for any number of items up to billions. Two sketches can be merged by taking the larger of each register pair, so you can count distinct visitors per hour and combine them into a day without re-reading anything. Here is a real implementation counting up to a million distinct ids.
Keep 100,000 ids and raise the register bits from 4 to 14: the estimate converges. Press “Another stream” to see how far a single run can wander.
1,024 registers (0.8 KB) estimated 98,909 for a true 100,000: -1.09% off, against a typical error of 3.25%. An exact set of the ids would need about 781.3 KB.
Real HyperLogLog with linear counting for small counts, over seeded hashed ids. The estimate for a given setting changes only when you press “Another stream”.
Which structure?
Exact sets are precise and big. Bloom filters answer membership, Count-Min sketches answer frequency, and HyperLogLog answers distinct counts, each in tiny memory with a controlled error. Each answer is worth 20 XP.
Ask: is it membership, frequency, or distinct count? and can a wrong answer be tolerated?
Count how many different users visited each day, to within 1 or 2%, over billions of events.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published systems and papers on probabilistic data structures.
Bloom filters per SSTable
The Bigtable paper describes letting clients ask for Bloom filters on a locality group's SSTables. The filter tells whether an SSTable might contain data for a given row and column pair, which sharply reduces the disk seeks needed for reads of rows that are not there.
PFADD and PFCOUNT
Redis offers HyperLogLog commands that count distinct elements using at most about 12 KB per key, with a documented standard error of 0.81%, whatever the number of elements. Counters can be merged with PFMERGE.
the Count-Min sketch paper
The paper 'An improved data stream summary: the count-min sketch and its applications' introduced the structure and its (ε, δ) guarantee: estimates never undercount and overcount by at most ε times the total with probability 1 − δ. It became the standard tool for frequency estimation in streams.
APPROX_COUNT_DISTINCT with HyperLogLog++
BigQuery's APPROX_COUNT_DISTINCT function uses the HyperLogLog++ algorithm from Google's 2013 paper, trading a small error for far less memory and time than an exact COUNT(DISTINCT) over huge tables.
Interview angle
Six questions, each worth 20 XP. Probabilistic structures show up whenever a design has to remember too much to store exactly.
Say which error is possible (false positive, overcount, +-1%), and why that is acceptable here.
A Bloom filter says a key is not present. What do you know?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
A replaces each bit with a small counter (increment on add, decrement on remove), which makes removal safe at 4 times the memory or more. Otherwise, rebuild the filter periodically from the source of truth, which is what LSM databases do naturally when files are compacted. This filter is sized for 2,000 keys at 10 bits each.
Try 4× the planned keys with a plain filter, then 30% deletions. Switch to a counting filter and the false negatives vanish.
Within its planned load and with no deletions, the filter behaves: false positives stay near the designed 1% and false negatives are impossible.
Real filters with 10 bits per planned key and 7 hash functions; 20,000 absent probes. Removal in the plain filter clears the key's bits; in the counting filter it decrements the counters.
Where to go next