Redis(十一) 布隆过滤器

lvtao

缓存中间件redis

发布于：2021年2月20日

次浏览

1.概述

布隆过滤器由二进制向量(位数组)和一系列随机映射函数组成，用于快速定位某个元素是否存在。如果你需要判断的元素都是数字，那么Redis提供的BitMap结构完全可以胜任，但很多场景我们需要对字符串进行判断，这就必须运用随机映射(哈希)函数将字符串转化为数字放入BitMap中，考虑到哈希值碰撞的情况，就需要多个随机映射函数来减少误判率。

2.二进制向量

BitMap也称为位图，实质上是一个二进制形式的字节数组，由0和1俩个数组构成，如图所示:

现在往创建的BitMap中添加7、15、24三个数字，看看bit结构的变化:

BitMap添加、查询元素的本质是对二进制数组的位与运算，并且这种结构并不直接存储元素本身，而是以偏移量的形式记录，每个元素在BitMap中仅占有一个bit空间(1亿个bit也仅占有12MB内存空间)。

3.基本原理

如果存储的元素为字符串或者复杂对象，那么BitMap是无法通过一个bit表示的，这时候需要随机散列函数转化为数字，假设某个布隆过滤器有三个哈希函数，然后往该布隆过滤器中添加张三、李四俩个字符串:

图中可以看出布隆过滤器并没有存储元素本身，只是记录对应的多个随机映射函数值，这样大大节省了存储空间。在判断某个元素是否存在时，会将计算出该元素的所有随机映射函数值，如果返回不存在，那么元素必定是不存在的。

另外图中也能看出随机映射函数的数量、BitMap的容量，直接影响到随机散列函数值碰撞的几率，也就是我们最关心的误判几率。在判断某个元素是否存在时，如果返回存在，有可能真的存在，也可能只是随机散列函数值发生碰撞造成的假象，实际元素是不存在的。

4.Redisson实现

RedisTemplate客户端实现布隆过滤器比较麻烦，需要借助google的guava框架提供的功能，然后实现对BitMap的操作达到布隆过滤器的效果。而Redisson客户端对布隆过滤器进行了封装，可以直接调用API。

创建一个普通的布隆过滤器:

1
2
3
4
5
6
7
8
9
10
11

// 创建对象
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");

// 初始化布隆过滤器，预计统计元素数量为55000000，期望误差率为0.03(误差率必须小于1大于0，否则报错)
bloomFilter.tryInit(55000000L,0.03);
bloomFilter.add(newSomeObject("field1Value","field2Value"));
bloomFilter.add(newSomeObject("field5Value","field8Value"));

// 判断元素是否存在
bloomFilter.contains(newSomeObject("field1Value","field8Value"));

创建一个分布式布隆过滤器:

1
2
3
4
5
6
7
8
9
10
11

// 创建分布式对象
RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");

// 初始化布隆过滤器，预计统计元素数量为255000000，期望误差率为0.03
bloomFilter.tryInit(255000000L,0.03);
bloomFilter.add(newSomeObject("field1Value","field2Value"));
bloomFilter.add(newSomeObject("field5Value","field8Value"));

// 判断元素是否存在
bloomFilter.contains(newSomeObject("field1Value","field8Value"));

注: Redisson客户端创建的布隆过滤器，不支持删除元素操作。

5.删除元素

布隆过滤器在初始化时，期望误差率是无法设置为0的，也就是说无论怎么设置都会出现哈希碰撞，这就导致了元素无法删除，因为你不能确定某个bit位到底被几个元素映射，也就无法删除某个元素映射的bit值。

第一个解决方案是定时重构BitMap结构，首先无论怎么设置都会出现哈希碰撞，因此必然会考虑到误判的处理逻辑，元素在删除后重构前这段时间被查询时，可以直接按误判处理。这种方案适合数据量不高、修改频率小的场景。

第二种方案是参考guava的设计，为BitMap结构中的每个bit设置一个计数器，添加元素后映射的位置计数+1，删除元素时计数-1，计数减少到0时将bit位的值设置为0，达到删除元素的效果。这种方案相对定时重构要灵活很多，并且在大数据量的情况下同步数据也不会占用多少CPU，缺点是占用空间过多，并且Redisson客户端没有支持这种功能，需要手动去实现(用到这种场景在更新)。

更新于：2021年7月26日