# HyperLogLog

> Count distinct users in 12 KB with about 1% error, and merge counts across servers.

Concept · Data structures for scale · https://levelcode.org/concepts/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.

```text
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](https://levelcode.org/concepts/bloom-filters)).
- 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](https://levelcode.org/concepts/count-min-sketch).