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

大家好，我是哪吒。

一、布隆过滤器BloomFilter是什么

布隆过滤器BloomFilter是一种专门用来处理去重问题的高档数据成果。

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

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

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

因为不同的字符串的hashcode或许相同，布隆过滤器BloomFilter是根据hashcode判别的，假如某个hashcode存在，它对应的字符串不一定是你想要的那个字符串；可是，hashcode不存在时，你所要的字符串，必定不存在，细品~

布隆过滤器BloomFilter只能增加元素，不能删去元素。

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

三、布隆过滤器运用场景

1、处理缓存穿透问题

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

在Redis前面增加一层布隆过滤器，恳求先在布隆过滤器中判别，假如布隆过滤器不存在时，直接回来，不再反诘Redis和MySQL。

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

完美处理缓存穿透问题。

2、黑名单

假如黑名单非常大，上千万了，寄存起来很消耗空间，在布隆过滤器中完成黑名单功用，是一个很好的选择。

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

四、操作布隆过滤器BloomFilter

1、运用布隆过滤器

（1）初始化bitmap

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

（2）增加key

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

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

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);
    }
}

六、总结

有，是或许有；无，是必定无；
运用时z，初始化值尽或许满足实践元素长度，避免扩容；
当实践元素数量超越初始长度时，应该对布隆过滤器进行重建，再将一切的历史元素批量增加进去；

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