一文讲透“布隆过滤器”

1、什么是布隆过滤器？

布隆过滤器本质上就是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

2、为什么需要布隆过滤器？

2.1 缓存穿透

我们经常会把一部分数据放在Redis中缓存，比如文章详情。

这样有查询请求进来，我们可以根据文章Id直接去缓存中取数据，而不用读取数据库，这是提升性能最简单，最普遍，也是最有效的做法。

一般的查询请求流程是这样的：先查缓存（有缓存的话直接返回）-> 如果缓存中没有，再去数据库查询（把数据库取出来的数据放入缓存）-> 返回数据。

好像一切看起来很美好。

问题：如果现在有大量请求进来，而且都在请求一个不存在的文章Id，那将会发生什么？

既然文章Id都不存在，那么肯定没有对应的缓存信息，没有缓存，那么大量的请求都堆积到数据库，数据库的压力一下子就上来了，甚至可能把数据库打满跑死。

2.2 大范围查询

查询近1亿用户手机号系统中是否存在其交易信息，如何做到判断的准确快速？

方案一：通过数据库查询

查询压力好像有点大，做不到高效而且还存在数据库服务被压垮的风险。

方案二：通过Redis缓存（存在交易单的用户手机号放入Set）

可能会产生大Key造成慢查询，同时内存资源会造成浪费。

以上例子有一个共同的特点： 如何判断一个元素是否存在一个集合中。这些问题用其他方式可能都会解决，但“布隆过滤器”就能够有效的解决。

3、布隆过滤器实现原理

3.1 哈希函数

哈希函数的概念：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。示意图如下所示：

可以明显的看到，原始数据经过哈希函数的映射后成为了一个个的哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。

3.2 数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组，示意图如下所示：

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。

假设我们要将x、y、z三元素放入布隆过滤器再去检索w，示意图如下所示：

具体的操作流程如下：

假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。将位数组进行初始化，将里面每个位都设置为0。

• 设置：对于集合{x, y, z}里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1（这样位置2、4、5、6、12、14、17均为1）。
• 查询：判断W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点（位置：5、14、16）。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。

注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。 假设某个元素通过映射对应下标为4，5，6 这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，由此推断出误判率存在的可能性。

4、布隆过滤器操作

4.1 添加元素

语法：[bf.add  key  options]

127.0.0.1:6379> bf.add users 15012345678
(integer) 1

• 将要添加的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 将这k个位置设为1

4.2 查询元素

语法：[bf.exists  key  options]

127.0.0.1:6379> bf.exists users 15012345678
(integer) 1
127.0.0.1:6379> bf.exists users 15012345679
(integer) 0

• 将要查询的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 如果k个位置有一个为0，则肯定不在集合中
• 如果k个位置全部为1，则可能在集合中

4.3 删除元素

传统的布隆过滤器并不支持删除操作。

但是名为 Counting Bloom Filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。大家感兴趣可自行检索了解~

5、最佳实践

5.1 应用场景

常见的使用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续更昂贵的查询请求。

既然我们使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。

5.2 设置哈希函数个数和布隆过滤器长度

假如布隆过滤器长度过小的话，那很快所有的 bit 位均会被置为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置为 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

往期热文推荐：

• MySQL explain 中的 rows 究竟是如何计算的？
• 表驱动法
• 一文搞懂 Redis高性能之IO多路复用

「技术架构精进」专注架构研究，技术分享

Thanks for reading!