数据结构——Redis中的bitmap

1. bitmap原理

8bit = 1byte = 0.001kb 通过最小的单位bit来进行0或1的设置，表示某个元素对应的值或状态。Redis中提供的函数接口有：

SETBIT key offset 对 key 所储存的字符串值，设置或清除指定偏移量上的位(bit)。 >= 2.2.0 O(1) GETBIT key offset 对 key 所储存的字符串值，获取指定偏移量上的位(bit)。 >= 2.2.0 O(1) BITCOUNT key 计算给定字符串中，被设置为 1 的比特位的数量。 >= 2.6.0 O(N) BITPOS key [start] [end] 返回位图中第一个值为 bit 的二进制位的位置。 >= 2.8.7 O(N) BITOP [AND OR NOT XOR] 对一个或多个保存二进制位的字符串 key 进行位元操作。 >= 2.6.0 O(N)

2. BITPOS的使用

在Redis中bitmap中，数据的存储是以的方式进行存储，也就是读取数据的时候，是从左往右读。因此，在使用bitpos命令时，返回值是从左往右找到的第一个为0或者为1的比特位的下标，且下标是从0开始计算。如下面的示例：

redis> SET mykey "xffxf0x00"
OK
redis> BITPOS mykey 0 # 查找字符串里面bit值为0的位置，从左向右找，结果为12（实际上是第13个bit位）
(integer) 12
redis> SET mykey "x00xffxf0"
OK
redis> BITPOS mykey 1 0 # 查找字符串里面bit值为1从第0个字节开始的位置
(integer) 8
redis> BITPOS mykey 1 2 # 查找字符串里面bit值为1从第2个字节(16)开始的位置
(integer) 16
redis> set mykey "x00x00x00"
OK
redis> BITPOS mykey 1 # 查找字符串里面bit值为1的位置，没找到则返回-1
(integer) -1
redis>

使用BITPOS有一个缺点，那就是每次只能找到一个为1的下标，因此，当我们需要统计处bitmap中有哪些位置为1的时候，则需要使用一些额外的代码计算，大致思想就是便利bitmap返回下标所在的字节，然后下一次从下一个字节开始查找，代码如下：

index, _ := rdb.BitPos(bitmapNameLast, 1).Result()
	indexTop := (index/8 + 1) * 8

	var userList []int64
	for index > 0 {
          
   
		for index < indexTop {
          
   
			val, _ := rdb.GetBit(bitmapNameLast, index).Result()
			if val == 1 {
          
   
				userList = append(userList, index)	// 记录下标
			}
		}
		index, _ = rdb.BitPos(bitmapNameLast, 1, index/8+1).Result()	// 当找不到1的时候，会返回-1，结束循环
	}

3. bitmap的优势以及应用

优势

1. 基于最小的单位bit进行存储，所以非常省空间。
2. 设置时候时间复杂度O(1)、读取时候时间复杂度O(n)，操作是非常快的。
3. 二进制数据的存储，进行相关计算的时候非常快。
4. 方便扩容

限制

redis中bit映射被限制在512MB之内，所以最大是2^32位。建议每个key的位数都控制下，因为读取时候时间复杂度O(n)，越大的串读的时间花销越多。

应用

1.一种是某一用户的横向扩展，即此个key值中记录这当前用户的各种状态值，允许无限扩展(2^32内)

2.一种是某一用户的纵向扩展，即每个key只记录当前业务属性的状态，每个uid当作bit位来记录信息(用户超过2^32内需要分片存储)

比如：

签到场景，每个用户的ID对应了bitmap中的偏移量，签到后直接将偏移量置为1，可以使用bitcount统计当天的签到数量，也可以使用bitop and 将连续几天的签到bitmap进行与运算，结果中依旧为1的则是连续签到的用户 视频属性，一个拥有亿级数据量的短视频app，视频存在各种属性(是否加锁、是否特效等等)，需要做各种标记。如果使用mysql，则会因为增加字段、读取效率而变得臃肿。直接记录在redis中，根据业务属性＋uid为key来存储。读取效率没问题，但是存储的角度来说key的数据量都大于value了，太耗费空间了