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计算:

也就是1000万用户只需要1.192MB,多么节约内存啊。

我利用setbit命令在redis中将第1000万bit设置为1,那么redis实际会分配大约1MB多的字节数组,并将数组末尾的比特位设置为1:

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天内注册的所有用户:

这里模拟12-03用户1000登录,12-04用户1005登录,那么对这两个bitmap求OR并集,结果保存到tmp。

那么tmp里面就有2个bit被设置过:

通过循环迭代运算,可以得到任意N天的注册用户集合,那么如何同时满足3天内活跃呢?

其实活跃就是登录过的意思,因此只需要维护一套按天记录的登录集合,同样可以通过求并集得到3天内登录过的用户集合。

那么当我们拿到15天内注册集合以及3天内登录集合之后,只需要对这2个集合做一次AND运算,就可以得到同时满足的用户集合了。

遍历推送

得到最终集合后,我们要遍历每一个bit,对比特位为1的用户进行推送:

redis get回来的是字节数组,我们关心的每一个比特,所以for循环内部需要计算bit坐落在哪个字节里的哪一位。

程序输出如下:

符合之前我们的测试数据,而整个计算过程只需要花费数秒,对于一个离线推送程序来说是绰绰有余了。

如果文章帮助了你,请帮我点击1次谷歌广告,或者微信赞助1元钱,感谢!

知识星球有更多干货内容,对我认可欢迎加入:

发表评论

电子邮件地址不会被公开。