HyperLogLog: Counting Uniques in 12 KB

In one line

HyperLogLog estimates how many distinct items you've seen, with about 0.81% standard error, in at most 12 KB per key, no matter whether you count a thousand or a billion. It can't tell you whether a specific item was seen.

0/6 · 0%

Think of it like this

Estimating how many different people visited a festival by noting, for each visitor, the longest run of heads they got when flipping a coin. Seeing someone with 20 heads in a row suggests you've met about a million people. HyperLogLog does this with hashes instead of coins, and averages thousands of such "records" to get a tight estimate.

Key ideas

01
Commands: PFADD key element... (returns 1 if the estimate changed), PFCOUNT key... (estimate; with several keys it counts the union on the fly), PFMERGE dest src... (union into a new HLL). The PF prefix honours Philippe Flajolet, who invented the algorithm.
02
How it works: each element is hashed (64 bits). The first 14 bits pick one of 16,384 registers; the rest are scanned for the position of the first 1-bit, and the register keeps the maximum seen. The harmonic mean of the registers, with bias corrections, estimates cardinality. 16,384 registers × 6 bits = 12 KB.
03
Small counts use a sparse encoding that's much smaller than 12 KB, converting to dense when it grows past hll-sparse-max-bytes (default 3,000 bytes). The standard error is 1.04/√16384 ≈ 0.81%, so a count of 1,000,000 is usually within about ±8,000.
04
What you can't do: check membership ("has user 42 visited?"), remove elements, or intersect exactly. Intersections can be estimated with inclusion–exclusion (|A∩B| = |A| + |B| − |A∪B|), but the error grows badly when the intersection is small relative to the sets.
05
HyperLogLogs are stored as strings, so they replicate, persist, and can be copied like any other value. Merging per-hour or per-shard HLLs is lossless, which is ideal for distributed counting.

Code & diagrams

unique-visitors.redisredis

127.0.0.1:6379> PFADD uv:2026-09-28 user:1 user:2 user:3 user:2
(integer) 1
127.0.0.1:6379> PFCOUNT uv:2026-09-28
(integer) 3
127.0.0.1:6379> PFADD uv:2026-09-27 user:2 user:4
(integer) 1
127.0.0.1:6379> PFCOUNT uv:2026-09-27 uv:2026-09-28     # union, on the fly
(integer) 4
127.0.0.1:6379> PFMERGE uv:week:39 uv:2026-09-27 uv:2026-09-28
OK
127.0.0.1:6379> MEMORY USAGE uv:2026-09-28
(integer) 104                                          # sparse encoding
# after ~10M elements:
127.0.0.1:6379> MEMORY USAGE uv:big
(integer) 14392                                        # dense: ~12 KB + overhead

hll-accuracy.pypython

import redis, uuid
r = redis.Redis()
r.delete("hll:test")
true_count = 1_000_000
pipe = r.pipeline(transaction=False)
for i in range(true_count):
    pipe.pfadd("hll:test", uuid.uuid4().hex)
    if i % 10_000 == 0:
        pipe.execute()
pipe.execute()
est = r.pfcount("hll:test")
print(est, f"error={abs(est - true_count) / true_count:.3%}")
# 1004281 error=0.428%

Interview problem

The problem

Unique visitors today

"How many unique visitors did our website have today?" Compare a set, a HyperLogLog and a bitmap, with the trade-offs for each.

You're given

50M unique visitors/day
Visitor IDs are UUIDs (cookies)
Also needed: weekly uniques, per-page uniques for 100K pages

The interviewer follows up

Can HyperLogLog tell you how many visitors came both Monday and Tuesday?

Explain it without notes

Why does HyperLogLog use a fixed 12 KB no matter how many elements you add?

Practice

Run hll-accuracy.py with 10K, 1M and 10M elements. How does the error behave?

Trade-offs

↔
HyperLogLog: fixed tiny memory and lossless merges, but approximate and no membership or deletion.
↔
Sets: exact, with membership and algebra, but memory grows linearly with members.

Done when you can

I can compare set, bitmap and HLL for unique counting and pick one with reasons.
I know HLL's error rate, memory and what it can't do.

Command Palette