Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to use the bit bit operation of redis". The editor shows you the operation process through the actual case. The operation method is simple, fast and practical. I hope this article "how to use the bit bit operation of redis" can help you solve the problem.

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

Operation mode: standalone mode

Redis bit operation

Reids bit operation, also known as bit array operation, bitmap, it provides SETBIT, GETBIT, BITCOUNT, BITTOP four commands for manipulating binary array.

First, let's take a look at a wave of basic operation examples.

SETBIT

Syntax: SETBIT key offset value

That is, the command key offset 0max 1

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

GETBIT

Syntax: GETBIT key offset

That is: command key offset

The gitbit command is used to get the binary value on the specified offset of the bit array:

BITCOUNT

Syntax: BITCOUNT key

That is, the command key

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

BITOP

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

That is, the target key key1 key2 of the command operation result.

The bitop command can perform and (bitwise and), or (bitwise OR), xor (bitwise XOR) operations on key of multiple bit arrays, and set the operation result to destkey:

Analysis of underlying data structure

SDS is a data structure in redis called simple dynamic string (Simple Dynamic String), and it is binary secure, and in most cases strings in redis are stored in SDS.

Data structure of SDS:

Struct sdshdr {# record the number of bytes used in the buff array # is also the length of the string saved by SDS int len; # record the number of unused bytes in the buff array int free; # byte array, where the string is stored in char buff [];}

Example of data storage:

Picture source "redis Design and implementation"

Advantages of SDS:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

The time complexity is O (1).

Eliminate buffer overflow

Reduce the number of memory reallocations required when modifying the length of a string

Binary secure API operation

Compatible with some C string functions

For a detailed introduction to SDS, please refer to the article "redis Design and implementation".

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

Picture source "redis Design and implementation"

What we all know is that a byte is stored in eight binary bits, that is, eight zeros or ones, that is, a byte can store decimal 0,127 numbers, that is, all numbers, uppercase and lowercase 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, starting with:

0 0 0

The bit operation is to set 0 or 1 on the corresponding offset offset, such as setting the third bit to 1, that is:

000010000 # corresponding to redis operation: setbit key 3 1

On this basis, if you want to set 1 at a location with an offset of 13, that is:

The storage in setbit key 13 1 # corresponding to redis is: 0 010 | 0 000 0 | 0 000 0 | 1 000 0

Time complexity

Time complexity of GETBIT command O (1)

Time complexity of STEBIT command O (1)

Time complexity of BITCOUNT command O (n)

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

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

Get which byte to write to the bitwise array: 10086 / 8x1260, the byte that needs to be written to the subscript 1260 of the array

To get the number of bits to write to this byte: 10086 mod 8 = 6, you need to write to this byte with the subscript 6, or bit 7.

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

The BITCOUNT command needs to traverse all the elements of the entire bit array to figure out how many are with a value of 1. Of course, redis has a set of complex optimization algorithms for redis to execute the bitcount command for big data's bit, but the core idea is still this way, just to reduce the number of partial traversal queries. For example, if you take 128 bits as a traversal, the number of times he traverses is all digits divided by 128.

The BITTOP command is executed in different ways according to different operations. For example, for AND operation, you need to check the bit value of 1.

Storage space calculation

According to the above introduction, I believe you already know how the memory size of the data stored in the redis-based bit array data structure is calculated. For example, if there is 10 billion data, then it needs a byte array:

1000000000 / 8 / 1024 / 1024 ≈ 119.21MB

In other words, 1 billion of the data storage only needs about the memory space of 119MB, which is no problem for the current 16G, 32G cluster version of redis.

It should be noted that if you do not have a large amount of data, then do not make the initial offset very large, which also takes up space. For example, we only need to store a few hundred pieces of data, but the offset is very large. This will cause a lot of memory space waste.

Application scenario

In the actual project development, there are many businesses that are suitable to be realized by redis's bit.

User check-in scenario

Daily date string as a key, user Id as offset, statistics of daily user check-ins and total number of user check-ins

Active user statistics

The number of daily active users, monthly active users and retention rate can be stored in the redis bit array, or the date of each day is used as the key. If the user is active, write offset as the bit value of the user id.

The same is true of the number of monthly active users.

Statistics on whether users are online and the total number of people online

Also use a bit array, the user's id mapping offset, online identity is 1, offline identity is 0. It can realize the query of users online and the statistics of the total number of people online.

The global message of users in APP prompts Little Red Dot

At present, most APP have the function of internal message. When there is a message, it will prompt a small red dot to indicate that the user has a new message.

This is the end of the introduction to "how to use the bit bit of redis". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.