The first time someone asks you to count unique users, the solution is almost embarrassingly obvious.
ts1const users = new Set<string>(); 2 3for (const event of events) { 4 users.add(event.userId); 5} 6 7console.log(users.size);
Done.
For a small system, this is completely fine. If your site gets 50,000 users a day, nobody needs to be clever. Put the IDs in a set, ask Redis for SCARD, and call it a day.
The interesting version of the problem starts when the number is not 50,000. It's:
4,000,000,000 unique users
Now the question changes.
You are no longer asking, "How do I count unique users?" You're asking, "How much information do I actually need to keep in order to estimate how many unique users I've seen?"
Those are very different problems.
HyperLogLog exists because the answer to the second one is surprisingly small:
4 billion uniques ↓ ~12 KB
Not 12 GB. Not a distributed set containing billions of IDs. About 12 KB of state.
The catch is that you stop asking for the exact answer.
The Obvious Design Gets Expensive Quickly
Say your event stream looks like this:
json1{ 2 "user_id": "usr_928341" 3}
And product wants:
http1GET /uniques?day=2026-08-20
The naive backend design is:
Event ↓ Redis Set ↓ SADD uniques:2026-08-20 user_123 SADD uniques:2026-08-20 user_456 SADD uniques:2026-08-20 user_123 ↓ SCARD
Redis removes duplicates for you. Nice API. Exact answer.
But to answer "How many different users did I see?", you're keeping the identity of every user you have ever seen. That's much more information than the question asks for.
If there are four billion distinct users and each identifier takes even a handful of bytes, you're already talking about tens of gigabytes before accounting for Redis and object overhead. And when the query arrives, you throw all of that identity information away and return one integer:
3,981,274,221
HyperLogLog starts from that observation: maybe we don't need to remember who showed up. Maybe we only need enough evidence to estimate how many different people showed up.
First, Throw the User ID Away
This is the part that feels wrong the first time you build one.
An event arrives:
user_928341
Hash it with something like xxhash64(user_id) and imagine that it gives us 64 random-looking bits:
101101001001001011000010000000...
From this point onward, we don't care about user_928341. The original ID can be discarded. Nothing in the HyperLogLog needs to store it.
user_id ↓ 64-bit hash ↓ small update ↓ user_id forgotten
Duplicate detection isn't happening by remembering previous IDs. There is no giant set hiding somewhere. There is just a tiny statistical sketch.
That is the first important mental shift: HyperLogLog doesn't compress a giant set. It avoids creating the giant set in the first place.
Random Bits Can Tell Us How Many Users Exist
Suppose I flip a fair coin. Getting H isn't interesting; its probability is 1 / 2. Getting HH has probability 1 / 4. Getting HHHHHHHHHH has probability 1 / 1024.
If someone tells you, "I just observed 20 heads in a row," you'd reasonably assume they probably flipped the coin quite a lot. One extremely unlikely observation is evidence that there were many attempts.
HyperLogLog uses basically that idea, except with hash bits. Instead of counting heads, we look for leading zeroes:
1... rank = 1 01... rank = 2 001... rank = 3 0001... rank = 4 00001... rank = 5
Seeing one leading zero happens frequently. Seeing twenty leading zeroes is much rarer. So if, somewhere in our stream, we observe a hash with a very long run of zeroes, that tells us we probably processed a lot of distinct values.
If the same user appears 5,000 times, they hash to the same bits 5,000 times. The sketch doesn't keep growing because of repeated traffic from the same person.
One Register Isn't Enough
You could keep one number:
ts1const hash = hash64(userId); 2const rank = leadingZeros(hash) + 1; 3maxLeadingZeros = Math.max(maxLeadingZeros, rank);
If the largest rank you've seen is large, you've probably seen lots of unique values. The problem is variance: one unusually lucky hash can throw the estimate around badly.
So instead of keeping one observation, HyperLogLog keeps thousands of small independent observations. A common design uses 16,384 registers because 16,384 = 2^14, which makes splitting the hash convenient.
Split the Hash
Take our 64-bit hash:
xxxxxxxxxxxxxx | xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 14 bits remaining bits
The first 14 bits choose a register:
ts1idx = top14Bits(hash); 2// idx ∈ [0, 16383]
The remaining bits determine the rank:
ts1rank = leadingZeros(remainingBits) + 1;
Every event now produces only two useful values, something like (8231, 7). Then we update:
ts1registers[idx] = Math.max(registers[idx], rank);
That's basically the entire write path.
The Register Remembers the Weirdest Thing It Has Seen
Suppose register 42 sees ranks 2, 3, 2, 6, 1, and 4. It ends up storing only:
6
It doesn't know which users produced those ranks, how many events arrived, or when they arrived. It only knows that the rarest hash pattern it has observed had rank 6.
Repeat that across 16,384 registers and you get a statistical fingerprint of the stream's cardinality. The values are tiny, which is where the memory saving comes from.
Where the 12 KB Comes From
We have 16,384 registers. Each register needs around 6 bits:
16,384 × 6 = 98,304 bits 98,304 / 8 = 12,288 bytes ≈ 12 KB
Whether your stream has 10,000 unique users or 4,000,000,000 unique users, the sketch doesn't allocate memory per user. Its state remains approximately 12 KB.
Exact Set 10 users → more memory 1M users → much more memory 4B users → good luck HyperLogLog 10 users → ~12 KB 1M users → ~12 KB 4B users → ~12 KB
You're buying bounded memory by accepting an approximate answer.
Getting the Count Back Out
The registers aren't the final answer. You can't sum them and call the result unique users. Each register gives an independent clue about cardinality, and HyperLogLog combines those clues using a harmonic-mean-based estimator with correction factors for statistical bias.
Conceptually:
registers [17, 20, 18, 16, 19, 22, ...] ↓ combine statistical evidence ↓ estimated cardinality ↓ 3,982,114,000 uniques
You don't need to memorize the estimator equation to understand the system. The architectural property matters much more: writes reduce user IDs into tiny register updates, and reads derive an estimate from those registers. The massive event history never needs to be replayed for normal queries.
The Write Path Is Almost Stupidly Cheap
The hot path should look roughly like this:
Event Stream | v hash(user_id) | v split hash | +---- idx | +---- rank | v register[idx] = max(register[idx], rank)
No database lookup. No SELECT EXISTS(...). No distributed deduplication table. No growing set. Just hash, bit operations, and max.
That's a very nice property when this code sits in the path of millions of events.
Distributed Counting Is Where This Gets Really Useful
Suppose the stream is split across several shards. With an exact set, you can't simply add the counts because the same user can appear on multiple shards. You need some kind of global deduplication.
HyperLogLog sketches have a nicer property: they can be merged register by register.
Shard A register[500] = 7 Shard B register[500] = 11 Shard C register[500] = 9 merged register[500] = max(7, 11, 9) = 11
Do that for every register:
ts1merged[i] = Math.max(shardA[i], shardB[i], shardC[i]);
The result behaves like a sketch that had observed the union of all those streams. There is no giant cross-shard exchange of user IDs; each shard sends a tiny sketch.
Conceptually, a Redis-backed design could use keys like uniq:{day}:{shard}, add IDs with PFADD, and query a sketch with PFCOUNT. For multiple sketches, merge them and estimate the union.
Think Carefully About the Key
You probably don't want one eternal sketch called uniques. Encode the dimensions you intend to query:
uniq:2026-08-20:0 uniq:2026-08-20:1 uniq:2026-08-20:2
Now daily uniques are straightforward. If your product later wants daily active users, weekly active users, unique viewers per video, unique users per country, and unique devices per campaign, think about those dimensions before creating millions of arbitrary sketches.
Approximate data structures save memory per sketch. They don't save you from bad cardinality in your keyspace. That's a different problem.
Don't Put a Network Call in Front of Every Event
If you receive 500,000 events per second and every event becomes one synchronous Redis call, you've solved memory and created a different bottleneck.
The sketch operation is cheap. The network round trip may not be. Depending on the workload, you'd think about pipelining, local buffering, batching, partitioning, and asynchronous writes.
The algorithm may be O(1). Your infrastructure still exists. In production, latency is often hiding between machines rather than inside the function.
What Do We Lose?
A lot. Once an ID has been reduced into the sketch, you cannot ask whether user_123 was present. You can't list the users. You can't delete one particular user and perfectly reconstruct the previous state.
You also shouldn't use the structure as the source of truth for authentication, billing, entitlements, or anything where exact membership matters.
HyperLogLog answers one question: approximately how many distinct values did I observe? It answers that question efficiently because it refuses to answer almost everything else.
Approximate Doesn't Mean Sloppy
You're making an explicit engineering trade:
exact answer + memory proportional to cardinality versus small bounded memory + mathematically controlled estimation error
If a dashboard says DAU: 87,413,921, many products don't care whether the exact number was 87,413,921 or 87,620,104. The growth graph looks the same, the capacity decision looks the same, and the experiment conclusion probably looks the same.
But if you're deciding whether to charge a customer for exactly 87,413,921 events, use an exact system. The workload decides whether approximation is acceptable, not the cleverness of the algorithm.
The Abstraction Is a Sketch
HyperLogLog belongs to a broader family of structures usually called sketches. Their philosophy is:
huge stream ↓ tiny summary ↓ answer one specific class of questions
Instead of retaining the full dataset, you retain just enough statistical information for the query you care about. A sketch is not the original picture, but it preserves the parts you decided mattered. For HyperLogLog, the part that matters is cardinality.
Build the Dumb Version Yourself
Don't start with Redis. Build the small version first:
ts1const REGISTERS = 1 << 14; 2const registers = new Uint8Array(REGISTERS); 3 4for (const userId of userIds) { 5 const hash = hash64(userId); 6 const idx = top14Bits(hash); 7 const remaining = remaining50Bits(hash); 8 const rank = leadingZeros(remaining) + 1; 9 10 registers[idx] = Math.max(registers[idx], rank); 11}
Then implement the estimator, create two sketches, put overlapping users into them, and merge them register by register:
ts1function merge(a: Uint8Array, b: Uint8Array) { 2 const output = new Uint8Array(REGISTERS); 3 4 for (let i = 0; i < REGISTERS; i++) { 5 output[i] = Math.max(a[i], b[i]); 6 } 7 8 return output; 9}
Test it with 10K, 100K, 1M, and 10M uniques. Comparing Set.size with the estimate makes the idea click much faster than reading the equation.
Then Break It
Send 10 million events with only 100 unique users, then send 10 million unique users. The number of events is identical, but the cardinality is completely different. Your sketch should reflect that.
Distribute users over ten shards and merge sketches in different orders:
merge(A, B) merge(B, A) merge(merge(A, B), C) merge(A, merge(B, C))
You should arrive at the same register state because max has exactly the properties you want for distributed aggregation. That means retries, fan-in trees, and different merge orders become much easier to reason about.
The Systems Lesson Hiding Underneath HyperLogLog
The impressive sentence is 4 billion uniques in ~12 KB. But the more useful lesson is broader.
We usually begin by storing objects because objects are what arrive: user IDs, user IDs, user IDs. Then somebody asks what queries the system actually needs to support. Sometimes you realize the full objects are unnecessary. The exact IDs were implementation baggage. The actual requirement was only cardinality.
Once you design around the question instead of the incoming data, a completely different architecture becomes possible:
Need unique count ↓ Hash every user ↓ Keep tiny statistical evidence ↓ Estimate cardinality
HyperLogLog doesn't fit four billion users into 12 KB. It realizes that to answer the question we asked, we never needed to keep four billion users in the first place.
