Redis中Bitops逻辑解析

研究Bitops的一小段历史

产品有个小需求,统计首页每日的pv/uv,想找一个省时省力的方法尽快完成这个需求,虽然简单,但是也问了一圈之前的leader们,看看他们都会给出什么样的答案。

第一个leader比较保守,php框架方面的经验比较丰富,但server架构层面还是停留在多年前的水准,他给的方案是,解析nginx access.log得到每日的数据,然后scp到一台服务器来满足汇总的需求。首先,数据的解析需要用awk或者java写逻辑,当有大量统计点需要做的时候就需要在解析逻辑上下文章,维护难,可读性也比较差;其次,只能定时收集,实时性与性能成反比。

第二个leader比较激进,对于自动化架构情有独钟,但是比较现实,对于多余需求不会增加人力成本维护。他给的方案是直接用内存手机用户信息,实时性好,做起来也快,但当统计点多的时候,需要在程序设计时考虑掉灵活度,基于Redis封装一层针对pv/uv统计的wrapper,用于简化上层逻辑。

最后采用的这种方法,利用Redis写了一个计数器用于统计pv,用Set存储用户uid,用于计算uv。由于当前Redis是单机状态,没有做高可用,而且与其他业务公用,所以需要定期清理掉,所以搭建Mongodb作为持久存储用于给后台提供长久的数据。这里由于犯懒,没有对Redis进行灵活度上的封装,如果统计点多了就比较麻烦。而且后续相似业务也不能重用,这就是快的代价

同事在面对这个问题的时候,也研究了下Redis,发现Redis提供对bit的支持,主要支持一下几个操作:getbit,setbit,bitcount,bitpos,bitop。这几个操作具体是干什么的不详细介绍。主要介绍下程序设计原理:

用sds(string)来存储bit,最大限制就是Redis中每个key对应的value的最大值512MB,512 × 1024 × 1024 × 8位,40亿位,容量能满足几乎所有场景。

setbit,首先定位传入的当前offset位于第几个byte,然后offset计算需要修改字节中的第几位,然后进行修改,代码如下:

// 右移3位相当于除以8,计算属于第几个字节
byte = bitoffset >> 3;
// 1字节有8bit,计算需要修改从左边数第几个bit
bit = 7 - (bitoffset & 0x7);
// 去除旧的bit的值用于返回
bitval = byteval & (1 << bit);

redisPopcount,如果之前你有做过求一个二进制串中所有1的位数的算法,惯性思维,对于我来说,一般O(n)的时间复杂度基本算是最优解,我就不会想再进一步缩小n了。这个函数给我上了一课,几年的业务逻辑coding已经对我的算法意识没有丝毫的积极影响。这个函数主要用了两个算法:
1 静态表,定义256大小的char数组bitsinbyte,bitsinbyte[i]中存储的就是i的二进制中1的个数,8bit可以表示的数字是256个(0~255),通过数组可以求出1byte中的1的个数。剩下的只需要你对输入的binary每次右移8位,直到binary为0

2 平行算法,类似归并查找,计算汇总相邻2个元素中1的个数,最后得到总数,不过时间复杂度和归并完全不同,因为有位属性参数到算法中。假设当前以28个byte为单位,每个单位分为7组,每组4byte工32位,将每个32位中1的个数汇总到前8为中,最后累加即可。

对于平行算法需要多少两句,该算法可读性非常差,尽量从抽象层面理解,下面拿1个32位group做个例子:

uint32_t aux1;
// 汇总相邻2位
aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
// 利用之前的结果,汇总相邻4位
aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
// 汇总8位,汇总后该group中每个byte表示的十进制数就是每个byte中1的个数
aux1 = (aux1 + (aux1 >> 4)) & 0x0F0F0F0F);
// 累加4个byte到32位中的前8位
uint32_t result = aux1 * 0x01010101;
// 计算最终结果
result = result >> 24;

此外redisPopcount还做了一个对齐优化,防止多次访问内存读取同一个32位group

参考:
http://www.cnblogs.com/ourroad/p/4883703.html
http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

Redis中Bitops逻辑解析
Share this