3.2 HyperLogLog：十二KB数清一亿基数

3.2 HyperLogLog：十二KB数清一亿基数

本节摘要：HyperLogLog 是基数估算结构：不存任何元素本身，只记录每个元素哈希后二进制串的"最长前导零"长度，用 16384 个寄存器分桶观测，以固定约 12KB 内存估算任意规模的去重计数，标准误差约 0.81%。它换来的是极致的空间，付出的是精确性与可列举性。

一个抛硬币问题

不停抛硬币，连续正面（反面）出现了 k 次才停。直觉告诉我们：进行了大约 2 的 k 次方次抛掷。反过来，知道了最大连续次数，就能反推总次数的量级——这就是 HyperLogLog 的全部直觉。

把每个元素的哈希值看成一串抛硬币结果：哈希值均匀分布，前导零越长越罕见。看到最长前导零是 20，说明大约见了 2 的 20 次方个不同元素。单次观测方差太大，于是分桶：低 14 位决定进哪个桶（共 16384 个），高 62 位里数前导零，各桶记各自的最大值，最后用调和平均汇总——异常值被平滑，误差收敛到百分之一以内。

哈希分桶与前导零观测

注意内存恒定的含义：一万个元素和一百亿个元素，占用的都是这 12KB。计数规模翻十倍，成本一个比特都不涨——这是传统"HashSet 去重存全量"永远做不到的。

命令全家桶只有三个

> PFADD page:index:uv u1 u2 u3 u4 u5    # 记录访问
> PFCOUNT page:index:uv                 # 估算去重后的数量
(integer) 5
> PFMERGE page:all:uv page:index:uv page:detail:uv   # 合并
> PFCOUNT page:all:uv
​

一个完整的每日 UV 统计流水线：每个页面一个 HLL 键按天命名，凌晨定时 PFMERGE 出全天总量，键设 TTL 让旧数据自动过期（第 5 章）。写入方在应用层按用户标识 hash 后 PFADD，读取方拿到的是一个"够准"的数字。

误差不是嘴上说的，亲手测一遍就有数。背景：往一个 HLL 键里灌十万个不同的用户 id；操作与结果：

# 应用侧生成十万个不同id，批量 PFADD
> PFADD test:uv id_1 id_2 id_3 ... id_100000
(integer) 1
> PFCOUNT test:uv
(integer) 100538            # 真实值100000，偏差约0.5%
# 再灌一百万，看误差与内存
> PFADD test:uv id_100001 ... id_1100000
> PFCOUNT test:uv
(integer) 1102934           # 真实值1100000，偏差约0.27%
> MEMORY USAGE test:uv
(integer) 12352             # 还是那12KB出头，纹丝不动
​

解读三点：偏差落在标准误差 0.81% 的一倍标准差以内，且基数越大相对误差越平稳；MEMOERY USAGE 的读数在两个量级之间完全没变——"恒定内存"不是比喻是实测；变式：把同一批 id 重复 PFADD 一万次，计数不变，幂等性让重放与补数操作随便做。这张实测表拿去说服评审，比引用论文有效。

原理多走一步：从观测到估算的公式

寄存器记的是各桶见到的前导零最大值，汇总时不是简单平均而是调和平均——因为各桶观测的量级差异巨大，算术平均会被个别大值拉爆，调和平均把异常桶的影响压平。估算结果再乘一个只与桶数相关的修正常数。对使用者来说，记住三件事就够：桶数固定 16384，误差只与桶数有关（约 1.04 除以桶数的平方根），与基数规模无关——所以小基数时相对误差反而可能显得大，几百个元素的场景 HLL 没有优势，直接用 Set 才几 KB。

这笔交易的账要算清

再加一行容易被忽略的对比：HashSet 的写入与查询都是精确操作，语义直白；HLL 的 PFADD 是"只进不出"的单向记录，任何"把某个用户从统计里剔掉"的需求都无法满足——删数据集重灌是唯一办法。评审时如果有人提出"误刷量怎么去掉"，这一行就是答案。

由此得出适用判据：报表里给人看趋势的数字，用 HLL；参与资金结算、配额扣减的数字，别用。误差 0.81% 在一亿量级意味着差几十万，趋势图毫无影响，账单就是灾难。

💡 关键直觉：HLL 与 Bitmap 各占一头——Bitmap 精确可运算但内存随基数线性涨，HLL 恒定内存但只有数量。中间还有个折中：RoaringBitmap 类的精确压缩结构，需要"较精确且可控内存"时可以考虑它的模块实现。

多维度统计是 HLL 的隐藏优势，展开走一遍。背景：报表要按"渠道"与"整体"两个口径同时出 UV，且渠道随时可能新增。用 Set 做多口径去重，每个口径都得存全量成员，内存按口径数翻倍；HLL 的做法是每个渠道一个键，读报表时现场合并：

# 渠道各自记录，天然增量
> PFADD uv:android u1 u2 u3
> PFADD uv:ios u4 u5
# 全站口径：合并出临时结果，不动源键
> PFMERGE uv:total_tmp uv:android uv:ios
> PFCOUNT uv:total_tmp
(integer) 5
​

解读：PFMERGE 的成本只是把各键的寄存器逐桶取最大值，微秒级完成；新渠道上线就是多一个键，历史数据一秒都不用重算。变式：按天的键合并成周报月报、按地域合并成大区，同一批 12KB 的键能组合出所有上卷口径——这是"存观测值而非存明细"带来的组合自由，Set 结构给不了。

排错与边界再列三条实操经验。其一，PFADD 的参数别一次传几十万个：命令参数总量有协议上限，应用层按千级分批。其二，PFCOUNT 传多个键时会现场做合并计算，键数多时有一定 CPU 开销，高频读的报表把合并结果落到单独键。其三，键要有 TTL 或滚动命名：HLL 键本身不会自动过期，"按天统计"若不配过期策略，一年后就是三百多个沉默的 12KB，积少成多也要管理。

本节要点回顾

• 原理一句话：最长前导零反推基数，分桶加调和平均压误差
• 16384 个 6bit 寄存器 ≈ 12KB，计数规模再大也不变
• 只有数量没有成员，删元素与列举都不可能
• PFMERGE 无损合并是跨维度统计的支点
• 判据：看趋势用 HLL，要结算回到精确结构