1 背景

现在有海量的数据，而这些数据的大小已经远远超出了服务器的内存，现在再来一条数据，如何快速高效判断这条数据在不在其中？

如果这些数据是存在数据库中的，考虑索引，分库分表；或者考虑其他目前主流的云数据库平台；或者基于内存存储的redis，即使redis读取速度快，但也会存在大key问题（hash，list，set等存储中value值过多，读写bigkey会导致超时严重，甚至阻塞服务）

如果服务器的内存足够大，那么用HashMap是一个不错的解决方案，理论上的时间复杂度可以达到O(1)，但是现在数据的大小已经远远超出了服务器的内存，而且这是建立在单体基础上的，随着分布式架构，一个map已经没法满足这个需求，实现共享又是不可行的。布隆过滤器应运而生，可应对海量数据判断是否存在。

2 应用场景

1 判断一个元素在海量级数据中是否存在

2 Google Chrome 使用布隆过滤器识别恶意 URL，加速安全浏览服务

3 Medium.com（专注于英文写作和阅读的平台） 使用布隆过滤器避免推荐给用户已经读过的文章，或者判断用户是否阅读过某视频或文章，比如抖音或头条

4 邮箱场景 反垃圾邮件，从数十亿个邮件列表中判断某邮箱是否垃圾邮箱

5 在网络爬虫里，对URL去重，避免爬取相同的URL地址

6 数据库防止穿库：Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的磁盘查找，提高数据库查询操作的性能

7 缓解缓存穿透问题

当我们把一些热点数据放在 Redis 中缓存， 通常一个请求我们会先查询缓存，而不用直接读取数据库，这是提升性能最简单也是最普遍的做法，但是如果一直请求一个不存在的缓存，那就会有大量请求直接打到数据库上，造成缓存穿透，布隆过滤器也可以用来解决此类问题，当对key查询的请求量很大时，很可能对DB造成影响。

需要注意的是以上问题通过布隆过滤器不能完全解决，我们只能将其控制在一个可以容忍的范围内。

3 基本原理

术语概念

1 位图：通过数组下标来定位数据，使用比特位来标记（映射）这些数据。布隆过滤器就是一种基于位图逻辑的一个很长的二进制向量和一系列随机映射函数

2 期望插入数目：表示预计放入的元素数量，需要对场景所需数据量进行预估。当实际数量超过这个值时，误判率就会提升，所以需要提前设置一个较大的数值避免超出导致误判率升高

3 误差率：允许达到的误差率是千分之一还是万分之一，误差率越低，所需数组长度就会越长，所需要的空间就越大

4 hash函数的特性：

4.1 如果两个hash值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是hash函数具有确定性的结果。

4.2 散列函数的输入和输出不是唯一对应关系的，如果两个hash值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“Hash碰撞（collision）”。

底层原理

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。它可以用来判断某个元素是否在集合内，布隆过滤器的基础数据结构是一个比特向量。每个占位符用二进制来表示，内存空间非常节省。

但是hash函数就存在冲突问题，可以使用更复杂的hash函数，同时用多个hash函数一起定位一条数据，也就是通过n个二进制位来表示一个数字是否存在，这样也可以降低冲突的概率。

考虑这样一种情况，随着插入元素越来越多，极端情况下布隆过滤器空间占满，会造成每一次查询都会返回1，这样就会造成严重的误差。因此，这就意味着初始化这个数组的长度严重取决于期望预计添加元素的数量，即数组长度要大于期望插入元素的长度。

推荐一款计算bit数组长度的小工具：https://hur.st/bloomfilter/?n=10000&p=1.0E-3&m=&k=3

关系趋势

1 误差率（p）和期望元素个数（n），随着期望插入个数的提升，误差率也会随之提升

2 误差率（p）和hash函数次数（k），随着hash函数次数的提升，误差率会随之降低

总结：预期总量一定的情况下，hash次数越多，误差率越低。但是hash次数过多又会降低查询速度

特点

优点

1 由于存放的不是完整的数据，而是0、1这样的二进制，所以占用的内存很少；

2 只需要做hash函数算法，所以新增，查询速度快。

缺点

1 随着数据的增加，误判率随之增加；

2 无法删除数据；当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行

3 只能判断数据是否一定不存在，而无法判断数据是否一定存在。

4 原理演示

算法

1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数；

2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0；

3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位的值修改为1；

4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。

图形演示

1 现在我们新建一个长度为16的布隆过滤器，默认值都是0，就像下面这样：

2 现在需要添加一个数据：

我们通过某种hash计算方式，比如Hash1，计算出了Hash1(数据)=5，我们就把下标为5的格子改成1，就像下面这样：

我们又通过某种hash计算方式，比如Hash2，计算出了Hash2(数据)=9，我们就把下标为9的格子改成1，就像下面这样：

还是通过某种计算方式，比如Hash3，计算出了Hash3(数据)=2，我们就把下标为2的格子改成1，就像下面这样：

这样，刚才添加的数据就占据了布隆过滤器“5”，“9”，“2”三个格子。

可以看出，仅仅从布隆过滤器本身而言，根本没有存放完整的数据，只是运用一系列随机映射函数计算出位置，然后填充二进制向量。

3 判断是否存在

只需利用上面的三种固定的计算方式，计算出这个数据占据哪些格子，然后看看这些格子里面放置的是否都是1，如果有一个格子不为1，那么就代表这个数字不在其中。

4 判断是否一定存在

但是有一个问题需要注意，即使这些格子里面放置的都是1，不一定代表给定的数据一定存在，也许其他数据经过这三种固定的计算方式算出来的结果也是相同的。

5 删除：比如要删除数据，把“5”，“9”，“2”三个格子都改成了0，但是可能其他的数据也映射到了“5”，“9”，“2”三个格子，这样就会造成数据错误，所以没法删除。

5 实现方式

1 引入guava包实现

2 利用redis来实现：Redis 因其支持 setbit 和 getbit 操作，且基于纯内存操作以至于性能高等特点，因此天然就可以作为布隆过滤器来使用

3 使用redis布隆过滤器插件来实现。redis4.0之后支持插件支持布隆过滤器 https://github.com/RedisBloom/RedisBloom

6 代码演示 show me the code

1 根据预期插入数目和误差率计算big数组长度

2 取模计算所占用位置

3 向布隆过滤器中添加值

4 在布隆过滤器中判断某值是否存在

7 温馨提示

1 针对大value做拆分：

布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。例如一千万数据进行拆分redis，就需要1000个桶，每个桶10000个bit，这样一个桶17k，一千个桶只需要17M左右。

所以通用的方案：1kw的数据量（分1k片，每个分片1w的数据量），做3次hash函数，设置误差率0.001，这样占用的内存大小17k*1000=17M。

8 总结

1 布隆过滤器可以帮助我们解决一些海量数据场景下的判断是否存在问题

2 他的特点是不一定存在，但是一定不存在，所以在使用过程中会存在误差率

3 他的查询速度快，占用内存空间小，但是通过一个大桶这样的不合理使用也会造成大key问题，导致阻塞，所以要进行分片

4 实现方式可以由guava、redis、redis自带bloom-filter插件实现