You Don't Need to Store 4 Billion Users to Count Them

A product manager wants a number on a dashboard: unique users today. Not page views, which are one counter. Unique users, so someone who opens the app forty times counts once.

Start with the version that looks fine

Keep a set per day, add every user id that shows up, read its size. In #redis that's two commands:

@itsnas — TypeScript

Hide line numbersCopy code

async function track(userId: string) {
  await redis.sadd(`uniq:${today()}`, userId)
}
 
async function uniquesToday() {
  return redis.scard(`uniq:${today()}`)
}

main

Nas (@itsnas)

At 50,000 users a day this is the right answer, and you should stop reading. At scale it falls over on memory. Four billion 64-bit ids are 32 GB before any overhead, and a hash set's per-entry overhead multiplies that several times. Keep a set per day for a month and it's a cluster's worth of RAM.

All of that memory goes into remembering exactly who visited, so the set can answer "was user 81,442 here?" and "list everyone". The dashboard asks neither. It asks "how many?", and it would be happy with 3.97 billion instead of 3,971,204,118.

Hashes as evidence

The trick is to stop keeping ids and keep something about them instead. Run each id through a good 64-bit hash (like xxHash) and look at the bits. A good hash makes every bit look like a coin flip, so:

• half of all hashes start with 1
• a quarter start with 01
• one in eight starts with 001
• one in $2^{k+1}$ starts with exactly $k$ zeros and then a one

Now turn it around. If the longest run of leading zeros you've seen across the whole stream is 20, you've probably hashed somewhere around $2^{20}$, about a million, distinct values. It's like someone telling you their longest streak of tails was 20 in a row. A streak like that turns up about once in a million tries, so you don't know exactly how many times they flipped, but it wasn't ten.

Duplicates are free. User 81,442 hashes to the same bits every time, so seeing them a thousand times can't make the run any longer than seeing them once. That's the property that makes this a count of unique users, and it's why no id ever needs storing.

One guess is too noisy: registers

A single longest run is a terrible estimate. One lucky hash with 25 leading zeros after ten users, and your count says $2^{25}$, about 33 million. The fix is to make many small guesses and combine them.

HyperLogLog splits every hash in two. The first 14 bits pick one of $2^{14} = 16{,}384$ registers. The remaining 50 bits are where the leading zeros get counted. Each register keeps one small number: the largest rank (leading zeros plus one) it has ever been handed.

@itsnas — text

Hide line numbersCopy code

00000010110110 | 0001011010010111...
└ register 182 ┘ └ 3 zeros, then a 1: rank 4

main

Nas (@itsnas)

1. Index 0: 70
2. Index 1: 51
3. Index 2: 82
4. Index 3: 63
5. Index 4: 74
6. Index 5: 9 (6 → 9)5
7. Index 6: 56
8. Index 7: 67
9. Index 8: 88
10. Index 9: 79
11. Index 10: 610
12. Index 11: 1011
13. Index 12: 712
14. Index 13: 513
15. Index 14: 614
16. Index 15: 815

Each register sees about a 16,384th of the users, so one lucky hash now skews one guess in 16,384 instead of the whole answer. A rank can never exceed 51, which fits in 6 bits, so the whole sketch is:

From registers to a count

A register holding $M_j$ is a rough guess that register $j$ has seen about $2^{M_j}$ users. HyperLogLog combines all $m$ guesses with one formula:

Read it from the inside out:

• $2^{-M_j}$ is one over a register's guess. A register holding 7 contributes $1/128$; one holding 10 contributes $1/1024$.
• $m$ divided by the sum of those is the harmonic mean of the guesses: what a typical register has seen.
• The second $m$ scales that up to all $m$ registers, since each saw about $1/m$ of the users.
• $\alpha_m$ is a correction factor derived in the paper, because the raw guesses run high. It depends only on $m$: 0.673 for 16 registers, about 0.7213 for 16,384.

Now run it on the 16 registers from the diagram (with register 5 already raised to 9), grouped by value:

1. 1Harmonic mean of the guesses: $16 / 0.20215 \approx 79.1$
2. 2Scale up to all 16 registers: $79.1 \times 16 \approx 1{,}266$
3. 3Correct the bias: $1{,}266 \times 0.673 \approx 852$

So this sketch has seen about 852 distinct users. Notice that the small values do most of the work: the 5s and 6s make up three quarters of the sum, and the lone 10 barely registers.

That's the point of the harmonic mean: one outlier can't take over. Say register 3 (holding 6) gets a freakishly lucky hash with rank 30. Its term drops from $1/64$ to almost zero, the sum falls from 0.20215 to 0.18653, and the estimate rises from 852 to 924, about 8%. A plain average of the same guesses would jump from 198 to about 67 million, all because of one hash.

When the sketch is nearly empty

The formula assumes every register has seen something. Give it an empty sketch and every term is $2^0 = 1$, so the sum is $m$ and the estimate is $\alpha_m \cdot m$: about 11,800 users for a sketch that has seen nobody.

So when the estimate comes out below $2.5m$ (40,960 for 16,384 registers) and some registers are still empty, implementations switch to linear counting, which only looks at how many registers are still empty ($V$):

The empty sketch now comes out right: $V = m$, $\ln 1 = 0$, zero users. And if 12,000 of the 16,384 registers are still empty:

$$E = 16{,}384 \times \ln \frac{16{,}384}{12{,}000} = 16{,}384 \times 0.3114 \approx 5{,}102$$

Only 4,384 registers are filled, yet the estimate is 5,102 users. The difference is users who landed on a register someone else had already filled. Collisions like that start early, for the same reason as the birthday paradox, and the logarithm accounts for them.

The whole thing in code

@itsnas — TypeScript

Hide line numbersCopy code

const P = 14
const M = 1 << P // 16,384 registers
 
class HyperLogLog {
  registers = new Uint8Array(M)
 
  add(id: string) {
    const hash = hash64(id) // any good 64-bit hash, as a bigint
    const index = Number(hash >> 50n) // top 14 bits
    const rest = hash & ((1n << 50n) - 1n) // low 50 bits
    const rank = rest === 0n ? 51 : 51 - rest.toString(2).length
    if (rank > this.registers[index]) this.registers[index] = rank
  }
 
  count() {
    let sum = 0
    let empty = 0
    for (const r of this.registers) {
      sum += 2 ** -r
      if (r === 0) empty++
    }
    const alpha = 0.7213 / (1 + 1.079 / M)
    const estimate = (alpha * M * M) / sum
    if (estimate <= 2.5 * M && empty > 0)
      return M * Math.log(M / empty)
    return estimate
  }
 
  merge(other: HyperLogLog) {
    for (let i = 0; i < M; i++)
      this.registers[i] = Math.max(this.registers[i], other.registers[i])
  }
}

Show all 33 lines

main

Nas (@itsnas)

add is the split from the diagram, count is the two formulas above, and merge gets its own section below. This version spends a byte per register for readability (16 KB); packing them into 6 bits is what gets you to 12 KB. Either way, the size is fixed the moment the sketch is created. Ten users, a million, four billion: same 16,384 registers.

How wrong is it?

For 16,384 registers:

$$\sigma = \frac{1.04}{\sqrt{16{,}384}} = \frac{1.04}{128} \approx 0.0081 = 0.81\%$$

Roughly two counts in three land within one $\sigma$ of the truth, and nineteen in twenty within two (1.6%).

Be honest about what that means at the top end. At four billion users, $4{,}000{,}000{,}000 \times 0.0081 \approx 32.5$ million people, and the 1-in-20 bad day is off by 65 million. That's fine for a dashboard, a trend line, or deciding which region needs more servers. It isn't fine for anything you'd bill on or report to an auditor.

More registers buy accuracy slowly. Every 2 bits added to the register index quadruples $m$ and the memory, but $\sqrt{m}$ only doubles, so the error only halves:

14 bits (what Redis uses) is the usual sweet spot: under 1% error for less memory than a small image.

Merging: the part that changes architectures

Look at merge again. A register holds the longest run it has seen, so the register for the union of two streams is just the larger of the two. Merge two sketches register by register and you get exactly the sketch you'd have built from both streams together, with users who appear in both counted once. The only condition is that both sketches were built the same way: same hash function, same number of registers. Otherwise register 182 doesn't mean the same thing in both.

That has two consequences that a set can't match cheaply.

Shards don't ship ids. Each server keeps its own sketch of the users it served and sends 12 KB to a central place every minute. The central place takes the max of each register. No server ever sends a user id, and the cost of combining a hundred servers is a hundred 12 KB arrays, not a hundred lists of users.

Days roll up into weeks. You can't get weekly uniques by adding seven daily counts: someone who visits every day would be counted seven times. With a sketch per day, the weekly count is the merge of seven sketches, and the returning user is counted once. Redis does this for you:

@itsnas — TypeScript

Hide line numbersCopy code

async function track(userIds: string[]) {
  await redis.pfadd(`uniq:${today()}`, ...userIds)
}
 
async function uniquesThisWeek() {
  // PFCOUNT over several keys counts their union
  return redis.pfcount(...lastSevenDays().map(d => `uniq:${d}`))
}

main

Nas (@itsnas)

PFADD, PFCOUNT and PFMERGE are the HyperLogLog commands. Redis stores a sketch sparsely while its count is small and switches to the dense 12 KB form as it grows, so a quiet day's key costs less.

Put the time window in the key (uniq:2026-10-03), not one sketch that grows forever. A sketch can't forget anyone, so "uniques in the last 30 days" is only possible if you kept the days apart and merge the ones you want. Give the daily keys a TTL a bit longer than the longest window you report on.

What you give up

The sketch threw away identity on purpose, so every question that needs identity is gone:

• Membership. "Was this user here today?" can't be answered. If you need that, it's a set or a Bloom filter, which answers "have I seen this one?" the way HyperLogLog answers "how many have I seen?"
• Listing. There's nobody in there to list.
• Removal. You can't un-count a user, for a refund, a bot you caught later, or a deletion request. Filter before you add.
• Exactness. Billing, quotas, rate limits and anything with a legal number attached need exact counts. An estimate within 1% is still an estimate.

Set versus sketch

HyperLogLog doesn't squeeze four billion users into 12 KB. It never stores them at all, because the question was "how many", and answering that never needed to know who.

---