Reids—神奇的HyperLoglog解决统计问题

一、HyperLogLog 简介

HyperLogLog是最早由 Flajolet 及其同事在 2007 年提出的一种估算基数的近似最优算法。但跟原版论文不同的是，好像很多书包括 Redis 作者都把它称为一种新的数据结构(new datastruct)(算法实现确实需要一种特定的数据结构来实现)。

关于基数统计

基数统计(Cardinality Counting)通常是用来统计一个集合中不重复的元素个数。

思考这样的一个场景：如果你负责开发维护一个大型的网站，有一天老板找产品经理要网站上每个网页的UV(独立访客，每个用户每天只记录一次)，然后让你来开发这个统计模块，你会如何实现？

如果统计PV(浏览量，用户没点一次记录一次)，那非常好办，给每个页面配置一个独立的 Redis 计数器就可以了，把这个计数器的 key 后缀加上当天的日期。这样每来一个请求，就执行 指令一次，最终就可以统计出所有的PV数据了。

但是UV不同，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求了每一个网页请求都需要带上用户的 ID，无论是登录用户还是未登录的用户，都需要一个唯一 ID 来标识。

你也许马上就想到了一个简单的解决方案：那就是为每一个页面设置一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。但这样的问题就是：

存储空间巨大：如果网站访问量一大，你需要用来存储的 set 集合就会非常大，如果页面再一多.. 为了一个去重功能耗费的资源就可以直接让你老板打死你；

统计复杂：这么多 set 集合如果要聚合统计一下，又是一个复杂的事情；

基数统计的常用方法

对于上述这样需要基数统计的事情，通常来说有两种比 set 集合更好的解决方案：

第一种：B 树

B 树最大的优势就是插入和查找效率很高，如果用 B 树存储要统计的数据，可以快速判断新来的数据是否存在，并快速将元素插入 B 树。要计算基础值，只需要计算 B 树的节点个数就行了。

不过将 B 树结构维护到内存中，能够解决统计和计算的问题，但是并没有节省内存。

第二种：bitmap

bitmap可以理解为通过一个 bit 数组来存储特定数据的一种数据结构，每一个 bit 位都能独立包含信息，bit 是数据的最小存储单位，因此能大量节省空间，也可以将整个 bit 数据一次性 load 到内存计算。如果定义一个很大的 bit 数组，基础统计中每一个元素对应到 bit 数组中的一位，例如：

bitmap 还有一个明显的优势是可以轻松合并多个统计结果，只需要对多个结果求异或就可以了，也可以大大减少存储内存。可以简单做一个计算，如果要统计1 亿个数据的基数值，大约需要的内存：，如果用32 bit的 int 代表每一个统计的数据，大约需要内存：

可以看到 bitmap 对于内存的节省显而易见，但仍然不够。统计一个对象的基数值就需要 ，如果统计 1 万个对象，就需要接近 ，对于大数据的场景仍然不适用。

概率算法

实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法，因此在不追求绝对精确的情况下，使用概率算法算是一个不错的解决方案。

概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括:

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 的基数估计误差更小

其中，HyperLogLog的表现是惊人的，上面我们简单计算过用bitmap存储1 个亿统计数据大概需要 内存，而在HyperLoglog中，只需要不到1 K内存就能够做到！在 Redis 中实现的HyperLoglog也只需要12 K内存，在标准误差 0.81%的前提下，能够统计 264个数据！

这是怎么做到的？！下面赶紧来了解一下！

二、HyperLogLog 原理

我们来思考一个抛硬币的游戏：你连续掷 n 次硬币，然后说出其中连续掷为正面的最大次数，我来猜你一共抛了多少次。

这很容易理解吧，例如：你说你这一次最多连续出现了 2 次正面，那么我就可以知道你这一次投掷的次数并不多，所以我可能会猜是 5或者是其他小一些的数字，但如果你说你这一次最多连续出现了 20 次正面，虽然我觉得不可能，但我仍然知道你花了特别多的时间，所以我说 GUN...。

这期间我可能会要求你重复实验，然后我得到了更多的数据之后就会估计得更准。我们来把刚才的游戏换一种说法：

这张图的意思是，我们给定一系列的随机整数，记录下低位连续零位的最大长度 K，即为图中的 ，通过这个 K 值我们就可以估算出随机数的数量 N。

代码实验

我们可以简单编写代码做一个实验，来探究一下 和 之间的关系：

跟上图中的过程是一致的，话说为啥叫 呢，包括 Redis 中的命令也一样带有一个 前缀，还记得嘛，因为HyperLogLog的提出者上文提到过的，叫 。

截取部分输出查看：

会发现 和 的对数之间存在显著的线性相关性：N 约等于 2k

更近一步：分桶平均

如果 介于 2k和 2k+1之间，用这种方式估计的值都等于 2k，这明显是不合理的，所以我们可以使用多个 进行加权估计，就可以得到一个比较准确的值了：

这个过程有点类似于选秀节目里面的打分，一堆专业评委打分，但是有一些评委因为自己特别喜欢所以给高了，一些评委又打低了，所以一般都要屏蔽最高分和最低分，然后再计算平均值，这样的出来的分数就差不多是公平公正的了。

上述代码就有1024个 "评委"，并且在计算平均值的时候，采用了调和平均数，也就是倒数的平均值，它能有效地平滑离群值的影响：

观察脚本的输出，误差率百分比控制在个位数：

真实的 HyperLogLog 要比上面的示例代码更加复杂一些，也更加精确一些。上面这个算法在随机次数很少的情况下会出现除零错误，因为 是不可以求倒数的。

真实的 HyperLogLog

有一个神奇的网站，可以动态地让你观察到 HyperLogLog 的算法到底是怎么执行的：http://content.research.neustar.biz/blog/hll.html

其中的一些概念这里稍微解释一下，您就可以自行去点击 来观察了：

m 表示分桶个数：从图中可以看到，这里分成了 64 个桶；

蓝色的 bit 表示在桶中的位置：例如图中的 实则表示二进制的 ，所以该元素被统计在中间大表格 中标红的第 46 个桶之中；

绿色的 bit 表示第一个 1 出现的位置：从图中可以看到标绿的 bit 中，从右往左数，第一位就是 1，所以在 第 46 个桶中写入 1；

红色 bit 表示绿色 bit 的值的累加：下一个出现在第 46 个桶的元素值会被累加；

为什么要统计 Hash 值中第一个 1 出现的位置？

因为第一个 1 出现的位置可以同我们抛硬币的游戏中第一次抛到正面的抛掷次数对应起来，根据上面掷硬币实验的结论，记录每个数据的第一个出现的位置 ，就可以通过其中最大值 Kmax来推导出数据集合中的基数：N = 2Kmax

PF 的内存占用为什么是 12 KB？

我们上面的算法中使用了1024个桶，网站演示也只有64个桶，不过在 Redis 的 HyperLogLog 实现中，用的是16384个桶，即：214，也就是说，就像上面网站中间那个 大表格有16384格。

而Redis 最大能够统计的数据量是 264，即每个桶的 需要6个 bit 来存储，最大可以表示 ，于是总共占用内存就是：(214) x 6 / 8(每个桶 6 bit，而这么多桶本身要占用 16384 bit，再除以 8 转换成 KB),算出来的结果就是 。

三、Redis 中的 HyperLogLog 实现

从上面我们算是对HyperLogLog的算法和思想有了一定的了解，并且知道了一个HyperLogLog实际占用的空间大约是 ，但 Redis 对于内存的优化非常变态，当计数比较小的时候，大多数桶的计数值都是零，这个时候 Redis 就会适当节约空间，转换成另外一种稀疏存储方式，与之相对的，正常的存储模式叫做密集存储，这种方式会恒定地占用 。

密集型存储结构

密集型的存储结构非常简单，就是16384 个 6 bit 连续串成的字符串位图：

我们都知道，一个字节是由 8 个 bit 组成的，这样 6 bit 排列的结构就会导致，有一些桶会跨越字节边界，我们需要对这一个或者两个字节进行适当的移位拼接才可以得到具体的计数值。

假设桶的编号为 ，这个 6 bity 计数值的起始字节偏移用 表示，它在这个字节的其实比特位置偏移用 表示，于是我们有：

前者是商，后者是余数。比如 的字节偏移是 1，也就是第 2 个字节。它的位偏移是 4，也就是第 2 个字节的第 5 个位开始是 bucket 2 的计数值。需要注意的是字节位序是左边低位右边高位，而通常我们使用的字节都是左边高位右边低位。

这里就涉及到两种情况，如果 小于等于 2，说明这6 bit 在一个字节的内部，可以直接使用下面的表达式得到计数值 ：

如果 大于 2，那么就会涉及到跨越字节边界，我们需要拼接两个字节的位片段：

不过下面 Redis 的源码要晦涩一点，看形式它似乎只考虑了跨越字节边界的情况。这是因为如果 6 bit 在单个字节内，上面代码中的 的值是零，所以这一份代码可以同时照顾单字节和双字节：

稀疏存储结构

稀疏存储适用于很多计数值都是零的情况。下图表示了一般稀疏存储计数值的状态：

当多个连续桶的计数值都是零时，Redis 提供了几种不同的表达形式：

：前缀两个零表示接下来的 6bit 整数值加 1 就是零值计数器的数量，注意这里要加 1 是因为数量如果为零是没有意义的。比如 表示连续 个零值计数器。

：6bit 最多只能表示连续 个零值计数器，这样扩展出的 14bit 可以表示最多连续 个零值计数器。这意味着 HyperLogLog 数据结构中 个桶的初始状态，所有的计数器都是零值，可以直接使用 2 个字节来表示。

：中间 5bit 表示计数值，尾部 2bit 表示连续几个桶。它的意思是连续 个计数值都是 。比如 表示连续 个计数值都是 。

注意上面第三种方式的计数值最大只能表示到 ，而 HyperLogLog 的密集存储单个计数值用 6bit 表示，最大可以表示到 。当稀疏存储的某个计数值需要调整到大于 时，Redis 就会立即转换 HyperLogLog 的存储结构，将稀疏存储转换成密集存储。

对象头

HyperLogLog 除了需要存储 16384 个桶的计数值之外，它还有一些附加的字段需要存储，比如总计数缓存、存储类型。所以它使用了一个额外的对象头来表示：

所以HyperLogLog整体的内部结构就是HLL 对象头加上16384个桶的计数值位图。它在 Redis 的内部结构表现就是一个字符串位图。你可以把HyperLogLog 对象当成普通的字符串来进行处理：

但是不可以使用HyperLogLog指令来操纵普通的字符串，因为它需要检查对象头魔术字符串是否是 "HYLL"。

四、HyperLogLog 的使用

HyperLogLog提供了两个指令 和 ，字面意思就是一个是增加，另一个是获取计数。 和 集合的 的用法是一样的，来一个用户 ID，就将用户 ID 塞进去就是， 和 的用法是一致的，直接获取计数值：

我们可以用 Java 编写一个脚本来试试 HyperLogLog 的准确性到底有多少：

结果输出如下：

发现 万条数据只差了 ，按照百分比误差率是 ，对于巨量的 UV 需求来说，这个误差率真的不算高。

当然，除了上面的 和 之外，还提供了第三个 指令，用于将多个计数值累加在一起形成一个新的 值：