Introduction to Redis bitmaps
Bitmaps are not an actual data type, but a set of bit-oriented operations defined on the String type which is treated like a bit vector. Since strings are binary safe blobs and their maximum length is 512 MB, they are suitable to set up to 2^32 different bits.
You can perform bitwise operations on one or more strings. Some examples of bitmap use cases include:
- Efficient set representations for cases where the members of a set correspond to the integers 0-N.
- Object permissions, where each bit represents a particular permission, similar to the way that file systems store permissions.
SETBITsets a bit at the provided offset to 0 or 1.
GETBITreturns the value of a bit at a given offset.
BITOPlets you perform bitwise operations against one or more strings.
See the complete list of bitmap commands.
Suppose you have 1000 sensors deployed in the field, labeled 0-999. You want to quickly determine whether a given sensor has pinged the server within the hour.
You can represent this scenario using a bitmap whose key references the current hour.
- Sensor 123 pings the server on January 1, 2024 within the 00:00 hour.
> SETBIT pings:2024-01-01-00:00 123 1 (integer) 0
- Did sensor 123 ping the server on January 1, 2024 within the 00:00 hour?
> GETBIT pings:2024-01-01-00:00 123 1
- What about sensor 456?
> GETBIT pings:2024-01-01-00:00 456 0
Bit operations are divided into two groups: constant-time single bit operations, like setting a bit to 1 or 0, or getting its value, and operations on groups of bits, for example counting the number of set bits in a given range of bits (e.g., population counting).
One of the biggest advantages of bitmaps is that they often provide extreme space savings when storing information. For example in a system where different users are represented by incremental user IDs, it is possible to remember a single bit information (for example, knowing whether a user wants to receive a newsletter) of 4 billion users using just 512 MB of memory.
> setbit key 10 1 (integer) 0 > getbit key 10 (integer) 1 > getbit key 11 (integer) 0
SETBIT command takes as its first argument the bit number, and as its second
argument the value to set the bit to, which is 1 or 0. The command
automatically enlarges the string if the addressed bit is outside the
current string length.
GETBIT just returns the value of the bit at the specified index.
Out of range bits (addressing a bit that is outside the length of the string
stored into the target key) are always considered to be zero.
There are three commands operating on group of bits:
BITOPperforms bit-wise operations between different strings. The provided operations are AND, OR, XOR and NOT.
BITCOUNTperforms population counting, reporting the number of bits set to 1.
BITPOSfinds the first bit having the specified value of 0 or 1.
> setbit key 0 1 (integer) 0 > setbit key 100 1 (integer) 0 > bitcount key (integer) 2
For example imagine you want to know the longest streak of daily visits of
your web site users. You start counting days starting from zero, that is the
day you made your web site public, and set a bit with
SETBIT every time
the user visits the web site. As a bit index you simply take the current unix
time, subtract the initial offset, and divide by the number of seconds in a day
This way for each user you have a small string containing the visit
information for each day. With
BITCOUNT it is possible to easily get
the number of days a given user visited the web site, while with
BITPOS calls, or simply fetching and analyzing the bitmap client-side,
it is possible to easily compute the longest streak.
Bitmaps are trivial to split into multiple keys, for example for
the sake of sharding the data set and because in general it is better to
avoid working with huge keys. To split a bitmap across different keys
instead of setting all the bits into a key, a trivial strategy is just
to store M bits per key and obtain the key name with
the Nth bit to address inside the key with
bit-number MOD M.