秒杀系统高并发优化实战（C++ / Drogon）：5.7 防缓存穿透：自实现布隆过滤器——海量随机 id 的终结者

5.6 的空值哨兵把"同一个不存在 id"挡在了 Redis 内，但它有个软肋：打过来的 id 如果每个都不一样，哨兵就要为每个不存在的 id 占一个 Redis key——内存随攻击流量线性涨。20 万商品的种子数据下，这个软肋变成现实威胁：id 是连续整数，攻击者随便枚举就能制造海量"新不存在的 id"。这一篇落地布隆过滤器：在进程内用约 1MB 内存维护"真实存在的 sku id 全集"的紧凑摘要，集合外的 id 直接 404——连 Redis 都不打。配套代码 src/service/BloomFilter.h（自实现，约 60 行核心）+ POST /api/cache/warm {"rebuild_bloom":true} 在 5.7 已落地。

本文是「秒杀系统（C++ / Drogon）」系列第五章第七篇。配套代码：src/service/BloomFilter.h、SeckillService::rebuildBloom / bloomAllows / detailSku 前置过滤、config cache.bloom_*。代码对应阶段二 v0.2.x。

一、布隆过滤器：是什么、坑在哪、本质一句话

• 是什么：一种概率型集合数据结构。给定一个元素，它能回答两件事："一定不在集合里"（返回 false），或 "可能在集合里"（返回 true，但可能是误判）。
• 坑（特性即代价）：它绝不漏报，但会误报——明明不在集合里的元素，可能被它放行（假阳性）。误报率由位数组大小和哈希个数决定，可以压到 0.1% 甚至更低，但永远不是 0。另外它不能删除元素（删一个元素要清位，可能把别的元素的位一起清了）。
• 本质一句话：布隆用"可容忍的假阳性"换"极小的内存 + O(k) 的查询"——在防穿透场景里假阳性只是"多放行一次回源"（无害），而"一定不存在"的判断是精确的（收益实打实），所以这笔交易稳赚。

二、为什么这个场景该上布隆：空值哨兵的软肋

空值哨兵（5.6）的问题是有状态：每个查过且不存在的 id 都要在 Redis 里占一个 key。比较一下两种攻击：

关键在量级：商品只有几十个时，空值哨兵的内存成本可忽略；但 seed_sku.sql 把种子推到了 20 万，id 又是连续的——攻击者枚举 1..10^7 随机数，里面 99.98% 是"不存在的 id"，每个都会让哨兵写一个 key。这时布隆的价值就出来了：它不记录"谁不存在"，只记录"谁存在"，内存与攻击流量无关，只与商品总量有关。

三、自实现：位数组 + 双哈希，约 60 行

布隆的全部内涵：m 个 bit + k 个哈希函数。插入时把 k 个哈希位置置 1；查询时看 k 个位置是否全为 1——全 1 才放行。位数组大小和哈希个数由预期元素数 n 与允许误判率 p 决定：

1
2

m = ceil(-n · ln p / ln²2)     位数组大小
k = round(m/n · ln2)           哈希函数个数

n=50 万、p=0.001 → m ≈ 719 万 bit ≈ 0.86 MB，k ≈ 10。用双哈希生成 k 个位置：idx_i = (h1 + i·h2) mod m，两个 64 位哈希用 splitmix64 混出（h2 第二路必须非零，否则所有位置坍缩到第一路）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// src/service/BloomFilter.h —— 自实现核心（节选）
// splitmix64：足够好的 64 位整数混合器，任何输入都均匀散开
static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

void add(uint64_t x) {
    uint64_t h1 = splitmix64(x);
    uint64_t h2 = splitmix64(x ^ 0x94d049bb133111ebULL);
    if (h2 == 0) h2 = 1;                    // 双哈希要求第二路非零
    for (int i = 0; i < hashes_; ++i) {
        setBit((h1 + (uint64_t)i * h2) % bitsCount_);
    }
}

// false = 一定不在集合；true = 可能在（也可能是误判）
bool maybeContains(uint64_t x) const {
    uint64_t h1 = splitmix64(x);
    uint64_t h2 = splitmix64(x ^ 0x94d049bb133111ebULL);
    if (h2 == 0) h2 = 1;
    for (int i = 0; i < hashes_; ++i) {
        if (!testBit((h1 + (uint64_t)i * h2) % bitsCount_))
            return false;                   // 任何一位为 0 → 一定不存在
    }
    return true;
}

为什么不引三方库（bloom / libbloom）：核心逻辑就是上面这几十行，标准库足够；本项目一贯原则——能用在场依赖自写的不引新库（对比自实现 JWT HS256 与登录模块选型，见 ADR-1）。自写还能精确控制线程模型：构建期只由单个预热线程 add，完成后整体替换指针发布，查询期只有只读的 maybeContains——结构上就不需要锁。

四、接入读路径 + "集合语义"的红线

详情接口的读路径变成四级漏斗：

1
2
3
4

GET /api/seckill/{skuId}
  → 布隆（进程内）：maybeContains == false  → 404（连 Redis 都不打）★ 5.7
  → Redis：命中 __nil__ / 命中 JSON        → 404 / 返回              ★ 5.6/5.3
  → 回源 MySQL：查到 → 回写缓存；查无 → 写空值哨兵                   ★ 真相源

1
2
3
4
5
6
7
8
9

// SeckillService::detailSku —— 布隆预过滤在读缓存之前
if (cache_ && cache_->enabled()) {
    if (bloomEnabled_ && !bloomAllows(skuId)) {   // 一定不存在
        bloomRejected_.fetch_add(1);               // 可观测：被挡掉的请求数
        cb(false, Json::Value());                  // 404
        return;
    }
    cache_->getDetail(skuId, /* ...原缓存逻辑... */);
}

两条红线必须写进文档，否则会出事故：

1. fail-open：未构建（冷启动/没跑 rebuild）时 maybeContains 恒返回 true——布隆没建好就放行，绝不误杀正常请求。防穿透是可用性优化，不是正确性闸门。
2. 集合语义：布隆是"构建那一刻的全量 id 集合"。构建之后新加的 sku 在重建前会被误判不存在（运营加品后必须重跑 rebuild）。所以布隆的集合来源必须是静态或低频变更的数据——秒杀商品活动前导入、活动期不变，恰好满足；这也是为什么构建动作和 5.5 预热一样是运营动作（rebuild_bloom 挂在同一个 warm 端点，幂等可随时重跑）。

1
2
3
4
5
6

# 构建（bloom_enabled: true 后重启，再调）：
curl -s -X POST localhost:8080/api/cache/warm \
  -H 'Content-Type: application/json' -d '{"limit":1000,"rebuild_bloom":true}'
# stats 里应能看到布隆已就绪：
curl -s localhost:8080/api/cache/stats | grep -o '"bloom":{[^}]*}'
# → {"enabled":true,"ready":true,"added":200000,"rejected":0,"bits":7188794,"hashes":10}

五、观测与验证：rejected 计数器是收益的直接度量

没有计数器的优化等于没做——布隆的收益被做成了 stats 字段 bloom.rejected（被布隆判"一定不存在"直接挡掉的请求数）。验证攻击场景：

1
2
3
4
5
6
7
8

# 场景：拿"必不存在的 id"连打 100 次（商品 20 万条，200100 必超范围）
for i in $(seq 1 100); do
  curl -s -o /dev/null localhost:8080/api/seckill/200100
done
curl -s localhost:8080/api/cache/stats | grep -o '"bloom":{[^}]*}'
# → rejected ≈ 100：100 次全部在进程内被挡，Redis 0 次 GET、DB 0 次查询
# 对比未开布隆（只有空值哨兵）时：Redis 里会躺着 1 个 200100 的空值 key，
# 且每次 TTL 过期后还要再穿一次。

再换一批不同的不存在 id 打（模拟随机枚举），更能看出布隆的内存优势：rejected 持续涨，而 Redis key 数与 DB miss 几乎不动——布隆挡掉的不是一次请求，是一整类请求。

实测数字（rejected 增量、DB miss 对比、Redis key 对比）在 WSL 上按上述步骤跑完回填本文与 PLAN §5.4。

六、小结

🐾 核心三句话：空值哨兵防"重复打同一个不存在"，布隆防"海量随机不存在"——后者用恒定 ~1MB 换掉随攻击流量线性涨的 Redis 内存；布隆说"不存在"是精确的、说"存在"是概率的，正合适防穿透（误判只是多放行一次无害回源）；但它是"构建时刻的全集"，新商品上架必须重跑 rebuild——把它和预热一起做成运营动作，就是这个原因。

5.8 讲最后一层：进程内本地 LRU 做 L1，把"Redis 命中也要走的那次网络往返"也省掉。