HyperLogLog: counting distinct things

A news site wants to show "unique readers" for each of its 20,000 articles, per hour, per day and per week, and the same for the whole site, which has about 40 million readers a day. Counting page views is easy: add one per view. Counting distinct readers isn't, because a reader who comes back must not be counted again.

The exact way is a set: keep every reader ID seen, and count the set. That has two costs:

• Memory grows with the answer. 40 million 8-byte reader IDs is 320 MB for the site's daily count alone, before any set overhead. One set per article per hour multiplies that by thousands.
• Counts don't add up. If 600,000 people read in the morning and 600,000 in the evening, the day's total is somewhere between 600,000 and 1.2 million. Only the sets themselves can tell, so every set must be kept to answer any longer period.

HyperLogLog gives up exactness to fix both. It estimates the number of distinct items, the cardinality, in a fixed amount of memory, typically 12 KB, with an error of about 1%. And two of its sketches can be merged into the sketch of the combined set, so a day can be built from its hours.

Hash each reader ID to 64 random-looking bits. The same reader always gives the same hash, so repeats change nothing. Then look at how many zeros each hash starts with. Each bit is 0 half the time, so:

So remembering just one number, the longest run of leading zeros seen so far, gives a rough count. If the longest run among all hashes is 20 zeros, the site has probably seen a million or two distinct readers. It is like someone who reports that their longest streak of heads today was 13: they probably flipped a coin thousands of times.

One observation is far too noisy, though. A single lucky hash with 20 zeros among the first ten readers makes the estimate a million. The answer is to make many independent observations and average them.

HyperLogLog splits the readers into m groups using the hash itself, and keeps one small counter, a register, per group. In Redis's version, m = 16,384:

To estimate, HyperLogLog combines the registers with a harmonic mean, which keeps one register with an unusually long run from dragging the answer up. The formula is E = α × m² ÷ Σ 2^(−M[j]), where M[j] is register j and α ≈ 0.7213 corrects a known bias. The relative error is about 1.04 ÷ √m: for 16,384 registers, 1.04 ÷ 128 ≈ 0.81%.

Each register only has to hold a number up to about 50, so 6 bits are enough. Memory is set by m alone, never by how many readers there are:

Four times the memory halves the error, since it falls with the square root of m. A 16,384-register sketch, run over growing numbers of distinct reader IDs, gave these errors:

Here is the property that makes HyperLogLog more than a memory saving. A reader always lands in the same register with the same value, so the sketch of two combined sets is just the register-by-register maximum of their sketches. The merged sketch is exactly the one you would have built by feeding both streams into a single sketch: no reader is counted twice.

So the news site never keeps raw reader lists. It keeps one sketch per article per hour, and merges them on demand into days, weeks or any group of articles. In Redis that is three commands:

PFCOUNT with several keys merges on the fly instead, which is slower and its result isn't cached, so a busy page should read a stored merged sketch. Warehouses offer the same: BigQuery's HLL_COUNT.INIT builds sketches in a query, HLL_COUNT.MERGE combines them, and a rollup table can store sketches rather than counts so later queries can still combine any periods (Data warehouses, lakes & pipelines).

The editors ask a new question: how many readers read both article A and article B? Each had about a million readers. There is no merge for an intersection, so the obvious trick is the inclusion-exclusion rule: |A ∩ B| = |A| + |B| − |A ∪ B|.

The error of a union of 2 million is about 0.81%, roughly 16,000 readers, more than three times the answer. Small overlaps between large sets can't be estimated this way. HyperLogLog is a poor fit when you need intersections or differences with reasonable accuracy; other sketch families, such as Theta sketches, do that better.

Small counts need care for a different reason. With few items, most registers are still zero and the raw formula is biased. Implementations switch methods at the low end:

And a sketch can only grow. It can't remove a reader, list who was counted, or tell whether one particular reader was seen; for that last question, see Bloom filters.

The algorithm counts beyond a billion items with about 2% error in only 1.5 KB. Error is a design choice, not an accident: pick m for the error you can live with, and the memory follows. BigQuery, for example, lets a sketch's precision be set from 10 to 24, defaulting to 15; higher means more accurate and larger.

For the news site, the checklist:

• One sketch per article per hour, merged into longer periods and wider groups on demand.
• Store sketches, not counts, in rollups, so any combination stays possible.
• Use the same hash and precision everywhere; sketches only merge with sketches built the same way.
• Show estimates as estimates ("about 1.2 million readers"), never as exact figures.
• Don't subtract sketches to find overlaps between large groups.