Last weekend, I dove into CMU’s [15-445/645](https://15445.courses.cs.cmu.edu/) database course and got hit with a deceptively simple problem: count the number of unique users visiting a website per day. Easy, right? Just throw user IDs into an unordered_set and return its size—classic LeetCode.
But what happens when you’re at Facebook scale? Tracking a billion unique users means burning through GBs of memory just to count. And in the real world, users are streaming in constantly, not sitting in a neat, static list. Storing every ID? Not happening.
I explored practical workarounds (like “last seen” timestamps and full table scans), but they’re either inefficient or put massive strain on your DB. Then the assignment introduces HyperLogLog: a probabilistic algorithm that estimates cardinality with just 1.5KB of memory—accurate to within 2% for billions of users.
The magic? Pure mathematics. It’s distributable, and powers real-world systems like Redis and Google Analytics. I break down how it works (with illustrations!), check out my deep dive.
Curious to hear from HN: Who’s using HyperLogLog in production? And have you run into accuracy issues, and how did you handle them?
Comments
Last weekend, I dove into CMU’s [15-445/645](https://15445.courses.cs.cmu.edu/) database course and got hit with a deceptively simple problem: count the number of unique users visiting a website per day. Easy, right? Just throw user IDs into an unordered_set and return its size—classic LeetCode.
But what happens when you’re at Facebook scale? Tracking a billion unique users means burning through GBs of memory just to count. And in the real world, users are streaming in constantly, not sitting in a neat, static list. Storing every ID? Not happening.
I explored practical workarounds (like “last seen” timestamps and full table scans), but they’re either inefficient or put massive strain on your DB. Then the assignment introduces HyperLogLog: a probabilistic algorithm that estimates cardinality with just 1.5KB of memory—accurate to within 2% for billions of users.
The magic? Pure mathematics. It’s distributable, and powers real-world systems like Redis and Google Analytics. I break down how it works (with illustrations!), check out my deep dive.
Curious to hear from HN: Who’s using HyperLogLog in production? And have you run into accuracy issues, and how did you handle them?