什么是布隆过滤器

布隆过滤器(Bloom Filter),是1970年,由一个叫布隆的小伙子提出的,距今已经五十年了。

它实际上是一个很长的二进制向量和一系列随机映射函数,二进制大家应该都清楚,存储的数据不是0就是1,默认是0。

主要用于判断一个元素是否在一个集合中,0代表不存在某个数据,1代表存在某个数据。

image-20201027212530487

布隆过滤器用途

  1. 解决Redis缓存穿透 ⭐️
  2. 在爬虫时,对爬虫网址进行过滤,已经存在布隆中的网址,不在爬取。
  3. 垃圾邮件过滤,对每一个发送邮件的地址进行判断是否在布隆的黑名单中,如果在就判断为垃圾邮件。

布隆过滤器原理

存入过程

布隆过滤器上面说了,就是一个二进制数据的集合。当一个数据加入这个集合时,经历如下步骤(这里有缺点,下面会讲):

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

例如,第一个哈希函数返回3,第二个第三个哈希函数返回5与7,那么:3、5、7对应的二进制改成1。

image-20201027214556447

查询过程

布隆过滤器主要作用就是查询一个数据,在不在这个二进制的集合中,查询过程如下:

  1. 通过K个哈希函数计算该数据,对应计算出的K个hash值
  2. 通过hash值找到对应的二进制的数组下标
  3. 判断:如果存在一处位置的二进制数据是0,那么该数据不存在。如果都是1,该数据存在集合中。(这里有缺点,下面会讲)

删除过程

一般不能删除布隆过滤器里的数据,这是一个缺点之一,我们下面会分析。

布隆过滤器的优缺点

优点

  • 由于存储的是二进制数据,所以占用的空间很小
  • 它的插入和查询速度是非常快的,时间复杂度是O(K),可以联想一下HashMap的过程
  • 保密性很好,因为本身不存储任何原始数据,只有二进制数据

缺点

添加数据是通过计算数据的hash值,那么很有可能存在这种情况:两个不同的数据计算得到相同的hash值。

image-20201027215328292

例如图中的“你好”和“hello”,假如最终算出hash值相同,那么他们会将同一个下标的二进制数据改为1。

这个时候,你就不知道下标为2的二进制,到底是代表“你好”还是“hello”。

由此得出如下缺点:

  • 存在误判

    假如上面的图没有存”hello”,只存了”你好”,那么用”hello”来查询的时候,会判断”hello”存在集合中。

    因为“你好”和“hello”的hash值是相同的,通过相同的hash值,找到的二进制数据也是一样的,都是1。

  • 删除困难

    还是用上面的举例,因为“你好”和“hello”的hash值相同,对应的数组下标也是一样的。

    这时候老哥想去删除“你好”,将下标为2里的二进制数据,由1改成了0。那么也会把“hello”一同删除。

实现布隆过滤器

实现步骤

1)引入Guava pom配置

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

2) 代码实现 这里我们顺便测一下它的误判率。

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);
  }
}

3) 运行结果:10万数据里有947个误判,约等于0.01%,也就是我们代码里设置的误判率:fpp = 0.01。

image-20201027221935046

核心代码分析

BloomFilter.create方法

public static <T> BloomFilter<T> create(
  Funnel<? super T> funnel, int expectedInsertions, double fpp) {
  return create(funnel, (long) expectedInsertions, fpp);
}

这里有四个参数:

  • funnel:数据类型(一般是调用Funnels工具类中的)
  • expectedInsertions:期望插入的值的个数
  • fpp:误判率(默认值为0.03)
  • strategy:哈希算法

fpp误判率

情景一:fpp = 0.01:

  • 误判个数:947
  • 占内存大小:9585058位数

image-20201027222816716

情景二:fpp = 0.03(默认参数):

  • 误判个数:3033
  • 占内存大小:7298440位数

image-20201027222845888

小结

  1. 误判率可以通过fpp参数进行调节
  2. fpp越小,需要的内存空间就越大:0.01需要900多万位数,0.03需要700多万位数。
  3. fpp越小,集合添加数据时,就需要更多的hash函数运算更多的hash值,去存储到对应的数组下标里。(忘了去看上面的布隆过滤存入数据的过程)

上面的 numBits,表示存一百万个int类型数字,需要的位数为7298440,700多万位。理论上存一百万个数,一个int是4字节32位,需要481000000=3200万位。如果使用HashMap去存,按HashMap50%的存储效率,需要6400万位。可以看出BloomFilter的存储空间很小,只有HashMap的1/10左右

上面的 numHashFunctions 表示需要几个hash函数运算,去映射不同的下标存这些数字是否存在(0 or 1)。

解决Redis缓存穿透 🤔

上面使用Guava实现的布隆过滤器是把数据放在了本地内存中。分布式的场景中就不合适了,无法共享内存。

我们还可以用Redis来实现布隆过滤器,这里使用Redis封装好的客户端工具Redisson。

其底层是使用数据结构bitMap,大家就把它理解成上面说的二进制结构,由于篇幅原因,bitmap不在这篇文章里讲,我们之后写一篇文章介绍。

1)pom配置:

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson-spring-boot-starter</artifactId>
  <version>3.13.4</version>
</dependency>

2) java代码:

public class RedissonBloomFilter {

  public static void main(String[] args) {
    Config config = new Config();
    config.useSingleServer().setAddress("redis://127.0.0.1:6379");
    //config.useSingleServer().setPassword("1234");
    //构造Redisson
    RedissonClient redisson = Redisson.create(config);

    RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
    //初始化布隆过滤器:预计元素为100000000L,误差率为3%
    bloomFilter.tryInit(100000000L,0.03);
    //将号码10086插入到布隆过滤器中
    bloomFilter.add("10086");

    //判断下面号码是否在布隆过滤器中
    //输出false
    System.out.println(bloomFilter.contains("123456"));
    //输出true
    System.out.println(bloomFilter.contains("10086"));
  }
}

Redis缓存穿透解决案例

其实布隆过滤器本质来讲,就是起到一个黑名单或者白名单的作用。我们从这两个角度去分析缓存穿透问题。

白名单解决缓存穿透

image-20201028093216785

注意问题

  • 如果没在白名单里的数据被误判存在于过滤器里的话,会穿透到数据库,不过误判的几率本来就很小,所以穿透问题不大。
  • 必须将所有的查询key都放到布隆过滤器和Redis里,否则请求会被直接返回空数据。

代码实现

用户实体类:

@Data
public class User implements Serializable {

    public static String maYunPhone = "18890019390";

    private Long id;
    
    private String userName;
    
    private Integer age;
    
}
/**
 * 解决缓存穿透—白名单
 */
public class RedissonBloomFilter {

    /**
     * 构造Redisson
     */
    static RedissonClient redisson = null;

    static RBloomFilter<String> bloomFilter = null;

    static {
      Config config = new Config();
      config.useSingleServer().setAddress("redis://127.0.0.1:6379");

      //构造Redisson
      redisson = Redisson.create(config);
      //构造布隆过滤器
      bloomFilter = redisson.getBloomFilter("userIdFilter");

      // 将查询数据放入Redis缓存和布隆过滤器里
      initData(redisson, bloomFilter);
  }
  
  public static void main(String[] args) {
    User user = getUserById(2L);
    System.out.println("user对象为:" + JSON.toJSONString(user));
  }
  
  private static void initData(RedissonClient redisson, RBloomFilter<String> bloomFilter) {

      //初始化布隆过滤器:预计元素为100000000L,误差率为3%
      bloomFilter.tryInit(100000000L,0.01);

      //将id为1的数据,插入到布隆过滤器中
      bloomFilter.add("1");
      bloomFilter.add("2");

      // 将id为1对应的user数据,插入到Redis缓存中
      redisson.getBucket("1").set("{id:1, userName:'张三', age:18}");
    }

    public static User getUserById(Long id) {

      if (null == id) {
          return null;
      }
      String idKey = id.toString();

      // 开始模拟缓存穿透
      // 前端查询请求key
      if (bloomFilter.contains(idKey)) {

          // 通过了过滤器白名单校验,去Redis里查询真正的数据
          RBucket<Object> bucket = redisson.getBucket(idKey);
          Object object = bucket.get();

          // 如果Redis有数据,直接返回该数据
          if (null != object) {
              System.out.println("从Redis里面查询出来的");
              String userStr = object.toString();
              return JSON.parseObject(userStr, User.class);
          }

          // 如果Redis为空,去查询数据库
          User user = selectByDb(idKey);
          if (null == user) {
              return null;
          } else {
              // 将数据重新刷进缓存
              redisson.getBucket(id.toString()).set(JSON.toJSONString(user));
          }
          return user;
      }

      return null;
    }

    private static User selectByDb(String id) {
      System.out.println("从MySQL里面查询出来的");
      User user = new User();
      user.setId(1L);
      user.setUserName("张三");
      user.setAge(18);
      return user;
    }

}

黑名单解决缓存穿透

image-20201028101347487

注意问题

  • 布隆过滤器里的数据,存在误判,如果正常数据被误判存在黑名单里的话,会直接返回空数据。
  • 黑名单里的数据要很全面才行,否则会有比较严重的穿透问题。
  • 本来是在黑名单里的非法数据,之后有可能是正常数据。如:用id大于100万的数来请求,我们数据库里只有10万数据,这时候如果把id放进黑名单里。等数据达到100万的时候,就会出现问题。

应用场景举例

视频推送场景(黑名单)

image-20201028101455019

背景:某视频网站给用户推送视频

布隆过滤器作用:当黑名单使用。

要求:对于某用户,已经推送过的视频,不在进行推送。

流程:当推送给用户一批视频时,先判断这些视频是否存在过滤器里;如果存在就不推送给用户,不存在就推送给用户;同时将推送过的视频存入过滤器黑名单里,防止下次重复推送。

转载文章(白名单)

image-20201028101536839

背景:某用户想转载某大🐮的文章。

布隆过滤器作用:当白名单使用。

要求:在大🐮转发白名单里的,有转发文章的权限。

流程:某用户想转发大🐮的文章,由于没在白名单里,转发失败。于是找到大🐮开白名单,大🐮把他加入了白名单里后,允许转发了。