从 Redis 缓存穿透到布隆过滤器，再到布谷鸟过滤器：一次穿透防护的进化

一、什么是缓存穿透缓存穿透指客户端请求的数据在缓存如 Redis 中不存在同时在数据库中也不存在。由于缓存不命中每次请求都会直接穿透到数据库。当大量这样的请求例如恶意攻击或随机非法 key并发过来时数据库会瞬间承受巨大压力甚至崩溃导致整个服务不可用。典型场景攻击者伪造大量不存在的用户 ID如-1,9999999查询用户信息。业务代码未做空值校验直接查询数据库。危害数据库连接被占满正常请求无法处理。缓存失去“挡箭牌”作用系统整体可用性急剧下降。二、常规应对方案的局限1. 缓存空对象将查询不到的数据也缓存一个空值例如null并设置较短过期时间。❌缺点非法 key 可以是无限多个随机生成缓存会被大量无意义空值占满浪费内存。攻击者不断变换 key依然可以绕过。2. 请求参数校验如 ID 格式、范围❌缺点无法防御随机生成但格式合法的 key例如1000000到9999999之间大量不存在的 ID。结论需要一种能高效判断“某个 key 一定不存在”的数据结构 ——布隆过滤器应运而生。三、布隆过滤器Bloom Filter—— 缓存穿透的第一道防线3.1 什么是布隆过滤器布隆过滤器是一个非常节省空间的概率性数据结构它可以告诉您一定不存在绝对可靠可能存在有一定误判率3.2 原理图解初始化一个位数组bit array所有位为 0。插入元素时使用k 个不同的哈希函数对元素计算 k 个哈希值分别对数组长度取模将对应位置设为 1。查询元素时同样计算 k 个哈希位置只要有一个位置为 0则该元素一定不存在如果所有位置都为 1则可能存在因为可能与其他元素发生哈希冲突。3.3 布隆过滤器能解决缓存穿透吗能。在查询缓存之前先用布隆过滤器判断 key 是否存在若布隆过滤器说“不存在”直接返回不查缓存更不查 DB。若说“可能存在”再走正常的缓存 → DB 流程。由于大多数非法 key 都是不存在的布隆过滤器会直接拦截掉绝大部分请求保护数据库。3.4 布隆过滤器的缺点❌不支持删除元素因为多个元素的哈希可能共享同一个位如果把某个位置 0会误伤其他元素。❌存在误判率假阳性随着元素增多位数组越来越满误判率会上升。❌ 参数位数组长度、哈希次数需要根据预估数据量和可容忍误判率通过公式计算新手容易设错。3.5 Google Guava 轻松使用布隆过滤器// 预估要插入 100 万个元素期望误判率为 1%BloomFilterStringbloomFilterBloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),1_000_000,0.01);// 插入存在的 keybloomFilter.put(user:1001);// 判断是否存在if(bloomFilter.mightContain(user:9999)){// 可能存在去查缓存/DB}else{// 一定不存在直接返回}Guava 会根据元素个数和误判率自动计算出最优的位数组长度和哈希次数无需手动公式。3.6 数据量增长导致误判率升高怎么办重建过滤器创建一个新的、更大的布隆过滤器将数据库中所有存在的 key 重新插入一次然后原子切换使用新过滤器。注意重建期间需要双写或暂停写入以避免数据不一致。✨ 3.7 为什么不支持删除会成为问题—— 真实业务场景举例很多业务场景中数据会从数据库中物理删除而布隆过滤器由于无法删除元素会一直认为这个 key 仍然“可能存在”。场景一用户注销/账号删除用户注册时系统将user:{uid}插入布隆过滤器。某天用户注销账号从 DB 中删除了该用户记录。布隆过滤器中该用户的指纹位依然为 1。攻击者或巧合请求该已注销的 uid → 布隆过滤器返回“可能存在”于是请求放行到缓存无数据→ 查询 DB无数据→ 返回空。结果每次请求依然会打到数据库布隆过滤器形同虚设防护效果丢失。场景二商品下架/库存清理电商平台商品 ID 范围相对固定活动商品下架后从 DB 删除。布隆过滤器无法同步删除 → 大量对已下架商品的请求仍然穿透到 DB。大促期间这些无效请求可能挤占数据库资源影响正常商品查询。场景三黑名单动态管理系统维护一个恶意 IP 黑名单采用布隆过滤器加速判断。某个 IP 被解封从黑名单中删除但布隆过滤器仍认为它在黑名单中 → 导致误拦截正常用户。要解决只能重建整个黑名单过滤器代价高昂。场景四缓存穿透防护中的“已删除数据”原始缓存穿透场景中我们使用布隆过滤器存储“所有存在于 DB 中的 key”。当 DB 中某个 key 被删除后过滤器本应不再认为该 key 存在从而直接拦截对该 key 的请求因为确实不存在。但因为布隆过滤器无法删除它仍然放行该请求前往 DB导致本可以拦截的请求变成了多余的 DB 查询甚至可能被恶意利用来试探哪些 ID 已被删除。结论在数据有增、删、改的业务中布隆过滤器会逐渐积累“已删除但未清除”的标记导致防护效果衰减甚至产生误判。这就迫切需要一种支持删除的过滤器。四、从布隆过滤器的痛点到布谷鸟过滤器布隆过滤器最大的两个痛点不支持删除上述业务场景充分说明了其缺陷随着容量增长误判率不易动态调整需重建于是一个更现代、支持删除的过滤器 ——布谷鸟过滤器Cuckoo Filter被提出。五、布谷鸟过滤器Cuckoo Filter详解布谷鸟过滤器的核心思想是使用桶bucket 指纹fingerprint并通过布谷鸟哈希实现踢出与重定位。5.1 核心数据结构一个桶数组每个桶可以存储多个指纹通常 4~8 个。指纹 元素的哈希值截取低若干位如 8 位用于存储和比对。每个元素通过哈希计算出两个候选桶位置h1和h2并且这两个位置可以相互推导通过异或运算。5.2 关键公式标准布谷鸟过滤器设fingerprint fingerprint(x)取哈希的低f位i1 hash(x) % bucket_numi2 i1 ⊕ hash(fingerprint)重要特性i2和i1可以通过指纹和异或运算互相计算这在踢出元素时非常有用。5.3 插入流程最精彩的部分计算fingerprint,i1,i2。尝试将fingerprint放入i1桶的空位如果满则尝试i2桶的空位。如果两个桶都满了则随机选择一个桶并随机踢出该桶内的一个旧指纹old_finger。将新指纹放入被踢出的位置。对被踢出的old_finger根据它当前所在的桶位置假设是i_current和old_finger计算出它的另一个候选桶i_other i_current ⊕ hash(old_finger)将old_finger插入到i_other桶中如果该桶也满则继续踢出形成递归。如果踢出次数超过阈值如 500 次表示过滤器太满需要扩容或重建。 这个“鸠占鹊巢、反复挪窝”的过程正是“布谷鸟”名字的由来。5.4 查询流程计算fingerprint,i1,i2。检查i1桶和i2桶中是否存在相同的fingerprint。若存在返回“可能存在”否则返回“一定不存在”。5.5 删除流程布隆过滤器做不到的事计算fingerprint,i1,i2。在i1桶和i2桶中查找与fingerprint完全匹配的指纹。如果找到删除其中一份副本注意同一个桶内可能有重复指纹只删一个。✅删除不会影响其他元素因为每个桶存储的是独立指纹不与其他元素共享位。5.6 布谷鸟过滤器的优点特性布隆过滤器布谷鸟过滤器空间效率高更高同等误判率下支持删除❌✅查询性能O(k)O(桶大小) 通常很小动态扩容需重建可设计渐进式扩容复杂实现复杂度简单中等5.7 注意事项布谷鸟过滤器仍有极低概率的误判指纹冲突。删除时可能误删如果两个不同元素碰巧生成相同的指纹且位于同一对桶中删除一个会导致另一个也被认为不存在但概率极低。填充率超过 ~95% 时插入可能失败需扩容。六、如何选择不需要删除 实现简单→ 布隆过滤器适合数据只增不减的场景如用户注册 ID 永不删除。需要删除 空间敏感→ 布谷鸟过滤器适合黑名单、动态商品库、用户数据可能注销等场景。极低误判率要求像数据库索引→ 仍用传统数据库或精确集合如 Redis Set。在实际缓存穿透防御中如果业务数据很少删除如用户 ID 一旦生成就不会删除布隆过滤器完全够用。如果存在频繁的 key 删除例如用户注销、商品下架、黑名单动态更新布谷鸟过滤器更合适。七、总结阶段解决方案核心特点缓存穿透问题布隆过滤器高效拦截不存在的 key但不支持删除布隆过滤器局限需要删除布谷鸟过滤器支持删除空间效率更高但实现稍复杂从 Redis 缓存穿透到布隆过滤器再到布谷鸟过滤器这是一条从简单高效到更灵活强大的技术演进之路。理解它们的原理和适用场景能帮助我们在高并发系统中更好地保护后端数据库。 最后提醒任何过滤器都只能拦截“一定不存在”的请求对于真实存在的 key仍需要缓存 数据库的正常读写流程。