Redis--基础知识点--29--HyperLogLog

Redis 的HyperLogLog是一种用于基数统计的概率数据结构。它可以在极小的内存开销下（每个键约 12 KB）估算一个集合中不重复元素的个数（即基数），标准误差为 0.81%。

为什么需要 HyperLogLog？

在传统方案中，统计唯一元素（如独立访客数 UV、唯一搜索词数）通常用 Set 或 Hash 存储，当数据量巨大时（如千万级 IP），内存会迅速膨胀。HyperLogLog 在牺牲少量精确度的前提下，将内存占用从 O(N) 降低到固定 12KB，非常适合超大数据集的基数估算场景。

工作原理简述

HyperLogLog 基于概率计数和伯努利试验的观察：

• 对每个元素使用哈希函数得到二进制串，统计该串中第一个 1 出现的位置（前导零数）。
• 通过多个桶（分桶平均）来抵消偶然性，最后用调和平均得到整体基数的估计值。

Redis 实现中使用了16384 个桶，每个桶用 6 位存储（共 16384 × 6 = 12KB），标准误差约 0.81%。

Redis 中的 HyperLogLog 命令

注意：命令前缀PF取自 HyperLogLog 的发明人 Philippe Flajolet 的名字。

使用示例

# 统计某网页的 UV（独立访客）127.0.0.1:6379>PFADD page1:uv user1 user2 user3(integer)1127.0.0.1:6379>PFADD page1:uv user2 user3 user4(integer)1127.0.0.1:6379>PFCOUNT page1:uv(integer)4# 实际去重后 user1,user2,user3,user4 共 4 个# 合并多个页面的 UV 得到整个网站的 UV127.0.0.1:6379>PFMERGE site:uv page1:uv page2:uv OK127.0.0.1:6379>PFCOUNT site:uv(integer)估算值

适用场景

• 独立访客数（UV）统计：每日访问网站的 IP 或用户 ID 去重计数。
• 注册 IP 去重统计：分析唯一来源 IP。
• 搜索词唯一性统计：计算有多少个不同的搜索词。
• 大数据流中计算 distinct count：如日志分析、用户行为埋点。

重要注意事项

1. 不是精确计数：误差约 0.81%，适合允许少量误差的大规模统计场景。需要精确值时请用 Set 或 Bloom Filter 变种。
2. 无法删除元素：HyperLogLog 是只增结构，不支持从统计中移除某个元素（无PFREM命令）。
3. 小数据量时精确：当基数较小时（< 几千），Redis 内部会使用稀疏编码，实际计数是精确的，达到阈值后才转为估算模式。
4. 合并性能：PFMERGE会读取所有源 key 并写回目标，复杂度 O(N)，大 key 需注意耗时。

与其他结构的对比

总结

HyperLogLog 是 Redis 中一个非常轻量级的基数估算工具，它以 12KB 的固定内存和 0.81% 的误差，解决了海量数据去重计数的痛点。适用于 UV、独立 IP、唯一词条等场景，是在精确性和内存之间取得良好平衡的工程方案。

工作原理详解：

了解即可

好的，我们抛开官方术语，从最直观的概率小实验开始讲起，一步一步让你真正理解 HyperLogLog 是如何“算”出基数的。

第一步：一个抛硬币的奇妙现象

想象你在抛一枚均匀硬币，记录第一次出现正面（记作 1）之前连续抛出了多少个反面（记作 0）。

• 抛一次就得到正面：连续 0 的个数 = 0
• 先反面再正面：01 → 连续 0 的个数 = 1
• 先两个反面再正面：001 → 连续 0 的个数 = 2
• 先三个反面再正面：0001 → 连续 0 的个数 = 3

你会发现：连续 0 的个数越大，这件事发生的概率就越低。
具体来说，连续 k 个 0 的概率是1/2^(k+1)。
所以，如果你在实验中观察到了连续 3 个 0，你就有理由相信：你大概进行了2^(3+1)=16 次抛掷（因为要等这么久才出现一次“001”这个模式）。

核心思想：一个罕见事件的发生，暗示了实验总次数很大。
观察到的“最长连续 0 的位数”可以用来估计总抛掷次数。

第二步：把抛硬币换成哈希函数

对于集合中的每一个元素（比如用户 ID），我们用一个哈希函数把它变成一个二进制串（比如 32 位或 64 位）。
这个二进制串可以看作是一长串的“硬币抛掷结果”——0 是反面，1 是正面。

我们规定：从二进制串的低位（最右边）开始数，看第一个 1 之前有多少个 0。
这个数叫做ρ（rho）。

• 如果哈希值是...1010，末尾是 0，再往前是 1，所以 ρ = 1（只有一个尾随 0）。
• 如果哈希值是...1000，末尾三个 0 然后 1，所以 ρ = 3。
• 如果哈希值是...1111，末尾就是 1，没有尾随 0，所以 ρ = 0。

显然，ρ 越大，这个哈希值就越罕见（概率为 1/2^(ρ+1)）。

第三步：单次估计为什么不准

假设我们只有一个元素，我们算出它的 ρ = 5。
那我们能否说“整个集合的基数大约是 2^(5+1) = 64”？
显然不能——因为可能只是运气好，随便一个元素就产生了很大的 ρ。
反过来，如果集合里有 10000 个不同元素，我们可能并没有观察到 ρ 很大的值（最大 ρ 才 4），那么用 2^(4+1)=32 去估计就会严重偏低。

单个样本波动太大，需要统计多个“实验”来平滑误差。

第四步：分桶平均 —— 让大数定律帮你

HyperLogLog 把哈希值的前几位用来分桶，后几位用来计算 ρ。

• 比如哈希值 64 位：前 14 位作为桶编号（2^14 = 16384 个桶），剩下 50 位用来计算 ρ。
• 每个桶只记录这个桶里所有元素中最大的 ρ。

为什么这样做？
每个桶相当于独立的“抛硬币实验”，我们把所有元素分散到 16384 个桶中，每个桶都看到了该桶内元素的最大尾随零个数。
然后我们把所有桶的估计值综合起来，用调和平均来得到一个更稳的总体估计。

第五步：综合公式（感性理解）

调和平均公式（简化版）：

估计基数 = 常数 × 桶数 × ( Σ 2^(每个桶的最大ρ) 的倒数 ) 的倒数

更直观的理解：
每个桶给出一个局部估计2^(max_ρ)，但这些估计值可能偏大或偏小。调和平均可以压制过大的异常值，使结果更稳定。
最终 Redis 使用的公式加上了一个偏差修正（小基数和大基数时修正不同），但核心就是基于每个桶里记录的最长尾随零，反向估算总的不重复元素数。

第六步：用一个简单例子手算

假设我们只有4 个桶（实际 Redis 有 16384 个桶），简化演示。

集合元素经过哈希后，分布到桶 0~3：

• 桶 0 收到的元素哈希尾随零最大值 = 2
• 桶 1 收到的元素哈希尾随零最大值 = 1
• 桶 2 收到的元素哈希尾随零最大值 = 4
• 桶 3 收到的元素哈希尾随零最大值 = 0

那么每个桶的局部估计：2^2=4，21=2，2^4=16，20=1。

调和平均 = 4 / (1/4 + 1/2 + 1/16 + 1/1) = 4 / (0.25 + 0.5 + 0.0625 + 1) = 4 / 1.8125 ≈ 2.206

乘以桶数（4）再乘一个修正系数（约 0.7213）≈ 2.206 × 4 × 0.7213 ≈ 6.37

所以估算出的基数大约 6 个。
如果实际元素有 7~8 个，误差在可接受范围内。

第七步：Redis 的具体实现细节

• 哈希函数：Redis 使用 MurmurHash2，生成 64 位哈希值。
• 分桶：取前 14 位作为桶索引（0 ~ 16383），剩下 50 位用来计算 ρ。
• 存储：每个桶用 6 位存储最大 ρ（因为 50 位二进制串的尾随零最多 50，6 位足够）。
  16384 × 6 = 98304 位 = 12288 字节 =12 KB。
• 编码优化：当基数很小时（比如桶里大部分还是 0），Redis 使用稀疏编码节省内存，只有超过阈值才转成 12KB 的密集编码。
• 合并（PFMERGE）：对多个 HyperLogLog 的相同桶取max(ρ)，然后重新计算估计值。

第八步：为什么误差是 0.81%？

数学上可以证明，这种分桶调和平均方法的相对标准误差约为1.04 / sqrt(桶数)。
Redis 的桶数 = 16384，sqrt(16384) = 128，1.04/128 ≈ 0.008125 ≈0.81%。
所以你得到的结果有 95% 的概率落在真实值 ±0.81% 范围内。

第九步：直观类比总结

HyperLogLog 就像一个拥有 16384 个记分员的公司。
每个新来的用户（元素）会随机跑到一个记分员那里，并展示自己抛硬币能连续抛多少个反面（ρ）。
记分员只记住他见过的最大反面次数。
最后所有记分员聚在一起，用每个人记住的最大反面次数，通过一个公式反推大概来了多少不同的用户。

因为每个记分员都只存一个很小的数字（最大 ρ，通常 0~50），所以总内存很小。
虽然不能精确说出人数，但误差控制在不到 1%，对于统计 UV 这种需求完全够用。

希望这个逐步拆解能让你彻底明白 HyperLogLog 的魔法。如果还有哪一步不清楚，可以继续问，我用更简单的例子或者画图解释。