Redis-布隆过滤器_布隆过滤器效率

为什么使用布隆过滤器

就当前互联网环境来说，头部的互联网生态越来越往高并发、分布式的形态发展。举例来说，各大网页的黑名单系统，爬虫的重复率判断。这些场景越来越多。

举例来说，实时状态下可能会对超过百亿级别的 URL 需要进行判断是否符合规范或者存在于系统中，能否正常使用。

通常情况下，每个 URL 的大小为 64B（字节），那么就按照100亿的 URL 数量来看，大概需要640GB的内存容量【64*100亿/1024³】，对于当前线上服务器来说，… 这个值依然还是很大的！但如果利用布隆过滤器的优势，在没有失误率的情况下只需要100亿个比特，即：1.2GB，即使为了降低失误率，也不会超过几十GB的空间【失误率后面会谈到】

那么在这种情况下，利用布隆过滤器来解决的确是很优秀，优秀到维基百科这样说「它的优点是空间效率和查询时间都远远超过一般的算法」，空间复杂度和时间复杂度都远超一般的算法，布隆过滤器存储空间和插入/查询时间都是常数O(1)！注意：远超！！

什么是布隆过滤器

维基百科的概念：布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

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

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

主要作用：判断一个元素是否在集合中

这样的场景会有很多。会去判断，要查询的元素是否存在于集合当中。【该网站是否允许该用户登录、该网站共是否接受这样的 url 请求】

通常在查询的时候，一般会先从 cache 中进行查询，如果没有的话会直接到磁盘或者数据库查询，这样的方式看起来很合理，但是如果在中间再加一层布隆过虑器，这样就会更加合理了！为什么？

假设要查询的一个元素，而该元素不存在

a. 如果没有 BloomFilter，从cache中查询完就会直接到数据库做查询了，这样带来的现象是“慢”，毕竟从库中查耗时是比较长的，很大程度上对服务的性能产生影响。

b. 中间存在 BloomFilter，从cache中查询完就会首先查询 BloomFilter，就会发现该元素不存在，就可以不往后面进行查询了，而 BloomFilter 的性能是极其优越的。这样，对于机器或者说服务性能避免了很大不必要的消耗。

就上图所示，假设元素不存在，如果没有布隆过滤器，就直接会查询【磁盘/数据库】，这样会带来很大不必要的性能消耗！

既然效率这么高，那到底是什么原因呢？下面就介绍一下其实现原理

实现原理

HashMap的问题

讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器数据结构：二进制数组+hash算法

二进制数组

这个是最关键的一个数据结构，会将每一个元素经过 hash 算法映射到每一个二进制数组中去。

开篇讲到在时间复杂度和空间复杂度方面来说，都是在常数级别，这也归功于一个数据结构就是由比特位构成的数组，所以在空间这块是很有优势的。就拿一个URL 64B来说，对应比特位就是1，大概是 64*8:1 这个空间比例。

hash算法

对于hash算法来说，应该是比较熟悉了，数据元素经过 hash 函数会映射到不同的数组中，如果发生冲突可以使用一些方法进行解决，比如说是拉链法解决。

hash 函数应用在 BloomFilter 中的时候，与一般的 hash 函数处理有区别的地方是：

a. BloomFilter 将值不会映射到一个地址，而是映射到对应的二进制数组位，然后将该数组为置为 1

b. BloomFilter 不会采用 hash 函数中常用的解决地址冲突的方法，而是会将同一个元素，经过几个 hash function 后，将对应二进制数组位置置为 1，后期如果进行查询的时候，==只有经过hash函数后，几个位置同时为1，才可以判断该元素存在。==如下图所示：

按照图例，每个数据元素会经过 3 个不同的 hash function，然后对应到不同的二进制数组位，并且置为 1，这样一方面减小了冲突的概率，另外一方面会减小误差率。

当一个客户端查询过来，对于 URL1、URL2 和 URL3 在BloomFilter 中都是存在的，所以对这三个元素进行查询的时候，一定是可以查到的。

下面咱们试着用 URL1、URL4 和 URL5 进行举例说明：查找成功、查找不存在以及查找失误这三种真实存在的情况。如下图所示：

在 BloomFilter 的二进制数组右边是指的进行客户端查询 URL1、URL4 和 URL5时候的情况，可以看到：

• URL1：完全可以和存储 URL1 时候的数组位能够对应上并且同时都为1，即位置：1、5、9。查询成功！
• URL4：在数组位 2处为0，其余为1，导致三个位置不全为1，查找不存在，返回空！
• URL5：URL5的三个二进制数组位都为1，按原理说结果是URL5元素存在于BloomFilter中，但是可以清楚看到，查询有错误！这个就是查询产生失误的情况。

这也就能够说明，BloomFIlter在空间和时间方面是极其优秀的，都达到了 O(1) 的级别，但是缺点是存在误识别率。

在这里注意，误识别率仅仅是存在查找成功的情况下，查询不存在是没有误识别率的。即：

• 查询存在：存在误识别率，就上面图示所示
• 查询不存在：肯定不会存在都是 1 的情况，所以这方面不会存在误识别率

性能分析

优势：省空间+高性能

省空间

这个在URL长度的案例说到，正是采用了二进制数组，一个元素经过 hash 函数对应着一个数组位（比特位），如果是真实存储一个URL（64B）的话，这就空间比例大约是64*8:1，即512:1

比特数组促使 BloomFilter 会省很大的空间，就空间效率来说，是极其高效的。

高性能

BloomFilter 不存在像链表查询一样，需要一个一个去遍历。反而会像数组一样，类似于直接取下标就可以找到所需要的结果。

不同的是，BloomFilter 需要过几个hash function，去查找下标。所以，综合来看，性能是很高的！

综合时间和空间效率，在有很低的误识别率情况下，各方面都是远超其他算法的。

不足：有误判+不能删除元素

有误判的情况-hash存在冲突

在前面举例 URL5 的时候，这种情况就会使得查询出现了失误，这也是传统hash冲突的直接表现，同时这也是使用了几个 hash 函数的原因。而这种错误识别，后期可以使用白名单的形式进行标记以补全这方面的不足。

但是在真正工业界的使用来看，这种冲突或者说查询失误也是保持在 0.01% 以下，一方面会考量 hash 函数的使用，另外一方面会增大 BloomFilter 二进制数组的位数来避免这种冲突。

那么，就上面两个考虑的方面，来具体看看：到底需要多大的二进制数组的长度以及多少个hash 函数才可以使得上述案例的失误率保持在 0.01% 以下？

二进制bit数组长度的选取

记：n=100亿，p=0.01， BloomFilter 的二进制bit数组长度 m 使用以下公式决定的：

可以求得：m=19.19n，即二进制bit数组长度大概是元素个数 n 的20倍，需要200亿个bit位，相当于大约25GB的空间，对于我们普通工业界的服务器来说，是足够容纳这个数组的

最好需要多少个 hash 函数

业界一般用这个公式来计算需要 k 个 hash 函数：

即：需要 14 个 hash 函数来进行构造

根据上述的计算，可以得到我们要使用 BloomFilter 的最佳方案

不能删除元素

这个就很好理解了，不同的元素通过 hash 函数使得相应位置都置为了 1，是绝对不能删除该元素，将它对应的位置置为 0 的。

下图中的 URL1 和 URL2，经过 hash 函数后，其中一个hash结果都指向了二进制数组中的3位置【红色箭头】，如果现在想要删除URL1，那么，按理说应该将 URL1 hash后指向的二进制数组对应位置都置为 0 才对，显然，这样做是不行的，会影响到 URL2 的查询。

操作举例

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

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：

我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：

值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

行业应用

工业界会有很多这种场景会使用到，例如：

博客系统黑名单限制
爬虫重复率的判定
比特币的应用
垃圾邮件过滤
等等…
不过大致都是很通用的一些解决方案，比如下图所示：

在信息写入的时候，会同时写入到缓存、数据库和布隆过滤器。需要查询的时候，先进行对缓存进行查询，如果找不到的话，就会先使用 BloomFilter 进行判断是否存在，如果存在就会继续向数据库查询；如果不存在，就直接返回空了。

这样在很大程度上提升了应用服务的效率！

资料来源
https://zhuanlan.zhihu.com/p/352675471
https://zhuanlan.zhihu.com/p/43263751