Counting at scale: probabilistic structures
Exact answers cost memory linear in the data; a whole family of structures trades a tunable error for constant space.
“How many unique visitors this month?” Exactly answered, that question costs a set with a hundred million members. Answered within 1%, it costs twelve kilobytes. That trade — a tunable error for orders of magnitude of memory — is a whole family of structures, and at scale it is rarely optional: the exact answer is often the one you cannot afford.
Bloom filters — “definitely not” in bits
A Bloom filter answers set membership with one asymmetry: no is certain, yes is probable. Mechanically: a bit array plus k hash functions; adding sets k bits, querying checks them — any zero means definitely absent; all ones means present or collision. False positives, never false negatives — and that asymmetry is exactly shaped for “skip the expensive lookup”: the LSM engine from the storage chapter consults one per SSTable (definitely-not → skip the file), caches use them to dodge penetration lookups, crawlers to skip seen URLs. Sizing is a formula, not folklore — ~10 bits and 7 hashes per element gives ~1% false positives — and the classic limitation (no deletes; a bit may be shared) is what counting and cuckoo variants exist to fix.
The counting family
| Structure | Question | Cost / error | Lives in |
|---|---|---|---|
| HyperLogLog | how many distinct? | ~12 KB for ~0.8% at any cardinality; mergeable across shards | uniques, cardinality alerts, COUNT DISTINCT approximations |
| Count–min sketch | how often has X appeared? | KBs; overestimates only, tunable | heavy hitters, trending, hot-key detection |
| Reservoir sample | a fair sample of a stream | exactly k items, uniform, single pass | debugging firehoses, sampled analytics |
| Top-K (sketch + heap) | the current leaders | bounded memory over unbounded streams | leaderboards, trending topics |
HyperLogLog’s trick deserves one sentence of intuition: hash every element and track the longest run of leading zeros seen — a run of 20 zeros suggests ~2²⁰ distinct values; many small registers plus careful averaging turns that gambler’s logic into 0.8% accuracy. Two properties make these production tools rather than curiosities: they are mergeable (per-shard sketches union into a global answer — distributed counting without coordination) and their error is a dial you set, with a formula linking memory to accuracy printed on the box.
Where it bites
- Billing, quotas, anything user-visible as an exact promise — ±1% is an SLA violation wearing a lab coat; sketches are for operational truth, not ledgers.
- Bloom filters sized for launch traffic — the false-positive rate climbs as it fills; size for the future or rotate.
- Counting distinct by
INSERT IGNOREinto a table — the 12 KB answer, purchased for gigabytes and lock contention. - Forgetting mergeability — per-node exact counts cannot be combined for distinct; per-node HLLs can. Choose the sketch because of the topology.