布隆过滤器简介

在日常写码中，我们经常能遇到判断一个元素是否在一个给定的集合中的需求。听起来这种问题很简单，用哈希集合就能轻松搞定，用 Python 表示的话，不难写出如下的代码，

>>> my_set = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
>>> 1 in my_set
True
>>> 11 in my_set
False

并且我们知道在集合中查询的时间复杂度是常数级。然而，如果集合上了规模，我们就不得不考虑这样一个集合将要占用多少空间了。假如里面存的都是整数，按一个整数四个字节计算，十亿个整数就要用掉大约 4GB 的内存，这个大小光是程序启动时从外存加载数据的时间就会变得令人难以忍受。

那么如何解决这个问题呢？

当然，如果我们确实希望精确知道一个元素是否在这规模大小为十亿的集合中，哈希集合的使用还是不可避免的，但实际的生产中我们往往只需要知道一个大致的结果即可，这个时候，我们可以考虑使用布隆过滤器（ bloomfilter ）来替代哈希集合，它能以更小的空间表示一个集合，并且在检查元素的存在与否时还能给出一个不算太差的结果。根据布隆过滤器的设计，它的结果有可能会是“假阳性”（ false positive ）的，但不可能出现“假阴性”（ false negative ）。换句话说，给定一个元素 X ，如果布隆过滤器说它存在于集合中，那么它有可能真的存在，而如果布隆过滤器说它不存在，那么就一定不存在。

布隆过滤器的原理

布隆过滤器的设计基于我们已经很熟悉的哈希函数，显然，对于同一个元素，不同的哈希函数会得出不同的哈希值，根据这一特性，就可以着手设计布隆过滤器了。首先，在一段长度为 m 的比特数组（ bit array ）中，将所有的比特置为 0 ，然后根据某种规则挑选 k 个哈希函数。当往布隆过滤器里添加一个元素 X 时，通过这 k 个哈希函数计算出 k 个哈希值，这也就对应着比特数组中的 k 个位置，将这 k 个位置的值置为 1 ，到此元素 X 添加完成。而判断一个元素是否存在于集合中也是同样的过程，计算出 k 个哈希值，然后去数组中对应的这 k 个位置检查是否都为 1 ，如果有 0 存在，那么意味着这个元素不可能存在于集合中。

下面用一个简单的例子来说明布隆过滤器是如何工作的，假设有一个集合，包含字母 “a” 和字母 “b” ，初始的数组长度为 11 ，如图所示，

我们用两个哈希函数来计算元素的哈希值： hash1() 和 hash2() 。对于字母 “a” ，计算得出的哈希值分别为 3 和 5 ，对应到数组中，需要将位置编号为 3 和 5 的比特置为 1 ，

对于字母 “b” ，得到的哈希值为 5 和 8 ，同样将 5 号位置和 8 号位置设置为 1 ，其中 5 号位置的值已经是 1 了，可以直接跳过，也可以覆盖一遍，对于最终的布隆过滤器是没有影响的，

我们可以向数组中添加更多的元素，而大小始终都是这 11 个 bit 。

在查找一个元素是否存在于集合时，用同样的哈希函数 hash1() 和 hash2() 计算出该元素的哈希值，然后去数组中对应的位置去检查该值是否都为 1 。因为对于数组的操作 0 -> 1 是单向的，所以只要该元素被添加到布隆过滤器了，那么它的哈希值对应位置的值必然为 1 ，因此如果对于一个元素，它的哈希值对应的位置在数组中的值为 0 ，它一定不可能存在于这个集合里，也就是“假阴性”的情况不可能出现。

那么为什么说会存在“假阳性”的情况呢？比如说我们想知道字母 “c” 是否在集合中，按照上述过程计算出它的两个哈希值，分别为 3 和 8 ，而数组中位置 3 和 8 的值都为 1 ，这时布隆过滤器就误判字母 “c” 也在集合中，其实不然。

如何提高布隆过滤器的准确率

也就是说如何才能降低布隆过滤器的假阳性率，毕竟这是唯一的错误来源。首先我们需要知道给定集合的大小 n ，哈希函数（假设所有哈希函数都是足够均匀的）的数量 k ，和数组的长度 m ，这样的一个布隆过滤器的假阳性率是多少。维基百科上给出了详细的推导过程，在此按下不表，结论是假阳性率约为

这无法用单纯的“增加哈希函数”或者“用更长的数组”来得到一个最优解，事实上， n 是已知量， m 也不难确定，只需要看看自己的空间预算即可，于是就只剩 k 还未确定。具体的推导过程可以参考维基百科或者这份课件，这里不再细表， k 的最优解为

布隆过滤器在生产中使用的一些问题

编程语言千千万，如果在实际生产中只用一门或者一个系列的语言，自然不会有任何问题，比如说 Java/JVM 有 Guava 库自带的布隆过滤器实现，这样一个模块生成的布隆过滤器序列化之后可以很方便地被其他模块反序列化。但如果想要跨语言的使用的话，事情就没那么简单了，从上述介绍可以看出，布隆过滤器天然就带有很多变量，比如说哈希函数的选取，哈希函数个数的选择，不同语言的布隆过滤器库之间的实现很有可能是不一样的，再涉及到序列化和反序列化，没有统一的协议，情况就更复杂了。

年初的时候恰好我们就遇到了这个问题，一个线上服务的几个模块都需要使用布隆过滤器，编程语言分布在 Kotlin ， Go ， Python 等，并且它们是严格的上下游关系，需要一个模块产生布隆过滤器，其他模块根据生成的布隆过滤器去判断一些元素存在与否。考虑到数据量和下游服务严格的实时性要求，让每个模块自己去计算布隆过滤器是不现实的，因此必须在上游的批处理任务中把布隆过滤器准备好。经过一番搜索和试验，并没有找到现成的跨语言布隆过滤器实现，最终只得以 Java 的 Guava 实现为基准，用 Python 和 Go 实现与之兼容的布隆过滤器。在开发之初，我考虑到其他人可能也会有同样的需求，就撇开工作电脑，完全在自己的开发环境上实现了这两个库并在 GitHub 开源。