Redis 中 BitMap 是如何储存的,以及 PHP 如何处理

阅读 830
收藏 24
2017-01-25
原文链接:mp.weixin.qq.com

setbit,getbit这些命令在redis是如何储存和获取的呢?直接通过get获取到的值我们如何判断对应的位是0或者1?

本编文章可以看为[Redis中BitMap的妙用]的续篇。

在Redis中setbit ,set ,getbit ,get 这些命令本身都是对字符串(SDS)的操作。

当我们执行setbit key (0,2,5,9,12,16,21) 1 命令后,bitmap表示如下图:

byte bit0 bit1 bit2 bit3 bit4 bit5 bit6 bit7
byte0 1 0 1 0 0 1 0 0
byte1 0 1 0 0 1 0 0 0
byte2 1 0 0 0 0 1 0 0

执行getbit 16 ,对应的byte为floor(16 / 8) ,bit为16%8 ,我们可以立刻得到对应的值为1,因为getbit 为常数级计算,所以算法复杂度为O(1)

上篇文章中提到bitcount 命令的参数start ,end 指的是byte而不是bit,所以我们如果想准确计算某bit位到bit位中1的数量,需要通过get 命令将整个值取出来自己计算,下面我用PHP演示如何计算正确的结果(其实这种密集运算不适合PHP搞,但思路相同)

计算方法一:一个位一个位算(脑子不如高斯,我们一个一个加!)

<?php

$redis = new Redis();

$redis->connect('127.0.0.1');


$cacheKey = 'bitmap';

//我们将7,8,10对应的位置设置为1

$redis->setBit($cacheKey, 7, 1);

$redis->setBit($cacheKey, 8, 1);

$redis->setBit($cacheKey, 10, 1);


$value = $redis->get($cacheKey);


/**

* 解包(redis返回来的是二进制字符串,我们需要把它解成对应的数字)

* 关于unpack的用法,如果不了解,大家可以网上搜索学习,改天可以单独写篇文章分享

*/

$bitmap = unpack('C*', $value);

$count = 0;

foreach($bitmap as $key => $number) {

   for($i = 0; $i < 8; $i++) {

       if(($number >> $i & 1) == 1) {

           $count++;

       }

   }

}

看完之后有的同学会有疑问,代码中($number >> $i & 1) == 1 是怎么回事儿?

先不管>> ,当一个数与1做与运算 会发生什么?1的二进制表示为00000001 ,所以当与1做与运算 后,如果结果为1(00000001 ),说明这个数的最后一位肯定为1,反之为0,而>> 右移位可以帮我们将计算好的最后一位扔掉。网上看到一种更简洁的写法:

$count = 0;

foreach($bitmap as $key => $number) {

   //主要看这一段哈,更简洁,更有通用性

   while($number) {

       $count += $number & 1;

       $n >>= 1;

   }

}

然而天外有天,人外有人,又发现一个更厉害的,上面的算法循环次数等于总位数,而下面这个做到了只循环包含1的位数的循环次数

$count = 0;

foreach($bitmap as $key => $number) {

   //原理是什么?且听我下面慢慢道来

   while($number) {

       $number &= ($number - 1);

       $count++;

   }

}

上面关键代码只有一句$number &= ($number - 1); ,上一个算法是一位一位的移除,这个算法是每次清除最右边的1,因为二进制相加逢二进一,二进制数每加一,尾数就会从0变成1或者从1变成0,而每减一最后一位的1一定会变成0 ,这样当我们计算$number & ($number-1) 的时候,会将最右的1移除掉,比如9&8=1001&1000=1000 ,再比如8&7=1000&0111=0000

上面的方法有一个最大的不确定因素就是其中1的个数,如果所有的位都为1,那么我们一次循环都节省不了(1MB的数据需要循环计算110241024*8=8388608,800多W次啊,你说CPU累不累?)

计算方法二:查表法

查表法是一种典型的空间换时间的算法,使用方法如下:

我们事前将一个字节(8位)对应的1的个数计算出来,放到一个数组中

//对效率要求这么高,我们请出PHP的SplFixedArray

$map = SplFixedArray::fromArray(

   array(

       0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

       4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,

   )

);


echo "125对应的位数为:{$map[125]}" . PHP_EOL;

echo "67对应的位数为:{$map[67]}" . PHP_EOL;

我在本地测试,通过查表法处理8MB的数据只需要0.7秒,而上面的方法需要2.3秒。当然上面的是8bit的表,如果改成16bit的表,速度会更快(但是空间占用会变大,根据实际情况调整)

计算方法三:variable-precision SWAR(不知道如何翻译)

这是一个不会带来内存压力并且效率还可以的算法

//这个最大支持32位运算

function getCount($n) {

   $n = ($n & 0x55555555) + (($n >> 1) & 0x55555555); //line1

   $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333); //line2

   $n = ($n & 0x0f0f0f0f) + (($n >> 4) & 0x0f0f0f0f); //line3

   $n = ($n & 0x00ff00ff) + (($n >> 8) & 0x00ff00ff); //line4

   $n = ($n & 0x0000ffff) + (($n >> 16) & 0x0000ffff); //line5

   return $n;

}

一眼看上去,这什么什么啊。。(0x 开头代表十六进制0b 开头代表二进制)

0x55555555=0b0101010101010101

0x33333333=0b0011001100110011

0x0f0f0f0f=0b0000111100000011

我们将$n设置为一个比较小的数,方便理解,假设$n=153(0b10011001 )

第一行:

($n&0x55555555 的目的是以二个位为一个分组,取出后一位)

0b10011001 & 0b01010101 = 0b00010001 (获取奇数位)

0b01001100 & 0b01010101 = 0b01000100 (因为向右移动了一位,so获取偶数位)

0b00010001 + 0b01000100 = 0b01010101 (结果中没两位表示其中1的个数)

第二行、第三行。。。到最后一只都是一个思想,就是2合1,4合1,8合1,16合1,如果要计算64位,继续32合1就可以了。

上面的PHP都是一个字节一个字节计算的,我们知道32位的数,占用4个字节,在PHP如何处理比较好呢

$redis = new Redis();

$redis->connect('127.0.0.1');


$cacheKey = 'bitmap'

$redis->setBit($cacheKey, 1, 1);

$redis->setBit($cacheKey, 12345, 1);

$redis->setBit($cacheKey, 123456789, 1);


//大约14MB的数据量

$value = $redis->get($cacheKey);


//解压,这里的N很重要(unsigned long (always 32 bit, big endian byte order)),因为redis里面的数据就是按大头存的

$bitmap = unpack('N*', $value);


$total = 0;


foreach($bitmap as $n) {

   $n = ($n & 0x55555555) + (($n >> 1) & 0x55555555);

   $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333);

   $n = ($n & 0x0f0f0f0f) + (($n >> 4) & 0x0f0f0f0f);

   $n = ($n & 0x00ff00ff) + (($n >> 8) & 0x00ff00ff);

   $total += ($n & 0x0000ffff) + (($n >> 16) & 0x0000ffff);  

}


echo $total;

本机测试:

  1. get数据花费0.01s

  2. unpack花费0.9s

  3. foreach+计算花费1.48s

  4. 总花费2.46s

    因为数据较大,我对2秒多的计算时间略满意,Redis本身的bitcount 会根据字符串长度自动选择variable-precision SWAR 还是查表法

    技术手段没有什么最好,只有最合适。如果本文帮到了你,关注公众号支持一下。



评论