【Java项目】布隆过滤器解决缓存穿透问题以及布隆过滤器删除困难问题

╰半橙微兮° 2024-03-17 16:21 81阅读 0赞

#### 文章目录 ####

*  什么是缓存穿透问题
 *  什么是布隆过滤器
 *  布隆过滤器的实现
 *  解决不支持删除的问题

## 什么是缓存穿透问题 ##

访问浏览器，用户访问那些存在在Redis或者数据库中的数据的时候都能正常返回结果，但是如果查询那些不存在于Redis中也不存在于数据库中的数据，那么这些无意义的查询如果非常多，都将直接穿过Redis而导向数据库，导致数据库压力提高，造成宕机。

因此，缓存穿透就是指用户访问那些在数据库和Redis中都不存在的数据，例如我们知道id采用自增策略，那么就不可能出现负数id，而如果不法分子使用负数id进行查询，那么这些请求都会穿过Redis直接向数据库发送请求，从而导致数据库压力骤增，导致数据库宕机。（一般是恶意行为）

那么如何解决缓存穿透问题？

*  缓存空对象，每次发送这种查询不到的id的时候都把这些id缓存到Redis中，并且设定值为空（null），那么下次如果是一样的id进行查询就会直接返回空对象。  
    优点在于实现简单，维护容易，缺点在于内存浪费。
 *  直接拉黑恶意请求的IP，对方可能不断更换IP
 *  对参数合法性进行校验
 *  布隆过滤器，优点在于内存占用少，不会出现多余的key，缺点在于实现不容易，并且有误判的可能

## 什么是布隆过滤器 ##

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难，原因是因为对于不同的数据，可能会出现使用同一个hash函数得出相同的值，导致某个bit位上被置为一。从而出现误判。  
也就是说布隆过滤器不是准确的，是纯在误差的。

布隆过滤器的原理：当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。

简单来说就是准备一个长度为length的位数组并初始化所有元素为 0，用 k 个散列函数对元素进行 k 次散列运算跟 length 取余得到 k 个位置并将位数组中对应位置设置为 1。

当布隆过滤器保存的元素越多，被置为 1 的 bit 位也会越来越多，元素 x 即便没有存储过，假设哈希函数映射到位数组的某个位都被其他值设置为 1 了，对于布隆过滤器的机制来讲，元素 x 这个值也是存在的，也就是说布隆过滤器存在一定的误判率。

从上面可以知道，布隆过滤器的空间复杂度为O(length)，查询和插入的事件复杂度为O(k)，其中k为散列函数的个数。  
还有一个特点是布隆过滤器是不支持删除数据的，因为删除一个位的数据，可能会影响其他也映射到了这个位的数据。所以布隆过滤器会随着使用，误差率越来越大，需要考虑一个方法去解决这个问题。

## 布隆过滤器的实现 ##

根据上面的了解，布隆过滤器的实现依靠的是二进制向量以及多个Hash函数，因此，对于布隆过滤器的准确度，其影响因素包含Hash函数的随机性，二进制向量的大小。  
目前比较常用的布隆过滤器实现有Guava和Redisson。  
对于使用Guava，方法如下

1、添加Maven依赖
    
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>31.0.1-jre<</version>
    </dependency>
    
    
    2、创建布隆过滤器
    BloomFilter<Integer> filter = BloomFilter.create(
      //Funnel 是一个接口，用于将任意类型的对象转换为字节流，
      //以便用于布隆过滤器的哈希计算。
      Funnels.integerFunnel(), 
      10000,  // 插入数据条目数量
      0.001  // 误判率
    );

对于使用Redission

1、添加Maven依赖
    
    <dependency>
       <groupId>org.redisson</groupId>
       <artifactId>redisson</artifactId>
       <version>3.16.1</version>
    </dependency>
    2、配置 Redisson 客户端
    
    @Configuration
    public class RedissonConfig {
        
    
     Bean
     public RedissonClient redissonClient() {
        
        Config config = new Config();
        config.useSingleServer().setAddress("redis://localhost:6379");
        return Redisson.create(config);
     }
     
    }
    3、初始化
    
    RBloomFilter<Long> bloomFilter = redissonClient.
                                          getBloomFilter("myBloomFilter");
    //10000表示插入元素的个数，0.001表示误判率
    bloomFilter.tryInit(10000, 0.001);
    //插入4个元素
    bloomFilter.add(1L);
    bloomFilter.add(2L);
    bloomFilter.add(3L);
    bloomFilter.add(4L);
    4、判断数据是否存在
    
    public boolean mightcontain(Long id) {
        
        return bloomFilter.contains(id);
    }

其实Java原生也提供了布隆过滤器的实现方式，Java提供了我们进行位运算的集合BitSet，我们可以使用BitSet以及自己实现Hash函数的方式自己实现一个布隆过滤器。

## 解决不支持删除的问题 ##

对于上面说到的，随着布隆过滤器的使用，会使得查询的误差越来越大，那么有什么办法解决这种问题？

先说一个简单的，就是直接替换这个布隆过滤器。  
我们可以编写一个定时任务，在一定事件之后，创建一个新的布隆过滤器，然后把数据库中的全量数据查询出来然后使用映射将其映射到新的布隆过滤器中，之后无感更新原有的布隆过滤器的指针即可。这种方式实现简单。

还有一种方式是使用计数的方式，我们知道布隆过滤器的底层使用的是二进制向量，也就是因为这个向量只有01两个值，那么如果多个元素都映射到这个位置，我们将其置为0，就会导致更大的误判，所以，如果我们考虑将二进制向量替换为Byte类型，也就是支持计数，这个位的值不仅仅只有01，那么我们就在映射到这个位置的时候使用 ++ 的方式来递增，如果要删除，我们就 – ，这样子如果这个位为0，也可以判断数据是否存在。  
有一个很大的缺点就是，空间浪费增大了，并且效率也下降了。同时，我们还得考虑并发修改问题。