HyperLogLog

How can a site count millions of unique visitors in 12 KB?

To count unique visitors exactly, you have to remember every visitor ID you've seen, so memory grows with the audience. HyperLogLog gives a close estimate using a small, fixed amount of memory, however many visitors arrive.

A hash function turns each ID into random-looking bits, and about one hash in 2ᵏ starts with k zeros. So if the longest run of leading zeros you've seen is 20, you've probably seen about 2²⁰, roughly a million, different IDs.

A repeat visitor produces exactly the same hash, so it can never raise that record. Duplicates cost nothing, and no list of past visitors is needed.

HyperLogLog

Redis's PFCOUNT command counts uniques in at most 12 KB

The Redis database has HyperLogLog built in. PFADD adds items, and PFCOUNT returns the estimated number of different ones. Each counter uses at most 12 KB, with a typical error of about 0.81%.

Reddit has described using it to count post views. Google BigQuery's APPROX_COUNT_DISTINCT uses a variant called HyperLogLog++. In both cases, an answer within about 1% is good enough.

HyperLogLog

Thousands of small counters cancel out one lucky hash

A single record is unreliable, because one lucky hash could make the estimate far too high. So the first bits of each hash pick one of m registers, small counters that each keep the longest zero run in their share of IDs.

The registers are combined with a harmonic mean, a kind of average that a few big values can't throw off, and then scaled up. Redis uses 16,384 six-bit registers, 12 KB in all.

Two sketches can be merged by keeping the larger value in each register. The result counts both sets together, for example two days of visitors.