System design · interactive
Counting distinct items with HyperLogLog
How many unique visitors today? A set of every id costs memory per visitor. HyperLogLog hashes each id and remembers only the longest run of leading zeros seen in each of a few registers. Rare long runs mean many distinct items.
64 registers (max leading-zero run + 1)
- Actual distinct
- 10,000
- Estimate
- 10,392
- Error
- 3.9%
memory: 48 bytes vs exact set ~160 KB
48 bytes estimates 10,000 distinct ids within 4%. Typical error with 64 registers is about 13%; Redis uses 16,384 registers (12 KB) for about 0.8%.
1 2 3 Some bits pick a register; each keeps its maximum. Combining many cuts the variance.
Error ≈ 1.04 ÷ √registers.
4
In production
Tools and technologies
HyperLogLog counts uniques in most analytics systems.
Not tied to one language — use these names when you search docs or design a system.