Bloom Filter技术及应用

第31卷第3期阜阳师范学院学报(自然科学版)Vol. 31. No. 32014年9月Journal of Fuyang Teachers College( Natural ScienceSep.2014Bloom filter技术及应用张华,郑世珏2,童德茂(1.阜阳职业技术学院工程科技学院,安徽阜阳236031;2.华中师范大学计算机科学系,湖北武汉430079摘要; Bloom filter采用位串向量表示数据集合,能够实现高效集合查询的数据结构。首先介绍了标准布隆过滤器的概念和工作原理,然后通过实验分析布隆过滤器的错误率、空间向量和哈希函数数量三者之间的动态相关关系,并对独立空间布隆过滤器和标准布隆过滤器性能进行对比,最后讨论了 Bloom filter的变种及应用关键词: Bloom filter;错误率;标准布隆过滤器;独立空间布隆过滤器中图分类号:TP301文献标识码:A文章编号:1004-4329(2014)03-06205Bloom Filter technology and its applicationsZHANG Hua, ZHENG Shi-jue, TONG De-mao(1. Institute of Engineering and Technology, Fuyang Vocational and Technical College, Fuyang Anhui 236031, China;2 Department of Computer Science, Huazhong Normal University, Wuhan Hubei 430079, China)Abstract: Bloom Filter is a data structure that uses bit string vector to represent data set so as to meet efficient membershipqueries. First, the concept and the operating principle of standard Bloom Filter were given. Second, based on experiments, the dynamic relationships among the false positive, the vector space and the numbers of hash function of Bloom Filter were analyzed. Fur-thermore, the performance of independence space Bloom Filter and that of standard Bloom Filter were compared. Finally, applications and development of bloom Filter were discussedKey words: Bloom Filter; false positive; standard Bloom Filter; independence space Bloom Filterloom filter是由 Burton bloom提出的采用位编码后的位数比集合元素位数少,因此节省了存储串向量表示数据集合,能够实现高效集合査询的数空间。编码位数取决于你所期望的错误率,编码位据结构。它是以哈希表为基础的算法。哈希表数越多,错误就越少,反之则越大,即“正确率换取的基本原理是使用一个容量相对合适的数组来保空间”的思想。布隆过滤器就在这一思想下产生。存数据,在记录的存储位置和关键字之间建立一个布隆过滤器算法由于高效的查找速度被广泛运用。确定的对应关系函数h(即哈希函数),然后,使每例如 Web cache共享、文本文件检索系统、P2P网个关键字的内容,通过这个哈希函数计算h(x)来络文件存储系统等网络应用领域。目前国内外的得到该关键字对应的存储位置,之后将该关键字存研究主要有标准布隆过滤器和多种变种,例如压缩在数组的相应位置中2。人们发现为了查找而将布隆过滤器、计数布隆过滤器、分层布隆过滤器、动整个元素都存储在数组中,空间需求很大,因此对态布隆过滤器等。文章重点分析了标准布隆过滤哈希表进行改进,并不直接将集合元素存在数组器里,而是将每个元素编码然后将编码存在数组里。标TH中国煤化卫立空间布隆过滤器和CNMHG比较,最后对布隆过滤收稿日期:201402-27基金项目:中央高校基本科研业务费项目(CCNU11C01003)资助。作者简介:张华(1975-),女,硕士,副教授。研究方向:数据挖掘。第3期张华,郑世珏,童德茂: Bloom filter技术及应用器的相关变种及应用做了简单综述。的结果是 false,说明该元素肯定不在集合内;如果1标准布隆过滤器返还的是true,说明元素可能存在于集合中。由前面分析知道,使用 Bloom filter判断一个一个布隆过滤器由以下几部分组成(3。元素是否属于集合时,可能岀现错判,可能把不属(i) Bloom filter用一个长度为m的位向量V于这个集合的元素误判为属于这个集合( False表示集合中的元素,每个位的初始值都设为0。Positive)4,但是,不会把属于这个集合的元素误(i)k个相互独立均匀分布的哈希函数组成的判为不属于这个集合。下面通过计算来估计发生集合H。“假阳性”错误率P的大小。(i)n个元素组成的集合S。当集合S={x1,x2,…,xn}的所有元素都被k布隆过滤器的工作原理分为两步:个哈希函数映射到长为m的向量V中时,对于一个第一步,数据装入。k个相互独立的哈希函数键值在m个空间的向量中,被映射为1的概率是分别将集合S中的n个元素映射到向量V中的相应1/m,则对立事件,被映射为0的概率是1-1/m位置,将V中相应位置为1,如图1所示。k*n个键值都被映射为0的概率为(1-1/m)。第二步,数据判断。当新元素y到来时,对y进也就是,当集合中所有元素都映射完毕后,V向量行k次哈希运算,检查所有的h1(y),h2(y),任一位为0的概率为(1-1/m),它的对立事件h2(y)对应向量V中的位是否全部为1,如果是,则当集合中所有元素都映射完毕后,V向量任一位为元素y属于集合S,否则,认为y不属于集合S1的概率L为1-(1-1/m)。即L=1又当m趋向无穷大时,(1-1)的极限为01001001/e,故L≈1-(1位当不属于集合S的元素y误判为属于集合S图1 Bloom filter工作原理图时,则必须满足y在Ⅴ向量的k个映射位的值都必须为1。即错误率P为L。2性能分析即P=(1-e-kn/m)哈希函数最优个数布隆过滤器是基于哈希表的算法,对每个元素为了计算哈希函数个数,针对(1)式令f的判断要进行k次哈希运算,它的时间复杂度为0(k)。它的存储空间由元素通过哈希函数映射到D P=(1-f'=exp(kIn(1-5))=exp(向量空间的位数大小决定,由引言分析知道布隆过如m1n(1-0),令g=-m1mAm(-),则当g滤器是通过允许少量的错误来节省大量的存储空取最小值时,错误率P最小。又有当lnf=间,因此它的空间复杂度和错误率是动态相关的,1n(1-时|lnn(1-f取最大值,故f=1-f下面具体分析布隆过滤器的错误率、位数组大小及推得∫=1/2时,错误率P最小。由定义厂=em哈希函数的个数之间的关系1/2可得2.1错误率估计布隆过滤器判断某个数据对象y是否属于集k=mIn 2合S时,先检查表示y的位向量对应的位,如果均中国煤化工ny=(1/2)2(3)为1,则该数据对象属于集合S,否则不属于集合SHCNMH(取最优个数时,错误但是,即使是采用均匀且不同的哈希函数,地址冲率p和集合中元素个数n和向量大小m相关。突也是不能避免的,因此布隆过滤器算法可能对位假设给定元素n=400,向量m=3580,则由向量中的同一个位多次置1,所以在进行数据判断(2)式可计算k=7,由(3)式得p≈0.014由仿真时可能出现错判。也就是说,如果布隆过滤器返还如图2所示,错误率P处于最低点。阜阳师范学院学报(自然科学版)第31卷3独立空间布隆过滤器☆m=3580n-400前面介绍的通过k个哈希函数将n个元素映射到m个向量空间V中,其中每个哈希函数的映射☆☆劉身身卒☆☆空间都是{0.1,…,m-2,m-1},因此也称为共享空间布隆过滤器。不同关键字被同一哈希函数映射到哈希空间的同一位置,即对任何k,≠k存在h(k)=h(k.),把它称为内部冲突。对不同关键0.02宇被不同哈希函数映射到同一哈希空间,即对任何k≠k存在hn(k)=h(k,),称为外部冲突。对应10哈希函数个数k0内部冲突,我们可以通过选择哈希函数来解决,对于外部冲突,我们采用将每个哈希函数的映射空间图2 Bloom filter错误率与哈希函数个数关系图区分开来,即独立哈希空间布隆过滤器5。我们将况下选取适量哈希函数可以降低错误率,但是这句平均分成连续的k段,每段m/k位,对向量空2.3位数组大小设计由以上分析,在确定元素个数和向量空间的情每一段只进行一次哈希操作,则哈希函数的映射范种方法降低的程度有限。如果给定布隆过滤器的(i-1)(1≤i≤k)错误率上限p0,取到最优哈希函数数量时,要让错映射空间如图4所示。误率P不超过上限p0,表示集合中每个元素,最少需要多少向量空间由(3)可推出x log, p(4)通过实验可得如图3所示,在能够取最优哈希函数前提下,错误率和向量空间成反比,即错误率越低,则所需空间越大m/k位由公式(4)可以得出,在给定错误率的前提下,所需的空间可以计算。假如设p=0.001,则图4独立空间布隆过滤器图5751,若p=0.002,则m=5174时仿真如图3所示P增大m减小的反比趋势对于一个键值在每段m/k位中,被映射为1的概率是k/m,被映射为0的概率是1-k/m,则n个8000n=400键值都被映射为0的概率为(1-b/m)。也就7500是,当集合中所有元素都映射完毕,向量中m/k段中任意一位值为0的概率为(1-k/m)",它的对立事件,当集合中所有元素都映射完毕,向量中5751m/k段任意一位值为1的概率为1-(1-k/m)。5174当不属于集合S的元素y误判为属于该集合时,则必中国煤化工的值都必须为14即错误CNMHG3500P∠=(1-(1-k/m))(5)0.0020.0040.0060.008001错误率由(1-b/m)"≤(1-1/则P2和标图3 Bloom filter错误率与向量空间关系图准布隆过滤器的错误率(设为P1)的关系如图5所小第3期张华,郑世珏,童德茂: Bloom filter技术及应用隆过滤器可以解决集合元素的删除问题。它通过定义m位的整型向量空间C作为向量V的计数器,计005数器的初始值都为0,元素插人时,相应位对应计数器向量C(i)值赠1,删除时,将对应位计数器向量0元素个数n105应用举例p2随着网络发展, Bloom filter的网络应用非常广泛。P2P网络中查找资源操作,可以对每条网络通路保存 Bloom Filter,当命中时,则选择该通路访元素个数n问。广播消息时,可以检测某个P是否已发包。检测广播消息包的环路,将 Bloom filter保存图5独立和标准 bloom filter错误率比较图在包里,每个节点将自己添加人 Bloom Filter。信息由实验分析,当m=120时,随着n的增加,P2队列管理,使用 Counter bloom Filter管理信息流渐渐大于Pl,当m=500时,P2≈P1,所以当m量。下面列举几个典型的应用案例。>>n时,P2和P1相等。因此,独立空间布隆过滤5.1 key-value加快查询器在元素个数和存储空间相差较大时,在错误率不Bloom- Filter可以与一些 key-value的数据库降低的条件下,使k个哈希函数可以并行访间位数起使用来加快查询。一般 key-value存储系统的组,从而提高程序性能。values存在硬盘,查询比较耗费时间。将 Storage的数据都插入Blom- Filter,在 Filter中查询都不存在4布隆过滤器的变种时,就不需要去 Storage查询了。当 False positionloom-Filter一般用于在大数据的集合中判定出现时,只会导致一次多余的 Storage查询。由于某元素是否存在。例如拼音检查、邮件服务器中的 Bloom-Filter所用的空间非常小,所有BF可以常驻垃圾邮件过滤器,搜索引擎领域网络蜘蛛的URL内存。这样对于大部分不存在的元素,只需要访问过滤,还可以实现数据字典,进行数据的判重。随内存中的 Bloom -Filter就可以判断了,只有一小部着应用需求,出现 Bloom filter的多个变种,主要有分,需要访问硬盘上的 key-value数据库,从而大大压缩布隆过滤器、计数布隆过滤器等地提高查询效率。4.1压缩布隆过滤器5.2 Google的 Bigtable布隆过滤器早期被应用于分布式数据库中节Gooe的 Bigtable也使用了 Bloom filter,以减点间的数据传输,当在不同节点之间传输数据时,少不存在的行或列在磁盘上的查询,大大提高了数希望尽量降低数据传输量,因此考虑如何在不降低据库查询操作的性能。错误率的条件下压缩布隆过滤器。由前面分析知5.3 Proxy-Cacheln2|,布隆过滤器的错误率最小,由文献在 Internet cache protocol中的 Proxy-Cache2很多都是使用 Bloom Filter存储URIs,除了高效的[刀]香浓编码原理知,当K取最优哈希函数个数查询外,还能很方便的传输交换 Cache信息。时,布隆过滤器的压缩率为0,因此,必须在k、m和5.4垃圾邮件地址过滤压缩率之间取得平衡点。针对分布式数据库,采用像网易、QQ这样的公众电子邮件提供商,需要适当增大本地节点存储空间m,既可以降低错误不断地过滤来自发送垃圾邮件的人的垃圾邮件,办率,还可以取得更小的k值,获得较高的压缩率,提法中国煤化工邮件的cma地址进行高数据传输效率CNMHG4.2计数布隆过滤器标准布隆过滤器中集合S的所有元素共享结语向量的m位,当删除元素时,将该元素对应的k个布隆过滤器最初应用于弱密码字典中,2000位置为0,则会影响集合中其他元素的判断。计数布年后WEB网络的发展,渐渐出现应用于P反向追阜阳师范学院学报(自然科学版)第31卷踪、高速缓存共享,随着应用的深入逐渐产生了布bloomslides. pdf隆过滤器的变种,如计数布隆过滤器、分层布隆过[5]彭艳兵,龚俭,刘卫江,等. Bloom filter哈希空间的滤器等,分别应用于文本检索系统、PP文件存储元素还原[J].电子学报,2006,34(5):821-826系统和测量网络流。随着大数据时代的来临,海量6]BteA, Mitzenmacher M. Network applications of数据处理成为布隆过滤器的研究和应用热点,比如bloom filters: A Survey [J]. Internet Mathematics003,1(4):485-5当前的垃圾邮件处理,提取某日访问百度次数最多[7]肖明忠,代亚非, Bloom filter及其应用综述[J].计算的IP和在线广告匹配问题等。机科学,2004,31(4):180-182[8]张丽果.基于布隆过滤器的字符串模糊匹配算法的参考文献:FPGA实现[J].电子设计工程,2013,21(9):95981]谢鲲,文吉刚,张大方,等.布鲁姆过滤器查询算法9徐韵洁,冉晓旻蚁群算法在网格资源发现中的应用[J].计算机应用研究,2013,30(5):1492-49[J].软件学报,2009,20(1):96-1082]黄涛.布隆过滤器在网页去重中的研究与应用10]CSDN.海量数据处理算法[EB/OL].(201208-14)http://blnet/hguisu/article/ details/[D].大连:大连海事大学信息科学与技术学院78661732013[11 Wikipedia. Bloom Filter[ DB/OL].(2013-11-12[3] Rajaraman A, Ullman J D.大数据互联网大规模数据挖掘与分布式处理[M].王斌.译.7版.北京:人民http://en.wikipediaorg/wiki邮电出版社,2012:9698[12]时磊,杨骅,王红梅,等.基于布隆过滤器的事务存储架构中的高速缓存[J].微电子学与计算机,[4 Honoroff J. An examination of Bloom Filters and their2011,28(3):141-143applicationsEb/Ol].(2006-03-16).http://wwwfabian/ courses/CS600. 624/slides/H中国煤化工CNMHG