No. 01Probabilistic structures
HyperLogLog
Counting, with commitment issues.
Published
Counting distinct visitors exactly usually means remembering who has already arrived. HyperLogLog would rather not maintain the guest list. It keeps a small sketch and estimates the headcount instead.
Try it: add visitors, then send some back
Add visitors. Send some back. Watch what the sketch remembers.
16 registers
- 1
- 0
- 3
- 2
- 0
- 1
- 0
- 0
- 1
- 2
- 0
- 0
- 0
- 0
- 1
- 2
- Exact distinct (comparison only)
- 10
- Toy estimate
- 11.1
- Visitors sent back
- 0
New visitors raised 8 registers. Each keeps only the largest rank it has seen.
16 registers
- 1
- 0
- 3
- 2
- 0
- 1
- 0
- 0
- 1
- 2
- 0
- 0
- 0
- 0
- 1
- 2
- Exact distinct (comparison only)
- 10
- Toy estimate
- 11.1
- Visitors sent back
- 10
Returning visitors hash to the same registers with the same ranks, so nothing changed.
This uses 16 registers to make the mechanism visible. It does not have Redis’s production precision.
Why?
A hash spreads visitors evenly. A run of leading zeros of length k turns up about once per 2^k different hashes, so the largest run in each register hints at how many different visitors it has seen. The same visitor always gives the same hash.
It hashes each item, uses part of that hash to choose a register, and remembers a particular extreme pattern in the remaining bits. Across many registers, those patterns help estimate how many different items went through. A returning visitor produces the same hash, so repeating that visitor doesn't keep inflating the sketch.
Try adding new visitors, then send the same ones back. Watch the registers, not just the headline number: even a new visitor may leave them unchanged.
The bargain is small storage for an approximate answer. You cannot ask the sketch to hand over its guest list. It never agreed to keep one.