先说一个我印象特别深的场景。某个深夜值班监控屏上数据库的QPS曲线突然拉成一条直线连接池排队数肉眼可见地涨接口超时率从 0 直接跳到百分之十几。当时第一反应是流量突增结果把网关日志翻了一遍发现同一批根本不存在的商品ID正以每秒几千次的频率涌进来。那批ID在缓存里没有在数据库里也没有但每个请求都老老实实打到数据库走了一遍。这就是缓存穿透处理完以后我把布隆过滤器正式引入了缓存链路之后同类问题再也没在深夜骚扰过我。布隆过滤器这个名字听起来像某种实验室装置其实原理简单得让人意外用一个位数组和几个哈希函数就能在占用极小内存的前提下回答某个元素一定不存在或者可能存在。这篇文章把三件事讲透为什么缓存穿透会把你数据库拖垮布隆过滤器凭什么用十几KB就把上百万数据挡在外面以及真正落地到缓存链路时有哪些坑必须提前知道。适合正在维护高并发缓存系统的人也适合面试前想把这个高频考点彻底搞懂的开发者。1. 缓存穿透的现场还原数据库濒临崩溃的一天1.1 穿透的本质缓存层形同虚设先定义一下什么是缓存穿透。正常的高并发查询链路是先查缓存、缓存没命中再查数据库、数据库查到后回填缓存。比如查一个订单详情第一次来缓存里没有去数据库里查到写进缓存后续同样的请求就直接命中缓存。这套机制能扛住高并发靠的是缓存把大部分重复请求拦在数据库外面。但如果查询的目标在数据库里压根不存在情况就完全变了。每次请求来缓存里没有去数据库查数据库也没有这个结果没法回填到缓存里——因为一个空往往不值得缓存或者根本不知道该拿它怎么办。于是这个数据永远不会在缓存里出现每次请求都穿透缓存直达数据库。我用快递柜类比过很多次正常流程是柜子里有包裹就直接取柜子没有就去仓库取取完再把包裹放进柜子穿透请求就像取一个根本不存在的包裹仓库也找不到问的人还特别多每个人都要去仓库里翻一遍。一个人问没什么一万个人同时来问仓库就乱套了。实际业务里最常见的穿透源有三种查询已删除的数据比如下架的商品、注销的用户、过期的优惠券查询非法构造的ID比如循环拼接一堆不存在的订单号正常业务中可能有但暂时没有的数据比如还没生成的报表。这几类请求单独看都不起眼但叠加上恶意循环访问效果就变成数据库每秒收到几万个无效查询。数据库的优势是存储和处理复杂关系不是无脑应付这种垃圾流量打满连接池以后连正常业务查询都会被拖死。1.2 常见应对方案和它们的边界缓存穿透不是只有布隆过滤器能解决业内先后折腾过好几种方案各有适用场景我直接把它们的优缺点摆出来对比。方案实现思路优点局限缓存空值数据库查不到就缓存一个空占位设置短TTL实现简单改动小恶意攻击者可以造出海量不同key空值占满缓存TTL到期后还会有少量穿透接口层校验在网关或Controller层拦截非法ID挡住格式明显不合法、超范围的参数挡不住存在格式合法但库里确实没有的数据互斥锁同一个key只放一个请求进数据库其余等待能削峰减少重复查询解决不了大量不同key都不存在的情况布隆过滤器在缓存前加一道存在性判断不存在的直接短路内存占用极小速度快能挡住几乎所有不存在请求存在少量误判且标准版不支持删除我自己的经验缓存空值适合偶尔有穿透的业务接口校验只能作为前置检查真正要在高并发场景下根治大量不存在数据打穿缓存的问题布隆过滤器是目前性价比最高的方案。这也是为什么它几乎成了缓存穿透问题的标准答案——内存省到可以忽略查询反而更快因为它连缓存都不查了直接短路。2. 布隆过滤器原理拆解位数组加哈希函数就够了2.1 一个极简的存在性判断题模型布隆过滤器的核心数据结构就是一个位数组初始全部为0加上k个相互独立的哈希函数。整个模型只做两件事插入和查询。插入一个元素时用k个哈希函数分别对元素算出一个位置然后把位数组上这k个位置全部置为1。查询一个元素是否存在时同样算k个位置然后检查这k个位置是否全为1只要有一个位置是0说明这个元素一定没有被插入过如果全部是1说明这个元素可能存在。我举个例子。假设位数组长度是16用3个哈希函数。现在插入alice3个哈希函数分别算出位置2、5、13把这三位置1。接着插入bob算出位置5、9、11置1。此时查询carl算出位置2、7、11其中位置7是0于是立刻断定carl不存在。这个判断是绝对正确的因为carl如果真的被插入过位置7必然已经是1。如果查询dave算出位置5、9、13全部是1于是我们说dave可能存在。注意这里不能肯定它一定存在因为这三个位置可能是alice和bob插入时各自置1后碰巧覆盖出来的。这就是布隆过滤器最核心的性质存在性判断是有误判的但误判方向是单向的——一定不会漏报只可能误报。2.2 为什么不存数据本身也能判断存在性很多人第一次接触布隆过滤器时会有一个疑问你不存原始数据怎么知道某个元素在不在答案是不需要知道原始数据只需要知道痕迹。位数组上的1就是元素留下的痕迹。一个元素进来它在位数组上烙下k个印记查询时就看这个元素对应的k个印记是否都在。这个过程完全不关心元素本身的内容只关心它算出来的那k个位置。这种做法最大的好处是省内存。假设有1000万个用户ID每个ID按20个字节存成字符串就要接近200MB如果要把这些ID全部加载到内存里做Set内存成本相当可观。但用布隆过滤器按1%误判率设计大约只需要9585万位也就是11.4MB左右而且这个大小和ID内容无关哪怕你是100字节的长指纹串也还是11.4MB。内存占用差了将近20倍这就是内存救星这个说法的来历。在高并发服务里内存是寸土寸金的用几百MB去缓存全量ID列表来抗穿透很多团队根本舍不得用11MB换个超低误判率几乎所有人都能接受。当然代价也有你不能从一个布隆过滤器里取出原始数据也不知道某个元素被插入过多少次更没法单独删除一个元素。所以它只适合做存在性判断这种特定场景不适合做完整存储。2.3 布隆过滤器为什么不怕哈希碰撞哈希碰撞是个绕不开的话题。两个不同的元素可能算出同一个位置把同一个位置置1。这不就会乱吗关键在于一个元素的值是由k个位置共同决定的不是只靠一个位置。单个位置被碰撞影响的只是这一个印记只有当查询时k个位置全部恰好都被其他元素置为了1才会出现误判。数学上可以算一下单次哈希碰撞导致某个位置被误置1的概率在均匀散列下约等于位数组的填充率大概在50%左右最优设计下但k个位置同时被错误覆盖的概率会随着k增大指数级下降。这就是多个哈希函数存在的意义——用k个独立的证据共同投票让巧合同时发生的概率降到业务可接受的水平。也正因为这个特性布隆过滤器对哈希函数的选择有讲究。生产环境一般用MurmurHash、CityHash这类非密码学哈希它们足够快散列足够均匀。不建议用SHA系列做这件事不是因为不安全而是因为慢——布隆过滤器的核心优势就是快加解密级别的哈希一次算几百纳秒在高频路径上完全是浪费。实现时选快且均匀的哈希别选安全但慢的哈希。3. 误判率的数学账参数决定了命运3.1 三个核心参数n、m、k用布隆过滤器之前必须先理解三个参数n预期要插入的元素数量m位数组的长度单位是位k哈希函数的个数。整个布隆过滤器的性能、内存、误判率全部由这三个参数决定。很多工程事故源头就是参数随便填导致误判率高得离谱过滤器形同虚设。3.2 误判率公式的推导拆解误判率的经典公式是 p ≈ (1 - e^(-kn/m))^k这个式子看起来吓人推导过程其实不难。初始时位数组全是0。插入一个元素时它对某个特定位没有任何影响的概率是 1 - 1/m。一个元素要算k个哈希位置所以插入一个元素后某个特定位仍然是0的概率是 (1 - 1/m)^k。依次插入n个元素后某个特定位仍然是0的概率是 (1 - 1/m)^(kn)。当m比较大时可以用自然对数的近似公式把这个概率约等于 e^(-kn/m)。也就是说经过n个元素插入后位数组上任一位置是0的概率约等于 e^(-kn/m)是1的概率约等于 1 - e^(-kn/m)。查询一个元素时它对应的k个位置都已经被置为1的概率就是 (1 - e^(-kn/m))^k这个概率就是误判率。因为一个不存在的元素恰好撞上这k个位置已经被其他元素覆盖满就会被误判成可能存在。这里的每个约等号背后都有假设哈希函数足够均匀位数组长度远大于元素数量各位置之间近似独立。实际使用中这些假设基本成立所以公式算出来的结果和实测非常接近。3.3 最优参数这样选给定预期元素数量n和能接受的误判率p两个关键参数可以直接算出来位数组长度 m - n * ln(p) / (ln2)^2哈希函数个数 k (m / n) * ln2约等于0.7倍的单位元素位数组长度。为了不让你每次都掏出公式现场算我把常用组合直接列成了一张速查表实际项目里可以对号入座预期元素n误判率p位数组m哈希函数k占用内存10万1%96万位7约117KB100万1%958万位7约1.14MB1000万1%9585万位7约11.4MB1000万0.1%1.44亿位10约17.2MB1亿0.1%14.4亿位10约171MB注意一个规律误判率从1%降到0.1%内存只增加了大约50%但哈希函数个数从7加到10CPU开销只增加了一点。这说明什么说明只要把位数组做大一点误判率就能显著下降性价比非常高。这也是我后面要说的重要经验——位数组宁可稍微做大也不要抠抠搜搜。3.4 一个不能忽略的坑误判率不是零但方向是单向的用布隆过滤器防缓存穿透必须接受一个事实会有一小部分不存在的请求被放过去。设计误判率为1%就意味着每100个不存在的ID里大约有1个会穿过过滤器走到下一步。很多第一次用的人会焦虑那这个漏网的怎么办答案是漏网的不直接返回不存在而是继续走原有缓存逻辑。如果缓存里没有就会打到数据库数据库也没查到这时我们可以回填一个短期空值把这次查询缓存下来。所以在缓存穿透场景里布隆过滤器从不孤军奋战。它的作用是挡住99%甚至99.9%的无效流量剩下的漏网之鱼由空值缓存兜底数据库实际收到的垃圾查询几乎可以归零。把过滤器设计成挡大头而不是追求100%拦截这才是工程上的正确姿势。4. 手写一个布隆过滤器从零到能跑4.1 最小可用版需要哪些部件虽然生产环境不建议自己造轮子但为了彻底搞懂原理我很推荐手动实现一个最小版本。你需要三个部件一个可以按位读写的数组、一个能生成多个独立哈希值的函数、以及add和mightContain两个核心方法。位数组的实现有个小技巧直接用long数组模拟。每个long是64位数组长度是(bitSize 63) / 64即可。读某个bit时先定位到它属于第几个long再定位到long内部第几位。4.2 完整代码示例下面这段Java代码是一个最小可用的布隆过滤器特意没有依赖任何第三方库方便你复制下来直接运行import java.util.BitSet; import java.util.Random; public class MiniBloomFilter { private final int bitSize; private final int hashFunctionCount; private final BitSet bits; public MiniBloomFilter(int bitSize, int hashFunctionCount) { this.bitSize bitSize; this.hashFunctionCount hashFunctionCount; this.bits new BitSet(bitSize); } // 核心哈希函数基于MurmurHash风格的64位混合散列 private long hash(String value, int seed) { long h 1125899906842597L * seed; for (int i 0; i value.length(); i) { h 31 * h value.charAt(i); } h ^ h 33; h * 0xff51afd7ed558ccdL; h ^ h 33; return Math.abs(h); } // 添加元素 public void add(String value) { for (int i 0; i hashFunctionCount; i) { int pos (int) (hash(value, i 1) % bitSize); bits.set(pos); } } // 可能存在性判断 public boolean mightContain(String value) { for (int i 0; i hashFunctionCount; i) { int pos (int) (hash(value, i 1) % bitSize); if (!bits.get(pos)) { return false; } } return true; } public static void main(String[] args) { int n 100_000; // 预期元素数量 double m -n * Math.log(0.01) / (Math.log(2) * Math.log(2)); int bitSize (int) Math.ceil(m); int k Math.max(1, (int) Math.round((bitSize / (double) n) * Math.log(2))); MiniBloomFilter filter new MiniBloomFilter(bitSize, k); // 插入10万个存在的数据 Random random new Random(42); for (int i 0; i n; i) { filter.add(user_ random.nextInt(Integer.MAX_VALUE)); } // 测试1已经插入的元素必须全部命中 random new Random(42); int miss 0; for (int i 0; i n; i) { if (!filter.mightContain(user_ random.nextInt(Integer.MAX_VALUE))) { miss; } } System.out.println(已插入元素漏判数量: miss); // 测试2未插入的元素统计误判率 int falsePositive 0; int total 1_000_000; for (int i 0; i total; i) { if (filter.mightContain(missing_ i)) { falsePositive; } } System.out.println(未插入元素误判率: (falsePositive * 100.0 / total) %); } }这段代码里最值得留意的是hash方法同一个元素通过不同seed算出的哈希位置彼此独立不需要为每个哈希函数单独写一套算法。这是布隆过滤器实现里非常常见的种子哈希技巧能有效降低计算开销。4.3 运行测试观察漏判与误判用上面这个程序跑一轮会得到两组结果第一组已经插入的10万个元素漏判数量通常是0。这是布隆过滤器最硬的保证——只要元素插入过查询永远返回true。第二组100万个没插入过的元素误判率大概在1%上下。参数设计得越准实测值和预期就越接近。我自己跑的时候第二次测试的误判率会在0.98%到1.1%之间浮动和公式预期一致。这里插一句之前有朋友问为什么误判率不是精确等于1%因为哈希碰撞是概率事件少量波动是正常的只要量级和设计值一致业务上就没问题。代码跑通以后你还可以做几个小实验加深理解把bitSize强行调小比如从96万位改成9万位误判率会瞬间跳到20%以上把k从7改成2误判率同样会飙升。这些实验会让你深刻理解参数不是随便填的这句话。4.4 生产环境为什么别自己造轮子刚才的手写版逻辑完整但它不适合上生产。原因有三个哈希质量不够稳Java原生的字符串哈希分布性本身就一般我那个简化版只适合演示缺少动态扩容能力元素数量超过预期后误判率会直线上升成熟实现普遍做了SIMD优化、内存映射、持久化等工程细节性能差距能有好几倍。所以我的建议是原理学习用手写版生产落地直接用你所在技术栈里被验证过的成熟实现。Java生态有非常流行的集合增强库Python有第三方位数组库Go、C也有各自的实现选一个文档全、社区活跃的就行。核心接口无非就是put和mightContain迁移成本极低。5. 防缓存穿透的落地姿势和缓存链路怎么配合5.1 整体业务流程加一道闸门原理和实现都清楚了接下来是工程落地。布隆过滤器防缓存穿透的标准姿势是在缓存链路前面加一道存在性闸门流程是这样请求进来 - 先查布隆过滤器 - 过滤器判定不存在直接返回空结果全程不碰缓存和数据库 - 过滤器判定可能存在继续走原缓存链路 - 缓存没命中则查数据库 - 数据库查到就回填缓存数据库没查到就回填短期空值。这个流程里布隆过滤器像一个严格的保安只放行可能是自己人的访客。绝大多数不存在的请求在第一步就被短路了代价仅仅是几次哈希计算和位数组内存访问耗时都在亚微秒级比查一次Redis还快。5.2 全量加载的三种策略要在请求进来前让过滤器生效必须提前把业务数据的全集ID构建进去。构建方式有三种各有适用场景策略做法适用场景注意事项启动加载应用启动时全量扫描业务数据构建过滤器业务数据量适中、启动时间可以容忍数据量大时启动变慢可以考虑异步构建定时重建每隔一段时间重新构建一次数据有增有删但删除不频繁重建期间要用双缓冲避免服务中断增量同步新增数据实时写入过滤器数据只有新增、几乎无删除简单高效但要处理好消息丢失的补偿实际项目里我最常用的是增量同步 定时重建的组合新增数据通过消息队列实时加入过滤器保证新数据立即可见同时每天凌晨重建一次把误判率重新校准回来顺便处理掉那些已经删掉了的数据。5.3 和缓存空值组合成双保险很多人纠结一个问题布隆过滤器已经有1%的误判那漏网的1%怎么办答案是补一层空值缓存。流程里那步数据库没查到就回填短期空值就是为了接住这1%的漏网之鱼。我把这段伪代码贴出来可以直接照着改造现有查询逻辑public Object query(String id) { // 第一道闸门布隆过滤器挡掉绝大多数不存在请求 if (!bloomFilter.mightContain(id)) { return null; } // 第二道闸门缓存 Object value cache.get(id); if (value ! null) { return value; } // 第三道闸门数据库 value database.query(id); if (value null) { // 布隆过滤器误判的漏网之鱼用短TTL空值缓存接住 cache.set(id, EMPTY_PLACEHOLDER, 30); return null; } cache.set(id, value, 3600); return value; }这样设计以后布隆过滤器的0.1%误判最多打到缓存这一层而空值缓存又挡住了绝大多数缓存未命中两者一叠加真正打到数据库的不存在查询寥寥无几。这也是我说布隆过滤器从来不是单独工作的原因它负责降低量级缓存空值负责兜底分工明确。5.4 定时重建时的过渡问题如果你选了定时重建一定要考虑过渡期的问题。重建需要时间这期间过滤器还在服务请求如果直接把旧过滤器替换掉重建完成前的新数据可能查不到重建完成后旧数据如果没被包含就会有一批已经存在的正常数据被误判成不存在直接返回空这是比误判更严重的故障。稳妥做法是双缓冲两个过滤器实例一个正在服务一个正在重建重建完成后把新的原子替换旧的。替换瞬间注意两点一是判断新旧之间存在的数据差异用增量消息补齐二是替换后把新构建完成的时间点作为增量同步的起始水位避免漏加。我在一个模拟项目里踩过一次这个坑。当时没做双缓冲直接重建替换结果替换窗口期间产生的一批新数据全部查询不到用户端表现就是刚创建的资源立刻消失了。从那以后凡是涉及重建的操作我都默认先构建新实例再切换已经成了肌肉记忆。6. 实战复盘坑、边界条件和我的建议6.1 坑一位数组大小拍脑袋定误判率直接失控我见过最典型的失误是预估100万条数据位数组随手设了100万位哈希函数设了3个。代入公式算一下误判率大约在20%以上——也就是每5个不存在的请求就有1个会穿透过滤器。这种过滤器上了生产以后数据库照样会被打成筛子唯一的区别是从全部穿透变成一部分穿透治理效果约等于零。正确做法是先用前面的公式算出参数再下单。你不需要每次都手算直接用成熟库的构造方法它一般会要求你传入预期元素数量和可接受误判率由内部自动计算m和k。如果你拿到的API只让你传bitSize和hashCount说明你大概率在用某低层实现建议换一个更友好的封装。6.2 坑二元素数量暴涨后忘记扩容布隆过滤器的误判率和实际插入数量/预期数量的比值强相关。预期100万实际塞进去500万误判率会从1%膨胀到不可接受。很多团队只关注上线那一刻的参数没有考虑业务增长。这里给几个可操作的监控建议在过滤器里周期性统计实际插入数量并对外暴露指标监测量级达到预期值的80%就启动扩容流程扩容不是原地变大而是新构建一个更大位数组的实例双缓冲切换扩容后旧实例延迟淘汰避免切换瞬间有查询漏过。这套流程看起来像缓存重建本质上也确实是一回事。布隆过滤器不是一锤子买卖它是一个需要被监控和运维的系统组件而不是写死就忘的静态配置。6.3 坑三标准布隆过滤器不支持删除这是最容易被忽视的坑。位数组上的每一位可能被多个元素共用你删掉一个元素不能把它对应的k个位清0因为那些位可能被其他元素占用了。那数据被删除后过滤器里还留着它的痕迹会不会有问题分场景如果业务是数据一旦生成ID永远有效比如用户ID自增那么痕迹留着也无所谓最多是过滤器里多几个永远不会再出现的ID白白占点空间如果业务里删除是常态比如商品频繁上下架那么必须用重建方案。定时重建可以把已删除ID的痕迹洗掉如果删除需要实时生效标准布隆过滤器做不到得换计数布隆过滤器。它把每个位从0/1扩展成计数器删除时对应计数器减1计数器归0才把位清掉。代价是空间占用变成原来的数倍实践中很少用。6.4 边界布隆过滤器不是银弹聊了这么多还是要泼点冷水。布隆过滤器解决的是大量不存在的查询打爆数据库这一个问题它不适用于以下场景需要精确去重而且误判会导致业务事故的场景比如记账、防重支付数据量很小比如只有几千条ID直接用Set或数据库索引反而更简单别为了用而用对删除实时性要求非常高的场景标准版做不到计数版空间代价又太大需要从结构中还原原始数据的场景布隆过滤器压根不存数据内容。另外还有个常见误解布隆过滤器是给缓存穿透用的不是给缓存击穿用的。击穿是热点Key过期瞬间大量请求同时打到数据库那是缓存里原本有、刚过期的问题靠布隆过滤器没用应该靠互斥锁或热Key永不过期来治理。这两个问题名字像解法和工具完全不同。6.5 我的一些经验总结按照我的习惯最后再分享几条实操体会都是踩过以后才真正信服的第一参数设计时位数组宁大勿小。误判率从1%降到0.1%内存只多50%但数据库承受的无效查询量直接少一个数量级。这个账怎么算都划算。第二布隆过滤器要当成运维对象来看。插入数量是核心指标必须监控起来。我见过线上过滤器实际插入量是预期的5倍误判率高到报警才发现当初的上限设得太保守。第三用的库一定要有原子替换和持久化能力。原子替换解决重建过渡问题持久化解决重启恢复问题。没有这两点每次发版重启后过滤器都是空的等于没上。第四如果只是单纯防缓存穿透最省心的方案还是主流缓存中间件自带的布隆过滤器扩展模块不用自己维护构建流程数据通过消息队列同步进去就行。自己写一套完整方案当然能做但考虑到后续运维成本成熟模块永远是第一选择。布隆过滤器这个结构我自己每次讲都还能有新体会。它最迷人的地方在于用一个看似不精确的思路换来了数量级的空间节省并且把误判控制在一个可量化的指标之内。理解它不光是为了解决今天这个缓存穿透问题更是理解用空间换时间、用概率换空间这套系统设计思维的一个好入口。