HyperLogLog: Counting Distinct Items

The idea: count distinct items without keeping them

How many different users visited today? A set of user ids answers exactly, but it grows with every new user. HyperLogLog (HLL) answers approximately in a fixed, tiny amount of memory, and never stores the items. Redis offers it as PFADD key item (add) and PFCOUNT key (estimate the number of distinct items).

This page uses a small HLL: m = 16 registers and a 16-bit hash, so every bit can be shown. Pick a key (A or B) and an item and press PFADD, press Add 1000 to fast-forward, or run a demo. Each HLL shows its estimate next to the true count, which the page keeps on the side only so you can see the error.

Leading zeros as a sign of many items

A good hash looks like coin flips. Half of all hashes start with 1, a quarter with 01, an eighth with 001. Seeing a hash that starts with k − 1 zeros is like flipping k − 1 tails in a row: it takes about 2^k tries. So the longest run of leading zeros seen so far says roughly how many different hashes went by.

HLL splits the hash in two. The first p = 4 bits pick one of the 2⁴ = 16 registers M[0..15]. In the other 12 bits it counts the leading zeros and adds 1; that number is ρ (rho). The register keeps the maximum ρ it has seen: M[j] = max(M[j], ρ). Nothing else is stored. In Demo 1, victor lands in register 14, where alice had left 1, and raises it to 5.

A duplicate has the same hash, so the same register and the same ρ. It can never raise a register, and PFADD returns 0 (Demo 2: a duplicate changes nothing). That is why HLL counts distinct items, not additions. The page's hash is FNV-1a followed by the MurmurHash3 finalizer, cut to 16 bits; Redis uses a 64-bit MurmurHash2.

From 16 registers to one number

One register alone is a poor guess. Register j sees about 1/16 of the items, so on its own it would say 16·2^M[j]. One unlucky item can make that huge. In Demo 5: why one register alone is noisy, register 14 met an item whose 12 bits were all zero (ρ = 13) and alone would say 131072, while others say 512. A plain average of the 16 guesses is 11744 for 1000 items.

HLL uses the harmonic mean, which large outliers barely move, times a bias correction α:

$$E=\frac{\alpha ·m^2}{\sum _{j=0}^{m-1}{2}^{-M\left[j\right]}},\alpha =0.673\text{for}m=16$$

For small counts most registers are still 0 and this formula is badly off. Then HLL switches to linear counting: with V registers still 0, $E=m·\ln (m/V)$. The rule used here is the original one: linear counting when E ≤ 2.5·m = 40 and V > 0. The formula panel under the registers shows every number.

demo	true count	PFCOUNT	error
1: five names	5	5 (linear counting, V = 12)	0%
2: alice, bob, alice	2	2 (V = 14)	0%
3: uid:1 … uid:1000	1000	852	−15%
4: A ∪ B after PFMERGE	500	432	−14%

The standard error is about 1.04/√m. With 16 registers that is 26%, so errors of 15% are normal here (Demo 3: 1000 items). Redis uses m = 16384 registers of 6 bits each, 12 KB per key, for an error of 0.81%.

Merging: PFMERGE

Two HLLs built with the same hash and the same m merge by taking the larger value in each register: A[j] = max(A[j], B[j]). The result is exactly the HLL you would get by adding both sets of items to one key, so items in both are not counted twice. Servers can count separately and merge later, per hour into per day, per shard into a total.

In Demo 4: merge two HLLs, A gets uid:1–300 (PFCOUNT 221) and B gets uid:201–500 (194). PFMERGE A B leaves A with 432 for the 500 distinct ids. Adding two plain counts would not work: 300 + 300 = 600 counts the 100 shared ids twice.

In Redis

PFADD visits:mon alice bob carol   # (integer) 1: a register changed
PFADD visits:mon alice             # (integer) 0: nothing changed
PFCOUNT visits:mon                 # (integer) 3
PFMERGE visits:week visits:mon visits:tue
PFCOUNT visits:mon visits:tue      # union of several keys, without storing it

A Redis HLL is a string. Small ones use a compact sparse encoding (runs of zero registers) and switch to the 12 KB dense form as they fill. PFCOUNT caches its last result in the header until the next change. Redis's estimator is a newer one by Otmar Ertl, which needs no switch to linear counting. See Redis Connection and RESP for how these commands travel to the server, and Open Hash Tables for the exact, item-storing way to count.

Another one-pass, small-memory stream algorithm is reservoir sampling, which keeps a uniform random sample of k items.

To estimate how often each item appears (not how many distinct items), see Count-Min Sketch.

What the page leaves out

A 64-bit hash and 16384 registers; the large-range correction of the original paper (not needed with 64-bit hashes); HyperLogLog++ bias tables and Redis's improved estimator; the sparse encoding and its promotion to dense; and other sketches such as Bloom filters (is this item in the set?) and Count-Min (how often?).

References

Redis docs: HyperLogLog

Flajolet, Fusy, Gandouet, Meunier: HyperLogLog, the analysis of a near-optimal cardinality estimation algorithm (2007)

Redis docs: PFADD, PFCOUNT and PFMERGE commands

Heule, Nunkesser, Hall: HyperLogLog in Practice (HyperLogLog++)