HyperLogLog 用千字节计数数十亿个不同元素

精确基数——即出现了多少不同的用户、IP 地址或搜索查询——通常需要与不同元素数量成正比的内存，这在互联网规模下是不可能的。2007 年，Philippe Flajolet 和 INRIA 的同事发表了 HyperLogLog，这是一种概率草图，能以约 2% 的准确率估算超过十亿的基数，仅需约 1.5 千字节内存。

这个技巧基于抛硬币的直觉：将每个元素哈希成一个均匀分布的随机数，观察最长的前导零序列。出现 n 个零的概率是 2 的负 n 次方，非常小——所以当它出现时，集合很可能足够大才会产生它，因此 2 的 n 次方是对基数的一个良好估计。HyperLogLog 将数据流分成多个子集，每个子集保留一个寄存器来存储其最长的零序列，然后用调和平均合并它们，这样异常值就不会扭曲估计。

该方法源自 Flajolet-Martin 1984 年的算法和 LogLog 算法。使其可用于生产的工程改进出现在 2013 年 Google 的 Heule、Nunkesser 和 Hall 发表的论文《HyperLogLog in Practice》中，该论文修复了大基数和小基数下的偏差和稀疏性问题。

Redis 将 HyperLogLog 作为一项产品功能：其 PFADD、PFCOUNT 和 PFMERGE 命令可以估算多达 2 的 64 次方个不同元素，每个键使用最多 12 KB 内存，标准误差为 0.81%，并且草图可以合并，因此每日计数无需重新读取原始数据流即可组合。