redis HyperLogLog，看这篇就够了

---

前言

本文参考源码版本为 redis6.2

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

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

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

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

---

一、动手试试？

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

1. 添加

PFADD 指令。语法：

PFADD key [element [element ...]]

可用版本：>= 2.8.9
时间复杂度：O(1) 的复杂度添加一个元素

关于返回值：

• 返回 1：如果命令执行后 HyperLogLog 对象有所更新
• 返回 0：命令执行后，HyperLogLog 没有任何变化

来看看效果：

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> 

2. 统计

PFCOUNT 指令。语法：

PFCOUNT key [key ...]

可用版本: >= 2.8.9
时间复杂度：针对一个 key 是 O(1) 常量时间，如果是 N 个 key 就是 O(N)

返回值：

• 单个 key：正常是 HyperLogLog 对象存储的基数统计结果，如果 key 不存在则返回 0。
• 多个 key：则是返回多个 key 对应的 HyperLogLog 合并结果。内部处理时，会先创建一个临时的 HyperLogLog 对象，然后将 keys 对应的 HyperLogLog 对象全部合并过去。

值得注意的是：该操作可能会修改 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> 

关于性能：

• 单 key：这种性能最好，由于计算结果会缓存起来，只要 HyperLogLog 对象没有变化，后续请求直接从缓存中获取结果。
• 多 key：这样性能要差的多，由于多 key 对应的 HyperLogLog 对象需要做合并操作，因此是没法缓存计算结果。

所以，在使用的时候我们应该清楚，该命令的单 key 和多 key 执行在语义上是不同的，具有不同的性能。

3. 合并

PFMERGE 指令。语法：

PFMERGE destkey sourcekey [sourcekey ...]

可用版本: >= 2.8.9
时间复杂度：合并 N 个 HyperLogLog 对象，时间复杂度是 O(N)，通常会有更高的时间消耗

来看看效果：

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> 

二、原理

1. 伯努利过程

抛出一次，正面朝上的概率是 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，公式如下：

调和平均数结果偏向几个值中较小值，可以避免较大值的影响，这样一来，偏差便会小很多。

2. HyperLogLog

Log 表示对数，HyperLogLog 意思是超对数计算，是 LogLog 算法的改进版，有兴趣可以自行了解下。

以下是两个大基数集合的 HyperLogLog 估算偏差，横轴是数据量，纵轴是误差率（图来自 Antirez 博客）：

2.1 工作原理

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

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

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

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

2.2 占用内存大小

12KB 的由来？

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

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

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

2.3 内存优化？

如果每个 key 都占用 12 KB 的空间，对于那些远小于 12 KB 的 key 来说，是不是太浪费了？

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

• 稀疏编码：主要应对数据量小的场景
• 密集编码：应对数据量大的场景

不管是 稀疏编码 还是 密集编码，都采用 16384 个分组，如果每个分组采用 6个 bit，需要 12 KB 的空间，这正是密集编码的方案。

对于稀疏编码来说，如果每个分组也采用 6bit 就有点奢侈了，因为，很多分组都可能没有数据，各分组将白白浪费 6bit 的空间。

具体区别我们继续往下看～

3. 数据编码

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

固定头部？

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

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

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

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

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

• HYLL：即固定魔法字符串 HYLL
• E 使用一个字节，表示编码
• N/U 是三个未使用的字节
• Cardin：缓存基数，缓存的是最近一次计算的基数，只要 HLL 没被修改过，就可以一直重复使用

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

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

• magic：4字节，填充固定字符串：HYLL
• encoding：1字节，填充 0 或 1，0 表示密集编码，1 表示稀疏编码
• notused：3字节，目前未使用，为将来使用保留
• card：8字节，缓存最近一次计算的基数
• registers：动态字节数组，用于 HLL 数据存储，不论编码是稀疏还是密集。散列值的低 14 位为分组序号，也就是说 redis 使用了 16384 个分组

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

• registers 用来存储组数据。
• hllhdr 为 HLL 的头部信息，其中 encoding 来标识使用的编码。

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

缓存？

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

3.1 稀疏编码

稀疏编码的主要目的是想将多个连续空分组、多个连续相同值分组的进行压缩，具体压缩方式提供了三种操作码：

• ZERO：1 字节，形如 00xxxxxx，其中 00 是操作码的值，xxxxxx 6 bit 代表的整数表示有多少个连续分组被设置为 0。
• XZERO：2 字节，形如 01xxxxxx yyyyyyyy，其中 00 是操作码的值，剩下 14 bit 代表的整数表示有多少个连续分组被设置为 0。
• VAL：1 字节，形如 1vvvvvxx，其中 1 是操作码的值，vvvvv 5 bit 表示分组的值，xx 表示有多少个连续分组被设置为 vvvvv。

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

例子：

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

再比如，我们有一个 HLL 只有三个非 0 分组，对应分组位置分别是 1000、1020、1021，对应的分组值分别是 2、3、3，我们来看看操作码组成：

• XZERO:1000：表示分组 0 - 999 都被设置成 0。
• VAL:2,1：一个分组被设置成 2，对应的分组编号是 1000
• ZERO:19：分组 1001-1019 被设置成 0
• VAL:3,2：两个分组被设置成 3，对应的分组编号是 1020、1021
• XZERO:15362：分组 1022-16383 被设置成 0

在这个例子中，仅用了 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

可以看到，随着基数的增加，稀疏编码占用的内存也在增加。

3.2 密集编码

密集编码相对来说就比较简单了，每个 key 占用固定的 12 KB 大小，其中有 16384（2^14） 个分组，每个分组占 6bit。

3.3 转码

默认情况下，当我们创建一个 HLL 结构时，使用稀疏编码：

• 一是因为刚开始基数记录较少，可能出现较多空分组，这个时候可以压缩
• 另外，由于基数少，出现 k_max 超过 32 的概率较小，稀疏编码完全能够容纳。

随着基数的增多，稀疏编码的优势将慢慢失去，当达到以下任一阈值条件时，稀疏编码将转换为密集编码：

• 当稀疏编码存储的任意一个组里的计数值大于 32（k_max）
• 总长度超过 3000 字节（可通过参数 hll-sparse-max-bytes 配置）

相关参考：

• Redis new data structure: the HyperLogLog
• hyperloglogs # docs
• HyperLogLog 算法的原理讲解以及 Redis 是如何应用它的
• <<Redis 5设计与源码分析>>

这篇好文章是转载于：学新通技术网