System Design HLD-15.04
Probabilistic data structures
Answering approximately in tiny memory: Bloom filters and false positives, Count-Min Sketch for heavy hitters, and HyperLogLog for counting distinct items.
The big idea
A web crawler has visited 5 billion URLs and needs to know, for each new link, "have I seen this before?". Storing every URL exactly takes hundreds of gigabytes. An analytics system wants "how many unique visitors today?" across a billion events; keeping a set of every visitor id is expensive and has to be repeated per page, per country, per hour. Exact answers cost memory proportional to the data. Often you do not need exact answers.
Probabilistic data structuresData structures that answer questions such as membership, frequency or distinct count approximately, with bounded error, using far less memory than an exact answer requires. trade a small, known error for enormous memory savings. A Bloom filter answers "definitely not seen" or "probably seen" in about 10 bits per item. A Count-Min Sketch estimates how often each item appeared using a small fixed grid of counters. HyperLogLog estimates the number of distinct items in a few kilobytes, whether there are a thousand or a billion.
Think of a nightclub bouncer who cannot remember every face, but keeps a few tally marks in a notebook using a clever scheme. If the marks say "never seen", that is certain. If they say "seen", there is a small chance of a mix-up, which is fine for deciding who gets a second look.
How it works
Step 1: Bloom filters
A Bloom filterA bit array plus k hash functions that answers whether an item is definitely not in a set or probably in it; it can give false positives but never false negatives. is an array of m bits, all 0, and k hash functions. To insert an item, hash it k times and set those k bits to 1. To check an item, look at its k bits: if any is 0, the item was definitely never inserted; if all are 1, it probably was, but those bits might have been set by other items, a false positiveAn answer of 'yes, present' for an item that was never actually inserted.. There are never false negatives.
The false positive rate depends on bits per item and the number of hashes:
With 10 bits per item and the best k of 7, p is about 0.8 percent. For a billion URLs, that is about 1.2 GB instead of hundreds. Plain Bloom filters cannot delete items (clearing a bit could erase other items); counting Bloom filters and cuckoo filters can.
Try it
Try this:
- With 128 bits, 3 hashes and 15 items, check the new emails: at least one bit is 0, so the answer is a certain "no".
- Raise items to 60. The array fills with 1s and the measured false positive rate climbs; a new email may now come back "probably in the set".
- Keep 60 items and vary k from 1 to 8. The rate first falls then rises again: too many hashes fill the array faster. Compare the best k with the formula in the output.
Step 2: Where Bloom filters save work
The pattern is always the same: a cheap in-memory check avoids an expensive lookup for items that are definitely absent.
- LSM-tree storage engines keep a Bloom filter per file, so a read for a missing key skips files that cannot contain it ( Storage engines: B-tree vs LSM-tree ).
- Caches avoid caching one-hit-wonders by remembering what has been requested once before.
- Crawlers skip URLs they have already fetched; an occasional false positive just means one page is not re-crawled.
Step 3: Count-Min Sketch and HyperLogLog
import hashlib, math, random
def h(x, seed): # 64-bit hash with a seed
return int.from_bytes(hashlib.blake2b(f"{seed}:{x}".encode(), digest_size=8).digest(), "big")
# Count-Min Sketch: 4 rows x 256 counters; estimate = min over rows (never under-counts).
W, D = 256, 4
cms = [[0] * W for _ in range(D)]
rnd = random.Random(1)
stream = ["/home"] * 5000 + ["/cart"] * 1200 + [f"/item/{rnd.randrange(20000)}" for _ in range(30000)]
for page in stream:
for r in range(D):
cms[r][h(page, r) % W] += 1
est = lambda page: min(cms[r][h(page, r) % W] for r in range(D))
print(f"Count-Min: /home true 5000 est {est('/home')}, /cart true 1200 est {est('/cart')} ({W * D} counters)")
# HyperLogLog: 1024 registers keep the longest run of leading zeros seen per bucket.
P = 10; M = 1 << P
reg = [0] * M
visitors = [f"user{rnd.randrange(10**9)}" for _ in range(100_000)]
for v in visitors:
x = h(v, 99)
bucket, rest = x >> (64 - P), x & ((1 << (64 - P)) - 1)
reg[bucket] = max(reg[bucket], (64 - P) - rest.bit_length() + 1)
alpha = 0.7213 / (1 + 1.079 / M)
estimate = alpha * M * M / sum(2.0 ** -r for r in reg)
print(f"HyperLogLog: true distinct {len(set(visitors)):,}, estimate {estimate:,.0f} using {M} small registers")
print(f"typical error 1.04/sqrt({M}) = {1.04 / math.sqrt(M):.1%}")Output
Count-Min: /home true 5000 est 5072, /cart true 1200 est 1309 (1024 counters)
HyperLogLog: true distinct 99,992, estimate 99,780 using 1024 small registers
typical error 1.04/sqrt(1024) = 3.2% A Count-Min SketchA small grid of counters with one hash function per row that estimates how often each item appeared in a stream; it can over-count but never under-count. has d rows of w counters. Each item increments one counter per row; its estimated count is the minimum across rows, since collisions only add. With 1,024 counters it estimated /home at 5,072 against a true 5,000 in a stream of 36,000 events. It is used to find heavy hitters: the most requested URLs, the noisiest clients for rate limiting, trending hashtags.
HyperLogLogAn algorithm that estimates the number of distinct items in a set using a small array of registers that record the longest run of leading zeros in hashed values. estimates distinct counts. Hash each item; in a random-looking hash, a run of r leading zero bits happens about once in 2^r items, so the longest run seen hints at how many distinct items there were. Averaging over many registers (here 1,024) tames the noise: it estimated 99,780 against a true 99,992, with a typical error of about 3 percent. Sketches also merge: combine per-server or per-hour HyperLogLogs by taking the maximum of each register, and get the distinct count for the union without double counting.
Going deeper
Choosing the error budget
Each structure's size is set by the error you accept: Bloom filter bits per item from the target false positive rate, Count-Min width and depth from the error bound and confidence, HyperLogLog register count from the standard error (1.04 divided by the square root of the number of registers). Decide what an error costs in your use case: a false positive Bloom answer usually just costs one unnecessary lookup.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Exact set or hash map | Small data, or when every answer must be exact | Memory grows with every distinct item |
| Bloom filter | Skipping expensive lookups for items that are definitely absent | False positives; no deletion or listing of items |
| Count-Min Sketch | Frequencies and heavy hitters in fixed memory | Over-estimates, especially for rare items |
| HyperLogLog | Distinct counts at any scale in kilobytes, mergeable across shards | Approximate (a few percent); cannot list the items |
Common mistakes
- Using a Bloom filter where a false positive is harmful, such as deciding a user is banned.
- Sizing a Bloom filter for today's item count and letting it overfill, so false positives explode.
- Expecting to delete from a plain Bloom filter.
- Trusting Count-Min estimates for rare items, which collisions inflate the most.
- Counting unique users per segment with exact sets when HyperLogLog sketches would merge cheaply.
In the wild
Storage engines such as Cassandra, HBase and RocksDB use Bloom filters to avoid reading files that cannot contain a key. Redis provides HyperLogLog as a built-in data type for counting unique items in a few kilobytes, and analytics databases offer approximate distinct counts based on it. Count-Min Sketches appear in stream processing for heavy-hitter detection and in network monitoring.
Check yourself
-
A Bloom filter says an item is not present. How sure is that?
Show answer
B. Certain: Bloom filters have no false negatives If any of its bits is 0, the item was never inserted.
-
A Bloom filter sized for 1 million items now holds 5 million. What happens?
Show answer
B. Most bits become 1 and the false positive rate rises sharply Plain Bloom filters do not grow; overfilling saturates the array.
-
Why does Count-Min Sketch take the minimum across rows?
Show answer
B. Collisions only add to counters, so the smallest counter is the least inflated estimate Every counter is at least the true count; the minimum has the least collision noise.
-
You have per-server HyperLogLogs of today's visitors. How do you get the distinct count across all servers?
Show answer
B. Merge the sketches by taking each register's maximum, then estimate once Merging avoids double counting visitors seen by several servers.
Recap
- Probabilistic structures trade a small, bounded error for huge memory savings.
- Bloom filters say 'definitely not' or 'probably yes', with about 10 bits per item for 1 percent false positives.
- They are used to skip expensive lookups: LSM files, caches, crawlers.
- Count-Min Sketch estimates frequencies and finds heavy hitters; it never under-counts.
- HyperLogLog counts distinct items in kilobytes and merges across shards.