1.11111E+14看这里!HyperLogLog原理及Redis实现分析

当特定需求得到满足时，面临的业务场景是重视千万级别的用户id。

Set、hashMap等常用的数据结构都能处理这种情况，但是这些数据结构也面临这样的问题：随着数据量的增多，占用的内存空间会越来越大。

出于对人力成本和内存资源消耗的考虑，最终我们选用了HyperLogLog来完成这一任务。

什么是HyperLogLog？一个(有限)集合里不同的元素个数就称为该集合的基数(cardinality)，HyperLogLog是一种在大数据量下统计基数的算法，标准误差为0.81%。相较于其它算法，HyperLogLog的一个明显优势就是仅需要12KB内存，就可以对大数据量级的数据进行基数统计。

在确定了0.81%的误差可接受之后，我们用pfadd的结果来判断用户id是否为重复id进行去重，预期是将误差控制在官方所说的0.81%左右。但结果却与预期的大相径庭，千万的用户id集合经过这样的去重过程，其中90%以上的id都被误判为重复id。为什么会产生如此大的差异呢？本文将从基数统计算法演进的过程出发，带大家了解HyperLogLog的算法原理，并向大家介绍Redis中HyperLogLog的具体实现，最后将通过一系列的实验去探讨这一问题的成因。

1. 基数统计算法演进

1.1 线性计数算法(Linear Counting)

线性计数算法是由Whang等人在1990年提出的算法，它整体的算法流程是：

下图是原论文中的一个例子，可以看到，使用上述过程，预估到的集合基数为

线性计数算法的流程比较简单，相较于bitmap，它的空间存储方面小有提升，但实际应用所需的空间复杂度仍为。

1.2 对数计数算法(LogLog Counting)

对数计数算法(简称LLC)基本思想是：将集合中所有元素做哈希，生成一个长度固定的比特串，令表示比特串中第一个“1”出现的位置，表示所有元素哈希得到的比特串中的最大值，那么集合总量可近似估计为：

为什么可以采用这种方式估计呢？因为比特串的每个比特都独立且服从0-1分布，那么扫描比特串寻找第一个“1”的过程，从统计学角度就可以认为是一次伯努利过程。类比于抛硬币试验，就可以看作不断抛掷一枚硬币直到得到一个正面的过程。那么进行次伯努利过程，所有投掷次数都不大于的概率为：

至少有一次不小于的概率为：

因此，

所以一旦集合中出现，那么从概率上讲的值即不可能远大于，也不会远小于，因此可作为基数的一个粗略估计。

不过如果直接使用单一的估计量进行基数估计，可能会因偶然性存在较大误差。所以LLC采用了均值法来尽可能地消减误差。基于上述思想，对数计数算法的整体流程如下：

假设hash结果定长 L 为32位。前10位用于桶编号，因此记录每个桶的，仅需要5bit()。能统计到的最大基数个数为，实际占用的内存为。这也就是算法名称中LogLog的由来。

但因为LLC使用的是算术平均数，对于离群值特别敏感，所以当要预估的值不是特别大时，它的误差可能较大。

1.3 超对数计数算法(HyperLogLog Counting)

如前所述，LLC算法使用的是算术平均数，当值较小时，会存在较多空桶，即为0的桶较多。并且因为计算的算术平均数被应用到2的指数上，这些离群值将会更大地干扰基数估计的结果，LLC的偏差就会很大。为了弥补LLC算法存在的这些问题，Flajolet等人提出了一种LLC的改进算法：超对数计数算法(HyperLogLog，后续简称HLL)。HLL中引入了分桶平均的概念，相较于LLC的改进如下：

可以看到，当计算出的基数较小时，HLL就退化成了线性计数算法，当预估的基数值较大时，也对结果做了一定的修正，由此来尽可能降低估算的误差率。

这三种算法的空间复杂度及标准差数据如下：

2. Redis的HyperLogLog实现

Redis定义的HyperLogLog使用了类似sds的结构存储数据，命名为hllhdr，采用了稀疏和密集两种编码处理和存储数据。提供了PFADD、PFCOUNT、PFMERGE三个命令来添加元素、计算基数和合并。它的基本数据结构如下图所示：

其中：

1. magic：占4字节，固定值“HYLL”，用于区别普通string
2. encoding：占1字节，存储registers保存的数据编码格式，取值为HLL_DENSE(0)、HLL_SPARSE(1)、HLL_RAW(255)，其中HLL_RAW只在内部使用。
3. notused：占3字节，全为0，暂未使用。
4. card：占8字节，用于缓存最新计算的近似基数。
5. registers：动态字节数组，用于HLL数据存储，不论编码是稀疏还是密集，散列值的低14位都为分组序号，也就是说Redis使用了16384()个分组。

从上述结构体可以大致看出，Redis实现的HLL结构大致分为两部分：头部信息和存储桶数据的registers。为了减少计算的成本，Redis的HLL实现使用card来保存基数估计的最新计算结果，card字段采用小端存储，用最高有效位来标识card内存储的结果是否还有效。由于Redis的HLL实现使用了16384个分组，基于前文所述的HLL的标准差计算方法，Redis的HLL实现的误差即是

，也就是Redis官方文档中公布的误差率。由于内部编码(HLL_RAW)只是一个临时存储结构，仅在内部MERGE使用或用作具有多个键的PFCOUNT的加速，不对外暴露，所以接下来就仅对HLL的稀疏/密集编码的具体实现形式和命令的执行流程做介绍。

2.1 HLL的稀疏编码

在HLL初始化时，如果仅有少量数据存入，这时候会有大量的空桶。如果这个时候就采用固定位数来存储16384个桶的话，大量的内存空间就被浪费了。因此，Redis使用稀疏编码(HLL_SPARSE)初始化一个新的HLL结构，它是具有压缩性质的编码，将重复的分组计数压缩成操作码(opcode)，以此降低内存使用。那么什么时候会发生编码的转换呢？

当HLL的任一组里的计数值大于32()，或总长度超过3000字节(由HLL_SPARSE_MAX_BYTES决定，可配置)时，发生编码转换。因为不管数据总长度还是计数值只会增加不会减少，所以不会发生由密集编码向稀疏编码的转换。

稀疏编码使用ZERO、XZERO、VAL三种操作码对registers存储的数据进行编码，其中ZERO、VAL占一个字节，XZERO占两个字节：

1. ZERO：操作码为00xxxxxx。6位xxxxxx表示有1到64(111111+1，0没有意义)个连续分组为空。
2. XZERO：操作码由两个字节01xxxxxx yyyyyyyy表示。其中xxxxxx yyyyyyyy表示有1到16384(111111 11111111+1)个连续分组为空， xxxxxx为XZERO的高位，yyyyyyyy为低位。此操作码是初始化一个HLL时使用的默认值，也就是说2个字节就可以表示一个刚创建好的HLL结构的registers。
3. VAL：操作码表示为1vvvvvxx。vvvvv表示投掷次数()，最大32（11111+1），这也是为什么大于32时会发生编码转换的原因；xx表示连续n+1个分组，此操作码可以表示1到32之间的值， 重复1到4次。

上图展示的是稀疏编码的三种操作码及示例，而下图则展示了HLL初始化结构以及插入部分元素后的状态。

2.2 HLL的密集编码

HLL的密集编码(HLL_DENSE)结构是由稀疏编码转换而来的，它的结构相对简单，由连续16384个桶拼接而成，每个组占用6位(16384×6/8，12KB的由来)。不过由于存储采用的是小端模式，所以每个桶的6bit计数值是从LSB(低位) 开始一个接一个地编码到MSB(高位)。具体可见下图：

为了尽可能地节省内存，密集编码的采用的是6bit()存储单个桶，所以存在跨字节存储的情况，这里Redis采用了比较巧妙的方式去定位桶(HLL_DENSE_GET_REGISTER)和设置桶值(HLL_DENSE_SET_REGISTER)。

上图展示的是跨字节情况获取桶值的方法HLL_DENSE_GET_REGISTER，而下面则是HLL_DENSE_SET_REGISTER相关的代码和图示。

2.3 HLL的命令实现

依据前述的HLL的数据结构，结合Redis源码，实际命令的执行过程可以用这些流程图来表述，PFADD命令：

简单来说，PFADD命令首先使用MurmurHash64A计算元素的64位散列值，然后根据散列值定位当前元素对应的桶index和旧桶值oldcount，比较当前值count与旧桶值oldcount。如果count>oldcount，则将card置位无效，返回1；否则返回0。

PFCOUNT命令的简要流程如下：

由于篇幅限制，这里仅介绍统计单个key时的过程，对统计多个key以及PFMERGE流程感兴趣的同学可自行查看Redis源码。

3. 关于HyperLogLog的一些实验

最后来到我们的实验环节，在实验环节主要验证两件事：1. 在大数据量的基数估计场景下，HLL的内存占用是否优于bitmap和hashmap？2. 回到文章最初，使用HLL是否可以保证标准差在0.81%，到底为什么实际使用时和官方提供的标准差相去甚远呢？

3.1 实验一：内存占用实验

下面就来通过实验真实对比一下Bitmap、Hashmap以及HyperLogLog这三种数据结构的内存消耗。同时为了更接近于真实用户id的场景，以一个固定数值为起始，并加上一个random值作为下一次的id值，以查看更真实的内存占用数据。

并分别选择了10、10000、10000000三个范围来进行测试。

最后使用memory usage来查看各个数据结构的内存占用：

整理后的最终实验结果如下：

可以看到，即使在key的数量达到一千万的情况下，HyperLogLog也能保证以12KB的内存去进行基数估计，对内存的消耗是远远小于Bitmap和HashMap的。

3.2 实验二：HLL标准差验证实验

接下来进行标准差相关的实验。选取了人群包的id数据，还原当时需求的使用场景，同时选用一个set来记录真实的id值和校准。最开始进行1000个id的重复性实验：

可以看到，在处理集合前1000个元素时，通过pfadd命令返回结果这种方式判断，HyperLogLog是判定存在21个重复元素，Set是判定无重复元素，那么实际通过pfcount和scard获取到的估计基数是多少呢？

分别是999和1000，这样看来好像有些奇怪，为什么过程中显示重复了21个元素，但是结果却只是判定有1个元素重复呢？先继续我们的实验，最后再一起揭晓我们的答案。

那么随着元素不断地被遍历，我们会发现每遍历1000个元素，HyperLogLog判定的重复元素会越来越多，但实际估计的基数差值与Set获取到的准确结果相差还尚在官方公布的标准差内。

当遍历了一百万左右的元素后，可以看到，每一页处理的过程中甚至能误判990+次重复集合元素，而实际基数估计误差仅在0.53%左右。

回顾上文提到的HyperLogLog的结构和PFADD/PFCOUNT实现机制，我们可以知道，随着集合元素的遍历，每个桶内的值(即count值)会越来越大，Hash处理后的值 会越来越难以使动态字节数组registers发生变更 (这个过程就恰似你在有多个靶子的靶场打靶，每次击中的环数都在0~10环。最开始每一轮的射击后，每个靶子命中的最高环数可能都不断在刷新。但是随着你打了一千轮、一万轮之后，每个靶的最高环数再被刷新的频次会越来越低)。每一次 pfadd返回结果为1的过程，就是动态字节数组registers发生了一次变化，从而基数估计值发生变更的过程 。HyperLogLog估计到的基数值并不是随着元素的遍历而递增，而是根据动态字节数组registers(即所有桶值count)而跳跃计算出的值。

所以根据实验的结果可以看到，并不是HyperLogLog这个数据结构的问题，而是没有去合理地使用它，而导致了集合去重结果的错误。

4. 总结与思考

结合前文所述，我们可以了解到，HyperLogLog是一个仅使用12KB就可以近似计算大数据量级集合基数的算法，它的Redis实现标准误差在0.81%。所以在精度要求不那么高的基数统计业务场景下，HyperLogLog不失为一种不错的选择。

不同的数据结构有不同的适用场景和优缺点，我们需要仔细权衡自己的需求之后，根据实际使用场景去合理地使用它们。希望在这次对HyperLogLog数据结构的探索中，可以帮助大家了解更多基数计数相关算法的思想，也能对Redis各种不同的数据结构使用有更多的思考。

5. 参考文献

• [1]Flajolet P , Éric Fusy, Gandouet O , et al. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm[J]. 2007.
• [2]陈雷 等. Redis 5设计与源码分析[M]. 北京: 机械工业出版社, 2019.
• [3]
• [4]Whang K Y , Vander-Zanden B T , Taylor H M . A linear-time probabilistic counting algorithm for database applications[J]. Acm Trans on Database Systems, 1990, 15(2):208-229.
• [5]Loglog Counting of Large Cardinalities. Springer Berlin Heidelberg, 2003.
• [6]
• [7]
• [8]
• [9]
• 原文 ;mid=2247487471&idx=3&sn=881b55f88e69235a07924f7b8ad06dbc