一般来说，我喜欢随机化算法，但其中有一个算法我尤其喜爱——即使在你已经理解了它的工作原理之后，从程序员的角度来看，它依然充满魔力。它仅用极少的时间或空间开销，就完成了几乎不可思议的事情。这个算法叫做 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 值仅为 16k 个寄存器使用 12KB 字节。

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



红色和绿色的线条是使用两个完全不相关的集合进行的两次不同运行。图中显示随着基数的增加，误差保持一致。然而对于小得多的基数，你可以获得小得多的误差：



绿线显示了基数达到 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”是为了向弗拉若莱致敬 [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 只在某个寄存器被修改时打开“缓存失效”位。

经过这一改动，即使尝试使用 50 个并发客户端、每个流水线 32 个元素以最大速度添加元素，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

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

    cardinality = m*log(m/ez);

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

线性计数在大基数下相比 HyperLogLog 表现不佳，但在小基数下表现非常好。由于 HLL 寄存器也会附带起到线性计数位图的作用，通过统计零寄存器的数量，就可以在 HLL 表现不佳的区间内应用线性计数。请注意，这之所以可行，是因为当我们更新寄存器时，我们实际使用的不是最长零序列，而是最长零序列加一。这意味着如果添加一个元素并且它寻址到一个从未被寻址过的寄存器，该寄存器将从 0 变为不同的值（至少为 1）。

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



蓝线是误差的平均值。如你所见，在 40k 之前使用线性计数时，越趋向更大的基数，点的“波束”就越宽（误差更大）。当我们切换到 HLL 原始估计时，误差较小，但存在偏差：算法在 40k-80k 范围内高估了基数。

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

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

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



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

值得注意的是，在我的研究过程中我发现，当不使用偏差修正时，至少对于 m=16384，从线性计数切换到原始 HLL 估计的最佳值实际上接近 3 而非 [1] 中提到的 2.5，因为 3 的值既能改善偏差也能改善误差。大于 3 的值会改善偏差（值为 4 时可完全修正偏差），但会对误差产生不良影响。

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

未来工作
===

直观上看，似乎有可能在采用线性计数时利用我们拥有的额外信息来改善算法输出的误差。在标准的线性计数算法中，寄存器宽度仅为 1 位，因此我们只有两种信息：迄今为止是否有元素哈希到该位。然而最初提出的 HLL 算法 [1] 以及在 Google 修改后的算法 [2]，在回退到线性计数时仍然仅使用零寄存器的数量作为算法的输入。有可能利用寄存器中存储的信息也能改善输出。

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

结论
===

HyperLogLog 是一种令人惊叹的数据结构。我希望 Redis 的实现——将在几天内于稳定版本中提供（Redis 2.8.9 将包含它）——能以即用形式为许多程序员提供这一工具。

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