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

This article mainly introduces the relevant knowledge of how to use Redis Bitmaps, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this article on how to use Redis Bitmaps. Let's take a look at it.

Redis version: 6.2.6

First, a brief introduction to Bitmaps

A bitmap is not an actual data type, but a set of bit-oriented operations defined on the String type. Because strings are binary-safe blob, and their maximum length is 512 MB, they are suitable for setting up to 2 ^ 32 different bits.

The above is an introduction to Bitmaps on the official website of Redis. Simply understand that Bitmaps is a series of instructions provided by Redis to directly manipulate String bits. For example, we now have a string: "a"

127.0.0.1 get 6379 > set K1 aOK127.0.0.1:6379 > get K1 "a"

The binary of an is 0110 0001. We can use the [GETBIT key offset] instruction to get the value of the corresponding bits of this string:

127.0.0.1 getbit K1 0 (integer) 0127.0.1 0.1 getbit 6379 > getbit K1 (integer) 1127.0.0.1 getbit 6379 > getbit K12 (integer) 1127.0.0.1 getbit 6379 > getbit K1 3 (integer) 0127.0.0.16379 > getbit K1 4 (integer) 0127.0.1 0.1 getbit 6379 > getbit K1 5 (integer) 0127.0.1 1 getbit 6379 > getbit K1 6 (integer) 0127.0.1 Rod 6379 > getbit K1 7 (integer) 1

The offset in this instruction represents the offset. As shown above, the offset is 1 bit, 2 bits, 7 bits is 1, and the other bits are 0. The corresponding binary is: 0110 0001, which is the ASCII value of the character a.

Next, we can use the [SETBIT key offset value] instruction to change the value of a bit, such as:

127.0.0.1 setbit 6379 > get K1 6 1 / / offset 6 bits, set to 1 (integer) 0127.0.1 get K1 "c"

As above, we set the position with an offset of 6 to 1, so that the binary object becomes: 0110 0011, corresponding to the character "c". We change the value of the string by directly manipulating the bits of the string.

Bitmaps is a tool for manipulating strings by bit in redis. According to this tool, we can use strings as a set of binary arrays. Let's give a simple example:

How do I record the online status of a billion users?

Here, we use a string of binaries to record the login status of these billion users. Each bit in binary represents a user. 0 means not logged in, 1 means logged in, and each login or logout uses Bitmaps to update the corresponding bit value. The final result looks like this:

We used the above string of binaries to record the login status of these billion users. Why would we do that? The main reason is to save space and read or update quickly.

Let's calculate the amount of storage space required for this storage method:

One billion users, each user accounts for 1 bit of space required = 1000000000 bit = 1000000000 / 8 / 1024 / 1024 = 119 MB

Take MySQL as an example, the amount of space required for storage:

Suppose there are only two fields: user id, presence user id is BIGINT type, size is 8 Bytes presence using TINYINT type, size is 1 Bytes space required = 1000000000 * (8 + 1) Bytes = 9000000000 Bytes = 8583 MB

The gap is obvious and it is easy to understand that the minimum units of Hash storage using MySQL or Redis are bytes, which naturally cannot be compared with the direct operation bits.

The above is a brief introduction to Redis's Bitmaps, and then we will introduce the basic commands and applications of Bitmaps.

II. Operation of Bitmaps

SETBIT

Time complexity: O (1)

SETBIT key offset value

Update the value at the offset location of the specified key. Value can only be 0 or 1.

It should be noted that:

1. Offset represents the offset, with a maximum of 232-1 (because the maximum is 512MB, the symbol occupies 1 bit).

2. Allocate memory. After one allocation, there will be no allocation overhead for the subsequent same key. The official website describes: on 2010 MacBook Pro, it takes about 300ms to set the number of digits 232-1 (512MB allocation).

3. Return the value and return the value before the corresponding offset operation.

GETBIT

Time complexity: O (1)

GETBIT key offset

Returns the bit value stored at offset in the string value of key.

It should be noted that:

Returns the integer 0 when key does not exist or offset is out of range

BITCOUNT

Time complexity: O (n)

BITCOUNT key [start end [BYTE | BIT]]

Calculate the number of 1s in a string

Example: 127.0.0.1 set aOK127.0.0.1:6379 > BITCOUNT K1 (integer) 3127.0.0.1 BITCOUNT 6379 > set K1 aaOK127.0.0.1:6379 > BITCOUNT K1 (integer) 6127.0.1 set 6379 > BITCOUNT K100 (integer) 3127.0.0.1 BITCOUNT 6379 > BITCOUNT K101 (integer) 6127.0.1 BITCOUNT 6379 > BITCOUNT K10-1 (integer) 6

It should be noted that:

1. Start and end parameters refer to Byte, not bit. Byte or bit can only be specified after version 7.0 on the official website.

2. If key does not exist, it will be 0.

3. The time complexity is O (n), which refers to the amount of data between start and end parameters, so when the amount of data is too large, make good use of start and end, or build more key.

BITOP

Time complexity: O (n)

BITOP operation destkey key [key...]

Perform bitwise operations between multiple keys (including string values) and store the results in the target key

Among them operation are: AND,OR,XOR and NOT

Destkey refers to the target key. After bitwise operation, the subsequent key is stored in the destkey.

/ / AND, bitwise and 127.0.0.1 set 6379 > set K1 aOK127.0.0.1:6379 > set K2 aaOK127.0.0.1:6379 > set K3 aaaOK127.0.0.1:6379 > bitop and dk1 K1 K2 K3 (integer) 3127.0.0.1 set 6379 > get dk1 "a\ x00\ x00"

As in the example above, the bitwise and subsequent results of K1, K2PowerK3 are stored in dk1.\ X00 after dk1 is hexadecimal, and a\ X00\ X00 is converted into binary: 0110 0001 0000 0000 0000.

/ / OR, bitwise or 127.0.0.1 integer > bitop or dk2 K1 K2 K3 (integer) 3127.0.0.1 integer > get dk2 "aaa"-/ / XOR, bitwise OR 127.0.0.1 aaa > bitop xor dk3 K1 K2 K3 (integer) 3127.0.0.1 integer 6379 > get dk3 "a\ x00a"-/ NOT Reverse 0110 0001 take reverse-> 1001 1110-> hexadecimal\ x9e127.0.0.1:6379 > bitop not dk4 K1 (integer) 1127.0.0.1 integer 6379 > get dk4 "\ x9e"

BITPOS

Time complexity: O (N)

BITPOS key bit [start [end [BYTE | BIT]

Returns the position of the first bit in the string set to 1 or 0.

Example 127.0.0.1 setbit K1 41 (integer) 0127.0.0.1 setbit K1 13 1 (integer) 0127.0.0.1 setbit 6379 > bitpos K11 (integer) 4127.0.0.1 bitpos K1 100 (integer) 4127.0.1 0.1 6379 > bitpos K11 (integer) 13

It should be noted that:

1. The parameters start and end here refer to Byte. You can specify Byte or bit after version 7.0.

2. Bitpos, setbit and getbit follow the same bit position convention.

3. When querying 1, the key that does not exist or the string in the corresponding range is all 0, and-1 is returned.

4. When querying 0, there are three special cases:

K2 = 1111 1111, K3 does not exist-/ / No range or only start is specified, and the values are all 1, so the position of the rightmost 1 will be found out. Can be regarded as the right side filled with 0127.0.0.1 BITPOS 6379 > BITPOS k20 (integer) 8 murmurband / no specified range or only specified start, and key does not exist. It returns 0127.0.0.1 start 6379 > BITPOS K30 (integer) 0Collector / specified range. And there is no 0 in the range. Return-1127.0.0.1 BITPOS 6379 > integer K211 (integer)-1

BITFIFLD

BITFIELD key [GET encoding offset] [SET encoding offset value] [INCRBY encoding offset increment] [OVERFLOW WRAP | SAT | FAIL]

This command treats the Redis string as an array of bits and can handle specific integer fields with different bit widths and any non-(necessary) alignment offset. The command has get, set, incrby operations.

That is to say, you can use this command to process strings in bitwise segments, for example:

127.0.0.1 aaaOKaaa0110 6379 > set K1 aaaOKaaa0110 00010110 00010110 0001

The binary of K1 is shown in the table above, and then we use the BITFIFLD command to manipulate K1

GET:

/ / U8 = unsigned + 8 bits; 0 = the result obtained from bit 0 is: 0110 0001, unsigned conversion to decimal is 97127.0.1 get 6379 > BITFIELD K1 U8 01) (integer) 97MB / i8 = signed + 8 bits 1 = start from the first bit / / result = 1100 0010, converted to decimal with symbols is-62 (do not understand why-62 can see the complement) 127.0.1 1 get 6379 > BITFIELD K1 get i8 11) (integer)-62

SET:

/ / change bit 0-7 to 98, that is, 0110 0010 This corresponds to b. So the first character becomes b127.0.0.1 set 6379 > BITFIELD K1 set u8 0981) (integer) 97127.0.0.1 baa > get K1 "baa"-127.0.1 baa 6379 > BITFIELD K1 set u8 # 98 / / # 1 means to start from the second 8 bits. Shi 1) (integer) 97127.0.0.1 bba 6379 > get K1 "bba"

INCRBY: increasing or decreasing

/ /-1 represents an increasing or decreasing number, and the 0-7 bit of K1 decreases by 1. The result is that 97 Magi K1 becomes "aba" 127.0.0.1 get 6379 > get K1 "bba" 127.0.0.1 incrby 6379 > BITFIELD K1 incrby u8 0-11) (integer) 97127.0.0.16379 > get K1 "aba" 127.0.0.1 incrby 6379 > BITFIELD K1 incrby u8 # 1-11) (integer) 97127.0.1 integer "aaa"

There is overflow control when using INCRBY for incrementing or decrementing operations, and Redis provides three behaviors to control overflows:

WRAP: surround, in the case of unsigned integers, line wrapping is like modulo on the maximum value that an integer can contain

/ / take U8 as an example, unsigned, 8 digits, then the maximum value is 256127.0.0.1overflow WRAP incrby 6379 > BITFIELD K1 get u8 01) (integer) 97127.0.0.1 overflow WRAP incrby 6379 > BITFIELD K1 overflow WRAP incrby u8 0 2561) (integer) 97127.0.1overflow WRAP incrby 6379 > BITFIELD K1 overflow WRAP incrby u8 0257 / 97q257 = 97q257256 = 981) (integer) 98127.0.1purl 6379 > BITFIELD K1 overflow WRAP incrby u8200200 / 98 + 200 = 298256 = 421) (integer) 42

In the case of sign, overflow up to a negative value and down to a positive value, taking i8 as an example 127 + 1 to-128

127.0.0.1 get 6379 > set K1 aaaOK127.0.0.1:6379 > BITFIELD K1 get u8 01) (integer) 97127.0.1 BITFIELD i8 0301) (integer) 127127.0.1 incrby i8 01 1) (integer)-128127.0.0.16379 > BITFIELD K1 incrby i8 0-11) (integer) 127

SAT: use the saturation algorithm, which is set to the minimum integer value for underflow and the maximum integer value for overflow.

/ / U8, maximum and minimum 0127.0.0.1 get 6379 > set K1 aaaOK127.0.0.1:6379 > BITFIELD K1 get u8 01) (integer) 97127.0.1 overflow SAT incrby u8 0 200001) (integer) 255127.0.1 get 6379 > BITFIELD K1 overflow SAT incrby u8 0-2131231) (integer) 0

FAIL: in this mode, no action is performed on detected overflows or underflows. The corresponding return value is set to NULL to send a conditional signal to the caller. That is, an overflow returns NUll.

127.0.0.1 get 6379 > set K1 aaaOK127.0.0.1:6379 > BITFIELD K1 U8 01) (integer) 97127.0.1 overflow FAIL incrby u8 0 2001) (nil) 127.0.1 overflow FAIL incrby u8 0 2001) (nil)

In addition, the above BITFIELD commands can be used together:

127.0.0.1 get 6379 > BITFIELD K1 overflow FAIL incrby u8 0-98 get u8 01) (nil) 2) (integer) 97

BITFIELD_RO

A read-only variant of the BITFIELD command. It is just like the original BITFIELD, but only accepts get subcommands and can be safely used with read-only copies.

Application of Bitmaps

In the above description, it is introduced that Bitmaps can record the online status of a user. What other functions can be done with it?

First, let's summarize the characteristics of Bitmaps:

There are only 0 and 1 states (the information described is limited)

Takes up very little memory.

Extremely fast access speed (set,get operation time complexity is O (1))

Based on these characteristics, we can use Bitmaps to determine whether the data exists in a collection, and it can also be used to record some user behaviors such as login or viewing, closing, check-in of a page, and so on. Next, let's give some more common examples.

Daily active users statistics

How to count the number of users logged in by the current system every day?

Using Redis's Bitmaps, set the system name + date to key. For example, in zcy20211215,value, use the user's Id as the offset, use 0 and 1 to record whether the user has logged in on the same day, and log in to set the corresponding bit to 1.

After doing this, you can get a Bitmaps every day, and if you want to get the number of users logged in on a given day, you can simply use the BITCOUNT operation.

If you want to count the users who have logged in in the past 30 days, you can use the BITOP AND operation to bitwise and operate the 30-day Bitmaps.

Bloom filter

The essence of Bloom filter is Hash mapping algorithm + Bitmaps.

As shown in the figure, a value enters the Bloom filter and goes through several Hash algorithms to get its mapping position on the Bitmap. When all positions are 1, the value is considered to be in the filter, otherwise it does not exist.

Marketing data statistics

There are many scenarios in which Bitmaps can be used in marketing systems:

The use of user profile information, a user has many tags and unlimited expansion, such as gender, whether or not a programmer, single, rent, whether to keep a pet, we can consider using Bitmap storage and use.

The user's behavior, whether to click on the ad, whether to browse to the bottom, whether to get a coupon and other behaviors are stored in a Bitmap, which is similar to the user profile above.

Here's a small example of the use of Bitmaps in a marketing system:

Suppose we have an e-commerce application with 100 million users, and the product raises the following demand:

When all male users enter the home page of the application, a pop-up window for anti-hair loss health products pops up.

The demand is very simple. An API is completed. When the user enters the API, he / she calls the API to obtain the advertisement. The database in the API is queried to determine whether the advertisement is male, whether the advertisement content is returned or not.

At this time, the product feels that this push is not accurate enough, and not all men will lose their hair, so the condition is added: programmers, our needs become:

When all male and professional programmers enter the home page of the application, a pop-up window for anti-hair loss health products pops up

After adding a condition is still very simple, the user's gender and occupation information is very likely to exist a table, but also a query.

However, male programmers have a high probability of hair loss, but they may not all be able to afford anti-hair loss health products. At this time, they need to push more accurately, so add another condition: the average consumption on the platform last month is more than 500. This condition is not in the same table as the above two conditions, male and programmers. If you use the above scheme, add another DB query. Slow and expensive to the database, the effect of Bitmaps is obvious at this time.

The current condition is that men, programmers and all spent more than 500 on the platform last month.

In this scenario, if you want to use Bitmaps, you need to load the data into Redis first. You can use a simple and rough method to directly traverse the database and load the tag information you need into Redis:

/ / user tag loading pseudo code public Boolean loadUserLabel () {/ / user gender bitmap data loading String key = "user_label_sex_male"; List users = userDao.queryUser () Users.forEach (t-> {if (Objects.equals (t.getSex (), "male")) {jedis.setbit (key,t.getId (), "1");}}); return true;}

After the above code, the user's gender is loaded into redis's bitmap, and other tags such as occupation and consumption are more than 500, similar to this.

After we have the user tag information we need in Redis, we can start to use it, like our above requirements, we can use the AND operation of the BITOP command to generate a Bitmap that meets these three conditions at the same time for men, programmers, and monthly consumption of more than five hundred. Here we only have three conditions, which can be simply checked three times in the code:

/ / the pseudocode public Response getHomepageAds (User user) {/ / is written here. In practice, the dynamic configuration is String maleKey = "user_label_sex_male"; String programmerKey = "user_label_occupation_programmer"; String spendMonth600Key = "user_label_spend_month_500". / / to bitmap, if the bit is 1, the condition if (jedis.getbit (maleKey,user.getId ()) & & jedis.getbit (programmerKey,user.getId ()) & & jedis.getbit (spendMonth600Key,user.getId () {return "content";} return "no advertising";}

The above is a small example of the application of Bitmap in the marketing system, based on which many extensions can be made, such as the real-time incremental loading of each tag, the dynamic configuration of the binding relationship between each advertisement and tag, the automatic generation of tags and so on.

Next, we can take a look at the application of Bitmaps in user behavior records, and now the product proposes a new requirement:

I want to know how many users clicked into our pop-up ads.

After clicking the pop-up advertisement, the front end sends the request, and the back end records the user's click status:

/ / pseudo code public Response getHomepageAds (User user) {String adActionKey = "homepage_ad_action_open"; jedis.setbit (adActionKey,user.getId (), "1");}

If you want to count the numbers later, you can use the BITCOUNT command directly. The records of other behaviors are similar to this, such as whether to drag to the bottom, whether the dwell time is greater than n seconds, and so on.

Collaborative mapping

This example comes from Redis's official website, which is r/place, a game played by Reddit on April Fool's Day in 2017, which is a very interesting Bitmaps application.

Game introduction:

An artboard with 1000 * 1000 pixels. Each player can edit one pixel every five minutes (there are 16 colors to choose from). The number of players involved is unlimited and ends in 72 hours.

The game is simple, everyone only needs to edit the color of the pixel, and 17 years of activity finally formed the painting (here is part of it):

There are one million pixels in it. According to statistics, at least 100,000 people participated in the game, and the concurrent volume is very high. How to ensure availability? Reddit uses Redis's Bitmap here:

First define the position of the pixels in the artboard, using x to represent Abscissa, y to represent ordinate, and the position of each pixel corresponds to an offset of Bitmap.

When the user edits the pixel, the location information (xPowery) and color information are stored in Bitmap, and the artboard data is also read directly using Bitmap.

The idea is very simple, mainly to solve the following two problems:

1. The mapping relationship between coordinates and Bitmap? How the coordinates are converted to the offset,offset of Bitmap and how to convert the XMagne y coordinates in the artboard.

2. How to directly use Bitmaps to store the information of a coordinate point? The color is stored here.

The project goes like this:

1. Since the total number of pixels is 1 million, a formula is designed: X + 1000y = offset.

When storing, convert (xQuery y) to offset, for example, (1meme2) position, then offset = 1 + 2000 = 2001

When reading, convert offset to (xjingy), for example, offset = 9008, then x = 9008 1000 = 8recovery = 9008 / 1000 = 9

2. Use the BITFIELD command of Bitmaps to segment:

Players can choose a total of 16 colors, so each point needs at least 4 digits, so when using BITFIELD, the digit field should be U4.

This is what it looks like:

The above is a brief introduction of the game for the Bitmaps application, the specific implementation and source code see the Reddit team's blog at the end of the article.

Using the BITFIELD command, you can also determine whether the data is duplicated, for example, if there are 1 billion integers, how to find the duplicate data? Each number can be given 2 digits, 01 indicates one occurrence, and 10 indicates repetition.

IV. Small expansion

How do I use Bitmaps when the user Id is not a self-adding Id?

In actual development, the user's Id may not be self-increasing, such as using the snowflake algorithm, or the Id generated by the UUID tool, in this case, it is not possible to directly use Bitmaps, the offset is too large. At this time, you can refer to the Bloom filter and design a mapping algorithm for Id to map the user Id within a certain range.

How to save space when using Bitmaps for persistent storage?

Use compression algorithms, such as the RLE algorithm

When using Bitmaps, there will be a large number of continuous location data duplications, which have room for compression. For example, if the first 1000 bits are all zeros, you only need to save 1000 zeros instead of 00000. Deposit a thousand of them like this.

This is the end of the article on "how to use Redis Bitmaps". Thank you for reading! I believe you all have a certain understanding of the knowledge of "how to use Redis Bitmaps". If you want to learn more knowledge, you are welcome to follow the industry information channel.

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.