Redis中bitmap应用场景

老板最近提了一个需求，统计应用的活跃用户。却暂时又不想接入第三方统计。 那么只能后端来出来处理了。 在首页的接口上做个钩子，记录用户。 查了些资料，发现redis的bit貌似是最优的处理方法了。 在Redis中我们经常用到set,get等命令，细心的你有没有发现，还有几个相似的命令叫setbit,getbit，它们是用来干嘛的？ ### **BitMap是什么** 就是通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身。我们知道8个bit可以组成一个Byte，所以bitmap本身会极大的节省储存空间。 ### **Redis中的BitMap** Redis从2.2.0版本开始新增了`setbit`,`getbit`,`bitcount`等几个bitmap相关命令。虽然是新命令，但是并没有新增新的数据类型，因为`setbit`等命令只不过是在`set`上的扩展。 ### **setbit命令介绍** 指令`SETBIT key offset value` 复杂度`O(1)`设置或者清空key的value(字符串)在offset处的bit值(只能只0或者1)。 ### **空间占用、以及第一次分配空间需要的时间** 在一台2010MacBook Pro上，offset为2^32-1（分配512MB）需要～300ms，offset为2^30-1(分配128MB)需要～80ms，offset为2^28-1（分配32MB）需要～30ms，offset为2^26-1（分配8MB）需要8ms。&lt;来自官方文档&gt; 大概的空间占用计算公式是：`($offset/8/1024/1024)MB` ### **使用场景一：用户签到**（类似我现在要做的需求） 很多网站都提供了签到功能(这里不考虑数据落地事宜)，并且需要展示最近一个月的签到情况，如果使用bitmap我们怎么做？一言不合亮代码！ ``` <span class="hljs-section"><?php $redis = new Redis(); $redis-></span>connect('127.0.0.1'); //用户uid $uid = 1; //记录有uid的key $cacheKey = sprintf("sign_%d", $uid); //开始有签到功能的日期 $startDate = '2017-01-01'; //今天的日期 $todayDate = '2017-01-21'; //计算offset $startTime = strtotime($startDate); $todayTime = strtotime($todayDate); $offset = floor(($todayTime - $startTime) / 86400); echo "今天是第{$offset}天" . PHP_EOL; //签到 //一年一个用户会占用多少空间呢？大约365/8=45.625个字节，好小，有木有被惊呆？ $redis->setBit($cacheKey, $offset, 1); //查询签到情况 $bitStatus = $redis->getBit($cacheKey, $offset); echo 1 == $bitStatus ? '今天已经签到啦' : '还没有签到呢'; echo PHP_EOL; //计算总签到次数 echo $redis->bitCount($cacheKey) . PHP_EOL; /** * 计算某段时间内的签到次数 * 很不幸啊,bitCount虽然提供了start和end参数，但是这个说的是字符串的位置，而不是对应"位"的位置 * 幸运的是我们可以通过get命令将value取出来，自己解析。并且这个value不会太大，上面计算过一年一个用户只需要45个字节 * 给我们的网站定一个小目标，运行30年，那么一共需要1.31KB(就问你屌不屌？) */ //这是个错误的计算方式 echo $redis->bitCount($cacheKey, 0, 20) . PHP_EOL; ``` ### **使用场景二：统计活跃用户** 使用时间作为cacheKey，然后用户ID为offset，如果当日活跃过就设置为1 那么我该如果计算某几天/月/年的活跃用户呢(暂且约定，统计时间内只有有一天在线就称为活跃)，有请下一个redis的命令 命令 `BITOP operation destkey key [key ...]` 说明：对一个或多个保存二进制位的字符串 key 进行位元操作，并将结果保存到 destkey 上。 说明：BITOP 命令支持 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种参数 ``` //日期对应的活跃用户 
$data = array(
 '2017-01-10' => array(1,2,3,4,5,6,7,8,9,10),
 '2017-01-11' => array(1,2,3,4,5,6,7,8),
 '2017-01-12' => array(1,2,3,4,5,6),
 '2017-01-13' => array(1,2,3,4),
 '2017-01-14' => array(1,2)
 );
 
//批量设置活跃状态
 foreach($data as $date=>$uids) {
 $cacheKey = sprintf("stat_%s", $date);
 foreach($uids as $uid) {
 $redis->setBit($cacheKey, $uid, 1);
 } 
} 

$redis->bitOp('AND', 'stat', 'stat_2017-01-10', 'stat_2017-01-11', 'stat_2017-01-12') . PHP_EOL;
 //总活跃用户：6
 echo "总活跃用户：" . $redis->bitCount('stat') . PHP_EOL;

 $redis->bitOp('AND', 'stat1', 'stat_2017-01-10', 'stat_2017-01-11', 'stat_2017-01-14') . PHP_EOL;
 //总活跃用户：2
 echo "总活跃用户：" . $redis->bitCount('stat1') . PHP_EOL; 

$redis->bitOp('AND', 'stat2', 'stat_2017-01-10', 'stat_2017-01-11') . PHP_EOL;
 //总活跃用户：8
 echo "总活跃用户：" . $redis->bitCount('stat2') . PHP_EOL; ``` 假设当前站点有5000W用户，那么一天的数据大约为50000000/8/1024/1024=6MB ### **使用场景三：用户在线状态** 使用bitmap是一个节约空间效率又高的一种方法，只需要一个key，然后用户ID为offset，如果在线就设置为1，不在线就设置为0，和上面的场景一样，5000W用户只需要6MB的空间。 ``` /批量设置在线状态 $uids = range(1, 500000);
 foreach($uids as $uid) {
 $redis->setBit('online', $uid, $uid % 2); 
}
 //一个一个获取状态 
$uids = range(1, 500000);
 $startTime = microtime(true);
 foreach($uids as $uid) {
 echo $redis->getBit('online', $uid) . PHP_EOL; 
} 
$endTime = microtime(true);
 //在我的电脑上，获取50W个用户的状态需要25秒
 echo "total:" . ($endTime - $startTime) . "s"; ``` **bitmap高级篇** setbit,getbit这些命令在redis是如何储存和获取的呢？直接通过get获取到的值我们如何判断对应的位是0或者1？ 在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搞，但思路相同) #### **计算方法一：一个位一个位算(脑子不如高斯，我们一个一个加！)** ``` <span class="hljs-section"><?php $redis = new Redis(); $redis-></span>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 &amp;= ($number - 1);,上一个算法是一位一位的移除，这个算法是每次清除最右边的1，因为二进制相加逢二进一，二进制数每加一，尾数就会从0变成1或者从1变成0，而每减一最后一位的1一定会变成0，这样当我们计算$number &amp; ($number-1)的时候，会将最右的1移除掉，比如9&amp;8=1001&amp;1000=1000,再比如8&amp;7=1000&amp;0111=0000。 上面的方法有一个最大的不确定因素就是其中1的个数，如果所有的位都为1，那么我们一次循环都节省不了(1MB的数据需要循环计算1\_1024\_1024\*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=153(0b10011001) 第一行： ($n&amp;0x55555555的目的是以二个位为一个分组，取出后一位) 0b10011001 &amp; 0b01010101 = 0b00010001(获取奇数位) 0b01001100 &amp; 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; ``` 本机测试： get数据花费0.01s unpack花费0.9s foreach+计算花费1.48s 总花费2.46s 因为数据较大，我对2秒多的计算时间略满意，Redis本身的bitcount会根据字符串长度自动选择variable-precision SWAR还是查表法。 本文参考： [https://segmentfault.com/a/1190000008188655](https://segmentfault.com/a/1190000008188655) [https://segmentfault.com/a/1190000008205145](https://segmentfault.com/a/1190000008205145)