Counting at scale — HyperLogLog, count-min, top-k, t-digest

Counting distinct things, ranking heavy hitters, and estimating percentiles at scale is where approximate structures earn their keep:

• HyperLogLog (distinct count): hash each element, track the max number of leading zeros in buckets → cardinality estimate with ~1.04/√m relative error (m = 2^14 registers ≈ 1.6% error in ~12 KB, regardless of set size). Mergeable (union = register-wise max) — the property that makes it work across shards/periods. Redis has it natively (PFADD/PFCOUNT).
• Count-min sketch (frequencies): a matrix of counters with multiple hash functions; increment all, query the min. Overestimates (never underestimates) with bounded error — perfect for "is this a heavy hitter" (check if estimated count > threshold). Mergeable.
• Top-k / heavy hitters: Space-Saving or Misra-Gries — a bounded counter set with eviction of the smallest; or Count-Min + a heap. Answers "what are the hottest keys right now?" in fixed memory.
• t-digest / HDR histograms (quantiles): clusters of values with size bounds — accurate p99 estimates with extreme compression; mergeable (percentile aggregation across instances). Your OTel/Better Stack latency percentiles are histograms of this family.
• Reservoir sampling: uniform sample of a stream in one pass, fixed memory — for "show me 100 examples" without storing everything.
• Bucketed time-window aggregation: pre-aggregate into time buckets (minute/hour/day) with counters/sketches per bucket → dashboards read buckets, not raw events; retention = drop old buckets. The standard time-series shape.

Mergeability is the theme: sharded/distributed analytics only work if partial results combine — HLL (max), CMS (sum), t-digest (merge clusters), bucketed counters (sum). Non-mergeable approximations force centralization.

Your systems' position (exact, and correctly so): traverse's stats endpoints COUNT rows in Postgres (_count, groupBy) — exact, instant at your scale; zoth's dashboard does the same. The right answer for interviews: "I count exactly because my data fits; at 100M events/month I'd add bucketed rollups (minute/hour tables written by workers) before sketches, and reach for HLL/CMS only when the distinct-cardinality or heavy-hitter queries themselves become the bottleneck — sketches are an optimization tier for queries you've proven are expensive, not a default."

The one place you'd want them tomorrow: traverse's analytics — "unique problems solved this month," "top 10 most-attempted topics" across all users. Both are currently SQL GROUP BYs; at scale they're HLL and CMS/top-k respectively, maintainable incrementally by the workers (a counter update per submission beats a table scan per dashboard load).

How they actually work (the mechanics, because the mechanics are the interview)

HyperLogLog, in four steps. (1) Hash each element to a 64-bit value — the hash must be uniform, which is why you never feed HLL a low-entropy key. (2) Use the first b bits (b = 14 → 16,384 registers) to pick a register. (3) In that register, store the count of leading zeros in the remaining bits, keeping the maximum. (4) Estimate cardinality from the harmonic mean of 2^register across all registers, with a bias correction. The intuition: a hash with k leading zeros appears roughly once in 2^k elements, so the largest leading-zero count in a bucket proxies how many elements hit it. Harmonic (not arithmetic) mean is what stops one unlucky register from destroying the estimate — a single register seeing 40 leading zeros out of 16,384 would swamp an average but barely moves a harmonic mean. Error is ~1.04/√m ≈ 0.8% at m = 2^14, and you can buy accuracy with registers (b = 16 gives ~0.4% at 128 KB). Registers are a fixed byte array, so a billion-element set costs the same ~12 KB as a thousand-element set — that is the whole point, and it is also why HLL cannot tell you which elements it saw, only how many distinct ones there were.

Count-min sketch, in three steps. (1) Pick d independent hash functions (4–5 in practice). (2) For each element, increment one counter per hash function — a d × w matrix of counters. (3) To query a frequency, take the minimum of the d counters. Why minimum: collisions can only add to a counter, never subtract, so every counter is an overestimate and the smallest is closest. Error is bounded by ε·N with probability 1 − δ, where w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉. The consequence to state clearly: count-min never underestimates. That asymmetry is a feature for heavy-hitter detection — if the estimate is already below your threshold, the true count definitely is too — and a liability wherever an inflated number causes harm, such as "did this user exceed their quota?", where an overestimate wrongly denies them. Choose by which direction of error you can tolerate.

Top-k, one level up. Count-min gives approximate frequencies but not which keys are heavy. Space-Saving keeps exactly k (key, counter) pairs: a new key either matches an existing entry (increment) or evicts the entry with the smallest counter and inherits its count, so the counter is an upper bound with a known error term. O(k) memory, one pass, heavy hitters directly. Misra-Gries does the same with a decrement-all variant. Both are what "top 10 most-attempted topics across all users" needs at scale, and both are mergeable enough to run per-shard and combine.

t-digest, and why percentiles are the hard one. A mean is mergeable and a percentile is not: averaging p99 across two shards is mathematically meaningless. t-digest solves this by storing clusters — a centroid (the mean of the values in the cluster) plus a count — with the constraint that clusters near the tails must be small while clusters near the median may be large. The result is high accuracy exactly where you care: p99 and p999 come from many small clusters, p50 from a few big ones. Clusters merge, so per-instance digests combine into a global one. HDR histograms are the fixed-bucket cousin (exponential buckets, so relative error is uniform across magnitudes) and are what most latency-instrumentation libraries emit — which is why the p99 on your Better Stack latency dashboard is trustworthy across services while a hand-rolled AVG(duration) is not.

The property that makes the whole family work is mergeability, and it has a direct architectural consequence: partial results from shards, replicas, or time windows combine into a global answer, so aggregation can be pushed to the edge and only the sketch travels. Non-mergeable approximations force every event to a central point — exactly the cost you were trying to avoid.

Reservoir sampling and bucketed rollups round out the toolkit: reservoir sampling gives a uniform sample of a stream in one pass at fixed memory (for "show me examples" and for arbitrary offline statistics), and bucketed time-window aggregation — pre-aggregating into minute/hour/day buckets with a counter or sketch per bucket — is the workhorse behind every dashboard you have ever seen. Its retention story is the cleanest of all: dropping old data is deleting rows, which is the only reclamation mechanism in this entire article that is O(1) rather than approximate.