布魯姆過濾器算法在P2P系統(tǒng)中的應(yīng)用

田小梅， 胡 燦

(1.湖南環(huán)境生物職業(yè)技術(shù)學(xué)院 藝術(shù)設(shè)計(jì)學(xué)院，湖南衡陽421005;2.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙410082)

自70年代由Burton Bloom創(chuàng)新性地提出以來，布魯姆過濾器算法(Bloom filter，BF)[1]已被廣泛用于各類網(wǎng)絡(luò)及分布式系統(tǒng)，各種布魯姆過濾器算法的變種和相關(guān)應(yīng)用領(lǐng)域不斷涌現(xiàn)[2].

1 布魯姆過濾器算法

布魯姆過濾器是一種空間高效的有損數(shù)據(jù)結(jié)構(gòu)，支持快速的數(shù)據(jù)成員查詢，能高效地過濾非集合成員.

通常我們使用布魯姆過濾器的場景如下:將集合S表示到布魯姆過濾器BF(S)中，在需要查詢?cè)厥欠駥儆诩蟂時(shí)，使用BF(S)而不是S本身進(jìn)行集合成員查詢，節(jié)約存儲(chǔ)空間及提高查詢的時(shí)間效率.

2 P2P網(wǎng)絡(luò)

對(duì)等網(wǎng)絡(luò)(Peer to peer，P2P)是一類分布式網(wǎng)絡(luò)，網(wǎng)絡(luò)的參與者(稱對(duì)等節(jié)點(diǎn)或Peer)共享他們所擁有的一部分硬件資源(處理能力、存儲(chǔ)能力、網(wǎng)絡(luò)連接能力、打印機(jī)等)，這些共享資源能被其它對(duì)等節(jié)點(diǎn)直接訪問而無需經(jīng)過中間實(shí)體.在此網(wǎng)絡(luò)中的對(duì)等節(jié)點(diǎn)既是資源提供者(Server)，又是資源獲取者(Client)[3].

P2P網(wǎng)絡(luò)最大的優(yōu)勢(shì)是資源共享，從理論上講，P2P網(wǎng)絡(luò)的能力和資源是網(wǎng)絡(luò)中各節(jié)點(diǎn)能力和資源的總和.為充分利用互聯(lián)網(wǎng)節(jié)點(diǎn)的閑置計(jì)算能力或存儲(chǔ)空間，通過P2P技術(shù)將計(jì)算任務(wù)或存儲(chǔ)資料分散到網(wǎng)絡(luò)的其它結(jié)點(diǎn)，各結(jié)點(diǎn)協(xié)同工作，得到各類文件共享系統(tǒng)、高性能計(jì)算系統(tǒng)、海量存儲(chǔ)系統(tǒng)等P2P分布式系統(tǒng).

3 互聯(lián)網(wǎng)中的P2P應(yīng)用實(shí)例

21世紀(jì)以來，互聯(lián)網(wǎng)在現(xiàn)代社會(huì)中的作用越來越舉足輕重，已經(jīng)成為人類社會(huì)重要的信息基礎(chǔ)設(shè)施，并強(qiáng)力滲透到政治、經(jīng)濟(jì)、社會(huì)、軍事、科技文化、教育等各個(gè)領(lǐng)域，對(duì)人類的生活、工作及學(xué)習(xí)產(chǎn)生了日益深遠(yuǎn)的影響.事實(shí)上，互聯(lián)網(wǎng)提供的即時(shí)通信、搜索、音樂、新聞、網(wǎng)絡(luò)視頻、娛樂等服務(wù)，都存在P2P技術(shù)的應(yīng)用實(shí)例.下面是P2P技術(shù)在互聯(lián)網(wǎng)中的一些應(yīng)用實(shí)例.

即時(shí)通訊(Instant messenger，IM)軟件，如 ICQ、QQ、UC、Yahoo Messenger、AOL Instant Messenger、KDT快遞通、Openext、POCO、ezPeer等早已成為網(wǎng)民上網(wǎng)的必備工具，正在逐漸改變?nèi)藗兊臏贤ㄅc交際方式.大多數(shù)的這類即時(shí)通訊軟件都是基于P2P技術(shù)的，如 ICQ、QQ、MSN Messenger等.

美國Digital公司正在研制的Pandango搜索引擎就是一種基于P2P技術(shù)的搜索引擎，公司的首席執(zhí)行官利亞德-梅達(dá)(Liad Meidar)表示，Pandango搜索引擎目前已經(jīng)幾近完成，公司正在與許多大名鼎鼎的門戶網(wǎng)站、ISP以及網(wǎng)絡(luò)公司協(xié)商合作事宜.就連著名的Google公司也宣稱正在采用P2P技術(shù)來改進(jìn)其現(xiàn)有的第二代搜索引擎，研發(fā)第三代搜索引擎.

Napster、Kuro、KuGou、Muper、百寶等 P2P 音樂共享軟件，成為用戶獲取音樂文件的主要手段.例如，KuGou軟件，積累了數(shù)萬首數(shù)字音樂版權(quán)，擁有超過數(shù)億的共享音樂文件，擁有上千萬用戶，深受廣大用戶的喜愛.

隨著互聯(lián)網(wǎng)的興起，作為“新電子媒體”的網(wǎng)絡(luò)逐漸成為一種新的新聞媒體類型.尤其是，很多基于P2P技術(shù)的視頻直播系統(tǒng)(如 PPTV、PPStream等)的誕生對(duì)網(wǎng)絡(luò)新聞的發(fā)展起到了極大的推進(jìn)作用.

目前視頻類網(wǎng)站運(yùn)營成本中最大的部分是帶寬成本，而P2P技術(shù)能有效降低服務(wù)器的負(fù)載，減少70%以上的帶寬租用.P2P技術(shù)能在保證用戶體驗(yàn)感的情況下，有效降低帶寬租用成本，提高視頻運(yùn)營商的業(yè)務(wù)競爭力，有望成為互聯(lián)網(wǎng)視頻領(lǐng)域的主流技術(shù).

許多網(wǎng)絡(luò)在線游戲均是基于P2P技術(shù)的，如泡泡堂、街頭籃球、跑跑卡丁車等.這對(duì)廣大青少年用戶來說是極富吸引力的娛樂方式.華中科技大學(xué)開發(fā)的Pktown大規(guī)模游戲?qū)?zhàn)服務(wù)平臺(tái)[4]也基于P2P技術(shù).

Farsite、Ocean Store等P2P海量數(shù)據(jù)存儲(chǔ)軟件，用于將網(wǎng)絡(luò)上原本由專用服務(wù)器存儲(chǔ)的數(shù)據(jù)對(duì)象分散到多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中存放，增加數(shù)據(jù)的可靠性和傳輸速度.

CNNIC的報(bào)告[5]指出:由于全球IPv4地址已于2011年2月分配完畢，我國IPv6地址數(shù)量在近一年內(nèi)飛速增長，截至2012年6月底，我國擁有IPv6地址數(shù)量為12499塊/32，全球排名第3位，僅次于巴西(65728塊/32)和美國(18694塊/32).由于IPv6使用128位IP地址，能使更多的節(jié)點(diǎn)加入P2P網(wǎng)絡(luò)，而且，IPv6技術(shù)中加入了身份驗(yàn)證、數(shù)據(jù)一致性和保密性機(jī)制，能提高P2P網(wǎng)絡(luò)的安全性.因此，IPv6地址的大規(guī)模部署能促進(jìn)P2P技術(shù)的發(fā)展.

CNNIC發(fā)布的《第30次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》[5]還指出，由于當(dāng)前智能手機(jī)的功能越來越強(qiáng)大，價(jià)格卻越來越低，加上移動(dòng)上網(wǎng)應(yīng)用軟件的大量涌現(xiàn)，2012年上半年，通過手機(jī)接入互聯(lián)網(wǎng)的網(wǎng)民數(shù)量達(dá)到3.88億，比臺(tái)式電腦用戶多出800萬，手機(jī)上網(wǎng)用戶首次超越臺(tái)式電腦上網(wǎng)用戶，手機(jī)成為我國網(wǎng)民的第一大上網(wǎng)終端.可以斷言，智能手機(jī)的普及勢(shì)必會(huì)推動(dòng)移動(dòng)P2P計(jì)算的進(jìn)一步發(fā)展.

從以上的種種實(shí)例可以看到，P2P無疑是目前互聯(lián)網(wǎng)上最為廣泛的技術(shù)應(yīng)用.而且，這種優(yōu)勢(shì)隨著IPv6地址的廣泛部署和智能手機(jī)的廣泛普及必將持續(xù)下去.

4 布魯姆過濾器算法在P2P系統(tǒng)中的應(yīng)用研究

布魯姆過濾器在P2P網(wǎng)絡(luò)中的主要作用是匯總各類資源如文件、關(guān)鍵字或其它對(duì)象，使用布魯姆過濾器匯總后，空間占用比直接存儲(chǔ)原始集合要少幾個(gè)數(shù)量級(jí).布魯姆過濾器可用于P2P系統(tǒng)中關(guān)鍵字檢索、資源路由、遠(yuǎn)程數(shù)據(jù)調(diào)和、社會(huì)網(wǎng)絡(luò)及P2P副本一致性維護(hù)等應(yīng)用場合.

4.1 關(guān)鍵字檢索

在Cuena-Acuna等人提出的PlanetP系統(tǒng)[6]中，使用布魯姆過濾器存儲(chǔ)對(duì)象的關(guān)鍵字，而不是存儲(chǔ)對(duì)象標(biāo)識(shí)符.比如說，存儲(chǔ)對(duì)象標(biāo)識(shí)符需64位，而使用布魯姆過濾器后每個(gè)對(duì)象卻只要8位或16位就可.在中等規(guī)模的P2P網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)均存儲(chǔ)其它節(jié)點(diǎn)的布魯姆過濾器表示的關(guān)鍵字列表是不難做到的.

現(xiàn)今流行的Gnutella2協(xié)議[7]使用布魯姆過濾器高效地表示文件的關(guān)鍵字列表.在Gnutella2文件共享系統(tǒng)中，使用兩層體系結(jié)構(gòu)，由超節(jié)點(diǎn)層和葉節(jié)點(diǎn)層組成.葉節(jié)點(diǎn)發(fā)送本地文件的關(guān)鍵字列表(布魯姆過濾器)給某超節(jié)點(diǎn)，超節(jié)點(diǎn)收集所屬葉節(jié)點(diǎn)的布魯姆過濾器，將其歸并到一個(gè)總布魯姆過濾器再發(fā)送給相鄰的超節(jié)點(diǎn).當(dāng)葉節(jié)點(diǎn)需要查詢文件，首先從它連接的超節(jié)點(diǎn)的索引中尋找，如果找到了文件，則直接根據(jù)文件所存儲(chǔ)的機(jī)器的地址建立連接，如果沒有找到，則超節(jié)點(diǎn)把這個(gè)查詢請(qǐng)求發(fā)給它連接的其他超節(jié)點(diǎn)，直到得到想要的資源.

隨著在網(wǎng)絡(luò)上用于數(shù)據(jù)交換的可擴(kuò)展標(biāo)記語言(XML)的普及，大量的數(shù)據(jù)源用XML格式表示或編碼.因此，查詢和檢索網(wǎng)絡(luò)上的XML數(shù)據(jù)受到了數(shù)據(jù)庫文獻(xiàn)的極大重視.同時(shí)，P2P計(jì)算模式推動(dòng)了互聯(lián)網(wǎng)上更靈活的自主數(shù)據(jù)共享.P2P系統(tǒng)中的XML數(shù)據(jù)檢索已吸引了研究團(tuán)體和工業(yè)界的廣大專業(yè)人士的研究.文獻(xiàn)[8]針對(duì)結(jié)構(gòu)化P2P系統(tǒng)提出了一種以布魯姆過濾器為基礎(chǔ)的用于XML數(shù)據(jù)檢索的關(guān)鍵字搜索框架，在該框架中，XML索引使用布魯姆過濾器編碼.與傳統(tǒng)的全索引方案相比，基于布魯姆過濾器的關(guān)鍵字搜索方法查詢響應(yīng)時(shí)間短，系統(tǒng)具數(shù)據(jù)規(guī)?？蓴U(kuò)展性和網(wǎng)絡(luò)規(guī)模可擴(kuò)展性.

4.2 資源路由

Rhea和Kubiatowicz等人設(shè)計(jì)了一種概率路由算法[9]用于 OceanStore[10]項(xiàng)目的資源定位，這種路由機(jī)制稱為資源路由.在請(qǐng)求某文件時(shí)，首先使用概率路由算法查找，當(dāng)請(qǐng)求文件已被復(fù)制到請(qǐng)求系統(tǒng)附近時(shí)能較快地完成資源定位.在OceanStore系統(tǒng)中，如果使用概率路由算法查找失敗，則再使用Tapestry協(xié)議實(shí)施確定的搜索算法.OceanStore系統(tǒng)中使用的衰減布魯姆過濾器(Attenuated Bloom filter)是一個(gè)由d個(gè)基本布魯姆過濾器組成的數(shù)組，其中，第i個(gè)基本布魯姆過濾器保存的是i跳可達(dá)的文件記錄.在該系統(tǒng)中，節(jié)點(diǎn)為每個(gè)鄰居節(jié)點(diǎn)均維護(hù)一個(gè)衰減布魯姆過濾器，衰減布魯姆過濾器的更新通過廣播機(jī)制實(shí)現(xiàn).當(dāng)然，這種資源路由機(jī)制也能用于與其他P2P網(wǎng)絡(luò)[11-13]中的確定性路由機(jī)制配合使用.

Cai和 Wang在 Foreseer系統(tǒng)[14]中提出使用地理局部性和時(shí)間局部性分別構(gòu)建鄰居覆蓋網(wǎng)和朋友覆蓋網(wǎng)來提高系統(tǒng)的搜索效率.系統(tǒng)中的每一個(gè)對(duì)等節(jié)點(diǎn)均維護(hù)有少量鄰居和朋友的內(nèi)容過濾器作為分布式索引.

4.3 遠(yuǎn)程數(shù)據(jù)同步

布魯姆過濾器可用于P2P網(wǎng)絡(luò)中的集合調(diào)和或數(shù)據(jù)同步[15-19].通常，在這類應(yīng)用中，布魯姆過濾器被用于精簡表示自身節(jié)點(diǎn)已經(jīng)擁有的條目，對(duì)等節(jié)點(diǎn)發(fā)送一個(gè)這樣的布魯姆過濾器給另一對(duì)等節(jié)點(diǎn)，接收節(jié)點(diǎn)根據(jù)接收到的布魯姆過濾器找出發(fā)送節(jié)點(diǎn)所缺少的條目，并將這部分條目發(fā)送回發(fā)起方.這樣，調(diào)和或同步過程中只需發(fā)送對(duì)方節(jié)點(diǎn)缺失的條目，而不需發(fā)送所有條目，從而節(jié)約帶寬、提高效率.但由于布魯姆過濾器假陽性的存在，接收節(jié)點(diǎn)在查找時(shí)，會(huì)遺漏部分條目，通?？膳浜鲜褂眉m刪碼以完成調(diào)和[17].

4.4 社會(huì)P2P網(wǎng)絡(luò)

布魯姆過濾器也被用于社會(huì)P2P網(wǎng)絡(luò)，例如社會(huì) P2P 文件共享系統(tǒng) Tribler[20].Tribler使用布魯姆過濾器來維護(hù)在對(duì)等節(jié)點(diǎn)間同步的社會(huì)信任網(wǎng)絡(luò).布魯姆過濾器被用于篩選出已由消息目標(biāo)節(jié)點(diǎn)通過群發(fā)現(xiàn)消息所知曉的對(duì)等節(jié)點(diǎn).在Tribler中，使用一個(gè)大小為260字節(jié)的布魯姆過濾器，信息就能到達(dá)兩對(duì)等節(jié)點(diǎn)共同的朋友的朋友，從而對(duì)等節(jié)點(diǎn)能在短時(shí)間內(nèi)與成千上萬個(gè)對(duì)等節(jié)點(diǎn)交換信息.

4.5 P2P副本一致性維護(hù)

在副本更新報(bào)文的頭部增加一個(gè)用布魯姆過濾器表示的地址鏈表，每個(gè)節(jié)點(diǎn)均有一個(gè)相應(yīng)長度的掩碼，該掩碼與副本更新報(bào)文頭部中的布魯姆過濾器進(jìn)行“或”運(yùn)算，如果布魯姆過濾器發(fā)生了改變，則使用副本更新報(bào)文更新該節(jié)點(diǎn)的副本，否則，表示該節(jié)點(diǎn)的副本已進(jìn)行過更新[21].

5 結(jié)束語

由于具有節(jié)約存儲(chǔ)空間、快速查詢集合成員的優(yōu)點(diǎn)，布魯姆過濾器在需要共享數(shù)據(jù)信息的大型分布式應(yīng)用系統(tǒng)中有巨大的應(yīng)用潛力.尤其是伴隨著P2P技術(shù)在互聯(lián)網(wǎng)中的廣泛部署及應(yīng)用，布魯姆過濾器算法在P2P系統(tǒng)中的應(yīng)用正呈現(xiàn)如火如荼的發(fā)展態(tài)勢(shì).

[1] BLOOM B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM，1970，13(7):422-426.

[2] 謝 鯤，文吉?jiǎng)?，張大方?布魯姆過濾器查詢算法[J].軟件學(xué)報(bào)，2009，20(1):96-108.

[3] 斯太門茲等.P2P系統(tǒng)及其應(yīng)用[M].機(jī)械工業(yè)出版社.2008.

[4] JIN H，YAO H，LIAO X，et al.PKTown:A peer-to-peer middleware to support multiplayer online games[A].Proceedings of the International Conference on Multimedia and Ubiquitous Engineering[C]，2007.54-59.

[5] 中國互聯(lián)網(wǎng)絡(luò)信息中心，第30次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào) 告[R].http://www.cnnic.org.cn/hlwfzyj/hlwxzbg/hlwtjbg/201207/t20120723_32497.htm，2012.7.19.

[6] CUENCA-ACUNA F M，PEERY C，MARTIN R P，et al.Planetp:Using gossiping to build content addressable peerto-peer information sharing communities[A].Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing[C]，2003.236-246.

[7] STOKES.M.Gnutella2 Specifications Part One[J].http://www.gnutella2.com/gnutella2_search.htm.

[8] HE W，LV T.Bloom filter-based keyword search over XML data in structured Peer-to-Peer systems[A].Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology[C]，2010.177-181.

[9] RHEA S，KUBIATOWICZ J.Probabilistic location and routing[A].Proceedings of the INFOCOM 2002[C]，2002.1248-1257.

[10] KUBIATOWICZ J，BINDEL D，CHEN Y，et al.Oceanstore:An architecture for global-scale persistent storage[J].ACM Sigplan Notices，2000，35(11):190-201.

[11] ROWSTRON A，DRUSCHEL P.Storage management and caching in PAST，a large-scale，persistent peer-to-peer storage utility[A].Proceedings of the Eighteenth ACM Symposium on Operations Systems Principles[C]，2001.188-201.

[12] RATNASAMY S，F(xiàn)RANCIS P，HANDLEY M，et al.A scalable content-addressable network[J].ACM SIGCOMM Computer Communication Review，2001，31(4):161-172.

[13] STOICA I，MORRIS R，KARGER D，et al.Chord:A scalable peer-to-peer lookup service for internet applications[J].ACM SIGCOMM Computer Communication Review，2001，31(4):149-160.

[14] CAI H，WANG J.Exploiting geographical and temporal locality to boost search efficiency in peer-to-peer systems[J].IEEE Transactions on Parallel and Distributed Systems，2006，17(10):1189-1203.

[15] STAROBINSKI D，TRACHTENBERG A，AGARWAL S.Efficient PDA synchronization[J].IEEE Transactions on Mobile Computing，2003，2(1):40-51.

[16] MINSKY Y，TRACHTENBERG A，Efficient reconciliation of unordered databases[R].TR1999-1778.Cornell University，1999.

[17] 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.

[18] 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.

[19] SKJEGSTAD M，MASENG T.Low complexity set reconciliation using Bloom filters[A].Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing[C]，San Jose，California，2011.33-41.

[20] POUWELSE J A，GARBACKI P，WANG J，et al.TRIBLER:a social‐based peer‐to‐peer system[J].Concurrency and Computation:Practice and Experience，2008，20(2):127-138.

[21] 謝 鯤，張大方，謝高崗等.基于軌跡標(biāo)簽的無結(jié)構(gòu)P2P副本一致性維護(hù)算法[J].軟件學(xué)報(bào)，2007，18(1):105-116.