0%

布隆过滤器(BloomFilter)原理 | 亿级数据过滤解决方案

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw

1970 年,布隆先生提出了一种很优秀的过滤器算法,用来判断一个元素是否在集合中

「布隆过滤器算法」

故事开始→_→

先看本故事结构

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

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

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

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

看着来自各方面这么牛B 的吹嘘,咱们把布隆过滤器安排到方方面面,来具体看看它的原理是怎么样的…

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

等方面系统性的说道说道…

【1】

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

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

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

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

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

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

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

既然效率这么高,那到底是什么原因呢?

【2】

数据结构:二进制数组+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 的情况,所以这方面不会存在误识别率

【3】

优势:省空间+高性能

省空间

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

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

高性能

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

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

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

【4】

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

有误判的情况 - 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 的查询。

【5】

业界应用

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

  • 博客系统黑名单限制

  • 爬虫重复率的判定

  • 比特币的应用

  • 垃圾邮件过滤

    等等…

不过大致都是很通用的一些解决方案,比如下图所示:

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

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


最后福利

这里为大家准备了几百本的互联网电子书,有需要的过来取吧。点击获取

------ 全文结束------