Streaming Algorithms and Sketches
How to compute statistics over a stream too large to store, the three canonical sketches and their guarantees, and the mergeability property that makes them work in distributed systems.
A stream of billions of events, sublinear memory, one pass. Exact answers to most questions are provably impossible under those constraints, so the field is built on approximate answers with quantified error, and the approximations are good enough that the exact versions are rarely missed.
The three canonical sketches
HyperLogLog estimates the number of distinct elements. Hash each element and track the maximum number of leading zeros observed across buckets: seeing a hash with \(k\) leading zeros suggests roughly \(2^k\) distinct elements, and averaging across buckets controls the variance. It uses a few kilobytes for a relative error around 2 percent regardless of cardinality, which can be billions. Exact distinct counting requires memory proportional to cardinality, so this is a substantial asymptotic saving rather than a constant-factor one.
Count-Min Sketch estimates the frequency of any element. Maintain a two-dimensional array of counters, hash each element with several independent functions, increment the corresponding counter in each row, and estimate frequency as the minimum across rows. Collisions only inflate counts, so the estimate is an over-estimate with a bound: the error exceeds \(\epsilon N\) with probability at most \(\delta\), for width and depth chosen from \(\epsilon\) and \(\delta\).
t-digest and KLL estimate quantiles. t-digest clusters values with higher resolution at the distribution's tails, which is the right allocation because the interesting quantiles are usually p99 and p999 rather than the median. KLL sketches give distribution-free error guarantees on rank.
Mergeability
The property that makes sketches work in real systems is that they merge. Two HyperLogLog sketches combine by taking the elementwise maximum; two Count-Min sketches by summing; both yielding exactly the sketch of the union.
This means each machine, shard or time bucket can maintain its own sketch independently, and aggregation over any subset is a cheap merge rather than a re-scan. Distinct users this week is the merge of seven daily sketches. Distinct users for a region is the merge of its shards. No re-processing occurs, and the same property is what makes sketches usable as materialised aggregates in a data warehouse.
When it breaks
Approximate answers must be labelled. A dashboard showing a count that is 2 percent off is fine until someone reconciles it against an exact figure and reports a data quality incident. The approximation and its error bound belong in the metric's definition.
Count-Min over-estimates, always. The minimum over rows is still an over-estimate because every counter has absorbed collisions. This matters for rare items, whose true count is small relative to the collision noise, so the sketch is accurate for heavy hitters and unreliable in the tail, which is the opposite of what people often want it for.
Deletion is not generally supported. Count-Min with decrements can go negative and lose its guarantee; HyperLogLog cannot remove elements at all. Streams with retractions need sketches designed for them, and the standard ones silently give wrong answers.
Parameters are fixed at creation. A sketch sized for one error target cannot be re-tuned later without reprocessing the stream, and merging sketches with different parameters is generally invalid. This is the operational constraint that most often bites, because the error target is chosen before anyone knows what the data looks like.
12 flashcards for this concept
Click a card to reveal the answer.