redis HyperLogLog，看这篇就够了

本文介绍: 考虑这样一个场景，如何统计一个大型网站的去重日活、月活用户（UV）？你可以通过 set 集合、bitmap 这类常用工具，但有个最大的缺点是，如果数据量巨大，比如 1 亿，甚至 10 亿将耗费巨大内存消耗。有人研究出了这样一种算法叫 `Hyp erLogLog`，是一种概率性的统计算法，每个 `HyperLogLog` 对象最大占用空间为 `12KB`，相当节省内存。你应该也猜到了，这么小的内存消耗，是无法记录真实的明细数据，统计数值也不是完全精准，有一定的误差比例。

考虑这样一个场景，如何统计一个大型网站的去重日活、月活用户（UV）？

你可以通过 set 集合、bitmap 这类常用工具，但有个最大的缺点是，如果数据量巨大，比如 1 亿，甚至 10 亿将耗费巨大内存消耗。

有人研究出了这样一种算法叫 HyperLogLog，是一种概率性的统计算法，每个 HyperLogLog 对象最大占用空间为 12KB，相当节省内存。

你应该也猜到了，这么小的内存消耗，是无法记录真实的明细数据，统计数值也不是完全精准，有一定的误差比例。

redis HyperLogLog 主要提供了三个操作：PFADD、PFCOUNT、PFMERGE，分别用于添加、计数与合并。

PFADD 指令。语法：

PFADD key [element [element ...]]

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> PFCOUNT hll
(integer) 7
127.0.0.1:6379>

PFCOUNT 指令。语法：

PFCOUNT key [key ...]

值得注意的是：该操作可能会修改 HyperLogLog，因为最后8个字节编码了用于缓存的最新计算基数，也就是说，PFCOUNT 命令本质来说算一个写操作。

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6
127.0.0.1:6379>

PFMERGE 指令。语法：

PFMERGE destkey sourcekey [sourcekey ...]

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6
127.0.0.1:6379>

抛出一次，正面朝上的概率是 50%，连续抛硬币直到出现正面朝上，记第一次出现正面朝上的位置为 k。

例如，抛一次出现正面的概率为 1/2，抛两次才出现正面的概率为 1/2*1/2，抛出 k 次才第一次出现正面的概率为 1/2^k

这种找出正面朝上的行为可以看作是伯努利过程，连续进行 n 次伯努利过程，可以找到 n 次正面朝上的 k 对应的位置（k1，k2，… kn）

通过概率统计发现，n 与 k 直接存在一定的联系，找出 n 次 k 中的最大值 k_max，存在如下关系： n ≈ 2^k_max

由此，我们可以通过 k_max 记录估算基数 n的大小。

但还存在一个概率偏差较大的问题，我们可以通过进行多轮这样的 n 次实验，然后通过调和平均数（也叫倒数平均数）找到多轮之间的均值作为最终的 k_final，公式如下：

散列计算：通过哈希散列函数，将输入的值散列输出为 64 位 0 和 1 这样的二进制串，结合抛硬币实验，我们可以把 1 看作是正面，0 是反面。

在 redis 中，对于散列函数的 64 位输出，低 14 位（从右）作为分组编号，2^14 = 16384 个分组。剩下 50 位作为基数估计。

剩下的 50 位，从低位到高位（从右至左）找到第一个1 的位置，记为 k，然后与当前分组的记录的 k_current 进行比较，如果大于 k_current 则更新，反之，不做任何处理。

为了降低概率偏差较大的影响，redis 采用分组（多轮）策略，然后每一组都有一个 k_max，并通过相应的计算找出最合适的 k_max 作为基数关联。

前面我们提到，64 位的散列输出只有 50 比特（bit）用来找 k，也就是说 k 出现的位置最大就是 50，因此，我们可以用 6 bit （最大值可达 63）就可以存储。

总共有 16384 分组，也就是说有 16384 个 6 bit，即 12 KB。

使用 12 KB 可以统计 2^64 个元素个数，只要在这个数量范围内，不管数量多少，都只占用 12 KB 的内存空间。

你应该也猜到了 redis 的套路，在其内部一般会采用不同的编码方式，目的就是节省内存空间，具体是这样的：

red i s 使用稀疏和密集两种编码处理与存储数据，默认情况下，red i s 创建的 HyperLogLog 对象使用稀疏编码，当稀疏编码长度超过一定值或者 k_max 超过一定值时发生编码转换。

HyperLogLog 简称 HLL，没有采用新的数据结构，其底层仍然采用 sds 的结构存储数据（字符串位图）。

因此，为了区别普通字符串，在 HLL 头部使用了固定的字符串（'HYLL'）。

而为了更好地管理 HLL 数据，redis 使用了一个 hllhdr（HLL头对象，HLL header）结构体来存储 HLL 数据的字段信息。

稀疏编码和密集编码都采用 16字节 的固定头部，如下：

 +------+---+-----+----------+
 | HYLL | E | N/U | Cardin.  |
 +------+---+-----+----------+

继续看看对应的 hllhdr 底层数据结构：

struct hllhdr {
    char magic[4];      
    uint8_t encoding;   
    uint8_t notused[3]; 
    uint8_t card[8];    
    uint8_t registers[];
};

大致是这样：redis 的 HLL 存储分为两部分：hllhdr 头部和 registers 数据：

对于稀疏与密集编码的主要区别，可以简单理解为空分组较多时使用稀疏编码存储，空分组较少时使用密集编码存储，内部计算使用 HLL_RAW 编码。

为了减少计算成本，redis 使用 card 来保存基数计数最新的计算结果（缓存），card 最高位用来标识剩下的 63 位数据是否有效（1 无效，0 有效），如果数据被更改，那么 card 缓存的值将失效。

值得注意的是，对于 VAL 操作码，因为分组值只有 5 bit，我们在找 k_max 的时候不能查超过 32，一旦超过内部就会自动转换成密集编码。

对于一个空的 HLL，压缩后是这样：XZERO:16384，也就是说用 2 字节就表示了 16384 个分组，实际编码是 01111111 111111，再加上 16 字节的固定头部，总共占用 18 字节。

在这个例子中，仅用了 7 字节，可见，比 12 KB 的密集编码要节省很多内存。

100 267
200 485
300 678
400 859
500 1033
600 1205
700 1375
800 1544
900 1713
1000 1882
2000 3480
3000 4879
4000 6089
5000 7138
6000 8042
7000 8823
8000 9500
9000 10088
10000 10591