Counting is expensive.
You have a stream of 1 Billion events coming into your analytics pipeline. You want to answer a simple question: "How many unique users visited today?"
Approach A: The Python Set
users = set()
for event in stream:
users.add(event.user_id)
print(len(users))
Result: You need to store 1 billion UUIDs. Each UUID is 32 bytes.
Cost: 32 GB of RAM. Your server crashes.
Approach B: The HyperLogLog You use a probabilistic counter.
Result: You use 12 Kilobytes of RAM.
Accuracy: 99.19%. (You might output
1,005,000instead of1,000,000).
For analytics, 0.81% error is negligible. The 99.999% RAM savings are massive.
1. The Intuition: The Coin Flip Game
How can you estimate a massive number without storing the data?
Math. Specifically, The Law of Large Numbers.
Imagine I tell you: "I flipped a coin until I got Heads."
If I say: "It took me 1 try," I probably didn't flip the coin very many times.
If I say: "It took me 10 consecutive Tails before I got a Heads," you know I probably flipped the coin thousands of times to get that lucky run.
HyperLogLog applies this to Binary Hashing:
Hash every user ID into a binary string (e.g.,
01100100...).Count the number of leading zeros.
If you see a hash with 20 leading zeros, you know statistically you must have seen roughly $2^{20}$ (1 Million) unique items to find that "lucky" hash.
By tracking the maximum number of leading zeros seen, you can estimate the total count.
2. The Code: Redis Implementation
You don't need to implement the math. Redis has it built-in. It's called PFADD (after Philippe Flajolet, the inventor).
# 1. Add users to the counter
PFADD daily_visitors "user_1"
PFADD daily_visitors "user_2"
# ... add 1 billion users ...
# 2. Get the count
PFCOUNT daily_visitors
# Output: 1004201
Memory used: 12kb. Time taken: O(1).
The Application: Where to use it?
Do not use HyperLogLog for:
Bank Balances.
Inventory Counts.
Anything needing 100% precision.
Do use HyperLogLog for:
Daily Active Users (DAU).
Unique views on a YouTube video.
Search keywords entered on Google.
3. THE CEREBRAL GYM: Solution & New Puzzle
Yesterday's solution (The Counter)
The puzzle was: What algorithm counts unique items with 12KB of RAM?
The Answer: HyperLogLog.
Today's puzzle (Distributed Clocks) Thursday is for Time.
In a distributed system, you cannot trust the system clock. Server A might think it is 12:00:00, and Server B might think it is 12:00:05. This makes ordering events impossible ("Did User A buy the item before User B?").
To solve this, Leslie Lamport invented a "Logical Clock." It doesn't track seconds; it tracks Causality. It is just an integer counter that increments with every event.
The Question: What is the specific name of the more advanced version of a Lamport Clock that uses an array of integers (one per node) to detect concurrent events?
(Reply with the name!)
4. THE PULSE: Industry Signals
Redis (PFADD) As shown above, Redis is the easiest way to use HLL. It merges HLLs too (Union), so you can combine "Morning Traffic" and "Evening Traffic" into "Daily Traffic" without losing accuracy. Link: redis.io/commands/pfadd
BigQuery (APPROX_COUNT_DISTINCT) If you use SQL, you are likely using HLL without knowing it. In BigQuery,
COUNT(DISTINCT x)is exact and slow.APPROX_COUNT_DISTINCT(x)uses HyperLogLog, costs less money, and runs 10x faster. Link: cloud.google.com/bigquery/docs/reference/standard-sql/hll_functionsDatasketches (Apache) This is the "Swiss Army Knife" of probabilistic algorithms. It includes HLL, Bloom Filters, and "Quantiles" (estimating the 99th percentile without sorting). Link: datasketches.apache.org
5. THE LATENT SPACE
"Precision is a luxury."
In the early days of a startup, you need exact numbers. You have 100 users. At scale, "exact" is too expensive. Google doesn't know exactly how many search results there are. YouTube doesn't know exactly how many views a video has (that's why it stops at 301+).
They trade precision for scale. You should too.
See you tomorrow.
Harsh Kathiriya - Query & Context