面试王牌：Redis源码之BitMap

在上面的《??面试杀手锏：Redis源码之SDS??》中，我们深入分析了SDS的实现。本次介绍的位图（BitMap）是借助SDS实现的。在本文的最后，我们讲解了BitMap解决腾讯面试题的方法，并基于BitMap实现了一个模仿GitHub提交数的日历图表。我希望你会喜欢看它。1.位图介绍如果我们需要记录一个用户在一年中是否每天登录我们的系统，我们应该如何完成这个需求呢？如果使用KV存储，每个用户需要记录365条，当用户数达到数亿时，这需要的存储空间是惊人的。Redis为我们提供了位图数据结构。每个用户每天的登录记录只占一个bit，365个bit就是365天的365个bit。只需要46个字节来存储，大大节省了存储空间。位图数据结构其实并不是一个全新的东西。我们可以简单的认为它是一个数组，但是里面的内容只能是0或者1（二进制位数组）。2、命令实战Redis提供了四种常用命令SETBIT、GETBIT、BITCOUNT、BITOP，用于处理二进制位数组。SETBIT：指定位数组偏移处的二进制位设置值。偏移量从0开始计数，二进制位的值只能为0或1。返回原位置值。GETBIT：获取指定偏移处二进制位的值。BITCOUNT：统计位数组中值为1的二进制位的个数。BITOP：对多个位数组进行按位与、或、异或运算。127.0.0.1:6379>SETBIT第一个01#00000001（整数）0127.0.0.1:6379>SETBIT第一个31#00001001（整数）0127.0.0.1:6379>SETBIT第一个00#00001000（整数）1127.0.11270.1:6379>GETBIT第一个0（整数）0127.0.0.1:6379>GETBIT第一个3（整数）1127.0.0.1:6379>BITCOUNT第一个#00001000（整数）1127.0.0.1:6379>SETBIT第一个01#00001001(整数）0127.0.0.1:6379>BITCOUNT第一个#00001001（整数）2127.0.0.1:6379>SETBIT第一个11#00001011（整数）0127.0.0.1:6379>BITCOUNT第一个#00001011（整数）0.3127：6379>SETBITx31（整数）0127.0.0.1:6379>SETBITx11（整数）0127.0.0.1:6379>SETBITx01#00001011（整数）0127.0.0.1:6379>SETBITy21（整数)0127.0.0.1:6379>SETBITy11#00000110(整数)0127.0.0.1:6379>SETBITz21(整数)0127.0.0.1:6379>SETBITz01#00000101(整数)0127.0.0.1:6379>BITOPANDandResxyz#00000000(整数)1127.0.0.1:6379>BITOPORorResxyz#00001111(整数)1127.0.0.1:6379>BITOPXORxyz#00001000(执行按位取反给定的位数组127.0.0.1:6379>SETBIT值01（整数）0127.0.0.1:6379>SETBIT值31#00001001（整数）0127.0.0.1:6379>BITOPNOTnotValue值#11110110（整数）13。BitMap源码分析3.1数据结构下面展示了一个用SDS表示的一个字节（8位）长的位图：扩展：Redis中的每个对象都是一个typedef，用一个redisObject结构体来表示structredisObject{//typeunsignedtype:4;//encodingunsignedencoding:4;unsignedlru:REDIS_LRU_BITS;/*lrutime(相对于server.lruclock)*///引用计数intrefcount;//执行底层实现数据结构的指针void*ptr;}robj;type的值为REDIS_STRING，说明这是一个字符串对象sdshdr.len的值为1，说明这个SDS保存了一个1字节位数组buf[buf数组中的0。]其实保存的是位数组buf[1]，buf数组中就是自动追加的\0字符。i字节，buf[i]后面的8格代表这个字节上的8位。为了再次对齐大家的思路，另外一个位数组如下：位数组由buf[0]、buf[1]、buf[2]存储，真实数据为1111000011000011101001013.2GETBITGETBIT为用于返回偏移量位数组的二进制位的值。值得注意的是，GETBIT的时间复杂度为O(1)。GETBIT命令的执行过程如下：GETBIT命令源码如下：voidgetbitCommand(client*c){robj*o;字符llbuf[32]；uint64_t位偏移；size_t字节，位；size_tbitval=0;//获取偏移量if(getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0)!=C_OK)return;//找到对应的位图对象if((o=lookupKeyReadOrReply(c,c->argv[1],shared.czero))==NULL||checkType(c,o,OBJ_STRING))return;//计算偏移量在位数组中的哪一行byte=bitoffset>>3;//计算一行中偏移的个数，相当于取模bit=7-(bitoffset&0x7);//#definesdsEncodedObject(objptr)(objptr->encoding==OBJ_ENCODING_RAW||objptr->encoding==OBJ_ENCODING_EMBSTR)if(sdsEncodedObject(o)){//SDS是RAW或EMBSTR类型if(byteptr))//获取指定位置的值//注意不是真正的二维数组，不能用((uint8_t*)o->ptr)[byte][bit]来获取~bitval=((uint8_t*)o->ptr)[byte]&(1<ptr))bitval=llbuf[byte]&(1<argv[2],&bitoffset,0,0)!=C_OK)return;//获取我们需要设置的值if(getLongFromObjectOrReply(c,c->argv[3],&on,err)!=C_OK)return;/*判断指定值是0还是1*/if(on&~1){//如果设置了0和1以外的值，直接报错addReplyError(c,err);返回;}//根据key查询SDS对象（会自动展开）if((o=lookupStringForBitCommand(c,bitoffset))==NULL)return;/*获取当前值*/byte=bitoffset>>3;byteval=((uint8_t*)o->ptr)[byte];位=7-(位偏移&0x7);bitval=byteval&(1<<位);/*更新值并返回旧值*/byteval&=~(1<ptr)[byte]=byteval；//发送数据修改通知signalModifiedKey(c,c->db,c->argv[1]);notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id);服务器脏++；addReply(c,bitval?shared.cone:shared.czero);}拿栗子1.0array来表示上图中的三字节位数组。以SETBIT数组101为例：举个栗子2.0，假设目标位数组长度为1字节。执行SETBITarray121，如下：3.4BITCOUNTBITCOUNT命令用于统计给定的位数组中值为1的二进制位的个数。功能看似简单，但实际上要高效地实现这条命令并不容易，需要一些精巧的算法。计算位数组中非零位的数量在数学上称为“计算汉明权重”。3.4.1暴力遍历BITCOUNT命令最简单直接的实现方式是遍历位数组中的每个二进制位，遇到值为1的二进制位时计数器加1。小数据还好，大数据直接PASS！3.4.2查表法对于一个有限集，集合元素的排列是有限的，对于一个有限长度的位数组，它所能表示的二进制数的位排列也是有限的。根据这个原理，我们可以创建一个表，表的键是一定排列的位数组，表的值是对应位数组中值为1的二进制位的个数。对于8位长的位数组，我们可以创建下表。通过这张表，我们可以一次从位数组中读取8位，然后根据这8位的值查表就可以直接知道这个值包含多少位。1.不幸的是，查表方式很耗内存！3.4.3二进制位统计算法：精度变SWAR目前已知最高效的通用算法是精度变SWAR算法。恒定时间（这太棒了