redis – 利用bitmap解决实时统计类需求
最近群友问了我一个这样的问题,说他们游戏公司有很多类似下面的运营需求:
需求:统计15天内注册且3天内活跃过的用户,向他们推送XXX消息。
性能背景:约1000万级注册用户,大约有10万活跃用户频繁上下线。
解决此类问题,可以想到2种不同的解决思路:
- 离线计算:通过日志记录注册与上线事件,推送之前进行日志挖掘统计,因为类似的运营需求特别多,所以这种基于日志挖掘的方案需要写很多计算脚本,日志量大也会导致运算周期长,实时性差,资源占用多。
- 实时计算:也就是我接下来要说明的一种更加简单高效的方案。
理解bitmap
1字节有8比特,2字节有16比特,3字节有24比特…
如果我们想知道某个用户是否活跃,则可以用0表示其没有登录,1表示其登录过,只占用1个比特位。
低内存占用
实际上,内存中只需要维护足够长的字节数组,就可以拥有足够多的比特位。
而对于1个用户ID来说,只需要通过ID/8定位到数组偏移量,ID%8定位到字节内的比特偏移量,就可以O(1)的时间获得对应的比特位,得知该用户是否登录过。
那么1000万用户需要一个多大的字节数组呢?只需要除以8换算为字节即可,下面我按MB计算:
1 2 |
>>> 10000000.0/8/1024/1024 1.1920928955078125 |
也就是1000万用户只需要1.192MB,多么节约内存啊。
我利用setbit命令在redis中将第1000万bit设置为1,那么redis实际会分配大约1MB多的字节数组,并将数组末尾的比特位设置为1:
1 2 3 4 5 6 7 |
[root@10-10-182-80 ~]# redis-cli 127.0.0.1:6379> setbit key1 10000000 1 (integer) 1 127.0.0.1:6379> getbit key1 10000000 (integer) 1 127.0.0.1:6379> strlen key1 (integer) 1250001 |
strlen key1表示这个bitmap占用了约1.25MB的内存,与我们的理论基本相符。
灵活的运算能力
回到需求自身:15天内注册 && 3天内活跃。
对于注册来说,可以按日期为key每天生成1个bitmap,这样可以灵活支持任意N天内注册的需求,而不仅仅是15天,如何做到呢?
在编程语言中,我们知道2个字节之间可以进行位运算(与、或、异或、非),那么2个字节数组之间也可以循环逐字节的进行位运算,从而实现2个bitmap之间的交并集处理。
我们知道1000万比特的bitmap对应1250001个字节,也就是百万个字节。
对于百万级的循环+位运算,对于现代CPU来说其耗时可以保持在1秒内,即便是ARM架构也不会耗时太久。
下面我利用redis演示如何利用bitmap求并集,得到2天内注册的所有用户:
1 2 3 4 5 6 |
127.0.0.1:6379> setbit 2019-12-03 1000 1 (integer) 0 127.0.0.1:6379> setbit 2019-12-04 1005 1 (integer) 0 127.0.0.1:6379> bitop OR tmp 2019-12-03 2019-12-04 (integer) 126 |
这里模拟12-03用户1000登录,12-04用户1005登录,那么对这两个bitmap求OR并集,结果保存到tmp。
那么tmp里面就有2个bit被设置过:
1 2 |
127.0.0.1:6379> bitcount tmp (integer) 2 |
通过循环迭代运算,可以得到任意N天的注册用户集合,那么如何同时满足3天内活跃呢?
其实活跃就是登录过的意思,因此只需要维护一套按天记录的登录集合,同样可以通过求并集得到3天内登录过的用户集合。
那么当我们拿到15天内注册集合以及3天内登录集合之后,只需要对这2个集合做一次AND运算,就可以得到同时满足的用户集合了。
遍历推送
得到最终集合后,我们要遍历每一个bit,对比特位为1的用户进行推送:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
[root@10-42-145-169 ~]# cat main.py import redis r = redis.Redis(host='localhost', port=6379, db=0) bitmap = r.get('tmp') total_bits = len(bitmap)*8 for i in range(total_bits): byte_offset = i // 8 bit_offset = i % 8 bit = (bitmap[byte_offset] << bit_offset) & 0x80 if bit != 0: print('user {} is set'.format(i)) |
redis get回来的是字节数组,我们关心的每一个比特,所以for循环内部需要计算bit坐落在哪个字节里的哪一位。
程序输出如下:
1 2 3 |
[root@10-42-145-169 ~]# python3 main.py user 1000 is set user 1005 is set |
符合之前我们的测试数据,而整个计算过程只需要花费数秒,对于一个离线推送程序来说是绰绰有余了。
如果文章帮助您解决了工作难题,您可以帮我点击屏幕上的任意广告,或者赞助少量费用来支持我的持续创作,谢谢~
