Redis

Redis BITOP

Fundamentals of Redis Bitmaps

Redis bitmaps are another way of treating the string-type data as a collection of bits or vectors of bits. Hence, the underlying data structure of bitmaps is a string where a string is stored using an array of zeros and ones in the computer memory. Redis bitmaps support the retrieval and alternation of the bit value of a given offset in a bitmap. Furthermore, it provides commands to perform the bitwise operations like AND, OR, NOT, and XOR on multiple strings that are stored at given keys.

As mentioned, a string value that is stored in the Redis database can be treated as a bitmap. We can perform the bitwise operations on multiple Redis strings stored at given keys as follows:

AND Operation

The following figure illustrates how the bitwise AND operation on two given strings works. In this example, we will use the strings A and B to perform the bitwise AND operation.

OR Operation

Let’s perform the bitwise OR operation on the same two strings from the previous example.

As shown, the resultant bitmap is 1000011 which is the ASCII representation of the letter C.

XOR Operation

The following figure clearly explains how the bitwise XOR operation operates on the same two strings:

NOT Operation

The NOT operator is used as a unary operator in the Redis bitwise operations. Hence, it takes only one string value as the input.

The bitwise NOT operation on string A returns the \xbe hexadecimal value and no associated printable ASCII value.

The BITOP Command

The BITOP command has been introduced by Redis to perform the earlier discussed bitwise operations on one or multiple strings(bitmaps) stored at given keys. This command operates with O(N) time complexity where N is the length of the longest string in the comparison which is quite slower than the other bitmap operations. This command performs the specified bitwise operation and stores the resultant bitmap(string) at the specified destination key.

The syntax of the BITOP command is as follows:

BITOP bitwise_operation destination_key bitmap_key [bitmap_key ...]

The BITOP command returns an integer value that is the size of the resultant bitmap. The size of the resultant bitmap is equal to the size of the longest input bitmap.

In some cases, the input bitmaps contain strings in different sizes. So, the BITOP command treats all the other input strings that are shorter than the longest one as zero-padded up to the size of the longest string. Similarly, the non-existing bitmap keys are considered zero-byte strings with equal sizes to the longest input string.

Use Case – Active Users of a Website in a Given Days

Let’s assume that a website owner is interested in the active users who are logged into a website, weekly. In this case, a bitmap is an ideal candidate to store the daily visits. Each user can be represented using an offset in the bitmap. In addition, separate bitmaps can be used per day with a unique id as shown in the following illustration:

Let’s create bitmaps for the previous three days (Sunday, Monday, and Tuesday) that hold each user’s visit status. The SET command can be used to create each bitmap as follows:

We create the first bitmap that is identified by the key visit:2022:08:4:SUN. So, the first user is identified by the offset 0. Let’s assume that the user who is associated with user id 0 visited the website on Sunday. Hence, the offset 0 is set to 0 as follows:

setbit visit:2022:08:4:SUN 0 1

Similarly, the visit status of the users associated with user IDs 1, 2, 3, and 4 is set accordingly.

setbit visit:2022:08:4:SUN 1 0

setbit visit:2022:08:4:SUN 2 1

setbit visit:2022:08:4:SUN 3 0

setbit visit:2022:08:4:SUN 4 0

Let’s inspect the bit values for each user using the GETBIT command as follows:

getbit visit:2022:08:4:SUN 0

getbit visit:2022:08:4:SUN 1

getbit visit:2022:08:4:SUN 2

getbit visit:2022:08:4:SUN 3

getbit visit:2022:08:4:SUN 4

Similarly, we can create the bitmaps to store the user visits on Monday and Tuesday that are identified by the keys visit:2022:08:5:MON and visit:2022:08:6:TUE.

The website owner’s interest is to get the users who visited the website at least a day from Sunday, Monday, or Tuesday. This type of information can be obtained using the BITOP command as follows. The OR bitwise operation is ideal to check the users who visited the site at least one day from the three days.

bitop OR atleaseonevisituser visit:2022:08:4:SUN visit:2022:08:5:MON visit:2022:08:6:TUE

We performed the bitwise OR operation on the earlier created three bitmaps. The resulting bitmap is stored at the key atleastonevisituser. Let’s check the resulting string or bitmap using the GET command as follows:

get atleaseonevisituser

The returned bitmap or string’s hexadecimal value is \xb0 which represents the degree sign in ASCII. Let’s inspect each bit of the string that is stored at the destination key atleaseonevisituser using the GETBIT command.

getbit atleaseonevisituser 0

getbit atleaseonevisituser 1

getbit atleaseonevisituser 2

getbit atleaseonevisituser 3

getbit atleaseonevisituser 4

As we could see in the output, the resulting bitmap looks like the following:

1 | 0 | 1 | 1 | 0

The offset 0 is associated with the user ID 0, the offset 1 is with user ID 1, and so forth. According to the result of the bitwise OR operation, only three users visited the website at least one day from the mentioned three days. The users that are stored at offsets 1 and 4 who are associated with user IDs 1 and 4 have not visited the website on Sunday, Monday, or Tuesday.

Conclusion

In summary, Redis bitmaps are an array of zeros and ones where each bit is identified by an offset value. As discussed, the BITOP command is used to perform the bitwise operations such as OR, AND, XOR, and NOT over a specified bitmap or string. As shown in the use case, the resulting string is stored at the specified key. This command is quite slow when the size of the longest string is increased. Overall, the BITOP command is useful in identifying the patterns of website visits and music app usage statistics over a given period.

About the author

Nimesha Jinarajadasa

Being a Full-stack Senior Software Engineer for more than five years, I love technology, as technology has the power to solve our many problems within just a minute. I try to learn more and create more opportunities for this new world.