Redis中bitmap应用场景

2020-05-15 16:40:32 查看 1045 回复 0

老板最近提了一个需求,统计应用的活跃用户。却暂时又不想接入第三方统计。
那么只能后端来出来处理了。
在首页的接口上做个钩子,记录用户。

查了些资料,发现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。<来自官方文档>

大概的空间占用计算公式是:($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);

//开始有签到功能的日期
$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;

//总活跃用户:6echo "总活跃用户:" . $redis->bitCount('stat') . PHP_EOL;



$redis->bitOp('AND', 'stat1', 'stat_2017-01-10', 'stat_2017-01-11', 'stat_2017-01-14') . PHP_EOL;

//总活跃用户:2echo "总活跃用户:" . $redis->bitCount('stat1') . PHP_EOL;



$redis->bitOp('AND', 'stat2', 'stat_2017-01-10', 'stat_2017-01-11') . PHP_EOL;

//总活跃用户:8echo "总活跃用户:" . $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搞,但思路相同)

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

<?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的个数计算出来,放到一个数组中

//对效率要求这么高,我们请出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&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还是查表法。

本文参考:

https://segmentfault.com/a/1190000008188655

https://segmentfault.com/a/1190000008205145