An in-depth analysis of bitmaps in Redis (bitmap)

This article will take you through the bitmap in Redis, I hope it will be helpful to you!

The bitmap of Redis is an array composed of multiple binary bits. Each binary bit in the array has a corresponding offset (from Starting from 0), these offsets can be used to operate on one or more binary bits specified in the bitmap. [Related recommendations: Redis Video Tutorial]

Actually, bitmap is not a new data type provided by Redis, it is an extension of the string type. Therefore, bitmap commands can be used directly on string type keys, and keys operated by bitmap commands can also be operated by string type commands.

For example, there is a string key foo:

redis> set foo bar

1 byte consists of 8 binary bits, so the binary form of the foo key is:

SETBIT

Through the SETBIT command, you can specify the binary bit setting value at the offset for the bitmap, offset must be greater than or equal to 0 , value can only be 0 or 1. The time complexity of this command is O(1).

SETBIT key offset value

After setting the binary bit, the SETBIT command will return the old value before the binary bit is set as the result.

Suppose now that you want to change bar into aar, you only need to do the following two steps:

redis> setbit foo 6 0
(integer) 1
redis> setbit foo 7 1
(integer) 0
redis> get foo"aar"

When executing the SETBIT command to try to set a bitmap, if the bitmap does not exist, or The current size of the bitmap cannot be satisfied. Redis will expand the set bitmap and initialize the values ​​of all unset binary bits to 0. For example:

redis> setbit far 10 1

Since far does not exist, Redis will set the binary bits from 0 to 9 to 0. Because Redis expands the bitmap in bytes, in fact far There are 16 binary bits in total, not 10, and the binary bits 11~15 are also 0.

Based on this situation, when the specified binary bit offset is too large, Redis needs to allocate all memory at once, which may cause the Redis server to block. For example, when storing the user's gender, 1 represents male and 0 represents female, using ID as a binary offset. If the ID starts from 10000000001, you need to subtract 10000000000 from the user ID before storing, otherwise it will cause a waste of memory.

GETBIT

Use the GETBIT command to obtain the value of the binary bit at the specified offset of the bitmap. The time complexity of this command is O(1).

GETBIT key offset

If the entered offset exceeds the maximum offset currently owned by the bitmap, 0 will be returned as the result.

BITCOUNT

The BITCOUNT command can be used to count the number of binary bits with a value of 1 in the bitmap. The time complexity of this command is O(n).

BITCOUNT key [start end]

By default, the BITCOUNT command counts the binary bits in all bytes contained in the bitmap. It can also be used to Select the start parameter and end parameter to let BITCOUNT only count the binary bits within the specified byte range (not the binary offset). For example, you want to count the number of binary numbers with a value of 1 in the two bytes of ar:

redis> bitcount foo 1 2
(integer) 7

The start and end parameters also support the use of negative indexes. The usage below is equivalent to the above:

redis> bitcount foo -2 -1
(integer) 7

BITPOS

By executing the BITPOS command, find the first binary bit set to the specified value in the bitmap and return the offset of this binary bit .

BITPOS key value [start end]

BITPOS also accepts optional start parameters and end parameters, allowing the BITPOS command to only specify bytes Search in binary bits within the range.

redis> get foo"aar"redis> bitpos foo 1
(integer) 1
redis> bitpos foo 0
(integer) 0
redis> bitpos foo 0 1 2
(integer) 8
redis> bitpos foo 1 1 2
(integer) 9
redis> bitpos foo 1 -1 -1
(integer) 17

Handling for boundaries:

• When trying to find a binary value of 1 in a bitmap that does not exist or a bitmap with all bits set to 0 bit, the BITPOS command will return -1 as a result.
• If a binary bit with a value of 0 is found in a bitmap with all bits set to 1, the BITPOS command will return the maximum offset of the bitmap plus 1 as the result

BITOP

Use the BITOP command to perform specified binary bit operations on one or more bitmaps and store the operation results in the specified key. .

BITOP operation destkey key [key ...]

operation 参数的值可以是 AND、OR、XOR、NOT 中的任意一个，这 4 个值分别对应逻辑并、逻辑或、逻辑异或和逻辑非 4 种运算，其中 AND、OR、XOR 这 3 种运算允许用户使用任意数量的位图作为输入，而 NOT 运算只允许使用一个位图作为输入。BITOP 命令在将计算结果存储到指定键中之后，会返回被存储位图的字节长度。

当 BITOP 命令在对两个长度不同的位图执行运算时，会将长度较短的那个位图中不存在的二进制位的值看作 0。

redis> set foo1 bar
OK
redis> set foo2 aar
OK
redis> bitop or res foo1 foo2
(integer) 3
redis> get res"car"

注意：BITOP 可能是一个缓慢的命令，它的时间复杂度是 O(N)，在处理长字符串时应注意一下效率问题。

应用场景

用户行为记录器

用用户 ID 作为偏移量，若用户做了某种行为则通过 SETBIT 将二进制位设置为 1，通过 GETBIT 判断用户是否做了某种行为，通过 BITCOUNT 可以知道有多少用户执行了行为。

用户上线统计

可以使用 SETBIT 和 BITCOUNT 来实现，以用户 ID 作为 key ，假设今天是上线统计功能开放的第一天，ID 为 1 的用户上线后就通过 SETBIT 1 0 1。当要计算此用户的总共以来的上线次数时，使用 BITCOUNT 命令就可以得出的结果。

使用这种方式存储数据，即使 10 年后，1个用户就只占用几百字节的内存，它的处理速度依然很快。如果 bitmap 数据比较大，建议将 bitmap 拆分成多个小的 bitmap 分别进行处理。

更多编程相关知识，请访问：编程入门！！

The above is the detailed content of An in-depth analysis of bitmaps in Redis (bitmap). For more information, please follow other related articles on the PHP Chinese website!