本文由简悦 SimpRead 转码，原文地址 segmentfault.com

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。< 来自官方文档 >
大概的空间占用计算公式是：($offset/8/1024/1024)MB

使用场景一：用户签到

很多网站都提供了签到功能 (这里不考虑数据落地事宜)，并且需要展示最近一个月的签到情况，如果使用 bitmap 我们怎么做？一言不合亮代码！

<?php
$redis = new Redis();
$redis->connect('127.0.0.1');
//用户uid
$uid = 1;
//记录有uid的key
$cacheKey = sprintf("sign_%d", $uid); // sign_1
//开始有签到功能的日期
$startDate = '2017-01-01';
//今天的日期
$todayDate = '2017-01-21';
//计算offset
$startTime = strtotime($startDate);
$todayTime = strtotime($todayDate);
$offset = floor(($todayTime - $startTime) / 86400);
echo "今天是第{$offset}天" . PHP_EOL; // 今天是第20天
//签到
//一年一个用户会占用多少空间呢？大约365/8=45.625个字节，好小，有木有被惊呆？
$redis->setBit($cacheKey, $offset, 1); //记录用户每天的签到情况，offset偏移量就是天数，将第20位的二进制位设置为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(就问你屌不屌？)
*/
//bitcount命令的参数start,end指的是 byte 而不是 bit;所以我们如果想准确计算某 bit 位到 bit 位中 1 的数量，需要通过get命令将整个值取出来自己计算
// 这是个错误的计算方式,正确的看下面的PHP如何处理
echo $redis->bitCount($cacheKey, 0, 20) . PHP_EOL;

使用场景二：统计活跃用户

使用时间作为 cacheKey，然后用户 ID 为 offset，如果当日活跃过就设置为 1
那么我该如果计算某几天 / 月 / 年的活跃用户呢 (暂且约定，统计时间内只有有一天在线就称为活跃)，有请下一个 redis 的命令
命令 BITOP operation destkey key [key ...]
http://redisdoc.com/bitmap/bitop.html
说明：对一个或多个保存二进制位的字符串 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";




/**

* 对于批量的获取，上面是一种效率低的办法，实际可以通过get获取到value，然后自己计算

* 具体计算方法改天再写吧，之前写的代码找不见了。。。

*/

Redis中BitMap是如何储存的

本文由简悦 SimpRead 转码，原文地址 segmentfault.com

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	bit4	bit5
byte0	1	0	1	0	1
byte1	0	1	0	1	0
byte2	1	0	0	0	1

执行getbit 16，对应的 byte 为floor(16 / 8)=2，落在byte2这一行，bit 为16%8=0，为第一列bit0上，我们可以立刻得到对应的值为 1，因为getbit为常数级计算，所以算法复杂度为O(1)

上篇文章中提到bitcount命令的参数start,end指的是 byte 而不是 bit，所以我们如果想准确计算某 bit 位到 bit 位中 1 的数量，需要通过get命令将整个值取出来自己计算，下面我用 PHP 演示如何计算正确的结果 (其实这种密集运算不适合 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 的数据需要循环计算 1_1024_1024*8=8388608,800 多 W 次啊，你说 CPU 累不累？)

计算方法二：查表法

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

我们事前将一个字节 (8 位) 对应的 1 的个数计算出来，放到一个数组中
8位二进制的范围为0到255

//对效率要求这么高，我们请出PHP的SplFixedArray
// SplFixedArray主要是处理数组相关的主要功能，与普通php array不同的是，它是固定长度的，且以数字为键名的数组，优势就是比普通的数组处理更快。通常情况下SplFixedArray要比php array快上20%~30%，所以如果你是处理巨大数量的固定长度数组，还是强烈建议使用。
$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,
  )
);

// 125的二进制为：1111101；为1的位有6个
echo "125对应的位数为:{$map[125]}" . PHP_EOL; // 125对应的位数为:6；
// 67的二进制为：1000011；为1的位有3个
echo "67对应的位数为:{$map[67]}" . PHP_EOL; // 67对应的位数为:3

我在本地测试，通过查表法处理 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;

本机测试：

get 数据花费 0.01s
unpack 花费 0.9s
foreach + 计算花费 1.48s
总花费 2.46s

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

数据库

Redis中bitmap的妙用