41.8 布隆过滤器
一句话
布隆过滤器用 m 位数组 + k 个哈希回答一个方向的问题——「这个元素一定不在」；它只会把不在的说成「可能在」，不会把在的说成不在，代价是假阳性可调不可消、不支持删除、每元素约 10 bit，所以它只能当否决开关，不能当缓存或唯一性判据。
布隆过滤器凭什么用 120MB 表示 1 亿个 key
插入 x：k 个哈希算出 k 个位置，全部置 1
查询 x：k 个位置里只要有 1 个是 0 → x 一定不在
全是 1 → x 可能在（也可能只是别人的位撞上了）
| 表示方式 | 1 亿 key 的内存 | 支持删除 | 假阴性 | 假阳性 | 能取回原值 |
|---|---|---|---|---|---|
| HashSet / 原值集合 | 6–10GB | ✅ | 无 | 无 | ✅ |
| 排序数组 + 二分 | 1–2GB | ❌（需重建） | 无 | 无 | ✅ |
| 标准布隆（p=1%） | 120MB | ❌ | 无 | 1% | ❌ |
| Counting Bloom | ~480MB | ✅ | 无 | 略高 | ❌ |
| Cuckoo Filter | ~150MB | ✅ | 无 | ~0.05% | ❌ |
🔑 省下的是「存原值」的钱，不是「存信息」的钱：布隆只记住「这些位被谁碰过」，所以它答不了「值是什么」，也删不掉单个元素。
参数：n 和 p 一确定，m 和 k 就定了
设位数组长度 m、哈希个数 k、元素数 n：
某一位仍为 0 的概率 ≈ e^(-kn/m)
误判率 p ≈ (1 - e^(-kn/m))^k
最优哈希个数 k = (m/n) · ln2 ≈ 0.693 · (m/n)
反解 m/n = -ln(p) / (ln2)^2 ≈ 1.44 · log2(1/p) （bit/key）
| 目标误判率 p | bit/key | 最优 k | 1 亿 key 的内存 |
|---|---|---|---|
| 10% | 4.8 | 3 | 60MB |
| 1% | 9.6 | 7 | 120MB |
| 0.1% | 14.4 | 10 | 180MB |
| 0.01% | 19.2 | 13 | 240MB |
| 0.0001% | 28.8 | 20 | 360MB |
🔑 误判率每降低 10 倍，内存只增约 4.8 bit/key（+48%）——这是布隆最划算的地方；但反过来，容量翻倍而参数不变，误判率会从 1% 涨到 16%（实测见下），超容量 4 倍时约 68%。所以生产上必须监控「已插入数 / 设计容量」，接近 100% 就重建。
布隆过滤器的假阳性有方向：只能否决，不能确认
| 场景 | 布隆的判断 | 该怎么用 | 安全吗 |
|---|---|---|---|
| 缓存前置过滤 | 不在 → 直接返回空 | 只拦「不在」 | ✅ |
| URL / 黑名单过滤 | 不在 → 放行；在 → 再查精确名单 | 「在」只当线索 | ✅ |
| 爬虫 URL 去重 | 已抓过 → 跳过 | 1% 会漏抓 | ⚠️ 业务可容忍才行 |
| 用户名唯一性校验 | 已存在 → 拒绝注册 | 1% 的新用户被误拒 | ❌ |
| 权限 / 白名单判定 | 在 → 放行 | 假阳性 = 越权 | ❌ |
判断口诀：「不在」是确定答案，「在」只是待验证的线索。 只要业务把「在」当最终结论用，1% 的假阳性就会变成 1% 的误杀或越权。
⚠️ 还有一类更危险的错误：假阴性。布隆过滤器承诺「没有假阴性」的前提是与权威存储同步——如果数据写进了 DB、但
Add布隆失败（进程崩溃、网络抖动、异步任务丢失），这个 key 就会被永久判成「不存在」，用户看不到自己刚创建的数据。这比假阳性严重得多：假阳性只是多查一次库，假阴性是数据「消失」。所以布隆过滤器的写入要走可靠投递（见 24.6 本地消息表），并有「定期全量重建」兜底。
布隆过滤器的死穴：不能删除
位是被 k 个元素共享的。要删除元素 x，你不能把它的 k 位清 0——那些位可能是别的元素置的，清掉就制造了假阴性。
| 方案 | 支持删除 | 内存/元素 | 误判率 | 代价 |
|---|---|---|---|---|
| 标准布隆 | ❌ | 9.6 bit | 1% | 最省；删除只能整体重建 |
| Counting Bloom | ✅ | 约 4×（每 bit 配 4 bit 计数器） | 略高 | 计数溢出后退化，仍需定期重建 |
| Cuckoo Filter | ✅ | 约 12 bit | 0.05% 量级 | 插入可能失败，需要扩容策略 |
| Scalable Bloom | ❌ | 随层数增长 | 逐层累加 | 适合 n 未知（按需加层）；仍不支持删单个元素 |
| 双 buffer 定期重建 | ✅（整体） | 2× | 1% | 最简单可靠：旧布隆继续服务，新布隆建好后原子切换 |
💡 选型顺序：n 已知且只增不减 → 标准布隆；有删除 → Cuckoo；n 会持续增长但删除很少 → 定期重建 + 预留 30% 余量。Counting Bloom 现在很少用，它的空间优势被 Cuckoo 吃掉了。
布隆过滤器和缓存怎么配合
请求 → 参数校验 → 布隆过滤器 ──不在──▶ 直接返回「不存在」（0 次 DB）
│
└─可能在─▶ L1 / L2 ──miss──▶ DB
它挡在缓存之前，因为它的判断比缓存还便宜（内存版一次查询约 100ns，RedisBloom 一次约 0.5ms）。放在哪一层，是个明确的取舍：
| 位置 | 查询耗时 | 容量 | 多实例一致性 | 适用 |
|---|---|---|---|---|
| 应用内存 | ~100ns | 每实例一份（1 亿 key @1% = 120MB × N） | 各自构建，需重建同步 | 数据量可控、追求极致延迟 |
RedisBloom（BF.RESERVE / BF.ADD / BF.EXISTS） | ~0.5ms | 一份（120MB） | 单一事实源 | 多实例、数据频繁变化 |
布隆只是漏斗的第一层，完整的分层顺序（浏览器 → CDN → L1 → L2 → DB）见 41.7 多级缓存。
内存布隆的容量账：1 亿 key、p=1% → 120MB/实例，20 个实例就是 2.4GB；RedisBloom 同样数据只占 120MB，但每次查询多 0.5ms。用「实例数 × 120MB」对比「每次多 0.5ms」做决定，不要拍脑袋。
它与进程内的 L1 抢同一块内存，预算要一起算（算法见 41.2 本地缓存与分布式缓存 的内存段）。
重建的窗口：1 亿 key × 7 次哈希 ≈ 7 亿次哈希运算，单核约 70 秒。这 70 秒里不能清空旧布隆——正确做法是双 buffer：旧布隆继续服务（新建但还没进布隆的数据会被误判「不存在」，靠空值缓存和写后读主兜底），新布隆建好后原子切换。
可运行实现：参数计算 + 实测误判率 + 穿透效果
package main
import (
"fmt"
"hash/fnv"
"math"
)
// ==================== 布隆过滤器 ====================
type bloom struct {
bits []uint64
m uint64 // 位数组长度
k uint64 // 哈希个数
}
// New 按目标误判率 p 反推参数：
//
// m = -n*ln(p) / (ln2)^2 （总位数）
// k = (m/n) * ln2 （最优哈希个数）
func New(n int, p float64) *bloom {
m := uint64(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
k := uint64(math.Round(float64(m) / float64(n) * math.Ln2))
if k < 1 {
k = 1
}
return &bloom{bits: make([]uint64, (m+63)/64), m: m, k: k}
}
// hash64 生成两个 64 位哈希：双哈希法用 h1 + i*h2 派生 k 个位置，
// 不必真的算 k 次字符串哈希。
func hash64(s string) (uint64, uint64) {
h := fnv.New64a()
h.Write([]byte(s))
h1 := h.Sum64()
h2 := (h1 >> 33) | (h1 << 31)
h2 *= 0x9e3779b97f4a7c15
h2 ^= h2 >> 29
if h2 == 0 {
h2 = 1
}
return h1, h2
}
func (b *bloom) Add(s string) {
h1, h2 := hash64(s)
for i := uint64(0); i < b.k; i++ {
pos := (h1 + i*h2) % b.m
b.bits[pos/64] |= 1 << (pos % 64)
}
}
func (b *bloom) MayContain(s string) bool {
h1, h2 := hash64(s)
for i := uint64(0); i < b.k; i++ {
pos := (h1 + i*h2) % b.m
if b.bits[pos/64]&(1<<(pos%64)) == 0 {
return false // 只要有一位是 0，就「一定不在」
}
}
return true // 全是 1：可能存在，也可能只是别人的位撞上了
}
// 用 n 个不存在的 key 实测误判率
func measureFP(b *bloom, n int) float64 {
fp := 0
for i := 0; i < n; i++ {
if b.MayContain(fmt.Sprintf("absent:%d", i)) {
fp++
}
}
return float64(fp) / float64(n)
}
func main() {
const n = 100_000
// ① 按 p=1% 设计，装 n 个 key
b := New(n, 0.01)
for i := 0; i < n; i++ {
b.Add(fmt.Sprintf("user:%d", i))
}
fmt.Printf("① 设计 p=1%%，n=%d：m=%d bit（%.1f bit/key），k=%d，实测误判率 %.2f%%\n",
n, b.m, float64(b.m)/float64(n), b.k, 100*measureFP(b, n))
// ② 同样的参数，塞 2n 个 key：观察误判率如何爆掉
b2 := New(n, 0.01)
for i := 0; i < 2*n; i++ {
b2.Add(fmt.Sprintf("user:%d", i))
}
fmt.Printf("② 超容量 2 倍（装入 %d 个）：实测误判率 %.1f%%\n", 2*n, 100*measureFP(b2, n))
// ③ 接 41.3 的穿透场景：1000 个不存在的 ID，各请求 100 次
const absentKeys, repeats = 1000, 100
dbLoads := 0
for i := 0; i < absentKeys; i++ {
k := fmt.Sprintf("absent:%d", i)
for j := 0; j < repeats; j++ {
if b.MayContain(k) { // 只有假阳性才会被放行
dbLoads++
}
}
}
fmt.Printf("③ 10 万次「查不存在」：挡掉 %d 次，放行回源 %d 次\n",
absentKeys*repeats-dbLoads, dbLoads)
}
输出：
① 设计 p=1%，n=100000：m=958506 bit（9.6 bit/key），k=7，实测误判率 1.01%
② 超容量 2 倍（装入 200000 个）：实测误判率 15.8%
③ 10 万次「查不存在」：挡掉 99100 次，放行回源 900 次
三行对应三个必须记住的事实：
- 设计值可信：1% 是算出来的，实测 1.01%；
- 超容量即失效：多装一倍 key，误判率从 1% 涨到 15.8%（16 倍），过滤效果基本报废；
- 漏斗是有效的：10 万次恶意查询只剩 900 次回源（0.9%），剩余部分由空值缓存兜住，完整的两级漏斗见 41.3 缓存穿透 / 击穿 / 雪崩。
工程细节：四个容易踩的点
| 细节 | 做法 | 不做的后果 |
|---|---|---|
| 容量预估 | 按「未来 12 个月的数据量 × 1.3」设计，监控填充率 | 半年后误判率从 1% 爬到 20%，过滤形同虚设 |
| 哈希函数 | 用双哈希（h1 + i*h2）或成熟库；不要用语言内置的弱哈希 | 分布不均，实际误判率高于公式 |
| 数据同步 | 写库成功后可靠地 Add；定期全量重建 | 假阴性 = 真实数据被判「不存在」 |
| 重建切换 | 双 buffer + 原子切换，旧布隆服务到新布隆就绪 | 重建窗口内所有请求回源，DB 被击穿 |
布隆过滤器在存储引擎里的用法值得对照：LSM 树的每一层有多个 SSTable，查一个不存在的 key 要挨个读盘。给每个 SSTable 配一个布隆（约 10 bit/key），一次内存查询就能排除大部分文件。这里的收益不是「省内存」，而是把一次 100µs 的磁盘 IO 换成一次 100ns 的内存查询——布隆的价值永远是「用极小的内存，省掉一次昂贵的查找」，具体到索引结构见 44.8 索引原理。
反模式
| 反模式 | 后果 |
|---|---|
| 用「布隆说存在」直接拒绝请求 | 1% 的合法用户被误杀，且投诉极难复现 |
| 用布隆校验用户名 / 订单号唯一性 | 误判 = 新用户无法注册 / 新订单被拒 |
| 容量按当前数据量设计，无余量 | 数据涨一倍，误判率涨 16 倍 |
| 期望布隆支持删除，手动清位 | 制造假阴性，把存在的数据判成不存在 |
写 DB 成功但 Add 失败不重试 | 数据「消失」，比假阳性严重一个量级 |
| 重建时先清空旧布隆 | 重建窗口内 100% 回源，DB 被击穿 |
| 多实例各自构建、从不重建 | 各实例判断不一致，问题随实例数放大 |
| 把布隆当缓存（以为能存 value） | 它只存「位」，取不出任何值 |
| 追求 p=1e-9 | 每降 10 倍要多花 4.8 bit/key，边际收益递减、内存线性上涨 |
| 多业务共用一个布隆、key 不加前缀 | 误判率叠加，A 业务的数据让 B 业务误判 |
自检
Q1 你按 1000 万用户、p=1% 上线了布隆过滤器。一年后用户涨到 2000 万，会发生什么？怎么提前发现？
▸ 答案：参数不动时，m/n 从 9.6 bit 掉到 4.8 bit，误判率从 1% 涨到约 16%（实测 15.8%）——原来 10 万次无效请求只放行 1000 次，现在放行 1.6 万次，穿透保护基本失效；若涨到 4 倍（4000 万），误判率约 68%，等于没有布隆过滤器。提前发现的唯一手段是监控填充率 / 已插入数占设计容量的比例，到 70% 就告警、到 90% 必须重建（重建为原容量的 2 倍）。不要等误判率表现出来——误判率本身很难直接观测，你只能看到 DB 回源 QPS 悄悄上涨。
Q2 团队想用布隆过滤器做「用户名是否已被注册」的前置校验，说「误判率只有 1%，可以接受」。这个设计错在哪？
▸ 答案：错在把假阳性用在了「拒绝」方向。布隆说「可能存在」时，真实情况有两种：确实存在（该拒），或者只是哈希撞了（不该拒）。1% 的假阳性意味着 1% 的新用户会被误判为「已注册」而注册失败——这不是性能问题，是功能事故，而且复现概率低、客服极难定位。正确用法是：布隆只用于「不在 → 直接放行 / 直接返回空」这种否决方向；「在」必须回落到权威存储（DB 唯一索引）去确认。唯一性校验的主场是数据库唯一约束，不是布隆。
Q3 1 亿个 key、目标误判率 0.1%，需要多少内存、几次哈希？如果要求再降 10 倍呢？值得吗？
▸ 答案：按公式 bit/key = 1.44·log2(1/p)，0.1% 需要 14.4 bit/key、k=10，1 亿 key 约 180MB；再降 10 倍（0.01%）需要 19.2 bit/key、k=13，约 240MB——只多 33% 内存。所以「从 1% 降到 0.1%」很划算（+50% 内存换 10 倍过滤效果），再往下收益就开始递减，且 k 越大每次查询的哈希次数越多（k=20 时单次查询 20 次内存访问）。经验值：p 取 0.1%–1% 足够，剩下那点假阳性交给空值缓存兜底，比继续加内存便宜。
Q4 布隆重建需要 70 秒，这 70 秒里怎么保证不把 DB 打穿？
▸ 答案：双 buffer + 原子切换，绝不先清空。重建期间旧布隆继续服务：它能挡住历史数据，只是挡不住「重建开始后新写入」的 key——这部分会多回源一次，由空值缓存（TTL 30–120s）和写后读主兜住。新布隆建好后一次性替换指针（Go 里用 atomic.Pointer），旧布隆等引用归零后回收。若重建耗时不可接受，就把「全量重建」拆成「分片重建 + 增量 Add」，每片只停几十毫秒。关键指标是「重建窗口内 DB 回源 QPS 增量」，不是重建耗时本身。