Recently I was building a piece of functionality to track the daily and monthly
active users on one of my sites. I already track this data in MySQL but
retrieving the data was sluggish, even after creating a few new indexes, so I
decided that I would use Redis. The question then became, which data type would
I use to track this?
The data itself is just a list of the unique user IDs that have accessed the
site on a given day or month. I could use a sorted set and use the timestamp as
the score, but I don’t need the score or the ability to sort the data, I just
need the count.
I did some research and came across this package to track user actions quickly
in Redis with Node.js. I was implementing this in PHP but still took a
gander at the code. To my surprise, they were using bitmaps in Redis to track
the users. SETBIT to track and then GET and some extra logic to count the
number of active users. I’m unsure why they didn’t use BITCOUNT to found the
number of set bits, but then again, I have never worked with bitmaps in Redis
so I set out to learn more.
After digging around the wonderful Redis documentation, I came to the
conclusion that bitmaps are great and all, but based on time complexity, sets
(not sorted sets) would be better for my particular use case.
In the following examples I’ll be tracking the monthly active users for
September 2015 and :UID represents the unique ID for the user.
Tracking
Bitmap
SETBIT MAU:BITMAP:201509 :UID 1
The argument of 1 tells it to flip the bit on. The time complexity for this
is O(1).
Set
SADD MAU:SET:201509 :UID
The time complexity is documented as O(N) but N represents the number of items
being added, not the number of items in the set, so it would also be O(1).
Retrieving
Bitmap
BITCOUNT MAU:BITMAP:201509
This would count every bit that’s set to on in the bitmap. The time complexity
is O(N). Unfortunately, the documentation doesn’t clearly explain what N
represents. Feel free to comment on this if you know, but from what I gathered
based on the performance considerations with larger bitmaps and this command,
the N represents the total number of bits set in the bitmap.
It’s documented that with smaller bitmaps the BITCOUNT command “is still as
fast as any other O(1) Redis command”. Thus, it gets slower as the bitmap grows
in size.
Set
SCARD MAU:SET:2015
Time complexity on this one is O(1) regardless of the size of the set.
Conclusion
Based on the vagueness of the documentation regarding BITCOUNT’s time
complexity, sets are the clear winner for me in this particular use case.
One thing I didn’t factor into this is the memory footprint for each of the
types. I suspect that bitmaps would be smaller then sets. Do you want a smaller
footprint or faster retrieval?
The other consideration is how large your user IDs are. Bitmaps only support
bit offsets up to 2^32 (4,294,967,296). More than most of us will ever need but
if you thought it would be cute to start your user IDs at 5 billion or
something you’re pretty much fucked.
I’m planning to put together an active user PHP package similar to the Node.js
one I found, be sure to follow me on GitHub if you’re interested.
