引言：一个看似不可能的问题
假设你正在运营一个日活用户超过十亿的社交平台，产品经理问你：“今天有多少独立用户访问了我们的网站？“这个问题听起来简单，但当你真正思考如何回答时，会发现它蕴含着深刻的计算机科学难题。
最直观的方法是维护一个包含所有用户ID的集合，每来一个用户就检查是否已存在，不存在则加入。但十亿用户意味着至少需要数十GB的内存——这在许多系统中是不可接受的。更糟糕的是，如果需要统计不同维度的去重（如每个城市的独立用户数），内存需求会呈指数级增长。
flowchart LR
A[用户访问] --> B{内存中存在?}
B -->|是| C[跳过]
B -->|否| D[加入集合]
D --> E[内存+8-64字节]
C --> F[返回计数]
D --> F
E --> G[十亿用户 = 数十GB内存]
早在1985年，法国计算机科学家Philippe Flajolet就意识到这个问题的普遍性，并开创性地提出了概率计数方法。经过二十多年的演进，最终诞生了HyperLogLog算法——一个仅用1.5KB内存就能估算十亿级基数、误差控制在2%以内的概率数据结构。这个结果听起来几乎违背直觉，但数学证明了它的可行性。
本文将深入剖析HyperLogLog算法的核心原理、数学基础、工程实现以及它在大数据时代的演进历程。
第一部分：问题定义与算法演进
1.1 基数估计问题
在集合论中，**基数（Cardinality）指的是集合中不同元素的个数。对于有限集合，基数就是元素的数量。但在实际应用中，我们需要处理的是多集合（Multiset）或数据流（Data Stream）**的基数估计问题。
定义：给定一个数据流 $M = \{x_1, x_2, ..., x_n\}$，其中元素可能有重复，估计其中不同元素的个数 $n = |distinct(M)|$。
这个问题的难点在于：
- 内存约束：无法存储所有见过的元素
- 单遍扫描：数据流只能遍历一次
- 实时性要求：需要在线计算估计值
1.2 精确方法的困境
最直接的精确方法是使用哈希集合：
def exact_count(stream):
seen = set()
for element in stream:
seen.add(element)
return len(seen)
这个方法的时间复杂度是 $O(n)$，看起来很高效，但空间复杂度是 $O(n)$，其中 $n$ 是不同元素的个数。当 $n$ 达到十亿级别时，即使每个元素只存储64位哈希值，也需要8GB内存。
graph TD
A[精确计数方法] --> B[哈希集合]
A --> C[位图法]
A --> D[排序去重]
B --> E[空间: O n]
C --> F[空间: O max_id]
D --> G[空间: O n, 需要2次扫描]
E --> H[十亿用户 = 8GB+]
F --> I[需要连续ID空间]
G --> J[不适合流式处理]
1.3 概率方法的曙光
1985年，Flajolet和Martin在论文《Probabilistic Counting Algorithms for Data Base Applications》中提出了第一个实用的概率基数估计算法，后来被称为Flajolet-Martin算法或PCSA算法。
这个算法的核心思想极其巧妙：利用哈希函数将元素随机化，然后观察哈希值中出现特定模式的概率来推断基数。
flowchart TB
subgraph 核心["核心观察"]
A[哈希值前导零] --> B["0001... → ρ = 4"]
A --> C["01... → ρ = 2"]
A --> D["1... → ρ = 1"]
end
subgraph 概率["概率分析"]
E["P(ρ ≥ k) = 2<sup>-(k-1)</sup>"]
F["如果有2<sup>k</sup>个元素"]
G["很可能出现 ρ ≥ k"]
end
核心 --> 概率
假设我们有一个理想的哈希函数 $h: D \rightarrow \{0, 1\}^L$，它将任意元素映射为长度为 $L$ 的比特串。对于均匀分布的哈希值，第一个比特为0的概率是 $1/2$，前两个比特为00的概率是 $1/4$，前 $k$ 个比特都为0的概率是 $2^{-k}$。
这意味着：如果集合中有大约 $2^k$ 个元素，那么很可能会出现一个元素，其哈希值的前 $k$ 个比特都是0。反之，如果我们观察到的最长前导零序列长度为 $\rho$，那么基数大约是 $2^\rho$。
1.4 算法演进时间线
timeline
title 基数估计算法演进史
1985 : Flajolet-Martin 算法
: 标准误差 ~1.30/√m
: 使用位图存储
2003 : LogLog 算法
: 标准误差 ~1.30/√m
: 内存减少 75%
2003 : SuperLogLog 算法
: 标准误差 ~1.05/√m
: 截断异常值
2007 : HyperLogLog 算法
: 标准误差 ~1.04/√m
: 调和平均, 近最优
2013 : Google HLL++
: 64位哈希
: 稀疏编码优化
2021 : SetSketch
: 统一MinHash与HLL
: 支持相似度估计
1.5 HyperLogLog算法概览
flowchart LR
subgraph 输入["输入处理"]
A[元素 x] --> B[哈希函数 h x]
B --> C[64位比特串]
end
subgraph 分桶["分桶策略"]
C --> D[前14位 → 桶索引 j]
C --> E[后50位 → 计算ρ值]
end
subgraph 更新["寄存器更新"]
D --> F[选择寄存器 M j]
E --> G[ρ = 前导零个数 + 1]
G --> H["M j = max M j, ρ"]
end
subgraph 估计["基数估计"]
H --> I[调和平均]
I --> J[校正常数 αm]
J --> K[估计值 ñ]
end
HyperLogLog的核心创新是使用**调和平均数（Harmonic Mean）**替代几何平均数。调和平均数对极端值更不敏感，能够有效降低方差：
$$\bar{Z} = \frac{m}{\sum_{j=1}^{m} 2^{-M[j]}}$$最终估计值为：
$$\hat{n} = \alpha_m \cdot m^2 \cdot \bar{Z} = \frac{\alpha_m \cdot m^2}{\sum_{j=1}^{m} 2^{-M[j]}}$$重要里程碑：HyperLogLog算法实现了与LogLog相同的精度，但只需要后者的64%内存。更重要的是，它的标准误差系数 $1.04$ 非常接近理论下界 $1/\sqrt{m}$（对应系数为1），因此被称为"近最优"算法。
第二部分：数学原理深度解析
2.1 为什么前导零个数能反映基数？
让我们从概率论角度深入理解算法的核心原理。
graph LR
subgraph 哈希分布["哈希值分布"]
A["h x 服从均匀分布"]
B["每个比特独立"]
C["每个比特为0的概率 = 1/2"]
end
subgraph 概率链["概率链条"]
D["P 第1位=0 = 1/2"]
E["P 前2位=00 = 1/4"]
F["P 前k位=0...0 = 2<sup>-k</sup>"]
end
哈希分布 --> 概率链
假设哈希函数输出 $L$ 位的比特串，对于一个均匀随机分布的哈希值，某个特定比特为0的概率是 $1/2$。定义 $\rho(h)$ 为哈希值 $h$ 中前导零的个数加1（即第一个1出现的位置）：
$$\rho(1...) = 1, \quad \rho(01...) = 2, \quad \rho(001...) = 3, \quad ...$$对于随机哈希值，$\rho$ 服从几何分布：
$$P(\rho = k) = 2^{-k}, \quad k \geq 1$$当 $n$ 较大时，最大 $\rho$ 值的期望约为 $\log_2 n$：
$$E[M] \approx \log_2 n + \text{const}$$2.2 调和平均 vs 算术平均
graph TB
subgraph 问题["为什么不用算术平均?"]
A["算术平均: Σ 2<sup>M j</sup> / m"]
B["2<sup>M</sup> 方差极大"]
C["受极端值影响大"]
end
subgraph 解决["调和平均的优势"]
D["调和平均: m / Σ 2<sup>-M j</sup>"]
E["2<sup>-M</sup> 方差有限"]
F["对极端值不敏感"]
end
问题 --> 解决
2.3 标准误差分析
HyperLogLog的标准误差为：
$$\sigma \approx \frac{1.04}{\sqrt{m}}$$xychart-beta
title "寄存器数量 vs 标准误差"
x-axis ["256", "1024", "4096", "16384", "65536"]
y-axis "标准误差 %" 0 --> 8
line [6.5, 3.25, 1.625, 0.81, 0.41]
这意味着使用2048个寄存器（每个5位，共1280字节），就可以达到约2.3%的标准误差；使用16384个寄存器（共10KB），误差可以降到约0.81%。
2.4 小基数和大基数的校正
flowchart TD
A["估计值 E"] --> B{E ≤ 2.5m?}
B -->|是| C["Linear Counting"]
B -->|否| D{E ≥ 2<sup>32</sup>?}
D -->|是| E["大基数校正"]
D -->|否| F["标准HLL估计"]
C --> G["ñ = m ln m/V"]
E --> H["ñ = -2<sup>32</sup> ln 1 - E/2<sup>32</sup>"]
F --> I["ñ = αm m² / Z"]
小基数校正（Linear Counting）：当 $n < 2.5m$ 时，很多寄存器仍然为0。此时使用Linear Counting算法更准确。设 $V$ 为值为0的寄存器个数，则：
$$\hat{n} = m \ln(m/V)$$第三部分：工程实现的艺术
3.1 Redis的实现架构
flowchart TB
subgraph Redis["Redis HyperLogLog"]
A["PFADD key element..."] --> B["哈希计算"]
B --> C["分桶选择"]
C --> D["寄存器更新"]
E["PFCOUNT key"] --> F["稀疏编码?"]
F -->|是| G["稀疏解码"]
F -->|否| H["直接计算"]
G --> I["调和平均计算"]
H --> I
I --> J["偏差校正"]
J --> K["返回估计值"]
L["PFMERGE dest src..."] --> M["逐寄存器取max"]
end
基本配置：
- 寄存器数量：$m = 16384 = 2^{14}$
- 每个寄存器：6位（可表示0-63）
- 总内存：$16384 \times 6 / 8 = 12288$ 字节 ≈ 12KB
- 标准误差：$1.04/\sqrt{16384} \approx 0.81\%$
3.2 稀疏编码 vs 密集编码
flowchart LR
subgraph 稀疏["稀疏编码 (小基数)"]
A["只存储非零寄存器"]
B["格式: index, value 对"]
C["行程编码压缩"]
end
subgraph 密集["密集编码 (大基数)"]
D["固定大小数组"]
E["每个寄存器6位"]
F["总大小12KB"]
end
稀疏 -->|数据量增加| G{大小超过阈值?}
G -->|是| 密集
G -->|否| 稀疏
稀疏编码适用于小基数场景：
- 使用行程编码（Run-Length Encoding）压缩连续相同的寄存器值
- 当稀疏编码的大小超过密集编码时，自动转换
3.3 Google HyperLogLog++改进
graph LR
subgraph 原始HLL["原始 HyperLogLog"]
A["32位哈希"]
B["需要大基数校正"]
C["固定编码"]
end
subgraph HLL++["HyperLogLog++"]
D["64位哈希"]
E["无需大基数校正"]
F["稀疏/密集自适应"]
G["精确偏差校正表"]
end
原始HLL -->|改进| HLL++
改进一：64位哈希函数——消除了大基数校正的需求。
改进二：稀疏表示——初始时只存储非零寄存器的（索引，值）对。
改进三：精确的偏差校正——通过大量实验建立了精确的偏差校正表。
3.4 合并操作原理
flowchart LR
subgraph HLL1["HLL A"]
A1["M1: 3,5,2,7,..."]
end
subgraph HLL2["HLL B"]
B1["M2: 4,2,6,3,..."]
end
subgraph 合并["合并操作"]
C1["逐位取最大值"]
C2["M = max M1, M2"]
C3["M: 4,5,6,7,..."]
end
HLL1 --> 合并
HLL2 --> 合并
subgraph 结果["结果"]
D["估计 |A ∪ B|"]
end
合并 --> 结果
HyperLogLog的一个强大特性是支持合并操作。两个HyperLogLog结构可以通过对每个寄存器取最大值来合并，合并后的估计值对应两个集合的并集的基数。
第四部分：工业应用与生态
4.1 主要应用场景
mindmap
root HyperLogLog应用
数据库系统
BigQuery 近似去重
Presto 分布式聚合
Redis UV统计
Elasticsearch 基数聚合
网络监控
DDoS检测
流量分析
异常检测
推荐系统
用户行为统计
去重计数
相似度计算
生物信息学
基因组分析
序列相似度
4.2 各系统实现对比
xychart-beta
title "不同系统HLL实现对比"
x-axis ["Redis", "BigQuery", "Presto", "Elasticsearch", "Snowflake"]
y-axis "特性支持度" 0 --> 5
bar [4, 5, 4, 3, 4]
bar [3, 5, 5, 4, 5]
bar [5, 5, 5, 4, 5]
BigQuery：Google BigQuery从2017年开始使用HyperLogLog++进行近似去重计数。官方数据显示，使用HyperLogLog++计算30亿独立用户只需5.7秒，而精确计数需要28秒。
Redis：Redis提供了PFADD、PFCOUNT、PFMERGE三个命令。
4.3 分布式计算架构
flowchart TB
subgraph 分布式["分布式计数架构"]
A[数据分片1] --> B[HLL 1]
C[数据分片2] --> D[HLL 2]
E[数据分片3] --> F[HLL 3]
G[数据分片n] --> H[HLL n]
end
B --> I[合并节点]
D --> I
F --> I
H --> I
I --> J["MERGE操作"]
J --> K["全局估计值"]
HyperLogLog天然支持分布式计算：每个节点独立统计本地数据，然后将结果合并得到全局估计。
第五部分：演进与前沿
5.1 概率数据结构对比
graph TB
subgraph 对比["概率数据结构对比"]
A["HyperLogLog: 基数估计, 极高内存效率"]
B["Bloom Filter: 成员检测, 高内存效率"]
C["Count-Min Sketch: 频率估计, 中等效率"]
D["MinHash: 相似度估计, 中等效率"]
E["Theta Sketch: 联合分析, 中等效率"]
F["SetSketch: 基数+相似度, 高效率"]
end
A --> G["并集操作"]
D --> H["并集+交集"]
E --> H
F --> H
5.2 SetSketch统一框架
flowchart LR
subgraph 参数b["参数 b 的调节"]
A["b → 1"] --> B["SetSketch → MinHash"]
A --> C["b = 2"] --> D["SetSketch → HyperLogLog"]
end
subgraph 功能["功能支持"]
E["基数估计 ✓"]
F["相似度估计 ✓"]
G["并集操作 ✓"]
H["交集操作 ✓"]
I["局部敏感哈希 ✓"]
end
2021年，Otmar Ertl在VLDB发表了论文《SetSketch: Filling the Gap between MinHash and HyperLogLog》，提出了SetSketch算法。
SetSketch的核心洞察是：MinHash和HyperLogLog可以看作同一框架的两种极端情况。通过引入一个参数$b$（基数），可以在两者之间连续调节。
第六部分：实践指南
6.1 参数选择决策树
flowchart TD
A["选择寄存器数量m"] --> B{精度要求?}
B -->|"±5%"| C["m = 256"]
B -->|"±2%"| D["m = 2048"]
B -->|"±1%"| E["m = 8192"]
B -->|"±0.5%"| F["m = 65536"]
C --> G["内存: 160B"]
D --> H["内存: 1.28KB"]
E --> I["内存: 5KB"]
F --> J["内存: 40KB"]
6.2 内存-精度权衡
| m | 标准误差 | 内存（5位寄存器） | 适用场景 |
|---|---|---|---|
| 256 | 6.5% | 160 B | 快速预览 |
| 1024 | 3.25% | 640 B | 实时监控 |
| 4096 | 1.625% | 2.5 KB | 业务报表 |
| 16384 | 0.81% | 10 KB | 精确统计 |
| 65536 | 0.41% | 40 KB | 科学研究 |
6.3 常见陷阱与解决方案
flowchart LR
subgraph 陷阱["常见陷阱"]
A["陷阱1: 寄存器初始化错误"]
B["陷阱2: 哈希函数选择不当"]
C["陷阱3: 合并操作误用"]
D["陷阱4: 精度期望过高"]
end
subgraph 解决["解决方案"]
E["初始化为0, 不是-1"]
F["使用MurmurHash3/xxHash"]
G["交集估计用容斥原理"]
H["明确这是估计值"]
end
A --> E
B --> F
C --> G
D --> H
6.4 监控指标
生产环境中应监控：
- 估计值的分布（是否符合预期）
- 寄存器值的分布（是否均匀）
- 内存使用情况
- 合并操作的频率
结语
HyperLogLog算法体现了概率算法的精髓：用可控的精度损失换取数量级的资源节省。从Flajolet-Martin到HyperLogLog再到SetSketch，这三十多年的演进展示了理论与实践的完美结合。
timeline
title HyperLogLog发展里程碑
section 理论奠基
1985 : Flajolet-Martin 概率计数
2003 : LogLog/SuperLogLog
2007 : HyperLogLog 论文发表
section 工程实践
2013 : Google HLL++
2014 : Redis集成HLL
2017 : BigQuery采用HLL++
section 持续演进
2021 : SetSketch统一框架
2024 : 各大系统广泛应用
Philippe Flajolet被誉为"算法分析之父”，他于2011年去世。但他留下的遗产——HyperLogLog算法——至今仍在支撑着互联网的规模。每当你打开Google Analytics查看用户数据，每当你使用Redis统计独立访客，背后都有Flajolet的智慧在默默工作。
在大数据时代，精确往往是一种奢望，而近似是一种艺术。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. ESA 2003, 605-617.
-
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. AofA 2007, 127-146.
-
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.
-
Ertl, O. (2017). New cardinality estimation algorithms for HyperLogLog sketches. arXiv:1702.01284.
-
Ertl, O. (2021). SetSketch: Filling the Gap between MinHash and HyperLogLog. PVLDB, 14(11), 2244-2257.
-
antirez. (2014). Redis new data structure: the HyperLogLog. Redis Blog.
-
Chassaing, P., & Gérin, L. (2006). Efficient estimation of the cardinality of large data sets. Mathematics and Computer Science, 419-422.