Redis 布隆过滤器实现：位图、RedisBloom 与缓存穿透防线

缓存开篇 §3.1 讲缓存穿透时，布隆过滤器只用一段带过：「在缓存前置一个 Bloom Filter，不在其中的 key 直接拒绝」。但真要在 Redis 上把它落地，问题一下多了起来——用原生 bitmap 手写还是上 RedisBloom 模块？误判率怎么算才不会内存爆炸？无法删除怎么办？ 这一篇就把布隆过滤器在 Redis 上的实现从原理到工程一次讲透。

本文是缓存系列的第 7 篇（布隆过滤器专题）。 开篇把它当作防穿透的一个手段一笔带过；这一篇只钻一件事：这个「概率型集合」在 Redis 上到底怎么实现、怎么调参、怎么扬长避短。

TL;DR

布隆过滤器是「概率型集合」：用一个位数组 + k 个哈希函数，O(1) 判断「元素一定不在」或「可能在」——只有假阳性（误判为在），绝无假阴性（漏判为不在）。这条不对称性是它所有用法的地基。
为什么没有假阴性：插入时把 k 个位都置 1，只要查询时任一位为 0，就证明它从没被插入过——所以「说不在」100% 可信，可放心短路。
假阳性从哪来：不同元素的哈希位会共享/碰撞，某个从未插入的元素恰好 k 个位都被别人置过 1，就被误判为「可能在」。
参数三件套 m/n/k：位数组大小 m、预期元素数 n、哈希个数 k。给定 n 和目标误判率 p，m ≈ -n·ln p / (ln2)²、最优 k ≈ (m/n)·ln2——容量必须提前估准，n 超了误判率会飙升。
Redis 上三条实现路径：① 原生 SETBIT/GETBIT 手写（零依赖但要自己算 m/k、自己保证原子）；② RedisBloom 模块（BF.ADD/BF.EXISTS，官方、可扩展、省心）；③ Redisson RBloomFilter（Java 客户端封装，分布式共享，但固定容量不可扩容）。
致命短板：标准布隆过滤器不支持删除——清 0 会误伤共享该位的其他元素（引入假阴性）。要删除得换计数布隆过滤器（位换成计数器）或 布谷鸟过滤器 Cuckoo Filter（存指纹、支持删除、空间更省）。
容量未知用可扩展布隆过滤器（Scalable Bloom Filter）：容量满了自动追加一层新过滤器（RedisBloom 默认行为），代价是查询要逐层查、误判率按几何级数收敛。
落地要点：BF 放缓存前只负责「拦住必不存在」，放行的少量误判仍要靠空对象缓存兜底；无法删除 → 定期全量重建；上线前务必按真实基数估 m，别拍脑袋。
AdTech 实践：竞价链路用它挡刷子拿随机不存在 ID 的缓存穿透、做曝光/点击去重、拦作弊设备黑名单、判用户是否已见过某广告——都是「读极频繁、能容忍极低误判」的典型场景。

Open Table of contents

1. 原理：位数组 + k 个哈希函数
2. 数学：误判率与 m / n / k 怎么算
3. 方案一：用原生 bitmap 手写
4. 方案二：RedisBloom 模块（首选）
5. 方案三：Redisson RBloomFilter（Java 客户端）
6. 变体：删除难题与计数 / 布谷鸟过滤器
7. 可扩展布隆过滤器：容量未知怎么办
8. 落地缓存穿透与 AdTech 实践
- 8.1 挡在缓存前的「否决器」
- 8.2 AdTech 场景
参考

1. 原理：位数组 + k 个哈希函数

布隆过滤器的结构简单到极致：一个初始全 0 的位数组（bit array）+ k 个相互独立的哈希函数。

插入元素 x：用 k 个哈希算出 k 个下标 h1(x)…hk(x)，把这 k 个位全部置 1。
查询元素 y：同样算 k 个下标，只要有任意一位是 0，y 一定没被插入过（返回「不存在」）；若 k 位全是 1，y「可能存在」。

布隆过滤器原理：插入 user:42 时 3 个哈希把 3 个位置 1；查 user:99 命中一个 0 位 → 一定不存在（无假阴性）；查 user:7 恰好 3 位都为 1 但从未插入 → 可能存在（假阳性/误判）

插入置 k 位为 1；查询时任一位为 0 即「一定不存在」，k 位全 1 才「可能存在」。误判源于不同元素的位碰撞。

关键在这条不对称性：

绝无假阴性：只要 y 真被插入过，它的 k 个位必然都是 1，绝不会漏判成「不存在」。所以布隆过滤器说「不存在」时，100% 可信——这正是它能安全短路、挡住穿透的根本。
存在假阳性：y 从没插入过，但它的 k 个位恰好被别的元素分别置过 1，就会被误判成「可能存在」。误判率随插入量增加而上升。

所以布隆过滤器只适合「说不在就放心、说在就再核实」的场景——把它当「快速否决器」，而不是「精确集合」。

2. 数学：误判率与 m / n / k 怎么算

三个核心参数：

m：位数组的总位数（bit）；
n：预计插入的元素个数；
k：哈希函数个数。

插入 n 个元素后，某一位仍为 0 的概率是 (1 - 1/m)^(kn) ≈ e^(-kn/m)。于是误判率（k 位全 1）近似为：

p ≈ (1 - e^(-kn/m))^k

由此反推工程上最有用的两条公式——给定 n 和目标误判率 p：

最优位数     m ≈ -n · ln p / (ln 2)²
最优哈希数   k ≈ (m / n) · ln 2 ≈ -log2(p)

直觉记忆：每个元素约需 -1.44 · log2(p) 位。几组常用取值：

目标误判率 p	每元素位数 m/n	最优 k	1000 万元素占用
1% (0.01)	≈ 9.6 bit	7	≈ 11.4 MB
0.1% (0.001)	≈ 14.4 bit	10	≈ 17.1 MB
0.01% (0.0001)	≈ 19.2 bit	13	≈ 22.9 MB

两个要点：

误判率每降一个数量级，内存只线性微增——布隆过滤器的空间效率极高（存 1000 万 key 到 1% 误判仅 ~11 MB，比存原始 key 省一两个数量级）。
n 必须估准。公式是按「实际插入 = n」推的；一旦真实插入量远超预设 n，位数组被填得过满，误判率会迅速逼近 100%，过滤器直接失效。这是最常见的翻车点（见 §9）。

3. 方案一：用原生 bitmap 手写

Redis 的 String 天然是二进制位数组，SETBIT key offset 1 / GETBIT key offset 就能当位数组用，零额外依赖。核心是自己实现「k 个哈希 → k 个 offset」。

public class RedisBloomFilter {
    private final Jedis jedis;
    private final String key;
    private final long m;      // 位数组大小（bit）
    private final int k;       // 哈希个数

    // 用两个哈希线性组合模拟 k 个（Kirsch-Mitzenmacher：g_i = h1 + i*h2）
    private long[] offsets(String value) {
        long[] pos = new long[k];
        long h1 = MurmurHash.hash64(value, 0x9747b28c);
        long h2 = MurmurHash.hash64(value, 0xc6a4a793);
        for (int i = 0; i < k; i++) {
            pos[i] = Math.floorMod(h1 + (long) i * h2, m);
        }
        return pos;
    }

    public void add(String value) {
        for (long off : offsets(value)) jedis.setbit(key, off, true);
    }

    public boolean mightContain(String value) {
        for (long off : offsets(value)) {
            if (!jedis.getbit(key, off)) return false;  // 任一位为 0 → 一定不存在
        }
        return true;                                     // 全 1 → 可能存在
    }
}

工程注意：

哈希别真的算 k 次：用 Kirsch-Mitzenmacher 技巧，g_i(x) = h1(x) + i·h2(x)，两个哈希线性组合出 k 个下标，误判率几乎无损，省 CPU。
原子性：add 里的 k 次 SETBIT 不是原子的，并发写一般无害（都是置 1、幂等）；但「先查后写」这类复合逻辑要用 Lua 脚本打包成一次原子执行。
提前算好 m/k：按 §2 公式按真实基数算，别用默认值裸跑。
短板：手写版容量固定、不支持删除、不能扩容，且没有 RedisBloom 的可扩展/计数能力——适合简单、基数已知、依赖极简的场景。

4. 方案二：RedisBloom 模块（首选）

RedisBloom 是 Redis 官方的概率数据结构模块（Redis Stack 内置），把布隆过滤器做成一等命令，无需自己算 m/k、自己管位数组。

# 预建：容量 1000 万、误判率 0.1%（不建也会用默认值惰性创建）
BF.RESERVE ad:seen 0.001 10000000

BF.ADD    ad:seen  user:42          # 加一个，返回 1=新增 / 0=已存在
BF.MADD   ad:seen  user:43 user:44  # 批量加
BF.EXISTS ad:seen  user:99          # 查单个，返回 1=可能在 / 0=一定不在
BF.MEXISTS ad:seen user:7 user:8    # 批量查
BF.INFO   ad:seen                   # 看容量、已插入数、扩展次数等

BF.RESERVE 的两个关键参数：

error_rate：目标误判率（如 0.001），越低越省心但越占内存；
capacity：预期容量 n。超出后不会失效——RedisBloom 默认会自动追加一个新的子过滤器（即 §7 的可扩展布隆过滤器），保证误判率不崩，代价是内存增长与查询要逐层查。可用 EXPANSION 调扩展系数，或 NONSCALING 关掉自动扩展（满了直接报错）。

相比手写，RedisBloom 的优势：参数语义清晰、自动扩展、性能经过优化、还带同族的计数（CF.* 布谷鸟）与 Count-Min Sketch、Top-K 等。生产上除非不能装模块，否则优先用它。

5. 方案三：Redisson RBloomFilter（Java 客户端）

如果不想引入 RedisBloom 模块、又在 Java 栈，Redisson 用普通 Redis 命令在客户端实现了分布式布隆过滤器：

RBloomFilter<String> filter = redisson.getBloomFilter("ad:seen");
// 初始化：预期 1000 万、误判率 1%（底层据此算好 m、k）
filter.tryInit(10_000_000L, 0.01);

filter.add("user:42");
boolean maybe = filter.contains("user:99");  // false = 一定不存在

它把 m、k 算好后同样落在 Redis 的位图上，多节点共享同一份。关键限制：RBloomFilter 容量固定、不支持删除、也不能扩容——tryInit 时定死的 n 一旦超了，就只能重建一个更大的。所以 Redisson 版更适合基数可预估、且能接受「满了整体重建」的场景。

选型速记：能装模块 → RedisBloom（可扩展、功能全）；Java 且不想装模块 → Redisson（简单、固定容量）；依赖极简 / 要完全掌控 → 原生 bitmap 手写（§3）。

6. 变体：删除难题与计数 / 布谷鸟过滤器

标准布隆过滤器最大的软肋是不支持删除：你不能简单地把某元素的 k 个位清 0，因为这些位很可能被别的元素共享——清 0 会让那些元素被误判成「不存在」，即引入了假阴性，直接破坏了「说不在就可信」这条地基。

两种支持删除的变体：

① 计数布隆过滤器（Counting Bloom Filter）：把每个「位」换成一个小计数器（如 4 bit）。插入时对应位 +1，删除时 -1，查询时判断计数器是否 > 0。代价是内存放大数倍（1 位 → 4 位），且计数器可能溢出。

② 布谷鸟过滤器（Cuckoo Filter）：存元素的指纹（fingerprint）而非置位，每个元素有两个候选桶（布谷鸟哈希），插入时若桶满就「踢走」已有指纹到它的备用桶。它支持删除、在低误判率下空间效率优于布隆、且查询只需看两个桶。RedisBloom 直接提供：

CF.RESERVE ad:seen 10000000   # 布谷鸟过滤器
CF.ADD     ad:seen user:42
CF.EXISTS  ad:seen user:42     # 1=可能在 / 0=一定不在
CF.DEL     ad:seen user:42     # 支持删除！

标准布隆过滤器 vs 布谷鸟过滤器：布隆用位数组 + k 哈希置位、不支持删除；布谷鸟存指纹、每元素两个候选桶、支持删除且低误判率下更省空间

布隆置位、简单省内存但不能删；布谷鸟存指纹、支持删除、低误判率下更省空间，代价是接近满载时插入可能失败。

维度	标准布隆	计数布隆	布谷鸟 Cuckoo
支持删除	❌	✅	✅
空间效率	高	低（位→计数器）	高（低 FPP 下更优）
假阴性	无	无	无（删对元素时）
插入失败	不会	计数溢出	接近满载可能失败
RedisBloom 命令	`BF.*`	—（用 `CF` 代替）	`CF.*`

选型：不需要删除 → 标准布隆最省；需要删除 → 优先布谷鸟（比计数布隆更省）；能容忍「满了重建」的话，标准布隆 + 定期全量重建往往比引入删除更简单可靠。

7. 可扩展布隆过滤器：容量未知怎么办

§2 强调「n 必须估准」，但现实里基数常常预估不了（如持续增长的用户 ID）。可扩展布隆过滤器（Scalable Bloom Filter）的思路：当当前过滤器填满（达到目标误判率上限）时，追加一个更大的新子过滤器继续插入；查询时逐层查，任一层命中即「可能存在」。

误判率收敛：每层误判率按几何比例收窄（如 0.5×），整体误判率是各层之和，仍能被目标上界压住。
代价：层数越多，查询要查的层越多（延迟微增），内存也随之增长。
RedisBloom 默认就是这套：BF.RESERVE 的 capacity 超出后自动扩展，EXPANSION 控制新层的倍数，NONSCALING 可关闭。

所以基数不确定时，别自己拍一个大 n 硬扛，用可扩展布隆（或直接用 RedisBloom 默认扩展）更稳。

8. 落地缓存穿透与 AdTech 实践

8.1 挡在缓存前的「否决器」

布隆过滤器防缓存穿透的定位很清晰：放在缓存之前，只负责快速否决「必不存在」的 key，把恶意/无效请求挡在缓存和数据库之外。

布隆过滤器作为缓存穿透防线：请求先查布隆过滤器，不存在则直接返回 null 拦截（不打缓存/DB），可能存在才走缓存→miss→回源数据库；放行的少量误判由空对象缓存兜底

布隆过滤器前置拦住「必不存在」的 key，只放行「可能存在」的进缓存/DB；少量误判透过时，靠空对象短 TTL 兜底。

两条工程红线：

误判仍要兜底：被 BF 放行的少量假阳性 key（实际不存在）仍会打到 DB，所以 BF 必须和空对象缓存配合——查到空也缓存一个空标记（短 TTL），不能只靠 BF。
无法删除 → 定期重建：数据下线后 BF 仍会放行它（残留假阳性），影响不大（只是少挡一个）；但如果误判率随基数增长恶化，就需要周期性全量重建 BF（用最新全量 key 重灌一份，切换指针）。

8.2 AdTech 场景

广告竞价里布隆过滤器（或布谷鸟）是「读极频繁、能容忍极低误判」的天然战场：

场景	用法	为何合适
挡穿透	合法 `creativeId/campaignId` 全量预建 BF，竞价前先过滤	刷子拿随机不存在 ID 狂查时直接短路，保护 Redis/DB
曝光/点击去重	已处理的 `impressionId/requestId` 灌入 BF，重复事件命中即丢	计费/归因链路要去重，误判导致丢极少数事件可接受
作弊黑名单	作弊设备/IP 指纹放 BF，竞价前判命中即拒	黑名单基数大、判断要极快，误伤率极低可控
frequency cap 预判	「该用户是否见过该广告」先用 BF 快筛，命中再查精确计数	绝大多数「没见过」被 BF 快速放行，减少精确查询

这些场景的共性正是布隆过滤器的适用边界：判断存在性、要求极快、能容忍极低误判、且（多数）不需要删除。

参考

Redis 官方文档 · Bloom filter（RedisBloom）：https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/
Redis 官方文档 · Cuckoo filter：https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
Redisson Wiki · Bloom filter：https://github.com/redisson/redisson/wiki/6.-distributed-objects#68-bloom-filter
Bloom, B. H. (1970) · Space/Time Trade-offs in Hash Coding with Allowable Errors：https://dl.acm.org/doi/10.1145/362686.362692
Fan et al. · Cuckoo Filter: Practically Better Than Bloom：https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf