写点什么

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

  • 2023-04-20
    湖南
  • 本文字数:3189 字

    阅读完需:约 10 分钟

一、布隆过滤器 BloomFilter 是什么

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


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

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

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


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


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


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

三、布隆过滤器使用场景

3.1 解决缓存穿透问题

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


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


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


完美解决缓存穿透问题。

3.2 黑名单

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

3.3 网页爬虫对 URL 的去重,避免爬取相同的 URL 地址

四、操作布隆过滤器 BloomFilter

4.1 使用布隆过滤器

(1)初始化 bitmap

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

(2)添加 key

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


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

4.2 删除 key

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

4.3 判断是否存在

向布隆过滤器查询某个 key 是否存在时,先把这个 key 通过相同的多个 hash 函数进行运算,查看对应的位置是否都为 1,只要有一个位为零,那么说明布隆过滤器中这个 key 不存在;


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


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

五、代码实例

5.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; }}
复制代码

5.2 布隆过滤器

import org.springframework.beans.factory.annotation.Autowired;import org.springframework.stereotype.Service;
/** * 布隆过滤器 -> redis -> mysql * @autor 哪吒编程 * @date 2023-04-17 */@Servicepublic 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. 当实际元素数量超过初始长度时,应该对布隆过滤器进行重建,再将所有的历史元素批量添加进去;


作者:哪吒编程

链接:https://juejin.cn/post/7223779544368496701

来源:稀土掘金

用户头像

还未添加个人签名 2021-07-28 加入

公众号:该用户快成仙了

评论

发布
暂无评论
Redis布隆过滤器的原理和应用场景,解决缓存穿透_Java_做梦都在改BUG_InfoQ写作社区