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位数组长度bitk哈希函数个数公式是这两个m -(n * ln p) / (ln 2)^2 k (m / n) * ln 2代入几个常用值感受一下量级元素数 n误判率 p位数组 m内存哈希个数 k100 万1%958 万 bit1.14 MB7100 万0.1%1437 万 bit1.71 MB10100 万0.01%1916 万 bit2.28 MB131000 万1%9585 万 bit11.4 MB7关键观察误判率每降低 10 倍内存只增加约 44%但哈希次数线性增长。这个非线性关系是布隆过滤器最有价值的性质——想要更准付出的内存代价并不夸张但 CPU 代价是实打实的。我当时犯的错就在这张表的用法上我按「全平台 8 亿条内容」算了一个过滤器的大小得出 1.2GB觉得可以接受。但实际方案是每个用户一个过滤器800 万用户就算每个只有 400 字节光是 key 的开销和内存碎片就把 Redis 撑爆了。Guava 的实现细节比公式更有意思单机场景 Guava 的BloomFilter够用它的实现有几处很值得学public static T BloomFilterT 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 BloomFilterT(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 次。k10 时这是 10 倍的 CPU 节省。combinedHash Long.MAX_VALUE是为了去掉符号位——负数取模会得到负下标。这个细节自己实现时极易漏掉。LockFreeBitArray内部用AtomicLongArray CAS所以 Guava 的 BloomFilter 是线程安全的。很多人以为它不是白加了一层锁。用法Component public class LocalDedupFilter { // 预计 1000 万元素误判率 0.1%占用约 1.7MB private final BloomFilterLong 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((RedisCallbackObject) 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((RedisCallbackObject) 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 万 → 20481024 桶 × 2 个 slot。内存碎片率1.42 → 1.06。BF.EXISTSP992.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这本身就是答案的一部分。你在什么场景用过布隆过滤器误判有没有真的坑到你评论区聊聊。