Introduction Bitmap elicits bitmap command Details Bitmap application scenarios How can bitmaps store hundreds of millions of bytes of data

 

In our normal development process, there will be some bool data that need to be accessed, for example, the user’s one-year check-in record, signed 1, not signed 0, to record 365 days. If ordinary keys/values are used, 365 keys/values are recorded for each user. When hundreds of millions of users are used, the storage space required is staggering. To solve this problem, Redis provides a bitmap data structure so that daily check-in records occupy only one bit, 365 days is 365 bits, and 46 bytes (a slightly longer string) can be fully accommodated, which saves a lot of storage space.

 

This bitmap data structure is of type String

Muzidao :0>set muzidao"OK" muzidao :0>bitcount muzidao #Copy the code

I have drawn the binary diagram of Muzidao below, it is clear at a glance, there are many operations, please read it

Each letter corresponds to 8 bits of binary code, less than 8 bits before the automatic completion of 0, the number of 1s is indeed 31

BITCOUNT key [start end]

Counts the number of bits set to 1 in the given string.

In general, the entire string given will be counted, and by specifying additional start or end arguments, you can make counting happen only on specific bits.

For example, -1 indicates the last byte, -2 indicates the penultimate byte, and so on.

A BITCOUNT operation on a nonexistent key results in 0.

Return value: Number of bits to be set to 1.
0>bitcount muzidao 0 5 # bitcount muzidao 0Copy the code

GETBIT key offset

Gets the bit at the specified offset for the string value stored by key.

Returns 0 if offset is greater than the length of the string value, or the key does not exist.

Return value: the string value specifies the bit at the offset.
Muzidao :0>getbit muzidao 0 # offset 1 = 1Copy the code

SETBIT key offset value

Sets or clears the bits at the specified offset for the string value held by key.

Bits can be set or cleared depending on the value argument and can only be 0 or 1. Abnormal other values

The offset argument must be 0 to 2^32 (the bit mapping is limited to 512 MB).

For SETBIT operations that use a large offset, memory allocation can cause the Redis server to block.

Return value: The string value specifies the bits originally stored at the offset.
1"0" ali cloud :0>setbit muzi 0 2 # Error, cannot set 2"ERR bit is not an integer or out of range" Ali cloud :0>setbit muzi 0 0" 0" ali cloud :0>getbit muzi 0" 0" ali cloud :0>getbit muzi 0" 0" ali cloud :0>getbit Muzi 0" 0"Copy the code

When we set multiple offsets, the data becomes hexadecimal

Let’s see by command

0>get muzi"�Copy the code
BITPOS key [start end]

Returns the first offset in the string set to 1 or 0.

Returns a position, treating the string as an array of bytes from left to right, with the first qualifying byte at position 0, 8, 16, +8 and so on

Bitpos muzidao 1 :0>bitpos muzidao 1 :0>bitpos muzidao 1 :0 Bitpos muzidao 1 2 # muzidao 1 2 # muzidao 2 # muzidao 2 # muzidao 1Copy the code

New features in version 3.2

BITFIELD key    [GET type offset]

BITFIELD key    [SET type offset value]

BITFIELD key    [INCRBY type offset increment] 

BITFIELD key    [OVERFLOW WRAP|SAT|FAIL]

The BITFIELD command can operate on more than one bit range simultaneously in a single call: it takes a list of operations to be performed as arguments and returns as a reply an array in which each element is the result of the corresponding operation.

The BITFIELD command supports up to 64 – and 63-bit unsigned integers. The 63-bit limit on unsigned integers is due to the Redis protocol’s inability to return 64 – bit unsigned integers.

Bitfield muzidao get i4 0 # I: signed bit 4: consecutive 4 bits 0: start position 1) "6" Bitfield muzidao get i4 2 # I: bitfield muzidao get u4 0 #u: bitfield muzidao get u4 0 # I: bitfield muzidao get u4 2 1) "11" aliyun :0>bitfield muzidao get i4 0 get i4 2 get U4 0 get U4 2 1) "6" 2) "5" 3) "6" 4) "11" aliyun :0>bitfield muzidao get u64 2 1"ERR Invalid bitfield type. Use something like i16 u8. Note that u64 is not supported but i64 is."Copy the code

Get i4 0: 0110 is the four bits starting from 0. The signed/unsigned decimal value is 6. 1*2^2+1*2^1 = 6

1*2^2 + 1*2^0 = 0101,1 *2^2 + 1*2^0 = 5, 1*2^2 + 1*2^0 = 5

1*2^3 + 1*2^ 1 + 1*2^ 0 =11. The result is the same

Muzidao :0>bitfield muzidao set u4 8 920 #u unmarked 1) "7" muzidao :0> muzidao"m�zidao" muzidao :0> muzidao set u8 1) "0" ali cloud :0>get muzidao"m�zidaow"Copy the code

What is the ASCII value for 920? What is the ASCII value for 119

The third subinstruction, incrby, is used to increment the bits in a specified range. Now that we’re talking about increments, there’s the possibility of spillovers. If you increase a positive number, you get an overspill, and if you increase a negative number, you get an underspill. Redis handles retractions by default. If an overflow occurs, the overflow sign bit is discarded. If it’s an 8-bit unsigned number 255, add one and it overflows and all zeros are made. If it’s an 8-bit signed number 127, add 1 and it overflows to -128.

Ali cloud: 0 > set muzidao muzidao "OK" ali cloud: 0 > get muzidao "muzidao ali cloud:" 0 > bitfield muzidao incrby u4 2 1 # 2 start continuous four unsigned since 1) "12" aliyun :0>get muzidaoCopy the code

1011 = 1100 = 1* 2^3 + 1* 2^2 = 12

WRAP: Use the WRAP around method to handle overflows of both signed and unsigned integers. For unsigned integers, wrapping is like performing a modular calculation using the value itself and the largest unsigned integer that can be stored, which is also standard behavior in C. For signed integers, an overflow causes the number to be reevaluated from the smallest negative number, while an underflow causes the number to be reevaluated from the largest positive number. For example, if we add one to an i8 integer with a value of 127, we get -128.

SAT: the saturation calculation method is used to handle overflow, that is, the result of underflow calculation is the smallest integer value, and the result of overflow calculation is the largest integer value. For example, if we add 10 to an i8 integer with a value of 120, the result of the command will be 127, the largest integer value that type I8 can store. In contrast, if a calculation of an i8 value causes an underflow, the i8 value is set to -127.

FAIL: In this mode, the command rejects computations that would cause overflows or underflows and returns a null value to the user indicating that the computations were not executed.

 
Application scenarios

I remember when I was used to get the App, I log in every day, but there is no sign in oh, login after 7 days in a row, will give you send an e-book, log in 30 consecutive days and will send you a e-book, sometimes also will be prompted to log in over 50 days to send you an ebook, I think this scene is very fit for using bitmap, log in to save one day 1, If you do not log in, the value is 0. Counting the number of logins (bitcount)

Bitmaps are good for storing bool data, and are the best choice when there are only two possible outcomes for a business

Why can you store billions of data?

Consider putting a key in redis. Its value is so large that its two-byte number is larger than the maximum user ID. The maximum value of a single key in Redis is 512MB, which can reach 4,294,967,296 bits, enough for many services. We use the user ID as the offset, and the value of the offset as the active value to achieve our goal. This can solve the query problem of all data with only one key. Assuming our maximum ID is 500 million, we need 500 million bits, which is equivalent to only 500 million /(8*1024*1024)≈59.6M memory. If you understand memory conversion,

Unit conversion:

1Byte = 8 Bit

1KB = 1024Byte

1MB = 1024KB

1GB = 1024MB

1TB = 1024GB

Let’s see why 4.2 billion can be saved, single key maximum is 512MB, by conversion

512(M) * 1024 (Kb) * 1024(Byte) * 8(Bit) = 4,294,967,296（bit） = 2 ^32

First look at the machine memory

Setbit testmax 4294967295 1 Total used free shared buff/cache availableMem: [root@astali redis-3.2.6] 1883496 699516 650264 436 533716 1022744Swap: 0 0Copy the code
Total: indicates the total memory size. Used: indicates the number of used memory. Free: indicates the number of free memory. Shared: it is not used. Buffers: Number of buffers; Cached Page: indicates the cached memory.Copy the code

If the maximum value 4294967296 is exceeded, the offset value [0,4294967296]

Setbit testmax 4294967296 1"ERR bit offset is not an integer or out of range" ali :0>setbit testmax 4294967295 1"0"Copy the code

After the setbit testmax 4294967295 command is executed, the free memory is reduced from 650264 to 124984

[root@astali redis-3.2.6]# free # Run setbit testmax 4294967295 1 after total used free shared buff/cache availableMem 1883496 1224796 124984 436 533716 497464Swap: 0 0 0Copy the code

I used Redis Desktop Manager to check testmax, but I did not use Redis to check testmax.

Money to buy services, knowledge to pay, really work, bitmap is the old money nuggets booklet mentioned, so understand a wave

Please give me more advice

The resources

Old money: Live frugally — bitmap