布隆过滤器与 HyperLogLog：用误差换内存的概率数据结构

前言

“这个 URL 爬过没有”“今天有多少独立访客”——精确答案可能要几百 MB，而 1% 的误差只要几 MB。概率数据结构就是这笔交易的产物，用可控的误差换内存和速度。

一、布隆过滤器：只能确定"一定不存在"

结构极简：一个 m 位的位数组 + k 个独立哈希函数。

• 插入：对元素算 k 个哈希，把对应位置全置 1；
• 查询：任一位置为 0 → 一定不存在；全为 1 → 可能存在。

所以它只有假阳性，没有假阴性。误判率近似：

[ p \approx \left(1 - e^{-kn/m}\right)^k ]

实用参数：控制 1% 误判率约需 m/n ≈ 9.6 bit/元素、k ≈ 7。100 万元素约 1.2MB——这就是它最大的价值。

不支持删除：多个元素共享位，清一个会误伤其他。需要删除时用计数布隆（每位一个计数器，内存约 4 倍）或布谷鸟过滤器（支持删除、空间利用率更高）。

二、工程落地：缓存穿透防护

async function getUser(id) {
  // 第一道闸：一定不存在，直接返回
  if (!(await redis.call('BF.EXISTS', 'user:bf', `user:${id}`))) return null;

  const cached = await redis.get(`user:${id}`);
  if (cached) return JSON.parse(cached);

  const row = await db.findUser(id);
  if (row) await redis.set(`user:${id}`, JSON.stringify(row), 'EX', 300);
  return row;   // 不存在时也建议写空值缓存，防单点打穿
}

BF.RESERVE user:bf 0.01 1000000   # 误判率 1%，容量 100 万
BF.ADD     user:bf user:1001
BF.EXISTS  user:bf user:1001

四个必须提前想清楚的点：

1. 容量要预估并留余量：超过 capacity 后误判率飙升（RedisBloom 会自动扩容子过滤器，但精度和查询成本都变差），一般留 2 倍；
2. 数据变更只能"加"，不能"减"：用户注销后过滤器里仍存在，表现为多查一次库——业务上可接受；
3. 重建要有切换方案：全量重建期间会漏判，用"双过滤器 + 影子写入"平滑切换；
4. 它替代不了空值缓存：两道闸叠加才对，布隆挡的是"明显不存在"，空值缓存挡的是"刚查过不存在"。

三、HyperLogLog：基数统计的内存奇迹

原理一句话：哈希值的前导零长度，能粗略反映集合规模。单个估计方差太大，于是分成 ( m = 2^{14} = 16384 ) 个桶，取调和平均，再做小基数与大基数偏差修正。

PFADD   uv:2026-11-04 user:1 user:2 user:3
PFCOUNT uv:2026-11-04
PFMERGE uv:week uv:2026-11-03 uv:2026-11-04

坑在这三处：

• PFCOUNT 是 O(n) 的合并计算，热点接口每次调用会吃掉大量 CPU，应定期算好结果缓存；
• PFMERGE 要求精度一致，不同实现（Redis / ClickHouse / 自研）不能混着合并；
• 单 key 适合百万到千万级；十亿级 UV 建议分桶（按日期/业务拆 key）或用 ClickHouse 的 uniqCombined（底层同为 HLL，精度更高且能并行）。

四、还有哪些概率结构

五、选型速查

六、绝对不要用错的地方

1. 权限判断：布隆的假阳性意味着"没权限的人被放行"，这是事故；
2. 唯一性约束：注册去重必须精确，用数据库唯一索引；
3. 计费与对账：HLL 的 0.81% 误差会被放大成真金白银的差额；
4. 需要删除的场景：标准布隆做不到，别硬改业务去凑。

判断标准只有一句：误差会不会转化为资损、越权或数据错误。会，就不能用。

总结

分工记牢：布隆过滤器回答"有没有可能出现"，HyperLogLog 回答"大概有多少"。

它们的经济学是"用 1% 的误差，换掉 99% 的内存和延迟"。在爬虫 URL 去重、缓存穿透防护、UV 统计、热点识别这些场景里，这笔买卖几乎总是划算的——前提是你清楚误差落在哪里，并且它落下的地方不重要。