一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题
1.什么是缓存穿透?
正常的查询数据库流程应该是先查缓存,如果缓存没有,再去查询数据库。当在数据库中查询完成后将查询的结果放入到缓存,这样下次请求的话就可以在缓存中获取到。那么缓存穿透就是类似于一种恶意攻击,例如数据库中存在id为1,2,3,4,5一共5条数据,如果一个请求查询id为6的数据,很明显这个数据缓存中没有,那么就会去查询数据库,但是数据库中也没有,那这样就造成了缓存穿透。如果这个请求一直在向服务器发送查询,则会给数据库带来很大的压力。
2.什么是布隆过滤器?
布隆过滤器(Bloom Filter)它实际上是一个很长的二进制向量和一系列随机映射函数,二进制大家应该都清楚,存储的数据不是0就是1,默认是0。
主要用于判断一个元素是否在一个集合中,0代表不存在某个数据,1代表存在某个数据。
布隆过滤器是一个二进制的数组,只存储0和1。
-
布隆过滤器存入数据的过程。
1.通过K个哈希函数计算该数据,返回K个计算出的hash值
2.这些K个hash值映射到对应的K个二进制的数组下标
3.将K个下标对应的二进制数据改成1。
如图所示:
- 布隆过滤器查询数据的过程
· 1.对这个数据进行多次hash运算
2.查看运算结果的下标位置的数据是否为1,如果都为1则说明不一定存在,如果有一个不为1,则说明一定不存在。
布隆过滤器判断不存在的一定不存在,判断存在可能不存在,可能存在。这里存在一个误判率的问题
- 为什么会存在误判率问题?
根本原因还是因为hash函数的算法原理,两个不同的数据经过hash函数运算得到的结果可能是相同的。
3.使用布隆过滤器
- 引入依赖
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
- 编写测试类
public class BloomFilterCase {
/**
* 预计要插入多少数据
*/
private static int size = 1000000;
/**
* 期望的误判率
*/
private static double fpp = 0.01;
/**
* 布隆过滤器
*/
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
// 插入10万样本数据
for (int i = 0; i < size; i++) {
bloomFilter.put(i);
}
// 用另外十万测试数据,测试误判率
int count = 0;
for (int i = size; i < size + 100000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
}
这里我们插,1 - 100W数据,预计误判率为0.01,我们从1000001-1100000测试,后10W条数据肯定是不存在1-1000000中的,我们看他的误判数。
947约等于1000,也就是0.01。
- 将误判率改为0.00再测试
其测试结果也是大差不差的。
- 误判率的原理是什么?
(1)将误判率改为0.01,以Debug模式进入布隆过滤器的create方法。
我们发现numBits为9585058 , numHashFunctions为7 ,
numBits就是这个布隆过滤器占用的内存空间,numHashFunctions表示插入数据时对这个数据进行几次hash运算。
(2)将误判率改为0.001,以Debug模式进入布隆过滤器的create方法。
我们发现numBits为 14377587, numHashFunctions为 10,也就是说我们误判率设置的越小,这个二进制向量占用的内存空间就越大,某个数据进行插入的时候经过的hash运算就更多,因为这样才能尽可能将数据保存在多个下标位置。
4.解决缓存穿透
- 引入redisson
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.13.4</version>
</dependency>
- 配置
@Configuration
public class RedissonConfig {
@Bean
public RedissonClient redissonClient(){
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
return Redisson.create(config);
}
}
- 布隆过滤器的封装类
@Component
public class BloomFilterUtils {
@Autowired
private RedissonClient redisson;
private RBloomFilter<Long> bloomFilter;
@PostConstruct
private void initBloomFilter(){
this.bloomFilter = redisson.getBloomFilter("Id_List");
//初始化布隆过滤器:预计元素为10000L,误差率为3%
this.bloomFilter.tryInit(10000L,0.03);
}
public boolean isContains(Long id){
return this.bloomFilter.contains(id);
}
public void put(Long id){
this.bloomFilter.add(id);
}
}
首先可以用isContains方法进行判断某个id存在与否,如果存在则直接返回,再进行查询数据库,如果数据库中不存在,则将这个id,放入过滤器。
上一篇: 数据库建表遇到的一些问题
下一篇: spider----51job实战