20. Probabilistic Data Structures
1
The picture to keep in your head2
20.1 Why is "approximately right, fast and tiny" a good trade?3
20.2 How does a Bloom filter work?4
20.3 What is a counting Bloom filter?5
20.4 How does HyperLogLog count unique visitors?6
20.5 What is a count-min sketch?7
20.6 How do you find the top K and heavy hitters?8
20.7 How do you choose size vs error rate?9
20.8 Where does each one show up in interviews?10
Memory card and where the analogy breaks11
Practice: five levels12
Interview questions13
Solutions14
Sources15
Code lab20. Probabilistic Data Structures
20.8 Where does each one show up in interviews?
3 min read+10 XP
At the door: Every trick has its moment. "Is this person banned?" is the card. "How many came tonight?" is the coin-flip count. "Who's been here the most?" is the tally board and the list of regulars.
In the system: Spot the question, name the structure, state the trade:
| You hear... | Reach for | Say this |
|---|---|---|
| "Avoid a database or disk lookup for things that don't exist" | Bloom filter | "No false negatives; a 'maybe' goes to the database." |
| "Has this crawler already visited this URL?" | Bloom filter | "Billions of URLs in a few GB; a rare false positive skips a page." |
| "Has this user already seen this item?" | Bloom filter per user | "A rare false positive hides one item. Fine." |
| "Need to remove items too" | Counting Bloom or cuckoo filter | "About 4× the memory of a plain filter." |
| "Daily or monthly active users", "unique visitors", "distinct searches" | HyperLogLog | "12 KB each, ~0.81% error, mergeable across days." |
| "How many times was each hashtag or term used?" | Count-min sketch | "Fixed memory, never undercounts." |
| "Trending", "top 10", "heavy hitters", "noisiest clients" | Top-K (sketch + heap, or Space-Saving) | "Windowed, compared with normal levels." |
| "Exact balance", "inventory", "billing" | None of these | "Needs exact counts in a database." |
Where they appear in this book's designs:
- LSM-tree storage (Chapter 9): a Bloom filter per file to skip disk reads.
- Rate limiting (Chapters 25 and 32): sketches to spot heavy hitters cheaply.
- Search autocomplete (Chapter 34): count-min and top-K for trending queries.
- Leaderboards and trending (Chapter 35): top-K over windows.
- Web crawler (Chapter 36): a Bloom filter for "seen URLs".
- News feed (Chapter 37): a Bloom filter for "already shown" posts; HLL for unique viewers.
Memory code: "In the set? Bloom. How many unique? HyperLogLog. How often? Count-min. Who's top? Top-K."