Three rows of counters. Keep the smallest.
Every event adds 1 in each row. Collisions only add, so the minimum is never too low, only sometimes too high.
ε = 0.01%. Is every count 0.01% off?
Bad: 0.01% of each count
So a 300-search query reads ≈ 300.
Good: 0.01% of the whole stream
≤ 100,000 over on a billion queries, 2% at 5 million, noise at 300.
Hash each user. Count leading zeros. Keep the max.
A first 1 at position r turns up about once per 2^r distinct items. Repeats hash identically, so they never move a register.
12 KB
for 100 million users, not 3.2 GB
You pay a 0.81% standard error. Memory follows the error you pick, not the count; quadruple the registers to halve it.
You saved 41,213 unique users for 9 am. Now you want the whole day.
The fix
A count can’t say who overlapped. Store the 12 KB sketch; merging keeps each register’s max, so repeats count once.
Name the question, then the structure
- How many distinct? HyperLogLog
- How often, or top 10? Count-min plus a heap
- Have we seen this before? A Bloom filter
- Moves money? Count exactly, never from a sketch
Say 10M users Monday, 10M Tuesday. How many came both days?
Inclusion–exclusion inherits the union’s error, about ±160,000 on 19.9 million, more than the 100,000 you want.
Remember
Distinct users? A HyperLogLog per page per hour, 12 KB at 0.81%, merged by register max. Top searches? Count-min plus a heap, over by at most εN. Billing stays exact.