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;

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190119G0YI7800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券