前导零 · 调和平均 · 标准误 1.04/√m

HyperLogLog：12KB 数清一亿个 key

「这个月有多少个不同的访客」是一个精确统计代价极高的问题：唯一的精确答法是把见过的 key 全存下来去重。HyperLogLog 用 12288 字节回答任意规模的这个问题，标准误 0.81%。

它依据的是一个观察：一个足够随机的 hash，其二进制表示以 $k$ 个 0 开头的概率是 $2^{-k}$ 。见过 $n$ 个不同的 hash，最长的那串前导零大约是 $\log_2 n$ 位。反过来，看见了一串 $k$ 位的前导零，就有理由猜基数在 $2^k$ 附近。

1 · 前导零个数与基数

把 32 位 hash 从高位往低位读，取前 $p$ 位当桶下标，余下 $32 - p$ 位数前导零。定义 $\rho(w)$ 为 $w$ 的前导零个数加一，那么 $\rho$ 的取值分布是几何分布： $P(\rho = k) = 2^{-k}$ 。

定义 1.1（rank） 对 32 位 hash $h$ 与桶下标位数 $p$ ，桶号为 $h$ 的高 $p$ 位，rank 为 $h$ 的低 $32 - p$ 位左对齐后的前导零个数加一。低位全为 0 时 rank 取 $32 - p + 1$ 。

图 1-1 · 一个 key 的 32 位 hash 如何切成桶下标与前导零两段，以及只用一个寄存器时八组独立数据各自给出的估计。可改 key 与

p

观察切分，可拖动真实基数观察单寄存器估计的抖动幅度。

2 · 单个极值的方差

只留一个寄存器、记录全部 key 里最长的那串前导零，估计式就是 $2^{\rho_{\max} - 1}$ 。实测真实基数 10000、八组独立数据时，八个估计分别是 16384、4096、16384、32768、8192、8192、65536、8192，最大与最小相差 16 倍，均方相对误差 216%。

问题出在估计量的粒度上。 $\rho_{\max}$ 是一个极值统计量，只能取整数， $2^{\rho_{\max} - 1}$ 于是只能落在 2 的整数次幂上，相邻两档之间差一倍。任何单一极值估计都逃不掉这个粒度。

出路是取多个独立的极值再平均。把 hash 的高 $p$ 位拿去选桶，每个桶各自维护一个 $\rho_{\max}$ ，就得到了 $m = 2^p$ 个近似独立的估计器，每个估计器看到约 $n/m$ 个 key。

3 · 分桶与调和平均

$m$ 个桶各给出一个 $2^{M[j]}$ ，怎么合成一个数是关键。算术平均不行：某个桶偶然拿到一个大 rank 时， $2^{M[j]}$ 会大得离谱，一个离群桶就能把平均值拉飞。

调和平均 是这一步的答案：先取倒数求和，再取倒。倒数把大值压成接近 0 的贡献，离群桶几乎不影响结果。HyperLogLog 的估计式是

E = \alpha_m \cdot m^2 \Big/ \sum_{j=0}^{m-1} 2^{-M[j]}

分母那一项正是 $m$ 除以调和平均。相比 LogLog 用几何平均，调和平均把标准误从 $1.30/\sqrt{m}$ 压到 $1.04/\sqrt{m}$ ，这一步是 HyperLogLog 相对 LogLog 的全部改进。

图 3-1 · 分桶后的寄存器分布、调和平均与最终估计。可调

p

与真实基数，观察空桶数、走的是哪一段修正，以及相对误差与标准误

1.04/\\sqrt m

的关系。

Redis 取 $p = 14$ ，即 $m = 16384$ 。每个桶存 6 bit（够表示 $0$ 到 $63$ 的 rank，而 32 位 hash 下 rank 最大只到 19），合计 $16384 \times 6 / 8 = 12288$ 字节。标准误 $1.04/\sqrt{16384} = 0.8125\%$ 。

4 · 偏差修正常数

上式里的 $\alpha_m$ 补的是一处系统性偏差：不加它的话，调和平均给出的估计恒偏高。Flajolet 等人算出的积分式是

\alpha_m = \left( m \int_0^\infty \left( \log_2 \frac{2 + u}{1 + u} \right)^m du \right)^{-1}

工程上不解这个积分，而是用它的渐近式 $\alpha_m = 0.7213 / (1 + 1.079/m)$ ，另给 $m = 16$ 、 $32$ 、 $64$ 三档写死的数值解 $0.673$ 、 $0.697$ 、 $0.709$ 。 $m = 16384$ 时渐近式给出 $0.721253$ ，与极限值 $0.7213$ 只差 $6.6 \times 10^{-5}$ 。

5 · 两端修正的接缝

$E$ 这个式子在两端都失效。基数远小于 $m$ 时大量桶还是 0，调和平均被这些 0 主导，估计严重偏高；基数接近 $2^{32}$ 时 hash 开始大量碰撞，估计偏低。标准做法各打一个补丁：

$E \le 2.5m$ 且还有空桶时改用 linear counting， $\hat{n} = m \ln(m/V)$ ，其中 $V$ 是空桶数。
$E > 2^{32}/30$ 时用 $\hat{n} = -2^{32} \ln(1 - E/2^{32})$ 反解碰撞。

第一个补丁的接缝处有一段真实的偏差。 $p = 14$ 、每个基数 24 组独立数据的实测：基数 36000 时平均相对误差 $-0.055\%$ ，40000 时跳到 $+1.933\%$ ，42000 时到峰值 $+2.227\%$ ，均方相对误差 2.286%，接近标准误的三倍。之后随基数增大缓慢回落，60000 时降到 $+0.342\%$ 。

图 5-1 ·

p = 14

时相对误差随基数的变化，红点表示该基数下两段修正被不同数据分别触发。可切换纵轴在偏差、均方误差与最大值之间观察接缝处的尖峰。

成因是两段公式在接缝处不连续：原始估计式在 $E$ 略大于 $2.5m$ 的区间本身带正偏差，而在此之前这一段一直被 linear counting 挡着。HLL++ 修的正是它，办法是给每个 $p$ 预先测出 200 个基数点上的偏差存成表，运行时按最近邻插值减掉。

警示 · 这一段偏差差点被写成另一个结论。用 12 组独立数据跑时，基数 80 万处的平均相对误差是 $+0.733\%$ ，看着像 32 位 hash 的碰撞开始咬人。把组数加到 32 组后，同一个基数的偏差落回 $+0.143\% \pm 0.162\%$ ，前一个数字是抽样噪声。真正稳定的正偏差只有接缝处那一处，全站正文里的 24 组曲线是重跑后的版本。

6 · 稀疏与稠密

12288 字节是定长的，基数只有几十时也照占不误。Redis 的对策是给小基数另备一套 稀疏编码：桶值大多为 0，把它们游程压掉。三个 opcode 各管一段：

opcode	字节	覆盖
`ZERO`	1	连续 1 到 64 个零桶
`XZERO`	2	连续 1 到 16384 个零桶
`VAL`	1	连续 1 到 4 个相同的非零桶值，值域 1 到 32

一个空的 HLL 是一条 XZERO，共 2 字节。基数增长时零桶被逐个填掉，游程碎成一堆 VAL，编码长度反超定长。实测 $p = 14$ 的切换点在基数 1676：此时稀疏编码要 3001 字节，刚越过 hll-sparse-max-bytes 的默认值 3000。

图 6-1 · 上半是一个

m = 64

的 HLL 的游程切分，下半是

p = 14

时两种编码的字节数曲线。可拖动已加入的 key 数观察 opcode 如何从一条 XZERO 碎成一串 VAL。

另有一条与字节数无关的硬条件：VAL 的值域只到 32，任何一个桶的值超过 32 就必须转稠密。 $p = 14$ 时 rank 最大 19，这条在实践中不会触发； $p$ 更小时（余下的位更多）才可能撞上。

7 · PFMERGE 的成立依据

PFMERGE 只做一件事：逐桶取两边的最大值。它成立的理由不在概率论，而在桶里存的那个量的语义——桶存的是「落进本桶的全部 hash 里，最长的那串前导零」，这个量对并集的答案，恰好等于两边各自答案的最大值。

合并结果与对并集直接建一份逐桶相等，不是近似相等。这一条可以逐桶断言，core/hll.test.ts 里就是这么验的： $p = 14$ 、两批各 3 万个 key，合并后 16384 个桶与直接建的那一份全部对上。

图 7-1 · 两批各 2 万个 key 的合并结果与直接建一份的对照，另附「把两个估计相加」的错误做法。可调重叠比例观察三种结果的分歧。

把两个估计相加则完全不行：重叠部分被计了两次。实测两批各 2 万个 key、重叠 30% 时，相加得 40203，真值 34000，高估 18.2%；重叠 100% 时高估 103%。这个误差随重叠比例上升，与 HLL 本身的精度无关。多机汇总要的是逐桶取 max 那一种，可合并性在分布式场景里的分量不低于省内存。

8 · 参考文献

Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics and Theoretical Computer Science Proceedings, AH, 137–156.
Durand, M., & Flajolet, P. (2003). Loglog counting of large cardinalities. ESA 2003, 605–617.
Heule, S., Nunkesser, M., & Hall, A. (2013). HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. EDBT 2013, 683–692.
Whang, K.-Y., Vander-Zanden, B. T., & Taylor, H. M. (1990). A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems, 15(2), 208–229.
Sanfilippo, S. (2014). Redis new data structure: the HyperLogLog. antirez.com.