欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题

程序员文章站 2022-05-08 11:20:45
...

1.什么是缓存穿透?

正常的查询数据库流程应该是先查缓存,如果缓存没有,再去查询数据库。当在数据库中查询完成后将查询的结果放入到缓存,这样下次请求的话就可以在缓存中获取到。那么缓存穿透就是类似于一种恶意攻击,例如数据库中存在id为1,2,3,4,5一共5条数据,如果一个请求查询id为6的数据,很明显这个数据缓存中没有,那么就会去查询数据库,但是数据库中也没有,那这样就造成了缓存穿透。如果这个请求一直在向服务器发送查询,则会给数据库带来很大的压力。

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题
2.什么是布隆过滤器?

布隆过滤器(Bloom Filter)它实际上是一个很长的二进制向量和一系列随机映射函数,二进制大家应该都清楚,存储的数据不是0就是1,默认是0。
主要用于判断一个元素是否在一个集合中,0代表不存在某个数据,1代表存在某个数据。
一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题布隆过滤器是一个二进制的数组,只存储0和1。

  • 布隆过滤器存入数据的过程。

    1.通过K个哈希函数计算该数据,返回K个计算出的hash值
    2.这些K个hash值映射到对应的K个二进制的数组下标
    3.将K个下标对应的二进制数据改成1。

如图所示:

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题

  • 布隆过滤器查询数据的过程

· 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中的,我们看他的误判数。

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题
947约等于1000,也就是0.01。

  • 将误判率改为0.00再测试

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题其测试结果也是大差不差的。

  • 误判率的原理是什么?

(1)将误判率改为0.01,以Debug模式进入布隆过滤器的create方法。

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题

我们发现numBits为9585058 , numHashFunctions为7 ,
numBits就是这个布隆过滤器占用的内存空间,numHashFunctions表示插入数据时对这个数据进行几次hash运算。

(2)将误判率改为0.001,以Debug模式进入布隆过滤器的create方法。

一文搞懂布隆过滤器以及如何解决Redis的缓存穿透问题

我们发现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,放入过滤器。