Bitmap在Redis中的应用

一叶而不知秋

向管中窥豹寻知外，坐井观天又出来。

作为铺垫，我们先来介绍一些Bitmap的相关内容：

位图主要用于快速检索关键字状态，通常要求关键字是一个连续的序列（或者关键字是一个连续序列中的大部分）， 最基本的情况，使用1bit标示一个关键字的状态（可标示两种状态），但根据需要也可以使用2bit（标示4种状态），3bit（标示8种状态）。 位图的主要应用场合：标示连续（或接近连续，即大部分会出现）的关键字序列的状态（状态数/关键字个数 越小越好）。

几种应用场景：

（1）磁盘空闲块的管理

很多文件系统采用bitmap管理磁盘空闲块，如果该块是空闲的，标为0，已使用则标为1； Ext3文件系统中使用位图来管理磁盘空闲块（空闲inode节点）。文件系统创建后，该文件系统拥有的块数以及inode节点数都是确定的，数据块区包含一系列连续的块（块号是连续的），于是可以用位图来标示数据块的分配状态（已分配、未分配两种状态，1bit即可标示）。

如下图，假设ext3的数据块从128开始，一直到1024，则需要1024-128 = 996bit = 128字节的位图空间。如下图，第1bit标示128号块已经被分配，第2bit标示129号块未被分配，依次类推。使用位图的高效性在于：1bit标示状态，节省存储空间，通过关键字来定位位图（偏移是固定的），效率高。

（2）区域服务器路由场景

腾讯的QQ号用一个数字标示，范围从0到20亿，每个QQ号都有可能出现，所有的QQ号被分散的存储北京、上海、深圳、武汉四个城市的服务器中，现在需要一个路由服务器快速的将登陆的QQ路由到正确的服务器，路由服务器可以读取四个QQ服务器的数据，并构建路由表（需全部存在内存中，内存限制1G），路由表该如何存储？

关键：QQ号从0-20亿，每个号码都有可能出现；服务器通过0、1、2、3标示，这四种状态可以用2bit来标示，于是可以考虑使用位图来描述路由表。

解法：从0~20亿，为每个QQ号分配2bit，路由服务器从QQ服务器中获取信息，并设置QQ于服务器号的对应关系。当QQ登录时，路由服务器根据QQ号定位到其对应的状态，并返回对应的服务器号。总的内存大小20亿 * 2 /8 = 5亿字节(约为0.5G)。

（3）大量数据的快速排序、查找、去重

关键：去掉电话号码的800后面就是7位的十进制整数，每个整数都有可能出现而且不会重复出现，可以采用各种排序算法对这些数据进行排序，但时间复杂度都在O(NlogN)及以上。

解法：因每个七位以内的整数都有可能出现，可以用1bit来标示电话号是否出现，遍历整个电话号序列，设置相应的位，遍历位图收集位被设置的号码即可，时间复杂度为O(N)；

【去重】场景：2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。 关键：一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。

解法：遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的状态位保持不变。 最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

Redis与Bitmap

因为redis的key和value本身就支持二进制的存储方式，所以bitmap只是一个独特的扩展，并不是新的数据类型。他的最大长度就是512M，即2^32个不同字节。

bitmap相关指令介绍：

getbit key offset //获取字符串类型键指定位置的二进制位的值

bitcount key [start] [end] //获取字符串类型键中为1的二进制位个数，start、end是字节的范围

bitpos key value start end //指定区间查询某个key的二进制位中首次出现0或1的位置（start和end是字节位置，不是bit位置）

bitop operation destkey key [key ...] //bitop命令可以对多个字符串进行位运算，并将结果存储在destkey参数指定的键中。bitop支持的运算操作有AND、OR、XOP和NOT。

魔术指令 bitfield：

bitfield key [GET type offset] [SET type offset value] [INCRBY type offset increment] [OVERFLOW WRAP|SAT|FAIL] bitfield 有三个子指令，分别是 get/set/incrby，它们都可以对指定位片段进行读写，但是最多只能处理 64 个连续的位，如果超过 64 位，就得使用多个子指令，bitfield 可以一次执行多个子指令。

示例：

应用场景：

（1）用户签到

1个用户1年会占用大约：1bit*365/8=45.625字节；

如果使用普通的 key/value，每个用户要记录 365 个，当用户量巨大时，需要的存储空间是惊人的。

（2）用户在线状态

只需要一个key，用户ID为offset，如果在线就设置为1，不在线就设置为0，1000万用户只需要100000000bit/8*=1.2MB的空间；

（3）统计活跃用户

使用时间作为cacheKey，然后用户ID为offset，如果当日活跃过就设置为1;

如果想计算某几天的活跃用户呢(暂且约定，统计时间内只要有一天在线就称为活跃)；

你如果想学技术 | 屯干货 | 聊职场