How to Count Millions of Unique Things Without Storing Them

Open any analytics dashboard and you'll see a number like 4.2 million unique visitors today. It's so ordinary you scroll past it. But stop on it for a second and ask the uncomfortable question: where is the list of those 4.2 million people kept?

The honest answer is that it isn't. Nobody wrote them down. The system that produced that number has, at most, a few kilobytes set aside for it — far too little to hold four million of anything. And yet the count is right to within a fraction of a percent. That gap, between "four million people" and "a few kilobytes," is one of my favorite ideas in all of computing. It's called HyperLogLog, and once you see how it works you start noticing it everywhere.

The dumb way, and why it dies

Start with the obvious solution, because it tells you what the hard part actually is. You want unique visitors, so the first instinct is a counter you bump on every request. That fails immediately: a counter measures hits, not people. One visitor who loads fifty pages adds fifty. You wanted one.

So to count unique things, you have to remember who you've already seen — a set of every IP or device that's shown up. And that's the whole expense, right there. Deduplication is the thing that costs memory. The set grows with every new visitor and never stops. Worse, it doesn't compose: you can't take two servers' counts and add them, because the people who visited both get counted twice. Seven days of daily unique counts don't sum to a weekly unique count. Counting distinct things is, quietly, one of the genuinely annoying problems at scale.

Which leads to the question that unlocks everything: do we actually need the exact number? Almost never. Nobody makes a different decision because the dashboard says 4,217,901 instead of 4.2 million. And the moment you allow yourself a small, bounded error — one or two percent — a door opens that's bolted shut for exact counting.

A coin, flipped

Here's the insight the whole thing rests on, and it has nothing to do with computers. Flip a coin and count how many heads you get in a row before the first tails. Most runs are short. A streak of ten heads is rare — it happens about once in a thousand tries.

Now turn that around. If I tell you the longest streak I saw all day was ten heads, you can guess how many times I flipped: roughly a thousand. You didn't watch me play. You worked out the scale of my afternoon purely from the rarest thing in it. Rare events are evidence of many attempts — that's the entire trick, and everything else is plumbing.

Now swap the coin for a hash function. Take each visitor's ID, hash it, and you get a string of effectively random bits. Look at the leading zeros — the run of zeros at the front before the first 1. Each leading zero is exactly one coin flip. A hash starting with a zero is a one-in-two event; two zeros is one-in-four; ten zeros in a row is one-in-1,024. So a hash with L leading zeros is a one-in-2^L rarity, and by the same logic as the coin game, if you actually saw one, you probably hashed about 2^L distinct things.

This is also where deduplication stops being a problem and starts being free. If alice comes back, she hashes to the exact same bits she did the first time. Her leading-zero count can't push the maximum any higher than it already did. A repeat visitor is invisible to the math — not because we checked a list and found her, but because the rarest-pattern trick simply doesn't care about a pattern it has already seen. You get dedup without remembering anyone. That still feels like cheating to me, and I've known about it for years.

From a lucky guess to an actual estimate

One maximum, on its own, is a terrible estimate. A single freak hash with a long zero-run throws the whole thing off, and the answer can only be a power of two — 8, 16, 32 — which is hopelessly coarse. The fix is the oldest move in statistics: don't take one measurement, take thousands and average them.

But you only have one stream of hashes. So you manufacture many measurements out of it by splitting. Read the first handful of bits of each hash as an address — say eleven bits, which name one of 2,048 buckets — and use the rest to count leading zeros. Now each bucket watches its own slice of the traffic and keeps its own maximum. Two thousand noisy little estimators instead of one, and because they're independent, averaging them crushes the noise. That version is called LogLog, and its estimate is a constant near 0.79 times the bucket count times two-to-the-average.

There's one more wrinkle. A plain average is still vulnerable to a single wild bucket. So you swap it for the harmonic mean — the reciprocal of the average of reciprocals — which leans toward the small values and barely flinches at one large outlier. That single change is the jump from LogLog to HyperLogLog, and it comes with its own constant, about 0.7213. (If you remember one thing for a code review: 0.79 is LogLog, 0.7213 is HyperLogLog. They are not interchangeable, and someone will notice.)

Strip away the names and the machine is small. Three moving parts.

The part that should be impossible

Here's the payoff, and it's worth sitting with. Run ten million distinct items through one of these and you'll land within about 0.16% of the true count — using roughly twelve kilobytes. Not twelve kilobytes per million. Twelve kilobytes, full stop. The memory does not grow with the traffic. A set would have ballooned into hundreds of megabytes; this never moves.

And the accuracy is a dial you set in advance, not a hope. More buckets, less error, still tiny: 2,048 registers fit in 1.5 KB at about 2.3% error; 16,384 registers take 12 KB and bring you under 1%. You pay once, up front, for exactly the precision you want, and then it's fixed forever. That property — bounded memory regardless of scale — is the reason this exists.

The trick that makes it usable: merging

One more property, and it's the one that moves HyperLogLog from a neat party trick to infrastructure. Suppose two data centers each counted their own visitors — call them east and west. You want the combined unique total. You already know you can't add the two numbers, because anyone who hit both gets counted twice.

But you can merge the two register rows, by taking the larger value in each position. The result is bit-for-bit identical to the row you'd have built if a single machine had watched all the traffic — because the same visitor always hashes to the same register, so the overlap lines up and quietly collapses instead of doubling.

So every edge node keeps a tiny sketch and ships only that to a collector. No raw identifiers leave the machine, the global count comes out correct, and the whole thing weighs less than a small image. This is the feature, not a footnote — it's what lets you count uniqueness across a fleet of servers without moving the data around.

Where this actually runs

I'd been carrying this around as a beautiful bit of theory until I went looking for it in production, and it's hiding in plain sight. The cleanest example I found is in Cloudflare's own engineering writeup on scaling their anomaly-detection platform — part of how they catch bots.

The idea is that bots distort ratios humans keep stable. A real audience for a site shows a modest number of distinct browser fingerprints. A bot farm faking a crowd suddenly shows tens of thousands. So Cloudflare keeps a sliding window of these high-cardinality features per site, in Redis, stored as HyperLogLog sketches, and watches for the distinct counts to go strange. Worth being precise here: HyperLogLog is the cheap sensor that makes "how many distinct" affordable across millions of sites; a separate scoring algorithm — histogram-based outlier scoring — is the part that actually decides "anomalous or not."

The detail that made me grin is the scaling story. When they pushed harder on it, the system started choking, and the culprit was the merge. Most Redis commands run in constant time; PFMERGE, the one that combines sketches, runs in linear time, proportional to the features times the window size. Under load, merging on every request piled up and became the bottleneck — the very operation that makes HyperLogLog elegant turned into the thing that broke it. Their fix was disarmingly simple: a small cache, a "recency register," that time-bounds how often the expensive detection runs for a given site-and-visitor pair. Stop recomputing an answer that barely changed since a moment ago, and throughput jumps. They didn't make merge faster; they stopped calling it when nothing had changed.

One honest note, because it matters: Cloudflare has since said it's winding this particular engine down in favor of newer behavioral detection. The lesson doesn't depend on the engine's lifespan, though. It's a clean, real example of a textbook data structure meeting the messy realities of running at 500,000 requests a second — including the part where its best feature becomes its worst bottleneck.

You've been using it for years

Once you know the shape of it, the names give themselves away. In Redis it's the PF commands — PFADD, PFCOUNT, PFMERGE — and the PF is a quiet tribute to Philippe Flajolet, who invented the original technique. Presto and Trino expose it as approx_distinct. Google's BigQuery and Google Analytics run on HLL++, their refined variant; that "active users" figure loading instantly on a site with hundreds of millions of visitors is an estimate off a sketch, not a tally of a list.

And there's a telling absence. MySQL has no built-in HyperLogLog — just exact COUNT(DISTINCT), done the slow way. That's not an oversight; MySQL is a transactional database, built for fetching and updating individual rows, not for sweeping billions of them to estimate cardinality. HyperLogLog shows up precisely where the scale is large enough that an estimate is the sane choice. The presence and absence both tell you the same thing about when to reach for it.

The one idea

Strip away the buckets and the harmonic mean and the war stories, and what's left is a single thought, the one the coin game handed us at the start:

When the question is "how many distinct?", you don't need the things themselves. You only need evidence of how rare the rarest pattern was.

Hold onto that and a billion visitors collapse into a few kilobytes you can carry in your pocket. It still reads like a magic trick. It's just math that learned to forget on purpose.

Sources & further reading

• Cloudflare, Lessons Learned from Scaling Up Cloudflare's Anomaly Detection Platform — the Redis/HyperLogLog and PFMERGE story.
• Flajolet, Fusy, Gandouet & Meunier (2007), HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm — the original paper.
• Heule, Nunkesser & Hall (2013), HyperLogLog in Practice — Google's HLL++ improvements.
• Google Cloud, Using HLL++ to speed up count-distinct on massive datasets .