建站
咨詢
售后
建站咨詢
新聞中心
今天分享一下Redis布隆過濾器的原理和應(yīng)用場(chǎng)景，解決緩存穿透，實(shí)現(xiàn)快速入門，豐富個(gè)人簡(jiǎn)歷，提高面試level，給自己增加一點(diǎn)談資，秒變面試小達(dá)人，BAT不是夢(mèng)。
一、布隆過濾器BloomFilter是什么
布隆過濾器BloomFilter是一種專門用來解決去重問題的高級(jí)數(shù)據(jù)結(jié)果。
實(shí)質(zhì)就是一個(gè)大型位數(shù)組和幾個(gè)不同的無偏hash函數(shù)，無偏表示分布均勻。由一個(gè)初值為零的bit數(shù)組和多個(gè)哈希函數(shù)組成，用來判斷某個(gè)數(shù)據(jù)是否存在，它和HyperLogLog一樣，不是那么的精準(zhǔn)，存在一定的誤判概率。
二、布隆過濾器BloomFilter能干嘛？
高效地插入和查詢，占用空間少，返回的結(jié)果是不確定的，一個(gè)元素如果判斷結(jié)果為存在，它不一定存在；不存在時(shí)，一定不存在。
因?yàn)椴煌淖址膆ashcode可能相同，布隆過濾器BloomFilter是根據(jù)hashcode判斷的，如果某個(gè)hashcode存在，它對(duì)應(yīng)的字符串不一定是你想要的那個(gè)字符串；但是，hashcode不存在時(shí)，你所要的字符串，肯定不存在，細(xì)品~
布隆過濾器BloomFilter只能添加元素，不能刪除元素。
這和上面提到的hashcode判定原理是一樣的，相同hashcode的字符串會(huì)存儲(chǔ)在一個(gè)index，刪除時(shí)，是將某個(gè)index移除，此時(shí)，就可能移除擁有相同hashcode的不同字符串，細(xì)品~
三、布隆過濾器使用場(chǎng)景
1、解決緩存穿透問題
一般情況下，先查詢Redis緩存，如果Redis中沒有，再查詢MySQL。當(dāng)數(shù)據(jù)庫(kù)中也不存在這條數(shù)據(jù)時(shí)，每次查詢都要訪問數(shù)據(jù)庫(kù)，這就是緩存穿透。
在Redis前面添加一層布隆過濾器，請(qǐng)求先在布隆過濾器中判斷，如果布隆過濾器不存在時(shí)，直接返回，不再反問Redis和MySQL。
如果布隆過濾器中存在時(shí)，再訪問Redis，再訪問數(shù)據(jù)庫(kù)。
完美解決緩存穿透問題。
2、黑名單
如果黑名單非常大，上千萬了，存放起來很耗費(fèi)空間，在布隆過濾器中實(shí)現(xiàn)黑名單功能，是一個(gè)很好的選擇。
3、網(wǎng)頁爬蟲對(duì)URL的去重，避免爬取相同的URL地址
四、操作布隆過濾器BloomFilter
1、使用布隆過濾器
（1）初始化bitmap
布隆過濾器 本質(zhì)上 是由長(zhǎng)度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有的值均設(shè)置為 0。
（2）添加key
使用多個(gè)hash函數(shù)對(duì)key進(jìn)行hash運(yùn)算，得到一個(gè)整數(shù)索引值，對(duì)位數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算得到一個(gè)位置，每個(gè)hash函數(shù)都會(huì)得到一個(gè)不同的位置，將這幾個(gè)位置的值置為1就表示添加成功。
例如，我們添加一個(gè)字符串“哪吒編程”，對(duì)字符串進(jìn)行多次hash(key) → 取模運(yùn)行→ 得到坑位。
2、刪除key
只要有其中一位是零就表示這個(gè)key不存在，但如果都是1，則不一定存在對(duì)應(yīng)的key。
3、判斷是否存在
向布隆過濾器查詢某個(gè)key是否存在時(shí)，先把這個(gè) key 通過相同的多個(gè) hash 函數(shù)進(jìn)行運(yùn)算，查看對(duì)應(yīng)的位置是否都為 1，
只要有一個(gè)位為零，那么說明布隆過濾器中這個(gè) key 不存在；
如果這幾個(gè)位置全都是 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ù)庫(kù)里面，重新?lián)瞥鲂聰?shù)據(jù)出來，做緩存
student=studentMapper.selectByKey(student.getId());
//緩存key
String key=CACHE_KEY+student.getId();
//往mysql里面插入成功隨后再?gòu)膍ysql查詢出來，再插入redis
redisTemplate.opsForValue().set(key,student);
}
}
public Student findstudentById(Integer studentId){
Student student = null;
String key=CACHE_KEY+studentId;
// 查詢r(jià)edis
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ù)庫(kù)里面，重新?lián)瞥鲂聰?shù)據(jù)出來，做緩存
student=studentMapper.selectByPrimaryKey(student.getId());
//緩存key
String key=CACHE_KEY+student.getId();
//往mysql里面插入成功隨后再?gòu)膍ysql查詢出來，再插入redis
redisTemplate.opsForValue().set(key,student);
}
}
public student findstudentById(Integer studentId){
student student = null;
//緩存key的名稱
String key=CACHE_KEY+studentId;
// 查詢r(jià)edis
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)，無是絕對(duì)無，有是可能有
if(!checkWithBloomFilter("whites",key)) {
log.info("白名單無此顧客信息:{}",key);
return null;
}
//查詢r(jià)edis
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é)
- 有，是可能有；無，是肯定無。
- 使用時(shí)z，初始化值盡可能滿足實(shí)際元素長(zhǎng)度，避免擴(kuò)容。
- 當(dāng)實(shí)際元素?cái)?shù)量超過初始長(zhǎng)度時(shí)，應(yīng)該對(duì)布隆過濾器進(jìn)行重建，再將所有的歷史元素批量添加進(jìn)去。
本文轉(zhuǎn)載自微信公眾號(hào)「哪吒編程」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系哪吒編程公眾號(hào)。
分享標(biāo)題：Redis布隆過濾器的原理和應(yīng)用場(chǎng)景，解決緩存穿透
轉(zhuǎn)載源于：http://www.5511xx.com/article/dhjheis.html
