12KB 内存估算 1 亿 UV：HyperLogLog 到底怎么做到的？

12KB 内存估算 1 亿 UV：HyperLogLog 到底怎么做到的？

一个真实的替换场景 + 完整可跑的 Python 实现 + 三组实测数据。
全文代码已跑通，数据都是本机实测，不是抄文档。

开篇：一次从 9GB 到 12KB 的替换

先摆一个场景。

假设你做的是日活上亿的产品，要统计每天的独立访客数（UV）。最直观的做法是什么？拿一个 SET，把每个用户的 ID 塞进去，最后 SCARD 一下。

问题来了。Python 里 set 存 1 亿个 64 位整数，实测要吃掉 7.5 GB 内存（这个数字下面有实测）。为了一个“去重计数”的需求占掉 7.5 GB，而且这只是一天的数据——你要是想统计"最近 30 天的去重用户"，内存直接乘 30。

换成 HyperLogLog 之后，同样 1 亿个元素，内存占用是 12 KB，恒定不变，且相对误差控制在 0.81% 以内。

差了多少？大约 64 万倍。

这篇文章把 HyperLogLog 拆开讲透，包括：

• 它凭什么能用常数内存“猜”出基数
• 为什么它的平均值要用调和平均而不是算术平均（这是论文最漂亮的一步）
• 一份纯标准库、可直接运行的 Python 实现（90 行）
• 三组实测数据：误差曲线、内存对比、误差分布

一、先看结论

本机实测（Python 3.14 + NumPy，m = 16384，即 2^14 个桶）：

关键点：从 1000 到 1 亿，相对误差始终在 1% 上下，而内存一个字节都没多。

理论标准误差是 1.04 / √m = 1.04 / 128 = 0.8125%，实测标准差基本贴合。

二、直觉：抛硬币能告诉你什么

先忘掉算法，做个思想实验。

你抛一枚硬币，记录第一次出现正面之前连续出现了几个反面。

• 如果你只抛了 2 次就见到正面，说明不了什么
• 但如果你连续抛出 10 次反面才见到正面，那你大概率抛了非常多次

落在哪个位置，反过来揭示了“你总共抛了多少次”。这就是 HyperLogLog 的全部直觉。

把用户 ID 哈希成一个 64 位整数，这个哈希值均匀随机，每一位是 0 或 1 的概率都一样。于是：

• 哈希值最高位就是 1，概率 1/2
• 最高位是 0、第二位是 1，概率 1/4
• 前 k 位全是 0，概率 1/2^k

如果我在所有哈希值里，观察到最长的前导零串长度是 k，那么大概有 2^k 个不同的值被处理过。

哈希值示例（64 位，只看高位）：
10110100… → 前导零 0 个
01101100… → 前导零 1 个
00101101… → 前导零 2 个
00000011… → 前导零 6 个 ← 最大

推测基数 ≈ 2^6 = 64

就这一句话，HyperLogLog 已经完成了一半。

但只用“最大值”估计，方差大到没法用——单次实验的随机性太强了。解决办法也很朴素：分桶，然后取平均。

三、算法：三步走

第一步：哈希

把每个元素映射成 64 位整数。均匀性是正确性的前提——如果哈希不均匀，后面的概率推导全部失效。

真实工程里用 MurmurHash / xxHash / SipHash（Redis 用的是自己实现的 64 位 MurmurHash）。本文的教学实现用 hashlib.blake2b，够均匀，也够简单。

第二步：分桶

把 64 位拆成两段：

|— 高 p 位 —|— 剩余 64-p 位 —|
桶号 idx 用来数前导零

• 高 p 位当桶号，决定这个元素归哪个桶
• 剩余 64-p 位用来数前导零，得到 rank

每个桶只保留见到过的最大 rank。因为桶数 m 是固定的，只要哈希均匀，元素就会均匀散进各个桶。

p = 14 时 m = 16384 个桶，每个桶只需要 6 bit 就能存下 rank（最大 rank 是 51，6 bit 够用）。

第三步：调和平均（这里才是精髓）

拿到 m 个桶的值 R₁, R₂, …, Rₘ，怎么合并成最终估计？

这里有个容易踩的坑。

如果直接算 2^R 的算术平均，会系统性高估。原因是：桶里存的是 max，不是随机采样。2^R 这个量的分布严重右偏，少数桶拿到极端大的 rank，会把算术平均整个拽上去。

HyperLogLog 用的是调和平均：

α · m²
E = ─────────────
Σ 2^(-Rᵢ)

调和平均对大值不敏感、对小值敏感。它天然抑制那少数几个 “运气爆棚” 的桶，让结果更稳。这是 Flajolet 等人在 2007 年那篇论文里最关键的一步，也是它比前身 LogLog 精度更高的原因。

α 是偏差修正系数：

if m == 16: α = 0.673
elif m == 32: α = 0.697
elif m == 64: α = 0.709
else: α = 0.7213 / (1 + 1.079 / m)

m 较小时用论文给的常数，m ≥ 128 时用那个渐近公式。p = 14 时 α ≈ 0.7213 / (1 + 1.079/16384) ≈ 0.72125。

四、完整实现（可直接运行）

以下是纯标准库实现，复制下来就能跑，不需要装任何包。

"""
HyperLogLog: 用恒定内存估算集合基数
教学版实现，仅依赖标准库，可直接运行。
"""
import hashlib
import math

class HyperLogLog:
"""标准 HyperLogLog，p=14 时桶数 m=16384，标准误差约 0.81%。"""

def __init__(self, p: int = 14):
if not 4 <= p <= 16:
raise ValueError("p 建议取 4~16，否则误差修正项不再适用")
self.p = p
self.m = 1 << p # 桶数
self.registers = bytearray(self.m) # 每个桶只需 6 bit，这里先用 1 字节
self.alpha = self._alpha(self.m)

@staticmethod
def _alpha(m: int) –> float:
"""偏差修正系数，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)

@staticmethod
def _hash64(item) –> int:
"""把任意元素映射成 64 位哈希。真实工程里用 MurmurHash / xxHash。"""
raw = hashlib.blake2b(repr(item).encode("utf-8"), digest_size=8).digest()
return int.from_bytes(raw, "big")

@staticmethod
def _rank(w: int, bits: int) –> int:
"""w 在 bits 位宽度下的前导零个数 + 1。"""
if w == 0:
return bits + 1
return bits – w.bit_length() + 1

def add(self, item) –> None:
h = self._hash64(item)
idx = h >> (64 – self.p) # 高 p 位选桶
w = h & ((1 << (64 – self.p)) – 1) # 剩余位用来数前导零
rank = self._rank(w, 64 – self.p)
if rank > self.registers[idx]: # 每个桶只留最大值
self.registers[idx] = rank

def count(self) –> int:
m = self.m
z = sum(2.0 ** (–r) for r in self.registers)
raw = self.alpha * m * m / z
if raw <= 2.5 * m: # 小基数时偏差大，改用线性计数
zeros = self.registers.count(0)
if zeros:
return round(m * math.log(m / zeros))
return round(raw)

@property
def memory_bytes(self) –> int:
return len(self.registers)

def merge(self, other: "HyperLogLog") –> "HyperLogLog":
"""两个 HLL 求并集：逐桶取大，这就是 UV 可以分天累加的原因。"""
if self.p != other.p:
raise ValueError("p 必须一致")
out = HyperLogLog(self.p)
for i in range(self.m):
out.registers[i] = max(self.registers[i], other.registers[i])
return out

跑一下看看：

import random

for n in (1_000, 10_000, 100_000):
hll = HyperLogLog(p=14)
seen = set()
rng = random.Random(42)
for _ in range(n):
x = rng.getrandbits(64)
hll.add(x)
seen.add(x)
est = hll.count()
print(f"真实基数 {len(seen):>8,} 估计值 {est:>8,} "
f"相对误差 {(est – len(seen)) / len(seen) * 100:+.3f}% "
f"占用 {hll.memory_bytes / 1024:.0f} KB")

输出：

真实基数 1,000 估计值 988 相对误差 -1.200% 占用 16 KB
真实基数 10,000 估计值 9,947 相对误差 -0.530% 占用 16 KB
真实基数 100,000 估计值 99,698 相对误差 -0.302% 占用 16 KB

这里 1000 的误差是 -1.2%，比理论值 0.81% 大。别慌，这是单次抽样的正常波动——理论标准误差是标准差，不是硬性上界，±2σ 就是 ±1.6%。下面实验三会用 300 次重复证明这一点。

merge 那个方法是白送的礼物：max 满足交换律和结合律，所以两个 HLL 逐桶取大就能得到并集。

这意味着 UV 统计可以这样玩：每天存一个 HLL（12KB），要算"最近 30 天去重 UV"，把 30 个 HLL merge 起来就行。存储成本 360KB，而不是 30 天的全量 ID。

验证一下：

a, b = HyperLogLog(), HyperLogLog()
rng = random.Random(7)
day1 = {rng.getrandbits(64) for _ in range(50_000)}
day2 = {rng.getrandbits(64) for _ in range(50_000)} | set(list(day1)[:20_000])

for x in day1: a.add(x)
for x in day2: b.add(x)

merged = a.merge(b)
print(f"两天合并: 真实 {len(day1 | day2):,} 估计 {merged.count():,}")

两天合并: 真实 100,000 估计 99,868

两天的并集真实是 10 万（有 2 万重叠），估计 99,868，误差 -0.13%。

五、实测：三张图

5.1 误差随基数变化

基数从 10³ 扫到 10⁸。浅蓝色带子是理论标准误差 ±0.81%。

两个值得注意的现象：

第一，小基数区（10³、10⁴）的误差反而更小，标准差只有 0.5% 上下，明显优于 0.81%。这不是运气——这个区间触发了线性计数修正（代码里 raw <= 2.5 * m 那个分支），用小基数下更准确的公式替代了调和平均。代价是这段区间必须维护"空桶数"。

第二，10⁵ 之后误差稳定在理论值附近，没有随基数增长而恶化。这正是"常数内存"的底气：精度不依赖数据量。

5.2 内存对比

Python set 实测：存 100 万个 64 位整数要 76.8 MB，每个元素约 80.5 字节（含 set 哈希表槽位和 PyLong 对象）。按这个系数外推到 1 亿个元素，就是 7.5 GB。

HyperLogLog 那条线是一条贴着底部的横线：12 KB，与元素个数完全无关。

这里得说句公道话：拿 Python 的 set 比不公平，set 的每元素开销里相当一部分是 Python 对象模型和哈希表负载因子。换成 C 实现的最紧凑方案（每个 64 位 ID 裸存 8 字节 + 哈希表开销），1 亿个元素也至少要 1GB 以上，而且必须常驻内存。

对比 12 KB——这是 5 到 6 个数量级的差距，不是常数因子的优化。

5.3 误差分布

固定基数 n = 10⁵，重复 300 次：

平均误差 -0.055%
标准差 0.794% （理论 0.812%）
最大偏差 2.934%
落在 ±1σ 内 74.0%
落在 ±2σ 内 94.3%

标准差 0.794% 和理论值 0.812% 对得非常准。

有意思的是 ±1σ 覆盖率 74.0%，而标准正态分布应该是 68.3%。说明 HyperLogLog 的误差分布比正态更集中在均值附近（尖峰厚尾），实际表现比"正态近似"的预期还要稳一点。

六、三个工程细节

6.1 Redis 的 12 KB 是怎么来的

我上面的实现用的是 bytearray，每个桶占 1 字节，所以是 16 KB。

Redis 的做法更抠：每个 rank 最大 51，6 bit 就够。16384 × 6 bit = 12288 字节 = 正好 12 KB。这就是 PFADD 的内存开销。

Redis 还做了两级编码：

• 稀疏编码：基数很小时，空桶占绝大多数，用稀疏表示把 PFADD 压到几百字节
• 密集编码：当稀疏表示超过 hll-sparse-max-bytes（默认 3000 字节）时，自动转成 12 KB 的密集格式

所以一个刚建的 HLL key，内存可能只有几百字节。

6.2 为什么 64 位哈希不需要大基数修正

Flajolet 原论文里有个大基数修正项：

if E > 2³² / 30:
E = -2³² · ln(1 – E / 2³²)

这是为 32 位哈希准备的——当基数逼近 2³² 时估计值会饱和，需要一个对数修正把它拉回来。

用 64 位哈希时，触发阈值是 2⁶⁴ / 30 ≈ 6.1 × 10¹⁷，现实中统计 UV 你不可能碰到。所以用 64 位哈希就可以直接省掉这段逻辑，这也是现代实现（包括 Redis）的普遍做法。

6.3 m 怎么选

精度和内存的权衡很干净：

标准误差 ≈ 1.04 / √m
内存 = m × 6 bit

p 每加 1，内存翻倍，误差降到原来的 1/√2 ≈ 71%。

p = 14 是绝大多数场景的甜点——12KB 换 0.81%，Redis 选它就是因为这个。

七、什么时候不该用它

HyperLogLog 有三个硬限制，用之前想清楚：

1. 它给不出准确值，只有估计值。 0.81% 是统计误差，不是 bug。如果业务要求“必须精确”（比如计费、财务对账），老老实实用精确集合。

2. 它不支持查询单个元素是否在内。 想知道某个用户今天来没来，HLL 回答不了——它只存了桶的 max，原始信息早就丢了。这种需求得用布隆过滤器。

3. 它只支持“添加”和“并集”，不支持删除。 一个用户不能从 HLL 里“移除”。要做滑动窗口（比如“最近 7 天”），得用分桶滚动：每天一个 HLL，过期就丢掉，需要时 merge。

如果只是想省内存又能接受小误判，还可以看看 布谷鸟过滤器（支持删除、查询更快）——那是另一篇文章的话题了。

八、小结

HyperLogLog 聪明的地方在于它承认自己不需要精确，然后把这个让步换成了 5 个数量级的内存节省。

三个关键点回顾：

实测下来，1 亿个元素、12 KB 内存、误差 0.5%，这个性价比很难有对手。

完整代码和实验脚本我放在一起了，直接跑就能复现上面所有图表。

下一篇预告：既然能用 12 KB 数清有多少人来了，那能不能用同样小的内存算出谁来得最多？这就是 Count-Min Sketch——Redis 热点 key 检测、搜索引擎热搜榜背后的算法。感兴趣的话评论区说一声。