HyperLogLog explained: an interactive distinct-count simulator
HyperLogLog counts how many distinct items a stream contains, such as unique visitors, unique search queries or unique IPs, using a fixed, tiny amount of memory: 12 KB counts a billion distinct items to within about 1%. It cannot list the items or say whether one was seen; it only estimates how many there were. Two sketches can be merged into one that counts their union.
The playground feeds numbered visitors into a sketch. Change the number of registers and visitors, repeat visitors, or merge two days, and compare the estimate with the truth.
RegistersDistinct visitors
1,000,000 distinct visitors in 16,384 registers, 12 KB. The estimate is 1,002,474, +0.2% from the truth; the typical error at this size is ±0.81%, and it stays about the same from a thousand visitors to a billion. Storing every visitor ID exactly would take at least 8 MB.
The first 512 of 16,384 registers: longest run of zeros seen, plus oneError of the estimate as visitors are added
True distinct1,000,000visitors
Estimate1,002,474+0.2% from the truth
Sketch size12 KB16,384 registers of 6 bits
Exact set8 MB8 bytes per ID, at the very least
±1.04/√m, the typical errorthis sketch’s error
How HyperLogLog works
Hash each item to a random-looking number. The same item always gives the same hash, so repeats change nothing.
Pick a register with the first p bits of the hash; there are m = 2p registers.
Count leading zeros in the rest of the hash, and keep the largest count seen, plus one, in that register.
Estimate: a run of k zeros turns up about once in 2k items, so each register guesses the count; the harmonic mean of all the guesses, scaled by m, is the estimate. For small counts, when many registers are still empty, counting the empty ones is more accurate, and the sketch switches to that.
One register alone would be a wild guess, like estimating how many coins were flipped from the longest run of heads. Many registers, each seeing a different slice of the items, average the luck out.
Accuracy and memory
The standard error is about 1.04/√m, and it does not depend on the count. Each register needs only 6 bits, since runs longer than 63 zeros never happen, so memory is tiny and fixed:
Registers
Memory
Typical error
16
12 bytes
±26%
256
192 bytes
±6.5%
1,024
768 bytes
±3.3%
4,096
3 KB
±1.6%
16,384
12 KB
±0.81%
In the playground, 16,384 registers estimate a million visitors as 1,002,474, 0.25% off, where an exact set of 64-bit IDs would need at least 8 MB. With 16 registers the same million comes out as 707,765, 29% low. The bump in the error curve at about two and a half times the number of registers is where the estimator switches from counting empty registers to the main formula, a known bias that the HyperLogLog++ variant corrects.
Merging sketches
Two sketches with the same number of registers merge by keeping the larger value in each register, and the result is exactly the sketch you would have built from both streams together. That is what makes HyperLogLog useful at scale: count per server, per shard, per hour or per day, then merge for any combination, without ever storing or shipping the raw IDs. Adding counts would double-count people who appear in both; merging does not. The one thing sketches cannot do well is subtract or intersect: estimates of overlaps computed by inclusion and exclusion are noisy.
HyperLogLog in Redis
# one sketch per page per day; each is at most 12 KB
PFADD visitors:2026-10-23:/pricing user:81 user:4410 user:81 # repeats change nothing
PFCOUNT visitors:2026-10-23:/pricing # distinct visitors, ~0.81% error
# weekly uniques without double counting people who came back
PFMERGE visitors:week43:/pricing visitors:2026-10-19:/pricing visitors:2026-10-20:/pricing ...
PFCOUNT visitors:week43:/pricing
Redis uses 16,384 registers, a sparse encoding for small counts and a 12 KB dense one above that. BigQuery, Snowflake, Presto and Postgres extensions offer approximate distinct counts built on the same algorithm, often the HyperLogLog++ variant from Google, which corrects the estimate’s bias at small and medium counts.
In a system design interview
When asked for unique counts at scale, say why exact is not worth it: “Unique viewers per video per day would need a set of user IDs per video, gigabytes a day. We keep a HyperLogLog per video per day in Redis, 12 KB each, with under 1% error, and merge days for weekly and monthly uniques.” Expect the follow-ups: whether 1% error is acceptable for the product (billing usually needs exact counts), how to count uniques across shards, and what to do for frequency questions, where a count-min sketch fits instead.
A probabilistic data structure that estimates how many distinct items are in a stream or set, using a small fixed amount of memory. It hashes each item, uses part of the hash to choose a register, and records in that register the longest run of leading zeros seen; together the registers estimate the count, typically within about 1% using 12 KB.
How accurate is HyperLogLog?
Its standard error is about 1.04 divided by the square root of the number of registers, regardless of how many items are counted. With 16,384 registers, as in Redis, that is about 0.81%: a true count of a million usually comes out within 8,000 or so. Fewer registers use less memory and give larger errors.
How much memory does HyperLogLog use?
A fixed amount set by the number of registers, each needing 6 bits. 16,384 registers take 12 KB whether the stream has a thousand or a billion distinct items. An exact set of a billion 64-bit IDs would need at least 8 GB. Implementations also use a sparse encoding while the count is small.
Can HyperLogLog sketches be merged?
Yes. Two sketches with the same number of registers merge by taking the larger value in each register, which gives exactly the sketch of the combined stream. That lets you count uniques per shard, server or day and combine them for any union, counting someone who appears in both only once.
What is the difference between HyperLogLog and a Bloom filter?
A Bloom filter answers whether an item has been seen, with possible false positives, and grows with the number of items. HyperLogLog answers how many distinct items there were, in fixed memory, but cannot answer whether a particular item was seen. They are often used together: one for membership, one for cardinality.
How do you count unique visitors at scale?
Keep a HyperLogLog per page or product per time bucket, for example per day, add each visitor ID to it, and read the estimate. Merge daily sketches for weekly and monthly uniques. Redis provides PFADD, PFCOUNT and PFMERGE, and analytics databases provide approximate distinct-count functions built on HyperLogLog.
When should you not use HyperLogLog?
When the count must be exact, such as for billing or financial reporting; when you need to know which items were seen, or how often each was seen, which a count-min sketch or exact counters answer; and when you need intersections of sets, which HyperLogLog can only estimate with large errors.