概率数据结构：Hyperloglog算法

现在我们想要实时统计有多少用户访问我们的网站，这是一个相当简单的任务，一般的做法是存储用户ID，然后计算任意时刻集合中不同ID的个数即为网站实时访问量，这是一种可行的做法，但是慢慢就会发现随着用户的不断增长，存储集合数据所需要的空间越来越大，所需要的统计成本也越来越高，因此我们需要另外一种算法来解决这个问题，即本次我们要介绍的hyperloglog概率数据结构。

什么是hyperloglog结构

Hyperloglog(HLL)是指从Loglog算法派生的概率算法，用于确定非常大的集合的基数，而不需要存储其所有值。正如我之前所说，常规集或位图可能非常耗费资源。HLL使用固定大小的结构来解决这个问题，根据实际使用情况，它可以低于16kb。作为低资源需求的代价，基数测量是概率性的，意味着具有小于2％的误差。也就是说：

• 假设我们有一个1.000.000个ID的集合
• 2％的错误意味着有可能在计算基数时错过1.000.000个唯一身份用户，为20.000
• 然后，我们可以得到以下两种最坏情况（1.000.000-20.000）= 980.000 || （1.000.000 + 20.000）= 1.020.000

看起来误差有点多，实际中大多数情况下HLL实现的错误率低于1％。而且由于存在错误率，所以使用HLL表示在其应用场景该误差是可以接受的。

HyperLogLog基本原理

HLL的数学原理在这里不作解释，通俗来说HLL是通过散列中左边连续0的数量来估计给定集合的基数，因为一个好的哈希算法可以确保我们每个可能的散列具有大致相同的出现概率和均匀分布。这允许HLL算法基于具有最左边0的流的散列来估计它已经“看到”的元素的量。例如，假设我有一个哈希函数，给定一个元素它返回数字0-15的二进制表示：

其中二进制共有4位，每位出现0的概率是1/2,所以如果连续出现四个0则元素个数至少有16个，那么我如果得到一个左边有k个0元素则至少有2 ^ k个元素。

但是如果集合中只有一个元素，且元素每一位都是0怎么办，这时候就需要采用HLL中的分桶平均法了。分桶平均的基本原理是将统计数据划分为m个桶，每个桶分别统计各自的最大连续0个数并能得到各自的基数预估值 ，最终求其调和平均数即可，举个例子我们将集合划分为8个子集，那么需要将哈希值的前3位用于子集寻址，后几位从左边统计连续0的个数。

Redis中的Hyperloglog

Redis使用16384寄存器实现HLL结构，使标准误差达到0.81％。至于散列函数，Redis使用的散列函数具有64位输出，这意味着它使用前14位来寻址16k寄存器，剩下的50位用于计算左边的0的数量。正如我们之前看到的，每个存储子集将存储最高的0流到该点，最高可能为50（因为散列中只有50个剩余位可以是0），每个存储子集需要6位才能能够存储最多50个（二进制为110010）。因此我们得到98304位来存储1个HLL结构，如果我们将这些位转换为字节，我们得到12288个字节（或12kb） 这就是hyperloglog在Redis实现占用的空间大小。

性能比较

首先我们计算文章开头所提出的方案，如果我们要统计日访问量、周访问量和月访问量，那么使用集合统计ID的方案中，需要56个计数器，其中统计一周7天每天需要5个，一个月4周每周5个，再加上一个统计月访问量，共需56个计数器，每个计数器8GB的话，则需要450GB存储空间才能完成任务。

如果采用第二套方案的话，每个计数器采用HLL结构。由于每个HLL结构在Redis实现中具有12kb的固定大小，我们的56个结构总共使用672kb，小于我们之前的解决方案的内存要求的0.00014％。

虽然HLL方案有一定的误差。但在我们的案例中，1％的错误率是可以接受的，因为我们的结果用于图表可视化，不需要精确数据，只需要代表性数据即可。

总之，Hyperloglog算法使我们能够拥有较小的存储结构，能够以最小的代价完成任务。如果对结果的精确度要求不高，那么HyperLoglog将是一个不错的选择。