06
Deep Dive — HyperLogLog vs Exact Counting
The defining data structure choice. HyperLogLog lets you count 500M unique elements in 12 KB of memory with 0.81% standard error — a 1.4-million-fold reduction vs exact sets. Here's why it works.
The Coin-Flip Intuition
Imagine each user flips a coin until they get heads, then reports the number of tails. You only track the maximum tails reported. If the max is R, you've probably seen ~2R unique people. A run of 20 tails (probability 1/220 ≈ 1 in a million) means ~1M unique visitors. One number, O(1) memory.
In practice: hash each user_id to a binary string, count leading zeros (equivalent to tails before heads). A single estimator has ~70% error. HLL fixes this with stochastic averaging — split elements into 16,384 buckets (using the first 14 bits of the hash), track max leading zeros per bucket, and combine using the harmonic mean.
Memory
16,384 registers × 6 bits each = 12 KB. Constant regardless of cardinality — works for 100 or 500M elements.
Error
Standard error = 1.04 / √16384 = 0.81%. For 200M DAU: ±1.62M (95% confidence ±3.24M).
The Killer Feature: Mergeability
Two HLL sketches merge by taking the register-wise maximum. The merged sketch equals a single sketch built over the union of both sets, with identical error bounds. This enables:
- Hourly → Daily: Merge 24 hourly sketches → DAU
- Daily → Monthly: Merge 30 daily sketches → MAU
- Cross-partition: Merge 10 Flink task slot sketches → global count
- Arbitrary ranges: "Users from March 10–25" → merge 16 daily sketches
Limitation: HLL supports union (merge) but NOT intersection or difference. "Users on iOS AND Android" requires Theta Sketches (Apache DataSketches) which support all set operations at ~32 KB, 2.7× more memory.
sequenceDiagram
participant SDK as Client SDK
participant API as Ingestion API
participant K as Kafka
participant F as Flink
participant R as Redis
SDK->>API: POST /v1/events (batch of 50)
API->>K: Produce to partition hash(user_id) % 64
K->>F: Consume event
F->>F: hash(user_id) → bucket #6746
F->>F: Leading zeros = 5 → Register[6746] = max(old, 5)
Note over F: Repeat for each segment:
global, country:IN, platform:ios
F->>R: PFMERGE hourly HLL sketches (every 30s)
Note over R: PFCOUNT → approximate DAU
PFMERGE 24 hourly → daily
Comparison Table
| Structure | Memory (200M, 1 ctr) | Memory (9K ctrs) | Accuracy | Merge | Intersect |
|---|
| HashSet | 9.6 GB | 150 TB | Exact | Yes (slow) | Yes |
| Roaring Bitmap | 200 MB–1 GB | ~9 TB | Exact | Yes (fast) | Yes |
| HyperLogLog | 12 KB | 108 MB | ±0.81% | Yes (trivial) | No |
| Theta Sketch | 32 KB | 288 MB | ±1.4% | Yes | Yes |
| Bloom Filter | 250 MB | 2.25 TB | N/A (not a counter) | Yes | ≈ Yes |
Redis HLL in Practice
# Add user to hourly sketch
PFADD hll:hourly:2026040614:country:IN "usr_204871"
→ (integer) 1 # sketch modified — new element
# Same user again — no change
PFADD hll:hourly:2026040614:country:IN "usr_204871"
→ (integer) 0 # already counted!
# Merge 24 hourly sketches → daily
PFMERGE hll:daily:20260406:country:IN \
hll:hourly:2026040600:country:IN \
... \
hll:hourly:2026040623:country:IN
# Get DAU
PFCOUNT hll:daily:20260406:country:IN
→ (integer) 14832901 # ±0.81% 