redis亿级用户登录日活及统计

2021/02/04 redis
如果文章图片无法显示,可尝试配置host:修复Github图片资源无法显示问题

redis-亿级用户登录日活及统计

面试真题:如何用redis存储统计1亿用户一年的登录情况,并快速检索任意时间窗口内的活跃用户数量?

img

方案一:使用string(排除)

如何用合适的数据类型来存储1亿用户的数据,用普通的字符串来存储肯定不行。经过查看一个最简单的kv(key为aaa,value为1)的内存占用,发现为48byte。

image

假设每个用户每天登陆需要占据1对KV的话,那一亿就是(48*100000000)/1024/1024/1024=4.47G。这还是一天的量。

方案二:bitmap

1、bitmap介绍

在redis 2.2.0版本之后,新增了一个位图数据,其实它不是一种数据结构。实际上它就是一个一个字符串结构(涉及单个bitmap可存储最大值问题),只不过value是一个二进制数据,每一位只能是0或者1。redis单独对bitmap提供了一套命令。可以对任意一位进行设置和读取。

主要命令有:

具体可参考:http://redisdoc.com/bitmap/index.html

相关语法为:

  • SETBIT key offset value
  • GETBIT key offset
  • BITCOUNT key [start] [end]
  • BITOP operation destkey key [key …]

注意事项:

  • bitmap本质为字符串,使用type命令对bitmap的相关key进行操作,可以看出结果为”string”,因此最大不能超过512MB,故可存储id号最大为:4294967295=4294967296-1(42亿多),计算方式为512MB可容纳的最大数据:232 = 512* 28 * 220
  • offset为偏移量,对使用大的 offsetSETBIT 操作来说,内存分配可能造成 Redis 服务器被阻塞

2、登录统计方案设计

(1)登录标记

用户登录时,使用setbit命令和用户id(假设id=123456)标记当日(2020-10-05)用户已经登录,具体命令如下:

# 时间复杂度O(1)
setbit login:20201005 123456 1

(2)每日用户登录数量统计

# 时间复杂度O(N)
bitcount login:20201005

(3)活跃用户(连续三日登录)统计

如果我们想要获取近三日活跃用户数量的话,可以使用bitop命令,

bitmap的bitop命令支持对bitmap进行AND(与)(OR)或XOR(亦或)NOT(非)四种相关操作,我们对近三日的bitmap做AND操作即可,操作之后会形成一个新的bitmap,我们可以取名为login:20201005:b3

# 时间复杂度O(N)
bitop and login:20201005:b3 login:20201005 login:20201004 login:20201003

然后我们可以对login:20201005:b3 使用bitcount或者getbit命令,用于统计活跃用户数量,或者查看某个用户是否为活跃用户

(4)内存占用

我们新建一个bitmap,用于测试最大值4294967296-1,内存相关占用:

127.0.0.1:6379> setbit login:20201005 4294967296 1
(error) ERR bit offset is not an integer or out of range
127.0.0.1:6379> setbit login:20201005 4294967295 1
(integer) 0

我们可以发现直接设置4294967296(超过最大值)会出现报错。

然后退出redis-cli,执行如下命令(测试环境使用),结果如下:

redis-cli -a pdabc  --bigkeys
Warning: Using a password with '-a' or '-u' option on the command line interface may not be safe.

# Scanning the entire keyspace to find biggest keys as well as
# average sizes per key type.  You can use -i 0.1 to sleep 0.1 sec
# per 100 SCAN commands (not usually needed).

[00.00%] Biggest string found so far 'login:20201005' with 536870912 bytes

-------- summary -------

Sampled 1 keys in the keyspace!
Total key length in bytes is 14 (avg len 14.00)

Biggest string found 'login:20201005' has 536870912 bytes

1 strings with 536870912 bytes (100.00% of keys, avg size 536870912.00)
0 lists with 0 items (00.00% of keys, avg size 0.00)
0 hashs with 0 fields (00.00% of keys, avg size 0.00)
0 streams with 0 entries (00.00% of keys, avg size 0.00)
0 sets with 0 members (00.00% of keys, avg size 0.00)
0 zsets with 0 members (00.00% of keys, avg size 0.00)

我们发现我们仅仅设置了一个值,但是这个bitmap已经达到了536870912 bytes = 64MB,如此想想还是有些恐怖的,尤其在初次设置大的offect时会进行内存分配,可能会出现内存分配问题。

期间出现一个有趣的小插曲,当我执行对这个大key进行如下get操作时,直接把redis服务搞崩溃了,因此禁止在生产环境下操作数据还是很有必要的。

[root@tao ~]# redis-cli
127.0.0.1:6379> type login:20201005
string
127.0.0.1:6379> get login:20201005
Could not connect to Redis at 127.0.0.1:6379: Connection refused
(3.09s)
not connected> exit
[root@tao ~]# ps -ef | grep redis
root     31897 24249  0 16:39 pts/0    00:00:00 grep --color=auto redis

如果key是比较小,正常情况是不会出现这种情况的哦,因此在超大量数据下,使用bitmap还有待商榷,但是在数据量不是很大,但是对统计要求精确的场景,可以使用此方案。

127.0.0.1:6379> setbit login:20201005 123 1
(integer) 1
127.0.0.1:6379> get login:20201005
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x10"

注意:

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

方案三:HyperLogLog

redis从2.8.9之后增加了HyperLogLog数据结构。这个数据结构,根据redis的官网介绍,这是一个概率数据结构,用来估算数据的基数。能通过牺牲准确率来减少内存空间的消耗。

HyperLogLog的方法

PFADD 添加一个元素,如果重复,只算作一个

PFCOUNT 返回元素数量的近似值

PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog

注意:PFADD命令不支持key中含有”:”,可以使用”_“进行分割

127.0.0.1:6379> PFADD login:20201005 123456
(error) WRONGTYPE Key is not a valid HyperLogLog string value.
127.0.0.1:6379> PFADD login_20201005 123456
(integer) 1

通过测试工程往HyperLogLog里PFADD了一亿个元素。通过rdb tools工具统计了这个key的信息:

image

只需要14392 Bytes!也就是14KB的空间。对,你没看错。就是14K。bitmap存储一亿需要12M,而HyperLogLog只需要14K的空间。

查了文档,发现HyperLogLog是一种概率性数据结构,在标准误差0.81%的前提下,能够统计2^64个数据。所以 HyperLogLog 适合在比如统计日活月活此类的对精度要不不高的场景。

bitmap与HyperLogLog对比

1、bitmap

优势是:非常均衡的特性,精准统计,可以得到每个统计对象的状态,秒出。

缺点是:当你的统计对象数量十分十分巨大时,可能会占用到一点存储空间,但也可在接受范围内。也可以通过分片,或者压缩的额外手段去解决。

2、HyperLogLog

优势是:可以统计夸张到无法想象的数量,并且占用小的夸张的内存。

缺点是:建立在牺牲准确率的基础上,而且无法得到每个统计对象的状态。

参考资料:


公众号:豆仔gogo

golang、算法、后端知识、面试手册

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory