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

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

方案一：使用string（排除）

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

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

方案二：bitmap

1、bitmap介绍

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

主要命令有：

SETBIT

GETBIT

BITCOUNT

BITPOS

BITOP

BITFIELD

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

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的信息：

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

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

bitmap与HyperLogLog对比

1、bitmap

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

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

2、HyperLogLog

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

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

参考资料：

Redis如何存储和计算一亿用户的活跃度

豆仔gogo

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