Redis布隆過濾器的原理和應(yīng)用場景，解決緩存穿透

作者：哪吒 2023-04-26 08:32:45

布隆過濾器BloomFilter是一種專門用來解決去重問題的高級數(shù)據(jù)結(jié)果。

今天分享一下Redis布隆過濾器的原理和應(yīng)用場景，解決緩存穿透，實(shí)現(xiàn)快速入門，豐富個人簡歷，提高面試level，給自己增加一點(diǎn)談資，秒變面試小達(dá)人，BAT不是夢。

一、布隆過濾器BloomFilter是什么

布隆過濾器BloomFilter是一種專門用來解決去重問題的高級數(shù)據(jù)結(jié)果。

實(shí)質(zhì)就是一個大型位數(shù)組和幾個不同的無偏hash函數(shù)，無偏表示分布均勻。由一個初值為零的bit數(shù)組和多個哈希函數(shù)組成，用來判斷某個數(shù)據(jù)是否存在，它和HyperLogLog一樣，不是那么的精準(zhǔn)，存在一定的誤判概率。

二、布隆過濾器BloomFilter能干嘛？

高效地插入和查詢，占用空間少，返回的結(jié)果是不確定的，一個元素如果判斷結(jié)果為存在，它不一定存在；不存在時，一定不存在。

因?yàn)椴煌淖址膆ashcode可能相同，布隆過濾器BloomFilter是根據(jù)hashcode判斷的，如果某個hashcode存在，它對應(yīng)的字符串不一定是你想要的那個字符串；但是，hashcode不存在時，你所要的字符串，肯定不存在，細(xì)品~

布隆過濾器BloomFilter只能添加元素，不能刪除元素。

這和上面提到的hashcode判定原理是一樣的，相同hashcode的字符串會存儲在一個index，刪除時，是將某個index移除，此時，就可能移除擁有相同hashcode的不同字符串，細(xì)品~

三、布隆過濾器使用場景

1、解決緩存穿透問題

一般情況下，先查詢Redis緩存，如果Redis中沒有，再查詢MySQL。當(dāng)數(shù)據(jù)庫中也不存在這條數(shù)據(jù)時，每次查詢都要訪問數(shù)據(jù)庫，這就是緩存穿透。

在Redis前面添加一層布隆過濾器，請求先在布隆過濾器中判斷，如果布隆過濾器不存在時，直接返回，不再反問Redis和MySQL。

如果布隆過濾器中存在時，再訪問Redis，再訪問數(shù)據(jù)庫。

完美解決緩存穿透問題。

2、黑名單

如果黑名單非常大，上千萬了，存放起來很耗費(fèi)空間，在布隆過濾器中實(shí)現(xiàn)黑名單功能，是一個很好的選擇。

3、網(wǎng)頁爬蟲對URL的去重，避免爬取相同的URL地址

四、操作布隆過濾器BloomFilter

1、使用布隆過濾器

（1）初始化bitmap

布隆過濾器本質(zhì)上是由長度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有的值均設(shè)置為 0。

（2）添加key

使用多個hash函數(shù)對key進(jìn)行hash運(yùn)算，得到一個整數(shù)索引值，對位數(shù)組長度進(jìn)行取模運(yùn)算得到一個位置，每個hash函數(shù)都會得到一個不同的位置，將這幾個位置的值置為1就表示添加成功。

例如，我們添加一個字符串“哪吒編程”，對字符串進(jìn)行多次hash(key) → 取模運(yùn)行→ 得到坑位。

2、刪除key

只要有其中一位是零就表示這個key不存在，但如果都是1，則不一定存在對應(yīng)的key。

3、判斷是否存在

向布隆過濾器查詢某個key是否存在時，先把這個 key 通過相同的多個 hash 函數(shù)進(jìn)行運(yùn)算，查看對應(yīng)的位置是否都為 1，

只要有一個位為零，那么說明布隆過濾器中這個 key 不存在；

如果這幾個位置全都是 1，那么說明極有可能存在；

因?yàn)檫@些位置的 1 可能是因?yàn)槠渌?key 存在導(dǎo)致的，也就是前面說過的hash沖突

五、代碼實(shí)例

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)
        {
            //到數(shù)據(jù)庫里面，重新?lián)瞥鲂聰?shù)據(jù)出來，做緩存
            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的數(shù)據(jù)寫入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) {
            //到數(shù)據(jù)庫里面，重新?lián)瞥鲂聰?shù)據(jù)出來，做緩存
            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撈到的數(shù)據(jù)寫入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;

        //布隆過濾器校驗(yàn)，無是絕對無，有是可能有
        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撈到的數(shù)據(jù)寫入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);
    }
}