This article will share with you the advanced redis feature: bit manipulation.

The redIS test code in this paper is based on the following environment:

Operating system: Mac OS 64-bit version: Redis 5.0.7 64-bit Running mode: Standalone Mode

Redis bit operation

Reids bit operation is also called bit array operation or bitmap. It provides SETBIT, GETBIT, BITCOUNT and BITTOP commands to operate binary bit arrays.

Let’s start with an example of a basic operation:

SETBIT

Syntax: SETBIT key offset value

That is, the key offset is 0/1

Setbit the setbit command is used to write the binary value of the offset specified in the bit array. The offset counts from 0 and only 1 or 0 can be written. Writing to values other than 0 and 1 fails:

GETBIT

Syntax: GETBIT key offset

That is, offset of the command key

The gitbit command is used to obtain the binary value at the specified offset of the bit array:

BITCOUNT

Syntax: BITCOUNT key

Command key

The bitcount command is used to obtain the number of bits in the bitarray with the value of 1 for the specified key. Previously, we wrote offset 0 as 1, offset 10 as 1, and offset 8 as 0:

BITOP

BITOP operation destkey key [key…]

Command operation Result Target key key1 key2…

The bitop command can perform and (bitwise and), OR (bitwise or), and xOR (bitwise xor) operations on keys of multiple bits, and set the operation result to destkey:

Analysis of underlying data structures

SDS is a data structure in REDIS, called Simple Dynamic String, and it is a binary safe. In most cases, the strings in REDis are stored by SDS.

SDS data structure:

Struct SDSHDR {# record the number of bytes used in the buff array # is also the length of the string stored by SDS int len; Buff array number of unused bytes int free; Char buff\[\]; }Copy the code

Data store example:

Advantages of SDS:

1. Time complexity is O(1)
2. Prevent buffer overflow
3. Reduces the number of memory reallocations required to modify the string length
4. Binary safe API operations
5. Compatible with some C string functions

The bit array in Redis is stored in the String data format, while the String object uses the SDS simple dynamic String data structure mentioned above.

It is known that a byte is stored in eight binary bits, that is, eight zeros or ones. That is, a byte can store decimal digits from 0 to 127, which contains all digits, upper and lower case letters, and punctuation marks.

1Byte=8bit 1KB=1024Byte 1MB=1024KB 1GB=1024MB

In the redis storage world, each byte is also 8 bits, starting with:

0, 0, 0, 0, 0Copy the code

The bit operation is to set 0 or 1 at the corresponding offset, such as setting the third bit to 1, i.e.

0 0 0 0 1 0 0 0 0Copy the code

On this basis, if you want to set 1 at the offset of 13, that is:

Setbit stored as in the corresponding redis key 1 # 13:1 0 0 0 | 0 0 0 0 | 0 0 0 0 | 1 0 0 0Copy the code

Time complexity

GETBIT command time complexity O(1)

STEBIT Command time complexity O(1)

BITCOUNT Command time complexity O(n)

BITOP command time complexity O(n), O(n2)

The time complexity of the GETBIT and SETBIT commands is O(1). When executing a SETBIT key 10086 1, the reids are calculated as follows:

Get which byte in the bit array to write: 10086÷8=1260, need to write in place of the array subscript 1260 bytes

Get the number of bits to write to the byte: 10086 mod 8 = 6, need to write to the byte subscript 6, that is, the seventh bit.

We can clearly see from these two calculation methods that the GETBIT and SETBIT of bit operation are constant calculation, so its time complexity is O(1).

The BITCOUNT command needs to iterate over all the elements of the entire bit array to figure out how many elements with a value of 1. Of course, redis has a set of complex optimization algorithms for executing BITCOUNT command for big data bits, but the core idea is still the same meaning, just to reduce part of the traversal query times. For example, if it traverses 128 bits once, its traversal number is all the bits divided by 128.

The BITTOP command has different execution modes according to different operations. For example, for the AND operation, you need to look at the bit value of 1.

Storage space calculation

We have already seen how to calculate the memory size of data stored by redis bitarray data structure. For example, if there are 10 billion bytes of data, it requires an array of bytes:

1000000000 present 8 present 1024 present 1024 material 119.21 MB

That’s 119MB of memory for a billion bytes of data, which is fine with the 16GB or 32GB clustered redis.

Note that if you have a small amount of data, do not make the initial offset very large, which also takes up space, for example, we only need to store a few hundred data, but the offset is very large, which will cause a lot of memory space waste.

Application scenarios

In the actual project development, a lot of business is suitable to use Redis BIT to achieve.

User check-in scenario

The date character string of each day is used as a key, and the user Id is used as the offset. The total number of daily user check-ins is counted

Active User statistics

The user’s daily activity, monthly activity and retention rate can all be stored by redis bit array. The date of each day is still used as the key. When the user is active, offset is written as the bit value 1 of the user ID.

The same is true of moonliving.

Whether users are online and the total number of online users

Again using a bit array, the user’s ID is mapped with an offset of 1 for the online identifier and 0 for the offline identifier. Can realize the user up and down online query and total online statistics

The global message of the user in the APP prompts a small red dot

Now most apps have the function of in-site message, when there is a message, it will prompt a small red dot, on behalf of the user has a new message.