基于ＤＨＴ的Ｐ２Ｐ搜索定位技術(shù)研究

摘 要：在P2P系統(tǒng)中，如何高效準(zhǔn)確地對(duì)資源進(jìn)行定位是衡量其性能的一個(gè)關(guān)鍵。通過(guò)對(duì)目前基于DHT的幾個(gè)典型P2P系統(tǒng)搜索定位算法的介紹，分析了基于DHT搜索定位技術(shù)的優(yōu)點(diǎn)和存在的問(wèn)題，并對(duì)P2P發(fā)展進(jìn)行了展望。

關(guān)鍵詞：對(duì)等網(wǎng)；DHT；關(guān)鍵值；P2P

中圖法分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1001-3695(2006)10-0226-03

Study of Data Search in DHT P2P Networks

LI Yundi，F(xiàn)ENG Yong

（Laboratory of AutomaticIllation， Chengdu Institute of Compute Application，Chinese Academy of Sciences， Chengdu Sichuan 610041， China）

Abstract:A key problem of the P2P systems is how to effectively locate the resources .This paper introduces the search of a few of typical P2P systems based on the DHT and gives the excellence and some existing problems. At last， the development of the P2P is given.

Key words:P2P Networks;DHT(Distributed Hash Table);Key;P2P(PeertoPeer)

P2P（PeertoPeer）即對(duì)等網(wǎng)技術(shù)，近年來(lái)隨著許多P2P系統(tǒng)的成功應(yīng)用，引起了人們對(duì)P2P技術(shù)的研究熱潮。 對(duì)等網(wǎng)打破了傳統(tǒng)的Client/Server模式，在對(duì)等網(wǎng)中，各節(jié)點(diǎn)是對(duì)等的具有相同的責(zé)任和能力并協(xié)同完成任務(wù)。傳統(tǒng)的C/S模式有中心服務(wù)器，服務(wù)器接收客戶端查詢請(qǐng)求并提供資源下載。在P2P網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)均是對(duì)等的，節(jié)點(diǎn)具有自組織、自適應(yīng)性，因此如何有效地對(duì)資源進(jìn)行搜索定位成為P2P系統(tǒng)研究的核心問(wèn)題，它幾乎決定了整個(gè)P2P網(wǎng)絡(luò)的性能。

1 P2P系統(tǒng)模型介紹

一般依據(jù)網(wǎng)絡(luò)的請(qǐng)求機(jī)制將P2P系統(tǒng)分為非純P2P系統(tǒng)和純P2P系統(tǒng)。其中在純P2P系統(tǒng)中依據(jù)其邏輯拓?fù)涫欠窬哂薪Y(jié)構(gòu)性又分為結(jié)構(gòu)化P2P系統(tǒng)和非結(jié)構(gòu)化P2P系統(tǒng)。

在非純P2P系統(tǒng)中有中心服務(wù)器，該服務(wù)器保存了對(duì)象的信息，其典型代表系統(tǒng)是Napster［2］。在Napster中，中心服務(wù)器保存有一即時(shí)更新的對(duì)象目錄列表。節(jié)點(diǎn)加入系統(tǒng)時(shí)首先注冊(cè)到服務(wù)器并將自己能提供的文件提交給服務(wù)器，當(dāng)節(jié)點(diǎn)的查詢請(qǐng)求被發(fā)往服務(wù)器時(shí)，服務(wù)器對(duì)對(duì)象目錄列表進(jìn)行檢索并返回符合要求的節(jié)點(diǎn)，然后再點(diǎn)對(duì)點(diǎn)進(jìn)行文件傳送。其原理如圖1所示。很明顯，中心控制存在單點(diǎn)失效與不可擴(kuò)展問(wèn)題，同時(shí)中心服務(wù)器還很可能形成瓶頸問(wèn)題。

非結(jié)構(gòu)化P2P系統(tǒng)以Gnutella［1］為代表，其邏輯拓?fù)涫请S機(jī)的。在非結(jié)構(gòu)化的P2P系統(tǒng)中由于沒(méi)有節(jié)點(diǎn)存放文件信息，搜索幾乎是隨機(jī)的，從一個(gè)節(jié)點(diǎn)開(kāi)始逐個(gè)詢問(wèn)是否有匹配查詢請(qǐng)求的信息。在Gnutella中查詢機(jī)制是以洪泛式進(jìn)行的，請(qǐng)求被發(fā)送到本地節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)，直到超時(shí)或找到目標(biāo)信息（圖2）為止。這種洪泛式的查詢機(jī)制使得系統(tǒng)極不可擴(kuò)展，因?yàn)殡S著節(jié)點(diǎn)的增多它帶給網(wǎng)絡(luò)的負(fù)荷劇增。這也是非結(jié)構(gòu)化的純P2P系統(tǒng)均存在的問(wèn)題。

結(jié)構(gòu)化的P2P系統(tǒng)一般都是基于DHT（Distributed Hash Table）技術(shù)的，運(yùn)用DHT技術(shù)建立具有一定結(jié)構(gòu)的邏輯拓?fù)洌构?jié)點(diǎn)與文件之間建立一定的關(guān)系，每個(gè)節(jié)點(diǎn)按一定規(guī)則保存系統(tǒng)中部分其他節(jié)點(diǎn)的信息，為文件的搜索提供一定的信息（圖3）。其代表系統(tǒng)有Chord，CAN，Tapestry，Pastry等，基于DHT的系統(tǒng)基本解決了早期系統(tǒng)所面臨的問(wèn)題，但其也有自己的問(wèn)題。本文首先介紹幾個(gè)典型的基于DHT技術(shù)的系統(tǒng)，然后對(duì)其算法進(jìn)行比較分析，給出DHT算法的優(yōu)點(diǎn)與不足，并提出以后可能的改進(jìn)。

2 基于DHT的P2P系統(tǒng)搜索定位機(jī)制分析

DHT的基本思想是在文件與節(jié)點(diǎn)之間建立一定的關(guān)系，即文件信息按照一定的規(guī)則存儲(chǔ)在節(jié)點(diǎn)上。在結(jié)構(gòu)化的P2P系統(tǒng)中，一個(gè)文件與一個(gè)Key值相對(duì)應(yīng)（一般通過(guò)對(duì)文件進(jìn)行哈希得到），系統(tǒng)中的每個(gè)節(jié)點(diǎn)負(fù)責(zé)保存一定范圍的Keys。不管內(nèi)部的搜索算法如何，應(yīng)用接口均由put(key，value)和get(key)這兩個(gè)函數(shù)組成，其中put(key，value)的功能是進(jìn)行節(jié)點(diǎn)的信息發(fā)布，get(key)的功能是進(jìn)行信息查詢。下面分別對(duì)幾個(gè)典型的系統(tǒng)模型進(jìn)行介紹。

2．1 Chord

Chord［4］運(yùn)用一致性雜湊函數(shù)（Consistent Hashing）將關(guān)鍵值分配給節(jié)點(diǎn)。一致性雜湊函數(shù)為每個(gè)節(jié)點(diǎn)和關(guān)鍵值賦予一個(gè)m位的標(biāo)識(shí)符，如使用SHA1上介紹的基本雜湊函數(shù)。節(jié)點(diǎn)的標(biāo)識(shí)符是通過(guò)對(duì)節(jié)點(diǎn)的IP地址進(jìn)行雜湊計(jì)算得到的；關(guān)鍵值的標(biāo)識(shí)符是通過(guò)對(duì)節(jié)點(diǎn)中存儲(chǔ)的關(guān)鍵值（如代表某個(gè)可被查找文件的關(guān)鍵值，即最終所需要的數(shù)據(jù)）進(jìn)行雜湊計(jì)算得到的。這種標(biāo)識(shí)符的長(zhǎng)度應(yīng)該取得足夠長(zhǎng)使兩個(gè)節(jié)點(diǎn)或兩個(gè)關(guān)鍵值雜湊計(jì)算后得到相等標(biāo)識(shí)符的可能性很小。

當(dāng)關(guān)鍵值和節(jié)點(diǎn)經(jīng)過(guò)雜湊函數(shù)計(jì)算后，關(guān)鍵值通過(guò)如下方法存儲(chǔ)在相應(yīng)的節(jié)點(diǎn)中。關(guān)鍵值k被存儲(chǔ)在一個(gè)節(jié)點(diǎn)值等于k的節(jié)點(diǎn)上，如果不存在這樣的節(jié)點(diǎn)則存儲(chǔ)在節(jié)點(diǎn)值大于k的第一個(gè)節(jié)點(diǎn)上。存儲(chǔ)關(guān)鍵值k的節(jié)點(diǎn)稱為關(guān)鍵值k的后繼節(jié)點(diǎn)。節(jié)點(diǎn)按照節(jié)點(diǎn)值從1~2m的形式排成一個(gè)環(huán)，那么k的后繼節(jié)點(diǎn)就是k在順時(shí)針?lè)较蛏系牡谝粋€(gè)節(jié)點(diǎn)，該環(huán)稱為Chord環(huán)。圖4是一個(gè)m=3的Chord環(huán)，環(huán)中有三個(gè)節(jié)點(diǎn)，0，1，3。關(guān)鍵值1的后繼節(jié)點(diǎn)就是1，2的后繼節(jié)點(diǎn)就是3，6的后繼節(jié)點(diǎn)就是0。

每個(gè)節(jié)點(diǎn)保存著一個(gè)路由表，路由表至少有m個(gè)入口，節(jié)點(diǎn)n的ith入口在節(jié)點(diǎn)ID空間中距n至少是2i-1。關(guān)鍵值k的查找就是通過(guò)路由表信息在Chord環(huán)中查找k的后繼的過(guò)程。由于節(jié)點(diǎn)n的ith入口在節(jié)點(diǎn)ID空間中距n至少是2i-1，這就保證了查找效率是O(log N)（N是系統(tǒng)所含有的節(jié)點(diǎn)數(shù)）。

2．2 CAN

CAN［5］是在現(xiàn)有網(wǎng)絡(luò)上抽象出一層疊加網(wǎng)絡(luò)。在CAN中將網(wǎng)絡(luò)的節(jié)點(diǎn)映射到一個(gè)d維的笛卡兒空間中，并盡可能為每個(gè)節(jié)點(diǎn)均勻分配一塊區(qū)域。CAN采用的哈希函數(shù)通過(guò)對(duì)關(guān)鍵值進(jìn)行Hash運(yùn)算得到笛卡兒空間中的一個(gè)點(diǎn)，并將關(guān)鍵值對(duì)存儲(chǔ)在該點(diǎn)所在區(qū)域的節(jié)點(diǎn)中。CAN的路由算法相當(dāng)簡(jiǎn)單直接，知道目標(biāo)節(jié)點(diǎn)后就將請(qǐng)求傳給當(dāng)前節(jié)點(diǎn)四鄰中最接近目標(biāo)的節(jié)點(diǎn)。CAN的路由性能是O(d.N1d)。

2．3 Kademlia

Kademlia［6］中關(guān)鍵值(Keys)用160位不透明的空間表示(如SHA1哈希一些大數(shù)據(jù)時(shí))，節(jié)點(diǎn)ID也用一個(gè)160位的空間來(lái)表示，它是節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)隨機(jī)分配的。Kademlia主要采用了XOR度量機(jī)制，將關(guān)鍵值與節(jié)點(diǎn)ID進(jìn)行異或運(yùn)算得到它們之間的距離，按照這種距離觀念，關(guān)鍵值被存在ID值與關(guān)鍵值距離最近的一些節(jié)點(diǎn)上。對(duì)于給定的Key值，基于ID的路由算法讓Kad中任何節(jié)點(diǎn)均可以定位到與Key最接近的節(jié)點(diǎn)上。

Kad的路由表是一棵二進(jìn)制樹(shù)，樹(shù)的葉子節(jié)點(diǎn)是kbuckets。在Kad中，為了進(jìn)行信息查詢，每個(gè)節(jié)點(diǎn)保存有一些關(guān)于其他節(jié)點(diǎn)的信息，對(duì)每個(gè)i（0≤i≤160），節(jié)點(diǎn)均保存有到自身距離在2i~2i+1之間的k（系統(tǒng)參數(shù)）個(gè)節(jié)點(diǎn)的信息。給定一個(gè)關(guān)鍵值，節(jié)點(diǎn)k查找與關(guān)鍵值最接近的節(jié)點(diǎn)。節(jié)點(diǎn)從自己最接近的kbucket開(kāi)始，選取部分節(jié)點(diǎn)并向其發(fā)送請(qǐng)求信息；然后再根據(jù)這些節(jié)點(diǎn)的應(yīng)答信息選取k個(gè)最接近的節(jié)點(diǎn)；此過(guò)程遞歸進(jìn)行，直到?jīng)]有更接近的節(jié)點(diǎn)被返回為止。Kad的查找是在一個(gè)個(gè)子數(shù)中進(jìn)行的，其效率也是O(log N)。

2．4 Tapestry

Tapestry［8］源于Plaxton的路由機(jī)制。與Pastry相似，節(jié)點(diǎn)通過(guò)一次糾正一位的方式遞交查詢請(qǐng)求，來(lái)一步步接近目標(biāo)節(jié)點(diǎn)，所以節(jié)點(diǎn)匹配自己標(biāo)識(shí)符的每一個(gè)前綴而下一位不同的鄰居信息。對(duì)于有N個(gè)節(jié)點(diǎn)的系統(tǒng)，每個(gè)節(jié)點(diǎn)有O(log N)個(gè)鄰居節(jié)點(diǎn)，由于每跳糾正一位，所以路由路徑為O(log N)跳。

2．5 Pastry

Pastry［7］中節(jié)點(diǎn)用128位空間的節(jié)點(diǎn)ID來(lái)標(biāo)志，節(jié)點(diǎn)ID是節(jié)點(diǎn)加入系統(tǒng)時(shí)通過(guò)哈希其IP地址隨機(jī)分配的。關(guān)鍵值被存放于與節(jié)點(diǎn)ID在數(shù)字上相接近的節(jié)點(diǎn)上，關(guān)鍵值查找是通過(guò)逐漸匹配前綴來(lái)進(jìn)行的。

Pastry的路由狀態(tài)由三部分組成，即路由表R、鄰居集M和葉子集L。R由｜log2b N｜行，每行2b-1個(gè)入口的表項(xiàng)組成（b是參數(shù)，可根據(jù)系統(tǒng)的大小選定，一般可為4），行n的2b-1個(gè)入口指向其ID和當(dāng)前節(jié)點(diǎn)ID共享前n位，但第n+1位不同于2b-1個(gè)表項(xiàng)；M包含了與本地節(jié)點(diǎn)最接近的|M|個(gè)節(jié)點(diǎn)；L是「L/2」個(gè)其ID最接近且大于本地節(jié)點(diǎn)ID的節(jié)點(diǎn)和「L/2」個(gè)其ID最接近且小于本地節(jié)點(diǎn)ID的節(jié)點(diǎn)的節(jié)點(diǎn)集合。給定一個(gè)關(guān)鍵值，節(jié)點(diǎn)先檢查它是否落在葉子集范圍內(nèi)，如是則直接將查詢交到葉子集中ID最接近關(guān)鍵值的節(jié)點(diǎn)，查詢結(jié)束；如在葉子集范圍外，則將查詢轉(zhuǎn)發(fā)到ID和關(guān)鍵值共享的位數(shù)比本地節(jié)點(diǎn)ID和關(guān)鍵值共享位數(shù)至少長(zhǎng)一位的節(jié)點(diǎn)，如這樣的節(jié)點(diǎn)不存在則轉(zhuǎn)發(fā)到共享位數(shù)一樣長(zhǎng)但I(xiàn)D值比本地節(jié)點(diǎn)ID值更接近關(guān)鍵值的節(jié)點(diǎn)。其查詢效率為O(log N)。

2．6 基于DHT技術(shù)搜索定位技術(shù)的優(yōu)點(diǎn)與不足

正是由于不具有結(jié)構(gòu)化的P2P系統(tǒng)的極不可擴(kuò)展性激發(fā)了人們對(duì)結(jié)構(gòu)化P2P系統(tǒng)的研究?；贒HT技術(shù)的系統(tǒng)基本解決了非DHT系統(tǒng)所面臨的問(wèn)題，如系統(tǒng)具有可擴(kuò)展性、一定程度的負(fù)載平衡等。但DHT算法也存在許多問(wèn)題。在文獻(xiàn)［3］中作者也對(duì)基于DHT的路由算法存在的問(wèn)題進(jìn)行了介紹，并提出15個(gè)問(wèn)題。

(1)QoS問(wèn)題。由于節(jié)點(diǎn)加入系統(tǒng)時(shí)ID是隨機(jī)分配的，使得兩個(gè)ID很近的節(jié)點(diǎn)在實(shí)際的物理位置可能很遠(yuǎn)，在P2P層的一跳到IP層就可能是多跳，這就存在請(qǐng)求延遲和下載延遲。目前人們開(kāi)始研究在原有算法基礎(chǔ)上考慮節(jié)點(diǎn)的實(shí)際物理位置，如按物理位置對(duì)節(jié)點(diǎn)聚集或分類等，進(jìn)一步研究還有待深入。

(2)擁塞問(wèn)題。對(duì)于那些比較熱的文件，請(qǐng)求和下載最后均路由到存儲(chǔ)該文件的節(jié)點(diǎn)上，這就會(huì)造成這些節(jié)點(diǎn)的超載甚至崩潰，進(jìn)而可能造成整個(gè)網(wǎng)絡(luò)的癱瘓。目前對(duì)此問(wèn)題提出的解決方法是緩存和多點(diǎn)復(fù)制，實(shí)驗(yàn)表明這在很大程度上可以解決這一問(wèn)題，但還有問(wèn)題存在。

(3)安全問(wèn)題和隨機(jī)失效性。目前的DHT算法基本上均未考慮惡意攻擊問(wèn)題，這在網(wǎng)絡(luò)中是經(jīng)常存在的。惡意攻擊可能給系統(tǒng)返回錯(cuò)誤數(shù)據(jù)或破壞系統(tǒng)數(shù)據(jù)搜索功能，嚴(yán)重時(shí)后者可能導(dǎo)致系統(tǒng)癱瘓。現(xiàn)在對(duì)P2P的安全性問(wèn)題研究還不太多，一些分布式加密開(kāi)始運(yùn)用到上面，還有的提出了信任度模型，但對(duì)于隨機(jī)節(jié)點(diǎn)失效系統(tǒng)的恢復(fù)功能均沒(méi)有采用洪泛算法的Gnutella性能好。

(4)多關(guān)鍵字查詢問(wèn)題。DHT算法采用分布式哈希函數(shù)，文件是通過(guò)對(duì)文件名進(jìn)行哈希得到的二進(jìn)制關(guān)鍵值，文件的查詢是按關(guān)鍵值進(jìn)行的，因此基于DHT的算法只支持精確查詢，無(wú)法進(jìn)行模糊匹配。這對(duì)用戶的查詢是個(gè)極大限制，現(xiàn)在這方面的研究也較多，主要考慮的是數(shù)據(jù)存儲(chǔ)方式，如建立多關(guān)鍵字索引等。

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

目前，各方面的人員已經(jīng)從不同的角度對(duì)P2P技術(shù)進(jìn)行了研究，主要有分布數(shù)據(jù)加密即安全性、分布式數(shù)據(jù)存儲(chǔ)和網(wǎng)絡(luò)性能等，其路由算法更是人們研究的一個(gè)熱點(diǎn)。本文通過(guò)對(duì)幾個(gè)典型系統(tǒng)，特別是基于DHT算法的幾個(gè)系統(tǒng)路由算法的描述與分析，給出了其目前存在的不足之處和改進(jìn)方向。相信隨著研究的深入，P2P系統(tǒng)各方面性能將會(huì)得到極大改善，其應(yīng)用范圍也將更加廣泛。

參考文獻(xiàn)：

［1］Gnutella Website［EB/OL］.http://www.gnutella.com．

［2］Napster Website［EB/OL］. http://www.napster.com．

［3］Sylvia Ratnasamy， Scott Shenker，Ion Stoica. Routing Algorithms for DHTs: Some Open Questions［C］. The 1st International Workshop on PeertoPeer Systems，2002.

［4］Ion Stoica， Robert Morris， et al.Chord:A Scalable PeertoPeer Lookup Service for Internet Applications［C］. ACM SIGCOMM，2001．

［5］Sylvia Ratnasamy， Paul Francis， Mark Handley， et al.A Scalable Contentaddressable Network［C］. Proc. of ACM SIGCOMM，2001.

［6］Petar Maymounkov，David Mazières. Kademlia: A PeertoPeer Information System Based on the XOR Metric ［C］. IPTPS 2002，LNCS 2429，2002．53-65.

［7］A Rowstron， P Druschel. Pastry:Scalable，Distributed Object Location and Routing for Largescale PeertoPeer Systems［EB/OL］.http://research.microsoft.com/~antr/pastry/，2001.

［8］B Y Zhao，L Huang，J Stribling，et al.Tapestry:A Resilient Globalscale Overlay for Service Deployment［J］.IEEE Journal on Seleted Areas in Communications，2004，22(1):41-53.

［9］Chonggang Wang ，Bo Li.PeertoPeer Overlay Networks:A Survey［EB/OL］.http://citeseer.ist.psu.edu/706822.html，2003.

［10］ClarkeI，Sandberg O，et al.Freenet: A Distributed Anonymous Information Storage and Retrieval System［C］.Berkeley，California:Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability，2000.

作者簡(jiǎn)介：

李運(yùn)娣，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng)；馮勇，研究員，博導(dǎo)，主要研究方向?yàn)榉植际接?jì)算與混合計(jì)算。

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