HyperLogLog & Cardinality Estimation

The question this answers

"How many distinct items have I seen?" — across a billion-event stream, in a few kilobytes, with a known error margin. An exact answer needs a hash set sized to the true cardinality; at "unique visitors per day" scale that's gigabytes for one counter. HyperLogLog answers it in ~12 KB at ~0.8% standard error, regardless of whether the true count is a thousand or a trillion.

The intuition in one step

Hash every item; the probability a random hash starts with exactly k leading zero bits is 1/2^k, so seeing a hash with k leading zeros suggests roughly 2^k distinct items have been hashed. A single register tracking the max leading-zero count seen is far too noisy to trust alone — HyperLogLog splits items across m buckets (by a few hash bits), tracks one register per bucket, and combines all m estimates with a bias-corrected harmonic mean. Averaging over m independent noisy samples is what drives the standard error down to ≈1.04/√m (about 0.8% at m = 16384).

Why it merges for free

An item's bucket is a deterministic function of its hash, so two sketches built over disjoint (or overlapping) data merge by taking the element-wise max of their registers — the result is identical to building one sketch over the union from scratch. An exact count doesn't offer this cheaply: merging two hash sets costs O(size of the smaller) and the result still needs O(n) space.

	HyperLogLog	Exact hash set
Space	O(m), fixed (~12 KB) regardless of cardinality	O(n), proportional to true count
Merge two sketches	O(m), exact result	O(n), still O(n) space
Accuracy	~0.8% standard error	Exact
Lists members?	No — count only	Yes

Where this lives in Redis

Redis ships HyperLogLog as a first-class type — PFADD, PFCOUNT, PFMERGE — specifically because "approximate unique count, bounded memory" is common enough to deserve a dedicated primitive. This is the mechanism behind "unique visitors today" dashboards at scale: Presto/Trino and BigQuery's APPROX_COUNT_DISTINCT and Elasticsearch's cardinality aggregation all use HyperLogLog or a close variant, for the same reason — a number a dashboard rounds to the nearest thousand anyway doesn't justify gigabytes of exact storage.

Design-interview framing: "each shard/machine/time-window keeps its own sketch independently, merge later via element-wise max" is the answer that shows you understand why HyperLogLog is designed the way it is — mergeability without re-scanning raw data is the feature, not an afterthought.

Common mistake

Confusing this with a Bloom filter — they answer different questions. Bloom filters answer "have I seen this specific item" (membership); HyperLogLog answers "how many distinct items, in total" (cardinality). Neither substitutes for the other.

Not covered here

The bucket/register mechanics, the leading-zero estimator derivation, and hands-on practice — see the DSA roadmap's Hash Table Internals & the Birthday Paradox subtopic for the underlying hashing fundamentals this builds on. Bloom filters (the membership-testing cousin) are covered in Storage Internals.

Where this goes next

KV, Redis, DynamoDB, Graph & Time-Series covers the rest of Redis's data model and persistence — HyperLogLog is one specialized type among several.