HyperLogLog

Counting distinct items exactly — unique visitors, unique search terms, distinct IPs — requires remembering every item seen, which for hundreds of millions of items means gigabytes of memory per counter. HyperLogLog (HLL) estimates the distinct count in a fixed, tiny amount of memory.

#The intuition

Hash each item to a random-looking bit string. In uniformly random hashes, a hash starting with k zero bits appears about once in every 2ᵏ items. So the longest run of leading zeros seen hints at how many distinct items there were. One such estimate is noisy; HLL splits hashes across many registers (using the first bits to choose a register), tracks the maximum run in each, and combines them with a harmonic mean and bias corrections.

#In practice

• Redis's HLL uses about 12 KB per counter with a standard error of about 0.81%, for counts up to billions.
• Adding the same item again doesn't change the estimate, so it's naturally idempotent.
• Sketches merge: the union of two HLLs is the register-wise maximum. Count per server or per hour, then merge for totals across servers or days — something exact sets can't do cheaply.

PFADD visitors:2026-10-27 user:42 user:7 user:42
PFCOUNT visitors:2026-10-27                    → 2
PFMERGE visitors:week visitors:2026-10-21 … visitors:2026-10-27
PFCOUNT visitors:week

#Limits

• Only cardinality: you can't list the items or ask whether a specific one was seen (that's a Bloom filter).
• Intersections ("visited both pages") can be estimated via inclusion–exclusion, but error grows quickly.
• Approximate by design: fine for dashboards and analytics, not for billing.

Analytics databases offer the same idea as functions such as approx_count_distinct. See also count-min sketch.