预防缓存击穿-布隆过滤器

为什么使用布隆过滤器

• 布隆过滤器是用来判断一个元素是否出现在给定集合中的重要工具,具有快速，比哈希表更节省空间等优点，而缺点在于有一定的误识别率

• 布隆过滤器(bloom filter)是Google Guava类库里面的组件

• 当代换联网环境下使用缓存的公司可说遍地都是大家都知道使用缓存就是为了缓存一些冷数据以减少数据库压力

• 查询一些缓存不存在的数据 透过缓存直接查询数据库

• 服务报错

  
  

布隆过滤器代码实现

• 代码实现

      package com.f.fmodules.fuser.bloom;
  
      import com.google.common.base.Charsets;
      import com.google.common.hash.BloomFilter;
      import com.google.common.hash.Funnels;
  
      import java.util.*;
  
      public class BloomFilterDemo {
  
          public static void main(String[] args) {
              final int count = 500000;
              List<String> stringList = new ArrayList<>(count);
              Set<String> stringSet = new HashSet<>();
              //创建布隆过滤器 初始化过滤器数据
              BloomFilter<String> bloomString = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),count);
              for (int i =0;i< count;i++){
                  String id = UUID.randomUUID().toString();
                  stringList.add(id);
                  stringSet.add(id);
                  bloomString.put(id);
              }
              int wrong = 0;
              int right = 0;
              for (int i =0;i< count; i++) {
                  String checkString = i % 100 == 0 ? stringList.get(i) : UUID.randomUUID().toString();
                  //布隆过滤器 进过hash算法和byte数组 校验是否存在于集合中
                  if (bloomString.mightContain(checkString)){
                      //校验是否误判
                      if (stringSet.contains(checkString)){
                          right++;
                      }else{
                          wrong++;
                      }
                  }
              }
              System.out.println("50万测试数据-->共抵挡: "+(count - wrong - right)+"次非法入侵"+"    误判"+wrong);
          }
      }
  
  

• 运行结果

  
  
• 为什么会有14721次误判呢 咱们跟进源码进行深入探索

  深入源码可发现 误判率在百分之三的情况下 有300多万个byte数组 会进行5次hash算法进行判断数据是否存在已知数据中

• 初始化布隆过滤器时设置误判率为0.01

      //创建布隆过滤器 初始化过滤器数据
      BloomFilter<String> bloomString = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),count,0.001);
  
  

• debug深入源码

  
  

  此时发现误判率设置为百分之一的情况下 byte数组达到七百多万 而需要进行的hash算法次数达到十次

• 查看运行结果

  
  

  结果可看出 误判率为百分之一的情况下 5000次正确访问 只有500多次误判(并不是设置的误判率越小越好 误判率越小 需要进行hash计算次数越多消耗资源越多)