redis 用setbit(bitmap)统计活跃用户

redis 用setbit(bitmap)统计活跃用户

redis 用setbit(bitmap)统计活跃用户

redis


getspool.com的重要统计数据是实时计算的。Redis的bitmap让我们可以实时的进行类似的统计,并且极其节省空间。在模拟1亿2千8百万用户的模拟环境下,在一台MacBookPro上,典型的统计如“日用户数”(dailyunique users) 的时间消耗小于50ms, 占用16MB内存。Spool现在还没有1亿2千8百万用户,但是我们的方案可以应对这样的规模。我们想分享这是如何做到的,也许能帮到其它创业公司。

Bitmap以及Redis Bitmaps快速入门(Crash Course on Bitmap and Redis Bitmaps)

Bitmap(即Bitset)
Bitmap是一串连续的2进制数字(0或1),每一位所在的位置为偏移(offset),在bitmap上可执行AND,OR,XOR以及其它位操作。

位图计数(Population Count)

位图计数统计的是bitmap中值为1的位的个数。位图计数的效率很高,例如,一个bitmap包含10亿个位,90%的位都置为1,在一台MacBook Pro上对其做位图计数需要21.1ms。SSE4甚至有对整形(integer)做位图计数的硬件指令。

mark

Redis Bitmaps

Redis允许使用二进制数据的Key(binary keys) 和二进制数据的Value(binary values)。Bitmap就是二进制数据的value。Redis的 setbit(key, offset, value)操作对指定的key的value的指定偏移(offset)的位置1或0,时间复杂度是O(1)。

一个简单的例子:日活跃用户

为了统计今日登录的用户数,我们建立了一个bitmap,每一位标识一个用户ID。当某个用户访问我们的网页或执行了某个操作,就在bitmap中把标识此用户的位置为1。在Redis中获取此bitmap的key值是通过用户执行操作的类型和时间戳获得的。
mark

这个简单的例子中,每次用户登录时会执行一次redis.setbit(daily_active_users, user_id, 1)。将bitmap中对应位置的位置为1,时间复杂度是O(1)。统计bitmap结果显示有今天有9个用户登录。Bitmap的key是daily_active_users,它的值是1011110100100101。

因为日活跃用户每天都变化,所以需要每天创建一个新的bitmap。我们简单地把日期添加到key后面,实现了这个功能。例如,要统计某一天有多少个用户至少听了一个音乐app中的一首歌曲,可以把这个bitmap的redis key设计为play:yyyy-mm-dd-hh。当用户听了一首歌曲,我们只是简单地在bitmap中把标识这个用户的位置为1,时间复杂度是O(1)。

  1. Redis.setbit(play:yyyy-mm-dd, user_id, 1)
  2. Redis.setbit(play:yyyy-mm-dd, user_id, 1)

今天听过歌曲的用户就是key是play:yyyy-mm-dd的bitmap的位图计数。如果要按周或月统计,只要对这周或这个月的所有bitmap求并集,得出新的bitmap,在对它做位图计数
mark

利用这些bitmap做其它复杂的统计也非常容易。例如,统计11月听过歌曲的高级用户(premium user):
(play:2011-11-01∪ play:2011-11-02∪ … ∪ play:2011-11-30)∩premium:2011-11

1亿2千8百万用户的性能比较(Performance comparison using 128 million users)

下面的表格显示了在1亿2千8百万用户上完成的时间粒度为1天,一周,一个月的用户统计的时间消耗比较。

mark

补充:

BITOP operation destkey key [key ...]

对一个或多个保存二进制位的字符串 key 进行位元操作,并将结果保存到 destkey 上。

operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种:

  • BITOP AND destkey key [key ...] ,对一个或多个 key 求逻辑并,并将结果保存到 destkey 。
  • BITOP OR destkey key [key ...] ,对一个或多个 key 求逻辑或,并将结果保存到 destkey 。
  • BITOP XOR destkey key [key ...] ,对一个或多个 key 求逻辑异或,并将结果保存到 destkey 。
  • BITOP NOT destkey key ,对给定 key 求逻辑非,并将结果保存到 destkey 。
    除了 NOT 操作之外,其他操作都可以接受一个或多个 key 作为输入。

处理不同长度的字符串

当 BITOP 处理不同长度的字符串时,较短的那个字符串所缺少的部分会被看作 0 。

空的 key 也被看作是包含 0 的字符串序列。

可用版本:>= 2.6.0
时间复杂度:O(N)
返回值:
保存到 destkey 的字符串的长度,和输入 key 中最长的字符串长度相等。

BITOP 的复杂度为 O(N) ,当处理大型矩阵(matrix)或者进行大数据量的统计时,最好将任务指派到附属节点(slave)进行,避免阻塞主节点。

  1. redis> SETBIT bits-1 0 1 # bits-1 = 1001
  2. (integer) 0
  3. redis> SETBIT bits-1 3 1
  4. (integer) 0
  5. redis> SETBIT bits-2 0 1 # bits-2 = 1011
  6. (integer) 0
  7. redis> SETBIT bits-2 1 1
  8. (integer) 0
  9. redis> SETBIT bits-2 3 1
  10. (integer) 0
  11. redis> BITOP AND and-result bits-1 bits-2
  12. (integer) 1
  13. redis> GETBIT and-result 0 # and-result = 1001
  14. (integer) 1
  15. redis> GETBIT and-result 1
  16. (integer) 0
  17. redis> GETBIT and-result 2
  18. (integer) 0
  19. redis> GETBIT and-result 3
  20. (integer) 1
本博客所有文章如无特别注明均为原创。作者:长颈鹿复制或转载请以超链接形式注明转自 SZY
原文地址《redis 用setbit(bitmap)统计活跃用户

相关推荐

发表评论

路人甲 表情
Ctrl+Enter快速提交

网友评论(0)