Redis 位图

摘要

Redis官方文档：https://redis.io/documentation (opens new window)

一：前言

在我们平时开发过程中，会有一些 bool 型数据需要存取，比如用户一年的签到记录，签了是 1，没签是 0，要记录 365 天。如果使用普通的 key/value，每个用户要记录 365 个，当用户上亿的时候，需要的存储空间是惊人的。 为了解决这个问题，Redis 提供了位图数据结构，这样每天的签到记录只占据一个位，365 天就是 365 个位，46 个字节 (一个稍长一点的字符串) 就可以完全容纳下，这就大大节约了存储空间。

位图不是特殊的数据结构，它的内容其实就是普通的字符串，也就是 byte 数组。我们可以使用普通的 get/set 直接获取和设置整个位图的内容，也可以使用位图操作 getbit/setbit 等将 byte 数组看成 「位数组」 来处理。

二：使用

2.1 基本使用

设置值：setbit key offset value

获取值：gitbit key offset

时间复杂度都为：O(1)

Redis 的位数组是自动扩展，如果设置了某个偏移位置超出了现有的内容范围，就会自动将位数组进行零扩充。

接下来我们使用位操作将字符串设置为 hello (不是直接使用 set 指令)，首先我们需要得到 hello 的 ASCII 码，及其二进制值。【也可参考在线 ASCII - Binary Character Table (opens new window)】

System.out.println(Integer.toString('h'));          // 104
System.out.println(Integer.toBinaryString('h'));    // 1101000 高位 -> 低位
System.out.println(Integer.toString('e'));          // 101
System.out.println(Integer.toBinaryString('e'));    // 1100101
System.out.println(Integer.toString('l'));          // 108
System.out.println(Integer.toBinaryString('l'));    // 1101100
System.out.println(Integer.toString('o'));          // 111
System.out.println(Integer.toBinaryString('o'));    // 1101111

使用redis-cli设置 he，只需要设置为1的位，如上图示，h 字符只有1、2、4位需要设置，e字符只有9、10、13、15需要设置。

> setbit s 1 1 
(integer) 0 
> setbit s 2 1 
(integer) 0 
> setbit s 4 1 
(integer) 0 
> setbit s 9 1 
(integer) 0 
> setbit s 10 1 
(integer) 0 
> setbit s 13 1
(integer) 0 
> setbit s 15 1 
(integer) 0 
> get s 
"he"

上面这个例子可以理解为「零存整取」，同样我们还也可以「零存零取」，「整存零取」。「零存」就是使用 setbit 对位值进行逐个设置，「整存」就是使用字符串一次性填充所有位数组，覆盖掉旧值。

2.2 零存零取

> setbit w 1 1
(integer) 0
> setbit w 2 1
(integer) 0
> setbit w 4 1
(integer) 0
> getbit w 1 # 获取某个具体位置的值 0/1
(integer) 1
> getbit w 2
(integer) 1
> getbit w 4
(integer) 1
> getbit w 5
(integer) 0
> getbit w 10000  # 由于offset=10000根本就不存在，所以返回结果也是0
(integer) 0

2.3 整存零取

> set h h  # 整存
OK
> getbit h 0
(integer) 0
> getbit h 1
(integer) 1
> getbit h 2
(integer) 1
> getbit h 3
(integer) 0
> getbit h 4
(integer) 1
> getbit h 5
(integer) 0
> getbit h 6
(integer) 0
> getbit h 7

# 如果对应位的字节是不可打印字符，redis-cli 会显示该字符的 16 进制形式。
> setbit h 0 1
(integer) 0
> get h
"\xe8"

需要注意，位数组的顺序和字符的位顺序是相反的

BitMap 占用的空间，就是底层字符串占用的空间。假如 BitMap 偏移量的最大值是 OFFSET_MAX，那么它底层占用的空间就是：

(OFFSET_MAX/8)+1 = 占用字节数

因为字符串内存只能以字节分配，所以上面的单位是字节。

但是需要注意，Redis 中字符串的最大长度是 512M，所以 BitMap 的 offset 值也是有上限的，其最大值是：

8 * 1024 * 1024 * 512 = 2³²

由于 C语言中字符串的末尾都要存储一位分隔符，所以实际上 BitMap 的 offset 值上限是：

(8 * 1024 * 1024 * 512) -1 = 2³² - 1

三：统计和查找

统计指定范围1个数：bitcount [start] [end]

计算第一个目标值偏移量：bitpos key targetBit [start] [end]

时间复杂度都为：O(n)

Redis 提供了位图统计指令 bitcount 和位图查找指令 bitpos，bitcount 用来统计指定位置范围内 1 的个数，bitpos 用来查找指定范围内出现的第一个 0 或 1。

start 和 end 参数是字节索引，也就是说指定的位范围必须是 8 的倍数，而不能任意指定。（getrange 可以取出字符串的子串）

> set w hello
OK
> bitcount w
(integer) 21
> bitcount w 0 0 # 第一个字符中 1 的位数
(integer) 3
> bitcount w 0 1 # 前两个字符中 1 的位数
(integer) 7
> bitpos w 0 # 第一个 0 位
(integer) 0
> bitpos w 1 # 第一个 1 位
(integer) 1
> bitpos w 1 1 1 # 从第二个字符算起，第一个 1 位
(integer) 9
> bitpos w 1 2 2 # 从第三个字符算起，第一个 1 位
(integer) 17

四：bitop

bitmaps间的运算：bitop operation destkey key [key....]

结果存储在destkey

时间复杂度：O(n)

返回值保存到 DESTKEY 的字符串的长度，和输入 KEY 中最长的字符串长度相等

当 bitop 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0 。空的 KEY 也被看作是包含 0 的字符串序列。

bitop 是一个复合操作，它可以做多个Bitmaps的and（交集）、or（并 集）、not（非）、xor（异或）操作并将结果保存在destkey中。

> mset h h e e
OK
> bitop and hAnde h e
(integer) 1
> bitcount hAnde
(integer) 2
> bitop or hOre h e
(integer) 1
> bitcount hOre
(integer) 5
> bitop xor hXore h e
(integer) 1
> bitcount hXore
(integer) 3
> bitop not hNot h
(integer) 1
> bitcount hNot
(integer) 5

结果说明

五：bitfield

前面的 setbit 和 getbit 指定位的值都是单个位。bitfield 有三个子指令，分别是get/set/incrby，它们都可以对指定位片段进行读写，但是最多只能处理 64 个连续的位，如果超过 64 位，就得使用多个子指令，bitfield 可以一次执行多个子指令。

时间复杂度：O(1)

5.1 get

## 单个子命令
> set w hello
OK
> bitfield w get u4 0 # 从第一个位开始取 4 个位，结果是无符号数 (u)
(integer) 6
> bitfield w get u3 2 # 从第三个位开始取 3 个位，结果是无符号数 (u)
(integer) 5
> bitfield w get i4 0 # 从第一个位开始取 4 个位，结果是有符号数 (i)
1) (integer) 6
> bitfield w get i3 2 # 从第三个位开始取 3 个位，结果是有符号数 (i)
1) (integer) -3

## 上面等同下面
## 多个子命令
> bitfield w get u4 0 get u3 2 get i4 0 get i3 2
1) (integer) 6
2) (integer) 5
3) (integer) 6
4) (integer) -3

	有符号位	无符号位
符号位	第一位符号位，1为负数，0为正数	都为非负数
范围	最多可以获取 64 位	只能获取63位 (因为Redis协议中的integer是有符号数，最大64位，不能传递64位无符号值)。如果超出位数限制，Redis就会告诉你参数错误

5.2 set

使用 set 子指令将第二个字符 e 改成 a，a 的 ASCII 码是 97

127.0.0.1:6379> bitfield w set u8 8 97 # 从第 8 个位开始，将接下来的 8 个位用无符号数 97 替换
1) (integer) 101
127.0.0.1:6379> get w
"hallo"

5.3 incrby

incrby 用来对指定范围的位进行自增操作。既然提到自增，就有可能出现溢出。如果增加了正数，会出现上溢，如果增加的是负数，就会出现下溢出。

Redis 默认的处理是折返。如果出现了溢出，就将溢出的符号位丢掉。如果是 8 位无符号数 255， 加 1 后就会溢出，会全部变零。如果是 8 位有符号数 127，加 1 后就会溢出变成 -128。

> set w hello
OK
> bitfield w incrby u4 2 1 # 从第三个位开始，对接下来的 4 位无符号数 +1
1) (integer) 11
> bitfield w incrby u4 2 1
1) (integer) 12
> bitfield w incrby u4 2 1
1) (integer) 13
> bitfield w incrby u4 2 1
1) (integer) 14
> bitfield w incrby u4 2 1
1) (integer) 15
> bitfield w incrby u4 2 1 # 溢出折返了
1) (integer) 0

bitfield 指令提供了溢出策略子指令 overflow，用户可以选择溢出行为，默认是折返(wrap)，还可以选择失败 (fail) 报错不执行，以及饱和截断 (sat)，超过了范围就停留在最大最小值。

overflow 指令只影响接下来的第一条指令，这条指令执行完后溢出策略会变成默认值折返 (wrap)

5.4 饱和截断SAT

> set w hello
OK
> bitfield w overflow sat incrby u4 2 1
1) (integer) 11
> bitfield w overflow sat incrby u4 2 1
1) (integer) 12
> bitfield w overflow sat incrby u4 2 1
1) (integer) 13
> bitfield w overflow sat incrby u4 2 1
1) (intege) 14 
> bitfield w overflow sat incrby u4 2 1 
1) (integer) 15 
> bitfield w overflow sat incrby u4 2 1 # 保持最大值
1) (integer) 15

5.5 失败不执行FAIL

> set w hello
OK
> bitfield w overflow fail incrby u4 2 1
1) (integer) 11
> bitfield w overflow fail incrby u4 2 1
1) (integer) 12
> bitfield w overflow fail incrby u4 2 1
1) (integer) 13
> bitfield w overflow fail incrby u4 2 1
1) (integer) 14
> bitfield w overflow fail incrby u4 2 1
1) (integer) 15
> bitfield w overflow fail incrby u4 2 1 # 不执行
1) (nil)

六：使用场景

https://juejin.cn/post/6844904020587315207

https://segmentfault.com/a/1190000040177140

https://blog.csdn.net/u011957758/article/details/74783347

https://www.jianshu.com/p/d995e7e986aa

https://www.jianshu.com/p/6a63738f1e95

https://blog.51cto.com/zhangxueliang/3000314

七：参考文献

• 《Redis 深度历险：核心原理和应用实践 - 钱文品》
• 《Redis 开发与运维 - 付磊、张益军》
• 官方文档 (opens new window)