Redis布隆过滤器的原理和应用场景，解决缓存穿透

电玩女神 2023-09-26 21:32 107阅读 0赞

## 一、布隆过滤器BloomFilter是什么 ##

布隆过滤器BloomFilter是一种专门用来解决去重问题的高级数据结果。

实质就是一个大型位数组和几个不同的无偏hash函数，无偏表示分布均匀。由一个初值为零的bit数组和多个哈希函数组成，用来判断某个数据是否存在，它和HyperLogLog一样，不是那么的精准，存在一定的误判概率。

## 二、布隆过滤器BloomFilter能干嘛？ ##

![format_png][]

高效地插入和查询，占用空间少，返回的结果是不确定的，一个元素如果判断结果为存在，它不一定存在；不存在时，一定不存在。

**因为不同的字符串的hashcode可能相同，布隆过滤器BloomFilter是根据hashcode判断的，如果某个hashcode存在，它对应的字符串不一定是你想要的那个字符串；但是，hashcode不存在时，你所要的字符串，肯定不存在，细品~**

布隆过滤器BloomFilter只能添加元素，不能删除元素。

这和上面提到的hashcode判定原理是一样的，相同hashcode的字符串会存储在一个index，删除时，是将某个index移除，此时，就可能移除拥有相同hashcode的不同字符串，细品~

## 三、布隆过滤器使用场景 ##

### 1、解决缓存穿透问题 ###

一般情况下，先查询Redis缓存，如果Redis中没有，再查询MySQL。当数据库中也不存在这条数据时，每次查询都要访问数据库，这就是缓存穿透。

在Redis前面添加一层布隆过滤器，请求先在布隆过滤器中判断，如果布隆过滤器不存在时，直接返回，不再反问Redis和MySQL。

如果布隆过滤器中存在时，再访问Redis，再访问数据库。

完美解决缓存穿透问题。

![format_png 1][]

### 2、黑名单 ###

如果黑名单非常大，上千万了，存放起来很耗费空间，在布隆过滤器中实现黑名单功能，是一个很好的选择。

### 3、网页爬虫对URL的去重，避免爬取相同的URL地址 ###

## 四、操作布隆过滤器BloomFilter ##

### 1、使用布隆过滤器 ###

（1）初始化bitmap

布隆过滤器 本质上 是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0。

![format_png 2][]

（2）添加key

使用多个hash函数对key进行hash运算，得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置的值置为1就表示添加成功。

例如，我们添加一个字符串“哪吒编程”，对字符串进行多次hash(key) → 取模运行→ 得到坑位。

![format_png 3][]

### 2、删除key ###

只要有其中一位是零就表示这个key不存在，但如果都是1，则不一定存在对应的key。

### 3、判断是否存在 ###

向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算，查看对应的位置是否都为 1，

只要有一个位为零，那么说明布隆过滤器中这个 key 不存在；

如果这几个位置全都是 1，那么说明极有可能存在；

因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的hash冲突

## 五、代码实例 ##

### 1、使用Redis做缓存 ###

public class StudentSerivce {
        public static final String CACHE_KEY = "student:";
    
        @Resource
        private StudentMapper studentMapper;
        @Resource
        private RedisTemplate redisTemplate;
    
        public void addstudent(Student student){
            int i = studentMapper.insertStudent(student);
    
            if(i > 0)
            {
                //到数据库里面，重新捞出新数据出来，做缓存
                student=studentMapper.selectByKey(student.getId());
                //缓存key
                String key=CACHE_KEY+student.getId();
                //往mysql里面插入成功随后再从mysql查询出来，再插入redis
                redisTemplate.opsForValue().set(key,student);
            }
        }
    
        public Student findstudentById(Integer studentId){
            Student student = null;
            String key=CACHE_KEY+studentId;
            // 查询redis
            student = (Student) redisTemplate.opsForValue().get(key);
            // redis没有，查询mysql
            if(student==null){
                // 从mysql查出来student
                student=studentMapper.selectByPrimaryKey(studentId);
                // mysql有，redis没有
                if (student != null) {
                    // mysql的数据写入redis
                    redisTemplate.opsForValue().set(key,student);
                }
            }
            return student;
        }
    }
    复制代码

### 2、布隆过滤器 ###

import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.stereotype.Service;
    
    /**
     * 布隆过滤器 -> redis -> mysql
     * @autor 哪吒编程
     * @date 2023-04-17
     */
    @Service
    public class StudentServiceImpl implements StudentService {
        public static final String CACHE_KEY = "student:";
    
        @Autowired
        private StudentMapper studentMapper;
    
        @Autowired
        private RedisTemplate redisTemplate;
    
        public void addstudent(student student){
            int i = studentMapper.insertSelective(student);
    
            if(i > 0) {
                //到数据库里面，重新捞出新数据出来，做缓存
                student=studentMapper.selectByPrimaryKey(student.getId());
                //缓存key
                String key=CACHE_KEY+student.getId();
                //往mysql里面插入成功随后再从mysql查询出来，再插入redis
                redisTemplate.opsForValue().set(key,student);
            }
        }
    
        public student findstudentById(Integer studentId){
            student student = null;
    
            //缓存key的名称
            String key=CACHE_KEY+studentId;
    
            // 查询redis
            student = (student) redisTemplate.opsForValue().get(key);
    
            //redis没有，查询mysql
            if(student==null) {
                student=studentMapper.selectByPrimaryKey(studentId);
                // mysql有，redis没有
                if (student != null) {
                    // 把mysql捞到的数据写入redis
                    redisTemplate.opsForValue().set(key,student);
                }
            }
            return student;
        }
    
        /**
         * BloomFilter -> redis -> mysql
         * 白名单：whites
         */
        public student findStudentByIdWithBloomFilter (Integer studentId) {
            student student = null;
    
            String key = CACHE_KEY + studentId;
    
            //布隆过滤器校验，无是绝对无，有是可能有
            if(!checkWithBloomFilter("whites",key)) {
                log.info("白名单无此顾客信息:{}",key);
                return null;
            }
    
            //查询redis
            student = (Student) redisTemplate.opsForValue().get(key);
            //redis没有，查询mysql
            if (student == null) {
                student = studentMapper.selectByPrimaryKey(studentId);
                // mysql有，redis没有
                if (student != null) {
                    // 把mysql捞到的数据写入redis
                    redisTemplate.opsForValue().set(key, student);
                }
            }
            return student;
        }
    
        /**
         * 查询布隆过滤器中是否存在
         */
        public boolean checkWithBloomFilter(String checkItem,String key) {
            int hashValue = Math.abs(key.hashCode());
            long index = (long) (hashValue % Math.pow(2, 32));
            return redisTemplate.opsForValue().getBit(checkItem, index);
        }
    }
    
    复制代码

## 六、总结 ##

1.  有，是可能有；无，是肯定无；
2.  使用时z，初始化值尽可能满足实际元素长度，避免扩容；
3.  当实际元素数量超过初始长度时，应该对布隆过滤器进行重建，再将所有的历史元素批量添加进去；

[format_png]: https://img-blog.csdnimg.cn/img_convert/ca8722adcdca5c3d88876f8541f5505b.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/28918e5b29b1bd3bf48ad37753fc1ee1.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/d09237b0d30c23178a99a9a84dfe8d04.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/cae6d6b617945000b30c2dd35f807b2a.webp?x-oss-process=image/format,png