HyperLogLog 深度实战：从 Flajolet-Martin 草图、调和均值估计到 HLL++ 稀疏表示与可合并基数估计的工程全解
引言
在大数据与流式系统里，"集合里有多少个不同元素"（基数 / Cardinality）是一个看似简单、实则昂贵的问题。直接 SELECT COUNT(DISTINCT user_id) 在大表上意味着全量扫描 + 去重排序，在 TB 级数据、每秒百万事件的实时管道里既慢又烧内存。更麻烦的是：基数本身往往只需要近似答案——DAU 是 1,283,400 还是 1,284,000 对决策毫无影响，但为此付出一次全表扫描的代价却难以接受。
HyperLogLog（HLL） 就是为这个问题而生的概率数据结构：它用约 12KB 内存，以 1% 左右的标准误差估计高达 10^9 量级集合的基数，且支持可合并（mergeable）——多个分片各自维护草图，最后按桶取 max 即可无损合并出全局基数。它与本站已发的《布隆过滤器》(16214)、《Count-Min Sketch》(16270) 共同构成"概率数据结构工程"三部曲：Bloom 回答"是否在集合中"，Count-Min 回答"某元素频次多少"，HLL 回答"集合有多大"。本文从第一性原理推导 HLL 的调和均值估计与偏差校正，落地 HLL++ 的稀疏表示，给出可合并的生产级实现与 12 项工程陷阱清单。
一、为什么不能 COUNT(DISTINCT)
精确去重的成本随数据量超线性增长：要么维护一个哈希集合（内存 O(n)），要么排序后相邻比较（CPU O(n log n) + 磁盘 IO）。在以下场景精确法直接出局：
- 实时大屏：每秒百万条事件，要求秒级更新 UV。全量去重无法在窗口内完成。
- 跨分片聚合：数据分散在 1000 个分片，精确去重需把所有 user_id shuffling 到单点，网络与内存爆炸。
- 长周期留存：7 日/30 日 UV，状态必须在内存中长期驻留。
近似基数算法的核心思想：用哈希值的统计特征代替存储元素本身。只要哈希足够均匀，某个比特模式的出现频率就携带了基数的信息。
二、概率计数演化：FM → LogLog → HyperLogLog
2.1 Flajolet-Martin（FM）草图
Flajolet 与 Martin 在 1985 年给出第一个概率计数方案。对集合中每个元素 x：
- 计算一个充分随机的哈希
h(x)（如 64 位）。 - 记
ρ(w)为 w 的二进制表示中从最低位起第一个 1 的位置（从 1 计数），即尾随零的个数 + 1。 - 所有元素中
ρ(h(x))的最大值大致正比于log2(N)。
直觉：若已看到 N 个不同元素，哈希空间被填充到约 2^N 量级，才会出现"末尾连续 N 个 0"的模式。于是估计 N ≈ 2^{max ρ}。FM 取多个独立哈希的均值降低方差。
2.2 LogLog 计数
LogLog 引入分桶（bucket） 思想：用哈希高 p 位把元素映射到第 j ∈ [0, m) 个桶（m = 2^p），每个桶独立记录 ρ 的最大值 M[j]。估计值为各桶 2^{M[j]} 的算术平均再乘以常数：
E = α_m · m · (1/m) · Σ 2^{M[j]} (LogLog 用算术平均)
2.3 HyperLogLog 的关键改进
LogLog 的算术平均对个别异常大的桶非常敏感——一个哈希碰撞导致的超大 M[j] 会严重高估。HyperLogLog（Flajolet 等，2007）用调和平均替代算术平均：
E = α_m · m^2 / Σ 2^{-M[j]}
调和平均天然压制离群桶（分母中 2^{-M[j]} 对大桶很小，权重被压低），把标准误差从 LogLog 的 1.30/√m 降到 1.04/√m，在同等内存下估计精度提升约 25%。
三、核心数学推导
3.1 哈希与分桶
取一个 64 位均匀哈希 h(x)。用低 p 位（或高 p 位，实现自由）定位桶：
j = h(x) & (m - 1) # m = 2^p，p 位桶索引
w = h(x) >> p # 剩余 64-p 位用于计数
ρ(w) = 1 + (w 的二进制中从最低位起第一个 1 的位置) # 即尾随零个数 + 1
M[j] = max(M[j], ρ(w)) # 每桶只保留最大 rank
工程要点：
ρ的分布是几何的。ρ = k的概率为2^{-k}，期望约 2。一个桶长期观察不到大 rank 是常态，调和平均正是为此而生。
3.2 原始估计量
E = α_m · m^2 / Σ_{j=0}^{m-1} 2^{-M[j]}
其中 α_m 是随 m 变化的偏差校正常数（对有限 m 的修正），常用取值：
α_m = (m · (∫_0^∞ (log2(1+t)/t)^m dt)^{-1})^{-1}
小 m 时的实用近似：
| m | 16 | 32 | 64 | 128 | 256 | 1024 | 16384 |
|---|---|---|---|---|---|---|---|
| α_m | 0.673 | 0.697 | 0.709 | 0.715 | 0.719 | 0.728 | 0.730 |
3.3 标准误差
无论基数多大，HLL 的相对标准误差恒为：
σ_E / E ≈ 1.04 / √m
| p | m | 内存（1B/桶） | 标准误差 |
|---|---|---|---|
| 10 | 1024 | 1 KB | 3.25% |
| 12 | 4096 | 4 KB | 1.63% |
| 14 | 16384 | 12 KB | 0.81% |
| 16 | 65536 | 64 KB | 0.41% |
注意：实际实现中每桶常存 5–6 位（rank 上限约 64，需 6 bit），故 12KB 对应
16384 × 6 bit = 12 KB。"12KB 估 10^9 基数误差 <1%" 是 HLL 最经典的卖点。
四、偏差校正：从原始 HLL 到 HLL++
原始 HLL 在小基数时偏差显著（调和平均对稀疏桶不稳定），在大基数时接近理论极限。两处需校正。
4.1 小基数：线性计数混合
当很多桶仍为 0（说明基数远小于 m）时，用 Linear Counting 估计更准：
E_LC = m · log(m / V) # V = 值为 0 的桶数量
实践（HLL 原始论文）按 E 与 m/30、5m/2 的阈值切换：极小时用 LC，中等用原始 HLL，极大时（接近 2^32）做 64 位修正。
4.2 HLL++（Google，Heule et al. 2013）的三大增强
- Empirical Bias Correction：用大量离线实验测量不同基数下的真实偏差，建表（或分段多项式）在运行期减去。这是 HLL++ 把误差再压一半的关键。
- Sparse 表示：基数小时绝大多数桶为 0，改为只存"非零桶 (index, rank)"的稀疏列表，用变长编码（varint）压缩，内存可省一个数量级；超过阈值再切换为 Dense。
- 64 位哈希 + 稀疏/dense 无缝合并：保证稀疏与密集两种内部表示能正确互操作。
工程现实：Redis 的
PFCOUNT/PFMERGE（HyperLogLog 结构）即 HLL 的实用实现；Spark 的approx_count_distinct、BigQuery 的APPROX_COUNT_DISTINCT、Apache DataSketches 均基于 HLL/HLL++ 家族。
五、可合并性：分布式基数的基石
HLL 最被低估的能力是逐桶 max 合并：
M_merged[j] = max(M_a[j], M_b[j]) for all j
因为每桶 M[j] 存的是"该桶见过的最大 rank"，合并两个集合的草图只需逐桶取 max，与合并顺序无关、无信息损失（不像均值需要权重）。这让 HLL 天然适配：
- 分片聚合：每个 worker 维护本地 HLL，shuffle 时只传 12KB 草图而非原始 ID。
- 流式窗口：每分钟一个 HLL，按时间窗 max-merge 得到任意区间 UV。
- 增量更新：新事件只更新对应桶，O(1)。
六、与 Bloom / Count-Min / HLL 的分工
| 结构 | 回答的问题 | 是否可合并 | 典型误差 | 内存(典型) |
|---|---|---|---|---|
| 布隆过滤器 | "x 是否在集合？" | 否（交集/并集受限） | 误判率可调 | 1.2KB@1% |
| Count-Min Sketch | "x 出现多少次？" | 是（逐格 min/加） | 有偏上界估计 | 随 ε/δ |
| HyperLogLog | "集合有多大（去重数）？" | 是（逐桶 max） | 1.04/√m | [email protected]% |
三者可组合： Bloom 挡住"必不存在"的查询，Count-Min 给出频次做限流/热点识别，HLL 给出全局 UV 做大盘——同一套流式管道里各司其职。
七、生产级 Python 实现
下面给出一个可合并、带稀疏/密集切换与序列化的参考实现（教学向，强调正确性而非极致性能）。
import hashlib
import math
import struct
class HyperLogLog:
def __init__(self, p=14):
if not (4 <= p <= 16):
raise ValueError("p must be in [4,16]")
self.p = p
self.m = 1 << p
self.alpha = self._alpha(self.m)
self.registers = [0] * self.m # dense 桶
self.sparse = {} # index -> rank (稀疏模式)
self.sparse_limit = max(64, self.m // 4) # 超过则转 dense
@staticmethod
def _alpha(m):
if m == 16: return 0.673
if m == 32: return 0.697
if m == 64: return 0.709
return 0.7213 / (1 + 1.079 / m)
def _hash(self, x):
# 64 位哈希：用 sha1 取前 8 字节
if isinstance(x, str):
x = x.encode('utf-8')
h = hashlib.sha1(x).digest()[:8]
return int.from_bytes(h, 'big') & ((1 << 64) - 1)
@staticmethod
def _rho(w, max_bits=64):
# 从最低位起第一个 1 的位置（1-based）；全 0 则记为 max_bits+1
if w == 0:
return max_bits + 1
return (w & (-w)).bit_length()
def add(self, x):
h = self._hash(x)
idx = h & (self.m - 1)
w = h >> self.p
rank = self._rho(w)
if self.sparse is not None:
cur = self.sparse.get(idx, 0)
if rank > cur:
self.sparse[idx] = rank
if len(self.sparse) > self.sparse_limit:
self._to_dense()
else:
if rank > self.registers[idx]:
self.registers[idx] = rank
def _to_dense(self):
for idx, rank in self.sparse.items():
if rank > self.registers[idx]:
self.registers[idx] = rank
self.sparse = None
def count(self):
if self.sparse is not None and len(self.sparse) <= self.sparse_limit:
# 稀疏模式：先尝试 Linear Counting
M = self.registers[:]
for idx, rank in self.sparse.items():
M[idx] = max(M[idx], rank)
zeros = sum(1 for v in M if v == 0)
if zeros > 0:
lc = self.m * math.log(self.m / zeros)
if lc <= 2.5 * self.m: # 小基数用 LC 更准
return lc
else:
M = self.registers
# 调和均值估计
sm = sum(2.0 ** (-v) for v in M)
E = self.alpha * (self.m ** 2) / sm
# 大基数 64 位修正
if E > (1 << 32) / 30:
E = -((1 << 32)) * math.log(1 - E / (1 << 32))
return E
def merge(self, other):
if self.p != other.p:
raise ValueError("p must match to merge")
if other.sparse is not None:
for idx, rank in other.sparse.items():
self.add_from_idx_rank(idx, rank)
else:
for idx, rank in enumerate(other.registers):
if rank:
self.add_from_idx_rank(idx, rank)
return self
def add_from_idx_rank(self, idx, rank):
if self.sparse is not None:
cur = self.sparse.get(idx, 0)
if rank > cur:
self.sparse[idx] = rank
if len(self.sparse) > self.sparse_limit:
self._to_dense()
else:
if rank > self.registers[idx]:
self.registers[idx] = rank
使用示例：
h1 = HyperLogLog(p=14)
for u in users_shard_a:
h1.add(u)
h2 = HyperLogLog(p=14)
for u in users_shard_b:
h2.add(u)
merged = HyperLogLog(p=14)
merged.merge(h1).merge(h2) # 可合并：逐桶 max
print(int(merged.count())) # 全局近似去重数
八、12 项生产陷阱清单
- 哈希必须 64 位且均匀：用 32 位哈希（如 CRC32）在基数 > 2^32 时必然撞车，估计直接塌方；优先 Murmur3 / XXH3 / SHA 截断。
- p 一旦选定不可改：合并要求两边
m完全相同，否则merge直接报错；线上变更 p 需全量重建草图。 - 跨语言一致性：Java/Go/Redis/Python 若哈希函数或
ρ的位序（大端/小端）不同，合并结果无意义——统一哈希与字节序。 - 稀疏/密集切换阈值：未设阈值或阈值过高，小基数时内存反而膨胀；HLL++ 的稀疏模式是省内存的关键，但切换瞬间有一次性成本。
- 估计是有偏的：HLL 给期望近似而非区间；对外展示建议同时给出 ±1.04/√m 的误差带，避免被当成精确数。
- 序列化兼容：草图要持久化/跨进程传输，必须定义稳定格式（寄存器数组 + p + 模式），版本升级时做兼容。
- 空集合处理：全 0 桶时
Σ 2^{-M}= m，公式退化；务必在 count() 里对空/极小基数特判（LC 或返回 0）。 - 大基数 64 位修正：接近 2^32 时原始公式会溢出/失真，必须做
−2^32·ln(1−E/2^32)修正。 - 不要对"已估计值"再算术平均：多分片合并必须 merge 草图再 count，绝不可先各算 count 再平均（丢失桶级信息，误差翻倍）。
- precision 与内存权衡：p=14（12KB）是线上甜点；p=16（64KB）换 0.4% 误差，仅在精度敏感场景使用。
- 哈希碰撞≠元素重复：HLL 统计的是"哈希去重"，若业务把不同元素映射到同一哈希（碰撞），会被错误合并——这是概率法的固有代价。
- 监控与校准：定期用已知基数做离线回放，验证实际误差是否符合 1.04/√m，防止哈希退化或实现 bug 悄悄放大偏差。
九、落地场景速查
- UV / DAU 大屏：每服务实例本地 HLL，分钟级 max-merge 出全局 UV。
- 去重 SQL 加速：
APPROX_COUNT_DISTINCT替代COUNT(DISTINCT)，TB 表从分钟级降到秒级。 - 爬虫/广告去重：估算"已见过的 URL/设备"规模，决定采样率。
- 数据质量：异构数据源的"重叠度"粗估（两集合草图合并后对比各自基数）。
结语与系列衔接
HyperLogLog 用 12KB 内存把"10 亿级去重计数"从不可行变成秒级近似，其调和均值估计、偏差校正与逐桶可合并性，是概率数据结构工程的典范。它与《布隆过滤器》(16214)、《Count-Min Sketch》(16270) 一起，构成了"用极小空间回答大问题的三件套"。
下一篇可顺着"可合并近似聚合"继续深入 T-Digest（分位数估计） 或 Count-Min 的孪生 brother——Count Sketch（中位数去偏），把"近似大数据全景"补齐。生产落地时，请务必回到第八节的 12 项陷阱清单逐条核对——绝大多数 HLL 线上事故，都源于哈希不一致或合并前先平均。
发表评论 取消回复