Redis之布隆过滤器（BloomFilter）-向日葵屋

Redis之布隆过滤器（BloomFilter）

野性酷女 2023-02-20 02:14 20阅读 0赞

在实际的开发中通常会遇到数据去重的问题，比如判断用户是不是新用户，哪些用户登陆过系统等等这些类似的问题，比较容易想到的解决方案如下：

使用set，但是数据量比较大的时候会非常浪费内存，并且性能也不高
使用之前提到的BitMap，但是在数据稀疏的场景下，反而还不如set

那么这种场景应该如何解决呢？业界有另外一个更优秀的数据结构来解决这类问题，那就是——布隆过滤器(BloomFilter)。

什么是布隆过滤器

布隆过滤器与BitMap类似，底层也是一个位数组。1表示有，0表示无。但布隆过滤器比BitMap需要更少的内存，它是怎么办到的呢？答案是多个hash。

hash算法就是把任意长度的输入，通过算法，变换成固定长度的输出，该输出就是hash值。

比如我们有一个10位的数组，使用某个hash算法及其数组上的表示：

hash("布隆") = 3
hash(“布隆过滤器”) = 5
0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0

这样，我们使用这个hash算法就能快速的判断一个字符串是不是存在一个集合里面了。但众所周知，hash算法是有可能发生hash冲突的。比如可能有两个不同的字符串映射到同一个数：

hash("布隆") = 3
hash("布隆过滤器") = 3

这种情况下，就不能准确得判断出某个字符串是不是存在于集合之中呢。

那怎么解决这个问题呢？答案是使用多个不同的hash算法。比如：

h1("布隆") = 3、h2("布隆") = 5、h3("布隆") = 7
h1("过滤器") = 5、h2("过滤器") = 6、h3("过滤器") = 7
h1("布隆过滤器") = 3、h2("布隆过滤器") = 6、h3("布隆过滤器") = 9

最开始，集合里没有元素，所有位都是0：

0, 0, 0, 0, 0, 0, 0, 0, 0, 0

然后，插入”布隆”，利用多次hash，把每次hash的结果下标3，5，7都插入到相应的地方：

0, 0, 0, 1, 0, 1, 0, 1, 0, 0

然后，插入”过滤器”，利用多次hash，把每次hash的结果下标5，6，7都插入到相应的地方，已经是1的下标不变：

0, 0, 0, 1, 0, 1, 1, 1, 0, 0

然后，插入”布隆过滤器”，利用多次hash，把每次hash的结果下表3，6，9插入到相应的地方，同样已经是1的下标不变：

0, 0, 0, 1, 0, 1, 1, 1, 0, 1

这个时候，如果想要判断”布隆”是否在集合中，只需要使用同样的3个hash算法，来计算出下标是3, 5, 7，发现这3个下标都为1，那么就认为”布隆”这个字符串在集合中。而”布隆过滤器”计算出来的下标是3， 6， 9。发现这三个下标有不是1的地方，比如下标为9的地方是0，那就说明”布隆过滤器”这个字符串还不在集合中。

关于布隆过滤器的误差

从布隆过滤器的原理来看，是存在一定误差的，尤其是当hash函数比较少的情况下。

布隆过滤器是根据多次hash计算下标后，数组的这些下标是否都为1来判断这个元素是否存在的。所以是存在一定的几率，要检查的元素实际上没有插入，但被其它元素插入影响，导致所有下标都为1。

所以布隆过滤器不能删除，因为一旦删除（即将相应的位置为0），就很大可能会影响其他元素。

如果使用布隆过滤器判断一个函数是否存在于一个集合，如果它返回true，则代表可能存在。如果它返回false，则代表一定不存在。

针对布隆过滤器存在一定误差的原因，常见的应用场景是对准确率要求不那么高的场景：

统计有多少用户登陆过系统
判断用户是否看过某篇文章

当然，对准确性要求严格的场景就不适合使用布隆过滤器：

用户是否购买过课程
用户是否收藏过我的文章

当然针对缓存穿透问题，布隆过滤器也是一个很好的解决方案。

redis中的布隆过滤器

Redis的布隆过滤器主要有两个命令：

bf.add 添加元素到布隆过滤器中：bf.add strs xy
bf.exists 判断某个元素是否在过滤器中：bf.exists strs xy

Redis中有一个命令可以来设置布隆过滤器的准确率：

bf.reserve strs 0.01 100

三个参数的含义：

第一个值是过滤器的名字。
第二个值为error_rate的值：允许布隆过滤器的错误率。
第三个值为initial_size的值：初始化位数组的大小。

拓展学习

Java实现的布隆过滤器

如果你的项目没有使用Redis，那可以使用一些开源库，基于代码实现，直接存放在内存。比如Google的guava包中提供了BloomFilter类，有兴趣的读者可以去了解一下，研究研究源码和使用。

布谷鸟过滤器

RedisBloom模块还实现了布谷鸟过滤器，它算是对布隆过滤器的增强版。解决了布隆过滤器的一些比较明显的缺点，比如：不能删除元素，不能计数等。除此之外，布谷鸟过滤器不用使用多个hash函数，所以查询性能更高。除此之外，在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省40%多。