Redis布隆过滤器实战：从原理到代码，彻底搞懂缓存穿透

一份Redis准备清单里，布隆过滤器往往被排在不那么起眼的角落，标题里的427也是我笔记里的一串编号。几次复盘下来，我发现这个知识点极其擅长区分两种人：一种能从头把原理讲明白，另一种只是背住了“防止缓存穿透”六个字。这篇内容就是把后者补成前者的过程，从为什么需要它、位数组长度怎么算，到Redis里怎么落地，再到线上和面试经常出现的问题，一次说透。适合正在准备Redis相关面试的开发者，也适合那些已经写完布隆过滤器代码、却仍然说不清内存开销和误判率的人。

先说一个常见场景。你的业务里一定有一条链路：请求进来先查Redis，没命中就查数据库，查到结果再回填Redis。这套逻辑在正常数据上跑得很好，但有一种数据会让它非常难堪——数据库里压根不存在的记录。比如一个被删掉的商品ID，或者恶意遍历的一批随机用户ID。这些请求每一次都会穿透Redis直击数据库，而数据库每次都会老老实实查一遍后返回“没有”。如果流量被放大，数据库的压力会成倍增长，这就是缓存穿透。布隆过滤器就是为这种场景准备的工具，而且在Redis生态里特别顺手。

1. 缓存穿透到底在问什么：布隆过滤器为什么被放在Redis旁边

1.1 一个极端流量下的读取链路

先把链路拆干净。正常情况下，一个查询请求的路径是：请求到达后先查Redis，Redis里有数据就直接返回；Redis没有，就去数据库查询；数据库有结果，再回填Redis并返回。

问题在于“数据库里本就没有的数据”。这张记录在Redis里永远不会存在，因为压根没有可回填的值。如果只有一两个这样的请求，数据库无所谓。但线上真实情况往往不是一两个，而是同一批异常ID被脚本反复循环，或者攻击者故意把ID设计成数据库里不存在的形态，高频访问。数据库每条查询都在做无用功，连接数、慢查询、CPU和磁盘IO一起飙升，这时候再叠加正常流量，很容易直接把数据库打挂。

布隆过滤器解决的是入口拦截问题。它放在Redis查询之前，或者作为Redis内的一种特殊查询前置判断：先问过滤器“这个ID我见过吗”，如果答案是“肯定没见过”，那就不必再查Redis，更不必查数据库，直接返回不存在。这里的关键词是“肯定”。布隆过滤器的特点是：它说“不存在”，那基本可以确信不存在；它说“存在”，其实是“可能存在”，有一定的误判概率。所以它是一个过滤器，不是精确索引。

1.2 布隆过滤器的位置：前置过滤器而非缓存替代品

可以打个比方。一个餐厅门口有一份预约名单，保安只会做两个动作：看名字在不在名单上，然后放行或者劝返。名单上登记过的客人，保安一定放进去；不在名单上的客人，保安可能会因为他长得眼熟而放进去一次，但大多数没预约的人会被挡在外面。这份名单就是布隆过滤器，它不负责给客人安排座位，也不负责上菜。

放到技术架构里，布隆过滤器不是缓存本身，更不是数据库的替代品。它只回答一个布尔问题：“这个key可能被我之前添加过吗？” 得到“否”，就拦截；得到“是”，才继续走缓存和数据库的链路。真正的数据仍然存在Redis和数据库里。

这个定位很重要，很多面试者在讲布隆过滤器时容易把层次搞混，开口就是“用布隆过滤器替代缓存”，这明显是概念没理清。布隆过滤器没有存储数据的能力，它只有一串位标记，标记的是“哪些元素曾经来过”的痕迹。它配合Redis使用，是因为Redis提供了Bitmaps这种方便操作单个二进制位的数据结构，而且Redis本身足够快，可以把这个判断过程保持在亚毫秒级别。

从部署位置上看，布隆过滤器可以整体放在Redis外部的应用内存里，也可以直接放进Redis。放进Redis还有一个额外好处：多个应用实例共享同一个过滤器，不会出现每台机器各自维护一份、数据不一致的问题。这就是为什么Redis面试题里几乎一定会带一笔布隆过滤器，因为它和Redis在工程上确实是天然搭档。

2. 位数组面积计算：m、n、k和误判率p的数学账本

2.1 公式推导不玄学

先约定几个符号：n是预计要放入过滤器的元素数量，m是位数组长度，k是每个元素需要用到的哈希函数个数，p是期望的误判率。

布隆过滤器初始是一个全0的位数组。插入元素时，用k个哈希函数分别算出一个位置，把这些位置都置为1。查询时，同样算出k个位置，只要有一个位置是0，就判定这个元素肯定不存在；如果k个位置全是1，判定这个元素可能存在。

误判是怎么产生的？因为位数组有限，随着插入的元素越来越多，某些位置会被不同的元素重复置1。查询一个从未插入过的元素时，它的k个位置可能已经被其他元素全部填成了1，于是过滤器错误地认为它存在。

推导误判率不需要高深数学。插入一个元素时，某个特定位置没有被某个哈希函数选中的概率是 1 - 1/m。一个元素需要k次哈希，那么这个位置没被这个元素的k次哈希选中的概率是 (1 - 1/m)^k。插入n个元素后，这个位置仍然是0的概率约等于 e^(-kn/m)。反过来，这个位置被置为1的概率是 1 - e^(-kn/m)。对于一个不存在的元素，它需要k个位置全都被置为1才产生误判，所以误判率近似为：

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

这个公式说明了两个直觉正确的结论：位数组m越大，误判率越低；元素量n越大，位数组被填得越满，误判率越高。哈希函数数量k则是个平衡点，太多会让位数组被快速填满，太少则每个元素只覆盖少数几个位置，碰撞概率反而上升。

最优的k可以通过对公式求导得到：k = (m / n) * ln2。也就是说，每个元素平均占用 m/n 个位时，哈希函数数量取这个值的0.693倍左右最优。把这个k代回误判率公式，再整理一下，就能得到规划容量时最常用的式子：

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

如果你手边没有公式，记住结论也可以：误判率每降低一个数量级，位数组长度大约增加三分之一；哈希函数最优个数约等于 m/n 乘以0.7。

2.2 容量估算表

我按常用场景做了一张表，直接可以用：

如果你用HashSet或Redis的Set去存100万个UUID，每个UUID大约36字节，光原始内容就是34MB左右，还得加上对象头、指针、桶数组等开销，实际往往超过80MB甚至100MB。布隆过滤器把同一批数据压到1MB多一点，这就是位数组的威力。

这里有个操作习惯要养成：不管是用Redis的Bitmaps手写，还是用现成客户端，先把n和p确定下来，再算m和k，最后再写代码。不要拿到一个开源工具就把默认参数往上填，默认参数往往针对通用场景，不一定匹配你的业务量。

2.3 拍脑袋选参数的代价

最常犯的错误是把n估小了。比如业务规划100万注册用户，过滤器按100万容量设计，结果半年后用户量到了5000万。由于位数组被大量元素填充，误判率会从设计时的1%迅速劣化，最后可能出现相当比例的无效请求被放行，穿透问题卷土重来。更麻烦的是，标准布隆过滤器不能随意扩容，m一变，所有元素的哈希位置就全变了，旧位数组直接作废。

所以容量规划建议按未来一到三年峰值来估算，宁可偏大，不要偏小。多花一倍内存，换来的是误判率稳定和不需要频繁迁移重建。哈希函数数量k也要按公式来，不要为了省CPU刻意减小k。k太小，每个元素只标记三五个位置，不同元素之间的碰撞概率会明显上升；k太大，每个元素要计算更多次哈希，插入和查询耗时增加，同时位数组被更快填满。

如果条件允许，可以对上线的过滤器做一次“容量水位”监控。比较简单的做法是定期统计位数组中已经置为1的比例，当超过总位数的某个阈值，比如80%，就要准备扩容或重建了。这个比例可以反映出过滤器已经进入了高误判区间。

3. Redis里的三种落地形态：原生Bitmap、Redisson、RedisBloom

3.1 原生SETBIT/GETBIT手写实现

最通用的是用Redis的字符串键配合SETBIT和GETBIT操作，每个offset对应位数组里的一个二进制位。这样不依赖任何额外模块，任何Redis版本都能跑。

下面是一段简化版的Java实现思路：

public class RedisBloomFilter { private static final long BIT_SIZE = 9586000L; private static final int[] SEEDS = {3, 7, 11, 17, 23, 29, 37}; private static final int K = SEEDS.length; public void add(String key, String value) { for (int seed : SEEDS) { long offset = hash(value, seed) % BIT_SIZE; redisTemplate.opsForValue().setBit(key, offset, true); } } public boolean mightContain(String key, String value) { for (int seed : SEEDS) { long offset = hash(value, seed) % BIT_SIZE; Boolean bit = redisTemplate.opsForValue().getBit(key, offset); if (bit == null || !bit) { return false; } } return true; } private long hash(String value, int seed) { // 建议使用MurmurHash等分布较均匀的哈希，不要直接用String.hashCode return 0; } }

这里有几个细节值得留意。第一，不要直接用String.hashCode。它有负数，取模前需要处理；而且不同进程里字符串哈希的随机种子可能不同，在多实例环境下会引起灾难性的不一致。第二，offset要取模，否则超过Redis字符串长度时会报错。第三，Redis字符串最长512MB，换算成bit是2^32-1左右，如果你的位数组规模接近这个上限，就不能塞进单个key，要做分片。

如果对并发有要求，插入和查询之间存在时间差并不影响正确性，因为查询到的位置可能已被别的插入置1，只会略微推高误判，不会漏掉真实存在的元素。但如果你想保证“先确认不存在，再放行请求”这个动作是原子的，可以借助Lua脚本把几个SETBIT操作一次性提交。脚本本身很简单：遍历种子，逐个SETBIT，全部成功才返回。

3.2 Redisson的RBloomFilter配置

Java生态里使用Redisson非常省事，它已经封装好了布隆过滤器。基本用法是：

RBloomFilter<String> bloomFilter = redisson.getBloomFilter("bloom:user"); bloomFilter.tryInit(1000000L, 0.01); boolean added = bloomFilter.add("uid:12345"); boolean exists = bloomFilter.contains("uid:12345");

tryInit的第二个参数是期望误判率，不是哈希函数数量，这点很多人会看错。调用一次tryInit后，Redisson会把容量和哈希种子序列化到Redis里，之后每次应用重启再调用tryInit是幂等的，不会重建。但如果某次部署时改了参数，比如把容量从100万改成1000万，就可能出现过滤器内部参数和已存数据不匹配的问题，严重时会抛异常或重新初始化，导致旧数据全部失效。

所以生产环境里，布隆过滤器的配置参数最好放进配置中心，并且标注“一旦初始化，禁止随意修改”。如果确实需要扩容，建议采用双过滤器方案：新建一个新参数的过滤器，业务双写一段时间，再把读流量切换到新过滤器上。

Redisson适合不想折腾Redis模块的Java项目。缺点是它封装了很多细节，排错时你需要清楚底层还是Redis的字符串位图，别把它的分布式行为想象得太神秘。

3.3 RedisBloom模块：服务器端BF命令

如果Redis版本支持模块扩展，可以安装RedisBloom。它把布隆过滤器做成了服务器端命令，应用不用自己管理哈希函数和位图偏移，客户端代码会简洁很多。

常用命令：

# 创建过滤器，参数顺序是误判率、预计容量 BF.RESERVE bloom:user 0.001 1000000 # 添加元素 BF.ADD bloom:user uid:12345 # 批量添加 BF.MADD bloom:user uid:10001 uid:10002 # 查询 BF.EXISTS bloom:user uid:12345

使用BF.RESERVE有个好处是容量和误判率在一开始就固定下来了，避免直接用BF.ADD时Redis以默认参数创建过滤器，默认误判率和容量未必适合你的场景。RedisBloom内部已经优化了哈希计算，性能比在客户端手写要高一些，而且天然支持多命令原子性，不需要额外写Lua。

选型时可以按这张表来：

从我自己的使用经验看，最稳妥的其实是“原生Bitmap手写+Lua脚本”的组合。它没有额外模块依赖，出问题时每一环都能看到，不容易出现客户端封装造成的黑盒困惑。

4. 上线之后才暴露的边界问题：误判、删除、键管理

4.1 误判不是bug，是精度换内存的代价

布隆过滤器的误判方向是固定的：它只会把不存在的元素误判为可能存在，绝不会把已经存在的元素判为不存在。后者的代价太大，比如一个注册用户被过滤器判定为不存在，导致请求直接返回“非法用户”，这是不可接受的。前者则温和得多，最多是让一个本应该被拦截的请求穿透到数据库。

正因为这个特性，布隆过滤器很适合做“拒绝名单”而不是“白名单”。举个例子：判断一个URL是否已经被爬虫处理过，把已经处理过的URL放进过滤器。新URL如果被判为“可能存在”，多处理一次代价不大；旧URL不会被漏掉，不会被重复处理。反过来，如果你用它做“黑名单判断”，比如判断用户是否在封禁名单里，误判就会导致正常用户被错误拦截，这就很危险。

线上还有一个隐蔽问题：容量是静态的，数据是动态的。当初按1000万容量设计，实际塞进来3000万，误判率会明显上升。这时候不是改一个参数就能解决的，必须重建。重建的一般流程是：新建一个容量更大的过滤器，在写入侧同时向新旧两个过滤器写入，等旧过滤器的数据在新过滤器中全部补齐后，把读取侧切到新过滤器，再逐步删除旧过滤器。这个过程要求业务允许短时间内的双写开销，最好在低峰期操作。

4.2 删除需求：Counting Bloom Filter与替代方案

标准布隆过滤器最大的局限性就是不能删除。因为不同的元素可能映射到同一个位，你想删除一个元素，如果把它的k个位置都置0，很可能把其他元素的标记也一起抹掉，造成真实存在的元素被误判成不存在。

如果业务确实有删除需求，最简单的规避办法是不要删除过滤器里的元素，而是另建一个删除标记集合，比如Redis的Set或ZSet。先查布隆过滤器，如果判定存在，再去查删除标记集合，看看是不是已经被删掉。这套方案能精确处理“已删除”状态，代价是删除集合的长度不能太大。

如果删除非常频繁，删除集合会持续膨胀，可以改用计数型布隆过滤器。计数布隆过滤器的每个位不是一个布尔值，而是一个计数器。插入时对k个计数器加一，删除时对k个计数器减一。Redis原生的Bitmaps不支持计数，用Hash结构实现的话内存开销会明显上涨。这时候要权衡：是用内存换取精确删除，还是接受“数据只增不减”的现状。

还有一种思路是定期重建。把过滤器按时间窗口切片，比如一周一个过滤器，过期数据直接丢弃，而不是一条一条删除。很多URL去重和日志过滤场景就是这么设计的，简单而且稳定。

4.3 大key与倾斜：布隆过滤器也会被运维找上门

布隆过滤器看着省内存，但它最终会成为一个Redis大key。比如估算1000万元素、误判率1%时，位数组约11.4MB，这个大小在Redis里已经需要关注了。单key只占11MB本身问题不大，但Redis在持久化、主从复制、大key扫描时都会对这个value做整体处理，网络传输和内存拷贝的开销会被放大。

另外要注意，不要把语义不同的业务数据塞进同一个过滤器。有人图省事把所有ID都放进一个bit key里，后来想单独统计某个业务的数据量时，发现完全做不到，而且一个业务的误判会污染另一个业务的查询结果。正确的键命名格式建议是：

bloom:{业务域}:{功能}:{版本}

比如bloom:user:register:v1、bloom:content:url:v3。版本号尤其重要，只要调整了容量或哈希函数数量，版本号跟着变，就知道哪个数据集合对应哪个参数，不会混淆。

在Redis Cluster环境里，布隆过滤器按key哈希到某个槽位，所以不存在跨槽分布的问题。但要注意热key问题：如果某个过滤器的访问量特别大，所有请求都打在同一节点上，容易形成单点热点。业务侧可以把过滤器做分片，比如按用户ID取模分成多个key，分摊单个Redis节点的压力。

5. 面试官在八股背后真正想确认的三件事

5.1 布隆过滤器能替代缓存吗——错在哪

这是一个高频陷阱题。正确的理解是：布隆过滤器在前面挡掉“一定不存在的请求”，缓存仍然负责热数据的快速返回，数据库仍然负责兜底。它们三个是串行协作的关系，不是替代关系。

如果布隆过滤器判定一个key“可能存在”，那么这个请求仍然会继续查Redis。如果Redis有，直接返回；如果没有，再查数据库，查到后回填。如果数据库也不存在，说明这个key确实不存在，只是布隆过滤器误判了，这次请求穿透了，但被布隆过滤掉的无效请求才是大头。所以说布隆过滤器解决的是“大量不同key的穿透”，而不是“单个热点key的缓存失效”。后者需要的是热点识别、分布式锁或本地缓存。

面试时能说出“布隆过滤器只回答是否存在，不回答值是什么”，这句话基本就算过关。

5.2 对比空值缓存、分布式锁、分片布隆过滤器

面试中很容易被要求比较不同防穿透方案。一张表能讲清楚：

实际生产里，布隆过滤器和空值缓存经常一起用。布隆过滤器挡掉大部分不存在请求，剩余误判的请求如果确实查不到数据，再用短TTL空值缓存挡住一小段时间，两层叠加效果最好。

5.3 手写实现时容易被追问的细节

面试官如果让你手写一个布隆过滤器，或者让你讲一个具体实现，真正想听的往往不是你把代码背下来，而是下面这些细节：

第一，哈希函数怎么选。一个合格的布隆过滤器需要一个分布均匀、速度快的哈希函数，MurmurHash是常用选择。不要用String.hashCode，因为它可能返回负数，而且不是为分布式场景设计的。如果要生成k个独立哈希，可以先用一个主哈希算出一个64位结果，再按不同seed扰动派生出多个值，这样比调用k个完全不相关的哈希函数更便宜。

第二，为什么要有k个哈希位置。单个哈希函数产生的碰撞概率可能很高，多个位置同时被占满的概率会显著下降。每个元素的k个偏移量要尽量独立，这样才能逼近前面推导的误判率。

第三，offset必须对位数组长度取模。位数组是环形使用的，不然越界。

第四，要知道Redis单字符串512MB限制。如果位数组接近这个边界，就是设计了过大的过滤器，需要考虑拆分。这个数字是2^32 bit左右，并不是随便来的。

第五，初始化时如果key已经存在，参数是否一致。使用RedisBloom的BF.RESERVE时，如果key已存在且参数不同，会报错；Redisson的tryInit在参数变化时的行为也需要警惕。面试时能把这种工程细节说出来，比单纯背公式加分很多。

6. 我实际用下来的体会：布隆过滤器适合什么，不适合什么

6.1 适合与不适合场景

适合的场景有几个明显特征：数据量特别大、可以容忍少量误判、查询的主要目的是过滤“一定不存在”的元素。典型的有用户名和手机号注册时的唯一性预检查，先挡掉明显重复的请求；爬虫系统里的URL去重；内容推荐系统里的已读内容过滤；以及缓存穿透防护。

不适合的场景也同样清楚。凡是涉及资金、权限、安全强校验的地方，不能接受任何误判。比如支付黑名单、账号是否存在、订单是否有效，这些一旦被判错，代价远大于省下的那点数据库查询成本。如果一定要用，也得在布隆过滤器后面叠加一层精确校验，让判定为“可能存在”的元素重新走一次精确查询。

我自己踩过的一个坑是把用户的“注销状态”放进了布隆过滤器。过滤器的本意是挡掉注销用户的登录请求，结果因为误判，极小比例的未注销用户也被挡了一轮。虽然最终精确校验能救回来，但用户会多一次请求延迟，体验很差。后来改成用精确的Redis Set存放注销用户ID，数量不大，内存完全可控，反而更可靠。

6.2 一条值得养成的运维习惯

无论采用哪种落地形态，都要给布隆过滤器加监控。最简单的是记录已经插入的元素量，用这个数量去和初始容量比较，当超过初始容量的一定比例时报警。更进一步，可以估算当前位数组中1的占比，这个比例越高，误判率就越高，越需要准备扩容或重建。

扩容和重建不要等到线上误判已经影响了业务才做，那时候很被动。平时把重建流程写在代码里，或者写成运维脚本。大流量期间直接拿现成的脚本做双写切换，几分钟就能完成。

布隆过滤器真正吸引人的地方，是它用极低的内存回答了一个“存在性”问题，而且答案在“不存在”方向上极其可靠。不要神化它，也不要因为误判率就否定它。把它理解成一个粗粒度的前置闸门，和Redis、数据库配合起来，它就能在很小的代价下挡住大部分无效流量。把它当作精确的判据去用，它就会在最关键的时候给你一个很难查的坑。这个边界把握住了，它就能长期稳定地为你省内存、省开销。