redis专题04 数据结构之redis位图系列问题
热度 °
redis位图数据结构bitmap将很多小的整数储存到一个长度较大的位图中， 又或者将一个非常庞大的键分割为多个较小的键来进行储存，从而非常高效地使用内存，使得redis能够应用在诸多场景中, 如用户签到、统计活跃用户、用户在线状态等
此外,
bitfield能够以指定的方式对计算溢出进行控制的能力，使得它特别适合应用于实时分析领域；
用户签到场景中, 签了记录1，没签0，如果使用普通的key/value结构，每个用户一年要记录365个，当用户上亿的时候，需要的存储空间是惊人的。采用redis位图数据结构bitmap，这样每天的签到记录只占据一个位，365天就是365个位，8个bit一个byte, 折算一下46个字节就可以完全容纳下，这就大大节约了存储空间。
当我们要统计月活的时候，因为需要去重，需要使用set来记录所有活跃用户的id，这非常浪费内存。这时就可以考虑使用位图来标记用户的活跃状态。每个用户会都在这个位图的一个确定位置上，0表示不活跃，1表示活跃。然后到月底遍历一次位图就可以得到月度活跃用户数。不过这个方法也是有条件的，那就是userid是整数连续的，并且活跃占比较高，否则可能得不偿失。
位图操作
redis位图是通过一个bit位来表示某个元素对应的值或者状态, 其中的key就是对应元素本身，当然redis位数组是自动扩展，如果设置了某个偏移位置超出了现有的内容范围，就会自动将位数组进行零扩充。
位图不是特殊的数据结构，它的内容其实就是普通的字符串，也就是byte数组。可以使用普通的get/set直接获取和设置整个位图的内容，从redis2.2.0版本开始新增了setbit,getbit,bitcount等几个bitmap相关命令， 也可以使用位图操作getbit/setbit等将byte数组看成「位数组」来处理。
8个bit组成一个Byte，可以通过setbit/getbit来操作单个位但是比较麻烦，但这也正是bitmap本身会极大的节省储存空间， 当然也可以通过bitfield命令来操作多个位。
以设置一个字符h为示例1
字符h对应的8位bit是: 0b1101000 (依次从高位到低位)
从上述可知 只需要设置位图的第1、2，4位置为1 ，即完成设置字符串h的操作，1
2
3
4
5
6
7
8
9127.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分3次设置，然后通过get操作一次取出8bit 得字符h, 也即零存整取的意思, 同样可以通过set s h配合getbit 1 来做到整存零取，或者setbit/getbit实现按位存入读取操作;
如果对应位的字节是不可打印字符，redis-cli 会显示该字符的 16 进制形式。
1 | 127.0.0.1:6379> setbit x 0 1 |
bitcount/bitpos 应用
redis提供了位图统计指令bitcount和位图查找指令bitpos，bitcount用来统计指定位置范围内1的个数，bitpos用来查找指定范围内出现的第一个0或1。
比如我们可以通过bitcount统计用户一共签到了多少天，通过bitpos指令查找用户从哪一天开始第一次签到。如果指定了范围参数[start, end]，就可以统计在某个时间范围内用户签到了多少天，用户自某天以后的哪天开始签到。
但
start和end参数是字节索引，也就是说指定的位范围必须是8的倍数，而不能任意指定。正因此无法直接计算某个月内用户签到了多少天，而必须要将这个月所覆盖的字节内容全部取出来 (getrange可以取出字符串的子串) 然后在内存里进行统计，这个非常繁琐。
1 | 127.0.0.1:6379> set s hello |
bitfield应用
redis3.2版本以后新增了一条bitfield命令，借助bitfield命令可以一次进行多个位的操作。
bitfield有三个子指令，分别是get/set/incrby，它们都可以对指定位片段进行读写，但是最多只能处理64个连续的位，如果超过64位，就得使用多个子指令，当然bitfield可以一次执行多个子指令。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26127.0.0.1:6379> set s hello
OK
127.0.0.1:6379> bitfield s get u4 0 # 从第一个位开始取 4 个位，结果是无符号数 (u)
1) (integer) 6
127.0.0.1:6379> bitfield s get u3 2 # 从第三个位开始取 3 个位，结果是无符号数 (u)
1) (integer) 5
127.0.0.1:6379> bitfield s get i4 0 # 从第一个位开始取 4 个位，结果是无符号数 (i)
1) (integer) 6
127.0.0.1:6379> bitfield s get i3 2 # 从第三个位开始取 3 个位，结果是无符号数 (i)
1) (integer) -3
同时执行多条命令
127.0.0.1:6379> bitfield s get u4 0 get u3 2 get i4 0 get i3 2
1) (integer) 6
2) (integer) 5
3) (integer) 6
4) (integer) -3
将将第二个字符e改成a，a的 ASCII 码是 97
127.0.0.1:6379> bitfield s set u8 8 97
1) (integer) 101
127.0.0.1:6379> get s
"hallo"
注意当设置位数不是8的整数倍，如下是7位时，会导致位数不对无法有效显示字符，redis直接显示出16进制代替
127.0.0.1:6379> bitfield s set u8 7 96
1) (integer) 48
127.0.0.1:6379> get s
"h\xc1llo"
所谓有符号数是指获取的位数组中第一个位是符号位，剩下的才是值。如果第一位是 1，那就是负数;
无符号数表示非负数，没有符号位，获取的位数组全部都是值;
有符号数最多可以获取 64 位，无符号数只能获取 63 位 (因为 Redis 协议中的 integer 是有符号数，最大 64 位，不能传递 64 位无符号值)。如果超出限制， redis会报错;
bitfield还有一个命令incrby，它用来对指定范围的位进行自增操作；
1 | 127.0.0.1:6379> set s hello |
既然提到自增，就有可能出现溢出。如果增加了正数，会出现上溢，如果增加的是负数，就会出现下溢出;
Redis默认的处理是折返。如果出现了溢出，就将溢出的符号位丢掉。如果是 8 位无符号数 255，加 1 后就会溢出，会全部变零。如果是 8 位有符号数 127，加 1 后就会溢出变成 -128。
bitfield 自增溢出策略overflow
bitfield指令提供了溢出策略子指令overflow，用户可以选择溢出行为，默认是折返(wrap)，还可以选择失败(fail)报错不执行，以及饱和截断(sat)，超过了范围就停留在最大最小值。overflow指令只影响接下来的第一条指令，这条指令执行完后溢出策略会变成默认值折返(wrap)
饱和截断策略 SAT
1 | 127.0.0.1:6379> set s 0111 0101 |
分析1
2
3
4
5
6
7
8字符'u'的ACSII二进制表示为 0111 0101
字符'u' 8bit 在位图数组中的位置如下
bitmap下标 0 1 2 3 4 5 6 7
'u'8bit分布 0 1 1 1 0 1 0 1
指令，bitfield s overflow sat incrby u4 1 1
表示从 第一位置依次取四个位置值出来 加上一个1
从第一位置依次取出四个位置值 为 bitmap下标1到4直接的值 即 1110 在加1 就是1111
失败不执行策略 FAIL
1 | 127.0.0.1:6379> set s what |
分析同上
总结
给出了
redis位图数据结构bitmap的基本概念，操作及应用场景;以签到场景为例 引入
bitcount/bitpos在实际案例中的应用分析;以依次操作多个位，引入
bitfield指令，并对bitfield三个子指令get/set/incrby进行了实例分析说明；进一步对
bitfield的incrby操作溢出情况，从redis给出的三种溢出策略折返(wrap)，选择失败(fail)报错不执行，饱和截断(sat)进行了实例使用说明;
作者署名：朴实的一线攻城狮
本文标题：redis专题04 数据结构之redis位图系列问题
本文出处：http://researchlab.github.io/2018/01/19/redis-04-bitmap/
版权声明：本文由Lee Hong创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处, 否则保留追究法律责任的权利。
