一種基于分布式Ｃａｃｈｉｎｇ的自適應(yīng)搜索機(jī)制

摘 要：針對(duì)基于Gnutella協(xié)議的非結(jié)構(gòu)P2P網(wǎng)絡(luò)中利用洪泛搜索機(jī)制進(jìn)行資源搜索的網(wǎng)絡(luò)流量大，效率低等問題，提出一種基于分布式Caching的自適應(yīng)搜索機(jī)制。在使用該搜索機(jī)制的Gnutella網(wǎng)絡(luò)中，所有的節(jié)點(diǎn)在邏輯上分成多層，在同一層的節(jié)點(diǎn)有相同的group ID，洪泛查詢被限制在與group ID匹配的一層。通過實(shí)驗(yàn)與統(tǒng)一索引Caching機(jī)制比較，該搜索機(jī)制在不增加響應(yīng)時(shí)間的條件下，能有效地減少網(wǎng)絡(luò)流量，提高搜索效率。

關(guān)鍵詞：非結(jié)構(gòu)化P2P；分布式Caching；自適應(yīng)搜索;Gnutella

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004-373X(2008)10-139-03

An Adaptive Search Mechamism Based on Distributed Caching

LI Peng，CAI Lecai

(Sichuan University of Science Engineering，Zigong，643000，China)[HJ1*5]

Abstract：Aiming at the problem of more traffic and less search efficient based on Gnutella protocol unstructured Peer-to-Peer network which makes use of the flooding mechanism to search resource，presents a new adptive search mechanism which based on distributed caching.In the Gnutella network which makes use of this mechanism，all the peers are logically divided into multiple layers，all the peers in the same layer have the same group ID.The query flooding is restricted in one layer with the matched group ID.The experiment shows that compared with uniform index caching mechanism，our proposed mechanism can singnificantly reduce the network traffic and improve the search efficient without increasing the response time.

Keywords：unstructured Peer-to-Peer;distributed Caching;adaptive search;Gnutella

與結(jié)構(gòu)化的P2P網(wǎng)絡(luò)相比，非結(jié)構(gòu)化P2P由于采用盲目的洪泛搜索機(jī)制，導(dǎo)致了他的網(wǎng)絡(luò)流量大，搜索效率低等問題。然而非結(jié)構(gòu)化的P2P系統(tǒng)，例如，Gnutella，因?yàn)樗暮?jiǎn)單性和節(jié)點(diǎn)的不確定性，而且其采用的洪泛搜索機(jī)制具有響應(yīng)時(shí)間短、搜索成功率高、可靠性好等一些優(yōu)點(diǎn)，使他在當(dāng)今仍然很流行。在Gnutella網(wǎng)絡(luò)中，查詢消息是通過廣播和再?gòu)V播的方式傳播的，直到找到一個(gè)滿足條件的結(jié)果。如果1個(gè)節(jié)點(diǎn)接收到1個(gè)查詢消息，并能夠提供請(qǐng)求的對(duì)象，他就沿著原路徑發(fā)送個(gè)源節(jié)點(diǎn)1個(gè)響應(yīng)消息。

寬度優(yōu)先的洪泛式搜索導(dǎo)致了網(wǎng)絡(luò)流量以指數(shù)方式增長(zhǎng)。實(shí)驗(yàn)結(jié)果表明：在Gnutella網(wǎng)絡(luò)中95%以上的節(jié)點(diǎn)都可以在7 hops內(nèi)被搜索到。采用洪泛式搜索僅50 000個(gè)節(jié)點(diǎn)每月就產(chǎn)生330 TB的流量。其中，91%的流量是由Query信息包產(chǎn)生的，8%的流量是由Ping信息包產(chǎn)生的。在文獻(xiàn)［1，2］中，對(duì)一些流行的P2P系統(tǒng)（例如：FastTrack，Gnutella，DirectConect）的測(cè)量表明：這些P2P系統(tǒng)的流量占據(jù)了整個(gè)Internet流量的一大部分。這種低效的盲目的洪泛搜索制約了非結(jié)構(gòu)化P2P系統(tǒng)的發(fā)展。

1 相關(guān)的搜索機(jī)制

在非結(jié)構(gòu)化P2P系統(tǒng)中已經(jīng)進(jìn)行了多方面的改進(jìn)避免由洪泛產(chǎn)生的大量的不必要的流量。

一種方法是改變洪泛搜索行為。例如，隨機(jī)漫步^[3]：節(jié)點(diǎn)不是向所有的鄰居節(jié)點(diǎn)發(fā)送查詢消息，而是選擇其中的K個(gè)節(jié)點(diǎn)發(fā)送；但是卻增加了響應(yīng)時(shí)間，而且這種搜索機(jī)制每次查詢都可能會(huì)漏掉一些目標(biāo)節(jié)點(diǎn)。

另一種方法是拓?fù)鋬?yōu)化^[4]，構(gòu)造具有超級(jí)節(jié)點(diǎn)的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)。選擇性能較好的節(jié)點(diǎn)作為超級(jí)節(jié)點(diǎn)。由超級(jí)節(jié)點(diǎn)維護(hù)所有的連接到他上的葉節(jié)點(diǎn)的索引信息。當(dāng)一個(gè)超級(jí)節(jié)點(diǎn)收到從他的葉節(jié)點(diǎn)發(fā)來的搜索信息時(shí)，他首先在本地搜索。如果沒有，他會(huì)把發(fā)來的搜索信息轉(zhuǎn)發(fā)到鄰居超級(jí)節(jié)點(diǎn)上去。所有的搜索在超級(jí)節(jié)點(diǎn)內(nèi)就能夠找到目標(biāo)對(duì)象。總的開銷就是葉節(jié)點(diǎn)和超級(jí)節(jié)點(diǎn)的索引更新。基于簇的拓?fù)浣Y(jié)構(gòu)通過把整個(gè)網(wǎng)絡(luò)劃分成多簇使搜索限制在小世界內(nèi)。SIL^[5]指出了基于并行搜索簇的P2P網(wǎng)絡(luò)在許多方面優(yōu)于超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)，例如，魯棒性和負(fù)載平衡。

第三種方法是使用一些cache或復(fù)制策略，文件的內(nèi)容或查詢響應(yīng)結(jié)果存儲(chǔ)在非查詢的節(jié)點(diǎn)中，使將來的查詢能夠在短查詢距離內(nèi)找到。在文獻(xiàn)［6］中介紹了一種統(tǒng)一索引Caching機(jī)制，他在沿查詢返回路徑的所有節(jié)點(diǎn)上存儲(chǔ)了查詢的結(jié)果。與超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)相比，索引信息的維護(hù)開銷相對(duì)比較小。然而實(shí)驗(yàn)表明統(tǒng)一索引Caching機(jī)制也能夠容易地在鄰居節(jié)點(diǎn)中產(chǎn)生大量重復(fù)的和不必要的緩存結(jié)果。

為了提高搜索效率、減少網(wǎng)絡(luò)流量，本文提出了一種分布式Caching機(jī)制，他在鄰居節(jié)點(diǎn)中分發(fā)緩存結(jié)果。此外，在使用分布式索引Caching的P2P系統(tǒng)中，因?yàn)橐粋€(gè)查詢結(jié)果將僅會(huì)被緩存在被選擇的節(jié)點(diǎn)中，所以就不必對(duì)所有的節(jié)點(diǎn)廣播查詢消息。這里提出了一種自適應(yīng)搜索機(jī)制，即有選擇性地僅轉(zhuǎn)發(fā)查詢信息給那些有高概率提供想要的緩存結(jié)果的節(jié)點(diǎn)。因?yàn)槊恳淮无D(zhuǎn)發(fā)過程中，所有的節(jié)點(diǎn)中僅有一部分被選擇。所以在很大程度上降低了搜索流量。把提出的分布式Caching機(jī)制和自適應(yīng)搜索機(jī)制相結(jié)合，定義為基于分布式Caching的自適應(yīng)搜索機(jī)制。在基于分布式Caching的自適應(yīng)搜索機(jī)制中，當(dāng)每一個(gè)節(jié)點(diǎn)加入P2P系統(tǒng)中時(shí)，就要在一定的范圍內(nèi)［0，1，…，N-1］隨機(jī)的取一個(gè)初始值作為group ID。定義一個(gè)查詢和一個(gè)節(jié)點(diǎn)匹配當(dāng)且僅當(dāng)滿足下面等式：



Peer Group ID=hash(query) Mod N

在基于分布式Caching的自適應(yīng)搜索機(jī)制下，一個(gè)查詢響應(yīng)將會(huì)被緩存在與之相匹配的節(jié)點(diǎn)中。查詢消息也會(huì)被限制發(fā)送到匹配的節(jié)點(diǎn)。在基于分布式Caching的自適應(yīng)搜索機(jī)制的Gnutella P2P網(wǎng)絡(luò)中，按照有相同的group ID的節(jié)點(diǎn)在同一層的特征，把所有節(jié)點(diǎn)組分為多層。洪泛式查詢僅被限制在有相同group ID的一層。圖1給出當(dāng)N=3時(shí)的多層P2P網(wǎng)絡(luò)。而且通過實(shí)驗(yàn)表明，在基于分布式Caching的自適應(yīng)搜索機(jī)制的非結(jié)構(gòu)化P2P系統(tǒng)下，顯著地減少了搜索產(chǎn)生的網(wǎng)絡(luò)流量，并且沒有增長(zhǎng)響應(yīng)時(shí)間。

圖1 在多層P2P網(wǎng)絡(luò)中的洪泛式搜索

2 分布式Caching和自適應(yīng)搜索

2.1Gnutella 協(xié)議

在詳細(xì)介紹提出的基于分布式Caching的自適應(yīng)搜索機(jī)制之前，首先介紹Gnutella協(xié)議。在Gnutella分布式P2P網(wǎng)絡(luò)模型中，每一個(gè)聯(lián)網(wǎng)計(jì)算機(jī)既是Client又是Server，因此被稱為Servent。通過與相鄰對(duì)等節(jié)點(diǎn)之間的連接遍歷整個(gè)網(wǎng)絡(luò)。Gnutella協(xié)議定義網(wǎng)絡(luò)中這些對(duì)等節(jié)點(diǎn)間通信的方式，是工作于TCP協(xié)議之上的應(yīng)用層協(xié)議。該協(xié)議包括在對(duì)等機(jī)間通信描述符集（服務(wù)原語集）和相應(yīng)的通信規(guī)則集。對(duì)等節(jié)點(diǎn)間通信描述符集如表1所示。

Gnutella網(wǎng)絡(luò)協(xié)議描述符的路由規(guī)則主要有以下4條：

（1） Pong描述符僅能沿著轉(zhuǎn)發(fā)Ping描述符的同樣路徑被發(fā)送。1臺(tái)對(duì)等節(jié)點(diǎn)收到1個(gè)Pong描述符，但卻未見相應(yīng)的Ping描述符，則將該P(yáng)ong描述符從網(wǎng)絡(luò)中刪除。同理，QueryHit描述符僅能沿著轉(zhuǎn)發(fā)Query描述符的同樣路徑發(fā)送。這保證了只有收到過Query的對(duì)等節(jié)點(diǎn)才能響應(yīng)QueryHit描述符。Push描述符僅能沿著轉(zhuǎn)發(fā)QueryHit描述符的同樣路徑被發(fā)送。這保證了只有收到QueryHit描述符的對(duì)等節(jié)點(diǎn)才能看到Push描述符。

（2） 一個(gè)對(duì)等節(jié)點(diǎn)除了從接收Ping和Query描述符方向的對(duì)等節(jié)點(diǎn)之外，將會(huì)向所有與之直接相連的對(duì)等節(jié)點(diǎn)轉(zhuǎn)發(fā)接收的Ping和Query描述符。

（3） 在進(jìn)行轉(zhuǎn)發(fā)之前，將會(huì)修改相關(guān)的TTL和HOP字段，將TTL值減1，HOP值加1。當(dāng)TTL值為0時(shí)，將該描述符從網(wǎng)絡(luò)中刪除。

（4） 如果一臺(tái)對(duì)等節(jié)點(diǎn)收到了與他原來曾經(jīng)收到過的Descriptor ID和Payload Descriptor一樣的描述符的話，應(yīng)該避免對(duì)該描述符的轉(zhuǎn)發(fā)。

表1 對(duì)等節(jié)點(diǎn)間通信描述符集

描述符 描 述

Ping用于在Gnutella網(wǎng)絡(luò)中主動(dòng)發(fā)現(xiàn)對(duì)等節(jié)點(diǎn)。一個(gè)收到Ping描述的對(duì)等節(jié)點(diǎn)會(huì)向發(fā)送方響應(yīng)1個(gè)或多個(gè)Pong描述符。

Pong用于對(duì)Ping響應(yīng)的描述符。他包括一個(gè)相連的Gnutella對(duì)等節(jié)點(diǎn)的地址和有關(guān)該節(jié)點(diǎn)能提供給網(wǎng)絡(luò)共享的信息。

Query是搜索Gnutella分布式網(wǎng)絡(luò)共享信息的主要機(jī)制，一個(gè)收到Query描述符的對(duì)等節(jié)點(diǎn)，如果其本地共享信息與Query搜索的內(nèi)容匹配，將會(huì)響應(yīng)1個(gè)QueryHit給Query的發(fā)起者。

Query Hit用于對(duì)Query響應(yīng)的描述符。他包括匹配Query搜索數(shù)據(jù)的對(duì)等節(jié)點(diǎn)IP地址及端口號(hào)、傳輸速度及結(jié)果集、對(duì)等節(jié)點(diǎn)標(biāo)識(shí)等。

Push提供一種機(jī)制允許1臺(tái)處于防火墻后的對(duì)等節(jié)點(diǎn)向網(wǎng)絡(luò)提供基于文件的數(shù)據(jù)。

Gnutella網(wǎng)絡(luò)的工作原理：每個(gè)節(jié)點(diǎn)加入到Gnutella時(shí)，他首先與Gnutella網(wǎng)絡(luò)中的一臺(tái)活動(dòng)的對(duì)等節(jié)點(diǎn)建立連接。初始狀態(tài)下，一臺(tái)活動(dòng)的對(duì)等節(jié)點(diǎn)通過訪問某特殊站點(diǎn)提供的主機(jī)緩存服務(wù)機(jī)制獲得。連接到網(wǎng)絡(luò)后，向其直接相連的鄰居節(jié)點(diǎn)周期性的發(fā)送Ping描述符，每個(gè)活動(dòng)的對(duì)等節(jié)點(diǎn)使用洪泛的方式將該P(yáng)ing描述符轉(zhuǎn)發(fā)到所有的與之相連的對(duì)等節(jié)點(diǎn)，如規(guī)則（2）。接收到Ping的對(duì)等節(jié)點(diǎn)在響應(yīng)Pong的同時(shí)，用同樣的方法繼續(xù)轉(zhuǎn)發(fā)該描述符直到TTL值減到0，如規(guī)則（3）。根據(jù)規(guī)則（1），按Query的發(fā)送路徑返回一個(gè)查詢響應(yīng)描述符QueryHit并向其他對(duì)等節(jié)點(diǎn)轉(zhuǎn)發(fā)直到TTL值減為0。一旦定位了響應(yīng)他查詢共享文件的對(duì)等節(jié)點(diǎn)后，將與響應(yīng)的對(duì)等節(jié)點(diǎn)建立TCP連接，通過HTTP協(xié)議從響應(yīng)的對(duì)等節(jié)點(diǎn)中下載文件，文件傳輸不在經(jīng)過Gnutella網(wǎng)絡(luò)。在目前的Gnutella網(wǎng)絡(luò)中，查詢響應(yīng)在返回的路徑中不被任何一個(gè)對(duì)等節(jié)點(diǎn)存儲(chǔ)。

2.2 分布式Caching

除了持有本地資源的本地索引之外，每個(gè)節(jié)點(diǎn)還維護(hù)從節(jié)點(diǎn)流過的存儲(chǔ)查詢結(jié)果的響應(yīng)索引。存儲(chǔ)在響應(yīng)索引中的每一項(xiàng)包括查詢文件名和響應(yīng)節(jié)點(diǎn)的IP地址。當(dāng)1個(gè)節(jié)點(diǎn)從他的鄰居節(jié)點(diǎn)收到1個(gè)查詢時(shí)，他會(huì)查看響應(yīng)索引和本地索引。1個(gè)查詢與他們其中的1個(gè)匹配就將會(huì)產(chǎn)生1個(gè)響應(yīng)。與在沿返回路徑的所有節(jié)點(diǎn)中存儲(chǔ)查詢響應(yīng)不同，分布式Caching在一些所選擇的節(jié)點(diǎn)上存儲(chǔ)響應(yīng)。分布式Caching的關(guān)鍵是1個(gè)到來的查詢響應(yīng)是否應(yīng)該被緩存，從而使在所有的節(jié)點(diǎn)中重復(fù)的查詢響應(yīng)達(dá)到最小值。在基于分布式caching的自適應(yīng)搜索機(jī)制中，當(dāng)一個(gè)節(jié)點(diǎn)加入P2P系統(tǒng)中時(shí)，就要在一定的范圍內(nèi)［0，1，…，N-1］隨機(jī)的取一個(gè)初始值作為groupID，這樣所有的節(jié)點(diǎn)就被分為N組。通過使用一個(gè)均勻哈希算法把查詢文件名字符串轉(zhuǎn)化成一個(gè)哈希值。定義當(dāng)滿足下面等式時(shí)，1個(gè)查詢和1個(gè)節(jié)點(diǎn)相匹配。



Peer Group ID=hash(query) Mod N

對(duì)1個(gè)返回的查詢響應(yīng)，每個(gè)節(jié)點(diǎn)使用哈希函數(shù)獨(dú)立的對(duì)其進(jìn)行計(jì)算，僅當(dāng)哈希值和節(jié)點(diǎn)的group ID匹配時(shí)存儲(chǔ)他。例如，當(dāng)N=2，所有的節(jié)點(diǎn)分成2個(gè)不同的group。假設(shè)對(duì)文件名的哈希值經(jīng)過求余運(yùn)算的結(jié)果等于1。僅當(dāng)group1的節(jié)點(diǎn)存儲(chǔ)這個(gè)響應(yīng)。如圖2所示。

圖2 分布式Caching

2.3 自適應(yīng)搜索

一個(gè)查詢也僅發(fā)送到與查詢的文件名的哈希值匹配的group ID的鄰居節(jié)點(diǎn)。例如，當(dāng)1個(gè)節(jié)點(diǎn)接收到1個(gè)查詢，與他匹配的group ID是1，這個(gè)查詢僅會(huì)被發(fā)送到group ID是1的鄰居節(jié)點(diǎn)。在P2P系統(tǒng)中，由于group ID的值是隨機(jī)選擇的，稱group ID服從均勻分布。正是因?yàn)間roup ID服從均勻分布，所以一次查詢?cè)诖蠖鄶?shù)情況下都能被發(fā)送到與之匹配的鄰居節(jié)點(diǎn)。盡管如此，如果沒有一個(gè)鄰居節(jié)點(diǎn)的group ID與查詢請(qǐng)求相匹配，他仍有可能導(dǎo)致網(wǎng)絡(luò)阻塞。為了避免查詢的早死，在這種情況下，節(jié)點(diǎn)將會(huì)選擇一個(gè)有高連接度的鄰居來發(fā)送這個(gè)查詢。以上就是自適應(yīng)搜索機(jī)制，查詢轉(zhuǎn)發(fā)被限制在與group ID匹配的節(jié)點(diǎn)上。那些節(jié)點(diǎn)形成一個(gè)虛擬層，與原始的P2P網(wǎng)絡(luò)相比，他的搜索空間更小。經(jīng)過求余運(yùn)算，整個(gè)網(wǎng)絡(luò)在邏輯上分成多層，并且每個(gè)查詢將會(huì)在與之相匹配的group ID的通信層內(nèi)轉(zhuǎn)發(fā)。

3 實(shí)驗(yàn)結(jié)果與分析

為了進(jìn)一步提高搜索效率，提出基于分布式Caching的自適應(yīng)搜索機(jī)制在被選擇的節(jié)點(diǎn)上來存儲(chǔ)響應(yīng)，并且轉(zhuǎn)發(fā)查詢到與他相匹配的group ID的節(jié)點(diǎn)上。本部分對(duì)基于分布式Caching的自適應(yīng)搜索機(jī)制進(jìn)行評(píng)估，令N=2，把搜索空間在邏輯上分成2層。圖3和圖4分別比較了統(tǒng)一索引Caching搜索機(jī)制和基于分布式Caching的自適應(yīng)搜索機(jī)制的平均流量和平均查詢響應(yīng)時(shí)間。能夠看到分布式Caching的自適應(yīng)搜索機(jī)制的平均流量比統(tǒng)一索引Caching搜索機(jī)制減少了65%。而平均查詢響應(yīng)時(shí)間僅增加5%。

圖3 平均流量比較

圖4 平均響應(yīng)時(shí)間比較

當(dāng)測(cè)量查詢成功率時(shí)發(fā)現(xiàn)，基于分布式Caching的自適應(yīng)搜索機(jī)制的查詢成功率與統(tǒng)一索引Caching相比有所降低。如何提高基于分布式Caching的自適應(yīng)搜索機(jī)制的查詢成功率將是下一步的研究工作。

4 結(jié) 語

通過實(shí)驗(yàn)表明在基于分布式Caching技術(shù)的自適應(yīng)搜索機(jī)制的Gnutella P2P網(wǎng)絡(luò)中能夠顯著地減少搜索流量，但他的平均響應(yīng)時(shí)間幾乎沒有增加。基于分布式Caching技術(shù)的自適應(yīng)搜索機(jī)制的Gnutella P2P網(wǎng)絡(luò)在一定程度上減少了大量的冗余搜索信息，減少了帶寬的消耗，提高了Gnutella P2P網(wǎng)絡(luò)的可擴(kuò)展性。然而也引出了查詢成功率有所降低的問題。如何在不增加網(wǎng)絡(luò)流量和響應(yīng)時(shí)間的條件下提高查詢成功率是下一步需要研究的工作。

參 考 文 獻(xiàn)

［1］Sen S，Wang J.Anaalyzing Peer-to-Peer Traffic across Large Networks.in Proceedings of ACM SIGCOMM Internet Measurement Workshop，2002.

［2］Saroiu S，Gummadi K P，Dumn R J，et al.An Analysis of Internet Content Delivery Systems.in Proceedings of the 5th Symposium on Operating Systems Design and Implementation，2002.

［3］Lv Q，Cao P，Cohen E，et al.Search and Replication in Unstructured Peer-to-Peer Networks.in Proceedings of the 16th ACM International Conference on Supercomputing，2002.

［4］Liu Y，Liu X，Xiao L，et al.Location Aware Topology Matc[CD*4]hing in Unstructured P2P Systems.in Proceedings of INFO[CD*4]COM 2004，2004.

［5］Cooper B F，Garcia-Molina.Studying Search Networks with SIL.In Proceedings of IPTPS，2003.

［6］The Popularity of Gnutella Queries and Its Implications on Scalability[EB/OL].http://www2.cs.cmu.edu/~kunwadee/-research/p2p/gnutella.html.

［7］Patro S，Hu Y C.Transparent Query Caching in Peer-to-Peer Overlay Networks.in Proceedings of the 17th International Parallerl and Distributed Processing Symposium(IPDPS)，2003.

［8］楊斌，孟波.P2P經(jīng)典路由算法的改進(jìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2004，25(2):262-264.

［9］董健全，武雪麗，李智昕.P2P網(wǎng)絡(luò)中應(yīng)用移動(dòng)Agent進(jìn)行資源搜索的研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2005，26(1):27-30.

［10］羅杰文.Peer-to-Peer計(jì)算機(jī)綜述［R］.北京:中科院計(jì)算技術(shù)研究所，2005.

作者簡(jiǎn)介 李 鵬 1982年出生，在讀研究生。

蔡樂才 1968年出生，教授，碩士生導(dǎo)師。研究方向?yàn)榫W(wǎng)絡(luò)安全。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。