HyperLogLog for Unique Counting
Counting the exact number of unique visitors (cardinality) over a month requires storing every single user ID in a Set. At Facebook or Google scale, this demands Terabytes of memory just to track unique counts.
The Magic of HyperLogLog (HLL)
HyperLogLog is a probabilistic data structure that estimates cardinality with extreme memory efficiency. Instead of storing IDs, it hashes the ID and looks at the binary representation of the hash. It tracks the maximum number of leading zeros seen in any hash. If you see a hash with 10 leading zeros, that hints you have processed on the order of 2^10 unique items. A single such observation is a very noisy estimate (one lucky hash can be off by orders of magnitude), so the real algorithm splits hashes across many registers and averages them, as described below.
Memory vs Accuracy Trade-off
Standard HLL uses one well-distributed hash per identity. The first p bits select one of m = 2^p registers; the remaining bits supply a rank based on the first set bit. Each register retains its maximum observed rank, and the estimator combines all registers with bias corrections. More registers use more memory and reduce standard error. Redis's implementation uses about 12 KB in its dense representation and targets roughly 0.81% standard error, but serialized format and sparse behavior are implementation-specific.
If you don't need exact accounting (e.g., displaying "1.2M Unique Views" on a dashboard), HLL is the perfect tool, replacing Terabytes of RAM with Kilobytes.
PFADD unique_visitors_today "user_123"
PFCOUNT unique_visitors_today // Returns estimated countWorked example: precision vs memory
| Precision p | Registers m = 2 to the power p | Memory at 6 bits per register | Standard error, 1.04 divided by sqrt m | 1 sigma at 100 million uniques |
|---|---|---|---|---|
| 10 | 1,024 | 768 bytes | 3.25 percent | plus or minus 3.25 million |
| 12 | 4,096 | 3 KB | 1.63 percent | plus or minus 1.63 million |
| 14, Redis default | 16,384 | 12 KB | 0.81 percent | plus or minus 812,000 |
| 16 | 65,536 | 48 KB | 0.41 percent | plus or minus 406,000 |
Compare exact counting: 100 million 8-byte user IDs in a hash set is at least 800 MB, and several GB with typical hash table overhead, per metric per day. HLL at 12 KB is roughly five orders of magnitude smaller.
Walking one item through
With p = 14, hash "user_123" to 64 bits. The first 14 bits, say 00000101101001, select register 361. In the remaining 50 bits, the first 1 appears at position 4, so the rank is 4. If register 361 currently holds 2, it becomes 4; if it holds 6, it stays 6. Re-adding "user_123" produces the same hash and changes nothing, which is why HLL naturally ignores duplicates.
Practical refinements
- Small-range correction: when many registers are still zero, the estimator switches to linear counting, which is far more accurate for small cardinalities.
- HyperLogLog++ (Google, 2013): 64-bit hashes, empirical bias correction, and a sparse representation for small sets. Redis similarly uses a sparse encoding until the set grows.
- Where it is used: Redis PFADD and PFCOUNT, BigQuery APPROX_COUNT_DISTINCT and HLL_COUNT functions, Presto and Trino approx_distinct, Druid and Pinot HLL aggregators.
Common interview uses
| Question | Why HLL fits |
|---|---|
| Daily active users per country | One 12 KB sketch per country per day; merge for weekly or monthly |
| Unique visitors per page | Millions of pages x 12 KB can still be large; use lower precision or sparse encoding for small pages |
| Distinct IPs hitting an endpoint, for abuse detection | Fixed memory per endpoint regardless of attack size |
| Distinct search queries per day | Accurate to about 1 percent without storing queries |
When the interviewer asks for exact counts, switch to a keyed set in a database or a batch COUNT DISTINCT; when they ask for intersections, mention Theta sketches.