The bitmap
A bitmap is a data structure composed of a large number of bits (each bit can only be 0 and 1), which is mainly suitable for some scenarios to save space and record data meaningfully.
For example, for the access of a large number of bool types, the check-in record of a user in 365 days is 1 and 0. If common key/value is used for storage, a large amount of storage space is required when there are a large number of users.
If you use bitmaps for storage, 365 days a year, 365 bits can be stored, 365 bits translate to 46 bytes (a slightly longer string), which saves a lot of storage space.
The essence of a bitmap is actually a common string, that is, a byte array. You can use get/set to directly obtain and set the content of the entire bitmap, or use getBit /setbit to treat the byte array as a bit array.
Set the string using bitwise operations
We use setbit to set the array of bits, and then get the string.
First of all, we get the two ASCII codes H and E, which are represented in binary as follows.
We can see that the binary code of H is 01101000 and the binary code of E is 01100101. We just need to pay attention to the position where bit is 1, and then setbit,
Note that the order of the bit array and the character bit order are reversed. According to this principle, we calculate the position of each 1 for h character is 1/2/4, and the position of each 1 for E character is 9/10/13/15.
So we’ll use setbit to set an array of bits and set the corresponding 1 at each position (1/2/4/9/10/13/15),
setbit data 1 1
setbit data 2 1
setbit data 4 1
setbit data 9 1
setbit data 10 1
setbit data 13 1
setbit data 15 1
Copy the code0 put whole take
Finally, if you just get the data key, you’ll find that you get exactly he,
The combination of setbit and get is called zeroband fetch. Zeroband is set one bit at a time. The zeroband fetch is to get all the data directly through the key name.
Similarly, we can also carry out zero to zero, zero to zero, lump-sum, which is to set the whole array of bits directly with the string, zero is to obtain the bit by the bit position.
LingCun has the
As can be seen, we set the bit of the array of bits called w in key according to setbit, and only set the value of the three positions 1/2/4 as 1. In the figure below, getbit w 3 obtains the value of the third position, which is 0 by default. If triggered from the perspective of business, it can be understood as: there are four check-in days in total, and no check-in on the third day.
Term has the
Getbit = getbit; getbit = getbit; getbit = getbit; getbit = getbit; getbit = getbit
Pay attention to
-
The redis bit array is automatically expanded. If an offset position is set outside the existing content range, the bit array is automatically expanded to zero, that is, the default value of the expanded bit is 0.
-
If the corresponding byte is a non-printable character, redis-CLI will display the hexadecimal form of the character.
-
A byte is eight bits, and bytes are distinguished from bits.
Count and find (bitcount/bitpos)
Redis provides the statistics instruction bitcount and the bitmap lookup instruction bitpos,
Bitcount counts the number of 1s in a range of locations, and bitpos looks for the first 0 or 1 in a range.
We can count the total number of check-in days by bitcount, and find the first check-in day by bitpos instruction.
If you specify the range parameter [start, end], you can count how many days the user checked in within a certain time range and the day after the user checked in.
Note, however, that the start and end arguments are byte indexes, that is, the range of bits specified must be multiples of 8,
It can’t be arbitrarily specified, so we can’t directly calculate how many check-in days a user has in a given month. If we need to calculate,
You can use the getrange command to fetch the bytes covered by the month and then collect statistics in memory. For example, if 10-12 bytes covered by the month of February, use getrange w 8 12.
127.0.0.1:6379> set w hello OK 127.0.0.1:6379> bitcount W # How many 1's (integer) 21 127.0.0.1:6379> bitcount w 0 0 # The number of bits of 1 in the first character (integer) 3 127.0.0.1:6379> bitcount w 0 1 # The number of bits of 1 in the first two characters (integer) 7 127.0.0.1:6379> bitpos w 0 # The first 0 bit (integer) 0 127.0.0.1:6379> bitpos w 1 # The first 1 bit (integer) 1 127.0.0.1:6379> bitpos w 1 1 1 1 # The first 1 bit (integer) 9 127.0.0.1:6379> bitpos w 12 2 # From the third character, the first 1 bit (integer) 17Copy the codebitfield
The setbit/getbit values are all single bits. If you want to operate on more than one bit at a time, you must use pipes.
After redis3.2, bitfield instruction is provided, which can operate on more than one bit at a time. Bitfield has three sub-instructions, namely GET /set/incrby, which can read and write the specified bit fragment.
However, it can only handle up to 64 consecutive bits. If more than 64 bits are used, multiple sub-instructions are required, and Bitfield can execute multiple sub-instructions at once.
The sample
Let’s do some operations with bitfield on the bit array shown below
127.0.0.1:6379> bitfield w get u4 0 # The result is the unsigned number (u) 1) (integer) 6 127.0.0.1:6379> bitfield w get u3 2 # start with 3 bits, The result is the unsigned number (u) 1) (integer) 5 127.0.0.1:6379> bitfield w get i4 0 The result is the signed number (I) 1) (integer) 6 127.0.0.1:6379> bitfield w get i3 2 # Take 3 bits from the third bit, the result is the signed number (I) 1) (integer) -3Copy the codeSigned number is when you get the first bit in the array of bits is the sign bit, the rest is the value, if the first bit is 1, it’s a negative number,
Unsigned numbers are non-negative numbers with no signed bits. The array of bits obtained is all values. Signed numbers can get up to 64 bits.
Unsigned numbers can only get 63 bits, because the redis protocol integer is a signed number with a maximum of 64 bits and cannot pass 64-bit unsigned values.
If the number limit is exceeded, Redis will tell you that the parameter is wrong.
The above instructions can be combined into one instruction, and you can see that the result is the same,
bitfield w get u4 0 get u3 2 get i4 0 get i3 2
Copy the code
Set to modify
We start with the ninth bit and replace the existing eight bits with eight unsigned digits, essentially replacing the second character from e to A (its ASCII code is 97) and seeing the result become hallo as well
127.0.0.1:6379> bitfield w set u8 8 97
1) (integer) 101
127.0.0.1:6379> get w
"hallo"
Copy the codeincrby
Incrby increments the specified range of bits, that is, ++, which can cause an overflow, an up overflow if a positive number is added, and a down overflow if a negative number is added.
Redis’s default processing is retracting, that is, if there is an overflow, the overflow of the symbol bits will be thrown away. For example, if it is an 8-bit unsigned number 255, it will all become zeros after adding 1. If it is an 8-bit signed number 127, it will overflow to -128 after adding 1.
Again, I’m going to demonstrate incrby in terms of the Hello character
127.0.0.1:6379> set w hello OK 127.0.0.1:6379> bitfield w get u4 2 # The first time is 10 1) (INTEGER) 10 127.0.0.1:6379> bitfield w incrby u4 2 11) (integer) 11 127.0.0.1:6379> bitfield w incrby u4 2 1 1) (integer) 12 127.0.0.1:6379> bitfield w incrby u4 2 1 1) (integer) 13 127.0.0.1:6379> bitfield w incrby u4 2 1 1) (integer) 14 127.0.0.1:6379> bitfield w incrby u4 2 1 1) (integer) 15 127.0.0.1:6379> bitfield w incrby u4 2 1 # 1) (integer) 0Copy the codeBitfield instruction provides overflow policy sub-instruction overflow. Users can choose overflow behavior, default is rewrap, fail, that is, fail to execute, and saturate truncation (SAT), that is, stay at the maximum or minimum value when exceeding the range.
Overflow directives affect only the first instruction that follows, after which the overflow policy becomes the default value wrap.
Saturated truncation
127.0.0.1:6379> set w hello OK 127.0.0.1:6379> bitfield W overflow sat incrby u4 2 11) (integer) 11 127.0.0.1:6379> Bitfield w overflow sat incrby u4 1 1) (integer) 12 127.0.0.1:6379> Bitfield W overflow sat incrby u4 2 1 1) (integer) 13 127.0.0.1:6379> bitfield W overflow sat incrby u4 2 1 1) (integer) 14 127.0.0.1:6379> bitfield W overflow sat incrby u4 2 1 1) (integer) 14 127.0.0.1:6379> Bitfield W overflow sat incrby U4 2 1 1) (integer) 15 127.0.0.1:6379> bitfield w overflow sat incrby u4 2 1 # 127.0.0.1:6379> bitfield W overflow sat incrby u4 2 1 1) (integer) 15 127.0.0.1:6379> bitfield W overflow sat incrby u4 2 1 1) (integer) 15Copy the codeFailure not to execute
127.0.0.1:6379> set w hello OK 127.0.0.1:6379> Bitfield W Overflow fail incrby u4 2 11) (integer) 11 127.0.0.1:6379> 1) (integer) 12 127.0.0.1:6379> Bitfield W overflow fail incrby u4 2 1 1) (INTEGER) 13 127.0.0.1:6379> Bitfield W overflow fail incrby U4 2 1 1) (integer) 14 127.0.0.1:6379> Bitfield W overflow fail incrby U4 2 1 1 Fail incrby u4 2 1 1) (integer) 15 127.0.0.1:6379> Bitfield W overflow fail incrby u4 2 1 # 127.0.0.1:6379> bitfield W overflow fail incrby u4 2 1) (nil) 127.0.0.1:6379> Bitfield W overflow fail incrby u4 2 1 1) (nil)Copy the codeGet, set, and incrby are executed together
127.0.0.1:6379> bitfield w set u4 1 0 get U4 1 incrby u4 2 1 1) (INTEGER) 0 2) (integer) 0 3) (integer) 1 127.0.0.1:6379 > get w \ x04ello ""Copy the code