Redis Bitmap 学习和使用

分类：软件应用 > Redis

前言

Bitmap，即位图，是一串连续的二进制数组（0和1），可以通过偏移量（offset）定位元素。BitMap通过最小的单位bit来进行0|1的设置，表示某个元素的值或者状态，时间复杂度为O(1)。由于bit是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用二值统计的场景。

这里的二值状态就是指集合元素的取值就只有 0 和 1 两种。例如在签到打卡的场景中，我们只用记录签到（1）或未签到（0），所以它就是非常典型的二值状态。在签到统计时，每个用户一天的签到用 1 个 bit 位就能表示，一个月（假设是 31 天）的签到情况用 31 个 bit 位就可以，而一年的签到也只需要用 365 个 bit 位，根本不用太复杂的集合类型。这个时候，我们就可以选择 Bitmap。

Bitmap不属于Redis的基本数据类型，而是基于String类型进行的位操作。而Redis中字符串的最大长度是 512M，所以 BitMap 的 offset 值也是有上限的，其最大值是：

8 * 1024 * 1024 * 512  =  2^32

下面我们就来看下Bitmap的相关操作吧！

SETBIT

可用版本：>= 2.2.0
时间复杂度：O(1)

命令格式

SETBIT key offset value

命令描述

针对key存储的字符串值，设置或清除指定偏移量offset上的位(bit)
位的设置或清除取决于value值，即1或0
当key不存在时，会创建一个新的字符串。而且这个字符串的长度会伸展，直到可以满足指定的偏移量offset（0 ≤offset< 2^32），在伸展过程中，新增的位的值被设置为0

警告！
如果设置较大的offset，内存分配可能会导致Redis阻塞。
如果key对应的字符串不存在或长度较短，但是设置的offset较大（比如最大为 2^32 -1），Redis需要对中间的位数进行内存分配，Redis可能会阻塞。
拿2010 MacBook Pro举例，offset = 2^32 -1 (分配512MB内存)，需要耗时300ms左右；offset = 2^30 -1 (分配128内存)，需要耗时80ms左右；offset = 2^28 -1 (分配32MB内存)，需要耗时30ms左右；offset = 2^26 -1 (分配8MB内存)，需要耗时80ms左右。
第一次分配内存后，后续对该key的相同操作不会再有内存分配开销。

设置Bitmap

如果想要设置Bitmap的非零初值，该怎么设置呢？一种方式就是将每个位挨个设置为0或1，但是这种方式比较麻烦，我们可以考虑直接使用SET命令存储一个字符串。

由于Bitmap就是基于String类型，因此Bitmap类型的数据也可以使用String类型的命令，主要是SET和GET。

比如对于字符串‘42’，底层保存数据时，使用0-7位保存‘4’，使用8-15位保存‘2’，‘4’对应的ASCII码为0011 0100，‘2’对应的ASCII码为0011 0010，我们通过挨个设置Bitmap来观察下：

127.0.0.1:6379> SETBIT bitmapsarestrings 2 1
(integer) 0
127.0.0.1:6379> SETBIT bitmapsarestrings 3 1
(integer) 0
127.0.0.1:6379> SETBIT bitmapsarestrings 5 1
(integer) 0
127.0.0.1:6379> SETBIT bitmapsarestrings 10 1
(integer) 0
127.0.0.1:6379> SETBIT bitmapsarestrings 11 1
(integer) 0
127.0.0.1:6379> SETBIT bitmapsarestrings 14 1
(integer) 0

# 通过挨个设置比特位，GET数据就是字符串”42“
127.0.0.1:6379> GET bitmapsarestrings
"42"

# 直接设置字符串，查出来bit位也是一致的
127.0.0.1:6379> set bitkey "42"
OK
127.0.0.1:6379> getbit bitkey 0
(integer) 0
127.0.0.1:6379> getbit bitkey 1
(integer) 0
127.0.0.1:6379> getbit bitkey 2
(integer) 1
127.0.0.1:6379> getbit bitkey 3
(integer) 1
127.0.0.1:6379> getbit bitkey 4
(integer) 0
127.0.0.1:6379> getbit bitkey 5
(integer) 1
127.0.0.1:6379> getbit bitkey 6
(integer) 0
127.0.0.1:6379> getbit bitkey 7
(integer) 0
127.0.0.1:6379> getbit bitkey 8
(integer) 0
127.0.0.1:6379> getbit bitkey 9
(integer) 0
127.0.0.1:6379> getbit bitkey 10
(integer) 1
127.0.0.1:6379> getbit bitkey 11
(integer) 1
127.0.0.1:6379> getbit bitkey 12
(integer) 0
127.0.0.1:6379> getbit bitkey 13
(integer) 0
127.0.0.1:6379> getbit bitkey 14
(integer) 1
127.0.0.1:6379> getbit bitkey 15
(integer) 0

因此通过上述例子我们可以明白，在设置非零初值时，不需要挨个设置比特位，只需要给定一个字符串就可以了。

返回值

整数：偏移量offset位置的原始值

示例

# 8对应的ASCII码为：0011 1000
127.0.0.1:6379> set mykey "8"
OK

# 8对应的ASCII码为：0011 1000
127.0.0.1:6379> getbit mykey 0
(integer) 0
127.0.0.1:6379> getbit mykey 1
(integer) 0
127.0.0.1:6379> getbit mykey 2
(integer) 1
127.0.0.1:6379> getbit mykey 3
(integer) 1
127.0.0.1:6379> getbit mykey 4
(integer) 1
127.0.0.1:6379> getbit mykey 5
(integer) 0
127.0.0.1:6379> getbit mykey 6
(integer) 0
127.0.0.1:6379> getbit mykey 7
(integer) 0

# 将第8位（索引为7）的位设置为1
127.0.0.1:6379> setbit mykey 7 1
(integer) 0
127.0.0.1:6379> getbit mykey 7
(integer) 1

GETBIT

可用版本：>= 2.2.0
时间复杂度：O(1)

命令格式

GETBIT key offset

命令描述

返回key对应的字符串，offset位置的位（bit）
当offset大于值的长度时，返回0
当key不存在时，可以认为value为空字符串，此时offset肯定大于空字符串长度，参考上一条，也返回0

返回值

整数：偏移量offset位置的bit值

示例

# 8对应的ASCII码为：0011 1000
127.0.0.1:6379> set mykey "8"
OK

# 8对应的ASCII码为：0011 1000
127.0.0.1:6379> getbit mykey 0
(integer) 0
127.0.0.1:6379> getbit mykey 1
(integer) 0
127.0.0.1:6379> getbit mykey 2
(integer) 1
127.0.0.1:6379> getbit mykey 3
(integer) 1
127.0.0.1:6379> getbit mykey 4
(integer) 1
127.0.0.1:6379> getbit mykey 5
(integer) 0
127.0.0.1:6379> getbit mykey 6
(integer) 0
127.0.0.1:6379> getbit mykey 7
(integer) 0

BITCOUNT

可用版本：>= 2.6.0
时间复杂度：O(N)

命令格式

BITCOUNT key [start end]

命令描述

统计给定字符串中，比特值为1的数量
默认会统计整个字符串，同时也可以通过指定 start 和 end 来限定范围
start 和 end 也可以是负数，-1表示最后一个字节，-2表示倒数第二个字节。注意这里是字节，1字节=8比特
如果key不存在，返回0

返回值

整数：bit值为1的数量

示例

# a: 0110 0001 
# b: 0110 0010 
# c: 0110 0011
# mykey: 01100001 01100010 01100011
127.0.0.1:6379> set mykey 'abc'
OK

# 统计整个字符串对应的bit=1的数量
127.0.0.1:6379> bitcount mykey
(integer) 10

# a
127.0.0.1:6379> bitcount mykey 0 0
(integer) 3

# ab
127.0.0.1:6379> bitcount mykey 0 1
(integer) 6

# c
127.0.0.1:6379> bitcount mykey 2 2
(integer) 4

使用场景

比如我们有一个App，需要统计2021年每个用户登录的情况，针对这个需求，我们以用户id+2021作为key，将用户上线那天对应的offset设置为1，这样就可以统计每个用户在本年度登录的情况，使用bitcount可以统计登录天数。

举个例子，今天是2021年第100天，而user_id:10001在今天阅览过网站，那么执行命令 SETBIT 2021:user_id:10001 100 1 ；如果明天该用户也登录的App，那么执行命令 SETBIT 2021:user_id:10001 101 1 ，以此类推。

最后使用 BITCOUNT 2021:user_id:10001，就可以统计该用户本年度登录App的次数了

通过上例我们可以看出，使用Bitmap来统计二值数据非常节省内存，一个用户一年只需要占用 365个比特，10年也只需要 365*10/8=456个字节。

BITPOS

可用版本：>= 2.8.7
时间复杂度：O(N)

命令格式

BITPOS key bit [start [end]]

命令描述

返回字符串中，从左到右，第一个比特值为bit（0或1）的偏移量
默认情况下会检查整个字符串，但是也可以通过指定start和end变量来指定字节范围，与BITCOUNT中的范围描述一致
SETBIT和GETBIT指定的都是比特偏移量，BITCOUNT和BITPOS指定的是字节范围
不论是否指定查询范围，该命令返回的偏移量都是基于0开始的
如果key不存在，认为是空字符串

返回值

整数：第一个比特值为指定bit（0或1）的偏移量

如果命令中参数bit=1，但是字符串为空，此时返回 -1 ；
如果命令中参数bit=0,但是字符串中所有的比特值都为1，此时命令返回字符串最大的offset+1。例如字符串对应的比特值为’11111111‘，那么此时会返回8。
默认情况下，如果查询bit=0，且没有指定范围，或者只指定了start，命令默认在字符串后面补0用于查询bit=0的offset。但是如果指定了start和end，且范围内所有值都为0，此时会返回-1，因为用户指定了范围且范围内没有0，不会在后面补充
如果查询bit=1，始终不会在字符串后面补充1，查询不到就会返回-1

示例

# 例1
# a: 0110 0001 
127.0.0.1:6379> SET mykey "a"
OK
# 第一个bit=1的偏移量
127.0.0.1:6379> bitpos mykey 1
(integer) 1
# 第一个bit=0的偏移量
127.0.0.1:6379> bitpos mykey 0
(integer) 0

# 例2
# '\xff': 1111 1111
#  全为1时，查询bit=1和bit=0
127.0.0.1:6379> SET mykey "\xff"   
OK
127.0.0.1:6379> bitpos mykey 1
(integer) 0
127.0.0.1:6379> bitpos mykey 0      
(integer) 8

# 例3
# '\xff': 0000 0000
#  全为0时，查询bit=1和bit=0
127.0.0.1:6379> SET mykey "\x00"
OK
127.0.0.1:6379> bitpos mykey 1
(integer) -1
127.0.0.1:6379> bitpos mykey 0
(integer) 0

# 例4
# 11111111 11111111 11111111
127.0.0.1:6379> set mykey "\xff\xff\xff"
OK
# 指定前两个字节，都为1，不会补充0，返回-1
127.0.0.1:6379> bitpos mykey 0 0 1
(integer) -1

BITOP

可用版本：>= 2.6.0
时间复杂度：O(N)

命令格式

BITOP operation destkey key [key ...]

命令描述

对多个字符串进行位操作，并将结果保存到destkey中
operation 可以是 AND、OR、XOR 或者 NOT
BITOP AND destkey srckey1 srckey2 srckey3 ... srckeyN，对多个key求逻辑与，并将结果保存到destkey中
BITOP OR destkey srckey1 srckey2 srckey3 ... srckeyN，对多个key求逻辑或，并将结果保存到destkey中
BITOP XOR destkey srckey1 srckey2 srckey3 ... srckeyN，对多个key求异或，并将结果保存到destkey中
BITOP NOT destkey srckey，对key求逻辑非，并将结果保存到destkey中
除了 NOT 操作之外，其他操作都可以接受一个或多个 key 作为输入。

不同长度的字符串

当给定的参数中，字符串长度不同时，较短的那个字符串与最长字符串之间缺少的部分会被看作 0 。

空的 key 也被看作是包含 0 的字符串序列。

返回值

整数：保存到 destkey 的字符串的长度（和参数给定的key中最长的字符串长度相等）

示例

127.0.0.1:6379> set key1 "\xff"
OK
127.0.0.1:6379> set key2 "\x00"
OK

# 逻辑与
127.0.0.1:6379> bitop AND andkey key1 key2
(integer) 1
127.0.0.1:6379> get andkey
"\x00"

# 逻辑或
127.0.0.1:6379> bitop OR orkey key1 key2
(integer) 1
127.0.0.1:6379> get orkey
"\xff"

# 异或
127.0.0.1:6379> bitop XOR xorkey key1 key2
(integer) 1
127.0.0.1:6379> get xorkey
"\xff"

# 逻辑非
127.0.0.1:6379> bitop not notkey key1
(integer) 1
127.0.0.1:6379> get notkey
"\x00"

BITFIELD

可用版本：>= 3.2.0
时间复杂度：对于每个子命令，复杂度为O(1)

命令格式

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

命令描述

BITFIELD 将Redis字符串看作一个由很多整数组成的数组，能够处理不同宽度的比特位，同时可以处理任意偏移量的字段。换句话说，通过这个命令，用户可以进行如下操作：“将从偏移量1234开始的5位有符号整数设置为一个值”、 “获取从偏移量4567开始的31位无符号整数”等
BITFIELD 命令还可以对指定的整数执行加法操作和减法操作，并且这些操作可以通过设置，有好的地处理计算时的溢出情况
BITFIELD可以在一个命令中，操作多个比特区间。即命令接受多个操作，并返回每个操作返回值组成的列表。
如下命令有两个操作：对从偏移量100处开始的5位有符号整数执行加法操作，获取偏移量0开始的4位无符号整数
> BITFIELD mykey INCRBY i5 100 1 GET u4 0
1) (integer) 1
2) (integer) 0

注意：
使用GET超出当前当前字符串范围时（key不存在相当于空字符串，也属于这种情况），超出的部分会被当做0
使用INCRBY或SET命令，且超出字符串范围时，缺失部分会被填充0

支持的子命令和整数类型

GET <type> <offset> -- 返回指定的比特范围
SET <type> <offset> <value> -- 设置指定的比特范围并返回旧值
INCRBY <type> <offset> <increment> -- 增加或减少（如果increment参数为负数）指定的比特范围并返回新值

除了上面三个子命令外，还有一个子命令可以改变SET和INCRBY在发生溢出时的行为：

OVERFLOW [WRAP|SAT|FAIL]

当被设置的二进制位范围值为整数时，我们可以在类型参数前面添加 i 来表示有符号整数，或者使用 u 来表示无符号整数。比如说，我们可以使用 u8 来表示8位无符号整数，也可以使用i16来表示 16 位有符号整数。

比特值和位置偏移量

我们有两种方式来设置偏移量：如果数字前没有前缀，那么就是基于0的比特位偏移量；如果数字有带有 ‘#’ 前缀，offset就等于提供的整数宽度乘以’#‘后面的偏移量。例如：

BITFIELD mystring SET i8 #0 100 SET i8 #1 200

第一个SET对应的偏移量为：8*0=0

第二个SET对应的偏移量为：8*1=8

使用 # 前缀可以让我们免去手动计算被设置比特位所在位置的麻烦。

溢出控制

通过OVERFLOW命令，可以控制BITFIELD在执行增加或减少时，发生向上溢出（overflow）或向下溢出（underflow）的情况时的行为：

WRAP：使用环绕的方式来控制有符号和无符号整数的溢出。对于无符号整数来说，环绕就是使用数值本身与能够被储存的最大无符号整数取模，这也是 C 语言的标准行为。对于有符号整数来说，上溢将导致数字从可以表示的最小负数开始计算，而下溢将导致数字从可以表示的最大正数开始计算。例如对一个值为 127 的 i8 整数执行加1操作，那么将得到结果 -128 。
SAT：使用饱和算法（saturation arithmetic）计算，也就是下溢结果为可以表示的最小的整数值，而上溢的结果为可以表示的最大的整数值。例如对一个值为 120 的 i8 整数执行加 10 计算，那么命令的结果将为 i8 类型所能储存的最大整数值 127，如果继续增加，始终为127不变。与此相反，如果一个针对 i8 值的计算造成了下溢，那么这个 i8 值将被设置为 -127 。
FAIL：当发生上溢或者下溢情况时，不会执行操作，并向用户返回空值表示计算未被执行。

需要注意的是，OVERFLOW子命令只会影响在它之后的SET和INCRBY命令，直到遇到下一个OVERFLOW就会停止作用。默认使用WARP模式。

# 初始都为0，执行无符号加一操作，前一个incrby默认使用 WARP 模式，后一个指定 SAT 模式
> BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
1) (integer) 1
2) (integer) 1

> BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
1) (integer) 2
2) (integer) 2

> BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
1) (integer) 3
2) (integer) 3

# u2最大表示为3，再加一会向上溢出。 WARP： (3+1)%4=0    SAT: 始终保持最大值
> BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
1) (integer) 0
2) (integer) 3

返回值

列表：每个子命令对应的返回值，OVERFLOW不会返回数据，只会影响后续命令的返回值。

动机

将很多小的整数储存到一个长度较大的位图中，又或者将一个非常庞大的键分割为多个较小的键来进行储存，可以非常高效地使用内存，从而使得 Redis 能够得到更多不同的应用 —— 特别是在实时分析领域： BITFIELD 能够以指定的方式对控制计算溢出，使得它可以被应用于这一领域。

性能考量

BITFIELD是一个较快的命令，但是需要注意的是：对较短的字符串，处理较大偏移量的比特位，会导致内存分配，进而导致耗时增加；而处理已存在的比特位耗时较少。

比特位的顺序

BITFIELD 把位图第一个字节偏移量为 0 的二进制位看作是 most significant 位，以此类推。举个例子，如果我们对一个已经预先被全部设置为 0 的位图进行设置，将它在偏移量为 7 的值设置为 5 位无符号整数值 23 （二进制位为 10111 ），那么命令将生产出以下这个位图表示：

+--------+--------+
|00000001|01110000|
+--------+--------+

当偏移量和整数长度与字节边界进行对齐时， BITFIELD 表示二进制位的方式跟大端表示法（big endian）一致，但是在没有对齐的情况下，理解这些二进制位是如何进行排列也是非常重要的。

示例

127.0.0.1:6379> set mykey "\x00"
OK

# offset从0开始，获取前5位有符号正数
127.0.0.1:6379> bitfield mykey get i5 0
1) (integer) 0

# offset从0开始，设置前5位有符号正数
127.0.0.1:6379> bitfield mykey set i5 0 10
1) (integer) 0

127.0.0.1:6379> bitfield mykey get i5 0
1) (integer) 10

# offset从0开始，前5位有符号正数加一
127.0.0.1:6379> bitfield mykey incrby i5 0 1
1) (integer) 11
127.0.0.1:6379> bitfield mykey get i5 0
1) (integer) 11

总结

本文介绍了Bitmap的相关操作，主要包括以下命令

SETBIT：设置比特位
GETBIT：查询比特值
BITCOUNT：统计比特值为1的数量
BITPOS：查询第一个比特值为0或1的偏移量
BITOP：对Bitmap做逻辑与、或、异或、非操作
BITFIELD：将Bitmap看作由多个整数组成的，对其中的整数操作

来源：https://zhuanlan.zhihu.com/p/401726844 发布时间：2022-06-05 17:24:13

PHP 服务器 Mysql Javascript