HyperLogLog: Approximate Distinct Counts at Massive Scale

HyperLogLog is a probabilistic algorithm that can count the number of distinct elements in a dataset of any size using only about 12KB of memory, with a standard error of approximately 0.81%. Instead of storing every unique element (which would require memory proportional to the dataset), it hashes each element and observes patterns in the binary representation to estimate cardinality. Redis, BigQuery, Presto, and most analytics platforms use HyperLogLog to power features like unique visitor counts and distinct value estimation at massive scale.

Why This Matters

Counting distinct elements exactly requires storing every unique element, which for billion-element datasets means gigabytes of memory. HyperLogLog solves this with a mathematical trick that uses about 12KB regardless of cardinality — a 100,000x memory reduction. This matters in real systems because counting unique visitors, distinct queries, unique devices, or cardinality estimation for query planning are everyday operations that would be prohibitively expensive without probabilistic approaches. HyperLogLog is also mergeable — you can combine counters from different time periods or servers, making it perfect for distributed analytics.

The Building Blocks

• Hash Function: Every element is hashed to a uniformly distributed binary string. The hash quality ensures that patterns in the binary representation reflect true cardinality, not data distribution.
• Register Array: The hash is split into a prefix (to select one of m registers) and a suffix (to count leading zeros). Each register stores the maximum leading zeros observed, serving as a local cardinality estimator.
• Harmonic Mean: The cardinality estimate combines all registers using a harmonic mean, which reduces the impact of outlier registers that observed unusually long or short zero runs.
• Bias Correction: For small cardinalities, HyperLogLog applies bias correction factors and falls back to linear counting to maintain accuracy across the full range from zero to billions.
• Mergeability: Two HyperLogLog structures can be merged by taking the max of each corresponding register — enabling distributed counting where each server maintains a local sketch and a coordinator merges them.

Under the Hood

The core insight of HyperLogLog is statistical: if you flip a fair coin repeatedly, the probability of seeing k consecutive heads decreases exponentially (1/2^k). So observing a long run of heads implies many flips. HyperLogLog applies this logic to hashed values — a hash with many leading zeros is like a long heads streak, implying many distinct elements were hashed.

Specifically, each element is hashed to a binary string. The first p bits select one of m = 2^p registers (typically p = 14, giving 16,384 registers). The remaining bits are examined for the position of the first 1-bit (equivalently, the count of leading zeros plus one). Each register stores the maximum such value it has ever seen. The raw estimate combines all registers using a harmonic mean: E = alpha_m * m^2 / sum(2^(-M[j])), where M[j] is the value in register j and alpha_m is a bias correction constant.

For small cardinalities (below 5/2 * m), many registers will be zero. HyperLogLog detects this and switches to linear counting, which counts the number of empty registers to estimate cardinality more accurately in this range. For very large cardinalities approaching 2^32, a correction for hash collisions is applied. The standard HyperLogLog with 16,384 registers (12KB total) achieves a standard error of 1.04/sqrt(m) ≈ 0.81%. Google's HyperLogLog++ improves the small-range bias correction and extends to 64-bit hashes, eliminating the large-range correction.

How Companies Actually Do This

Redis The PFADD and PFCOUNT commands implement HyperLogLog for use cases like counting unique page visitors — each key uses exactly 12KB of memory whether tracking 10 or 10 billion distinct values, and PFMERGE combines counters across time windows.

Google BigQuery Uses HyperLogLog++ (Google's enhanced version) for the APPROX_COUNT_DISTINCT function, enabling approximate unique counts across petabyte-scale tables orders of magnitude faster than exact COUNT(DISTINCT).

Amazon Redshift Implements HyperLogLog for approximate distinct counting in analytics queries, allowing data analysts to get fast cardinality estimates on massive tables without the memory cost of exact counting.

Common Pitfalls

1. Expecting exact counts — HyperLogLog gives an estimate with ~0.81% standard error; for a true cardinality of 1 million, the result will typically be between 991,900 and 1,008,100
2. Not merging correctly — HyperLogLog sketches must be merged by taking the register-wise maximum, not by adding counts; merging incorrectly produces wildly inaccurate results
3. Using too few registers — reducing the register count below 1,024 saves tiny amounts of memory but dramatically increases error rate; the standard 16,384 registers (12KB) is almost always the right choice

Interview Questions Worth Practicing

1. Explain the intuition behind HyperLogLog — why does observing leading zeros in hash values help estimate cardinality?
2. How would you count unique daily visitors across 100 web servers using HyperLogLog without centralized logging?
3. Compare HyperLogLog with exact counting and Bloom filters — what are the tradeoffs and when would you use each?

The Tradeoffs

• Accuracy vs Memory: HyperLogLog uses only 12KB regardless of cardinality but accepts ~0.81% standard error — exact counting uses memory proportional to cardinality but is perfectly accurate
• Speed vs Precision: HyperLogLog inserts and counts in O(1) time, but cannot be made more precise without starting over with more registers
• Mergeability vs Information: HyperLogLog can be merged across distributed systems but only answers 'how many distinct' — it cannot list the elements or check membership like a Bloom filter

How to Explain This in an Interview

Here is how I would explain HyperLogLog in a system design interview:

Start with the problem: counting exact distinct elements in a billion-element stream requires gigabytes of memory. HyperLogLog solves this in 12KB. Explain the intuition with a coin flip analogy: if someone tells you the longest streak of heads they saw was 20, you'd estimate they flipped the coin about 2^20 (a million) times — long streaks are unlikely without many flips. HyperLogLog applies this to hash values, using the longest run of leading zeros as a cardinality signal. To reduce variance, it splits elements into 16,384 registers using the hash prefix, each tracking its own maximum zero run, then combines estimates using a harmonic mean. The result has ~0.81% standard error. Mention that HyperLogLog counters are mergeable — each distributed server can maintain its own sketch and a central system takes the register-wise max, making it perfect for distributed analytics. Redis's PFADD/PFCOUNT is the most common implementation.

Related Topics

• Bloom Filters
• Database Scaling
• Caching Strategies
• Database Types

Original DosiBridge notes for HyperLogLog: Approximate Distinct Counts at Massive Scale

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study HyperLogLog: Approximate Distinct Counts at Massive Scale is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Query Shape: For HyperLogLog: Approximate Distinct Counts at Massive Scale, decide the query shape before choosing tools; otherwise the design looks clean but fails when hyperloglog changes.
• Write Amplification: For HyperLogLog: Approximate Distinct Counts at Massive Scale, decide the write amplification before choosing tools; otherwise the design looks clean but fails when hyperloglog changes.
• Replication Lag: For HyperLogLog: Approximate Distinct Counts at Massive Scale, decide the replication lag before choosing tools; otherwise the design looks clean but fails when hyperloglog changes.
• Migration Safety: For HyperLogLog: Approximate Distinct Counts at Massive Scale, decide the migration safety before choosing tools; otherwise the design looks clean but fails when hyperloglog changes.
• Data Ownership: For HyperLogLog: Approximate Distinct Counts at Massive Scale, decide the data ownership before choosing tools; otherwise the design looks clean but fails when hyperloglog changes.

Production review question

If a team adopts HyperLogLog: Approximate Distinct Counts at Massive Scale, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track hyperloglog health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For HyperLogLog: Approximate Distinct Counts at Massive Scale, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.