title: 布隆过滤器把 Redis 撑到 3.2GB 那天：位数组、哈希个数和 3 个被算错的参数
tags: [布隆过滤器, Redis, 缓存穿透, Guava, Java]
category: 后端
一个「省内存」的方案，最后最费内存
我们做内容平台的推荐去重：用户看过的内容不再重复推。最初用的是 Redis Set，每个用户一个 key 存已读内容 ID。日活 800 万，人均日读 60 条，保留 30 天——算下来 Redis 直接爆掉。
于是换成布隆过滤器。方案评审时我信誓旦旦地说：「布隆过滤器一个用户几 KB 就够了，内存能省 90%。」
上线两周后，Redis 内存从 900MB 涨到3.2GB，比换之前的 Set 方案还多。
问题不在布隆过滤器，在我算错了参数。这篇把那次踩坑之后重新推导的公式、Guava 的源码实现、以及分布式场景的正确用法整理出来。环境是 Redis 6.2.6 + RedisBloom 2.2.6、Guava 31.0.1、JDK 11。
先把原理讲透，不然参数一定会算错
布隆过滤器的结构简单到一句话能说完：一个位数组 + k 个哈希函数。
- 插入元素：用 k 个哈希函数算出 k 个位置，把这些位置置 1。
- 查询元素：算出同样的 k 个位置，只要有一个是 0，元素一定不存在；全是 1，元素可能存在。
「可能存在」就是误判（false positive）的来源：别的元素把这些位置都置 1 了。
三个参数互相牵制：
- n：预计插入的元素数量
- p：可接受的误判率
- m：位数组长度（bit）
- k：哈希函数个数
公式是这两个：
m = -(n * ln p) / (ln 2)^2 k = (m / n) * ln 2代入几个常用值感受一下量级：
| 元素数 n | 误判率 p | 位数组 m | 内存 | 哈希个数 k |
|---|---|---|---|---|
| 100 万 | 1% | 958 万 bit | 1.14 MB | 7 |
| 100 万 | 0.1% | 1437 万 bit | 1.71 MB | 10 |
| 100 万 | 0.01% | 1916 万 bit | 2.28 MB | 13 |
| 1000 万 | 1% | 9585 万 bit | 11.4 MB | 7 |
关键观察：误判率每降低 10 倍，内存只增加约 44%，但哈希次数线性增长。这个非线性关系是布隆过滤器最有价值的性质——想要更准，付出的内存代价并不夸张，但 CPU 代价是实打实的。
我当时犯的错就在这张表的用法上：我按「全平台 8 亿条内容」算了一个过滤器的大小，得出 1.2GB，觉得可以接受。但实际方案是每个用户一个过滤器，800 万用户，就算每个只有 400 字节，光是 key 的开销和内存碎片就把 Redis 撑爆了。
Guava 的实现：细节比公式更有意思
单机场景 Guava 的BloomFilter够用，它的实现有几处很值得学：
public static <T> BloomFilter<T> create( Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) { checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions); checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp); checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp); if (expectedInsertions == 0) { expectedInsertions = 1; } // 按公式算位数组长度和哈希个数 long numBits = optimalNumOfBits(expectedInsertions, fpp); int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits); try { return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy); } catch (IllegalArgumentException e) { throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e); } } static long optimalNumOfBits(long n, double p) { if (p == 0) { p = Double.MIN_VALUE; } return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } static int optimalNumOfHashFunctions(long n, long m) { // 至少 1 个哈希函数 return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); }真正的巧思在哈希计算上：
// BloomFilterStrategies.MURMUR128_MITZ_64 public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) { long bitSize = bits.bitSize(); byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal(); long hash1 = lowerEight(bytes); long hash2 = upperEight(bytes); boolean bitsChanged = false; long combinedHash = hash1; for (int i = 0; i < numHashFunctions; i++) { // 只算一次 128 位哈希，切成两半后线性组合出 k 个哈希值 bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize); combinedHash += hash2; } return bitsChanged; }这段代码的要点：
- 只算一次 murmur3_128 哈希，然后把 128 位切成两个 64 位，用
h1 + i * h2的线性组合模拟出 k 个独立哈希。这是 Kirsch-Mitzenmacher 优化，论文证明了误判率几乎不受影响，但把 k 次哈希计算降成了 1 次。k=10 时这是 10 倍的 CPU 节省。 combinedHash & Long.MAX_VALUE是为了去掉符号位——负数取模会得到负下标。这个细节自己实现时极易漏掉。LockFreeBitArray内部用AtomicLongArray+ CAS，所以 Guava 的 BloomFilter 是线程安全的。很多人以为它不是，白加了一层锁。
用法：
@Component public class LocalDedupFilter { // 预计 1000 万元素，误判率 0.1%，占用约 1.7MB private final BloomFilter<Long> filter = BloomFilter.create( Funnels.longFunnel(), 10_000_000L, 0.001); public boolean mightContain(Long contentId) { return filter.mightContain(contentId); } public void add(Long contentId) { filter.put(contentId); } /** 监控用：估算已插入元素数，超出预期时误判率会失控 */ public long approximateCount() { return filter.approximateElementCount(); } }第 16 行的approximateElementCount()是我强烈建议接到监控上的方法。布隆过滤器最危险的失效方式不是报错，而是悄悄地误判率飙升。实际插入量超过预期 n 的两倍时，0.1% 的误判率会退化到接近 5%，而系统不会给你任何提示。
我们的三个参数错误
回到那次事故，复盘下来一共三个错：
错误一：粒度选错了。每个用户一个过滤器，意味着 800 万个 Redis key。即使每个只存 400 字节，key 本身的元数据开销（Redis 每个 key 约 50-90 字节额外开销）加起来就是 500MB+。而且 800 万个小对象带来的内存碎片率一度到 1.4。
改法：改成按用户分桶，1024 个桶，每个桶一个大的布隆过滤器，用户 ID 取模决定进哪个桶。key 数量从 800 万降到 1024，碎片问题消失。代价是同桶用户之间会互相干扰，误判率需要重新按「桶内总元素数」计算。
错误二：没有考虑过期。布隆过滤器不支持删除。我想的是「30 天后重建」，但没设计重建流程，结果过滤器只增不减，位数组饱和度越来越高。
改法：双缓冲轮转。同时维护两个过滤器 A 和 B，写入时两个都写，查询只查 A；每 15 天把 A 丢弃、B 变成 A、新建一个 B。这样任意时刻的数据覆盖窗口在 15-30 天之间，而且不会有「重建瞬间全部失效」的空窗。
@Component public class RotatingBloomFilter { private static final String KEY_PREFIX = "bf:read:"; private final StringRedisTemplate redis; /** 当前活跃过滤器的序号，随时间轮转 */ private int currentSlot() { // 每 15 天换一个 slot，只在 0/1 之间轮转 return (int) ((System.currentTimeMillis() / (15L * 24 * 3600 * 1000)) % 2); } public void add(long userId, long contentId) { int slot = currentSlot(); String bucket = String.valueOf(userId % 1024); // 双写：当前 slot 和下一个 slot 都写，保证轮转时不丢数据 redis.execute((RedisCallback<Object>) conn -> { conn.execute("BF.ADD", key(slot, bucket), member(userId, contentId)); conn.execute("BF.ADD", key(1 - slot, bucket), member(userId, contentId)); return null; }); } public boolean hasRead(long userId, long contentId) { // 只查当前 slot Object r = redis.execute((RedisCallback<Object>) conn -> conn.execute("BF.EXISTS", key(currentSlot(), String.valueOf(userId % 1024)), member(userId, contentId))); return Long.valueOf(1L).equals(r); } private byte[] key(int slot, String bucket) { return (KEY_PREFIX + slot + ":" + bucket).getBytes(StandardCharsets.UTF_8); } private byte[] member(long userId, long contentId) { // 同桶内不同用户要能区分，所以 member 必须带 userId return (userId + "_" + contentId).getBytes(StandardCharsets.UTF_8); } }第 40 行那个细节是我们第二次踩坑才补上的：分桶之后 member 如果只用contentId，同一个桶里的所有用户会共享去重结果——用户 A 看过的内容，用户 B 也被判定为已读。上线后第二天就有人反馈「推荐内容变少了」，查了半天才发现是这个。
错误三：误判方向没想清楚。布隆过滤器的误判永远是「说存在但实际不存在」，绝不会「说不存在但实际存在」。在去重场景，这意味着可能把用户没看过的内容误判为已看，从而少推。这个方向是可以接受的。
但如果反过来用——比如用布隆过滤器判断「这个订单号是否已处理过」来做幂等，误判就会导致正常订单被当成重复而丢弃，这是不可接受的。布隆过滤器只能用在「误判可容忍」或者「误判后有兜底查询」的场景，用它做强一致的幂等判断是错的。
RedisBloom 和自己用 SETBIT 实现的对比
| 方案 | 优点 | 缺点 | 我的选择 |
|---|---|---|---|
| Guava 本地 | 无网络开销，纳秒级 | 多实例不共享，重启丢失 | 一级过滤 |
| Redis SETBIT 自实现 | 无需插件，可控 | 多次网络往返或需 Lua，易出错 | 不推荐 |
| RedisBloom 插件 | 一条命令搞定，支持自动扩容 | 需要装模块，部分云 Redis 不支持 | 首选 |
| Cuckoo Filter | 支持删除，空间效率略优 | 插入可能失败，实现复杂 | 需要删除时用 |
RedisBloom 的BF.RESERVE一定要显式调用，不要依赖BF.ADD的自动创建：
BF.RESERVE bf:read:0:512 0.001 500000 EXPANSION 2三个参数分别是误判率、初始容量、扩容倍数。不显式创建的话，RedisBloom 会用默认的 0.01 误判率和 100 的初始容量，随后靠 scaling 不断加层——每加一层，查询就要多查一层，性能线性下降。我们有个 key 因为忘了 RESERVE，跑了一个月之后叠了 11 层，BF.EXISTS的耗时从 0.2ms 涨到 2.8ms。
修复后的数据
- Redis 内存：3.2GB →420MB（分桶 + 双缓冲轮转 + 显式 RESERVE）。
- key 数量：800 万 → 2048（1024 桶 × 2 个 slot）。
- 内存碎片率：1.42 → 1.06。
BF.EXISTSP99：2.8ms → 0.35ms。- 实测误判率：抽样 10 万次查询比对真实 Set，误判 118 次，约 0.118%，与设定的 0.1% 基本吻合。
- 一级本地过滤（Guava，缓存热门内容 ID）拦掉了约 34% 的 Redis 查询。
我的判断
布隆过滤器是个目的性极强的工具，它只解决一件事：用可控的错误率换取巨大的空间节省。用之前先回答三个问题：
- 误判发生时，业务能接受吗？接受不了就别用，或者必须设计兜底查询。
- 元素总量的上界能估准吗？估不准就得用支持扩容的实现（RedisBloom）或者做轮转，否则误判率会失控且无声。
- 需要删除吗？需要就直接上 Cuckoo Filter，别指望用 Counting Bloom Filter 打补丁——计数器占的空间通常是 4 倍起，优势就没了。
我不建议把布隆过滤器当成缓存穿透的唯一防线。它防的是「查询一个根本不存在的 ID」这种情况，对于「ID 存在但缓存刚过期」的击穿完全无效。穿透用布隆过滤器 + 空值缓存，击穿用互斥锁或逻辑过期，雪崩用随机 TTL，三件事三种药，混为一谈的方案基本都会在某个环节漏。
最后一个实用建议：把approximateElementCount或 RedisBloom 的BF.INFO接到监控告警上。布隆过滤器不会主动告诉你它失效了，只有你自己盯着饱和度。
思考题
如果两个布隆过滤器 A 和 B 的位数组长度和哈希函数完全相同，把它们的位数组按位「或」起来得到 C。C 是 A 和 B 的并集吗？误判率会怎么变？
那如果按位「与」呢，得到的是交集吗？
提示：Guava 的BloomFilter提供了putAll但没有提供and，这本身就是答案的一部分。
你在什么场景用过布隆过滤器？误判有没有真的坑到你？评论区聊聊。
