How to use redis bit operations

The redis test code in this article 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 and bitmap. It provides four commands: SETBIT, GETBIT, BITCOUNT, and BITTOP for operating binary bit arrays.

Let’s take a look at a basic operation example

SETBIT

Syntax: SETBIT key offset value

That is: Command key offset 0/1

The setbit command is used to write the binary bit setting value of the specified offset in the bit array, The offset starts counting from 0, and only 1 or 0 is allowed to be written. If a value other than 0 and 1 is written, the writing fails:

GETBIT

Syntax: GETBIT key offset

That is: Command key offset

The gitbit command is used to obtain Binary value at the specified offset in the bit array:

BITCOUNT

Syntax: BITCOUNT key

That is: Command key

The bitcount command is used to get the number of binary bits with a value of 1 in the bit array of the specified key. Before we wrote the offset 0 has a value of 1, offset 10 has a value of 1, and offset 8 has a value of 0:

BITOP

Syntax: BITOP operation destkey key [key...]

That is: Command operation result target key key1 key2...

bitop The command can perform and (bitwise AND), or (bitwise OR), xor (bitwise exclusive OR) operations on the keys of multiple bit arrays, and set the operation results to destkey:

Underlying data structure analysis

SDS is a data structure in redis, called Simple Dynamic String, and it is a binary Safe, in most cases strings in redis are stored using SDS.

Data structure of SDS:

struct sdshdr {   #记录buff数组中已使用字节的数量   #也是SDS所保存字符串的长度   int len;   #记录buff数组中未使用字节的数量   int free;   #字节数组，字符串就存储在这个数组里   char buff[];  }

Data storage example:

##Picture source "Redis Design and Implementation"

## Advantages of #SDS:

Hongmeng official strategic cooperation and co-construction - HarmonyOS technology community
Time complexity is O(1)
Prevent buffer overflow
Reduce the number of memory reallocations required when modifying the string length
Binary safe API operation
Compatible with some C string functions

For a detailed introduction to SDS, please refer to "Redis Design and Realization" article.

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

Picture source "Redis Design and Implementation"

Everyone knows that a byte is stored with 8 binary bits, that is 8 0s or 1s, that is, one byte can store decimal numbers from 0 to 127, which includes all numbers, English upper and lower case letters, and punctuation marks.

1Byte=8bit

1KB=1024Byte

1MB=1024KB

1GB=1024MB

Bit array In the redis storage world, each byte is also 8 bits, and the initial value is:

0 0 0 0 0 0 0 0

The bit operation is to set 0 or 1 on the corresponding offset offset, for example, set the third bit to 1, that is:

0 0 0 0 1 0 0 0  #对应redis操作即：  setbit key 3 1

Based on this, if you want to set the offset to 13 The position is set to 1, that is:

setbit key 13 1  #对应redis中的存储为：  0 0 1 0 | 0 0 0 0 | 0 0 0 0 | 1 0 0 0

Time complexity

##GETBIT command time complexity O(1)

STEBIT command time complexity O(1)

BITCOUNT command time complexity O(n)

The time complexity of the BITOP command is O(n), O(n2)

Let’s look at why the time complexity of the GETBIT and SETBIT commands is O(1). When we When executing a SETBIT key 10086 1 value, reids are calculated as follows:

Get which byte to be written in the bit array: 10086÷8=1260, which needs to be written to the subscript of the bit array The byte of 1260

Gets the number of this byte to be written: 10086 mod 8 = 6. It needs to be written to the index of this byte which is 6, that is, the 7th bit.

Through these two calculation methods, you can clearly see that GETBIT and SETBIT of bit operations are constant calculations, so their time complexity is O(1).

The BITCOUNT command needs to traverse all the elements of the entire bit array to calculate how many elements have a value of 1. Of course, redis will have a set of complex optimization algorithms for executing the bitcount command on bits with big data, but the core The idea is still the same, it is nothing more than reducing the number of partial traversal queries. If 128 bits are explicitly used as one traversal, then the number of times he needs to traverse is equal to all the digits divided by 128.

The BITTOP command has different execution methods according to different operations. For example, for AND operation, you need to check the bit value is 1.

Storage Space Calculation

Based on the above introduction, we can know how to calculate the memory size occupied by using the Redis-based bit array data structure to store data. For example, if there are 10 billion data, then the byte array it requires:

1000000000÷8÷1024÷1024≈119.21MB

That is, only about 119MB of memory is needed to store 1 billion data Space, this is no problem at all for the 16G and 32G cluster versions of redis that are now available.

It should be noted that if the amount of your data is not large, then don’t make the starting offset very large. This will also take up space. For example, we only need to store a few hundred pieces of data, but The offset is very large, which will cause a lot of waste of memory space.

Application scenarios

In actual project development, there are many businesses that are suitable to be implemented using redis bits.

User sign-in scenario

The daily date string is used as a key, the user ID is used as the offset, and the daily user sign-in status is counted, and the total user sign-in number

Statistics on the number of active users

User daily activity, monthly activity, retention rate, etc. can be stored using redis bit arrays, or use the daily date as the key. Write when the user is active Enter offset as the bit value 1 of the user ID.

The same goes for monthly living expenses.

Whether the user is online and the total number of people online

Use the same bit array, set the bit offset of the user ID mapping to 1 to indicate online, and to 0 Indicates offline. This can realize user online and offline queries and statistics of the total number of people online

The global message prompt of users in the APP is a red dot

Now most APPs have in-site With the message function, when there is a message, a small red dot will be prompted, indicating that the user has new messages.

The above is the detailed content of How to use redis bit operations. For more information, please follow other related articles on the PHP Chinese website!