多布魯姆過(guò)濾器檢索算法研究

田小梅，胡 燦，李 浪

（1.衡陽(yáng)師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖南 衡陽(yáng) 421002；2.湖南環(huán)境生物職業(yè)技術(shù)學(xué)院 藝術(shù)設(shè)計(jì)學(xué)院，湖南 衡陽(yáng) 421005）

中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心最近發(fā)布的《第36次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》指出：截至2015年上半年止，我國(guó)網(wǎng)民數(shù)量占人口總數(shù)的48.8%，達(dá)6.68億［1］。計(jì)算機(jī)網(wǎng)絡(luò)的迅猛發(fā)展，產(chǎn)生了包括各類網(wǎng)絡(luò)交互數(shù)據(jù)和業(yè)務(wù)數(shù)據(jù)在內(nèi)的海量數(shù)據(jù)［2］，人類迎來(lái)了海量數(shù)據(jù)時(shí)代，開(kāi)始用拍字節(jié)（PB，Petabyte，千萬(wàn)億字節(jié)）作為基本單位來(lái)計(jì)量各類數(shù)據(jù)。海量數(shù)據(jù)的處理得到了越來(lái)越多人的重視，尤其是對(duì)于谷歌、百度、騰訊等涉及海量業(yè)務(wù)數(shù)據(jù)的公司。在PB、EB（Exabyte，1EB＝1024PB）乃至ZB（Zettabyte，1ZB＝1024EB）數(shù)量級(jí)的數(shù)據(jù)汪洋中定位和檢索某個(gè)特定數(shù)據(jù)或特定數(shù)據(jù)記錄，對(duì)于網(wǎng)絡(luò)設(shè)計(jì)者和網(wǎng)絡(luò)數(shù)據(jù)管理者來(lái)說(shuō)是一個(gè)大的挑戰(zhàn)。

1 處理海量數(shù)據(jù)的布魯姆過(guò)濾器

處理海量數(shù)據(jù)，通常需要一個(gè)索引類型的數(shù)據(jù)結(jié)構(gòu)，用于快速判斷數(shù)據(jù)記錄是否存在于數(shù)據(jù)集中。能用于處理海量數(shù)據(jù)的常用索引結(jié)構(gòu)有哈希（hash）、位圖（bitmap）、布魯姆過(guò)濾器（Bloom fil－ter）、堆（heap）、映射化簡(jiǎn)（mapreduce）、特里樹(shù)（trie tree）等。布魯姆過(guò)濾器這一數(shù)據(jù)結(jié)構(gòu)其空間復(fù)雜度和時(shí)間復(fù)雜度均較低，可以用于高效檢索某元素是否歸屬某集合，但是，它有一定的誤判可能：將原本不在某集合中的元素誤判為該集合的成員，這種現(xiàn)象稱假陽(yáng)性現(xiàn)象。所以，布魯姆過(guò)濾器檢索算法不適合“零誤判”的應(yīng)用場(chǎng)合，但在允許少量誤差的場(chǎng)合中，布魯姆過(guò)濾器是一類處理海量數(shù)據(jù)的首選方案。

布魯姆過(guò)濾器算法［3］最初是由Bloom提出的，當(dāng)時(shí)的應(yīng)用領(lǐng)域主要是拼寫檢查、數(shù)據(jù)庫(kù)系統(tǒng)、文件系統(tǒng)等。計(jì)算機(jī)技術(shù)與互聯(lián)網(wǎng)技術(shù)在高速發(fā)展，各類網(wǎng)絡(luò)數(shù)據(jù)的規(guī)模在不斷增長(zhǎng)，布魯姆過(guò)濾器算法相應(yīng)地得到了前所未有的發(fā)展：新的應(yīng)用領(lǐng)域以及變種層出不窮，被大量運(yùn)用于各類分布式系統(tǒng)及網(wǎng)絡(luò)系統(tǒng)［4］，如IP查找［5］、包分類［6］、網(wǎng)絡(luò)測(cè)量與監(jiān)測(cè)［7］、搜索引擎［8］、P2P 網(wǎng)絡(luò)路由算法［9］、內(nèi)容分發(fā)與數(shù)據(jù)同步［10－13］、網(wǎng)絡(luò) 安全［14－15］、生物 工程［16－17］、分布式存儲(chǔ)系統(tǒng)［18］、無(wú)線傳感器網(wǎng)絡(luò)［19］、云計(jì)算數(shù)據(jù)中心［20］等。

2 多布魯姆過(guò)濾器檢索算法

使用單個(gè)的布魯姆過(guò)濾器結(jié)構(gòu)即可查詢?cè)厥欠駥儆谀硞€(gè)集合，這一方法我們稱其為單布魯姆過(guò)濾器檢索算法（圖1）。有時(shí)，在各集合相應(yīng)的布魯姆過(guò)濾器結(jié)構(gòu)已知的基礎(chǔ)上，我們需要查詢?cè)厥欠駥儆诙鄠€(gè)集合參與運(yùn)算后的結(jié)果集合（并集、交集、差集等），這樣，單布魯姆過(guò)濾器檢索算法存在無(wú)法勝任的情形。同時(shí)查詢多個(gè)布魯姆過(guò)濾器完成數(shù)據(jù)檢索操作的方法稱為多布魯姆過(guò)濾器檢索算法（如圖2所示）。如何高效地在多個(gè)布魯姆過(guò)濾器結(jié)構(gòu)上完成檢索操作，成為目前具有挑戰(zhàn)性的課題領(lǐng)域。

圖1 單布魯姆過(guò)濾器檢索算法

圖2 多布魯姆過(guò)濾器檢索算法（以檢索交集為例）

3 多布魯姆過(guò)濾器檢索算法應(yīng)用與研究

與單布魯姆過(guò)濾器檢索算法的研究正在廣泛開(kāi)展不同，關(guān)于多布魯姆過(guò)濾器檢索算法的研究則要少得較多，概括地說(shuō)主要有兩個(gè)方面：①多布魯姆過(guò)濾器直接檢索算法（即并行布魯姆過(guò)濾器）的應(yīng)用研究；②多個(gè)布魯姆過(guò)濾器間的代數(shù)運(yùn)算及其應(yīng)用研究。

3.1 多布魯姆過(guò)濾器直接檢索算法的應(yīng)用

多布魯姆過(guò)濾器直接檢索算法并行查詢多個(gè)布魯姆過(guò)濾器，以獲取特定信息。這類算法主要用于包分類系統(tǒng)、IP路由查找等方面。

由于IPv6地址的廣泛使用，傳統(tǒng)包分類器變得越來(lái)越復(fù)雜，流標(biāo)識(shí)符（包含源IP、目標(biāo)IP的五元組）數(shù)量越來(lái)越多，從而導(dǎo)致包分類過(guò)程中使用的緩存也越來(lái)越大，流標(biāo)識(shí)符的檢索過(guò)程越來(lái)越慢。文獻(xiàn)［21］使用并行布魯姆過(guò)濾器構(gòu)建包分類緩存，一個(gè)哈希函數(shù)對(duì)應(yīng)一個(gè)布魯姆過(guò)濾器結(jié)構(gòu)，將流標(biāo)識(shí)符映射到多個(gè)布魯姆過(guò)濾器。當(dāng)數(shù)據(jù)包到達(dá)時(shí)，并行檢索所有布魯姆過(guò)濾器，如果所有二進(jìn)制位均為1，則認(rèn)定數(shù)據(jù)包在緩存中，然后將其進(jìn)行轉(zhuǎn)發(fā)。實(shí)驗(yàn)結(jié)果表明：與精確緩存方案相比，這種近似緩存策略其檢索速度更快，存儲(chǔ)效率更高。

文獻(xiàn)［22］則指出，文獻(xiàn)［21］的包分類方法具有能耗大及呑吐量低的缺點(diǎn)，針對(duì)其缺陷，提出了新的包分類程序：將多個(gè)布魯姆過(guò)濾器結(jié)構(gòu)組織成二叉樹(shù)的形式，實(shí)驗(yàn)數(shù)據(jù)表明該算法具有更少的能耗以及更大的呑吐量。

文獻(xiàn)［23］將布魯姆過(guò)濾器用于IP查找過(guò)程中的最長(zhǎng)前綴匹配過(guò)程。一個(gè)布魯姆過(guò)濾器對(duì)應(yīng)一個(gè)IP前綴長(zhǎng)度，在查找匹配的最長(zhǎng)前綴過(guò)程中并行檢索這一系列的布魯姆過(guò)濾器結(jié)構(gòu)。

事實(shí)上，文獻(xiàn)［21］和文獻(xiàn)［23］等工作是在多個(gè)布魯姆過(guò)濾器結(jié)構(gòu)上完成并行檢索，查找并集成員的具體應(yīng)用實(shí)例。文獻(xiàn)［24］則系統(tǒng)地分析了雙（多）布魯姆過(guò)濾器直接檢索算法檢索并集、交集成員等的性能問(wèn)題，并給出了相關(guān)的應(yīng)用場(chǎng)合，從而將多布魯姆過(guò)濾器直接檢索算法的檢索范圍從并集拓展到了交集、補(bǔ)集、差集或?qū)ΨQ差。

3.2 布魯姆過(guò)濾器代數(shù)運(yùn)算與應(yīng)用

早在2002年，Whitaker等人就在Icarus系統(tǒng)中將布魯姆過(guò)濾器用于路由環(huán)路檢測(cè)［25］，其具體過(guò)程為：長(zhǎng)度不大的小型布魯姆過(guò)濾器被加入數(shù)據(jù)包的頭部，用于映射數(shù)據(jù)包轉(zhuǎn)發(fā)路徑上已訪問(wèn)的節(jié)點(diǎn)列表，同時(shí)，每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)與數(shù)據(jù)包內(nèi)布魯姆過(guò)濾器等長(zhǎng)的掩碼（該掩碼實(shí)際上就是一個(gè)僅包含節(jié)點(diǎn)自身地址信息的布魯姆過(guò)濾器），當(dāng)數(shù)據(jù)包到達(dá)某節(jié)點(diǎn)時(shí)，將節(jié)點(diǎn)的掩碼與數(shù)據(jù)包中的小型布魯姆過(guò)濾器逐位完成“或”運(yùn)算（即“并”運(yùn)算），比較運(yùn)算前后的布魯姆過(guò)濾器，若相同，則說(shuō)明在該節(jié)點(diǎn)處極可能形成了環(huán)路。

文獻(xiàn)［26］使用類似于文獻(xiàn)［25］的包內(nèi)布魯姆過(guò)濾器以及“位或”運(yùn)算，完成P2P網(wǎng)絡(luò)中的副本維護(hù)工作。它所采用的副本維護(hù)機(jī)制與文獻(xiàn)［25］中的環(huán)路檢測(cè)機(jī)制相似：將副本更新報(bào)文傳播時(shí)經(jīng)過(guò)的節(jié)點(diǎn)地址列表用布魯姆過(guò)濾器表示，添加到副本更新報(bào)文的頭部。根據(jù)副本更新報(bào)文中布魯姆過(guò)濾器的變化情況，判斷是否需要更新目標(biāo)節(jié)點(diǎn)的副本。

布魯姆過(guò)濾器并運(yùn)算也能用于關(guān)鍵字檢索，譬如，Gnutella2文件共享協(xié)議［27］將在文件中抽取的關(guān)鍵字映射到布魯姆過(guò)濾器結(jié)構(gòu)中。Gnutella2中的節(jié)點(diǎn)分屬于兩個(gè)層次：超節(jié)點(diǎn)層、葉節(jié)點(diǎn)層。葉節(jié)點(diǎn)發(fā)送本地布魯姆過(guò)濾器給上層的超節(jié)點(diǎn)，超節(jié)點(diǎn)則合并它下層所有葉節(jié)點(diǎn)的布魯姆過(guò)濾器，并將合并后的布魯姆過(guò)濾器傳送給與其相鄰的超節(jié)點(diǎn)。在進(jìn)行關(guān)鍵字檢索時(shí)，葉節(jié)點(diǎn)首先檢索與它直接相連的超節(jié)點(diǎn)，若檢索不成功，則由超節(jié)點(diǎn)將關(guān)鍵字檢索請(qǐng)求轉(zhuǎn)發(fā)給相鄰超節(jié)點(diǎn)。

Rhea和Kubiatowicz則使用布魯姆過(guò)濾器的并運(yùn)算來(lái)查找資源的位置，并稱這種算法為資源路由算法［28］。資源路由表在構(gòu)造過(guò)程中使用了布魯姆過(guò)濾器的并運(yùn)算。當(dāng)節(jié)點(diǎn)收到文件共享請(qǐng)求時(shí)，首先在其資源路由表中查找，若查找失敗，則再使用Tapestry等確定性路由協(xié)議進(jìn)行搜索。

標(biāo)準(zhǔn)布魯姆過(guò)濾器使用比特向量保存數(shù)據(jù)信息，文獻(xiàn)［29］的研究工作表明：可使用多個(gè)比特向量“位或”、“位與”運(yùn)算后得到的新比特向量來(lái)檢索并集、交集元素。

文獻(xiàn)［30］則完整地定義了標(biāo)準(zhǔn)布魯姆過(guò)濾器的并運(yùn)算、交運(yùn)算，且將并運(yùn)算推廣到了其它使用比特向量作為存儲(chǔ)結(jié)構(gòu)的布魯姆過(guò)濾器，如動(dòng)態(tài)布魯姆過(guò)濾器、多維布魯姆過(guò)濾器、多維動(dòng)態(tài)布魯姆過(guò)濾器等。

文獻(xiàn)［31］的作者指出：標(biāo)準(zhǔn)布魯姆過(guò)濾器間除可進(jìn)行并運(yùn)算、交運(yùn)算之外，還能完成其它代數(shù)運(yùn)算，如補(bǔ)運(yùn)算、減運(yùn)算及異或運(yùn)算，詳盡地討論了標(biāo)準(zhǔn)布魯姆過(guò)濾器各種代數(shù)運(yùn)算的性質(zhì)，得出如下結(jié)論：標(biāo)準(zhǔn)布魯姆過(guò)濾器并運(yùn)算后的新比特向量與并集的標(biāo)準(zhǔn)布魯姆過(guò)濾器向量是一致的；交運(yùn)算后的新比特向量與交集的標(biāo)準(zhǔn)布魯姆過(guò)濾器比特向量相比，其非零比特?cái)?shù)量稍多，從而產(chǎn)生了稍高的假陽(yáng)性比率；使用標(biāo)準(zhǔn)布魯姆過(guò)濾器并運(yùn)算或交運(yùn)算檢索并集或交集元素時(shí)均不會(huì)產(chǎn)生假陰性誤判；但補(bǔ)、減、異或等運(yùn)算則因?yàn)闀?huì)有較嚴(yán)重的假陰性誤判問(wèn)題，不能用于檢索補(bǔ)集、差集或?qū)ΨQ差元素。

文獻(xiàn)［32］則研究計(jì)數(shù)器向量布魯姆過(guò)濾器間的代數(shù)運(yùn)算，定義了計(jì)數(shù)布魯姆過(guò)濾器的并、交、補(bǔ)、減及異或運(yùn)算，從理論分析和實(shí)驗(yàn)驗(yàn)證兩個(gè)角度對(duì)計(jì)數(shù)布魯姆過(guò)濾器代數(shù)運(yùn)算的特性進(jìn)行了探討，得到如下結(jié)論：計(jì)數(shù)布魯姆過(guò)濾器并、交、補(bǔ)、減及異或運(yùn)算后的新計(jì)數(shù)器向量能用于檢索并集、交集、補(bǔ)集、差集及對(duì)稱差元素，不會(huì)發(fā)生假陰性誤判。在此基礎(chǔ)上，我們提出了一種使用計(jì)數(shù)布魯姆過(guò)濾器減運(yùn)算的數(shù)據(jù)同步方法［12］，新算法能在單輪消息交換過(guò)程中完成精確的數(shù)據(jù)同步。

4 結(jié)束語(yǔ)

在各類分布式網(wǎng)絡(luò)系統(tǒng)中，常常運(yùn)用布魯姆過(guò)濾器來(lái)高效存儲(chǔ)各類海量數(shù)據(jù)，以支持?jǐn)?shù)據(jù)同步、內(nèi)容分發(fā)、資源路由等應(yīng)用中的快速檢索，在這類應(yīng)用中，需要同時(shí)檢索多個(gè)布魯姆過(guò)濾器結(jié)構(gòu)。在多個(gè)布魯姆過(guò)濾器結(jié)構(gòu)上高效地完成海量數(shù)據(jù)的檢索，是多布魯姆過(guò)濾器檢索算法的主要目標(biāo)。目前有關(guān)多布魯姆過(guò)濾器檢索算法的研究工作不多；同時(shí)，這些應(yīng)用研究工作通常集中在多布魯姆過(guò)濾器代數(shù)運(yùn)算中的并運(yùn)算，以及使用多個(gè)布魯姆過(guò)濾器直接檢索并集成員這兩個(gè)方面，對(duì)于其他方面，如多布魯姆過(guò)濾器代數(shù)運(yùn)算中交、減運(yùn)算等的應(yīng)用，所做的研究工作不多，因此，在多布魯姆過(guò)濾器檢索算法領(lǐng)域還存在不少的研究空間。

［1］中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心，第36次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng) 計(jì) 報(bào) 告 ［R］.http：／／www.cnnic.cn／hlwfzyj／hlwxzbg／hlwtjbg／201507／P020150723549500667087.pdf，2015.7.23.

［2］馮丹.海量存儲(chǔ)系統(tǒng)及技術(shù)研究進(jìn)展 ［M］.中國(guó)計(jì)算機(jī)科學(xué)技術(shù)發(fā)展報(bào)告2010.北京：機(jī)械工業(yè)出版社.2011：46－71.

［3］BLOOM B H.Space／time trade－offs in hash coding with allowable errors ［J］.Communications of the ACM，1970，13（7）：422－426.

［4］TARKOMA S，ROTHENBERG C，LAGERSPETZ E.Theory and practice of bloom filters for distributed systems［J］.IEEE Communications Surveys ＆ Tutorials，2012，14（1）：131－155.

［5］YANG T，XIE G G，DUAN R A，et al.Towards practical use of Bloom Filter based IP lookup in operational network ［A］.Proceedings of the Network Operations and Management Symposium（NOMS）2014［C］，2014.1－4.

［6］CHEN Y，OGUNTOYINBO O.Power efficient packet classification using cascaded bloom filter and off－theshelf ternary CAM for WDM networks［J］.Computer Communications，2009，32（2）：349－356.

［7］吳樺，龔儉，楊望.一種基于雙重 Counter Bloom Filter的長(zhǎng) 流 識(shí) 別 算 法 ［J］.軟 件 學(xué) 報(bào)，2010，21（5）：1115－1126.

［8］PANG M，XU G.A personalized search engine research based on Bloom filter［A］.Proceedings of the 2011International Conference on Electric Engineering and Computer（MEC）［C］，Jilin，China，2011.2365－2368.

［9］KUMAR A，XU J，ZEGURA E W.Efficient and scalable query routing for unstructured peer－to－peer networks［A］.Proceedings of the INFOCOM 2005［C］，Miami，F(xiàn)L，United States，2005.1162－1173.

［10］EPPSTEIN D，GOODRICH M T，UYEDA F，et al.What’s the difference？Efficient set reconciliation without prior context［A］.Proceedings of the ACM SIGCOMM 2011［C］，Toronto，Ontario，Canada，2011.218－229.

［11］BYERS J，CONSIDINE J，MITZENMACHER M，et al.Informed content delivery across adaptive overlay networks［J］.ACM SIGCOMM Computer Communication Review，2002，32（4）：47－60.

［12］田小梅，張大方，謝鯤，等.基于計(jì)數(shù)布魯姆過(guò)濾器的集合調(diào)和算法 ［J］.通信學(xué)報(bào)，2012，33（8）：119－127.

［13］ZHAO T，LIU Z，YAN W，et al.BFBD：A Bloom Filter based Buffering Data Dissemination algorithm for Vehicular Ad hoc Networks ［A］.Proceedings of the 2011IEEE Consumer Communications and Networking Conference（CCNC）［C］，Las Vegas，USA，2011.447－481.

［14］MARKKU A ，TUOMAS A，MIKKO S.Denial－ofservice attacks in bloom－filter－based forwarding ［J］.IEEE／ACM Transactions on Networking （TON），2014，22（5）：1463－1476.

［15］GERAVAND Shahabeddin， AHMADI Mahmood.Bloom filter applications in network security：A stateof－the－art survey［J］.Computer networks，2013，57（18）：4047－4064.

［16］MELSTED P，PRITCHARD J K.Efficient counting of k－mers in DNA sequences using a bloom filter ［J］.BMC bioinformatics，2011，12（1）：1－7.

［17］RATHGEB C，BREITINGER F，Busch C.Alignmentfree cancelable iris biometric templates based on daptive bloom filters ［A］.Proceedings of the International Conference on Biometrics 2013［C］，2013：1－8.

［18］PHYU M P，THEIN N L.Efficient storage management for distributed storage system ［A］.Proceedings of the SPIE －The International Society for Optical Engineering 2012［C］，2012.

［19］LI G L，GUO L J，GAO X，et al.Bloom filter based processing algorithms for the multi－dimensional event query in wireless sensor networks［J］.Journal of network and computer applications，2014，37 （1）：323－333.

［20］LI D，CUI H，HU Y，et al.Scalable data center multicast using multi－class Bloom Filter［A］.Proceedings of the 19th IEEE International Conference on Network Protocols［C］，Vancouver，BC，2011.266－275.

［21］CHANG F，F(xiàn)ENG W，LI K.Approximate caches for packet classification［A］.Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies （INFOCOM） ［C］，2004.2196－2207.

［22］YU H，MAHAPATRA R N.A Power and Throughput－Efficient Packet Classifier with n Bloom Filters［J］.IEEE Transactions on Computers，2011，60（8）：1182－1193.

［23］DHARMAPURIKAR S，KRISHNAMURTHY P，TAYLOR D E.Longest prefix matching using bloom filters［J］.IEEE／ACM Transactions on Networking（TON），2006，14（2）：397－409.

［24］田小梅，張大方，史長(zhǎng)瓊，等.雙布魯姆過(guò)濾器法查詢集合成員 ［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（28）：10－15.

［25］WHITAKER A，WETHERALL D.Forwarding without loops in icarus［A］.Proceedings of the Fifth IEEE Conference on Open Architectures and Network Programming［C］，2002.63－75.

［26］謝鯤，張大方，謝高崗，等.基于軌跡標(biāo)簽的無(wú)結(jié)構(gòu)P2P副本一致性維護(hù)算法 ［J］.軟件學(xué)報(bào)，2007，18（1）：105－116.

［27］STOKES.M.Gnutella2Specifications Part One［EB／OL］. http：／／www. gnutella2. com／gnutella2 ＿search.htm.

［28］RHEA S，KUBIATOWICZ J.Probabilistic location and routing［A］.Proceedings of the INFOCOM 2002 ［C］，2002.1248－1257.

［29］BRODER A，MITZENMACHER M.Network applications of bloom filters：A survey ［J］.Internet Mathe－matics，2005，1（4）：485－509.

［30］GUO D，WU J，CHEN H，et al.Theory and network applications of dynamic bloom filters［A］.Proceedings of the INFOCOM 2006［C］，Washington，2006.1－12.

［31］謝鯤，張大方，文吉?jiǎng)偅?布魯姆過(guò)濾器代數(shù)運(yùn)算探討 ［J］.電子學(xué)報(bào)，2008，36（5）：869－874.

［32］田小梅，張大方，謝鯤，等.計(jì)數(shù)布魯姆過(guò)濾器代數(shù)運(yùn)算 ［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（12）：2598－2617.