"How many people visited this restaurant's page today?" sounds like a counting question, but it isn't. It's a counting distinct question. If Asha opens the page five times, she counts once. To answer it exactly you have to remember every visitor you've already seen, so the memory grows with the number of unique visitors.
For one restaurant that's fine. For 60,000 restaurants, per day, per city, per app version, it adds up to tens of gigabytes of sets. HyperLogLog answers the same question for any number of visitors in about 12 KB per counter, with a typical error under 1%.
The problem: distinct counts are expensive
Tiffin's analytics team wants daily and weekly unique visitors for every restaurant page, every dish and every city. The exact way:
| Approach | Memory for 50 million unique users |
|---|---|
| Set of 8-byte user IDs | 400 MB, plus overhead (often 2 to 4× that) |
| Bitmap with one bit per possible user | about 6 MB, but only if IDs are small dense integers |
| HyperLogLog | 12 KB, for any number of users |
And it gets worse: weekly uniques aren't the sum of daily uniques (Asha visits on Monday and Friday). With exact sets you'd have to keep every day's set around to union them. HyperLogLog sketches can be merged, so daily sketches roll up into weekly ones for free.