qidao123.com技术社区-IT企服评测·应用市场

标题: 缓存穿透的解决方式？—布隆过滤器 [打印本页]
作者: 王海鱼    时间: 2025-4-30 06:34
标题: 缓存穿透的解决方式？—布隆过滤器
扼要答复

缓存穿透（cache penetration）是用户访问的数据既不在缓存当中，也不在数据库中。出于容错的考虑，如果从底层数据库查询不到数据，则不写入缓存。这就导致每次哀求都会到底层数据库举行查询，缓存也失去了意义。当高并发或有人利用不存在的Key频仍攻击时，数据库的压力骤增，甚至崩溃，这就是缓存穿透题目。
缓存穿透与缓存击穿同样非常相似，区别点在于缓存穿透的实际哀求数据在数据库中也没有，而缓存击穿是仅仅在缓存中没命中，但是在数据库中其实是存在对应数据的。

发生场景：
缓存穿透解决方案：
接下来本文会详细介绍一下布隆过滤器及其使用场景
扩展-布隆过滤器

概述

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比力巧妙的概率型数据结构，特点是高效地插入和查询，查询时可以用来判断 “一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。
原理

当一个元素被参加集合时，通过 K 个散列函数将这个元素映射成一个位图中的 K 个位置，把它们置为 1。查询时，只要检察这些位置是不是都是 1 ，就知道集合中有没有它了：如果这些位置有任何一个 0，则被查询元素一定不存在；如果都是 1，则被查询元素很可能存在。
简单来说就是将一个长度为 m 的位数组的所有元素初始化为 0，用 k 个散列函数对元素举行 k 次散列运算跟 len (m) 取余得到 k 个位置并将 m 中对应位置设置为 1。

如上图，位数组的长度是８，散列函数个数是 3，两个元素ｘ，ｙ。这两个元素都颠末三次哈希函数天生三个哈希值，并映射到位数组的差别的位置，并置为1。元素 x 映射到位数组的第０位，第４位，第７位，元素ｙ映射到数组的位数组的第１位，第４位，第６位。
当布隆过滤器保存的元素越多，被置为 1 的 bit 位也会越来越多，元素 z 即便没有存储过，假设哈希函数将z映射到位数组的三个位都被其他值设置为 1 了，对于布隆过滤器的机制来讲，元素 z 这个值也是存在的，也就是说布隆过滤器存在一定的误判率。因此布隆过滤器只能包管一定不存在和可能存在。
误判率

布隆过滤器包含如下四个属性：
若位数组长度太小则会导致所有 bit 位很快都会被置为 1 ，那么检索任意值都会返回“可能存在” ， 起不到过滤的效果。位数组长度越大，则误判率越小。同时，哈希函数的个数也需要考量，哈希函数的个数越大，检索的速度会越慢，误判率也越小，反之，则误判率越高。
为什么就用一个hash函数不可？
其实布隆过滤器底层是用 位图 实现的，而多个hash函数就是为了减少位图的误判率的。详细可往下看
假设布隆过滤器中的hash函数满意simple uniform hashing假设：每个元素都等概率地hash到m个位中的任何一个，与别的元素被hash到哪个位无关。那么
p = $(1- (1 - 1/m){nk})k ~ (1 - e^{- nk/m})^k$
显然，当m越大，n减少时，误判率就越低。而且当k越大，误判率p也就越小，也就是说，hash函数越多，误判率越低，但相对检索的速度会越慢。
如图：雷同位数组长度的情况下，随着哈希函数的个数的增长，误判率明显的下降。

布隆过滤器的效率和缺点

布隆过滤器的空间复杂度为 O(m) ，插入和查询时间复杂度都是 O(k) 。 存储空间和插入、查询时间都不会随元素增加而增大。 空间、时间效率都很高。
但是布隆过滤器并不支持删除元素，因为多个元素可能哈希到一个布隆过滤器的同一个位置，如果直接删除该位置的元素，则会影响其他元素的判断。因此，就提出了 计数布隆过滤器
计数布隆过滤器

计数过滤器（Counting Bloom Filter）是布隆过滤器的扩展，标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1，删除元素时给对应的 k 个 Counter 的值分别减 1。

显然，又引入了另一个题目：更多的资源占用，而且在很多时候会造成极大的空间浪费
使用场景

Redis的缓存穿透

对于一个数据查询，其过程大致如下：

但是当查询的数据既不在缓存中，也不存在数据库中，则没有办法回写缓存，当有类似如许大量的哀求访问服务时，数据库的压力就会极大。这就是缓存穿透
因此，引入布隆过滤器，当用户哀求时，判断过滤器中是否存在该元素，若不存在该元素，则直接返回不存在。若包含则从缓存中查询数据，若缓存中也没有，则查询数据库并回写到缓存里，最后给前端返回。

尽管布隆过滤器有少量的误判，即可能不存在的数据会判断存在，从而继承查询缓存和数据库，但只要将m和k的值设置相对理想，少量的不存在查询也是可以接受的。
元素删除场景

实际上，元素不仅仅是只有增加，还存在删除元素的场景，比如说商品的删除，删除后数据其实已经不存在了，但是布隆过滤器中还没删除，则会判断其存在。
第一种方案就是使用计数布隆过滤器。
第二种方案，则是通过 定时重新构建布隆过滤器

在删除商品 到 使用新的布隆过滤器B 之间的这段时间的不存在的查询有可能还会到数据库层面，但这种少量的不存在查询也是可以接受的。
应用布隆过滤器

Redisson

Redisson 提供了操纵布隆过滤器的简单易用 API，以下是使用布隆过滤器的示例：
  1.   <dependency>
  2.     <groupId>org.redisson</groupId>
  3.     <artifactId>redisson</artifactId>
  4.     <version>3.37.0</version>
  5. </dependency>
复制代码
  1. private void redisson() {
  2.     RedissonClient redissonClient = Redisson.create();
  4.     RBloomFilter < Object > bloomFilter = redissonClient.getBloomFilter("bloomFilter");
  5.     // 初始化大小为 10亿，假阳率为 0.001（在使用布隆过滤器之前，必须完成初始化操作）
  6.     bloomFilter.tryInit(1000000000, 0.001);
  8.     Object object = new Object();
  9.     // 添加元素
  10.     bloomFilter.add(object);
  12.     // 检查元素是否存在
  13.     boolean exist = bloomFilter.contains(object);
  14. }
复制代码
Guava

Guava 也提供了 BloomFilter 实现，用于高效地判断一个元素是否存在于集合中，在 23.0 及之后版本中，是线程安全的。以下是 Guava 中布隆过滤器使用示例：
  1. <dependency>
  2.     <groupId>com.google.guava</groupId>
  3.     <artifactId>guava</artifactId>
  4.    
  5.     <version>33.3.1-jre</version>
  6. </dependency>
复制代码
  1. import com.google.common.hash.BloomFilter;
  2. import com.google.common.hash.Funnels;
  4. public class BloomFilterExample {
  5.     public static void main(String[] args) {
  6.         // 创建一个布隆过滤器，预计插入 3000000 个整数，假阳率为0.01
  7.         BloomFilter < Integer > bloomFilter = BloomFilter.create(
  8.             Funnels.integerFunnel(), 3000000, 0.01);
  10.         // 向布隆过滤器中添加元素
  11.         for (int i = 0; i < 3000000; i++) {
  12.             bloomFilter.put(i);
  13.         }
  15.         // 测试布隆过滤器
  16.         for (int i = 0; i < 3001000; i++) {
  17.             if (bloomFilter.mightContain(i)) {
  18.                 System.out.println(i + " might be in the filter.");
  19.             } else {
  20.                 System.out.println(i + " is definitely not in the filter.");
  21.             }
  22.         }
  23.     }
  24. }
复制代码
布隆过滤器总结

布隆过滤器的空间效率O(m) 和查询时间O(k) 都很良好，但是存在一定的误判率 （布隆过滤器以为不存在，则一定不存在；布隆过滤器以为存在，则只是可能存在）
bit数组的位数m越大，hash函数的个数k越多，误判率就越低。但也需要控制合适的大小，比如m越大，但存储的数据少，则会引起空间浪费，k的个数越多，则会一定程度降低查存效率
普通布隆过滤器无法删除元素，但可以通过计数布隆过滤器和定时重新构建布隆过滤器两种方案实现删除元素的效果。
拓展：布谷鸟过滤器

布隆过滤器不记录元素本身，而且存在一个位被多个元素共用的情况，所以它不支持删除元素。布谷鸟过滤器（详细了解可以参考这篇论文《布谷鸟过滤器：实际上优于布隆过滤器》）的提出解决了这个题目，它支持删除操纵，此外它还带来了其他优势：
布谷鸟过滤器之所以被称为“布谷鸟”，是因为它的工作原理类似于布谷鸟在天然界中的举动。布谷鸟以将自己的蛋产在其他鸟类的巢中而闻名，如许一来，寄主鸟就会抚养布谷鸟的幼鸟。
在布谷鸟过滤器中，如果一个位置已经被占用，新元素会“驱逐”现有元素，将其移到其他位置。这种“驱逐”举动类似于布谷鸟将其他鸟蛋推出巢外，以便安置自己的蛋。因此，这种过滤器得名为“布谷鸟”过滤器。
布谷鸟过滤器本质上是一个 桶数组，每个桶中保存多少数量的 指纹（指纹由元素的部门 Hash 值盘算出来）。定义一个布谷鸟过滤器，每个桶记录 2 个指纹，5 号桶和 11 号桶分别记录保存 a, b 和 c, d 元素的指纹，如下所示：

此时，向此中插入新的元素 e，发现它被哈希到的两个候选桶分别为 5 号 和 11 号，但是这两个桶中的元素已经添加满了：

按照布谷鸟过滤器的特性，它会将此中的一个元素重哈希到其他的桶中（详细选择哪个元素，由详细的算法指定），新元素占据该元素的位置，如下：

以上便是向布谷鸟过滤器中添加元素并发生冲突时的操纵流程，在我们的例子中，重新放置元素 e 触发了另一个重置，将现有的项 a 从桶 5 踢到桶 15。这个过程可能会重复，直到找到一个能容纳元素的桶，这就使得布谷鸟哈希表更加紧凑，因此可以更加节省空间。如果没有找到空桶则以为此哈希表太满，无法插入。固然布谷鸟哈希可能实行一系列重置，但其均摊插入时间为 O(1)。
与布隆过滤器一样，布谷鸟过滤器同样会造成假阳性，造成假阳性的有以下原因：
cuckoofilter 是 Github 上 Star 数较多的一个仓库，它参考了论文内容，并用 Golang 实现了布谷鸟过滤器，大家感兴趣的话可以直接去参考它的源码。该过滤器重要的参数如下：
我们在此讨论下它的删除方法实现：
  1. // Delete 删除过滤器中的指纹
  2. func (cf *Filter) Delete(data []byte) bool {
  3.   // 尝试在首选桶中删除
  4.   i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
  5.   if cf.delete(fp, i1) {
  6.     return true
  7.   }
  8.   // 删除失败，则尝试从备用桶删除
  9.   i2 := getAltIndex(fp, i1, cf.bucketPow)
  10.   return cf.delete(fp, i2)
  11. }
复制代码
它的删除方法实现比力简单：它检查给定元素的两个候选桶，如果在首选桶中匹配到则将该指纹移除，否则去备用桶中匹配，在备用桶中则移除备用桶指纹，如果备用桶中没有，则会提示删除失败。如果两个元素 a, b 发生碰撞（共享桶和指纹），那么在 a 元素删除后，因为 b 元素的存在，仍然会判断 a 元素在过滤器中，体现出假阳性。需要注意的是，想要安全的删除某元素，必须事先插入它，否则删除插入项可能会无意中删除共享指纹的真实存在的项，而且如果多次插入重复元素，想要将其删除干净还需要知道该元素插入了多少次。
此外，相比于布隆过滤器它也存在一些的劣势：
对于过滤器缓存的使用，大部门情景都是读多写少的，而重复插入并没有什么意义，布谷鸟过滤器的删除固然不完善但总好过没有（因为布隆过滤器想要删除元素便需要重修，上亿甚至几十亿的数据重修缓存也蛮花时间），同时还有更优的查询和存储效率，应该说在绝大多数情况下其都是一个性价比更高的选择。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4