springboot使用布隆过滤器——缓存穿透

ゞ浴缸里的玫瑰 2024-04-03 11:31 83阅读 0赞

**目录**

1.布隆过滤器原理

2.具体使用场景

3.springboot集成布隆过滤器

4.总结

### 1.布隆过滤器原理 ###

布隆过滤器（Bloom Filter）是非常经典的以空间换时间的算法。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

布隆过滤器一般常用于存储数据，并判断数据是否存储与过滤器中。他的原理如下：

![a1d34b7949284646a0e7c5dd9d757ad9.png][]

当一个数据存入过滤器中时，会经过哈希函数进行计算（图中是三个，不一定是三个），计算后得出对应的结果，存入对应的位中，将其值改为1。‘

当查询一个值时，会经过同样的哈希运算，然后去找寻对应的位值，如果都为1，即判断该值**可能**会存在；若有一个值不为1，都认为该值不存在于过滤器中。

但布隆过滤器会存在误判;

![2fe0355b2207401f999f7d70f76b82d4.png][]

如上图所示，两个不同的值，经过相同的哈希运算后，可能会得出同样的值。即上图中，hello和你好经过哈希运算后，都为2，把位2上的值改为1。所以，无法判断位2上的值为1是谁的值。同时，如果只存储了"你好"未存储"hello"，当查询hello时，经过哈希运算得出值为2，去位2中查看，得知值为1，得出结论"hello"可能存在于过滤器中，即发生了误判。

误判可以通过增多哈希函数进行降低。**哈希函数越多，误判率越低**。同时，布隆过滤器查找和插入的时间复杂度都为O(n)，n为哈希函数的个数。所以，哈希函数越多，时间复杂度越高。具体如何选择，需要根据数据量的多少进行。

布隆过滤器优缺点如下：

*  相比于其它的数据结构，由于布隆过滤器不存储数据本身，而使用二进制位来存储数据，在空间和时间方面都有巨大的优势，且在某些对保密要求非常严格的场合有优势。
 *  由于上文中提到的数据经过哈希计算后值相同的原因，一般情况下不能从布隆过滤器中删除元素。

### 2.具体使用场景 ###

布隆过滤器可以应用于缓存穿透场景中。缓存穿透，一般判断数据是否在缓存中，如果在则直接返回结果，不在则查询数据库；如果来一波冷数据（比如使用大量随机生成的uuid进行查询），由于这个key不存在于redis中，会导致缓存大量击穿，于是服务器会去请求mysql，但是在mysql中也找不到相应的记录。此时请求全都打在了mysql上，导致数据库压力剧增，甚至可能崩溃。该问题可以通过在redis存储null值解决。但当无用请求大量增多进行攻击时，会知道redis缓存中存储大量的null值数据，出现另外的问题。

这时候可以用布隆过滤器对请求进行过滤。只有在布隆过滤器中，才去查询数据库。如果不在布隆器中，则直接返回。避免了数据库的压力。

我们可以设计一个场景方案，如下：

![a3a917ec13ae4a3e9f93ae9e3c85dca8.png][]

请求进来后先在过滤器中进行查询，如果布隆过滤器判断编号**可能存在**，则直接去读取存储在 Redis 缓存中的数据；如果此时 Redis 缓存没有存在对应的商品数据，则直接去读取数据库，并将读取到的信息重新载入到 Redis 缓存中。如果布隆过滤器判断编号不存在，直接过滤该请求。

### 3.springboot集成布隆过滤器 ###

springboot中一般可以通过两种方式调用布隆过滤器（主要演示基于redission实现的布隆过滤器整套业务）：

（1）通过redission实现（需要先使用redis下载布隆过滤器插件）:

<dependency>
                <groupId>org.redisson</groupId>
                <artifactId>redisson</artifactId>
                <version>3.17.7</version>
            </dependency>

配置文件：

import org.redisson.Redisson;
    import org.redisson.api.RedissonClient;
    import org.redisson.config.Config;
    import org.springframework.beans.factory.annotation.Value;
    import org.springframework.context.annotation.Bean;
    import org.springframework.context.annotation.Configuration;
    
    @Configuration
    public class RedissonConfig {
    
        @Value("${spring.redis.host}")
        private String host;
    
        @Value("${spring.redis.port}")
        private String port;
    
        @Bean
        public RedissonClient getRedisson(){
    
            Config config = new Config();
            //单机模式  依次设置redis地址和密码
            config.useSingleServer().
                    setAddress("redis://" + host + ":" + port);
            return Redisson.create(config);
        }
    }

业务类（下面代码中整合了mybatis-plus和redission实现分布式锁下的数据查询，不熟悉可以不用修改为简单的数据库查询）：

import com.alibaba.fastjson.JSON;
    import com.alibaba.fastjson.TypeReference;
    import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
    import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl;
    import com.seven.springcloud.Pojo.Address;
    import com.seven.springcloud.dao.UserAddressMapper;
    import com.seven.springcloud.service.UserAddressService;
    import lombok.extern.slf4j.Slf4j;
    import org.redisson.api.*;
    import org.springframework.data.redis.core.StringRedisTemplate;
    import org.springframework.stereotype.Service;
    import org.springframework.util.StringUtils;
    
    import javax.annotation.Resource;
    import java.util.*;
    
    @Service
    @Slf4j
    public class UserAddressServiceImpl extends ServiceImpl<UserAddressMapper, Address> implements UserAddressService {
    
        @Resource
        private StringRedisTemplate stringRedisTemplate;
        @Resource
        private UserAddressMapper userAddressMapper;
        @Resource
        private RedissonClient redisson;
    
        //基于redission分布式锁下的mybatis-plus数据库查询
            public Map<String,Address> searchByDb(int id){
    
            Map<String,Address> map = new HashMap<>();
            RLock lock = redisson.getFairLock("myLock");       //获取锁
            try {
                lock.lock();    //上锁
                synchronized (this){
                    if(StringUtils.isEmpty(stringRedisTemplate.opsForValue().get("addressList"))){
                        log.info("查数据库");
                        Address address = userAddressMapper.selectById(id);
                        map.put("placeList",address);
                    }else {
                        log.info("缓存击中！");
                        return JSON.parseObject(stringRedisTemplate.opsForValue().get("addressList"),new TypeReference<Map<String,List<Address>>>(){});
                    }
                }
            }catch (Exception e){
                log.warn("系统错误，稍后重试");
            }
            finally {
                lock.unlock();    //删除锁
            }
    
            return map;
        }
    
        //添加数据
        public int bloomAdd(Address address) {
            //数据库中插入数据
            int result = userAddressMapper.insert(address);
            //插入成功，存入布隆过滤器中
            if(result > 0){
                //获取布隆过滤器
                RBloomFilter<Object> bloomFilter = redisson.getBloomFilter("idList");
                //初始化布隆过滤器(数据量，误差率)
                bloomFilter.tryInit(1000000L,0.02);
                //往过滤器中加入数据
                bloomFilter.add(address.getId());
            }
            return result;
        }
    
        //查询
        public Map<String,Address> bloomFilter(int id) {
    
            //获取布隆过滤器
            RBloomFilter<Object> bloomFilter = redisson.getBloomFilter("idList");
            //判断数据是否在过滤器中
            boolean flag = bloomFilter.contains(id);
            if(flag){
                //存在，查缓存
                String addressList = stringRedisTemplate.opsForValue().get("addressList");
                //判断缓存中是否存在
                if (StringUtils.isEmpty(addressList)){
                    log.info("缓存未命中");
                    //调用查询数据库的方法
                    Map<String,Address> map = searchByDb(id);
                    //封装查询结果
                    String result = JSON.toJSONString(map);
                    //以json格式存入redis中
                    stringRedisTemplate.opsForValue().set("addressList",result);
                    return map;
                }else {
                    log.info("缓存命中");
                    //直接返回缓存数据
                    return JSON.parseObject(addressList,new TypeReference<Map<String,Address>>(){});
                }
            }else {
                //过滤器不命中，过滤请求、
                log.info("请求被过滤");
                return null;
            }
        }
    
    }

如上所示：在插入数据时，将实体类的唯一id作为布隆过滤器值插入过滤器中，用以判断请求。

当用户发来请求时，会附加一个编号，如果布隆过滤器判断编号存在，则直接去读取存储在 Redis 缓存中的数据；如果此时 Redis 缓存没有存在对应的商品数据，则直接去读取数据库，并将读取到的信息重新载入到 Redis 缓存中。这样下一次用户在查询相同编号数据时，就可以直接读取缓存了

我们打开redis，可以看到如下key:

![f82581b1f26a4e6ab1a1dedf602fc980.png][]

其中idList是布隆过滤器存储的id编号；addressList是redis缓存的数据值；config 是布隆过滤器的相关依赖。

具体业务过程中，实体类的key值还需要有一定的区别，不该使用统一的String值（如上述代码中的addressList，主要是为了方便演示），可以使用字符+编号的形式，比如 Address:\{id\}，还需自行进行设计。

（2）使用GUAVA实现布隆过滤器

<dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>30.0-jre</version>
            </dependency>

下面是一个简单使用，可进行参考：

/**
     * Guava版布隆过滤器
     *
     */
    public class BloomFilterTest {
    
        /**
         * @param expectedInsertions 预期插入值
         *  这个值的设置相当重要，如果设置的过小很容易导致饱和而导致误报率急剧上升，如果设置的过大，也会对内存造成浪费，所以要根据实际情况来定
         * @param fpp                误差率，例如：0.001,表示误差率为0.1%
         * @return 返回true，表示可能存在，返回false一定不存在
         */
        public static boolean isExist(int expectedInsertions, double fpp) {
            // 创建布隆过滤器对象
            BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);
    
            // 判断指定元素是否存在
            System.out.println(filter.mightContain(10));
    
            // 将元素添加进布隆过滤器
            filter.put(10);
    
            // 再判断指定元素是否存在
            System.out.println(filter.mightContain(10));
            return filter.mightContain(10);
        }
    
        //主类中进行测试
        public static void main(String[] args) {
    
            boolean exist = isExist(100000000, 0.001);
        }
    }

### 4.总结 ###

布隆过滤器主要就是利用一个很长的二进制数组，通过一系列的hash函数来确定该数据是否存在。可以避免由于恶意用户在短时内大量查询不存在的数据，导致大量请求被送达数据库进行查询，当请求数量超过数据库负载上限时，使系统响应出现高延迟甚至瘫痪的问题。

**针对布隆过滤器误判的问题**，其实在大多数情况下，我们出现误判也不会对系统产生额外的影响。因为像刚才我们设置 0,02 的误判率，1 万次请求才可能会出现 200 次误判的情况。我们已经将大多数的无效请求进行了拦截。 所以我们不需要设置过低的误判率，而需要根据业务需求动态进行设置，避免执行时间过长。

**针对删除困难问题**，我们可以mybatis-plus中的逻辑删除。即不从表中删除某条记录，而是增加一个状态字段，将这行记录的状态字段设为已删除状态。这样可以一定程度上解决布隆过滤器的删除问题，也不会对其性能造成太大影响。如果追求更好的性能，可以使用布谷鸟过滤器，具体不在此处阐释。

[a1d34b7949284646a0e7c5dd9d757ad9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0490e73a014c41afa4d646e38b2bcc37.png
[2fe0355b2207401f999f7d70f76b82d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/2bd4e12d2972452d9eb93c2afe881a92.png
[a3a917ec13ae4a3e9f93ae9e3c85dca8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/df8699c7d93a4cae8657bc4b825a6805.png
[f82581b1f26a4e6ab1a1dedf602fc980.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7cdf9f549a114065b604e23061ec7c1c.png