Probabilistic data structures

Some questions are cheap to answer approximately and expensive to answer exactly. "Have we crawled this URL before?" across 10 billion URLs needs hundreds of gigabytes as an exact set. "How many unique users visited today?" across 100 million users needs a set of 100 million IDs. "Which hashtags are trending in a stream of a million events per second?" needs a counter for every hashtag ever seen.

Probabilistic data structures answer these questions in kilobytes or megabytes. Each one comes with a mathematically bounded error. You trade a small, known error for a large saving in memory.

The big idea

All of these structures rest on one assumption: a good hash function behaves like a random function. It spreads inputs evenly over its output range, and it looks unrelated to the input. That lets us reason about collisions and bit patterns with probability.

Each structure answers one kind of question, and each has a direction of error. Knowing the question tells you the structure.

Concepts in this section

Read them in this order. Bloom filters come first because the others use the same ideas of hash functions and error.

When approximate is acceptable

Use a probabilistic structure when all three conditions hold.

1. The exact answer is expensive. It needs too much memory, too many disk reads, or a shuffle across machines.
2. The error is bounded, and it points in a safe direction, or it is small compared with the decision.
3. A wrong answer is cheap or recoverable.

Good fits are dashboards, trending lists, cache admission, a filter in front of an exact check, and crawler deduplication. Bad fits are billing ("you were charged for approximately 1,003 API calls"), access control, fraud decisions and audited numbers. For billing, count exactly and aggregate later.

Explaining the error to non-engineers

Translate the math into the units the decision uses, and say which way the error goes.

• "Unique visitors are accurate to about 1%, roughly ±40,000 on 4 million. That is smaller than normal day-to-day change, so week-over-week trends are reliable."
• "The 'already seen' check is never wrong when it says no. When it says yes, it is wrong about 1 time in 100, so we skip about 1% of new URLs."
• "Trending counts can be overstated, but never understated. Anything over 5,000 an hour is reliably in the list."

Quote a 95% range to non-engineers. A standard error is one standard deviation, so about 95% of estimates fall within twice that.

Common mistakes

• Using approximate counts for money. Count exactly where the number has to add up.
• Forgetting the error direction. Bloom filters can say yes wrongly. Count-min overcounts. Know which way to lean.
• Sizing for the average load. Bloom filters need their size chosen for the largest n you expect.
• Trusting an estimate for a small slice. Errors are relative to the whole stream, so small groups are noisy.

Key takeaways

• Each structure answers one question with a known error. Match the question to the structure first.
• A good hash function is the foundation. Collisions and bit patterns are reasoned about as probabilities.
• Use approximation when the exact answer is expensive, the error is bounded, and a wrong answer is cheap.
• Explain the error in the decision's units, and state which direction it goes.

Further learning

Spanning Tree's short animated explainer is a clear visual introduction to Bloom filter bits and hash functions.

Breaking Taps builds the HyperLogLog intuition from coin flips and leading zeros, at an accessible pace.

Hello Interview covers Bloom filters, count-min sketch and HyperLogLog together, framed around system design interviews.