4.4 Bitmap
在我们平时开发过程中,会有⼀些布尔型数据需要存取,⽐如CSDN APP⽤户⼀年的签到记录(我快签到100天了,还是比较活跃的,欢迎与我交流),签了是1,没签是 0,要记录 365天。如果使⽤普通的key/value,每个⽤户要记录365个,⽤户上千万的时候,需要的存储空间是比较大的。
为了解决这个问题,Redis提供了位图数据结构,这样每天的签到记录只占据⼀个位,365 天就是365个位,46个字节(⼀个稍⻓⼀点的字符串)就可以完全容纳下,这就⼤⼤节约了存储空间。
位图不是特殊的数据结构,它的内容其实就是普通的字符串,也就是byte数组。我们可以使⽤普通的get/set直接获取和设置整个位图的内容,也可以使⽤位图操作getbit/setbit等将byte数组看成「位数组」来处理。
首先来看一个例子,字符串big
字母b的ASCII码为98，转换成二进制为 01100010 字母i的ASCII码为105，转换成二进制为 01101001 字母g的ASCII码为103，转换成二进制为 01100111
如果在Redis中,设置一个key,其值为big,此时可以get到big这个值,也可以获取到 big的ASCII码每一个位对应的值,也就是0或1
127.0.0.1:6379> set hello big OK 127.0.0.1:6379> getbit hello 0 # b的二进制形式的第1位，即为0 (integer) 0 127.0.0.1:6379> getbit hello 1 # b的二进制形式的第2位，即为1 (integer) 1
字符串Big对应的二进制¶
对应的key-value¶
我们看一下它常用的API
1.setbit¶
SETBIT key offset value
时间复杂度:O(1)
对key所储存的字符串值,设置或清除指定偏移量上的位(bit)。位的设置或清除取决于 value 参数,可以是0也可以是1。当key不存在时,自动生成一个新的字符串值。字符串会进行伸展(grown)以确保它可以将value保存在指定的偏移量上。当字符串值进行伸展时,空白位置以0填充。
offset参数必须大于或等于0,小于2^32(bit映射被限制在512 MB之内)。
redis> SETBIT bit 10086 1 (integer) 0 redis> GETBIT bit 10086 (integer) 1 redis> GETBIT bit 100 # bit 默认被初始化为 0 (integer) 0
偏移量不要太大,向上面的 SETBIT bit 10086 1 0-10085都要初始化成0
2.getbit¶
GETBIT key offset
时间复杂度:O(1) 对key所储存的字符串值,获取指定偏移量上的位(bit)。当offset 比字符串值的长度大,或者key不存在时,返回 0 。
# 对不存在的 key 或者不存在的 offset 进行 GETBIT， 返回 0 redis> EXISTS bit (integer) 0 redis> GETBIT bit 10086 (integer) 0 # 对已存在的 offset 进行 GETBIT redis> SETBIT bit 10086 1 (integer) 0 redis> GETBIT bit 10086
3.bitcount¶
时间复杂度:O(N) 计算给定字符串中,被设置为1的比特位的数量。
一般情况下,给定的整个字符串都会被进行计数,通过指定额外的start或end参数,可以让计数只在特定的位上进行。
start和end参数的设置和GETRANGE key start end命令类似,都可以使用负数值: 比如-1表示最后一个字节,-2表示倒数第二个字节,以此类推。
不存在的key被当成是空字符串来处理,因此对一个不存在的key进行BITCOUNT操作,结果为0。
redis> BITCOUNT bits (integer) 0 redis> SETBIT bits 0 1 # 0001 (integer) 0 redis> BITCOUNT bits (integer) 1 redis> SETBIT bits 3 1 # 1001 (integer) 0 redis> BITCOUNT bits (integer) 2
对了哦,前面提到的CSDN APP签到的应用,就是用这个命令实现的。
4.bitop¶
BITOP operation destkey key [key …]
对一个或多个保存二进制位的字符串key进行位元操作,并将结果保存到destkey上。返回保存到destkey的字符串的长度,和输入key中最长的字符串长度相等。
operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种：
- BITOP AND destkey key [key …],对一个或多个key求逻辑并，并将结果保存到 destkey 。
- BITOP OR destkey key [key …],对一个或多个key求逻辑或，并将结果保存到 destkey 。
- BITOP XOR destkey key [key …],对一个或多个 key 求逻辑异或，并将结果保存到 destkey 。
- BITOP NOT destkey key,对给定 key 求逻辑非，并将结果保存到 destkey 。
除了NOT操作之外,其他操作都可以接受一个或多个key作为输入。
处理不同长度的字符串¶
当BITOP处理不同长度的字符串时,较短的那个字符串所缺少的部分会被看作0 。 空的key也被看作是包含0的字符串序列。
redis> SETBIT bits-1 0 1 # bits-1 = 1001 (integer) 0 redis> SETBIT bits-1 3 1 (integer) 0 redis> SETBIT bits-2 0 1 # bits-2 = 1011 (integer) 0 redis> SETBIT bits-2 1 1 (integer) 0 redis> SETBIT bits-2 3 1 (integer) 0 redis> BITOP AND and-result bits-1 bits-2 (integer) 1 redis> GETBIT and-result 0 # and-result = 1001 (integer) 1 redis> GETBIT and-result 1 (integer) 0 redis> GETBIT and-result 2 (integer) 0 redis> GETBIT and-result 3 (integer) 1
5.bitpos¶
BITPOS key bit [start] [end]
时间复杂度:O(N),其中N为位图包含的二进制位数量 返回位图中第一个值为bit的二进制位的位置。在默认情况下,命令将检测整个位图,但用户也可以通过可选的start参数和end参数指定要检测的范围。
127.0.0.1:6379> SETBIT bits 3 1 # 1000 (integer) 0 127.0.0.1:6379> BITPOS bits 0 (integer) 0 127.0.0.1:6379> BITPOS bits 1 (integer) 3
下面我们再说一个应用
如果一个网站有1亿用户,假如user_id用的是整型,长度为32位,每天有5千万独立用户访问,如何判断是哪5千万用户访问了网站。
- 方式一:用set来保存
使用set来保存数据运行一天需要占用的内存为 32bit*50000000=(4 * 50000000) / 1024 /1024 MB,约为200MB
运行一个月需要占用的内存为6G，运行一年占用的内存为72G 30 * 200 = 6G
- 方式二：使用bitmap的方式
如果user_id访问网站，则在user_id的索引上设置为1，没有访问网站的user_id，其索引设置为0，此种方式运行一天占用的内存为 1 * 100000000 = 100000000 / 1014 /1024/ 8MB，约为12.5MB 运行一个月占用的内存为375MB，一年占用的内存容量为4.5G
由此可见,使用bitmap可以节省大量的内存资源。
值得注意的是
- bitmap是string类型,单个值最大可以使用的内存容量为512MB
- setbit时是设置每个value的偏移量,可以有较大耗时(偏移量不要太大)
- bitmap不是绝对好,用在合适的场景最好
