redis-04-位图Bitmaps

一般知道前面介绍的五种redis数据结构，就可以开心的玩耍了，但如果知道Bitmaps，Hyperloglogs，GEO，就更开心了。

这次我们来看下Bitmaps。

简介

假设一个场景：记录用户的签到天数。

方法一：将用户的id和日期关联起来，做个key，比如用户007在2018/08/14这天的签到情况，设置个key：sign_2018_08_14_007，并将值设置为1。如果用户越来越多，数值则越来越大，到后面的统计耗时肯定越来越长，并且储存量也越来越大。

方法二：用hash结构，uid做key，里面存签到的日期，但储存量还是很大。

有没有更优雅的方法呢？有，答案是bitmaps。

在看bitmaps的概念前，先做个小验证：

1. 设置个key的值为h

127.0.0.1:6379> set w h
OK
127.0.0.1:6379> get w
"h"

h对应的ASCII为0110 1000，即：

2.通过getbit来验证下

127.0.0.1:6379> getbit w 0 #用getbit获取w第0位的值
(integer) 0
127.0.0.1:6379> getbit w 1 #用getbit获取w第1位的值
(integer) 1
127.0.0.1:6379> getbit w 2 #用getbit获取w第2位的值
(integer) 1
127.0.0.1:6379> getbit w 3
(integer) 0
127.0.0.1:6379> getbit w 4
(integer) 1
127.0.0.1:6379> getbit w 5
(integer) 0
127.0.0.1:6379> getbit w 6
(integer) 0
127.0.0.1:6379> getbit w 7
(integer) 0

到这里，对bitmaps也就有了个大概的感受了。

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

用字符串'world'来做个例子，首先看下world对应的ASCII值，可以用python直接获取

>>> bin(ord('w'))
'0b1110111'
>>> bin(ord('o'))
'0b1101111'
>>> bin(ord('r'))
'0b1110010'
>>> bin(ord('l'))
'0b1101100'
>>> bin(ord('d'))
'0b1100100'

用setbit来设置个key，值为'w'

127.0.0.1:6379> get test 
(nil)
127.0.0.1:6379> setbit test 0 0
(integer) 0
127.0.0.1:6379> setbit test 1 1
(integer) 0
127.0.0.1:6379> setbit test 2 1
(integer) 0
127.0.0.1:6379> setbit test 3 1
(integer) 0
127.0.0.1:6379> setbit test 4 0
(integer) 0
127.0.0.1:6379> setbit test 5 1
(integer) 0
127.0.0.1:6379> setbit test 6 1
(integer) 0
127.0.0.1:6379> setbit test 7 1
(integer) 0
127.0.0.1:6379> get test
"w"

把'world'对应的值从左到右放在一起

01110111 01101111 01110010 01101100 01100100

即

0111011101101111011100100110110001100100

redis验证下

127.0.0.1:6379> set t world
OK
127.0.0.1:6379> getbit t 0
(integer) 0
127.0.0.1:6379> getbit t 2
(integer) 1
127.0.0.1:6379> getbit t 7
(integer) 1
127.0.0.1:6379> getbit t 14
(integer) 1

统计和查找

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

比如我们可以通过 bitcount 统计用户一共签到了多少天，通过 bitpos 指令查找用户从哪一天开始第一次签到。

bitcount

格式

BITCOUNT key [start] [end]

统计下'world'有多少个1:

127.0.0.1:6379> bitcount t
(integer) 23

统计下'wo'有多少个1:

127.0.0.1:6379> bitcount t 0 1 #wo是前两个字符，所以范围是0-1
(integer) 12

统计下'orl'有多少个1:

127.0.0.1:6379> bitcount t 1 3
(integer) 14

注意点： start 和 end 参数是字节索引，也就是说指定的位范围必须是 8 的倍数，而不能任意指定。

bitpos

显示0首次出现的位置

127.0.0.1:6379> bitpos t 0
(integer) 0

显示1首次出现的位置

127.0.0.1:6379> bitpos t 1
(integer) 1

bitfield

前文我们设置 (setbit) 和获取 (getbit) 指定位的值都是单个位的，如果要一次操作多个位，就必须使用管道来处理。

Redis 的 3.2 版本以后新增了一个指令bitfield，通过这个指令可以一次进行多个位操作。

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

回到我们刚才设置的'world',它对应的二进制码如下：

0111011101101111011100100110110001100100

get

这次我们使用bitfield的get来获取它的有符号数和无符号数

127.0.0.1:6379> get t
"world"
127.0.0.1:6379> bitfield t get i4 0 #i表示有符号位，4表示连续取4位，0表示开始位置
1) (integer) 7

我们算下，看值是不是7.

从0位开始，取4位，即0111。首位是0，所以直接将111转为十进制，得到值7，与结果一样

我们再算个：

127.0.0.1:6379> bitfield t get i3 7
1) (integer) -3

看下是不是-3

从7位开始，取3位，即101。首位是1，是负数，后面01为补码，先减1，再反转，得到11，转为十进制，即3，得到值-3，与结果一直

再验证个有符号位：

127.0.0.1:6379> bitfield t get u3 7
1) (integer) 5

同样从7位开始，取3位，即101。由于是无符号位，所以直接求值，值为5，与结果一致

多个同时操作

127.0.0.1:6379> bitfield t get u3 7 get i3 7 get i4 1
1) (integer) 5
2) (integer) -3
3) (integer) -2

set

我们用bitfield的set指令在'world'后增加个'w'。

'w'在ASCII中对应的值119，加在'world'后，属于第六个字母，那么在8位的二进制中则是从40位开始，所以指令如下：

127.0.0.1:6379> bitfield t set u8 40 119 #设置无符号位，连续8位，从40位开始，值为119
1) (integer) 0
127.0.0.1:6379> get t
"worldw"

使用同样的计算方式，再增加三个字母'ild'

127.0.0.1:6379> bitfield t set u8 48 105 set u8 56 108 set u8 64 100
1) (integer) 0
2) (integer) 0
3) (integer) 0
127.0.0.1:6379> get t
"worldwild"

我们得到了一个新的单词'worldwild'

incrby

再看第三个子指令 incrby，它用来对指定范围的位进行自增操作。既然提到自增，就有可能出现溢出。如果增加了正数，会出现上溢，如果增加的是负数，就会出现下溢出。Redis 默认的处理是折返。如果出现了溢出，就将溢出的符号位丢掉。如果是 8 位无符号数 255，加 1 后就会溢出，会全部变零。如果是 8 位有符号数 127，加 1 后就会溢出变成 -128。

做下实验

127.0.0.1:6379> set a w
OK
127.0.0.1:6379> getbit a 0
(integer) 0
127.0.0.1:6379> getbit a 1
(integer) 1
127.0.0.1:6379> getbit a 2
(integer) 1
127.0.0.1:6379> getbit a 3
(integer) 1

从0位开始，对连续的4位无符号数做自增

127.0.0.1:6379> bitfield a incrby u4 0 1
1) (integer) 8

看下结果

127.0.0.1:6379> get a
"\x87"
127.0.0.1:6379> getbit a 0
(integer) 1
127.0.0.1:6379> getbit a 1
(integer) 0
127.0.0.1:6379> getbit a 2
(integer) 0
127.0.0.1:6379> getbit a 3
(integer) 0

测试下溢出

127.0.0.1:6379> setbit a 0 1
(integer) 0
127.0.0.1:6379> setbit a 1 1
(integer) 1
127.0.0.1:6379> setbit a 2 1
(integer) 1
127.0.0.1:6379> setbit a 3 1
(integer) 1
127.0.0.1:6379> setbit a 4 1
(integer) 0
127.0.0.1:6379> setbit a 5 1
(integer) 1
127.0.0.1:6379> setbit a 6 1
(integer) 1
127.0.0.1:6379> setbit a 7 1
(integer) 1
127.0.0.1:6379> get a
"\xff"

127.0.0.1:6379>  bitfield a incrby u8 0 1
1) (integer) 0
127.0.0.1:6379> get a
"\x00"
127.0.0.1:6379> getbit a 0
(integer) 0
127.0.0.1:6379> getbit a 1
(integer) 0
127.0.0.1:6379> getbit a 2
(integer) 0
127.0.0.1:6379>

overflow

bitfield 指令提供了溢出策略子指令 overflow，用户可以选择溢出行为，默认是折返 (wrap)，还可以选择失败 (fail) 报错不执行，以及饱和截断 (sat)，超过了范围就停留在最大最小值。overflow 指令只影响接下来的第一条指令，这条指令执行完后溢出策略会变成默认值折返 (wrap)。

折返 (wrap)

127.0.0.1:6379> setbit a 0 1
(integer) 0
127.0.0.1:6379> setbit a 1 1
(integer) 0
127.0.0.1:6379> setbit a 2 1
(integer) 0
127.0.0.1:6379> setbit a 3 1
(integer) 0
127.0.0.1:6379> setbit a 4 1
(integer) 0
127.0.0.1:6379> setbit a 5 1
(integer) 0
127.0.0.1:6379> setbit a 6 1
(integer) 0
127.0.0.1:6379> setbit a 7 1
(integer) 0
127.0.0.1:6379>  bitfield a overflow wrap incrby u8 0 1
1) (integer) 0
127.0.0.1:6379> get a
"\x00"

失败 (fail)

127.0.0.1:6379> setbit a 0 1
(integer) 0
127.0.0.1:6379> setbit a 1 1
(integer) 0
127.0.0.1:6379> setbit a 2 1
(integer) 0
127.0.0.1:6379> setbit a 3 1
(integer) 0
127.0.0.1:6379> setbit a 4 1
(integer) 0
127.0.0.1:6379> setbit a 5 1
(integer) 0
127.0.0.1:6379> setbit a 6 1
(integer) 0
127.0.0.1:6379> setbit a 7 1
(integer) 0
127.0.0.1:6379> get a
"\xff"
127.0.0.1:6379> bitfield a overflow fail incrby u8 0 1
1) (nil)

截断 (sat)

127.0.0.1:6379> bitfield a overflow sat incrby u8 0 1
1) (integer) 255
127.0.0.1:6379> get a
"\xff"