Why architecture matters here
HLL architecture matters because count-distinct is one of the most-run aggregations in analytics, and exact algorithms don't scale. Counting distinct users in a stream of a billion events requires exact storage of every seen user ID; HLL does the same job at 0.016 of the memory with 1.6% error. Understanding the trade-off shapes analytical accuracy expectations.
Cost is dramatic. HLL uses fixed memory regardless of cardinality — 1.5 KB is enough to count trillions of distinct items with 1.6% error. Exact count needs storage proportional to cardinality.
Reliability of the estimate depends on correct implementation. Bias correction at small and large cardinalities matters; naive HLL produces wildly wrong estimates outside the middle range.
The architecture: every step explained
Walk the diagram top to bottom.
Item. The input — user ID, event ID, whatever you want to count distinctly.
Hash Function. Uniform 64-bit hash (MurmurHash, xxHash). Distribution matters more than cryptographic strength.
Registers. m = 2^p buckets. Common choice: p = 14, m = 16384 registers, 1.5 KB total (registers hold small integers, 5-6 bits each).
Bucket by top p bits. The top p bits of the hash pick which register to update.
Rank = leading zeros + 1. In the remaining 64-p bits, count leading zeros and add 1. Very high rank means the item happened to hash to a rare bit pattern.
Update rule. R[bucket] = max(R[bucket], rank). Only the maximum rank per bucket matters.
Harmonic mean. E = α_m · m² / Σ 2^(-R_j). The harmonic mean gives a better estimator than arithmetic mean. α_m is a constant for the given m.
Bias correction. At small n (much smaller than m), the estimator is biased; use LinearCounting instead. At very large n approaching 2^32, apply correction. HLL++ (Google) refines these corrections.
Merge (union). Two HLL sketches can be merged by taking max register-wise. This gives you distributed / mergeable cardinality.
Space vs error. Standard error ~1.04 / sqrt(m). At m=16384, error ≈ 0.8%; with practical bias, ≈ 1.6%.
End-to-end count flow
Trace a count. Insert item "user-42". Hash gives 64 bits.
Top 14 bits: bucket index (say, 8237). Remaining 50 bits: rank = leading zeros + 1 (say, 4 leading zeros → rank 5).
R[8237] = max(current, 5). If current was 3, now 5.
Insert 10 million more items. Registers gradually accumulate high ranks in a distribution characteristic of true cardinality.
Query estimate: compute harmonic mean of 2^R across all 16384 registers, multiply by α_m · m². Apply bias correction if estimate is small or large. Return.
Actual cardinality: 10 million. Estimated: 10.08 million. Error: 0.8%.
Merge scenario: two servers each maintained an HLL for their subset. Union register-wise (element max). Estimate on union HLL gives distinct across both — no need to re-scan.
Delete not supported. HLL is monotone increasing; you can add but not remove. For deletion, use HLL variants or a Count-Min sketch.