Counting unique things is the rare problem where the naive solution is also the memory-hungriest one: to know whether you've seen an element before, you have to remember every element you've seen. A set of 100 million user IDs costs gigabytes. Yet Redis will count those same IDs to within 0.81% in at most 12 KB per key — a fixed cost whether the true count is six or six billion. The structure behind that, HyperLogLog, is built from three ideas that are each simple enough to fit in a sentence, plus one empirical patch that both Google and Redis had to bolt on because the elegant math fails exactly where production workloads live: small counts.

The entire count is hiding in leading zeros

Hash every element to a uniform bit string. Flajolet, Fusy, Gandouet and Meunier's 2007 paper calls the key quantity a bit-pattern observable: seeing the prefix 0^(ρ−1)1 — ρ−1 zeros then a one — at the start of a hashed value "is more or less a likely indication that the cardinality n is at least 2^ρ."

The coin-flip intuition: a hash starting with 1 happens for about half of distinct elements, 01 for a quarter, 0001 for one in sixteen. If the longest run of leading zeros you've ever observed is 20, you've plausibly seen on the order of 2^20 ≈ a million distinct values. Duplicates are free — the same element hashes to the same bits and can never update the maximum, which is why the estimate counts distinct elements by construction.

Storing that observable is absurdly cheap. The run length for a 64-bit hash is at most 64, so the whole "database" is one number that fits in 6 bits. The problem is variance: a single lucky hash doubles your estimate. One register is a rumor, not a measurement.

16,384 experiments from one hash function

The fix is stochastic averaging: instead of hashing each element with m different functions (m times the CPU), split one hash output. Redis takes a 64-bit hash, uses the first 14 bits to pick one of 2^14 = 16,384 registers, and counts the leading-zero run in the remaining 50 bits. Each register ends up tracking the maximum run over its own random 1/16,384th slice of the elements.

This also explains the famous 12 KB. A run within 50 bits needs 6 bits of storage, so the dense representation is 16,384 registers × 6 bits = 12,288 bytes — 12 KB, exactly, forever, for a structure that can estimate cardinalities up to 2^64.

The harmonic mean is the actual invention

Averaging 16,384 noisy estimates was already the LogLog algorithm (Durand–Flajolet, 2003), which averaged the register values themselves — amounting to a geometric mean of the per-register estimates 2^M[j]. HyperLogLog's contribution is almost embarrassingly small: use a normalized harmonic mean of the 2^M[j] instead.

The 2007 paper credits the idea to a note by Chassaing and Gérin and explains why it works: harmonic means "have the effect of taming probability distributions with slow-decaying right tails, and here they operate as a variance reduction device." A register that got a freak 40-zero run would drag an arithmetic or geometric mean upward; in a harmonic mean, one huge term barely moves the result, because you're averaging reciprocals.

That one change takes the standard error from LogLog's 1.30/√m to 1.04/√m — the paper notes LogLog's accuracy "can be matched by consuming only 64% of the original memory." Concretely: cardinalities "well beyond 10^9 with a typical accuracy of 2% while using a memory of only 1.5 kilobytes" in the paper's configuration, and 1.04/√16384 = 0.81% for Redis's 16,384 registers.

Where the math breaks: small counts

The raw HyperLogLog estimator is biased upward at low cardinalities — with most registers still at zero, the formula systematically overestimates. The original paper's remedy is to switch algorithms entirely below 2.5m: use LinearCounting, which just counts empty registers (ez) and estimates m · log(m/ez). For Redis that threshold is around 40,000.

Google's 2013 "HyperLogLog in Practice" paper (Heule, Nunkesser, Hall) shows why this regime matters more than the asymptotics. Their PowerDrill datastore runs about 5 million count-distinct computations on an average day, and 99% of them return 100 or less — while roughly 100 per day exceed one billion. The common case is tiny; the tail is enormous. Their changes, now collectively called HLL++:

  • A 64-bit hash instead of 32 bits, which eliminates the original paper's large-range collision correction entirely — hash collisions stop being a concern below 2^64 distinct items.
  • Empirical bias correction. They ran the raw estimator at known cardinalities, recorded the bias at 200 interpolation points, and ship that table with the algorithm; at query time, a k-nearest-neighbor interpolation (k=6) over the raw estimate looks up the correction. Measured bias vanishes above about 5m, so the correction only applies below that. With bias subtracted, the crossover where LinearCounting stops winning drops to an empirically determined 11,500 for precision 14 — the bias-corrected estimator takes over far earlier than the original 2.5m rule.
  • A sparse representation. If 99% of your counters hold ≤100 values, allocating 16,384 registers up front wastes nearly all of them. HLL++ instead stores a sorted list of (register index, value) pairs — kept compact with difference encoding between successive entries and a variable-length integer encoding, with a small unsorted buffer absorbing writes between merges. The sparse form can even run at a higher precision than the dense one, giving near-exact small counts, and converts to the dense 6-bits-per-register layout only when it would exceed 6m bits.

Redis's implementation, described in Salvatore Sanfilippo's release post, made the same moves independently of the HLL++ sparse design: a sparse encoding for small counters and a dense 12 KB encoding beyond it, plus its own bias fix — a polynomial regression correcting the estimate in the awkward 40,960–72,000 range where neither LinearCounting nor the raw estimator is clean.

Max-merge is why HLL took over distributed systems

Every register only ever moves one direction: it holds a maximum. So the sketch of a union is just the element-wise max of two sketches — merging per-shard or per-day HLLs is lossless with respect to the sketches, giving exactly the structure you'd have built from the combined stream. That's PFMERGE in Redis (O(N) in the number of sketches; PFADD and PFCOUNT are O(1)), and it's the property that lets you precompute per-hour uniques and answer "uniques this month" by folding 720 sketches of 12 KB each. Note what you don't get: intersections. Max-merge gives unions only; intersection estimates require inclusion-exclusion on top, with error that grows accordingly.

Two engineering details from the Redis implementation are worth stealing. First, an HLL is encoded as an ordinary Redis string, so GET serializes a sketch and SET restores it — replication, backup and client-side transfer came for free. Second, PFCOUNT caches its last computed estimate with an invalidation bit that writes flip, which took it from recomputing 16,384 registers per call to about 60,000 calls per second in Sanfilippo's testing.

The arc of HyperLogLog is a good template for reading any "clever algorithm" paper: the asymptotic result (1.04/√m with harmonic means) is the headline, but the production systems — PowerDrill and Redis both — earned their accuracy in the unglamorous region the analysis treats as a footnote, with lookup tables of measured bias and encodings tuned for counters that mostly stay small. The commands are even named in that spirit: Redis's PF prefix honors Philippe Flajolet, who died the year before antirez implemented them.

References

hyperloglogcardinalityredisprobabilistic-data-structuressketches