布隆过滤器防缓存穿透，位数组大小和哈希函数个数不是你拍脑袋定的

2026年08月05日 后端架构

布隆过滤器好不好用，关键看两个数字：位数组开多大、哈希函数用几个。这两个值算对了，过滤器才能真正拦住穿透、控制误判；算错了，要么内存白花，要么误判率飙到没法用。

下面直接拆解：从业务数据量反推参数，到实际代码落地，再到线上调整的坑，全流程走一遍。

先理解误判率公式，这是所有计算的起点

布隆过滤器的误判率公式长这样：

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

其中 k 是哈希函数个数，n 是预估要插入的元素数量，m 是位数组大小（bit 数），p 就是误判率。

这个公式直观解释：插入 n 个元素后，位数组中某一位仍然为 0 的概率是 e^(-kn/m)，一个不在集合中的元素被 k 个哈希函数都命中已置 1 的位，概率就是那个公式。

但实战中我们不会直接解这个方程，而是用它推导出的两个工程公式。

从预期数据量和误判率反推位数组大小

给定 n（预估数据量）和 p（你能接受的误判率），m 的最优计算公式是：

m = -n * ln(p) / (ln(2)^2)

ln(2)^2 约等于 0.48，所以很多人会记一个近似版本：m ≈ -n * ln(p) / 0.48。

举个例子：假设你要缓存 1000 万条商品 ID，允许误判率 1%（0.01），那么：

m = -10000000 * ln(0.01) / 0.48
  = -10000000 * (-4.605) / 0.48
  = 46050000 / 0.48
  ≈ 95,937,500 bit

换算成 MB：约 11.4 MB。这个值就是你至少需要开辟的位数组大小。如果误判率要求更严格，比如 0.1%，m 会涨到约 14.4 MB——看起来没多多少，因为对数关系决定了 p 每缩小一个数量级，m 只是线性增长。

实际分配时要注意两点：一是位数组大小通常取一个便于内存对齐的值，比如向上凑整到 2 的幂次或 8 的倍数；二是很多布隆过滤器实现用的是 Redis 的 Bitmap，Redis 的字符串最大 512 MB，单个位数组别超过这个限制，数据量大就分片。

哈希函数个数也不是越多越好

最优哈希函数个数 k 的计算公式：

k = (m/n) * ln(2)

ln(2) 约等于 0.693。继续用上面的例子：m ≈ 95,937,500，n = 10,000,000，那么：

k = (95937500 / 10000000) * 0.693 ≈ 6.64

取整就是 7 个哈希函数。

注意：k 必须是整数，向上还是向下取整？严格来说要比较一下 k=6 和 k=7 时的实际误判率，选更接近目标的那个。但实践中差一个哈希函数对误判率的影响在 10% 以内，通常直接四舍五入就够用了。

很多人直觉上觉得哈希函数越多越准，其实不然。k 超过最优值后，位数组被填充得太密，反而增加误判。你可以验证一下：同样的 m 和 n，k=10 时的误判率比 k=7 要高。

落地到代码：用 Guava 或 Redisson 算参数

Google Guava 的 BloomFilter 类提供了静态方法 create，你只需要传入预期插入量和误判率，它会自动算 m 和 k：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(Charset.defaultCharset()),
    10_000_000,  // 预期插入 1000 万条
    0.01         // 误判率 1%
);

Guava 内部实现就是按照上面的公式反推的，源码在 BloomFilter.optimalNumOfBits 和 optimalNumOfHashFunctions 里，你可以直接点进去看。

如果用的是 Redis 布隆过滤器模块（RedisBloom），初始化命令同样需要指定误判率：

BF.RESERVE myfilter 0.01 10000000

RedisBloom 内部会按公式自动创建合适大小的 Bitmap，你不需要手动算 m 和 k。但如果你的 Redis 版本低于 4.0 或者没用 RedisBloom 模块，而是自己拿 Bitmap 实现，那就得按上面的公式手动分配。

自己实现时，哈希函数怎么选

双哈希函数技巧可以生成任意数量的哈希函数，不需要真的搞 7 个不同的哈希算法：

long hash1 = MurmurHash3.hash64(data);
long hash2 = FnvHash.hash64(data);

for (int i = 0; i < k; i++) {
    long combinedHash = hash1 + i * hash2;
    int index = (int) (combinedHash % m);
    // 将位数组中 index 位置为 1
}

这个技巧来自 Kirsch-Mitzenmacker 的论文，数学上等价于使用 k 个独立哈希函数。Guava 的布隆过滤器也是这样实现的，你可以看 BloomFilterStrategies.MURMUR128_MITZ_32 的源码。

关键点：hash1 和 hash2 必须是高质量的 64 位哈希，不要用 Object.hashCode() 这种碰撞率高的东西。MurmurHash3 和 FNV-1a 是常见选择。

线上跑起来之后，参数要不要调

布隆过滤器一旦初始化，m 和 k 就固定了。但你的数据量 n 是预估的，实际可能增长。如果实际插入量远超预估，误判率会上升——因为公式里的 n 变大了，m 没变。

应对方法：

  1. 预估时留一倍余量：比如预估 1000 万，按 2000 万算 m。内存开销翻倍，但对大多数场景 20~30 MB 完全可接受。
  2. 定期重建：如果布隆过滤器是用来防缓存穿透的，可以在业务低峰期根据当前实际数据量重建一个新的过滤器，然后热切换。
  3. 分层布隆过滤器：插入量实在太大时，按时间或数据范围分片，比如每个月一个过滤器，查询时从最新的开始查。

重建时有一个容易踩的坑：你必须在重建完成前保留旧过滤器继续服务，否则重建期间的查询会直接穿透到数据库。做法是先建一个新的 Bitmap，把数据全量灌进去，然后一把切换 Redis 的 key 引用。这个过程可以用一个临时 key，比如 bloom:filter:new，灌完后 RENAME 成正式 key，Redis 的 RENAME 是原子操作。

实际案例：电商 SKU 缓存穿透防护

拿一个真实场景说：某电商平台有 800 万个 SKU，缓存层用 Redis，数据库扛不住恶意查询不存在的 SKU ID。布隆过滤器放在缓存前，所有查询先过过滤器。

参数计算：n 取 1000 万（留了余量），p 取 0.001（千分之一误判率）。按公式算 m ≈ 14.4 MB，k ≈ 10。

部署时过滤器加载全量 SKU ID，内存占用 14.4 MB 几乎忽略不计。误判率千分之一意味着每 1000 次查询不存在的 SKU，有 1 次会穿透到数据库——这个量级数据库完全扛得住。上线后缓存穿透量从每天 200 万次降到 2000 次左右，效果直接。

有人会问：千分之一误判率意味着正常请求也有概率被误判为“不存在”吗？不会。布隆过滤器的误判是单向的：不存在的一定不会被判为存在，但存在的有极小概率被判为不存在。所以在这个场景里，正常存在的 SKU 不会被拦，只有不存在的 SKU 有千分之一概率漏过去。

常见问题

布隆过滤器能不能删除元素？

标准布隆过滤器不支持删除。因为多个元素可能共享同一个位，把某一位从 1 改成 0 可能导致其他元素被误删。如果需要删除，用计数布隆过滤器（Counting Bloom Filter），把每一位扩展成一个计数器，删除时计数器减 1。代价是内存占用翻几倍，具体看计数器用几位。

误判率设多少合适？

没有统一答案，取决于你的数据库能承受多少额外查询。一般缓存穿透场景设 1% 或 0.1% 就够，因为布隆过滤器已经拦截了 99% 以上的无效请求，剩下的量数据库完全能扛。如果你做的是黑名单过滤、反垃圾这种对误判极度敏感的场景，可能需要 0.001% 甚至更低，但内存会相应增大。

为什么我按公式算出来的 m 和 Guava 自动算的不一样？

Guava 的实现在 optimalNumOfBits 里对 m 做了向上取整到 64 的倍数，optimalNumOfHashFunctions 里对 k 做了四舍五入。你手算的时候如果没做这两个步骤，结果会有微小偏差。另外 Guava 内部用的是 Math.log(2) 和 Math.log(p)，浮点精度也会带来一点差异，不影响实际使用。

布隆过滤器的位数组用什么数据结构存？

本地内存用 byte[] 或 long[] 数组，按位操作。Redis 里没有原生的位数组类型，但可以用 String 类型的 SETBIT 和 GETBIT 命令操作，一个 String 最大 512 MB，足够存 40 多亿位。分布式场景下 Redis 的 Bitmap 是最常见的存储方式，单机几十万 QPS 无压力。

#参数计算 #布隆过滤器 #缓存穿透 #误判率