第31卷第3期阜陽師范學(xué)院學(xué)報(自然科學(xué)版)Vol. 31. No. 32014年9月Journal of Fuyang Teachers College( Natural ScienceSep.2014Bloom filter技術(shù)及應(yīng)用張華,鄭世玨2,童德茂(1.阜陽職業(yè)技術(shù)學(xué)院工程科技學(xué)院,安徽阜陽236031;2.華中師范大學(xué)計算機(jī)科學(xué)系,湖北武漢430079摘要; Bloom filter采用位串向量表示數(shù)據(jù)集合,能夠?qū)崿F(xiàn)高效集合查詢的數(shù)據(jù)結(jié)構(gòu)。首先介紹了標(biāo)準(zhǔn)布隆過濾器的概念和工作原理,然后通過實(shí)驗分析布隆過濾器的錯誤率、空間向量和哈希函數(shù)數(shù)量三者之間的動態(tài)相關(guān)關(guān)系,并對獨(dú)立空間布隆過濾器和標(biāo)準(zhǔn)布隆過濾器性能進(jìn)行對比,最后討論了 Bloom filter的變種及應(yīng)用關(guān)鍵詞: Bloom filter;錯誤率;標(biāo)準(zhǔn)布隆過濾器;獨(dú)立空間布隆過濾器中圖分類號:TP301文獻(xiàn)標(biāo)識碼: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提出的采用位編碼后的位數(shù)比集合元素位數(shù)少,因此節(jié)省了存儲串向量表示數(shù)據(jù)集合,能夠?qū)崿F(xiàn)高效集合査詢的數(shù)空間。編碼位數(shù)取決于你所期望的錯誤率,編碼位據(jù)結(jié)構(gòu)。它是以哈希表為基礎(chǔ)的算法。哈希表數(shù)越多,錯誤就越少,反之則越大,即“正確率換取的基本原理是使用一個容量相對合適的數(shù)組來?？臻g”的思想。布隆過濾器就在這一思想下產(chǎn)生。存數(shù)據(jù),在記錄的存儲位置和關(guān)鍵字之間建立一個布隆過濾器算法由于高效的查找速度被廣泛運(yùn)用。確定的對應(yīng)關(guān)系函數(shù)h(即哈希函數(shù)),然后,使每例如 Web cache共享、文本文件檢索系統(tǒng)、P2P網(wǎng)個關(guān)鍵字的內(nèi)容,通過這個哈希函數(shù)計算h(x)來絡(luò)文件存儲系統(tǒng)等網(wǎng)絡(luò)應(yīng)用領(lǐng)域。目前國內(nèi)外的得到該關(guān)鍵字對應(yīng)的存儲位置,之后將該關(guān)鍵字存研究主要有標(biāo)準(zhǔn)布隆過濾器和多種變種,例如壓縮在數(shù)組的相應(yīng)位置中2。人們發(fā)現(xiàn)為了查找而將布隆過濾器、計數(shù)布隆過濾器、分層布隆過濾器、動整個元素都存儲在數(shù)組中,空間需求很大,因此對態(tài)布隆過濾器等。文章重點(diǎn)分析了標(biāo)準(zhǔn)布隆過濾哈希表進(jìn)行改進(jìn),并不直接將集合元素存在數(shù)組器里,而是將每個元素編碼然后將編碼存在數(shù)組里。標(biāo)TH中國煤化衛(wèi)立空間布隆過濾器和CNMHG比較,最后對布隆過濾收稿日期:201402-27基金項目:中央高?；究蒲袠I(yè)務(wù)費(fèi)項目(CCNU11C01003)資助。作者簡介:張華(1975-),女,碩士,副教授。研究方向:數(shù)據(jù)挖掘。第3期張華,鄭世玨,童德茂: Bloom filter技術(shù)及應(yīng)用器的相關(guān)變種及應(yīng)用做了簡單綜述。的結(jié)果是 false,說明該元素肯定不在集合內(nèi);如果1標(biāo)準(zhǔn)布隆過濾器返還的是true,說明元素可能存在于集合中。由前面分析知道,使用 Bloom filter判斷一個一個布隆過濾器由以下幾部分組成(3。元素是否屬于集合時,可能岀現(xiàn)錯判,可能把不屬(i) Bloom filter用一個長度為m的位向量V于這個集合的元素誤判為屬于這個集合( False表示集合中的元素,每個位的初始值都設(shè)為0。Positive)4,但是,不會把屬于這個集合的元素誤(i)k個相互獨(dú)立均勻分布的哈希函數(shù)組成的判為不屬于這個集合。下面通過計算來估計發(fā)生集合H。“假陽性”錯誤率P的大小。(i)n個元素組成的集合S。當(dāng)集合S={x1,x2,…,xn}的所有元素都被k布隆過濾器的工作原理分為兩步:個哈希函數(shù)映射到長為m的向量V中時,對于一個第一步,數(shù)據(jù)裝入。k個相互獨(dú)立的哈希函數(shù)鍵值在m個空間的向量中,被映射為1的概率是分別將集合S中的n個元素映射到向量V中的相應(yīng)1/m,則對立事件,被映射為0的概率是1-1/m位置,將V中相應(yīng)位置為1,如圖1所示。k*n個鍵值都被映射為0的概率為(1-1/m)。第二步,數(shù)據(jù)判斷。當(dāng)新元素y到來時,對y進(jìn)也就是,當(dāng)集合中所有元素都映射完畢后,V向量行k次哈希運(yùn)算,檢查所有的h1(y),h2(y),任一位為0的概率為(1-1/m),它的對立事件h2(y)對應(yīng)向量V中的位是否全部為1,如果是,則當(dāng)集合中所有元素都映射完畢后,V向量任一位為元素y屬于集合S,否則,認(rèn)為y不屬于集合S1的概率L為1-(1-1/m)。即L=1又當(dāng)m趨向無窮大時,(1-1)的極限為01001001/e,故L≈1-(1位當(dāng)不屬于集合S的元素y誤判為屬于集合S圖1 Bloom filter工作原理圖時,則必須滿足y在Ⅴ向量的k個映射位的值都必須為1。即錯誤率P為L。2性能分析即P=(1-e-kn/m)哈希函數(shù)最優(yōu)個數(shù)布隆過濾器是基于哈希表的算法,對每個元素為了計算哈希函數(shù)個數(shù),針對(1)式令f的判斷要進(jìn)行k次哈希運(yùn)算,它的時間復(fù)雜度為0(k)。它的存儲空間由元素通過哈希函數(shù)映射到D P=(1-f'=exp(kIn(1-5))=exp(向量空間的位數(shù)大小決定,由引言分析知道布隆過如m1n(1-0),令g=-m1mAm(-),則當(dāng)g濾器是通過允許少量的錯誤來節(jié)省大量的存儲空取最小值時,錯誤率P最小。又有當(dāng)lnf=間,因此它的空間復(fù)雜度和錯誤率是動態(tài)相關(guān)的,1n(1-時|lnn(1-f取最大值,故f=1-f下面具體分析布隆過濾器的錯誤率、位數(shù)組大小及推得∫=1/2時,錯誤率P最小。由定義廠=em哈希函數(shù)的個數(shù)之間的關(guān)系1/2可得2.1錯誤率估計布隆過濾器判斷某個數(shù)據(jù)對象y是否屬于集k=mIn 2合S時,先檢查表示y的位向量對應(yīng)的位,如果均中國煤化工ny=(1/2)2(3)為1,則該數(shù)據(jù)對象屬于集合S,否則不屬于集合SHCNMH(取最優(yōu)個數(shù)時,錯誤但是,即使是采用均勻且不同的哈希函數(shù),地址沖率p和集合中元素個數(shù)n和向量大小m相關(guān)。突也是不能避免的,因此布隆過濾器算法可能對位假設(shè)給定元素n=400,向量m=3580,則由向量中的同一個位多次置1,所以在進(jìn)行數(shù)據(jù)判斷(2)式可計算k=7,由(3)式得p≈0.014由仿真時可能出現(xiàn)錯判。也就是說,如果布隆過濾器返還如圖2所示,錯誤率P處于最低點(diǎn)。阜陽師范學(xué)院學(xué)報(自然科學(xué)版)第31卷3獨(dú)立空間布隆過濾器☆m=3580n-400前面介紹的通過k個哈希函數(shù)將n個元素映射到m個向量空間V中,其中每個哈希函數(shù)的映射☆☆劉身身卒☆☆空間都是{0.1,…,m-2,m-1},因此也稱為共享空間布隆過濾器。不同關(guān)鍵字被同一哈希函數(shù)映射到哈?？臻g的同一位置,即對任何k,≠k存在h(k)=h(k.),把它稱為內(nèi)部沖突。對不同關(guān)鍵0.02宇被不同哈希函數(shù)映射到同一哈?？臻g,即對任何k≠k存在hn(k)=h(k,),稱為外部沖突。對應(yīng)10哈希函數(shù)個數(shù)k0內(nèi)部沖突,我們可以通過選擇哈希函數(shù)來解決,對于外部沖突,我們采用將每個哈希函數(shù)的映射空間圖2 Bloom filter錯誤率與哈希函數(shù)個數(shù)關(guān)系圖區(qū)分開來,即獨(dú)立哈希空間布隆過濾器5。我們將況下選取適量哈希函數(shù)可以降低錯誤率,但是這句平均分成連續(xù)的k段,每段m/k位,對向量空2.3位數(shù)組大小設(shè)計由以上分析,在確定元素個數(shù)和向量空間的情每一段只進(jìn)行一次哈希操作,則哈希函數(shù)的映射范種方法降低的程度有限。如果給定布隆過濾器的(i-1)(1≤i≤k)錯誤率上限p0,取到最優(yōu)哈希函數(shù)數(shù)量時,要讓錯映射空間如圖4所示。誤率P不超過上限p0,表示集合中每個元素,最少需要多少向量空間由(3)可推出x log, p(4)通過實(shí)驗可得如圖3所示,在能夠取最優(yōu)哈希函數(shù)前提下,錯誤率和向量空間成反比,即錯誤率越低,則所需空間越大m/k位由公式(4)可以得出,在給定錯誤率的前提下,所需的空間可以計算。假如設(shè)p=0.001,則圖4獨(dú)立空間布隆過濾器圖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是,當(dāng)集合中所有元素都映射完畢,向量中m/k段中任意一位值為0的概率為(1-k/m)",它的對立事件,當(dāng)集合中所有元素都映射完畢,向量中5751m/k段任意一位值為1的概率為1-(1-k/m)。5174當(dāng)不屬于集合S的元素y誤判為屬于該集合時,則必中國煤化工的值都必須為14即錯誤CNMHG3500P∠=(1-(1-k/m))(5)0.0020.0040.0060.008001錯誤率由(1-b/m)"≤(1-1/則P2和標(biāo)圖3 Bloom filter錯誤率與向量空間關(guān)系圖準(zhǔn)布隆過濾器的錯誤率(設(shè)為P1)的關(guān)系如圖5所小第3期張華,鄭世玨,童德茂: Bloom filter技術(shù)及應(yīng)用隆過濾器可以解決集合元素的刪除問題。它通過定義m位的整型向量空間C作為向量V的計數(shù)器,計005數(shù)器的初始值都為0,元素插人時,相應(yīng)位對應(yīng)計數(shù)器向量C(i)值贈1,刪除時,將對應(yīng)位計數(shù)器向量0元素個數(shù)n105應(yīng)用舉例p2隨著網(wǎng)絡(luò)發(fā)展, Bloom filter的網(wǎng)絡(luò)應(yīng)用非常廣泛。P2P網(wǎng)絡(luò)中查找資源操作,可以對每條網(wǎng)絡(luò)通路保存 Bloom Filter,當(dāng)命中時,則選擇該通路訪元素個數(shù)n問。廣播消息時,可以檢測某個P是否已發(fā)包。檢測廣播消息包的環(huán)路,將 Bloom filter保存圖5獨(dú)立和標(biāo)準(zhǔn) bloom filter錯誤率比較圖在包里,每個節(jié)點(diǎn)將自己添加人 Bloom Filter。信息由實(shí)驗分析,當(dāng)m=120時,隨著n的增加,P2隊列管理,使用 Counter bloom Filter管理信息流漸漸大于Pl,當(dāng)m=500時,P2≈P1,所以當(dāng)m量。下面列舉幾個典型的應(yīng)用案例。>>n時,P2和P1相等。因此,獨(dú)立空間布隆過濾5.1 key-value加快查詢器在元素個數(shù)和存儲空間相差較大時,在錯誤率不Bloom- Filter可以與一些 key-value的數(shù)據(jù)庫降低的條件下,使k個哈希函數(shù)可以并行訪間位數(shù)起使用來加快查詢。一般 key-value存儲系統(tǒng)的組,從而提高程序性能。values存在硬盤,查詢比較耗費(fèi)時間。將 Storage的數(shù)據(jù)都插入Blom- Filter,在 Filter中查詢都不存在4布隆過濾器的變種時,就不需要去 Storage查詢了。當(dāng) False positionloom-Filter一般用于在大數(shù)據(jù)的集合中判定出現(xiàn)時,只會導(dǎo)致一次多余的 Storage查詢。由于某元素是否存在。例如拼音檢查、郵件服務(wù)器中的 Bloom-Filter所用的空間非常小,所有BF可以常駐垃圾郵件過濾器,搜索引擎領(lǐng)域網(wǎng)絡(luò)蜘蛛的URL內(nèi)存。這樣對于大部分不存在的元素,只需要訪問過濾,還可以實(shí)現(xiàn)數(shù)據(jù)字典,進(jìn)行數(shù)據(jù)的判重。隨內(nèi)存中的 Bloom -Filter就可以判斷了,只有一小部著應(yīng)用需求,出現(xiàn) Bloom filter的多個變種,主要有分,需要訪問硬盤上的 key-value數(shù)據(jù)庫,從而大大壓縮布隆過濾器、計數(shù)布隆過濾器等地提高查詢效率。4.1壓縮布隆過濾器5.2 Google的 Bigtable布隆過濾器早期被應(yīng)用于分布式數(shù)據(jù)庫中節(jié)Gooe的 Bigtable也使用了 Bloom filter,以減點(diǎn)間的數(shù)據(jù)傳輸,當(dāng)在不同節(jié)點(diǎn)之間傳輸數(shù)據(jù)時,少不存在的行或列在磁盤上的查詢,大大提高了數(shù)希望盡量降低數(shù)據(jù)傳輸量,因此考慮如何在不降低據(jù)庫查詢操作的性能。錯誤率的條件下壓縮布隆過濾器。由前面分析知5.3 Proxy-Cacheln2|,布隆過濾器的錯誤率最小,由文獻(xiàn)在 Internet cache protocol中的 Proxy-Cache2很多都是使用 Bloom Filter存儲URIs,除了高效的[刀]香濃編碼原理知,當(dāng)K取最優(yōu)哈希函數(shù)個數(shù)查詢外,還能很方便的傳輸交換 Cache信息。時,布隆過濾器的壓縮率為0,因此,必須在k、m和5.4垃圾郵件地址過濾壓縮率之間取得平衡點(diǎn)。針對分布式數(shù)據(jù)庫,采用像網(wǎng)易、QQ這樣的公眾電子郵件提供商,需要適當(dāng)增大本地節(jié)點(diǎn)存儲空間m,既可以降低錯誤不斷地過濾來自發(fā)送垃圾郵件的人的垃圾郵件,辦率,還可以取得更小的k值,獲得較高的壓縮率,提法中國煤化工郵件的cma地址進(jìn)行高數(shù)據(jù)傳輸效率CNMHG4.2計數(shù)布隆過濾器標(biāo)準(zhǔn)布隆過濾器中集合S的所有元素共享結(jié)語向量的m位,當(dāng)刪除元素時,將該元素對應(yīng)的k個布隆過濾器最初應(yīng)用于弱密碼字典中,2000位置為0,則會影響集合中其他元素的判斷。計數(shù)布年后WEB網(wǎng)絡(luò)的發(fā)展,漸漸出現(xiàn)應(yīng)用于P反向追阜陽師范學(xué)院學(xué)報(自然科學(xué)版)第31卷蹤、高速緩存共享,隨著應(yīng)用的深入逐漸產(chǎn)生了布bloomslides. pdf隆過濾器的變種,如計數(shù)布隆過濾器、分層布隆過[5]彭艷兵,龔儉,劉衛(wèi)江,等. Bloom filter哈?？臻g的濾器等,分別應(yīng)用于文本檢索系統(tǒng)、PP文件存儲元素還原[J].電子學(xué)報,2006,34(5):821-826系統(tǒng)和測量網(wǎng)絡(luò)流。隨著大數(shù)據(jù)時代的來臨,海量6]BteA, Mitzenmacher M. Network applications of數(shù)據(jù)處理成為布隆過濾器的研究和應(yīng)用熱點(diǎn),比如bloom filters: A Survey [J]. Internet Mathematics003,1(4):485-5當(dāng)前的垃圾郵件處理,提取某日訪問百度次數(shù)最多[7]肖明忠,代亞非, Bloom filter及其應(yīng)用綜述[J].計算的IP和在線廣告匹配問題等。機(jī)科學(xué),2004,31(4):180-182[8]張麗果.基于布隆過濾器的字符串模糊匹配算法的參考文獻(xiàn):FPGA實(shí)現(xiàn)[J].電子設(shè)計工程,2013,21(9):95981]謝鯤,文吉剛,張大方,等.布魯姆過濾器查詢算法9徐韻潔,冉曉旻蟻群算法在網(wǎng)格資源發(fā)現(xiàn)中的應(yīng)用[J].計算機(jī)應(yīng)用研究,2013,30(5):1492-49[J].軟件學(xué)報,2009,20(1):96-1082]黃濤.布隆過濾器在網(wǎng)頁去重中的研究與應(yīng)用10]CSDN.海量數(shù)據(jù)處理算法[EB/OL].(201208-14)http://blnet/hguisu/article/ details/[D].大連:大連海事大學(xué)信息科學(xué)與技術(shù)學(xué)院78661732013[11 Wikipedia. Bloom Filter[ DB/OL].(2013-11-12[3] Rajaraman A, Ullman J D.大數(shù)據(jù)互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理[M].王斌.譯.7版.北京:人民http://en.wikipediaorg/wiki郵電出版社,2012:9698[12]時磊,楊驊,王紅梅,等.基于布隆過濾器的事務(wù)存儲架構(gòu)中的高速緩存[J].微電子學(xué)與計算機(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