Hyperloglog算法

在Redis中有一种叫作Hyperloglog的数据结构，用于基数统计，其背后原理就是Hyperloglog算法，本文介绍下HyperLogLog算法的原理和具体实现方式。主要包括LLC算法原理及实现，HLLC算法原理及实现，Redis中HeperLogLog的具体实现。

基数统计概述

基数统计通常用来统计一个集合中不重复元素的个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量等等。当数据量比较少的时候，我们用一个set或者性能更高的bitmap就能轻松解决。但是当数据量非常大，比如上亿级别，这时用set就不切实际了。

实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法，因此在不追求绝对准确的情况下，使用概率算法算是一个不错的解决方案。概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括:

• Linear Counting(LC)：早期的基数估计算法，LC在空间复杂度方面并不算优秀，实际上LC的空间复杂度与简单bitmap方法是一样的（但是有个常数项级别的降低），都是O(Nmax)；
• LogLog Counting(LLC)：LogLog Counting相比于LC更加节省内存，空间复杂度只有O(log2(log2(Nmax)))
• HyperLogLog Counting(HLL)：HyperLogLog Counting是基于LLC的优化和改进，在同样空间复杂度情况下，能够比LLC的基数估计误差更小。

本文重点介绍后两种算法，即LLC和HLL。

LLC

算法思想

LLC算法的思想其实来源于伯努利实验，下面我们以抛硬币实验为例，简单介绍下伯努利。

硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。

那么对于多次的伯努利试验，假设这个多次为n次。就意味着出现了n次的正面。假设每次伯努利试验所经历了的抛掷次数为k。第一次伯努利试验，次数设为$k_1$，以此类推，第n次对应的是$k_n$。

其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数k，例如抛了12次才出现正面，那么称这个为$k_{max}$，代表抛了最多的次数。

伯努利试验容易得出有以下结论：

1. n 次伯努利过程的投掷次数都不大于 $k_{max}$。
2. n 次伯努利过程，至少有一次投掷次数等于 $k_{max}$。

最终结合极大似然估算的方法，发现在$n$和$k_{max}$中存在估算关联：$n = 2^{k_{max}}$ 。这种通过局部信息预估整体数据流特性的方法似乎有些超出我们的基本认知，需要用概率和统计的方法才能推导和验证这种关联关系。

例如下面的样子：

1
2
3
4

第一次试验: 抛了3次才出现正面，此时 k=3，n=1
第二次试验: 抛了2次才出现正面，此时 k=2，n=2
第三次试验: 抛了6次才出现正面，此时 k=6，n=3
第n 次试验：抛了12次才出现正面，此时我们估算， n = 2^12

假设上面例子中实验组数共3组，那么 k_max = 6，最终 n=3，我们放进估算公式中去，明显： 3 ≠ 2^6 。也即是说，当试验次数很小的时候，这种估算方法的误差是很大的。

下面我们尝试从数学角度，来解释：为什么可以用$2^{k_{max}}$来估算实验次数n。

现在考虑下面两个问题：

1. 进行n次伯努利实验，所有投掷次数都不大于k的概率是多少？
2. 进行n次伯努利实验，至少有一次投掷次数等于k的概率是多少？

首先看第一个问题，在一次伯努利实验中，投掷次数大于k的概率是$1/2^k$，即前k次都投出了反面。因此，问题1的答案是$P_n(X\leq k) = (1-1/2^k)^n$。那么第二个问题的答案显然是，$P_n(X\geq k) = 1-(1-1/2^k)^n$。

从上述分析，我们可以得出这样的结论：当$n << 2^k$时，$P_n(X\geq k)$的概率几乎为0，同时，当$n >> 2^k$时，$P_n(X\leq k)$的概率也几乎为0。

用自然语言描述就是：当实验次数远远小于$2^k$时，至少有一次实验投掷次数等于k的概率几乎为0；当实验次数远远大于$2^k$时，没有一次实验投掷次数大于k的概率也几乎为0。

如果将上面描述作一个对应：一次伯努利实验对应一个比特串，反面对应0，正面对应1，投掷次数k对应第一个“1”出现的位置，我们就得出如下结论：

假设一个集合基数为n，$k_{max}$为所有比特串中，首个“1”出现位置最大的位置，如果n远远小于$2^{k_{max}}$，那么我们得到$k_{max}$为当前只的概率几乎为0，同样的，如果n远远大于$2^{k_{max}}$，则我们得到$k_{max}$的概率也几乎为0，因此$2^{k_{max}}$可以作为基数n的一个粗糙估计。

总结来说就是： 进行n次抛硬币实验，每次分别记录第一次抛出正面的次数k，假设n个k中最大值为$k_{max}$，那么我们可以用$2^{k_{max}}$来估计实验次数n。

回到基数统计的问题，我们需要统计一组数据中不重复元素的个数，

集合中每个元素的经过hash函数后可以表示成0和1构成的二进制数串，一个二进制串可以类比为一次抛硬币实验，1是抛到正面，0是反面。

二进制串中从低位开始第一个1出现的位置可以理解为抛硬币试验中第一次出现正面的抛掷次数k，

那么基于上面的结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，

同样可以可以通过第一个1出现位置的最大值$k_{max}$来预估总共有多少个不同的数字（整体基数）。

具体实现

LogLogCounting算法伪代码如上图所示，主要包含哈希和分桶两部分。

哈希

在使用LLC之前，需要选取一个合适的哈希函数，将所有元素映射成一个二进制串。哈希函数需要满足一下性质：

1. 均匀分布
2. 哈希碰撞可以忽略不计
3. 哈希结果长度固定

分桶

基于前文的分析，如果使用单一估计量进行基数估计会由于偶然性而存在较大误差。因此，LLC采用了分桶平均的思想来消除误差。

具体来说，就是把哈希空间平均分成m份，每份称之为一个桶。对于每个元素，根据其哈希值的前k比特作为桶编号，其余比特作为基数估计的比特串。

桶编号相同的元素被分配到同一个桶，在进行基数估计时，首先计算每个桶内元素最大的第一个“1”的位置，设为$M[i]$，然后对这m个值取平均后再进行估计，即： $\hat n=2^{1/m}\sum M[i]$。

这其实相当于我们熟知的多次试验取平均的做法，可以有效消减因偶然性带来的误差。

设一个元素哈希值的比特串为“0001001010001010”，由于m为32，因此前5个bit为桶编号，所以这个元素应该归入“00010”即2号桶（桶编号从0开始，最大编号为m-1）

而剩下部分是“01010001010”且显然k(01010001010)=2，所以桶编号为“00010”的元素最大的k即为M[2]的值。

偏差修正

上述经过分桶平均后的估计量看似已经很不错了，不过通过数学分析可以知道这并不是基数n的无偏估计。因此需要修正成无偏估计。这部分的具体数学分析在“Loglog Counting of Large Cardinalities”中，过程过于艰涩这里不再具体详述，有兴趣的朋友可以参考原论文。

通过数学推导，可以得到如下的渐进五篇估计量：

$\begin{aligned} \hat{n}&=\alpha_{m} 2^{1 / m} \sum M[i]\\ \alpha_{m}&=\left(\Gamma(-1 / m) \frac{1-2^{1 / m}}{\log 2}\right)-m \\ \Gamma(s)&=\frac{1}{s} \int_{0}^{\infty} e^{-t} t^{s} d t \end{aligned}$

该估计量的偏差为：$\operatorname{Std} \operatorname{Error}(\hat{n} / n) \approx \frac{1.30}{\sqrt{m}}$。

因此在实际应用中，如果我们想将误差控制在$\epsilon$内，那么$m>(1.30/\epsilon)^2$。

内存使用分析

内存使用与m的大小及哈希值长度有关，假设哈希值长度为32，由于$k_{max} \leq 32$，因此每个桶需要5bit空间来存储这个桶的$k_{max}$，m个桶就需要$5\times m/8$个字节。

举个例子，加入基数上限为一亿（约$2^{27}$），当分桶数m=1024时，每个桶的基数上限约为$2^{17}$，而$log_2(log_2(2^{17}))=4.09$，因此每个桶需要5bit存储$k_{max}$，需要的字节数就是$5\times 1024/8=640$，误差为$1.30/\sqrt {1024}=0.040625$，约等于4%。

HLLC

HLLC是对LLC的一种改进。

HLLC的第一个改进是使用调和平均数替代几何平均数。注意LLC是对各个桶取算数平均数，而算数平均数最终被应用到2的指数上，所以总体来看LLC取得是几何平均数。由于几何平均数对于离群值（例如这里的0）特别敏感，因此当存在离群值时，LLC的偏差就会很大，这也从另一个角度解释了为什么n不太大时LLC的效果不太好。这是因为n较小时，可能存在较多空桶，而这些特殊的离群值强烈干扰了几何平均数的稳定性。

因此，HLLC使用调和平均数来代替几何平均数，调和平均数的定义如下：

$H=\frac{n}{\frac{1}{x_{1}}+\frac{1}{x_{2}}+\ldots+\frac{1}{x_{n}}}=\frac{n}{\sum_{i=1}^{n} \frac{1}{x_{i}}}$

调和平均数可以有效抵抗离群值的扰动。使用调和平均数代替几何平均数后，估计公式变为如下：

$\begin{aligned} \hat{n}&=\frac{\alpha_{m} m^{2}}{\sum 2^{-M}}\\ \alpha_{m}&=\left(m \int_{0}^{\infty}\left(\log _{2}\left(\frac{2+u}{1+u}\right)\right)^{m} d u\right)^{-1} \end{aligned}$

该估计的误差期望为：$S_{\text {hllc }}(\hat{n} / n)=1.04 / \sqrt{m}$。

因此在存储空间相同的情况下，HLLC比LLC具有更高的精度。例如，对于分桶数m为2^13（8k字节）时，LLC的标准误差为1.4%，而HLLC为1.1%。

Redis中的HyperLogLog

在 Redis 中，HyperLogLog 是它的一种高级数据结构。提供有包含但不限于下面两条命令：

• pfadd key value，将 key 对应的一个 value 存入
• pfcount key，统计 key 的 value 有多少个

在Redis中，设有 16384 个桶，即：2^14 = 16384，每个桶有 6 位，每个桶可以表达的最大数字是：2^5+2^4+…+1 = 63 ，二进制为： 111 111 。因为每个value（哈希值）为64位，去掉前14位，还剩50，因此$k_{max}$最大为50，用每个桶用6bit空间足够表示50了。

因此，Redis中一个HyperLogLog，只需要(6 * 16384)/8/1024 K=12K的空间，就能统计最多$2^{64}$个数，统计误差大约为$1.04/\sqrt{16384}=0.008125$。

参考资料

1. https://juejin.cn/post/6844903785744056333
2. https://zhuanlan.zhihu.com/p/77289303
3. http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf