★ FEATURED ARTICLE 一份Redis准备清单里布隆过滤器往往被排在不那么起眼的角落标题里的427也是我笔记里的一串编号。几次复盘下来我发现这个知识点极其擅长区分两种人一种能从头把原理讲明白另一种只是背住了“防止缓存穿透”六个字。这篇内容就是把后者补成前者的过程从为什么需要它、位数组长度怎么算到Redis里怎么落地再到线上和面试经常出现的问题一次说透。适合正在准备Redis相关面试的开发者也适合那些已经写完布隆过滤器代码、却仍然说不清内存开销和误判率的人。先说一个常见场景。你的业务里一定有一条链路请求进来先查Redis没命中就查数据库查到结果再回填Redis。这套逻辑在正常数据上跑得很好但有一种数据会让它非常难堪——数据库里压根不存在的记录。比如一个被删掉的商品ID或者恶意遍历的一批随机用户ID。这些请求每一次都会穿透Redis直击数据库而数据库每次都会老老实实查一遍后返回“没有”。如果流量被放大数据库的压力会成倍增长这就是缓存穿透。布隆过滤器就是为这种场景准备的工具而且在Redis生态里特别顺手。1. 缓存穿透到底在问什么布隆过滤器为什么被放在Redis旁边1.1 一个极端流量下的读取链路先把链路拆干净。正常情况下一个查询请求的路径是请求到达后先查RedisRedis里有数据就直接返回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 容量估算表我按常用场景做了一张表直接可以用预计元素量 n目标误判率 p位数组长度 m实际内存最优哈希数 k100万1%约958万bit约1.14MB7100万0.1%约1437万bit约1.71MB101000万1%约9585万bit约11.42MB75000万1%约4.79亿bit约57.11MB7如果你用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、RedisBloom3.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非常省事它已经封装好了布隆过滤器。基本用法是RBloomFilterString 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手写不依赖模块逻辑可控需要自己实现哈希和参数管理删除困难不想装模块、需要完全掌控细节Redisson封装API简单内存开销小参数改动风险大调试需要看底层Java项目快速集成RedisBloom模块服务端指令性能好需要安装和管理模块Redis运维权限充足追求性能和简洁从我自己的使用经验看最稳妥的其实是“原生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 对比空值缓存、分布式锁、分片布隆过滤器面试中很容易被要求比较不同防穿透方案。一张表能讲清楚方案核心思路优点缺点空值缓存DB查询结果为空时把key缓存为null并设置短TTL实现简单精确恶意攻击换随机ID时缓存堆积严重防不住大规模遍历分布式锁只让一个请求回源DB其余等待能避免同一key的并发击穿对大量不同key的穿透无效且有锁等待开销布隆过滤器预先判定key是否可能存在内存极省查询复杂度O(k)能防不同key有误判不支持删除需要容量规划分片布隆过滤器拆成多个小过滤器分片重建缓解大key和热点管理和运维复杂度上升实际生产里布隆过滤器和空值缓存经常一起用。布隆过滤器挡掉大部分不存在请求剩余误判的请求如果确实查不到数据再用短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、数据库配合起来它就能在很小的代价下挡住大部分无效流量。把它当作精确的判据去用它就会在最关键的时候给你一个很难查的坑。这个边界把握住了它就能长期稳定地为你省内存、省开销。
阅读完成 · 觉得有帮助？
