Redis的HyperLogLog

1 基本概念

HyperLogLog 是Redis中的高级数据结构，特点如下：

• 用于对海量数据（可以统计2^64个数据）做基数统计（去重统计数量）；
• 速度快；
• 占空间小（12KB）；
• 基于概率统计，存在误差，标准误差为0.81%；
• 只做统计，不保存输入元素本身。

2 基本指令

HyperLogLog提供了三个基本指令。

2.1 pfadd key element [element …]

将指定元素“添加”到HyperLogLog中，可以“添加”多个元素。

127.0.0.1:6379> pfadd hk 1 2 3
(integer) 1

2.2 pfcount key [key …]

返回key对应的pf的基数估算值。

当一次统计多个pf时，需要对多个pf结构进行比较，并将并集的结果放入一个临时的pf，性能不高，谨慎使用！！！

127.0.0.1:6379> pfcount hk
(integer) 3

2.3 pfmerge destkey sourcekey [sourcekey …]

将多个pf合并，并将结果存入一个指定的pf中。

127.0.0.1:6379> pfadd pf1 1 2 3 4 5
(integer) 1
127.0.0.1:6379> pfadd pf2 1 2 3
(integer) 1
127.0.0.1:6379> pfmerge pf1_pf2 pf1 pf2
OK
127.0.0.1:6379> pfcount pf1_pf2
(integer) 5

合并并去重。

3 几个问题

1. HyperLogLog适合什么场景使用？

适合网站UV访问量统计等大数据量去重统计场景，可以接受有一定的误差。

2. 为什么占用空间是12KB？

HyperLogLog中使用16384（也就是2^14）个桶进行独立计数，每个桶的maxbits需要6个bits来存储，最大可以表述maxbits=63,于是总的占用空间就是 2^14 * 6 / 8 = 12KB。

HyperLogLog并不是一开始就是占用12KB的，在计数比较小的时候，他的存储空间采用稀疏矩阵，空间占用很小。仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值才会一次性转变成稠密矩阵的，才会占用12KB的空间。