3 ms·

HyperLogLog is quite neat, and I very much enjoyed antirez's writeup as well. There are probably a lot of uses for it beyond e.g. counting active users. I'd l

by Groxx 12y ago

HyperLogLog is quite neat, and I very much enjoyed antirez's writeup as well. There are probably a lot of uses for it beyond e.g. counting active users. I'd love to hear about them. But nearly everyone uses counting users as an example. For this kind of use, I honestly have to ask: at WhatsApp's scale, is 5GB of ram really an issue? It seems like they could probably keep that exact setup and roll it over every minute and not even really tax a modern server. Or compact it - one bit per person, lookup is just jumping to the address at their ID, counting is just summing, which would probably meet most needs. With this you can handle every person on earth in < 8GB. You can do that with an m3.xlarge on EC2 (15GiB ram) for a measly 25 cents per hour. That's $6/day. That's literally nothing compared to normal server costs.

bialecki 12y ago
I'm sure other people are wondering the same thing, so a quick take. The problem is not if you're counting one thing (or even 100). The problem is when you want analytics and you want it to scale to 1,000s or 1,000,000s of counters. That may seem ridiculous (who could possibly need that many counters?). But it happens quickly when you say, "How many DAUs do we have? How many from country X? How many using device Y? How many from country X and using device Y?" Also, to address an idea you mentioned around bitmaps. Bitmaps are great until you have lots of counters and lots of users/things to count. Then the problem is they get very sparse. Imagine user #100,000 does something. You need to allocation 97k of space (lots of zeros behind that 100,000th bit) just to count that one thing. Are bitmaps a good idea? Sure, in a lot of cases they are. The problem is they just break down at some point and that's when these other tricks are really nice.
Groxx 12y ago
(geh, too late to edit) correction: an m3.medium will do this, as it's only 8 gigabits, which is $0.064/hour, or ~$1.50/day.

by Groxx 12y ago

bialecki 12y ago

I'm sure other people are wondering the same thing, so a quick take. The problem is not if you're counting one thing (or even 100). The problem is when you want analytics and you want it to scale to 1,000s or 1,000,000s of counters. That may seem ridiculous (who could possibly need that many counters?). But it happens quickly when you say, "How many DAUs do we have? How many from country X? How many using device Y? How many from country X and using device Y?" Also, to address an idea you mentioned around bitmaps. Bitmaps are great until you have lots of counters and lots of users/things to count. Then the problem is they get very sparse. Imagine user #100,000 does something. You need to allocation 97k of space (lots of zeros behind that 100,000th bit) just to count that one thing. Are bitmaps a good idea? Sure, in a lot of cases they are. The problem is they just break down at some point and that's when these other tricks are really nice.

Groxx 12y ago

(geh, too late to edit) correction: an m3.medium will do this, as it's only 8 gigabits, which is $0.064/hour, or ~$1.50/day.