The Cardinality Problem
Counting the number of distinct elements in a stream — called cardinality estimation — is deceptively hard. To know if a visitor is truly new, you must remember every visitor you have ever seen. For a site with 1 billion daily visitors, an exact HashSet approach requires gigabytes of memory just for this one metric.
HyperLogLog (HLL) is an algorithm that estimates cardinality using roughly 1.5 KB of memory, regardless of whether the true count is 1 million or 1 trillion, with a typical error rate of about 2%.
The Intuition: Coin Flips and Rare Events
Consider flipping a fair coin until you get heads. The probability of needing exactly k flips is (1/2)^k. Getting 10 tails in a row before a head has probability 1 in 1,024. Getting 20 tails in a row has probability 1 in 1,048,576.
Now imagine you flip the coin many times and record the longest run of tails you observed before a head. If I tell you the longest run was 3, I can guess you flipped the coin maybe 10–20 times. If you tell me the longest run was 20, I know you must have flipped it millions of times — because that outcome is so rare that you needed a huge number of trials to encounter it.
HyperLogLog applies this logic to hash values. Every incoming item is hashed to a uniformly distributed binary number. HLL counts the number of leading zeros in the hash (equivalent to counting tails before a head). The more distinct items you hash, the higher the probability of eventually seeing a hash with many leading zeros. By tracking the maximum number of leading zeros seen across all items, HLL estimates the total cardinality as 2^(max_leading_zeros).
Reducing Error with Buckets
A single maximum-leading-zeros tracker has high variance — one unlucky hash could wildly skew the estimate. HLL reduces this by using m independent sub-estimators called registers (typically 2,048 or 4,096 of them). The first few bits of each hash value determine which register to update; the remaining bits are used for the leading-zero count. The final estimate is computed as the harmonic mean of 2^(register_value) across all registers. The harmonic mean is specifically chosen because it is robust to outliers — a single register with an unusually large value does not dominate the result.
Real-World Usage
Redis has built-in HyperLogLog support via the PFADD and PFCOUNT commands. A single HLL key in Redis uses at most 12 KB of memory and can count up to 2^64 unique elements with a standard error of 0.81%. This is how Redis-backed analytics systems count unique daily active users without storing individual user IDs.
A common interview question: "How does Redis count unique visitors without storing every user ID?" The answer is HyperLogLog. Be ready to explain the trade-off: PFCOUNT returns an estimate with ~0.81% standard error, not an exact count. If the interviewer asks "when would you not use HLL?", the answer is: when you need exact counts (billing, compliance, deduplication of financial records), or when you need to enumerate the actual distinct elements (HLL only stores a sketch — you cannot retrieve the original items from it).