布隆过滤器（Bloom Filter）详解

今天在看Redis缓存穿透问题时里面讲到了布隆过滤器，研究了一番，总结一下。

一、什么是布隆过滤器

布隆过滤器，Bloom Filter是1970年由Bloom提出的，它是由一组哈希（Hash）函数和一个位阵列组成。布隆过滤器可以用于查询一个元素是否存在于一个集合当中，查询结果为以下二者之一：

• 这个元素可能存在于这个集合当中。
• 这个元素一定不存在于这个集合当中。

布隆过滤器的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器在实际中主要用来解决网页URL去重复，垃圾邮件检测，大集合中重复元素判断和缓存击穿等问题。

二、设计原理

如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。

这时候我们可以利用哈希表这种数据结构，基于哈希函数的特性，它在理想情况下(不发生哈希冲突)，检索速度可以达到O(1)。一张哈希表的示意图如下所示：

哈希函数是这样的：

$hashcode = H(key)$

这里的hashcode就是哈希桶的索引，如何哈希函数H足够完美，那么每个key就会对应一个唯一的hashcode，但实际上往往会出现哈希冲突，即两个不同的key对应同一个hashcode，如下图所示，“John Smith” 和 “Sandra Dee” 经过哈希之后得到了相同的哈希值“02”。

布隆过滤器使用了上面的思路，即利用哈希表这个数据结构，通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点（每个点只能表示0或者1），这样一来，我们只要看看这个点是不是1就知道在集合中有没有它了。这就是Bloom Filter的基本思想。

但是在哈希冲突的情况下，我们无法使用一个哈希函数来判断一个元素是否存在于集合之中，解决方法也简单，就是使用多个哈希函数，如果其中有一个哈希函数判断该元素不在集合中（元素经过Hash之后映射在位阵列中的点为0），那肯定就不在。如果它们都判断存在，那也有一定可能性它们都在说谎，不过这要比只用一个哈希函数来判断“一个元素存在于集合之中”的可靠性要高很多。这种多个Hash组成的数据结构就叫Bloom Filter。

一个Bloom Filter是基于一个m位的位阵列（b1,…bm），这些位阵列的初始值为0。另外，还有一系列的hash函数（h1,…hk），这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图：

上图中，m=18，k=3；

插入x时，三个hash函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入y，z时，类似的，分别将红线，紫线对应的位向量改为1。

查找时，当查找x时，三个hash值对应的位向量都为1，因此判断x在此数据集中。y，z也是如此。但是当查找w时，w有个hash值对应的位向量为0，因此可以判断不在此集合中。但是，假如w的最后那个hash值比上图中的大1，这是就会认为w在此集合中，而事实上，w可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。

产生误报的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。幸运的是，布隆过滤器有一个可预测的误判率（FPP）：

 

n 是已经添加元素的数量；
k 哈希的次数；
m 布隆过滤器的长度（如比特数组的大小）；

极端情况下，当布隆过滤器没有空闲空间时（满），每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ，并且 m 需要远远大于 n 。

实际情况中，布隆过滤器的长度 m 可以根据给定的误判率（FFP）的和期望添加的元素个数 n 的通过如下公式计算：

对于 m/n 比率表示每一个元素需要分配的比特位的数量，也就是哈希函数 k 的数量可以调整误判率。通过如下公式来选择最佳的 k 可以减少误判率（FPP）：

了解完上述的内容之后，我们可以得出一个结论，当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。

三、布隆过滤器应用

在实际工作中，布隆过滤器常见的应用场景如下：

• 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
• Google Chrome 使用布隆过滤器识别恶意 URL；
• Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
• Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。

利用布隆过滤器我们可以预先把数据查询的主键，比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候，我们先判断该 ID 是否存在，若存在的话，则进行下一步处理。若不存在的话，直接返回，这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。

四、代码实践

布隆过滤器有很多实现和优化，由 Google 开发著名的 Guava 库就提供了布隆过滤器（Bloom Filter）的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器，只需要引入以下坐标：

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>

在导入 Guava 库后，我们新建一个 BloomFilterDemo 类，在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器，接着我们初始化 1 百万条数据到过滤器中，然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中：

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
 
public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 总数量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }
}

当以上代码运行后，控制台会输出以下结果：

已匹配数量 1000309

很明显以上的输出结果已经出现了误报，因为相比预期的结果多了 309 个元素，误判率为：

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的话，我们可以在创建布隆过滤器的时候设置误判率 fpp：

BloomFilter<CharSequence> bf = BloomFilter.create(
  Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);

在 BloomFilter 内部，误判率 fpp 的默认值是 0.03：

// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
  return create(funnel, expectedInsertions, 0.03D);
}

在重新设置误判率为 0.0002 之后，我们重新运行程序，这时控制台会输出以下结果：

已匹配数量 1000003

通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

五、总结

Bloom Filter有以下几个特点：

• 不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。
• 可能存在误报（False Positive），即某个元素不在某个集合中，可能也被爆出来。
• 确定某个元素是否在某个集合中的代价和总的元素数目无关。

优点：

相比于其它的数据结构，Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。Bloom Filter不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点：

一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

参考资料

https://en.wikipedia.org/wiki/Bloom_filter

https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

http://www.sigma.me/2011/09/13/hash-and-bloom-filter.html

https://segmentfault.com/a/1190000021136424