LESSON 23.2
HyperLogLog
Count unique visitors, IPs or search terms across billions of events in 12 KB with under 1% error. The intuition, the accuracy numbers, and why sketches can be merged.
7 min read
"How many distinct users visited today?" sounds simple. Counting exactly means remembering every user id seen, which for billions of events across many dimensions (per page, per country, per hour) is a lot of memory. HyperLogLog (HLL) estimates distinct counts with a fixed, tiny amount of memory and a known error.
Stream a million unique IDs, change the precision, or merge two sketches.
The intuition
Hash each item to a uniformly random bit string. Look at how many leading zeros it has:
- Starts with 1
- 1 in 2 hashes
- Starts with 01
- 1 in 4
- Starts with 0001
- 1 in 16
- r leading zeros, then a 1
- about 1 in 2^(r+1)
If the longest run of leading zeros you've seen is 20, you've probably hashed around a million distinct items. Duplicates hash identically, so they never change the answer. That's what makes it a distinct count.
One maximum is a very noisy estimate. HyperLogLog fixes that by averaging many.
How it works
- Hash each item to 64 bits. Use the first p bits to pick one of m = 2^p registers.
- In the remaining bits, count the position of the first 1. Store it in that register if it's larger than what's there.
- To estimate, combine all registers with a harmonic mean (which damps outliers) and a correction constant.
- Small and very large counts get extra corrections; modern variants (HyperLogLog++) handle small sets exactly.
Accuracy and memory
- m = 1,024 registers~768 bytes
- ~3.2% error
- m = 16,384 (Redis)12 KB
- ~0.81% error
- Exact set of 100M ids~1.6 GB of 16-byte ids
- 0% error
The memory doesn't grow with the count: 12 KB estimates ten users or ten billion with the same relative error.
Merging
HLL sketches built with the same parameters can be merged by taking the maximum of each register. The result is the sketch of the union. That enables:
- Counting per server or per partition, then merging centrally.
- Daily sketches rolled up into weekly and monthly uniques without rereading raw data.
- Storing one sketch per dimension combination in an OLAP store and merging at query time.
Intersections can be estimated with inclusion–exclusion, but error grows quickly; prefer other techniques when overlaps are small.
Exact set
- Exact
- Can list members
- Memory grows with distinct items
Pick it when: Small sets, or when exactness matters (billing).
HyperLogLog
- Fixed tiny memory
- Mergeable
- ~1% error
- Can't list or remove members
Pick it when: Unique visitors, distinct IPs, cardinality in analytics.
In Redis: PFADD visitors:2026-10-17 user42, PFCOUNT visitors:2026-10-17, and PFMERGE for unions. Analytics databases expose the same idea as approx_count_distinct.
Try it
API Usage Metering Pipeline HLD
Count usage per customer accurately and cheaply.