Redis之_节衣缩食_位图
前言
Github:https://github.com/HealerJean
1、为什么用位图
位图不是特殊的数据结构,它的内容其实就是普通的字符串,也就是
byte
数组。我们 可以使用普通的get
/set
直接获取和设置整个位图的内容,也可以使用位图操作getbit
/setbit
等将byte
数组看成「位数组」来处理。在我们平时开发过程中,会有一些
bool
型数据需要存取,比如用户一年的签到记录, 签了是1
,没签是0
,要记录365
天。如果使用普通的key
/value
,每个用户要记录365
个,当用户上亿的时候,需要的存储空间是惊人的。为了解决这个问题,
Redis
提供了位图数据结构,这样每天的签到记录只占据一个位,365
天就是365
个位,46
个字节 (46*8bit = 368 > 365
一个稍长一点的字符串) 就可以完全容纳下,这就大大 节约了存储空间。
2、基本使用
Redis
的位数组是自动扩展,如果设置了某个偏移位置超出了现有的内容范围,就会自动将位数组进行零扩充。
案例:接下来我们使用位操作将字符串设置为 hello
(不是直接使用 set
指令),首先我们需要得到 hello
的 ASCII
码
ASCII | 二进制 |
---|---|
h | 01101000 |
e | 01100101 |
l | 01101100 |
l | 01101100 |
o | 01101111 |
接下来我们使用 redis-cli
设置第一个字符,也就是位数组的前 8
位,我们只需要设置值为 1
的位,如上图所示,
⬤ h
字符只有 1
/2
/4
位需要设置
⬤ e
字符只有 9
/10
/13
/15
位需要设置。
⬤ l
字符只有17
、18
、 20
、 21
⬤ ………………
127.0.0.1:6379> setbit s 1 1
(integer) 0
127.0.0.1:6379> setbit s 2 1
(integer) 0
127.0.0.1:6379> setbit s 4 1
(integer) 0
127.0.0.1:6379> get s
"h"
127.0.0.1:6379> setbit s 9 1
(integer) 0
127.0.0.1:6379> setbit s 10 1
(integer) 0
127.0.0.1:6379> setbit s 13 1
(integer) 0
127.0.0.1:6379> setbit s 15 1
(integer) 0
127.0.0.1:6379> get s
"he"
2.1、零存零取
「零存」就是使用
setbit
对位值进行逐个设置,
127.0.0.1:6379> setbit w 1 1
(integer) 0
127.0.0.1:6379> setbit w 2 1
(integer) 0
127.0.0.1:6379> setbit w 4 1
(integer) 0
127.0.0.1:6379> getbit w 1
(integer) 1
127.0.0.1:6379> getbit w 2
(integer) 1
127.0.0.1:6379> getbit w 4
(integer) 1
127.0.0.1:6379> getbit w 5
(integer) 0
2.2、整存零取
「整存」就是使用字符串一次性填充所有位数组,覆盖掉旧值。
127.0.0.1:6379> set w h # 整存 (integer) 0
127.0.0.1:6379> getbit w 1
(integer) 1
127.0.0.1:6379> getbit w 2
(integer) 1
127.0.0.1:6379> getbit w 4
(integer) 1
127.0.0.1:6379> getbit w 5
(integer) 0
2.3、不可打印字符,显示16进制
如果对应位的字节是不可打印字符,
redis-cli
会显示该字符的 16 进制形式。
127.0.0.1:6379> setbit x 0 1
(integer) 0
127.0.0.1:6379> setbit x 1 1
(integer) 0
127.0.0.1:6379> get x
"\xc0"
3、统计和查找
Redis
提供了位图统计指令bitcount
和位图查找指令bitpos
,⬤
bitcount
用来统计指定位 置范围内1
的个数,⬤
bitpos
用来查找指定范围内出现的第一个0
或1
。
start
和end
参数是字节索引(第几个字符),也就是说指定的位范围必须是8
的倍数, 而不能任意指定 这很奇怪,我表示不是很能理解
Antirez
为什么要这样设计。因为这个设 计,我们无法直接计算某个月内用户签到了多少天,而必须要将这个月所覆盖的字节内容全 部取出来 (getrange
可以取出字符串的子串) 然后在内存里进行统计,这个非常繁琐。
1、通过 bitcount
统计用户一共签到了多少天,
2、通过 bitpos
指令查找用户从 哪一天开始第一次签到。
如果指定了范围参数[start
, end
],就可以统计在某个时间范围内用户 签到了多少天,用户自某天以后的哪天开始签到。
127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitcount w # 总共有
(integer) 21
127.0.0.1:6379> bitcount w 0 0 # 第一个字符中 1 的位数,h -> 3个1
(integer) 3
127.0.0.1:6379> bitcount w 0 1 # 前两个字符中 1 的位数 he -> 7个1
(integer) 7
127.0.0.1:6379> bitpos w 0 # 第一个bit 0 位
(integer) 0
127.0.0.1:6379> bitpos w 1 # 第一个bit 1 位
(integer) 1
127.0.0.1:6379> bitpos w 1 1 1 # 从第二个字符算起(1-1),第一个 1 位
(integer) 9
127.0.0.1:6379> bitpos w 1 2 2 # 从第三个字符算起(2-2),第一个 1 位
(integer) 17
3、魔术指令 bitfield
前文我们设置 (
setbit
) 和获取 (getbit
) 指定位的值都是单个位的,如果要一次操作多个位,就必须使用管道来处理。不过
Redis
的 3.2 版本以后新增了一个功能强大的指令,有 了这条指令,不用管道也可以一次进行多个位的操作。⬤
bitfield
有三个子指令,分别是get
/set
/incrby
,它们都可以对指定位片段进行读写,但是最多只能处理64
个连续的位,如果 超过64
位,就得使用多个子指令,bitfield
可以一次执行多个子指令。
⬤ 有符号数是指获取的位数组中第一个位是符号位,剩下的才是值,如果第一位是 1
,那就是负数。(有符号数最多可以获取 64
位)
⬤ 无符号数表示非负数,没有符号位,获取的位数组全部都是值。无符号数只能获取 63
位(因为首位表示正数/负数)
127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitfield w get u4 0 # 从第一个位开始取 4 个位,结果是无符号数 (u)
(integer) 6
0110 -> 6
127.0.0.1:6379> bitfield w get u3 2 # 从第三个位开始取 3 个位,结果是无符号数 (u)
(integer) 5
101 -> 5
127.0.0.1:6379> bitfield w get i4 0 # 从第一个位开始取 4 个位,结果是有符号数 (i)
1) (integer) 6
0110 -> 0开头表示正数 -> 6
127.0.0.1:6379> bitfield w get i3 2 # 从第三个位开始取 3 个位,结果是有符号数 (i)
1) (integer) -3
101 -> 1开头表示负数 -> 减1 -> 100 取反 011 -> 3 -> 加负号 -3
3.1、一次执行多个指令
127.0.0.1:6379> 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
3.1.2、set
:修改字符
然后我们使用 set 子指令将第二个字符 e 改成 a,a 的 ASCII 码是 97。
127.0.0.1:6379> bitfield w set u8 8 97 #从第9个位开始,将接下来的 8 个位用无符号数 97 替换
1) (integer) 101
127.0.0.1:6379> get w
"hallo"
3.2.3、incrby
:自增
再看第三个子指令
incrby
,它用来对指定范围的位进行自增操作。既然提到自增,就有可能出现溢出,bitfield
指令提供了溢出策略子指令overflow
,用户可以选择溢出行为。⬤ 如果增加了正数,会出现上溢
⬤ 如果增加的是负数,就会出现下溢出。
3.2.3.1、折返 (wrap
)
Redis 默认的处理是折返。如果出现了溢出,就将溢出的符号位丢掉。
◯ 如果是 8 位无符号数
255
, 加 1 后就会溢出,会全部变零。◯ 如果是 8 位有符号数
127
,加1
后就会溢出变成-128
。
127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitfield w incrby u4 2 1 # 从第三个位开始,对接下来的 4 位无符号数 +1
1) (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) 0
3.2.3.2、饱和截断 SAT
饱和截断 (
sat
),超过了范围就停留在最大/最小值。`
127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitfield w overflow sat incrby u4 2 1 # 从第三个位开始,对接下来的 4 位无符号数 +1
1) (integer) 11
127.0.0.1:6379> bitfield w overflow sat incrby u4 2 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) (intege) 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 # 保持最大值
1) (integer) 15
3.2.3.3、失败不执行 FAIL
失败 (
fail
) 报错不执行
127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> bitfield w overflow fail incrby u4 2 1 1) (integer) 11
127.0.0.1:6379> bitfield w overflow fail incrby u4 2 1 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) (integer) 15
127.0.0.1:6379> bitfield w overflow fail incrby u4 2 1 # 不执行
1) (nil)