Redis布隆過濾器的原理和應(yīng)用場景，解決緩存穿透
今天分享一下Redis布隆過濾器的原理和應(yīng)用場景，解決緩存穿透，實現(xiàn)快速入門，豐富個人簡歷，提高面試level，給自己增加一點談資，秒變面試小達人，BAT不是夢。
一、布隆過濾器BloomFilter是什么
布隆過濾器BloomFilter是一種專門用來解決去重問題的高級數(shù)據(jù)結(jié)果。
實質(zhì)就是一個大型位數(shù)組和幾個不同的無偏hash函數(shù)，無偏表示分布均勻。由一個初值為零的bit數(shù)組和多個哈希函數(shù)組成，用來判斷某個數(shù)據(jù)是否存在，它和HyperLogLog一樣，不是那么的精準(zhǔn)，存在一定的誤判概率。
二、布隆過濾器BloomFilter能干嘛？
高效地插入和查詢，占用空間少，返回的結(jié)果是不確定的，一個元素如果判斷結(jié)果為存在，它不一定存在；不存在時，一定不存在。
因為不同的字符串的hashcode可能相同，布隆過濾器BloomFilter是根據(jù)hashcode判斷的，如果某個hashcode存在，它對應(yīng)的字符串不一定是你想要的那個字符串；但是，hashcode不存在時，你所要的字符串，肯定不存在，細品~
布隆過濾器BloomFilter只能添加元素，不能刪除元素。
這和上面提到的hashcode判定原理是一樣的，相同hashcode的字符串會存儲在一個index，刪除時，是將某個index移除，此時，就可能移除擁有相同hashcode的不同字符串，細品~
三、布隆過濾器使用場景
1、解決緩存穿透問題
一般情況下，先查詢Redis緩存，如果Redis中沒有，再查詢MySQL。當(dāng)數(shù)據(jù)庫中也不存在這條數(shù)據(jù)時，每次查詢都要訪問數(shù)據(jù)庫，這就是緩存穿透。
在Redis前面添加一層布隆過濾器，請求先在布隆過濾器中判斷，如果布隆過濾器不存在時，直接返回，不再反問Redis和MySQL。
如果布隆過濾器中存在時，再訪問Redis，再訪問數(shù)據(jù)庫。
完美解決緩存穿透問題。
2、黑名單
如果黑名單非常大，上千萬了，存放起來很耗費空間，在布隆過濾器中實現(xiàn)黑名單功能，是一個很好的選擇。
3、網(wǎng)頁爬蟲對URL的去重，避免爬取相同的URL地址
四、操作布隆過濾器BloomFilter
1、使用布隆過濾器
（1）初始化bitmap
布隆過濾器 本質(zhì)上 是由長度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有的值均設(shè)置為 0。
（2）添加key
使用多個hash函數(shù)對key進行hash運算，得到一個整數(shù)索引值，對位數(shù)組長度進行取模運算得到一個位置，每個hash函數(shù)都會得到一個不同的位置，將這幾個位置的值置為1就表示添加成功。
例如，我們添加一個字符串“哪吒編程”，對字符串進行多次hash(key) → 取模運行→ 得到坑位。
2、刪除key
只要有其中一位是零就表示這個key不存在，但如果都是1，則不一定存在對應(yīng)的key。
3、判斷是否存在
向布隆過濾器查詢某個key是否存在時，先把這個 key 通過相同的多個 hash 函數(shù)進行運算，查看對應(yīng)的位置是否都為 1，
只要有一個位為零，那么說明布隆過濾器中這個 key 不存在；
如果這幾個位置全都是 1，那么說明極有可能存在；
因為這些位置的 1 可能是因為其他的 key 存在導(dǎo)致的，也就是前面說過的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)
{
//到數(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;
//布隆過濾器校驗，無是絕對無，有是可能有
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);
}
}六、總結(jié)
- 有，是可能有；無，是肯定無。
- 使用時z，初始化值盡可能滿足實際元素長度，避免擴容。
- 當(dāng)實際元素數(shù)量超過初始長度時，應(yīng)該對布隆過濾器進行重建，再將所有的歷史元素批量添加進去。
本文轉(zhuǎn)載自微信公眾號「哪吒編程」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系哪吒編程公眾號。
