Data Sketch
Counting the uncountable with HyperLogLog. Stream millions of events through a few kilobytes of registers and watch the estimate chase the true distinct count.
View sourceAbout this experiment
HyperLogLog answers one question — “how many distinct things have I seen?” — without storing the things. Each incoming key is hashed; the leading bits pick one of 2 ᵖ registers, and each register remembers only the longest run of leading zeros it has witnessed. Rare long runs imply many distinct inputs, so a harmonic mean over the registers recovers the count. The memory never grows with the data: every readout above comes from the same 16,384 one-byte registers, whether you feed it ten items or ten million.
Slide precision up for more registers and a tighter error band; slide it down to watch the estimate get noisy. Hit +1M duplicates to confirm the payoff: the event counter rockets while the estimate barely twitches, because duplicates carry no new information. That is the whole trick behind APPROX_COUNT_DISTINCT, Redis PFCOUNT, and ClickHouse uniq — a defensible number with a known error bound, computed in one pass over a firehose.