目录
使用布隆过滤器解决缓存穿透的问题(使用之前注意加入依赖和配置类)
什么是布隆过滤器
布隆过滤器(Bloom Filter)是一种概率型数据结构,用于检测某个元素是否在集合中。其特点是能够快速判断元素是否存在,但可能出现假阳性,即可能错误地报告某元素存在,但绝不会错过实际存在的元素。它通过使用多个哈希函数将元素映射到一个位数组中,当查询时,检查所有相关位是否为1。如果所有位均为1,则元素可能存在;否则,元素肯定不存在。由于其高效性和低空间需求,布隆过滤器常用于大规模数据集的去重和查询优化。
优点
- 空间效率高
:布隆过滤器在存储大量数据时,所需的空间相比其他数据结构(如哈希表或集合)要小得多。它使用一个位数组和多个哈希函数来表示集合,从而显著减少了内存占用。
- 查询效率高
:查询操作非常快速。布隆过滤器可以在常量时间内(O(k),其中k为哈希函数的数量)判断元素是否可能存在。这个特性使得布隆过滤器特别适合于需要高性能查询的场景。
- 不需要存储数据
:布隆过滤器只存储哈希值对应的位信息,而不直接存储元素本身,因此它节省了存储空间。
- 支持大规模数据处理
:在需要处理非常大的数据集合(如网络爬虫、大数据处理系统等)时,布隆过滤器的空间效率可以极大地减轻存储压力。
缺点
- 假阳性
:布隆过滤器可能错误地报告某个元素存在(即假阳性),这意味着它会告知某个元素可能在集合中,但实际上可能并不存在。假阳性的概率随着元素的增加和布隆过滤器的填满而增加。
- 无法删除元素
:标准的布隆过滤器不支持删除操作。一旦一个元素被添加,无法从布隆过滤器中移除它。删除操作会破坏布隆过滤器的准确性,因为这可能会影响到其他元素的查询结果。
- 确定假阳性率需要设置参数
:布隆过滤器的性能依赖于正确的参数设置(位数组大小和哈希函数数量)。如果这些参数设置不当,可能会导致较高的假阳性率或者空间浪费。
- 无法给出具体元素的存在信息
:布隆过滤器只能判断元素是否可能存在,不能提供有关元素的具体信息或位置。如果需要对元素进行更多的操作(如获取实际数据),布隆过滤器就不适用了。
布隆过滤器的使用场景
布隆过滤器适用于以下场景:
- 缓存系统:用于快速检查缓存是否包含某个数据,减少不必要的数据库查询。
- 去重:在大规模数据处理中,例如网页爬虫或日志分析,用于避免重复记录。
- 网络安全:用于过滤恶意请求或防止垃圾邮件,快速检测是否已知恶意源。
- 数据库优化:在大型数据库中使用布隆过滤器加速查询操作,减少对存储的访问。
使用步骤
依赖
<!-- 布隆过滤器依赖-->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>27.0.1-jre</version>
</dependency>
配置类
package com.bawei.config;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import java.nio.charset.Charset;
/**
* @author: 作者
* @create: 2024-07-05 11:02
* @Description: Spring3.0时代配置类创建对象
*/
@Configuration
public class BloomFilterConfig {
@Bean
public BloomFilter<String> stringBloomFilter(){
Charset charset = Charset.forName("UTF-8");
BloomFilter<String> strBloomFilter = BloomFilter.create(Funnels.stringFunnel(charset),1000000, 0.03);
return strBloomFilter;
}
@Bean
public BloomFilter<Integer> integerBloomFilter(){
BloomFilter<Integer> integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(),1000000, 0.03);
return integerBloomFilter;
}
}
使用布隆过滤器实现去重功能(使用之前注意加入依赖和配置类)
将数据存储到布隆过滤器中
@Autowired
private BloomFilter integerBloomFilter;
//循环集合将id存放到布隆过滤器
for (Hospital hos: list) {
integerBloomFilter.put(hos.getHospitalId());
}
从布隆过滤器中拿出来进行判断
//判断id是否存在
boolean b = integerBloomFilter.mightContain(hospitalId);
if(!b){
return Result.res(Res.IS_NOT_ID,null);
}
使用布隆过滤器解决缓存穿透的问题(使用之前注意加入依赖和配置类)
查询bloomfilter是否存在id
boolean b = integerBloomFilter.mightContain(id);
if(!b){
return R.ok(ResultCodeAndMsg.ERROR).msg("id不存在");
}
//1先查缓存
Object o = redisTemplate.opsForValue().get("ar:reader:" + id);
//2 是否命中,如果命中直接返回
if(null!=o){
return R.ok(ResultCodeAndMsg.AR_GET_SUCCESS,o).msg("id查询成功");
}
//分布式锁===>Redission分布式锁[看门狗]===>lua脚本保证原子性
//如果能设置成功,返回true,加锁成功
Boolean flag = redisTemplate.opsForValue().setIfAbsent("lock:ar:" + id, 1,2, TimeUnit.MINUTES);
if(!flag) { //没有获取锁
//等待2秒钟
try {
Thread.sleep(2000);
//重新执行方法
getArById(id);
return null;
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//3 未命中查询数据库
Articles articles = articlesMapper.selectById(id); //3分钟
//4 存入缓存
redisTemplate.opsForValue().set("ar:reader:" + id, articles);
//手动释放锁
redisTemplate.delete("lock:ar:" + id);
return R.ok(ResultCodeAndMsg.AR_GET_SUCCESS,articles).msg("id查询成功");
标签:元素,布隆,查询,过滤器,BloomFilter,id
From: https://blog.csdn.net/2301_81405087/article/details/142767770