HyperLogLog详解

一、什么是HyperLogLogs？

HyperLogLogs是Redis提供的一种概率数据结构，用于高效统计集合的基数（Cardinality，即集合中不同元素的数量）。例如：

• 统计网站的独立访客数（UV）；
• 统计APP的活跃用户数；
• 统计广告的独立曝光数。

1.1 基数估计的痛点

传统的基数统计方法（如用Set存储所有元素）存在内存瓶颈：
假设每个用户ID占8字节，统计1亿个独立用户需要1亿×8字节=800MB内存。若按天统计，一个月需要24GB，这对内存是极大的消耗。

1.2 HLL的优势

HLL通过概率算法将内存消耗压缩到固定大小（Redis中为16KB），且误差可控（标准误差约0.81%）。无论基数是1还是1亿，HLL都只占用16KB内存，完美解决了大基数统计的内存问题。

二、HLL的核心原理

HLL的原理基于概率统计中的基数估计算法，具体来自Flajolet-Martin（FM）算法的改进，核心思想是通过哈希值的分布特征估计基数。

2.1 前置知识：伯努利试验与最大前缀零

2.1.1 伯努利试验

伯努利试验是一种只有两种结果（成功/失败）的独立重复试验，例如抛硬币（正面为成功，概率1/2）。
假设我们进行一系列伯努利试验，记录第一次成功时的试验次数（记为k）。例如：

• 第一次抛就正面：k=1；
• 第一次反面，第二次正面：k=2；
• 前3次反面，第4次正面：k=4。

k的期望：E[k] = 1×(1/2) + 2×(1/2)^2 + 3×(1/2)^3 + ... = 2（无穷级数求和）。

2.1.2 最大前缀零（Max Leading Zeros）

假设我们有一个均匀分布的二进制哈希函数（如Redis使用的MurmurHash2），生成的哈希值是64位的二进制串。对于任意元素x，其哈希值h(x)的二进制形式可视为伯努利试验的结果：
从最低位开始（或最高位，不影响结论），第一个1出现的位置记为r（r从1开始计数）。例如：

• 哈希值000...001（最低位是1）：r=1；
• 哈希值000...010（第二位是1）：r=2；
• 哈希值000...100（第三位是1）：r=3；
• 哈希值全为0：r=65（64位全0，第一个1在第65位）。

由于哈希函数是均匀的，r的分布符合伯努利试验的k分布：P(r=t) = (1/2)^t（前t-1位是0，第t位是1）。

2.2 FM算法：基于最大前缀零的基数估计

FM算法是HLL的基础，其核心思想是：通过哈希值的最大前缀零位置估计基数。

2.2.1 原理推导

假设我们有一个集合S，基数为n。对每个元素x∈S，计算其哈希值的r_x（第一个1的位置），取所有r_x的最大值（记为M）。
根据概率理论，M的期望与n的关系为：
E[M] ≈ log2(n)
因此，基数的估计值为：
n ≈ 2^M

2.2.2 示例

假设集合S={a,b,c}，其哈希值的r分别为2、3、4，则M=4，估计基数n≈2^4=16。显然，这个估计值与实际基数3偏差极大（误差433%）。

2.2.3 FM算法的问题

FM算法的误差太大，因为单个M的波动很大（例如，若有一个元素的r异常大，会导致估计值飙升）。

2.3 HLL算法：FM算法的改进

HLL算法通过分桶+调和平均数解决了FM算法的误差问题，是当前最先进的基数估计算法之一。

2.3.1 分桶（Bucketization）

HLL将哈希值分为两部分：

• 前p位：作为桶索引（Bucket Index），用于将元素分配到不同的桶中；
• 后64-p位：用于计算r（第一个1的位置）。

例如，Redis中p=14，因此桶的数量为2^14=16384个（这是Redis选择的参数，平衡了内存和误差）。每个桶对应一个寄存器（Register），存储该桶中所有元素的r的最大值（记为m_i，i为桶号）。

2.3.2 调和平均数（Harmonic Mean）

对于m个桶（m=16384），每个桶的估计值为2^{m_i}。HLL取这些估计值的调和平均数（而非算术平均数）来降低误差。
调和平均数的计算公式为：
H = m / (sum_{i=0}^{m-1} 1/2^{m_i})

为什么用调和平均数？
调和平均数对极端值的敏感度低于算术平均数。例如，若有一个桶的m_i=20（2^20=1,048,576），其1/2^{m_i}=1e-6，对总和的影响很小；而算术平均数会被这个极端值拉高，导致估计值偏大。

2.3.3 修正因子（Correction Factor）

调和平均数的估计值需要乘以修正因子α_m，以修正偏差。α_m的取值与桶的数量m有关，Redis中m=16384，因此：
α_m ≈ 0.7213 / (1 + 1.079/m) ≈ 0.7213（当m很大时，1.079/m可忽略）。

2.3.4 最终估计公式

HLL的基数估计值为：
E = α_m × H = α_m × m / (sum_{i=0}^{m-1} 1/2^{m_i})

2.3.5 误差分析

HLL的标准误差（Standard Error）为：
σ = 1.04 / √m

Redis中m=16384，因此σ=1.04/128≈0.81%。这意味着：

• 估计值落在[n×(1-0.81%), n×(1+0.81%)]区间内的概率为68%（1σ）；
• 落在[n×(1-1.62%), n×(1+1.62%)]区间内的概率为95%（2σ）；
• 落在[n×(1-2.43%), n×(1+2.43%)]区间内的概率为99.7%（3σ）。

2.4 小值与大值修正

HLL的估计公式在基数很小（n < 2.5×m）或基数很大（n > 2^32）时会有偏差，因此需要额外修正：

2.4.1 小值修正（Linear Counting）

当E < 2.5×m（m=16384，即E < 40960）时，使用线性计数（Linear Counting）修正。线性计数的原理是：未被击中的桶的数量越多，基数越小。
修正公式为：
E = m × log(m/k)
其中，k是未被击中的桶的数量（即m_i=1的桶的数量，因为初始时所有桶的m_i=1）。

2.4.2 大值修正（Large Value Correction）

当E > 2^32时，由于哈希值的位数（64位）有限，需要修正：
E = -2^64 × log(1 - E/2^64)

三、Redis中的HLL实现

Redis中的HLL是字符串类型（string），占用16384字节（16KB），对应16384个桶（每个桶用1字节存储m_i）。

3.1 数据结构

每个HLL字符串的结构如下：

• 16384个字节：每个字节对应一个桶（寄存器），存储该桶的m_i（m_i的取值范围是1~65，1字节足够存储）。
• 初始值：所有桶的m_i=1（表示未添加任何元素）。

3.2 核心操作

Redis提供了三个核心命令操作HLL：PFADD（添加元素）、PFCOUNT（估计基数）、PFUNION（合并HLL）。

3.2.1 PFADD：添加元素

功能：将一个或多个元素添加到HLL中。
原理：

1. 对每个元素x，计算其64位哈希值（使用MurmurHash2）；
2. 取哈希值的前14位，得到桶号i（0 ≤ i < 16384）；
3. 取哈希值的后50位，计算r（第一个1的位置，用__builtin_ctz函数高效计算）；
4. 若r >桶i的当前值m_i，则更新m_i=r（否则不操作）。

时间复杂度：O(k)（k为添加的元素数量）。

3.2.2 PFCOUNT：估计基数

功能：返回HLL的基数估计值。
原理：

1. 检查是否有元素添加（是否有桶的m_i>1），若没有，返回0；
2. 遍历16384个桶，计算每个桶的1/2^{m_i}，求和得到sum；
3. 计算调和平均数H = 16384 / sum；
4. 计算初始估计值E = 0.7213 × H；
5. 若E < 40960，使用线性计数修正（E = 16384 × log(16384/k)，k为m_i=1的桶数）；
6. 若E > 2^32，使用大值修正（E = -2^64 × log(1 - E/2^64)）；
7. 返回E的整数部分。

时间复杂度：O(1)（固定遍历16384个桶）。

3.2.3 PFUNION：合并HLL

功能：将多个HLL合并成一个HLL（合并后的HLL的基数是原始HLL的并集的基数）。
原理：

1. 对每个桶i，合并后的HLL的m_i等于所有原始HLL的m_i的最大值（因为每个桶存储的是该桶的最大r，合并后的最大r即为并集的最大r）。

时间复杂度：O(m×k)（m=16384，k为合并的HLL数量）。

3.3 示例：Redis中HLL的使用

# 添加元素到HLL（键为uv:2025-07-11）
127.0.0.1:6379> PFADD uv:2025-07-11 user1 user2 user3
(integer) 1

# 估计基数（返回3，误差0）
127.0.0.1:6379> PFCOUNT uv:2025-07-11
(integer) 3

# 添加更多元素（模拟1亿个用户）
127.0.0.1:6379> PFADD uv:2025-07-11 user4 ... user100000000
(integer) 1

# 估计基数（返回约1亿，误差≤0.81%）
127.0.0.1:6379> PFCOUNT uv:2025-07-11
(integer) 99187500  # 示例值，实际可能在99187500~100812500之间

# 合并两个HLL（uv:2025-07-11和uv:2025-07-12）
127.0.0.1:6379> PFUNION uv:2025-07 uv:2025-07-11 uv:2025-07-12
OK

# 估计合并后的基数（返回两周的独立访客数）
127.0.0.1:6379> PFCOUNT uv:2025-07
(integer) 150000000  # 示例值

四、HLL的优缺点

4.1 优点

• 空间效率极高：固定16KB内存，不受基数大小影响；
• 时间效率高：添加元素（PFADD）、估计基数（PFCOUNT）、合并（PFUNION）均为高效操作；
• 误差可控：标准误差约0.81%，满足大多数应用场景；
• 支持合并：方便统计多个集合的并集基数（如周UV、月UV）。

4.2 缺点

• 无法存储元素：HLL只统计基数，无法获取具体元素列表，也无法判断元素是否存在（如无法用HLL实现“新用户判断”）；
• 估计值有误差：不适合需要精确基数的场景（如金融交易中的精确计数）；
• 合并不可逆：合并后的HLL无法拆分成原始HLL。

五、HLL的适用场景

HLL适用于需要高效统计独立元素数量且对内存敏感的场景，典型示例包括：

• 网站/APP的独立访客数（UV）：按天存储HLL，合并得到周/月UV；
• 广告的独立曝光数：统计每个广告的独立观看用户数；
• 社交网络的好友数：统计每个用户的好友基数（而非具体好友列表）；
• 日志分析中的独立IP数：统计访问日志中的独立IP数量。

六、总结

Redis的HyperLogLogs是概率基数估计的典范，通过分桶+调和平均数将内存消耗压缩到16KB，同时保持了低误差（0.81%）和高速度。其核心原理是利用哈希值的最大前缀零分布特征，通过概率统计估计基数。

HLL的优势在于空间效率和时间效率，适合处理大基数统计场景；缺点是无法存储元素和估计值有误差。在实际应用中，需根据需求选择合适的数据结构（如Set用于精确计数，HLL用于高效估计）。

参考资料：

• Redis官方文档：HyperLogLog；
• 论文：《HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm》（Flajolet et al.）；
• 论文：《HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimator》（Heule et al.）。