0 回复 最新回复: Nov 27, 2017 11:18 PM Leo Li RSS

使用Bloom Filter提高索引效率(上)

Leo Li

Bloom Filter 介绍:

 

在日常生活中,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新 元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用hash table来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。比如说,雅虎或者Gmail总是需要过滤垃圾邮件,一个办法就是记录下那些发垃圾邮件的 email 地址。如果用哈希表,每存储一亿 个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹, 然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。而全世界少说也有几十亿个发垃圾邮件的地址,因此可能需要上百 GB 的内存,一般服务器是无法存储的。

 

而Bloom Filter作为一种传统hash table的改良算法。通过“正确率换空间”的思想,摆脱了传统hash table的存储方式,允许用户在错误率和存储空间之间作权衡,很好的解决了在存储空间有限的条件下,快速判断元素是否在海量集合中的问题。

 

Bloom Filter是1970年由一个叫布隆的提出的,目前广泛应用在很多互联网应用中,其主要具有下面两个特点:

1. 查询时间和传统hash索引的方式相当,空间效率却远远超过一般的hash算法

2. 在保证空间效率的同时,会有一定的正向错误率

 

它实际上由一个m位的位数组和k个hash函数组成。初始状态下,位数组中所有位的值都设置为。我们假设取m=10, k=3, 用蓝色表示某位为0,红色表示为1:

 

 

 

插入元素的过程是三步走:

1. 计算k个hash值

2. 将k个hash值对m取模得到k个下标

3. 将数组中k个下标对应的位设置为1

 

比如向刚才的Bloom Filter插入元素“Alice”。分别用3个hash函数计算“Alice”的hash值,将hash值对10取模,得到在[0, 10)范围内的r1、r2、r3,假设计算结果为:

 

r1 = h1("Alice") % m = 1
r2 = h2("Alice") % m = 3
r3 = h3("Alice") % m = 5

 

于是将数组中第1位、第3位和第5位的值置为1:

 

 

再插入元素“Bob”的过程还是一样的,假设:

 

r1 = h1("Bob") % m = 8
r2 = h2("Bob") % m = 2
r3 = h3("Bob") % m = 3

 

那就将数组中第2位、第3位、第8位的值置为1(值已经为1的第3位不动):

 

 

以此类推,Bloom Filter运行过程中不断插入新元素,位数组里的0逐渐被翻转成1.

那我们怎么判断元素是否在集合里呢?同样还是三步走:

1. 计算k个hash值

2. 将k个hash值对m取模得到k个下标

3. 检查数组中k个下标对应的位是否都为1

 

如果元素对应的hash值在数组中不全为1,那么该元素肯定不在集合中。

 

但是如果元素对应的hash值在数组中全为1,该元素就一定在集合中吗?答案是不一定。这就是Bloom Filter会产生正向错误率的地方。那么Bloom Filter的正向错误率有多大?

 

经过一系列严谨的数学推导,Bloom Filter的误报率是:

 

 

 

其中m表示Bloom Filter中位数组的长度,n表示已有的元素个数,k表示hash函数的个数。那么误报率到底是多大呢?下图就是一个当m/n=8时的例子。可以看到,此时最佳的误差率仅在2%左右。

 

 

总结:

 

现在我们学习了Bloom Filter这种数据结构,了解了它是怎样通过允许少量的错误(Fale Positive)来节省大量的存储空间的。在下篇的文章中,我们一起来看看DataDomain中的重复数据检查,以及Bloom Filter如何在其中发挥威力的。

 

 

 

 

作者简介:

 

 

 

Walker Huang from Avamar

2016年2月加入Dell EMC Avamar,现在主要从事Avamar与DataDomain集成数据备份系统的开发和维护。资深跑友,有7次全程马拉松完赛经历。