一般来说，我喜欢随机化算法，但其中有一个我特别喜欢——即使你已经明白了它的工作原理，从程序员的角度看，它依然充满魔力。它以极少的时间和空间代价，完成了一件近乎不可思议的事情。这个算法叫做 HyperLogLog，今天它作为一种新的数据结构被引入到了 Redis 中。

统计不重复元素的数量
===

通常，统计不重复元素的数量——例如今天访问你网站的不重复 IP 的数量，或用户执行的不重复搜索的次数——需要记住迄今为止遇到的所有不重复元素，以便将下一个元素与已见集合进行比较，只有当新元素从未出现过时才递增计数器。

这需要的内存与我们正在统计的集合的基数（元素数量）成正比，而这往往是完全不可接受的。

有一类算法利用随机化，仅用恒定且很小的内存，就能对集合中不重复元素的数量给出近似估计。目前已知的这类算法中最优秀的就是 HyperLogLog，它由 Philippe Flajolet 提出。

HyperLogLog 的出色之处在于，即使只使用极小的内存，也能对集合的基数给出非常好的近似。在 Redis 的实现中，每个键仅使用 12KB 就能以 0.81% 的标准误差进行计数，而且对可计数的元素数量没有限制，除非接近 2^64 个元素（这似乎不太可能）。

该算法在原始论文 [1] 中有详细论述，其实际实现和变体则在 Google 于 2013 年发表的一篇论文 [2] 中得到了深入探讨。

[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf

它是如何工作的？
===

关于 HyperLogLog，有很多优秀的资料可以进一步学习，比如 [3]。

[3] http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

这里我只借助在 [3] 中看到的一个非常巧妙的例子来讲讲基本思路。想象一下，你告诉我你花了一整天抛硬币，并统计连续出现正面的最长长度。如果你告诉我最长的一次是连续 3 个正面，我会猜你其实没抛多少次。如果最长的一次是 13 个正面，你大概抛了很久。

然而，如果你运气好，第一次就抛出了 10 个连续正面——这虽然不太可能，但确实可能发生——然后就停止抛硬币，那么我对你抛硬币次数的估计就会大错特错。于是我可能会让你重复这个实验，但这次用 10 枚硬币和 10 张纸，每枚硬币对应一张纸，用来记录各自最长的连续正面次数。这一次由于我能观察到更多数据，我的估计就会更准确。

长话短说，这正是 HyperLogLog 所做的：它对每一个新观察到的元素进行哈希。哈希值的一部分用来索引一个寄存器（相当于前面例子中的一枚硬币加一张纸。本质上我们是把原集合拆成了 m 个子集）。哈希值的另一部分则用来计算哈希值开头连续零的最长长度（相当于我们的连续正面）。出现 N+1 个零的概率是出现 N 个零概率的一半，因此通过观察不同寄存器的值——每个寄存器都记录了对应子集中迄今为止观察到的最长零序列——HyperLogLog 就能给出非常好的基数近似估计。

Redis 中的实现
===

HyperLogLog 的标准误差是 1.04/sqrt(m)，其中“m”是寄存器的数量。
Redis 使用了 16384 个寄存器，因此标准误差为 0.81%。

由于 Redis 实现中使用的哈希函数输出为 64 位，而我们用其中 14 位来寻址 16k 个寄存器，剩下 50 位，因此我们能遇到的最长零序列可以用一个 6 位的寄存器来存储。这就是为什么 Redis 中一个 HyperLogLog 值仅用 12k 字节就能容纳 16k 个寄存器。

由于使用了 64 位输出的哈希函数——这是 Google 在 [2] 中提出的算法改进之一——我们对可计数的集合基数实际上没有限制。此外值得注意的是，对于很小的基数，误差往往也非常小。下图展示了该算法在两个不同的大型集合上的运行情况。横轴表示集合的基数，纵轴表示相对误差（百分比）。



红色和绿色的线条是两个完全不相关的集合上的两次不同运行。可以看到，随着基数的增长，误差保持稳定。不过对于小得多的基数，误差会更小：



绿线显示了基数到 100 时单次运行的误差，而红线是在 100 次运行中找到的最大误差。在基数只有几百以内时，算法很可能产生非常小的误差，甚至给出精确答案。当计算结果需要展示给能够直观判断答案是否正确的用户时，这一点非常有价值。

Redis 实现的源代码可在 Github 上获取：

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c

API
===

在 Redis 看来，一个 HyperLogLog 就是一个字符串，恰好长 12k + 8 字节（精确地说是 12296 字节）。所有 HyperLogLog 命令在传入恰好为此大小的字符串值时都能正常执行，否则会报错。不过无论字符串中存储的是什么，所有的调用都是安全的：即使你存入的是垃圾数据，依然可以请求基数的估计值。在任何情况下这都不会导致服务器崩溃。

此外，整个表示都是大小端无关的，也不受处理器字长的影响，因此 32 位大端处理器可以读取 64 位小端处理器生成的 HLL。

HyperLogLog 以字符串形式存储，避免了在 RDB 层面引入真正的类型。这使得该功能可以在未来几天内被反向移植到 Redis 2.8 中，让你尽快就能用上 HyperLogLog。此外，该格式会自动序列化，可以轻松地获取和恢复。

API 由三个新命令组成：

PFADD var element element … element
PFCOUNT var
PFMERGE dst src src src … src

命令前缀“PF”是为了致敬 Philippe Flajolet [4]。

[4] http://en.wikipedia.org/wiki/Philippe_Flajolet

PFADD 向存储在“var”中的 HLL 添加元素。如果该变量不存在，会像 Redis API 调用一贯的那样自动创建一个空的 HLL。该命令是可变参数的，因此可以进行非常高效的流水线和批量插入。

如果底层的 HyperLogLog 被修改，该命令返回 1，否则返回 0。这对用户很有意义，因为随着元素的不断添加，某个元素实际修改某个寄存器的概率会越来越低。API 能够提示是否存在新的基数，使得那些持续添加元素、仅在有新基数可用时才获取近似基数的程序成为可能。

PFCOUNT 返回估计的基数，如果键不存在则为零。

最后，PFMERGE 可以将 N 个不同的 HLL 值合并为一个。合并后的 HLL 报告的估计基数，即为用不同 HLL 值计数的各个集合的并集的基数。这看起来很神奇，但之所以可行，是因为 HLL 虽然是随机化的，却是完全确定性的，因此 PFMERGE 只需对每个寄存器取 N 个 HLL 值中的最大值即可。一个给定的元素总是会哈希到同一个寄存器并产生相同的零序列长度，因此以这种方式进行的合并只会累加那些在不同 HLL 中不共有的元素的计数。

如你所见，HyperLogLog 是完全可并行化的，因为可以将一个集合拆分为 N 个子集分别独立计数，之后再合并结果以获得总基数的近似值。Redis 中的 HLL 本身就是字符串，这也有助于在不同实例之间迁移 HLL 值。

先保证正确，再追求速度
===

Redis 的 HLL 由 16k 个打包在 6 位整数中的寄存器组成。这带来了一些必须解决的性能问题，才能提供一套无需过多顾虑即可调用的命令 API。

一个问题是，访问寄存器需要访问多个字节，并进行位移和掩码操作才能取出正确的 6 位值。对于每次只触及一个寄存器的 PFADD 来说这不是大问题，但 PFCOUNT 需要使用全部 16k 个寄存器进行计算，因此如果访问每个寄存器都有不可忽略的常量开销，该命令就有可能变慢。此外，在访问寄存器的同时，我们还需要计算 pow(2,-register) 的总和，这涉及浮点运算。

有人可能会想直接用完整的字节来代替 6 位整数以加速计算，但这未免可惜，因为每个 HLL 将占用 16k 而不是 12k，差别并不小，因此这一方案一开始就被否决了。通过以下改动，该命令相比最初的实现获得了约 3 倍的加速：

* 对于 m=16k（这是 Redis 的默认值，实现本身更通用，理论上可以使用不同的值），实现选择了一条快速路径，通过展开循环每次访问 16 个寄存器。寄存器通过固定的偏移/位移/掩码来访问（通过一个每次递增 12 字节的指针）。
* 修改了浮点计算，使其在可能的情况下允许多个操作并行执行。这只是加括号的问题。浮点运算不满足交换律，但在这种情况下并没有损失精度。
* 将 pow(2,-register) 项预先计算在一张查找表中。

通过上述改动的 3 倍加速，该命令在较快的硬件上能够达到每秒约 60k 次调用。然而，这仍然远不及从用户角度看概念上类似的 SCARD 等命令所能达到的每秒数十万次。

与其进一步优化近似基数的计算，还有一个更简单的解决方案。基本上，只有当某个寄存器发生变化时，算法的输出才会改变。然而如上所述，大多数 PFADD 调用并不会导致任何寄存器改变。这基本上意味着可以缓存上一次的输出，仅在某个寄存器发生变化时才重新计算。

因此，我们的数据结构在末尾额外增加了 8 个字节，表示一个小端格式的 64 位无符号整数。如果最高位被置位，则表示预计算的值已过期需要重新计算，否则 PFCOUNT 可以直接使用它。PFADD 只需在某个寄存器被修改时打开“缓存失效”位。

经过这一改动，即使以最高速度通过 32 个元素的流水线配合 50 个并发客户端不断添加元素，PFCOUNT 也能像其他任何 O(1) 命令一样，以非常小的常量时间高效执行。

使用多项式回归进行偏差校正
===

HLL 算法要想实用，就必须在任何基数范围内都能同样良好地工作。不幸的是，算法给出的原始估计对于小于 m*2.5（当 m=16384 时约为 40000 个元素）的基数来说并不理想，因为在这个范围内，算法的输出会产生偏差，甚至根据具体区间的不同出现较大误差。

原始的 HLL 论文 [1] 建议，当 HLL 算法第一部分估计的原始基数小于 m*2.5 时，切换到 Linear Counting [5]。

[5] http://dblab.kaist.ac.kr/Publication/pdf/ACM90_TODS_v15n2.pdf

Linear counting 是一种不同的基数估计器，其概念很简单。我们有一个 N 位的位图。每当需要计数一个新元素时，就对其进行哈希，并用哈希值随机索引位图中的一位，将其置为 1。位图中未置位比特的数量可以让我们通过以下公式大致了解迄今为止添加了多少元素：

    cardinality = m*log(m/ez);

其中‘ez’是零位的数量，m 是位图中的总位数。

与 HyperLogLog 相比，Linear counting 在大基数下表现不佳，但在小基数下表现很好。由于 HLL 的寄存器在副作用上也可以充当 Linear counting 的位图，通过统计零寄存器的数量，就可以在 HLL 表现不佳的区间应用 Linear counting。注意，这之所以可行，是因为在更新寄存器时，我们实际使用的不是最长零序列本身，而是最长零序列加一。这意味着如果添加的元素寻址到了一个从未被寻址过的寄存器，该寄存器会从 0 变为另一个值（至少为 1）。

Linear counting 的问题在于，随着基数变大，其输出误差也会变大，因此我们需要尽快切换回 HLL。然而当我们在 2.5m 处切换时，HLL 仍然存在偏差。下图中，同一基数用 1000 个不同的集合进行了测试，每次运行的误差都显示为一个点：



蓝线是误差的平均值。如你所见，在基数为 40k 之前使用 Linear counting 时，越往大基数的方向，点的“光束”就越宽（误差越大）。当切换到 HLL 原始估计时，误差变小了，但存在偏差：算法在 40k-80k 范围内会高估基数。

Google 的工程师们对此问题进行了广泛研究 [2] 以校正偏差。他们的解决方案是创建一张基数值与对应偏差的经验表。他们修改后的算法使用该表和插值来获取给定范围内的偏差，并据此进行校正。

我采用了不同的方法：可以看到偏差并非随机的，而看起来像一条非常平滑的曲线，因此我计算了一些基数-偏差样本，并执行多项式回归以找到一条近似该曲线的多项式。

目前我在 40960-72000 范围内使用一个四阶多项式进行校正，以下是偏差校正后的结果：



虽然在两种算法的切换点仍存在一些偏差，但与原始的 HLL 算法相比，结果已经相当令人满意，不过很可能还可以找到一条更贴合偏差曲线的曲线来进一步改进。我暂时没有时间进一步研究。

值得一提的是，在我的研究过程中我发现，至少对于 m=16384，在不使用偏差校正的情况下，从 Linear counting 切换到 HLL 原始估计的最佳值实际上接近 3，而不是 [1] 中提到的 2.5，因为取 3 既能改善偏差也能改善误差。大于 3 的值会改善偏差（取 4 则能完全校正偏差），但会对误差产生不利影响。

原始的 HLL 算法还会对接近 2^32 的值进行校正 [1][2]，因为一旦接近很大的值，哈希函数的碰撞就开始成为问题。我们不需要这种校正，因为我们使用的是 64 位哈希函数和 6 位计数器，这是 Google 工程师提出的修改之一 [2]，并已被 Redis 的实现所采用。

未来的工作
===

直观上看，当使用 Linear counting 时，似乎有可能通过利用我们拥有的额外信息来改进算法输出的误差。在标准的 Linear counting 算法中，寄存器只有 1 位宽，因此我们只有两种信息：迄今为止是否有元素哈希到这一位。但最初提出的 HLL 算法 [1] 以及 Google 修改后的版本 [2]，在回退到 Linear counting 时仍然只将零寄存器的数量作为算法的输入。有可能利用寄存器中存储的信息也能改进输出。

例如，在标准的 Linear counting 中，假设我们有 10 位，我可能添加了 5 个元素，而它们恰好都寻址到同一位。这是一种特殊情况，算法无法纠正，提供的估计值很可能会小于实际基数。然而在 HLL 所使用的 Linear counting 算法中，在类似情况下，我们可能会发现唯一被置位的那个寄存器的值暗示了有多个元素在那里发生了碰撞，从而可以对输出进行校正。

结语
===

HyperLogLog 是一种令人惊叹的数据结构。我希望 Redis 的实现——将在几天内随稳定版发布（Redis 2.8.9 将包含它）——能以开箱即用的形式将这一工具带给众多程序员。

HN 上的帖子在这里： https://news.ycombinator.com/item?id=7506774