HyperLogLog

From "Is It In?" to "How Many?"

The last two lessons — Bloom Filters and Cuckoo Filters — answered one question: is this thing in the set? They test membership. This one answers a completely different question that comes up just as often: how many distinct things have I seen? Unique visitors to a site today. Distinct IP addresses hitting a firewall. Distinct search terms this hour. Distinct users who saw an ad.

The exact way is brutal. To count distinct, you keep a set — every new item you check "have I seen this?" and add it if not. That works, and for a few thousand items it's the right answer. But the memory grows with the number of distinct items: counting a billion distinct IPs means holding a billion IPs in RAM — tens of gigabytes, per counter, and you often want thousands of counters (per page, per hour, per campaign). Exact distinct counting simply doesn't fit.

HyperLogLog answers "how many distinct?" using a fixed, tiny amount of memory — about 12 kilobytes — no matter whether the true count is a thousand or a billion, with a typical error under 1%. And it does it while storing not one of the items. That sounds impossible; counting distinct things is supposed to mean remembering which things you've seen. The trick is to stop remembering the things and instead watch how rare a pattern the stream has accidentally produced — because rarity, it turns out, is a measuring stick for cardinality.

How HyperLogLog counts distinct items without storing any of them. An item is hashed into a string of random bits. The first few bits — call it p bits — pick one of m registers. The remaining bits are scanned for their leading zeros, and the position of the first 1 is the item's rank. Each register keeps only the maximum rank it has ever seen. The picture shows an item flowing through a hash into a bit string split into a register index and a rank, the rank landing in a wall of registers, and those registers being combined by a harmonic mean into a single cardinality estimate. The headline result is drawn as a badge: with 16,384 registers this counts up to a billion distinct items using a flat 12 kilobytes of memory, with a standard error of about 0.81 percent — and it never stores a single one of the items themselves. The intuition underneath: rare bit patterns only show up after many distinct trials, so the rarest pattern the stream has produced is a ruler for how many distinct things went in.

Rarity Is a Ruler

Here's the whole idea in one image: flip a coin until you get heads, and count the tails first. Usually you get heads quickly. But if you told me the longest opening run of tails you ever saw in a big batch of tries was ten, I'd bet you ran that experiment about a thousand times — because a run of ten tails happens only about once in 2¹⁰ ≈ 1024 tries. The rarest thing you've observed is a ruler for how many times you tried.

HyperLogLog turns every item into exactly that experiment. Hash the item into a string of uniformly random-looking bits, and count its leading zeros. Because each bit is 50/50, the chance of seeing k leading zeros is 1 in 2ᵏ — one leading zero is a coin flip, three leading zeros is 1 in 8, ten is about 1 in 1,024. So across a whole stream of distinct items, the longest run of leading zeros you've seen estimates the count: if the rarest pattern is k leading zeros, you've probably fed in about 2ᵏ distinct items. (Call that longest run the rank.)

And it genuinely works: hash a million distinct items, and the longest leading-zero rank 21 is about what shows up — and 2²¹ ≈ 2,000,000, the right order of magnitude. Duplicates don't fool it, either: re-hashing an item you've already seen produces the same bits and the same rank, so it can't push the maximum any higher. You're measuring distinctness, for free.

There's just one problem, and it's a big one: a single "longest run" is wildly noisy. One unlucky item that happens to hash to twenty leading zeros would scream "a million items!" after you've added ten. The raw estimate can be off by a factor of two in either direction. A single ruler isn't enough.

The core intuition of HyperLogLog: rarity is a ruler. Each item is hashed to uniformly random bits, so the chance of seeing a run of k leading zeros is one in two-to-the-k — one leading zero is a coin flip, ten leading zeros is about one in a thousand. So the longest run of leading zeros you have seen across the whole stream is a signal of how many distinct items went in: if the rarest pattern is k leading zeros, you have probably made about two-to-the-k trials. It is the same idea as the longest run of heads in a batch of coin-flip sessions — a long run means many sessions. A measured example: hashing one million distinct items, the longest leading-zero rank observed was 21, and two-to-the-21 is about two million, the right order of magnitude. But a single longest-run reading is wildly noisy — one lucky rare pattern can throw the estimate off by a factor of two — which is exactly the problem the next step solves.

A Thousand Rulers: Stochastic Averaging

The fix is the heart of the algorithm, and it's beautiful: don't use one ruler — use thousands, and average them.

Split the stream into m independent buckets, called registers. Which register an item belongs to is decided by the item's own hash: take the first p bits as the register index (so m = 2ᵖ registers), and use the remaining bits for the leading-zero rank. Each register quietly keeps the maximum rank it has ever seen — its own little longest-run experiment, run on the roughly n/m items that landed in it. One lucky item now only corrupts one register out of thousands, instead of the whole estimate. This is stochastic averaging: the hash does double duty, both partitioning the stream and measuring each part.

Then you combine the m registers into one number. HyperLogLog's specific choice — the thing that makes it Hyper — is to combine them with a harmonic mean (roughly, α · m² / Σ 2^(−register), with a small constant α ≈ 0.7). Why the harmonic mean instead of a plain average? Because it's robust to large outliers: one register that got unlucky and holds a huge rank barely moves a harmonic mean, whereas it would wreck an arithmetic one. That single choice is what tamed the earlier "LogLog" algorithm into HyperLogLog.

The payoff is a clean, tunable law. The relative standard error is about 1.04 / √m — so accuracy is a dial you turn with the number of registers. A real run shows it converging exactly as promised: ~14% error at 16 registers, 3.7% at 256, 1.6% at 4,096, and ~0.81% at 16,384. Quadruple the registers, halve the error. The lab below lets you feel it directly — add items and watch each one light up a register and set a rank, then slide the register count up and watch a hopeless estimate snap into a sharp one.

A live HyperLogLog. Add an item and watch its hash split — the first p bits light up a register, the leading zeros of the rest set a rank, and the register keeps its max. Add the same item again and nothing moves: it counts distinct, not volume. Stream a burst and watch the estimate track the true distinct count. Then drag the register dial: with only a handful of registers the estimate is wild, but as m grows the error collapses toward the theoretical 1.04/√m — the whole reason a real HyperLogLog uses 16,384 of them.

Why HyperLogLog uses thousands of registers instead of one: stochastic averaging. A single longest-run estimator is in the right ballpark but has enormous variance. The fix is to split the stream into m independent buckets — the first p bits of each item's hash choose which register it belongs to — and let each register track its own longest run. The m register readings are then combined with a harmonic mean, which is robust to a single lucky-large register, and scaled by a constant. The result is that the relative standard error falls as roughly 1.04 divided by the square root of m. The accompanying chart shows measured error shrinking as m grows: about 14 percent at 16 registers, 3.7 percent at 256, and down to about 0.81 percent at 16,384 registers. Many noisy rulers, averaged the right way, become one sharp estimate. This is the step that turns a cute idea into a production-grade algorithm.

The Budget: 12 KB Counts a Billion

Now count the cost, because this is where HyperLogLog stops being clever and starts being magic.

A register only ever holds a small number — the longest run of leading zeros, which for a 64-bit hash tops out around 50, so 6 bits per register is plenty. The standard configuration uses m = 2¹⁴ = 16,384 registers, which is 16,384 × 6 bits = 12,288 bytes ≈ 12 KB. Plug that m into the error law: 1.04 / √16384 = 0.81%. So twelve kilobytes buys you distinct-counting with under one percent error.

And here's the part that breaks intuition: that 12 KB is flat. It does not grow with the number of distinct items. A HyperLogLog that has counted a thousand distinct users and one that has counted a billion are both exactly 12 KB — the registers just hold slightly larger ranks. Against an exact set, the gap is absurd: at a billion distinct items, an exact set needs roughly 20 GB (tens of gigabytes), so the HyperLogLog is roughly 1.6 million times smaller. And because it counts distinctness, duplicates are free — you can pour two million repeated events into it and the estimate doesn't budge, because a repeat can only re-set a register to a rank it already holds. Constant memory, sublinear error, unlimited duplicates. That's the trade §8 has been building toward: give up exactness, and the impossible fits in a cache line's worth of RAM.

The two payoffs of HyperLogLog, shown together. On the left, memory is flat: a HyperLogLog with 16,384 registers of 6 bits each is a fixed 12 kilobytes, whether it has counted a thousand distinct items or a billion. Compared with an exact set that must store every item, that is roughly 1.6 million times smaller at a billion distinct — and duplicate items are free, because re-adding a value can only re-set a register to a rank it already holds. On the right, HyperLogLogs merge: the union of two sketches is computed by taking, for each register position, the larger of the two values. No re-scan, and shared items are never double-counted. That means you can count uniques on many machines or across many days independently, then combine the sketches with a register-wise maximum to get the total distinct count — which is exactly what Redis's PFMERGE and multi-key PFCOUNT do.

Merge for Free

There's one more property, and for distributed systems it might be the most important of all: HyperLogLogs merge.

Because a register just holds the maximum rank seen for the items that hashed to it, the union of two HyperLogLogs is computed by taking, register by register, the larger of the two values. That's it — a register-wise maximum. The merged sketch is exactly the sketch you'd have built by feeding both streams into one HyperLogLog from the start, and it counts shared items only once, automatically, because a duplicate across the two streams was always going to produce the same rank in the same register.

This is enormous in practice. You can count unique visitors per server, or per hour, or per shard, entirely independently — no coordination, no shuffling raw data around — and then combine any subset of those sketches with a cheap register-wise max to get the exact-same-quality distinct count over the whole. Weekly uniques? Merge the seven daily sketches. Uniques across the fleet? Merge one sketch per machine. A real merge bears this out: two sketches of 60,000 and 50,000 items that overlapped on 20,000 merged to an estimate of about 91,800 against a true union of 90,000 — the 20,000 overlap counted once, not twice. Try doing that by shipping and de-duplicating raw sets.

Where It Runs, and the Sharp Edges

HyperLogLog is everywhere you need to count uniques over data too big or too fast to store.

Redis ships it as a first-class type: PFADD to add, PFCOUNT to estimate, PFMERGE to union — and the commands are prefixed PF in memory of Philippe Flajolet, who invented the algorithm. A real session makes it concrete: PFADD-ing 100,000 distinct visitors and calling PFCOUNT returned 99,471 (0.53% off), in a key that STRLEN reports as 12,304 bytes; pouring in 500,000 duplicate adds left the count unchanged; and PFMERGE-ing a Monday and Tuesday sketch gave the two-day unique count directly, overlap and all.
Data warehouses lean on it hard: BigQuery's APPROX_COUNT_DISTINCT, Presto/Trino's approx_distinct, Spark's approx_count_distinct, Druid, and Elasticsearch's cardinality aggregation are all HyperLogLog under the hood — because COUNT(DISTINCT ...) exactly over billions of rows is a query that either runs out of memory or takes forever.

Two sharp edges worth knowing. First, HyperLogLog is weakest when the count is small — with only a handful of distinct items, most registers are still empty and the harmonic-mean formula misbehaves, so real implementations switch to a simpler linear-counting correction in that range (and HyperLogLog++, Google's 2013 refinement, adds 64-bit hashing, a compact sparse representation for small counts, and empirical bias correction). Second, it answers exactly one question — how many distinct — and only approximately. It cannot tell you whether a specific item is present (that's a Bloom filter), it cannot list the items, and if you need the exact number, it's the wrong tool. Reach for it when the set is huge, the memory is fixed, and a ~1% error on a distinct count is a price you're glad to pay.

The Counting Sketches Begin

Step back and the shape of §8's second half comes into focus. The membership sketches — Bloom and Cuckoo — answered is this one thing in the set? HyperLogLog opened the counting sketches by answering a question no set membership can: how many distinct things are in the set? — and it did it in a flat 12 KB by measuring rarity instead of remembering items.

Two counting questions remain, and each gets the same treatment: a clever hash-based structure that trades a little accuracy for enormous space savings. "How often does each thing occur?" — the heavy hitters, the frequency of every key in a stream — is answered by a Count-Min sketch, and it's next. "How similar are two sets?" — the overlap between two huge collections — is answered by MinHash. You've now seen the deepest of the counting sketches; the remaining two reuse the same instinct you just built — hash it, keep a tiny summary, accept a bounded error — pointed at frequency and similarity instead of cardinality.