20.4 How does HyperLogLog count unique visitors?

At the door: The bouncer asks everyone to flip a coin until it lands heads, and remembers only the longest run of tails anyone has managed. If the longest run tonight is 10 tails in a row, that's about a 1-in-1,000 event, so roughly a thousand different people probably came. One number, no guest list.

In the system: HyperLogLog (HLL) estimates the number of distinct items (the cardinality) using a hash as the coin:

1. Hash each item. A good hash looks random, and the same visitor always gives the same hash, so repeat visits don't count twice.
2. About half of all hashes start with 0, a quarter with 00, one in 16 with 0000. Seeing a long run of leading zeros suggests many distinct items.
3. One run is noisy (one lucky visitor), so HLL splits hashes into many registers (Redis uses 16,384), using the first bits of the hash to pick one. Each register keeps its longest run.
4. A harmonic mean of the registers, with corrections for small counts, gives the estimate.

Figure: the longest run of zeros tells you roughly how many distinct hashes you've seen.

Accuracy: standard error about 1.04 ÷ √(registers); with 16,384 registers, about 0.81%. Redis's HyperLogLog uses up to 12 KB per counter, whether it has seen a thousand visitors or a billion.

Merging is the superpower: take the maximum of each register across two HLLs, and you get the HLL of the union. So you keep one HLL per day, and "unique visitors this week" is a merge of seven, with no raw IDs stored.

In the chapter's code: Monday's 300,000 visits from about 130,000 distinct visitors are estimated within 0.1%, and the merged Monday + Tuesday estimate is within 0.7% of the true 186,505.

In Redis: PFADD visitors:2026-10-08 user123, PFCOUNT visitors:2026-10-08, PFMERGE visitors:week ....

What HLL can't do: tell you who visited, or whether a particular person did. For that you'd need the set itself (or a Bloom filter for "probably").

Memory code: "The longest lucky streak tells you how many tried."

---