Data structures · 10 min

HyperLogLog

Count 10 million different visitors in 12 KB, to within about 1%, without storing a single ID.

Here is a challenge. Your home page gets 30 million visits today from about 10 million different people. At midnight you must say how many different people came. You get 12 KB of memory.

The obvious answer is a set holding every visitor ID you have seen. At 16 bytes an ID, 10 million IDs is 160 MB. 12 KB holds just 768 IDs. It sounds impossible.

You get one allowance: the answer may be off by about 1%. A dashboard that says 10.1 million instead of 10 million is fine. That allowance turns out to be enough, and the trick that uses it is called HyperLogLog.

A clue from coin flips

Forget visitors for a moment. A friend spends the afternoon flipping a coin in rounds. Each round, they flip until the first tails. The heads before that tails are the round’s run. At the end they tell you one thing only: their longest run was 10.

How many rounds did they play? A run of 10 or more needs the first 10 flips to be heads, which happens about once in 2¹⁰ = 1,024 rounds. So they probably played somewhere around a thousand rounds. Not exactly a thousand, but surely not 10, and surely not a million.

That is the clue. You never saw the rounds. You kept one small number, the longest run, and it still told you roughly how many rounds there were.

Make every visitor flip coins

Hash each visitor’s ID and write the number in binary. A good hash makes every digit behave like a coin flip: 0 half the time, 1 half the time. Treat each 0 as heads and the first 1 as tails. The run is the number of 0s at the start, before the first 1.

A hash that starts 000001… has a run of 5. About 1 visitor in 2⁵ = 32 gets a run of 5 or more. About 1 in 1,024 gets 10 or more.

Now keep one number: the longest run seen so far. If it reaches 10, you have probably seen about a thousand different visitors. With 10 million visitors it lands around 23: 2²³ is about 8.4 million and 2²⁴ about 16.8 million, and 10 million sits between them.

Repeat visits cost nothing. The same ID always gives the same hash and the same run, so the record doesn’t move. Someone who reloads the page 50 times is counted once. That is why this counts different people, not visits.

Split the crowd into boxes

The fix: keep many records instead of one. Use the first few digits of each hash to send the visitor to a box. Four digits give 16 boxes, #0 to #15. Each box keeps its own longest run, counted in the digits after those first four.

The demo’s example ID, “sakura”, hashes to 3,506,458,617. In binary, split into its parts, that is 1101 | 000 | 1 | 0000 0000 0100 1111 1111 1001. The first part, 1101, is 13, so “sakura” goes to box #13. Then come three 0s before a 1, so its run is 3. The rest is ignored.

The demo stores run + 1 and calls it the score, so that 0 can mean “empty box”. “sakura” has run 3 and score 4, and box #13 keeps 4 unless it already holds more. The numbers you see in the demo’s boxes are scores.

Each box sees about a sixteenth of the crowd and guesses its share the same way as before: a box holding score 6 (a longest run of 5) has probably seen around 2⁵ = 32 visitors. A lucky visitor can now spoil only one box in 16.

Then the guesses are combined. Say four boxes guess 30, 34, 28 and 1,000,000. A plain average gives about 250,000: the one lucky box swamps the other three.

HyperLogLog flips each guess into 1 ÷ guess first. A huge guess becomes a tiny number, so it can barely move the total: 1/30 + 1/34 + 1/28 + 1/1,000,000 ≈ 0.098. Divide the 4 boxes by that and flip back: 4 ÷ 0.098 ≈ 41 per box. This kind of average is called the harmonic mean.

Each box only saw about a quarter of the crowd, so 41 is a guess for a quarter. Multiply by the 4 boxes: about 160 visitors in total.

Buying accuracy with boxes

More boxes means each box’s luck matters less. The demo shows the typical error next to the guess as “typical ±”.

The ± error is typical, not a limit: about two counts in three land within it, and nearly all within three times it.

The challenge, solved

Redis, the in-memory database, has HyperLogLog built in with 16,384 boxes. Its hash is 64 bits instead of 32, so the first 14 digits pick the box (2¹⁴ = 16,384) and 50 are left for the run. So a score can reach 51. The 5 bits a box in the table hold only up to 31, which is plenty for the demo’s 32-bit hash but not here, so Redis gives each box 6 bits (up to 63).

16,384 boxes × 6 bits = 98,304 bits = 12,288 bytes: 12 KB. With 0.81% typical error, your 10 million visitors come out at around 10 million, give or take about 81,000. A billion visitors would still fit in the same 12 KB.

In Redis, PFADD adds an ID to a counter and PFCOUNT reads the count.

Many servers, no double counting

Your home page runs on 20 servers, and each keeps its own counter. Plenty of people hit two or more servers in a day, so adding up the 20 counts would count them more than once.

The same move turns daily counters into a weekly one: merge seven 12 KB counters and you have unique visitors for the week, without ever storing an ID.

People who came on both Monday and Tuesday are harder. You can estimate them as Monday + Tuesday − merged, but the errors of all three counts land on a much smaller answer, so it is often far off.

When to reach for it

Any “how many different” over a big stream: unique visitors, daily active users, distinct IPs hitting an API, especially when counts per page, day or server must merge later. SQL engines offer it as approx_distinct in Presto and APPROX_COUNT_DISTINCT in BigQuery.