Probabilistic Sketches: HyperLogLog, Count-Min, and t-Digest in Production

Three questions appear in every large system: how many distinct things (daily active users), which things are hot (top talkers, trending items), and what does the distribution look like (p99 latency)? Answered exactly, each requires memory proportional to the data — a set of a billion user IDs, a counter per key, every latency sample. Sketches answer them in kilobytes, with errors you can dial, and — the property that actually earns them their place in distributed systems — they merge: shard-local sketches combine into a global answer without ever centralizing raw data. That mergeability, more than the memory savings, is why they belong in a system design interview.

HyperLogLog: count-distinct in 12KB

The idea is a coin-flip argument: hash every element; the probability of a hash starting with k leading zeros is 2^-k, so observing a run of 20 zeros suggests you've seen on the order of a million distinct values. One maximum is noisy, so HLL keeps m registers (say 2^14 = 16,384), routes each element by its hash's low bits to one register, and stores the max leading-zero count seen there; a corrected harmonic mean across registers yields the estimate.

add(x):   h = hash(x); j = h & (m-1); registers[j] = max(registers[j], lz(h >> 14)+1)
error:    ~1.04/√m  ->  m=16384: ±0.8%  in ~12KB, regardless of cardinality
merge(A,B): register-wise max         <- the superpower
union across shards/days = merge;  duplicates are free by construction

Duplicates never inflate the count (same hash, same register, same max) — dedup without storing identities. The merge being a pointwise max means per-shard, per-hour HLLs roll up into per-cluster, per-month counts by pure combination — this is how "distinct users last 30 days" is one loop over 720 hourly sketches instead of a 100TB DISTINCT. (Intersections, though, come via inclusion-exclusion and get noisy fast — promise unions, hedge intersections.)

Count-Min: heavy hitters from a stream you can't store

A count-min sketch is d hash rows × w counters. Add: increment one counter per row. Query: take the min across rows — collisions only ever overcount, so the min is the tightest bound.

add(x):    for i in 1..d: table[i][h_i(x)] += 1
count(x):  min_i table[i][h_i(x)]     -- overestimate, never under
space:     d=5, w=2000 -> 40KB;  error ≤ εN with prob 1-δ  (ε~e/w, δ~e^-d)

The one-sided error is the design feature: paired with a small top-K heap, it finds heavy hitters — hot keys, top talkers, trending hashtags — because big counts stay accurate (error is additive εN, negligible against a heavy hitter) while the long tail smears into noise you didn't care about. This is the "detect hot keys with a top-K sketch" line from the cache and rate-limiter posts, unpacked: the detector those systems wave at is 40KB of counters and a heap. Decay variants (sliding windows, exponential aging) keep "hot now" honest.

t-Digest: percentiles that merge

"You cannot average percentiles" — the metrics post's warning — has a constructive answer. A t-digest compresses a distribution into weighted centroids, denser at the extremes (a size limit that shrinks near ranks 0 and 1), so p50 is coarse but p99.9 — where SLOs live — stays sharp in a few KB. Digests merge by combining centroid sets, so per-instance latency digests roll up into a service-wide p99 that is correct, not an average of averages. This is the mathematically honest path for "global p99 across 500 pods" and the reason histogram/digest types exist in every serious metrics pipeline (Prometheus native histograms and DDSketch are cousins with different error contracts — relative-error buckets rather than rank-adaptive centroids).

Using them like an adult

Sketches are answers to aggregate questions with declared error, and the errors are part of the API — surface them ("DAU: 41.2M ± 0.3%"), don't launder them into exact-looking numbers. The recurring production pattern is sketch at the edge, merge in the middle: every node summarizes its own traffic locally (bounded memory, no coordination), a collector merges (cheap, associative, order-independent — idempotent replays merge harmlessly if you dedupe at the window level), and the exact-answer path (raw events in the lake) stays available for the rare question that needs a needle rather than a distribution. That split — cheap approximate now, expensive exact on demand — echoes the leaderboard's exact-head/approximate-tail and the log-search cost curve; it's the same budget philosophy applied to memory instead of storage.

Question	Sketch	Size	Error shape
Distinct count / dedup'd union	HyperLogLog	~12KB	±~1% symmetric
Per-key frequency / heavy hitters	Count-min (+heap)	~40KB	Overestimate only, additive εN
Percentiles / distributions	t-digest	~few KB	Tight at tails, mergeable
Membership ("seen before?")	Bloom filter	varies	False positive only

Interview probes worth anticipating: "exact DAU for billing?" — then it's not a sketch problem, it's a lake query; sketches serve dashboards and detectors, ledgers serve invoices. "Adversarial keys?" — hash with a keyed/seeded function or count-min becomes a collision-attack target. "Windowing?" — keep sketches per time bucket and merge ranges; never try to subtract from a sketch (HLL and CMS don't unmix — deletions need different structures or bucketed retention doing the forgetting).

The distilled principle: when the question is statistical, store a statistic — engineered for merging — instead of the data. Every mature fleet is quietly running dozens of these; knowing them by name, size, and error shape is what "back-of-envelope at scale" actually looks like in practice.