HyperLogLog

Counting unique visitors sounds easy until the list is 100 million user IDs long. An exact set needs memory that grows with the number of distinct items. HyperLogLog (Flajolet and colleagues, 2007) counts distinct items in fixed memory, with a predictable error. Redis uses 12 KB per counter and is typically within about 1% of the true count.

The big idea: leading zeros

Hash every item to a random-looking 64-bit number. Then look at how many leading zeros the number has.

• Half of all hashes start with 1, so they have 0 leading zeros.
• A quarter start with 01, so they have 1 leading zero.
• One in 2^(k+1) hashes starts with exactly k zeros.

If the longest run of leading zeros you have seen is 20, you have probably seen about 2^20, or 1 million, distinct values. Duplicates do not change this. The same item always hashes to the same value, so repeats never create a longer run.

One lucky hash can ruin a single maximum, so HyperLogLog splits the stream into m buckets. It uses the first few bits of the hash to choose a bucket, keeps the largest run seen in each bucket, and combines the buckets with a harmonic mean, which resists outliers.

Walking through the numbers

Redis uses m = 16,384 buckets, each holding a 6-bit value.

memory         = 16,384 buckets × 6 bits = 98,304 bits = 12,288 bytes ≈ 12 KB
standard error = 1.04 / √16,384 = 1.04 / 128 ≈ 0.81%

Halving the error costs four times the memory. With 4,096 buckets (about 3 KB), the error is 1.04 / 64 ≈ 1.6%.

The standard error is one standard deviation. About 68% of estimates fall within ±0.81%, and about 95% fall within ±1.6%.

Code

This version uses 14 bits for the bucket index, so m = 16,384. Estimates for small counts use a correction that is left out here.

import hashlib, math

class HyperLogLog:
    def __init__(self, b: int = 14):
        self.b, self.m = b, 1 << b
        self.registers = [0] * self.m
        self.alpha = 0.7213 / (1 + 1.079 / self.m)   # corrects a known bias

    def add(self, item: str):
        x = int.from_bytes(hashlib.blake2b(item.encode(), digest_size=8).digest(), "big")
        j = x >> (64 - self.b)                        # first b bits pick a bucket
        w = x & ((1 << (64 - self.b)) - 1)            # the other 50 bits
        rank = (64 - self.b) - w.bit_length() + 1     # leading zeros + 1
        self.registers[j] = max(self.registers[j], rank)

    def count(self) -> float:
        return self.alpha * self.m ** 2 / sum(2.0 ** -r for r in self.registers)

h = HyperLogLog()
for i in range(1_000_000):
    h.add(f"id-{i}")
print(round(h.count()))

Output:

1007854

The true count is 1,000,000, so this estimate is about 0.8% high. That is within the expected error for this bucket count.

Merging is the real advantage

Two HyperLogLogs with the same m merge by taking the largest value in each bucket. The result is exactly the sketch you would get from the union of both streams.

You cannot add distinct counts. If Monday had 1 million unique users and Tuesday had 1 million, the two-day total is not 2 million if most people came both days. With HyperLogLog, store one sketch per day and merge any range.

exact:  50 million user IDs per day × ~16 bytes ≈ 800 MB raw, per day
HLL:    12 KB per day × 365 days ≈ 4.4 MB for a year, any date range answerable

Query engines use the same idea for approximate distinct counts. BigQuery's APPROX_COUNT_DISTINCT, and similar functions in Trino, Spark and ClickHouse, can be far cheaper than an exact COUNT(DISTINCT …) on a large table.

Intersections are harder. You can estimate |A ∩ B| = |A| + |B| − |A ∪ B|, but the error becomes large when the overlap is small compared with the sets.

Common mistakes

• Using it for billing or exact reporting. It is an estimate with a known error. Count exactly where precision is required.
• Subtracting or summing sketches to get new counts. Only merging (taking the max per bucket) is exact in the sense of the sketch.
• Estimating small overlaps. The error on an intersection dominates when the overlap is small.

Check yourself

1. Why does a duplicate item not raise the estimate? The same item always hashes to the same value, so its leading-zero run is the same each time. The maximum does not change.
2. Redis uses 16,384 buckets. What error do you get with 4,096 buckets? About 1.6%, which is 1.04 / √4,096. The error doubles when the buckets drop by a factor of four.

Key takeaways

• HyperLogLog estimates distinct counts from the longest run of leading zeros in hashed values.
• With 16,384 buckets (12 KB), the standard error is about 0.81%.
• Sketches merge by taking the maximum per bucket, so you can answer any date range from daily sketches.
• Use it for dashboards and trends, not for billing.

Further learning

Next, read count-min sketch to estimate how often each item appears, which is a different question from how many distinct items there are.