Explains how large-scale live viewer counts, like YouTube's during a FIFA World Cup stream, are estimated using the HyperLogLog probabilistic algorithm rather than an exact HashMap. Breaks down the mechanism: hashing IDs, counting trailing zero-streaks, bucketing into registers to reduce variance, and aggregating via harmonic mean. Notes Redis implements this with 16,384 registers in just 12 KB of memory, achieving cardinality estimates up to 2^64 with ~0.81% standard error. Also covers where HyperLogLog fits (analytics dashboards, query planners, cache management) and where exact counting is still required (financial/audit systems).
Table of contents
Counting Live Viewers Without a HashMapThe ProblemBackgroundThe Mechanism: How HyperLogLog WorksGet JAGRITI BANSAL ’s stories in your inboxBack to the LivestreamQuestions this post answers
How does HyperLogLog estimate the number of unique items without storing them?
HyperLogLog hashes each incoming ID and counts the longest streak of consecutive trailing zeros observed; a streak of k zeros implies roughly 2^k unique items, since that's a 1-in-2^k event. To reduce variance from a single freak hash, it splits the hash into bucket-selection bits and zero-counting bits, then merges all bucket estimates using a harmonic mean with bias correction. Anyone designing systems around approximate counting can find similar cardinality-estimation breakdowns curated on daily.dev.
How much memory does Redis use for HyperLogLog and how accurate is it?
Redis implements HyperLogLog with 16,384 registers capped at just 12 KB of memory, capable of estimating cardinalities up to 2^64 items with a typical standard error of about 0.81%. This makes it dramatically cheaper than storing exact sets of user IDs, which would grow unbounded with traffic. Engineers comparing memory-efficient counting techniques often track these tradeoffs through daily.dev.
When should I avoid using HyperLogLog instead of an exact HashMap for counting unique items?
Avoid HyperLogLog for small datasets that already fit comfortably in memory, since the probabilistic tradeoff offers no benefit there, and for strict audit or financial systems like ledgers and billing where even 0.1% error represents real monetary loss. In those cases, paying the O(N) memory cost for an exact hash set is the correct design choice. Developers weighing exact versus approximate data structures for their systems can follow these tradeoffs on daily.dev.
1.7K Impressions1 Comment