Probabilistic Data Structures

Bloom filters, HyperLogLog, Count-Min Sketch, heavy hitters and MinHash.

Some questions don't need exact answers: "have we probably seen this URL before?", "roughly how many unique visitors today?", "which items are approximately the most popular?" Probabilistic data structures answer them using a tiny, fixed amount of memory, in exchange for a small, controlled error. Naming the right one is a classic way to solve a scaling deep dive in a sentence.

At a glance

Bloom filter

A bit array plus several hash functions. To add an item, set the bits at each hash position. To check, see whether all those bits are set.
If any bit is 0, the item is definitely not in the set. If all are 1, it's probably in the set.
You can't delete items from a standard Bloom filter (a counting Bloom filter or cuckoo filter allows it), and the false-positive rate rises as it fills, so size it for the expected item count.

Typical uses:

Avoid expensive lookups — LSM-tree databases (Cassandra, RocksDB, Bigtable) keep a Bloom filter per file so reads skip files that can't contain the key. See Database Indexing.
Crawlers — "have we already crawled this URL?" across billions of URLs. See Design a Web Crawler.
Username availability — reject taken names without hitting the database; confirm "available" with a real check.
Content filters — "has this user already seen this post?" for feed deduplication.

HyperLogLog

Hash each item and track the longest run of leading zeros seen in each of many buckets; long runs are rare, so they reveal how many distinct items have been seen.
Counts billions of distinct values with about 12 KB and ~0.8% error. Mergeable: union the sketches for each hour to get the day's count.
Built into Redis (PFADD, PFCOUNT, PFMERGE), BigQuery (APPROX_COUNT_DISTINCT) and most analytics databases.
Use for unique visitors, unique viewers per video, distinct search queries.

Count-Min Sketch

A small 2-D array of counters with one hash function per row. To count an item, increment one counter per row; to estimate, take the minimum across rows.
Collisions only add, so estimates are never too low.
Pair it with a small min-heap to track heavy hitters: the top-K most frequent items in a stream. See Design Top-K (Trending).

MinHash and locality-sensitive hashing

MinHash produces a short signature per set; the fraction of matching signature values estimates the Jaccard similarity of two sets.
LSH buckets similar signatures together, so near-duplicates can be found without comparing every pair.
Used for near-duplicate web pages, plagiarism detection and similar-item recommendations.

[!TIP] Say what error is acceptable These structures are the right answer when an approximate result is acceptable to the product. Say so explicitly: "A 1% error on the unique viewer count shown on the dashboard is fine; billing uses the exact count from the batch job."

[!INTERVIEW] Trending hashtags "Each stream processor keeps a Count-Min Sketch plus a min-heap of the top 100 hashtags per one-minute window — a few megabytes no matter how many distinct hashtags appear. Windows are merged every minute to produce the global top-K, and HyperLogLog tracks unique users per hashtag so a single spammer can't make one trend."