布隆过滤（Bloom Filter）

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either “possibly in set” or “definitely not in set”. —— From wikipedia.

应用场景

数据字典
进行数据的判重
黑名单
CDN（squid）代理缓存技术

基本原理

Bloom Filter是一种空间效率极高的随机数据结构，它的原理是：当一个元素被加入集合时，通过 K 个Hash函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检索元素一定不在；如果都是1，则被检索元素很可能在。

重点：牺牲一定的准确率换取非常高的空间利用率

优点

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

布隆过滤器可以表示全集，其它任何数据结构都不能；

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

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

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

Java 实现（Guava）

Google Guava 库在第 v11.0 版本加入了 Bloom Filter 的实现，常用 API 介绍如下：

Bloom Filter 构造器

/**
 * 构造方法
 *
 * @param funnel 			漏斗模型，用于添加要检测的数据
 * @param expectedInsertions   预期要检测的数据总量
 * @param fpp                  误报率
 * @return                     Bloom Filter
 */
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp) {
	...
}

这是全参数的构造器，还有几个重载的构造函数（可以不指定误报率，默认为 3%）

注意事项 ：正确估计预期插入数量是很关键的一个参数，当插入的数量接近或高于预期值的时候，布隆过滤器将会填满，这样的话，它会产生很多无用的误报点。

检测内容是否存在

/**
 * 检测数据是否存在
 *
 * @param object  要检测的数据
 * @return        是否存在
 */
public boolean mightContain(T object) {
	...
}

注意事项 ：当返回不存在时，一定不存在，但返回存在时，则有可能存在，误报率在构造器中已经说明

实际应用场景

需求：给10亿用户每人发送一条消息

方案一：在内存中记录用户消息发送的状态

详细描述：在内存设计一个缓存，地将所有的用户已发送状态放入缓存中，当下一个用户过来时，校验缓存中是否已经存在。
优点：实现方式逻辑简单；
缺点：按 UTF-8 编码，用户标识符 10 个字符（10个字节） 10亿 = 10 10^9 ~= 10 G，基本超出常用的 JVM 内存；

方案二：将10亿用户号码存到数据库中，并标记发送状态

详细描述：设计数据库表记录各个用户的发送状态；
优点：无内存问题，逻辑简单；
缺点：10 亿级的数据记录存储本身的架构设计、高性能查询就是一个需要解决的很复杂的难题。

方案三：利用分布式缓存存储用户消息发送状态

详细描述：通过分布式 K-V 数据库（Redis）记录用户的发送状态；
优点：无内存问题，逻辑相对简单；
缺点：每条记录都需要跟缓存服务交互 2 次，存在分布式网络延迟；

方案四：Bloom Filter + 分布式缓存

详细描述：本地将所有的用户已发送状态放入 Bloom Filter 中（以及分布式缓存中），当下一个用户过来时，先在 Bloom Filter 中查询状态。如果不存在，则一定未发送，执行发送逻辑；如果存在，则 不一定 发送过，则去分布式缓存中进行二次确认，确认之前的 不一定 状态；
优点：无内存问题，绝大部分校验过程在本地完成，只有极少部分（来源于之前介绍的 Bloom Filter 的误差）会去分布式缓存进行二次校验，无网络延迟问题；
缺点：逻辑上会相对复杂一些；