HyperLogLog
Estimates cardinality (unique count) in fixed memory — billions of unique visitors with ~1% error.
Interview tip Lead with a 30-second definition, then one real system example and name 2–3 designs where HyperLogLog is non-negotiable.
① What it is (30 seconds)
Estimates cardinality (unique count) in fixed memory — billions of unique visitors with ~1% error.
② How it works in system design
Hash values into registers; estimate unique count from bit patterns. Redis PFADD/PFCOUNT. Mergeable across nodes for distributed unique counts.
Typical placement
Client→Edge / Gateway→HyperLogLog→Services→Data stores
③ Concrete system design example
Scenario: Unique daily viewers per video: HyperLogLog per video_id instead of storing every viewer_id — 12KB per video vs GB of sets.
④ Important interview Q&A
| Question | Answer |
|---|---|
| HLL vs exact set? | HLL approximate; exact set accurate but memory explodes at scale. |
| Merge HLL? | Union of sketches estimates unique across shards — global UV from regional counts. |
| vs Bloom filter? | Bloom membership test; HLL cardinality estimate — different questions. |
⑤ Seen in these system designs
- Shared Counter — unique viewers
- YouTube — view metrics
- Real-time Analytics — UV estimates
In interviews, after explaining the concept, say: "This shows up directly in …" and link two designs.
⑥ Revision checklist
- Approximate cardinality
- Fixed memory
- PFMERGE across shards
- Error ~1-2%