BloomFilter【布隆过滤器】

简介

概述：布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上由一个很长的二进制向量(二进制数组)和一系列随机映射函数(hash函数)。

作用：布隆过滤器可以用于检索一个元素是否在一个集合中。

添加元素：将商品的id(id1)存储到布隆过滤器

假设当前的布隆过滤器中提供了三个hash函数，此时就使用三个hash函数对id1进行哈希运算，运算结果分别为：2、5、10那么就会数组中对应的位置数据更改为1。

判断数据是否存在：使用相同的hash函数对数据进行哈希运算，得到哈希值。然后判断该哈希值所对应的数组位置是否都为1，如果不都是1则说明该数据肯定不存在。如果都是1说明该数据可能存在，因为哈希运算可能就会存在重复的情况。如下图所示：

假设添加完id1和id2数据以后，布隆过滤器中数据的存储方式如上图所示，那么此时要判断id3对应的数据在布隆过滤器中是否存在，按照上述的判断规则应该是存在，但是id3这个数据在布隆过滤器中压根就不存在，这种情况就属于误判。

误判率：数组越小误判率就越大，数组越大误判率就越小，但是同时带来了更多的内存消耗。

删除元素：布隆过滤器不支持数据的删除操作(因为有hash冲突,如果把A的hash值删除可能会影响B的查询)，因为如果支持删除那么此时就会影响判断不存在的结果。

优势：

  1. 因为是二进制0,1，所以占用空间很小

  2. 修改和查询速度快

布隆过滤器的优缺点

优点：占用空间小、查询速度快

缺点：存在误差率、不支持删除操作

redisson的布隆过滤器

1. 初始化布隆过滤器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * albumInfo BloomFilter
 *
 * @param redissonClient
 * @return
 */
@Bean
public RBloomFilter albumInfoBloomFilter(RedissonClient redissonClient) {
    RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter(BFConstants.BF_ALBUM_INFO);
    // 1. 若没有则初始化
    if (!bloomFilter.isExists()) {
        bloomFilter.tryInit(1000000L, 0.001d);
        log.info("{}布隆过滤器初始化成功", BFConstants.BF_ALBUM_INFO);
    }
    return bloomFilter;
}

2.初始化布隆过滤器的数据

本质上就是让服务在启动的同时添加数据
1 : ApplicationRunner
2: SpringApplicationListener
3: @Bean
4: CommandLineRunner
5: @PostConstruct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
  public void run(ApplicationArguments args) {
      //1. albumBloomFilter 初始化数据
      CompletableFuture.runAsync(() -> {
          RBloomFilter<Object> bloomFilterAlbum = redissonClient.getBloomFilter(BFConstants.BF_ALBUM_INFO);

          //1.获取全部id
          List<Long> albumInfoAllId = albumInfoMapper.getAlbumInfoAllId();
          //2.将ids加入布隆过滤器
          for (Long albumId : albumInfoAllId) {
              bloomFilterAlbum.add(albumId);
          }
          log.info("ApplicationRunner实现服务启动初始化布隆过滤器数据成功,一共有{}个数据", bloomFilterAlbum.count());
      }, myExecutor);

  }

3. 运行时自动更新布隆过滤器

定时任务:

  1. spring boot自带task :@Schedule
  2. 线程池的定时和延迟任务的方法
    • 1.定时任务scheduleAtFixedRate
    • 2.schedule 延迟任务+自己回调
  3. 分布式定时任务