HyperLogLog：用 12KB 统计十亿基数

假设你在运营一个日活过亿的平台。产品经理问你：昨天有多少独立访客？你的第一反应是开一个 HashSet，把每个 user_id 丢进去，最后看 size。

一亿个 64-bit ID，HashSet 的开销大约是 \(100 \times 10^6 \times (8 + 16 + 8) \approx 3.2\text{GB}\)——这还只是一个计数器。如果你要按省份、按渠道、按页面分别统计 UV，内存账单会让你的 SRE 同事当场辞职。

HyperLogLog 告诉你：12KB 够了。不是 12MB，不是 12GB，就是 12KB。

用 12KB 内存，你可以估计高达 \(10^9\) 量级的基数，标准误差仅约 0.81%。这意味着如果真实 UV 是一亿，HyperLogLog 的回答大概率落在 9919 万到 10081 万之间。对于绝大多数业务场景，这个精度绰绰有余。

这不是魔法，是数学。具体地说，是 Philippe Flajolet 和他的合作者们在二十多年间逐步打磨出来的一系列算法：从 1985 年的 Probabilistic Counting，到 2003 年的 LogLog，再到 2007 年的 HyperLogLog，最后是 Google 在 2013 年提出的 HyperLogLog++。每一步改进都建立在严格的概率论和解析组合学之上，同时也包含着精巧的工程权衡。

本文将从基数统计问题的定义出发，完整地推导这条演化路径。我会给出核心公式的直觉解释和严格推导，分析偏差修正的三段式策略，展示 HyperLogLog++ 的稀疏表示优化，讨论 Redis 中的实现细节，最后提供一个完整的 C 语言实现。如果你只想了解”怎么用”，可以直接跳到第九节的 Redis 部分；但如果你想真正理解”为什么有效”，建议从头读起。

一、基数统计问题

什么是基数

给定一个多重集合（multiset）\(S\)，其中元素可以重复出现，基数（cardinality）\(n\) 定义为 \(S\) 中不同元素的数量：

\[ n = |\\{x : x \in S\\}| \]

这个定义看似平凡，但在流式计算场景中它变得极其困难。流式意味着：

数据量巨大，无法全部存入内存。
每个元素只能被观察一次（single-pass）。
我们可能需要在任意时刻给出当前基数的估计。

实际应用场景

基数统计无处不在：

场景	元素	基数含义
网站分析	访客 cookie/user_id	独立访客数（UV）
网络监控	源 IP 地址	发起连接的不同主机数
数据库优化	列值	列的 distinct count（用于查询优化器）
搜索引擎	查询词	独立查询词数量
广告系统	(广告 ID, 用户 ID) 对	广告触达的独立用户数
DDoS 检测	目标端口	被扫描的不同端口数

精确方案的代价

精确计算基数有几种经典方案：

方案一：排序去重。 对数据排序后扫描一遍统计不同元素。时间 \(O(n \log n)\)，空间 \(O(n)\)。流式场景下不可行——你不能对流排序。

方案二：HashSet。 将每个元素插入哈希表，最终返回表大小。时间 \(O(n)\)，空间 \(O(n)\)。这是最直接的方案，但内存开销与基数成正比。一亿个 64-bit 元素，Java 的 HashSet 大约需要 3-4GB。

方案三：Bitmap。 如果元素值域有限（比如 32-bit 整数），可以用一个 \(2^{32}\) 位的位图标记每个出现过的值。空间固定为 512MB，不依赖基数大小。但值域必须预先已知且不能太大。

方案四：Bloom Filter。 空间比 HashSet 小很多（大约 \(1.44 \times n \times \log_2(1/\epsilon)\) 位），但 Bloom Filter 本身不能直接告诉你基数是多少——它只回答”某元素是否可能在集合中”。虽然可以通过 Bloom Filter 的填充率反推基数，但精度很差。

核心矛盾是：精确计数需要的空间与基数成线性关系，而我们希望用与基数无关的常数空间来完成估计。

HyperLogLog 正是为此而生。

二、Flajolet-Martin 的直觉

抛硬币与前导零

让我们从一个极其简单的观察开始。

假设你均匀随机地生成 \(n\) 个二进制字符串。对于每个字符串，你观察它的前导零的数量。直觉告诉你：

大约一半的字符串以 0 开头（前导零 \(\geq 1\)）。
大约四分之一以 00 开头（前导零 \(\geq 2\)）。
大约 \(1/2^k\) 的字符串有 \(\geq k\) 个前导零。

反过来说：如果你在 \(n\) 个字符串中观察到的最大前导零数为 \(R\)，那么 \(n\) 大约是 \(2^R\)。

这就是 Flajolet 和 Martin 在 1985 年论文 Probabilistic Counting Algorithms for Data Base Applications 中提出的核心思想。

形式化

设 \(h: \mathcal{U} \to \\{0, 1\\}^L\) 是一个将元素映射到 \(L\)-bit 二进制串的哈希函数（假设行为近似均匀随机）。定义函数 \(\rho(x)\) 为 \(x\) 的二进制表示中第一个 1 的位置（即前导零数加一）：

\[ \rho(0001\ldots) = 4, \quad \rho(1\ldots) = 1, \quad \rho(01\ldots) = 2 \]

对于多重集合 \(S\) 中的每个元素 \(v\)，计算 \(h(v)\) 并记录 \(\rho(h(v))\)。令：

\[ R = \max_{v \in S} \rho(h(v)) \]

则 \(2^R\) 是 \(|S|\) 的一个（非常粗糙的）估计。

为什么这是对的

考虑事件”至少有一个哈希值的 \(\rho\) 值 \(\geq k\)“。每个哈希值的 \(\rho \geq k\) 的概率是 \(1/2^k\)。如果有 \(n\) 个不同元素：

\[ \Pr[R \geq k] = 1 - (1 - 2^{-k})^n \approx 1 - e^{-n/2^k} \]

当 \(n \gg 2^k\) 时，\(\Pr[R \geq k] \approx 1\)（几乎肯定会观察到）。当 \(n \ll 2^k\) 时，\(\Pr[R \geq k] \approx n/2^k \approx 0\)（几乎不可能观察到）。转折点就在 \(n \approx 2^k\) 附近。所以 \(R \approx \log_2 n\)，即 \(2^R \approx n\)。

致命缺陷

这个估计的方差极大。\(2^R\) 只能取 \(\\{1, 2, 4, 8, 16, \ldots\\}\) 这些 2 的幂次值——这意味着你的估计要么翻倍，要么减半，没有中间状态。对于任何实际应用，这个精度都不可接受。

但 Flajolet-Martin 的贡献不在于给出一个好的估计器，而在于建立了这个令人惊叹的直觉：哈希值的位模式携带了基数信息。

三、LogLog：分桶取平均

随机平均化

降低方差的经典方法是取多次独立实验的平均值。但我们只有一个数据流，怎么得到”多次独立实验”？

答案是随机分桶（stochastic averaging）。将哈希值的前 \(p\) 位用作桶索引，把元素分到 \(m = 2^p\) 个桶中。对每个桶，用剩余位计算 \(\rho\) 值，维护每个桶的最大 \(\rho\) 值。

设 \(M[0], M[1], \ldots, M[m-1]\) 为 \(m\) 个寄存器，每个存储对应桶中观察到的最大 \(\rho\) 值。对于输入元素 \(v\)：

idx = h(v) 的前 p 位
w   = h(v) 的剩余位
M[idx] = max(M[idx], ρ(w))

由于哈希的均匀性，每个桶大约分到 \(n/m\) 个不同元素。每个桶的 \(M[j]\) 大约是 \(\log_2(n/m)\)。对所有桶取平均再做指数变换，就得到一个好得多的估计。

LogLog 算法

Durand 和 Flajolet 在 2003 年提出的 LogLog 算法使用算术平均：

\[ \hat{E}_{\text{LogLog}} = \alpha_m \cdot m \cdot 2^{\frac{1}{m}\sum_{j=0}^{m-1} M[j]} \]

其中 \(\alpha_m\) 是一个依赖于 \(m\) 的修正常数，用于消除系统性偏差。

LogLog 的标准误差为 \(1.30 / \sqrt{m}\)。当 \(m = 2048\)（使用 5-bit 寄存器，内存约 1.25KB）时，标准误差约为 2.87%。

LogLog 的局限

LogLog 使用的算术平均（对 \(M[j]\) 求平均后再取 \(2\) 的幂）等价于对 \(2^{M[j]}\) 取几何平均。几何平均对离群值非常敏感：如果某个桶因为运气好出现了异常大的 \(\rho\) 值，它会显著拉高整体估计。

这种敏感性在小基数场景下尤其明显。当 \(n\) 较小时，很多桶可能是空的（\(M[j] = 0\)），少数桶有偶然偏大的值，导致估计严重偏高。

四、HyperLogLog：调和平均的力量

从几何平均到调和平均

HyperLogLog 的核心改进在于用调和平均（harmonic mean）替代几何平均。调和平均天然地压制大值、强调小值，对离群值的鲁棒性远强于算术平均和几何平均。

回忆三种平均的定义（对正数 \(x_1, \ldots, x_m\)）：

\[ \text{算术平均} = \frac{1}{m}\sum x_j, \quad \text{几何平均} = \left(\prod x_j\right)^{1/m}, \quad \text{调和平均} = \frac{m}{\sum 1/x_j} \]

它们之间有经典不等式：调和 \(\leq\) 几何 \(\leq\) 算术。

HyperLogLog 公式

设 \(Z = \left(\sum_{j=0}^{m-1} 2^{-M[j]}\right)^{-1}\)，即 \(2^{-M[j]}\) 的调和平均（去掉 \(m\) 的因子）。HyperLogLog 的原始估计为：

\[ E = \alpha_m \cdot m^2 \cdot Z = \alpha_m \cdot m^2 \cdot \left(\sum_{j=0}^{m-1} 2^{-M[j]}\right)^{-1} \]

其中修正常数：

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

当 \(m \geq 128\) 时，有很好的近似：

\[ \alpha_m \approx \frac{0.7213}{1 + 1.079/m} \]

特殊值：\(\alpha_{16} = 0.673\)，\(\alpha_{32} = 0.697\)，\(\alpha_{64} = 0.709\)。

直觉解释

为什么这个公式是对的？考虑一个桶分到了 \(n_j\) 个不同元素。\(M[j]\) 大约是 \(\log_2 n_j\)，所以 \(2^{-M[j]}\) 大约是 \(1/n_j\)。于是：

\[ \sum_{j=0}^{m-1} 2^{-M[j]} \approx \sum_{j=0}^{m-1} \frac{1}{n_j} \]

由于元素均匀分到 \(m\) 个桶，\(n_j \approx n/m\)，所以：

\[ \sum 2^{-M[j]} \approx m \cdot \frac{m}{n} = \frac{m^2}{n} \]

因此：

\[ E \approx \alpha_m \cdot m^2 \cdot \frac{n}{m^2} = \alpha_m \cdot n \]

\(\alpha_m\) 的作用就是修正这个近似中的系统性偏差，使得 \(E[E] = n\)（无偏估计）。

标准误差

HyperLogLog 的标准误差为：

\[ \frac{\sigma}{\hat{n}} = \frac{1.04}{\sqrt{m}} \]

当 \(m = 2^{14} = 16384\) 时：

\[ \frac{\sigma}{\hat{n}} = \frac{1.04}{\sqrt{16384}} = \frac{1.04}{128} \approx 0.0081 = 0.81\% \]

这是一个显著的改进：相比 LogLog 的 \(1.30/\sqrt{m}\)，HyperLogLog 只需要约 \((1.04/1.30)^2 \approx 64\%\) 的寄存器就能达到同样的精度，或者在同样的寄存器数量下标准误差降低约 20%。

12KB 的由来

\(m = 2^{14} = 16384\) 个寄存器。每个寄存器需要存储的最大值是 \(\rho\) 的上界。对于 64-bit 哈希，去掉 14 bit 的桶索引，剩余 50 bit，\(\rho\) 的最大值是 51（50 个前导零加一），用 6 bit 就够了（\(2^6 = 64 > 51\)）。

\[ \text{总内存} = 16384 \times 6 \text{ bit} = 98304 \text{ bit} = 12288 \text{ Byte} = 12 \text{ KB} \]

用 12KB 内存，标准误差 0.81%，可以估计的基数上限远超 \(10^{18}\)（64-bit 哈希的理论极限）。在绝大多数实际场景中，\(10^9\) 级别的基数估计轻而易举。

五、偏差修正：三段式策略

HyperLogLog 的原始公式在中等基数范围内表现优秀，但在极小和极大基数时存在系统性偏差。Flajolet 等人在 2007 年的论文中提出了三段式修正策略。

小范围修正（Linear Counting）

当估计值 \(E\) 较小（\(E < 5m/2\)）且有较多空寄存器时，使用 Linear Counting 算法进行修正。

设 \(V\) 为值为 0 的寄存器数量。如果 \(V > 0\)：

\[ E^* = m \ln\frac{m}{V} \]

这个公式来自 Linear Counting 算法（Whang et al., 1990）。其直觉是：将 \(m\) 个寄存器视为 \(m\) 个位置，每个元素随机占据一个位置，空位置的比例与已插入的不同元素数之间存在指数关系。这与经典的”抛球入箱”（balls into bins）模型完全对应。

如果 \(V = 0\)（没有空寄存器），则不进行小范围修正，直接使用 \(E\)。

中间范围：不修正

当 \(5m/2 \leq E \leq 2^{32}/30\) 时，原始估计已经足够好，直接使用 \(E\)。

这里的 \(2^{32}\) 是 Flajolet 原始论文中假设的 32-bit 哈希的值域上界。在使用 64-bit 哈希的现代实现中，这个上界实际上可以调整为 \(2^{64}/30\)，但由于 64-bit 哈希在实际基数范围内几乎不会出现大范围碰撞问题，很多实现直接跳过大范围修正。

大范围修正

当 \(E > 2^{32}/30\) 时，哈希碰撞变得不可忽略。修正公式为：

\[ E^* = -2^{32} \ln\left(1 - \frac{E}{2^{32}}\right) \]

这个公式来自对哈希碰撞的泊松近似。当基数接近哈希值域大小时，不同元素映射到相同哈希值的概率显著增加，原始公式会低估基数。大范围修正通过”生日悖论”的逆运算来补偿这一偏差。

完整算法

def hll_count(registers, m, p):
    """HyperLogLog 基数估计（含偏差修正）"""
    # 修正常数
    if m == 16:
        alpha = 0.673
    elif m == 32:
        alpha = 0.697
    elif m == 64:
        alpha = 0.709
    else:
        alpha = 0.7213 / (1.0 + 1.079 / m)

    # 调和平均
    Z = 1.0 / sum(2.0 ** (-Mj) for Mj in registers)
    E = alpha * m * m * Z

    if E <= 5.0 * m / 2.0:
        # 小范围修正
        V = registers.count(0)
        if V > 0:
            E_star = m * math.log(m / V)
        else:
            E_star = E
    elif E <= (2 ** 32) / 30.0:
        # 中间范围：不修正
        E_star = E
    else:
        # 大范围修正
        E_star = -(2 ** 32) * math.log(1.0 - E / (2 ** 32))

    return E_star

修正策略的工程启示

这三段式修正体现了一个重要的工程哲学：没有一个公式在所有范围内都是最优的，不如在不同范围内使用不同的最优策略。 小范围用 Linear Counting（基于空桶比例），中间范围用 HyperLogLog 的调和平均公式，大范围用哈希碰撞修正。三个公式在各自的最优区间内平滑拼接，覆盖了从 0 到 \(2^{64}\) 的全部范围。

我个人认为这种”分段最优”的思路在很多工程问题中都适用。比如排序算法中，Timsort 在小数组上用插入排序、大数组上用归并排序；比如内存分配器中，小对象走 slab cache、大对象走 mmap。承认”没有银弹”然后分段攻克，往往比寻找一个”统一优雅的解决方案”更实用。

六、HyperLogLog++：Google 的工程改进

2013 年，Google 发表了 HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm，提出了 HyperLogLog++ 算法。这篇论文是工程改进的典范——没有改变核心数学，但通过一系列精巧的工程优化，使得 HyperLogLog 在实际部署中表现更好。

改进一：64-bit 哈希

原始论文使用 32-bit 哈希。在现代应用中，基数可能超过 \(10^9\)，32-bit 哈希（值域仅 \(4.3 \times 10^9\)）会在大范围内引入严重碰撞。HyperLogLog++ 全面切换到 64-bit 哈希，彻底消除了大范围修正的需求。

改进二：小范围偏差修正表

Google 通过大规模实验发现，在小基数范围内，HyperLogLog 的原始估计存在可预测的偏差。他们用经验方法（对每个基数值运行数万次模拟）构建了一个偏差修正查找表。

在估计阶段，如果原始估计 \(E\) 落在小范围内，算法会查找表中最近的几个点，用线性插值得到偏差修正值 \(\text{bias}(E)\)，然后返回 \(E - \text{bias}(E)\)。

if E <= 5 * m:
    bias = interpolate(rawEstimateData, biasData, E)
    E_corrected = E - bias

这个修正表是预计算的，不增加运行时开销。它消除了小范围内 Linear Counting 和 HLL 公式之间的切换不连续性，使得估计在全范围内更加平滑。

改进三：稀疏表示

这是 HyperLogLog++ 最重要的工程创新。

观察：当基数很小时（比如只有几百个不同元素），16384 个寄存器中绝大多数是空的。用密集数组存储这些空寄存器是巨大的浪费。

HyperLogLog++ 引入了稀疏表示（sparse representation）：只存储非零寄存器的 (索引, 值) 对。具体实现使用一个排序列表，每个条目编码为一个整数：

条目 = (桶索引 << 6) | ρ值

当基数很小时，非零寄存器数量远小于 \(m\)，稀疏表示的内存开销远低于密集数组。当非零寄存器数量增长到一定阈值（稀疏表示的大小超过密集表示的 12KB 时），自动转换为密集表示。

稀疏表示还有一个额外好处：可以使用更大的虚拟精度 \(p'\)（比如 \(p' = 25\)）在稀疏阶段获得更高精度。转换为密集表示时，再将 \(p' = 25\) 的桶映射到 \(p = 14\) 的桶上。

稀疏阶段：虚拟精度 p' = 25，2^25 = 33,554,432 个虚拟桶
密集阶段：实际精度 p  = 14，2^14 = 16,384 个实际桶
转换时：每 2^(p'-p) = 2^11 = 2048 个虚拟桶合并为一个实际桶

HyperLogLog++ 的实际效果

Google 的论文报告，在相同精度下，HyperLogLog++ 在小基数范围内的误差比原始 HyperLogLog 降低了数倍，同时在小基数时的内存使用显著减少。在 Google 内部，HyperLogLog++ 被广泛用于广告系统、搜索分析和 BigQuery 等产品中。

算法演化：
FM-Sketch (1985)  → 单个位图，方差极大
     ↓
LogLog (2003)     → 分桶 + 算术平均，σ/n = 1.30/√m
     ↓
HyperLogLog (2007)→ 分桶 + 调和平均，σ/n = 1.04/√m
     ↓
HLL++ (2013)      → 64-bit 哈希 + 稀疏表示 + 偏差修正表

七、合并操作：天然的分布式亲和力

HyperLogLog 最令人赞叹的性质之一是它天然支持合并。这个性质使得它在分布式系统中具有无可替代的价值。

合并原理

给定两个 HyperLogLog 实例 \(A\) 和 \(B\)（使用相同的哈希函数和参数 \(p\)），它们的合并结果是：

\[ C[j] = \max(A[j], B[j]), \quad j = 0, 1, \ldots, m-1 \]

为什么这是正确的？因为 \(M[j]\) 存储的是”桶 \(j\) 中观察到的最大 \(\rho\) 值”。如果一个元素出现在 \(A\) 或 \(B\) 中，它会被分到某个桶 \(j\)，并贡献一个 \(\rho\) 值。合并后的 \(C[j]\) 应该反映 \(A\) 和 \(B\) 中所有元素在桶 \(j\) 中的最大 \(\rho\) 值，这恰好就是 \(\max(A[j], B[j])\)。

void hll_merge(uint8_t *dst, const uint8_t *src, int m) {
    for (int j = 0; j < m; j++) {
        if (src[j] > dst[j])
            dst[j] = src[j];
    }
}

分布式场景

这个性质的威力在分布式计算中充分体现：

场景一：分片聚合。 数据分布在 100 台服务器上，每台服务器独立维护一个 HyperLogLog。需要全局基数时，将 100 个 HLL 逐个合并（或用树形归约），得到的结果与在单台机器上处理全部数据完全等价。

场景二：时间窗口滑动。 预计算每小时的 HyperLogLog，需要”最近 24 小时的 UV”时，合并 24 个小时级 HLL 即可。无需重新扫描原始数据。

场景三：多维度交叉。 为每个 (省份, 渠道) 维度组合维护一个 HLL。需要”全国某渠道的 UV”时，合并该渠道下所有省份的 HLL。需要”某省所有渠道的 UV”时，合并该省下所有渠道的 HLL。

合并的代数性质

合并操作是：

可交换的：\(A \cup B = B \cup A\)
可结合的：\((A \cup B) \cup C = A \cup (B \cup C)\)
幂等的：\(A \cup A = A\)

这三个性质使得 HyperLogLog 构成一个幂等可交换幺半群（idempotent commutative monoid），在代数上属于一种 CRDT（Conflict-free Replicated Data Type）。这意味着在分布式系统中，无论合并的顺序如何、是否有重复合并，结果都是确定的。

节点 1: HLL_A
节点 2: HLL_B
节点 3: HLL_C

合并方式一：merge(merge(A, B), C)
合并方式二：merge(A, merge(B, C))
合并方式三：merge(merge(A, C), B)
合并方式四：merge(merge(A, B), merge(B, C))  ← 重复合并 B

以上四种方式结果完全相同！

合并不支持减法

需要注意的一点：HyperLogLog 不支持删除操作。\(\max\) 操作不可逆——你无法从合并结果中”减去”某个 HLL。如果你需要支持删除，需要考虑其他数据结构，或者使用可以从时间窗口中移除的预聚合策略。

合并的网络开销

合并一个 HLL 只需要传输 12KB 数据。在分布式环境中，这几乎可以忽略不计。对比精确计数方案，后者可能需要传输数 GB 的原始数据或 HashSet。这使得 HyperLogLog 在跨数据中心的聚合场景中尤其有价值。

八、Redis 的 HyperLogLog 实现

Redis 从 2.8.9 版本（2014 年）开始内置 HyperLogLog 支持。Redis 的实现是学习 HyperLogLog 工程细节的绝佳案例。

基本命令

PFADD  key element [element ...]   # 添加元素
PFCOUNT key [key ...]              # 估计基数（多 key 时自动合并）
PFMERGE destkey sourcekey [sourcekey ...]  # 合并多个 HLL

PF 前缀是为了纪念 Philippe Flajolet（2011 年去世），算法的主要发明人。

Redis 实现细节

参数选择。 Redis 使用 \(p = 14\)（\(m = 16384\) 个寄存器），每个寄存器 6 bit。这与原始论文的推荐一致。

内存布局。 密集表示下，16384 个 6-bit 寄存器紧凑排列在一个字节数组中。每个字节存储 1.33 个寄存器（\(8/6 \approx 1.33\)）。具体的位操作：

// 获取第 regnum 个寄存器的值
int byte_offset = regnum * 6 / 8;
int bit_offset  = regnum * 6 % 8;  // 0, 6, 4, 2, 0, 6, ...
int val = (registers[byte_offset] >> bit_offset) & 0x3F;
if (bit_offset > 2) {
    // 寄存器跨越字节边界
    val |= (registers[byte_offset + 1] << (8 - bit_offset)) & 0x3F;
}

稀疏表示。 Redis 实现了类似 HyperLogLog++ 的稀疏表示。稀疏编码使用三种字节操作码：

操作码	格式	含义
ZERO	`00xxxxxx`	连续 x+1 个值为 0 的寄存器
XZERO	`01xxxxxx yyyyyyyy`	连续 (x<<8\|y)+1 个值为 0 的寄存器
VAL	`1vvvvvxx`	连续 x+1 个值为 v+1 的寄存器

这种 run-length encoding（RLE）在稀疏情况下极其高效。一个空的 HyperLogLog 只需要 2 字节（一个 XZERO 操作码表示 16384 个连续的零）。

自动升级。 当稀疏表示的字节数超过 hll-sparse-max-bytes（默认 3000）时，Redis 自动将其转换为密集表示。

哈希函数。 Redis 使用 MurmurHash2 的 64-bit 变体作为内部哈希函数。

Redis HyperLogLog 的内存实际开销

空 HLL（稀疏表示）：    约 200 字节
少量元素（稀疏表示）：  几百字节到几 KB
转换阈值后（密集表示）：12304 字节（12KB 寄存器 + 16 字节头部）

在 Redis 中，一个 HyperLogLog 键的最大内存消耗约为 12KB。这使得你可以轻松维护数万个 HLL 键（比如每个页面一个、每个广告位一个），总内存开销仍然很小。

实际使用示例

# 网站 UV 统计
PFADD page:home:20250715 user1 user2 user3
PFADD page:home:20250715 user2 user4 user5  # user2 重复，不影响

# 查看今日首页 UV
PFCOUNT page:home:20250715
# 返回 5（近似值）

# 合并最近 7 天的数据，得到周 UV
PFMERGE page:home:week \
    page:home:20250709 page:home:20250710 \
    page:home:20250711 page:home:20250712 \
    page:home:20250713 page:home:20250714 \
    page:home:20250715

PFCOUNT page:home:week
# 返回 7 天的独立访客总数（自动去重）

一个容易被忽略的陷阱

PFCOUNT 在多 key 模式下（PFCOUNT key1 key2 key3）会在内部执行合并操作。这意味着它的时间复杂度是 \(O(N \cdot m)\)，其中 \(N\) 是 key 数量。如果你频繁地对大量 key 调用 PFCOUNT，应该考虑用 PFMERGE 预合并，然后对合并结果调用 PFCOUNT。

九、与其他方案的对比

基数统计方案全景

方案	空间	时间（每元素）	精度	可合并	支持删除
HashSet	\(O(n)\)	\(O(1)\) 均摊	精确	是（集合并）	是
Bitmap	\(O(\|\mathcal{U}\|)\)	\(O(1)\)	精确	是（OR）	是
Linear Counting	\(O(n)\)	\(O(1)\)	~1%	是（OR）	否
Bloom Filter（反推）	\(O(n)\)	\(O(k)\)	差	是（OR）	否
LogLog	\(O(\log\log n)\)	\(O(1)\)	~1.30/sqrt(m)	是（max）	否
HyperLogLog	\(O(\log\log n)\)	\(O(1)\)	~1.04/sqrt(m)	是（max）	否
HLL++	\(O(\log\log n)\)	\(O(1)\)	更优	是（max）	否

HyperLogLog vs. Bloom Filter

这两者经常被混淆，但它们解决的是不同问题：

Bloom Filter 回答集合成员查询：“元素 \(x\) 是否在集合中？”（可能有假阳性）
HyperLogLog 回答基数查询：“集合中有多少不同元素？”

如果你需要同时回答两个问题，就需要同时维护两个数据结构。

HyperLogLog vs. Linear Counting

Linear Counting（Whang et al., 1990）使用一个 \(m\) 位的位图。每个元素哈希到一个位置并置 1。基数估计为 \(-m \ln(V/m)\)，其中 \(V\) 是仍为 0 的位数。

Linear Counting 的精度与 HyperLogLog 相当，但它的空间是 \(O(n)\)——位图大小必须与基数同阶才能保证精度。当基数增长到位图接近全满时，精度急剧下降。

HyperLogLog 的空间是真正的 \(O(\log\log n)\)，在任意基数范围内都保持恒定的相对误差。

HyperLogLog vs. 精确计数

在什么情况下应该使用 HyperLogLog 而非精确计数？

用 HyperLogLog： 基数可能很大（百万级以上），内存预算有限，能接受约 1% 的误差，需要合并多个计数器。

用精确计数： 基数不大（几千以下），需要 100% 精确，需要知道具体有哪些元素（不只是数量），需要支持删除。

一个常见的工程模式是两者结合：先用 HyperLogLog 做粗略估计，如果估计值超过阈值则触发精确计数流程。

十、完整 C 语言实现

以下是一个完整的 HyperLogLog 实现，约 200 行，包含所有核心操作。

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>

/* --------------------------------------------------------
 *  HyperLogLog implementation
 *  p = 14, m = 16384 registers, 6-bit each => 12KB
 * -------------------------------------------------------- */

#define HLL_P          14
#define HLL_M          (1 << HLL_P)        /* 16384 */
#define HLL_ALPHA      0.7213 / (1.0 + 1.079 / HLL_M)
#define HLL_REG_MAX    51                   /* max ρ for 64-bit hash, p=14 */

typedef struct {
    uint8_t registers[HLL_M];
} HyperLogLog;

/* ---- MurmurHash3 finalizer (64-bit mix) ---- */
static uint64_t hll_hash(const void *key, int len) {
    const uint8_t *data = (const uint8_t *)key;
    uint64_t h = 0x5bd1e995ULL;
    for (int i = 0; i < len; i++) {
        h ^= (uint64_t)data[i];
        h *= 0xc6a4a7935bd1e995ULL;
        h ^= h >> 47;
    }
    h *= 0xc6a4a7935bd1e995ULL;
    h ^= h >> 47;
    return h;
}

/* ---- Count leading zeros in the lower (64-p) bits ---- */
static uint8_t hll_rho(uint64_t hash) {
    /* We look at bits [0 .. 64-HLL_P-1] of the remaining part.
     * ρ = position of the first 1-bit (1-indexed), or max+1 if all zero. */
    uint64_t w = hash & ((1ULL << (64 - HLL_P)) - 1);
    if (w == 0)
        return (uint8_t)(64 - HLL_P + 1);  /* all zeros */
    /* __builtin_ctzll: count trailing zeros (we treat LSB as leftmost) */
    return (uint8_t)(__builtin_ctzll(w) + 1);
}

/* ---- Initialize ---- */
void hll_init(HyperLogLog *hll) {
    memset(hll->registers, 0, sizeof(hll->registers));
}

/* ---- Add an element ---- */
void hll_add(HyperLogLog *hll, const void *elem, int len) {
    uint64_t h   = hll_hash(elem, len);
    uint32_t idx = (uint32_t)(h >> (64 - HLL_P));  /* top p bits as index */
    uint8_t  rho = hll_rho(h);

    if (rho > hll->registers[idx])
        hll->registers[idx] = rho;
}

/* ---- Estimate cardinality ---- */
double hll_count(const HyperLogLog *hll) {
    double sum = 0.0;
    int    zeros = 0;

    for (int j = 0; j < HLL_M; j++) {
        sum += 1.0 / (1ULL << hll->registers[j]);
        if (hll->registers[j] == 0)
            zeros++;
    }

    double alpha = HLL_ALPHA;
    double E = alpha * (double)HLL_M * (double)HLL_M / sum;

    /* Small range correction */
    if (E <= 2.5 * HLL_M) {
        if (zeros > 0) {
            E = (double)HLL_M * log((double)HLL_M / (double)zeros);
        }
    }

    /* Large range correction (for 32-bit hash; skip for 64-bit) */
    /*
    double two32 = 4294967296.0;
    if (E > two32 / 30.0) {
        E = -two32 * log(1.0 - E / two32);
    }
    */

    return E;
}

/* ---- Merge two HLLs (union) ---- */
void hll_merge(HyperLogLog *dst, const HyperLogLog *src) {
    for (int j = 0; j < HLL_M; j++) {
        if (src->registers[j] > dst->registers[j])
            dst->registers[j] = src->registers[j];
    }
}

/* ---- Estimate intersection via inclusion-exclusion ---- */
double hll_intersection_estimate(const HyperLogLog *a, const HyperLogLog *b) {
    /* |A ∩ B| ≈ |A| + |B| - |A ∪ B|
     * Note: this estimate can be very inaccurate for small intersections. */
    HyperLogLog merged;
    memcpy(&merged, a, sizeof(HyperLogLog));
    hll_merge(&merged, b);

    double count_a     = hll_count(a);
    double count_b     = hll_count(b);
    double count_union = hll_count(&merged);

    double intersection = count_a + count_b - count_union;
    return intersection > 0 ? intersection : 0;
}

/* ---- Debug: print register distribution ---- */
void hll_debug(const HyperLogLog *hll) {
    int dist[HLL_REG_MAX + 2];
    memset(dist, 0, sizeof(dist));
    for (int j = 0; j < HLL_M; j++)
        dist[hll->registers[j]]++;

    printf("Register distribution:\n");
    for (int i = 0; i <= HLL_REG_MAX; i++) {
        if (dist[i] > 0)
            printf("  rho=%2d : %d registers\n", i, dist[i]);
    }
}

/* ---- Memory usage ---- */
size_t hll_memory(void) {
    return sizeof(HyperLogLog);
}

/* ============================================================
 *  Demo / test
 * ============================================================ */

int main(void) {
    HyperLogLog hll;
    hll_init(&hll);

    printf("HyperLogLog demo (p=%d, m=%d, memory=%zu bytes)\n",
           HLL_P, HLL_M, hll_memory());

    /* Test 1: add known number of elements */
    int test_sizes[] = {100, 1000, 10000, 100000, 1000000};
    int n_tests = sizeof(test_sizes) / sizeof(test_sizes[0]);

    for (int t = 0; t < n_tests; t++) {
        hll_init(&hll);
        int n = test_sizes[t];

        for (int i = 0; i < n; i++) {
            char buf[32];
            int  len = snprintf(buf, sizeof(buf), "elem-%d", i);
            hll_add(&hll, buf, len);
        }

        double est = hll_count(&hll);
        double err = (est - n) / n * 100.0;
        printf("  n=%8d  estimate=%10.0f  error=%+.2f%%\n", n, est, err);
    }

    /* Test 2: merge two HLLs */
    HyperLogLog hll_a, hll_b;
    hll_init(&hll_a);
    hll_init(&hll_b);

    for (int i = 0; i < 50000; i++) {
        char buf[32];
        int  len = snprintf(buf, sizeof(buf), "a-%d", i);
        hll_add(&hll_a, buf, len);
    }
    for (int i = 25000; i < 75000; i++) {
        char buf[32];
        int  len = snprintf(buf, sizeof(buf), "a-%d", i);
        hll_add(&hll_b, buf, len);
    }

    HyperLogLog hll_merged;
    memcpy(&hll_merged, &hll_a, sizeof(HyperLogLog));
    hll_merge(&hll_merged, &hll_b);

    printf("\n  Merge test:\n");
    printf("    |A|=%10.0f (expect 50000)\n", hll_count(&hll_a));
    printf("    |B|=%10.0f (expect 50000)\n", hll_count(&hll_b));
    printf("    |A∪B|=%8.0f (expect 75000)\n", hll_count(&hll_merged));
    printf("    |A∩B|≈%7.0f (expect 25000)\n",
           hll_intersection_estimate(&hll_a, &hll_b));

    /* Test 3: duplicate insensitivity */
    hll_init(&hll);
    for (int round = 0; round < 10; round++) {
        for (int i = 0; i < 10000; i++) {
            char buf[32];
            int  len = snprintf(buf, sizeof(buf), "dup-%d", i);
            hll_add(&hll, buf, len);
        }
    }
    printf("\n  Duplicate test: 10000 unique elements inserted 10 times\n");
    printf("    estimate=%10.0f (expect ~10000)\n", hll_count(&hll));

    return 0;
}

编译与运行

gcc -O2 -o hll hyperloglog.c -lm
./hll

典型输出：

HyperLogLog demo (p=14, m=16384, memory=16384 bytes)
  n=     100  estimate=       100  error=+0.00%
  n=    1000  estimate=       999  error=-0.10%
  n=   10000  estimate=      9960  error=-0.40%
  n=  100000  estimate=    100260  error=+0.26%
  n= 1000000  estimate=    997614  error=-0.24%

  Merge test:
    |A|=     49821 (expect 50000)
    |B|=     49763 (expect 50000)
    |A∪B|=   74902 (expect 75000)
    |A∩B|≈   24682 (expect 25000)

  Duplicate test: 10000 unique elements inserted 10 times
    estimate=     10021 (expect ~10000)

十一、工程陷阱

在生产环境中使用 HyperLogLog 时，以下是常见的陷阱和解决方案：

陷阱	现象	解决方案
哈希函数质量差	估计严重偏离，偏差不随数据量增长而收敛	使用密码学级别或高质量非密码学哈希（MurmurHash3、xxHash、CityHash）；避免 Java 默认 `hashCode()`
哈希位数不足	大基数时估计饱和，无法区分 \(10^8\) 和 \(10^9\)	使用 64-bit 哈希；如果使用 32-bit 哈希，大范围修正也有天花板
合并不同参数的 HLL	结果错误且无明确报错	所有参与合并的 HLL 必须使用相同的 \(p\) 和哈希函数；在序列化格式中包含参数校验
小基数精度差	基数 < 1000 时相对误差达 5-10%	使用 HLL++ 的偏差修正表或稀疏表示；对精度要求高的小基数场景考虑精确计数
高估交集基数	包含-排斥公式 \(\\|A \cap B\\| = \\|A\\| + \\|B\\| - \\|A \cup B\\|\) 误差放大	当 \(\\|A \cap B\\|\) 远小于 \(\\|A\\|\) 和 \(\\|B\\|\) 时，包含-排斥的相对误差被放大；考虑使用 MinHash 估计 Jaccard 相似度再推算交集
忘记元素编码一致性	同一个 user_id 在不同服务中被编码为不同字节序列（如 UTF-8 vs. ASCII、大端 vs. 小端），导致被视为不同元素	规范化元素编码：统一字符编码、统一字节序、统一序列化格式
Redis PFCOUNT 多键性能	对数百个键执行 `PFCOUNT key1 key2 ...` 导致延迟飙升	用 `PFMERGE` 预合并到目标键，然后对目标键执行 `PFCOUNT`
寄存器位数选择错误	自行实现时使用 5-bit 寄存器，导致溢出	64-bit 哈希配 \(p = 14\) 时，\(\rho\) 最大值为 51，需要 6-bit 寄存器（范围 0-63）
序列化兼容性	不同语言/版本的实现使用不同的序列化格式，合并时出错	定义明确的二进制序列化协议（参考 Redis 的格式或 Google 的 Protobuf 格式）；在头部包含版本号和参数
过度信任单次估计	运气差时单次估计偏差可达 3-4 个标准差	理解 0.81% 是标准误差（1σ），95% 置信区间约 \(\pm 1.62\%\)，99.7% 约 \(\pm 2.43\%\)；关键决策场景应多次采样或使用精确计数

十二、个人思考

概率数据结构的哲学

HyperLogLog 所属的概率数据结构家族（Bloom Filter、Count-Min Sketch、MinHash 等）共享一个深刻的洞见：在很多实际场景中，“大致正确”比”精确但昂贵”更有价值。

这与传统计算机科学教育的重点相悖。我们被教导追求精确算法、最优复杂度、零误差。但现实世界中，数据量的增长速度远超硬件的提升速度，而业务对精度的要求往往没有那么高。HyperLogLog 用 0.81% 的误差换取了 \(10^6\) 倍的内存节省——这不是”退而求其次”，而是一种理性的工程选择。

数学之美

我一直觉得，HyperLogLog 的数学推导是概率论在工程中最优美的应用之一。从”哈希值前导零的最大值可以估计基数”这个粗糙的直觉，到通过分桶和调和平均将其打磨成一个精度可控、误差可证明的工程工具，整个过程展示了数学分析如何将一个看似不靠谱的 trick 变成一个严谨的算法。

Flajolet 本人是解析组合学（Analytic Combinatorics）领域的大师。他对 HyperLogLog 精度的分析使用了梅林变换（Mellin transform）和鞍点法（saddle-point method）等高深的复分析工具。如果你有兴趣深入，强烈推荐他与 Robert Sedgewick 合著的《Analytic Combinatorics》一书——你会发现，HyperLogLog 只是他宏大理论框架中的一个小应用。

工程与理论的平衡

Google 的 HyperLogLog++ 论文让我印象最深的一点是：它没有改变任何核心数学，所有改进都是工程层面的。64-bit 哈希消除了一个边界条件问题；偏差修正表用实验数据弥补了理论公式在小范围内的不足；稀疏表示利用了实际工作负载的特征（大多数 HLL 实例的基数远小于寄存器数量）。

这提醒我们：好的工程不是”实现论文”，而是”在论文的基础上，针对真实工作负载做持续优化”。 理论给你正确性保证和渐近最优性，工程给你常数因子和边界条件的处理。两者缺一不可。

关于 12KB 的思考

12KB 这个数字本身就很有教育意义。它告诉我们：信息论意义上的下界和工程意义上的实际开销之间，可能存在巨大的鸿沟。朴素方案需要 GB 级内存，HyperLogLog 需要 12KB，两者都在解决同一个问题，差距是五个数量级。

这种”以空间换不确定性”的交易，在我看来是未来大规模数据处理的核心范式之一。当数据增长到一定规模，你将不得不接受近似结果——不是因为你不想要精确答案，而是因为精确答案的代价已经超过了它带来的边际价值。

HyperLogLog 证明了这种交易可以做得非常划算。

参考文献

Flajolet, P., Martin, G. N. (1985). Probabilistic Counting Algorithms for Data Base Applications. Journal of Computer and System Sciences, 31(2), 182-209.
Durand, M., Flajolet, P. (2003). LogLog Counting of Large Cardinalities. In Annual European Symposium on Algorithms (ESA), 605-617.
Flajolet, P., Fusy, E., Gandouet, O., Meunier, F. (2007). HyperLogLog: the Analysis of a Near-Optimal Cardinality Estimation Algorithm. In Conference on Analysis of Algorithms (AofA), 127-146.
Heule, S., Nunkesser, M., Hall, A. (2013). HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm. In International Conference on Extending Database Technology (EDBT), 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.
Redis Documentation. PFADD / PFCOUNT / PFMERGE. https://redis.io/commands/pfadd
Flajolet, P., Sedgewick, R. (2009). Analytic Combinatorics. Cambridge University Press.
Antirez (Salvatore Sanfilippo). Redis new data structure: the HyperLogLog. http://antirez.com/news/75

算法系列导航：上一篇：Unicode 算法 | 下一篇：Count-Min Sketch

相关阅读：Bloom Filter 全家族 | 流式算法总论

目录