HyperLogLog: Counting the Uncountable
Bloom Filters & Probabilistic Data Structures · Data & Hashing track
6 min read
In this module
How Many Unique Visitors?
You're running a busy website and you'd like a daily unique-visitor count. With 100 million page views in a day, the naive route — chuck every visitor ID into a set — costs gigabytes of RAM. The thing is, you don't really need the exact count. "About 12.3 million unique visitors, plus or minus 1%" satisfies almost every business question you could ask.
HyperLogLog (HLL) estimates the number of distinct elements (the cardinality) of a dataset using around 12 kilobytes of memory, regardless of how many billions you push through it.
The Key Insight
Here's the thought experiment that makes HLL click. You flip a coin over and over, tracking the longest run of consecutive heads you ever see. A 10-head streak has probability 1/1024, so seeing one suggests you've flipped at least a thousand times. A 20-head streak puts you somewhere near a million flips. The length of the streak quietly leaks how many flips happened.
HLL plays the same trick on hash values. The bits of a hash, for any halfway-decent hash function, behave like fair coin flips. So the longest run of leading zeros you've ever observed across all the hashes hints, surprisingly directly, at how many distinct items you've fed through.
hash("alice") = 0001... --> 3 leading zeroshash("bob") = 0100... --> 1 leading zerohash("carol") = 0000001. --> 6 leading zeros <-- this is rare!Six leading zeros somewhere in your observations hints at roughly 2^6 = 64 distinct elements seen (with the heavy caveat that one estimator on its own is wildly noisy).
HyperLogLog estimates cardinality by tracking the longest run of leading zeros it has seen across hash values. Long zero-runs, like long head-streaks, suggest many trials, which here means many distinct elements. Wrap the raw idea in some clever maths and you get estimates that are remarkably tight.
The HyperLogLog Algorithm
The headline trick is averaging across many independent estimators:
- Hash the element.
- Use the first few bits of the hash to pick a register (bucket).
- Count leading zeros in the remaining bits.
- Update that register with the maximum it's ever held.
m = 1024 registers (uses first 10 bits for register selection)registers = array of 1024 values, all initially 0
function add(element): h = hash(element) register_index = first 10 bits of h // 0 to 1023 remaining = rest of the bits leading_zeros = count_leading_zeros(remaining) + 1 registers[register_index] = max(registers[register_index], leading_zeros)For the final estimate, HLL takes the harmonic mean of 2^(register value) across every register, then multiplies by a bias-correcting constant (alpha). Two patches cover the edges: when many registers are still zero, small counts switch to a different estimator (linear counting), and the original paper adds a large-range correction for 32-bit hashes as they near saturation. The harmonic mean is what keeps the estimate stable — it tames the influence of any one outlier register.
Shrink it to something you can follow by hand: m = 4 registers chosen by 2 index bits, and eight distinct items. Before each step, work out the register and rho yourself, then check. The final two steps compute the estimate.
HyperLogLog by hand: 4 registers, 8 items
Accuracy
A thousand registers (1 KB) gets you a standard error around 3.25%. Bumping to 16,384 registers (12 KB) drops the error to roughly 0.81%.
For 100 million unique visitors, that's an estimate accurate to within about 800,000 — fine for analytics, fine for capacity planning, fine for billing thresholds.
Memory: The Shocking Efficiency
Lay them side by side:
| Approach | Memory for 100M unique elements |
|---|---|
| Exact HashSet | ~4 GB |
| Bloom filter (existence only) | ~120 MB |
| HyperLogLog (count only) | ~12 KB |
Against the exact set that's a ratio of roughly 300,000 to one. The compromise is steep — you only get a count, the elements themselves are gone, and even the count is fuzzy. For many use cases, that count is the entire deliverable.
HyperLogLog in Practice
Redis ships HyperLogLog as a first-class data type, exposed through PFADD, PFCOUNT, and PFMERGE. Count unique visitors, unique queries, unique source IPs — anywhere cardinality is the question.
PFADD visitors "user_123"PFADD visitors "user_456"PFADD visitors "user_123" // duplicate, does not change the countPFCOUNT visitors // returns 2Analytics engines like Trino and Presto use HLL behind their approx_distinct function, and distinct-value estimates like these feed the planner's choice of join strategy. Core PostgreSQL takes a different route: ANALYZE estimates distinct values from a random sample of rows, and HLL arrives only through the postgresql-hll extension.
Network telemetry uses HLL on live flows to count distinct source IPs, destination ports, or flow IDs as packets stream past.
Mergeability
HyperLogLog sketches merge. Run one sketch on server A, another on server B, and you can combine them into a single sketch that counts the union of unique visitors — no double-counting of users who hit both servers.
The merge is just the element-wise maximum of the two register arrays. The result is mathematically identical to what you'd have gotten if every event in both streams had been fed into one HLL from the start.
That property is why HyperLogLog is the de-facto cardinality tool in distributed systems. Each node keeps a local sketch, sends it to a coordinator, and the coordinator merges them into a global estimate without any of the original data ever leaving the edge.
The Elegance of HyperLogLog
HyperLogLog is a small marvel of applied mathematics. The premise — that the longest run of leading zeros in a stream of hashes encodes how many distinct hashes you saw — fits on a postcard. The consequence is that 12 kilobytes of memory can hold an estimate of billions of distinct elements to within a percent or two. Mergeable sketches, predictable error bars, vanishing memory footprint. If you need to count distinct things at any serious scale, HyperLogLog is almost always the answer you arrive at, and usually the answer you should have started with.