對等網(wǎng)絡(luò)中ＤＨＴ搜索算法綜述

摘要：在P2P網(wǎng)路中如何快速準(zhǔn)確地對資源進行定位是衡量其性能的一個關(guān)鍵。現(xiàn)在的分布式P2P系統(tǒng)普遍采取的是DHT（distributed hash table，分布式哈希表）搜索方法。基于DHT的P2P網(wǎng)絡(luò)搜索算法的研究已經(jīng)是P2P研究的一個熱點。從P2P定義出發(fā)，介紹了P2P網(wǎng)絡(luò)按照拓撲結(jié)構(gòu)的分類發(fā)展；然后深入介紹了目前對等網(wǎng)絡(luò)幾種分布式哈希查找算法Chord、CAN、SkipNet和Cycloid等，并對這些算法從拓撲結(jié)構(gòu)、路由復(fù)雜度、路由表大小、容錯性、擴展性、負載平衡性等方面進行了評估比較；最后分析了這些算法的優(yōu)缺點及今后研究的重點。

關(guān)鍵詞：對等網(wǎng)絡(luò)； 搜索； 分布式哈希表； Chord ； CAN； 關(guān)鍵字

中圖分類號：TP393文獻標(biāo)志碼：A

文章編號：1001－3695(2008)06－1611－05

P2P是一種分布式網(wǎng)絡(luò)，網(wǎng)絡(luò)的參與者共享他們所擁有的一部分硬件資源（處理能力、存儲能力、網(wǎng)絡(luò)連接能力、打印機等）。這些共享資源需要由網(wǎng)絡(luò)提供服務(wù)和內(nèi)容，能被其他對等節(jié)點(peer)直接訪問而無須經(jīng)過中間實體。在此網(wǎng)絡(luò)中的參與者既是資源（服務(wù)和內(nèi)容）提供者（server），又是資源（服務(wù)和內(nèi)容）獲取者（client）。

P2P按照拓撲結(jié)構(gòu)的不同可以分為三種：a)集中式拓撲模式，如Napster[1]。這種模式必須有中央服務(wù)器。當(dāng)系統(tǒng)中節(jié)點數(shù)增多時，中央服務(wù)器就成為系統(tǒng)的瓶頸。b)分布式非結(jié)構(gòu)化拓撲模式，如Gnutella[2]和Freenet[3]。每個節(jié)點存儲自身的信息或信息的索引，當(dāng)用戶需要在P2P系統(tǒng)中獲取信息時，他們預(yù)先并不知道這些信息會在哪個節(jié)點上存儲，搜索采用泛洪方式，搜索在超出一定范圍后就不能進一步擴展。因此，在非結(jié)構(gòu)化P2P系統(tǒng)中，信息搜索的算法難免會帶有一定的盲目性。c)分布式結(jié)構(gòu)化拓撲模式，它們都是基于DHT技術(shù)的，如Chord[4]、CAN[5]、Pastry[6]和Tapestry[7]。每個節(jié)點只存儲特定信息或特定信息的索引。當(dāng)用戶需要在P2P系統(tǒng)中獲取信息時，他們必須知道這些信息(或索引)可能存在于哪些節(jié)點中。由于用戶預(yù)先知道應(yīng)該搜索哪些節(jié)點，避免了非結(jié)構(gòu)化P2P系統(tǒng)中使用的泛洪式查找，提高了信息搜索的效率。

本文介紹了基于DHT的P2P搜索算法的原理，以及典型的分布式結(jié)構(gòu)化路由算法（如Chord、CAN、Pastry、Tapestry、Kademlia[8]、SkipNet[9]）和基于常數(shù)度數(shù)的路由算法（如Viceroy[10]、Koorde[11]、Cycloid[12]）。

1DHT算法原理介紹

DHT算法使用分布式哈希函數(shù)來解決結(jié)構(gòu)化的分布式存儲問題。分布式哈希表實際上是一張很大的散列表；每個節(jié)點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。DHT及其發(fā)現(xiàn)技術(shù)為P2P網(wǎng)絡(luò)中資源的組織與查找提供了一種全新的算法思想。

該方法的原理是：每一份資源都由一組關(guān)鍵字進行標(biāo)志，系統(tǒng)對其中的每個關(guān)鍵字進行哈希，得到關(guān)鍵字標(biāo)志符key；網(wǎng)絡(luò)中的每個節(jié)點也通過哈希節(jié)點IP得到節(jié)點標(biāo)志符ID；關(guān)鍵字標(biāo)志符和節(jié)點標(biāo)志符都是惟一的；按照某種映射關(guān)系，將關(guān)鍵字標(biāo)志符映射到節(jié)點標(biāo)志符上，該節(jié)點標(biāo)志符對應(yīng)的節(jié)點就存儲此關(guān)鍵字標(biāo)志符的對應(yīng)信息。所有的〈key，value〉對構(gòu)成一張很大的文件索引散列表。其中：key 是關(guān)鍵字哈希；va－lue是要存儲的信息地址。例如：key=hash(千里之外.mp3)，value=http://video.com.cn/qlzw.mp3。每個節(jié)點按照某種規(guī)則維護散列表的一部分。這里的規(guī)則依協(xié)議的不同而不同。用戶搜索時，用同樣的哈希算法計算出每個關(guān)鍵字的標(biāo)志符key，再根據(jù)關(guān)鍵字標(biāo)志符知道該關(guān)鍵字標(biāo)志對應(yīng)信息的存儲位置，從而能夠快速定位資源的位置。

基于分布式哈希表的分布式檢索和路由算法因為具有查找可確定性、簡單性和分布性等優(yōu)點，正成為國際上結(jié)構(gòu)化P2P網(wǎng)絡(luò)研究和應(yīng)用的熱點。

2現(xiàn)有DHT搜索算法介紹

2．1典型DHT搜索算法

自從DHT思想提出來以后，分布式結(jié)構(gòu)化P2P搜索算法得到了快速發(fā)展。目前很多DHT協(xié)議被提出并且得到應(yīng)用，其中比較典型的有美國麻省理工學(xué)院的Chord、加州大學(xué)伯克利分校的Tapestry和CAN、微軟研究院的Pastry和SkipNet、美國紐約大學(xué)的 Kademlia。

1）Chord在2001年由美國麻省理工學(xué)院提出。它的設(shè)計基于一維環(huán)形空間，每個關(guān)鍵字和節(jié)點都分配一個m bit的標(biāo)志符；所有節(jié)點按照其節(jié)點標(biāo)志符從小到大按順時針方向排列成一個Chord環(huán)。 〈key， value〉對存儲在節(jié)點標(biāo)志等于key或者在Chord環(huán)上緊跟在key之后的節(jié)點，這個節(jié)點被稱為key的后繼節(jié)點。每個節(jié)點需要維護一個路由表（指針表），表中每一項包含相關(guān)節(jié)點的標(biāo)志符和IP地址（和端口號）。如果關(guān)鍵字和節(jié)點標(biāo)志符用m位二進制位數(shù)表示，那么指針表中最多含有m個表項，節(jié)點n的指針表中第i項是Chord環(huán)上標(biāo)志大于或等于n+2i-1的第一個節(jié)點。顯然，指針表的第一項為當(dāng)前節(jié)點的后繼節(jié)點。節(jié)點收到查詢key的請求時，首先檢查該關(guān)鍵字標(biāo)志是否落在該節(jié)點標(biāo)志與它的后繼節(jié)點標(biāo)志之間。如果是，那么這個后繼節(jié)點就是存儲目標(biāo)〈key，value〉對的節(jié)點；否則，節(jié)點將查找它的指針表，找到表中節(jié)點標(biāo)志符最大但不超過key標(biāo)志符的第一個節(jié)點，并將這個查詢請求轉(zhuǎn)發(fā)給該節(jié)點。通過重復(fù)這個過程，最終可以定位到存儲有目標(biāo)〈key，value〉對的節(jié)點。圖1給出了Chord環(huán)和節(jié)點標(biāo)志符是8的節(jié)點指針表[4]。

Chord的突出特點是算法簡單，性能較好，但是在Chord系統(tǒng)中，隨著節(jié)點規(guī)模的不斷增大，節(jié)點性能的差異會嚴重影響系統(tǒng)的效率。文獻[13]提出了雙向路由 dual－Chord。其基本思想是從當(dāng)前節(jié)點的順時針和逆時針同時構(gòu)造路由表，雙向路由的平均查找長度可以減少到1/3 log(N)。但是這種方法的路由表是原來的兩倍。文獻[14]提出一種改進的Chord算法G－Chord，通過對Chord環(huán)進行分組，實現(xiàn)組內(nèi)節(jié)點的自治，而組間的路由和查詢則通過組代表進行，使得路由表的長度得到大幅度的減少，而且在總跳數(shù)和平均路徑長度方面基本保持一致。

2)CAN在2001年由美國加州大學(xué)伯克利分校提出。它的設(shè)計基于虛擬的d維笛卡兒坐標(biāo)空間。這個坐標(biāo)空間完全是邏輯的，與任何物理坐標(biāo)系統(tǒng)都沒有關(guān)系；整個坐標(biāo)空間動態(tài)地分配給系統(tǒng)中的所有節(jié)點，每個節(jié)點負責(zé)維護互不相交的一塊區(qū)域。與Chord標(biāo)志符是一維的不同，它的每個關(guān)鍵字和節(jié)點通過哈希后都分別擁有一個d維向量的標(biāo)志符，對應(yīng)于d維坐標(biāo)空間中的一點，〈key，value〉對存儲在負責(zé)管理key所在空間的節(jié)點上；每個CAN節(jié)點都要保存一張坐標(biāo)路由表，包括它的鄰居節(jié)點（相鄰空間區(qū)域中的節(jié)點）的IP地址和其維護的虛擬坐標(biāo)區(qū)域，當(dāng)需要查詢key時，路由的每一步只需將查詢信息發(fā)給離key值更近的鄰接節(jié)點。圖2給出了二維CAN空間中節(jié)點1到點（x，y）的路由過程[5]。因為整個CAN空間要分配給系統(tǒng)中現(xiàn)有的全部節(jié)點，當(dāng)一個新的節(jié)點加入網(wǎng)絡(luò)時，必須得到自己的一塊坐標(biāo)空間。CAN通過分割現(xiàn)有的節(jié)點區(qū)域?qū)崿F(xiàn)這一過程，它把某個現(xiàn)有節(jié)點的區(qū)域分裂成同樣大小的兩塊，自己保留其中的一塊而另一塊分給新加入的。

CAN算法的路由路徑趨于很長，定位內(nèi)容花費的世紀鏈路延遲大，因此文獻[15]提出了一種CAN的擴展算法——eCAN(expressways CAN)。它考慮一個二維空間（實際上該算法適合任何維數(shù)空間），把空間劃分為四部分，每個節(jié)點保留其兩個鄰接區(qū)域的LRCs；然后每部分再同樣劃分為更小的四部分。這樣每個節(jié)點保留了所有LRC。實際上eCAN算法是在CAN算法的基礎(chǔ)上進一步引入了加速指針，因而提高了查找效率。文獻[16]提出了一種改進的CAN算法HIMCAN。該系統(tǒng)按照物理網(wǎng)絡(luò)距離把節(jié)點分成多組，組內(nèi)獨立建立CAN，使用HD模型和FN模型參數(shù)以及結(jié)合算法將各組節(jié)點連接起來，組成全局意義的HiMCAN，實現(xiàn)查詢的路由本地化，優(yōu)化路由參數(shù)，適合在廣域范圍實現(xiàn)結(jié)構(gòu)性的P2P網(wǎng)絡(luò)應(yīng)用。

3)Pastry由位于英國劍橋的微軟研究院和萊斯大學(xué)提出，它是自組織的重疊網(wǎng)絡(luò)。為了進行路由，Pastry把節(jié)點和關(guān)鍵字標(biāo)志符表示為一串以2b為基的數(shù)(b的取值是路由表大小與任意兩節(jié)點間需要的最大路由跳數(shù)之間的折中)，查詢消息被路由到節(jié)點標(biāo)志和關(guān)鍵字標(biāo)志在數(shù)值上最接近的節(jié)點。方法是：每個節(jié)點將查詢消息轉(zhuǎn)發(fā)給下一個節(jié)點時，要保證這個節(jié)點標(biāo)志和關(guān)鍵字標(biāo)志的相同前綴至少要比當(dāng)前節(jié)點的標(biāo)志和關(guān)鍵字標(biāo)志的相同前綴長一個數(shù)位（即b bit）。如果找不到這樣的鄰居節(jié)點，消息將轉(zhuǎn)發(fā)給前綴長度相同但是節(jié)點號數(shù)值更接近關(guān)鍵字標(biāo)志的節(jié)點。為此每個Pastry節(jié)點都需要三張表：一張路由表、一個鄰居節(jié)點集和一個葉子節(jié)點集。節(jié)點收到一條查詢消息時，首先檢查該消息的關(guān)鍵字標(biāo)志K是否落在葉子節(jié)點集范圍內(nèi)。如果是，則直接將消息轉(zhuǎn)發(fā)給葉子節(jié)點集中節(jié)點標(biāo)志和關(guān)鍵字標(biāo)志最接近的節(jié)點。如果K沒有落在葉子節(jié)點集范圍內(nèi)，節(jié)點就會將消息轉(zhuǎn)發(fā)給路由表中的一個節(jié)點。該節(jié)點的標(biāo)志符和K的相同前綴至少要比當(dāng)前節(jié)點的標(biāo)志符和K的相同前綴長一個數(shù)位。如果路由表中相應(yīng)的表項為空，或者表項中對應(yīng)的節(jié)點不可達，這時查詢消息將被轉(zhuǎn)發(fā)給前綴長度相同但節(jié)點標(biāo)志符更接近K的節(jié)點。很明顯，路由的每一步都比上一步向目標(biāo)節(jié)點前進了一步，因此路由過程總是收斂的。

4)Tapestry是美國加州大學(xué)伯克利分校提出的一種新型的P2P網(wǎng)絡(luò)定位和路由算法。該算法可以對消息進行與位置無關(guān)的路由，將查詢消息傳遞到最近的存儲有目標(biāo)對象拷貝的節(jié)點。Tapestry標(biāo)志符用一個全局統(tǒng)一的進制表示（如使用十六進制）。所有的節(jié)點依據(jù)標(biāo)志符自組織成一個重疊網(wǎng)絡(luò)。每個節(jié)點需要維護一個鄰居映射表，每個表項包括一個鄰居節(jié)點的標(biāo)志符和IP地址。節(jié)點N的鄰居映射表分為多個級別，每個級別包含的鄰居節(jié)點數(shù)量等于標(biāo)志符表示法的基數(shù)；每個級別中鄰居節(jié)點標(biāo)志符和本節(jié)點標(biāo)志符的相同前綴都比前一級別多一個數(shù)位。

Tapestry采用基于地址前綴的路由機制。其思想是按照從左到右的順序，每次只改變一個數(shù)位。圖3給出了節(jié)點5230查找節(jié)點42AD的過程[7]。這種方法可以保證路由至多經(jīng)過logb N個節(jié)點就可以到達目的節(jié)點；同樣，由于每個節(jié)點的鄰居映射表的每個級別只需要保存b個表項，鄰居映射表的空間為logb N。

5)Kademlia協(xié)議是美國紐約大學(xué)在2002年提出的。與Chord、CAN、Pastry、Tapestry不同，在Kademlia網(wǎng)絡(luò)中，兩個節(jié)點之間距離并不是依靠物理距離、路由跳數(shù)來衡量的，而是根據(jù)兩個節(jié)點標(biāo)志的異或（XOR），建立了一種全新的DHT拓撲結(jié)構(gòu)，相比于其他算法，大大提高了路由查詢速度。 

每一個節(jié)點均維護了160個list。其中的每個list均被稱之為一個k－桶。在第i個list中，記錄了與當(dāng)前節(jié)點距離為[2i，2i+1)的一些其他對端節(jié)點的網(wǎng)絡(luò)信息(Node ID、IP地址、UDP端口)。當(dāng)需要查詢關(guān)鍵字key時，首先發(fā)起者從自己的k－桶中篩選出若干距離目標(biāo)節(jié)點最近的節(jié)點，并向這些節(jié)點同時發(fā)送異步查詢請求；被查詢節(jié)點收到請求之后，將從自己的k－桶中找出自己所知道的距離目標(biāo)節(jié)點最近的若干個節(jié)點，并返回給發(fā)起者；發(fā)起者在收到這些返回信息之后，再次從自己目前所有已知的距離目標(biāo)較近的節(jié)點中挑選出若干沒有請求過的。上述步驟不斷重復(fù)，直至無法獲得比查詢者當(dāng)前已知的k個節(jié)點更接近目標(biāo)的活動節(jié)點為止。

6)SkipNet是2003年由微軟Redmond研究院提出的。與前面幾種結(jié)構(gòu)化路由協(xié)議相比， 每個節(jié)點有兩個標(biāo)志：字典域標(biāo)志和數(shù)字域標(biāo)志。字典域標(biāo)志符由于一般使用網(wǎng)絡(luò)域名等標(biāo)志串，它越近就表示網(wǎng)絡(luò)距離越近。SkipNet把節(jié)點組織成多個層次的環(huán)，每個環(huán)上的節(jié)點按照字典域標(biāo)志符順時針排列。第0層的環(huán)比較特殊，它包含所有節(jié)點，稱該環(huán)為根環(huán)。以后第i層的環(huán)一分為二構(gòu)成第i+1層環(huán)。SkipNet也是采用基于地址前綴的路由查找算法。由于它具有兩個地址空間，相應(yīng)的路由算法也比其他算法多，分別有字典域路由、數(shù)字域路由和混合路由。字典域路由算法相當(dāng)于折半查找過程；數(shù)字域路由算法相當(dāng)于前綴匹配過程。

2．2基于超節(jié)點的DHT算法

很多結(jié)構(gòu)化覆蓋網(wǎng)都保證消息可以通過不到log (N)次轉(zhuǎn)發(fā)到達目標(biāo)節(jié)點，包括Chord、CAN、Tapestry、Pastry、SkipNet、Kademlia等。然而，另外一些結(jié)構(gòu)化覆蓋網(wǎng)的研究者認為，O(logN)跳仍然效率不高，而現(xiàn)在的終端節(jié)點有能力維護更多的指針，從而取得更高的路由效率。他們提出一些在一跳或兩跳之內(nèi)即可完成消息路由的結(jié)構(gòu)化覆蓋網(wǎng)協(xié)議，包括Kelips[17]、One－h(huán)op[18]、Twins[19]等。

Kelips將節(jié)點分成k組，組內(nèi)節(jié)點全連接，通過Gossip的方式進行更新。這樣維護開銷增大很多，但是路由可以在2跳完成。One－h(huán)op中每個超級節(jié)點維護全局路由狀態(tài)，記錄其他所有節(jié)點的信息。這樣路由可以在1跳內(nèi)完成，查找速度快、延時小。這些協(xié)議與前述協(xié)議的根本不同在于，它們使用組播或者廣播的方式進行指針維護，即節(jié)點加入或退出時將消息廣播（或組播）給所有需要知道該消息的節(jié)點。這種方法較顯式探測的方法帶寬開銷小很多，因此節(jié)點可以維護非常大量的指針，保證路由在很少的跳數(shù)內(nèi)完成。但是該方法路由表的開銷較大，路由表的開銷為O（N）或O（N1/2）。在大規(guī)模的重疊網(wǎng)環(huán)境中，由于可能存在大量的(數(shù)百萬)節(jié)點，加之節(jié)點都是動態(tài)加入和退出網(wǎng)絡(luò)，這一條件幾乎不可能滿足。

2．3常數(shù)度數(shù)DHT搜索算法

網(wǎng)絡(luò)節(jié)點度數(shù)決定了每個節(jié)點需要維護的鄰居節(jié)點數(shù)目。為減少維護開銷，近年來提出了具有常數(shù)度數(shù)的DHT算法，主要包括Koorde、Viceroy和Cycloid。

1）Viceroy基于一個具有常數(shù)度數(shù)和對數(shù)直徑的類似蝴蝶網(wǎng)的連接圖，它的每個節(jié)點都有兩個值：標(biāo)號ID∈[0，1)和層號l。標(biāo)號ID均勻獨立地分布在[0，1)上；層號是從區(qū)間[1，log N]之間隨機選取的一個值（N是網(wǎng)絡(luò)規(guī)模估計值）。標(biāo)號ID可以惟一地標(biāo)志一個節(jié)點，是不會變的；但是層號在節(jié)點的生存期內(nèi)可作適當(dāng)調(diào)整，層號只起路由作用，不起標(biāo)志作用。所有的節(jié)點構(gòu)成一個大環(huán)，同層節(jié)點又構(gòu)成一個小環(huán)。一個位于1層的節(jié)點有7個指針指向它的鄰居節(jié)點，分別是在大環(huán)中的前驅(qū)和后繼節(jié)點、同一小環(huán)上的前后兩個相鄰節(jié)點以及下層l+1層的左右兩個節(jié)點和上面l-1層的上行節(jié)點。

Viceroy的路由包括三個步驟：通過上行指針上升到第一層的某個節(jié)點；通過下行指針到達一個離目標(biāo)ID最近的節(jié)點；再通過大環(huán)或同層環(huán)到達目標(biāo)節(jié)點。每次查詢的路徑長度需要O(log N)步。

2）Koorde結(jié)合了Chord環(huán)和de Bruijn圖的特征，節(jié)點和關(guān)鍵字標(biāo)志符都是均勻分布在大小為2d的環(huán)形空間域中。其中，每一個節(jié)點都有兩個出度，節(jié)點標(biāo)志為N的節(jié)點指向節(jié)點標(biāo)志為2N和2N+1的節(jié)點。每個節(jié)點要維護后繼節(jié)點和首個de Bruijn節(jié)點。

Koorde的路由過程是：對于給定的鍵值K，路由算法必須根據(jù)相應(yīng)的de Bruijn圖找到K的后繼節(jié)點；但由于de Bruijn圖是不完全的，Koorde是將查詢轉(zhuǎn)發(fā)給假象節(jié)點i的前驅(qū)節(jié)點來模擬完全de Bruijn圖進行查找。每個節(jié)點與其他節(jié)點的連接度為O(1)，每次查詢的路徑長度需要O(log N)步。

3）Cycloid將Pastry與CCC(cube－connected cycles)結(jié)合起來， 它模仿 CCC的拓撲結(jié)構(gòu)。一個d維的CCC圖是在一個d為立方體上用d個節(jié)點的環(huán)替換各個頂點而構(gòu)成的。Cycloid中每個節(jié)點都由一對標(biāo)號（k，ad-1 ad-2 … a0)共同標(biāo)志。立方體標(biāo)號相同的所有節(jié)點構(gòu)成一個小環(huán)，而這些小環(huán)又構(gòu)成一個大環(huán)。每個節(jié)點有一個環(huán)上大鄰居(k-1，ad-1 ad-2 … akbk-1 … b0)和環(huán)上小鄰居(k-1，ad-1 ad-2 … akck-1 … c0)，還有一個立方體鄰居（k-1，ad-1 ad-2 … akxkxk-1 … x0)、兩個內(nèi)部葉節(jié)點（分別指向本地環(huán)上前驅(qū)和后繼節(jié)點）、兩個外部葉節(jié)點（它們與本節(jié)點有著相同的立方體標(biāo)號，分別指向前驅(qū)環(huán)和后繼環(huán)上具有最大環(huán)標(biāo)志的節(jié)點）。

Cycloid的路由過程分為三個階段：上升階段找到環(huán)標(biāo)號k≥MSDN的節(jié)點；再通過下降階段改變立方體標(biāo)號，使之更接近目標(biāo)節(jié)點的立方體標(biāo)號；最后遍歷環(huán)循環(huán)找到目標(biāo)節(jié)點。在節(jié)點數(shù)為n=d×2d的Cycloid系統(tǒng)中，每次查詢只要O(d)步，并且每個節(jié)點只需維護O(1)個鄰居，每一個節(jié)點與網(wǎng)絡(luò)中的其他節(jié)點連接只需七項，總的路徑長度為O(d)步。

3DHT搜索算法性能比較

上述介紹的算法都是基于分布式哈希表，其本質(zhì)是一樣的，但都有自己的特點。表1歸納總結(jié)了各種算法的拓撲結(jié)構(gòu)、路由表大小、路由復(fù)雜度和〈key，value〉的存放位置。下面將從算法擴展性、容錯性、負載平衡性三個方面綜合評估各種算法的優(yōu)劣并作比較。

3．1算法容錯性

在對等網(wǎng)絡(luò)中，節(jié)點可能隨時退出或者失效，一旦如此，查找不能進行。Chord中節(jié)點失效時，每個包含該節(jié)點的指針表都要把該節(jié)點換成它的后繼節(jié)點，為此每個Chord節(jié)點都維護一張包括r個最近后繼節(jié)點的后繼列表。如果某個節(jié)點注意到它的后繼節(jié)點失效了，就可以用其后繼列表中第一個正常節(jié)點替換失效節(jié)點。正常情況下，CAN中每個節(jié)點向其所有鄰居節(jié)點發(fā)送周期性的更新消息。如果多次沒有接收到某個鄰居的更新消息，那么節(jié)點就認為這個鄰居失效。這時節(jié)點將啟動接管機制來更新路由表。采用這種機制可以有效地選擇面積最小的鄰居節(jié)點來接管失效節(jié)點。CAN中一個節(jié)點一個或幾個鄰居節(jié)點失效時，它依然可以沿著有效的路徑路由，因此CAN算法的穩(wěn)健性很好。Pastry系統(tǒng)的節(jié)點一旦檢測出其葉子節(jié)點集L中的某個節(jié)點失效，它就會請求該集合中標(biāo)志符最大或最小的節(jié)點將其葉子節(jié)點集L′發(fā)送過來（如果失效節(jié)點的標(biāo)志符比當(dāng)前節(jié)點的標(biāo)志符大，則用葉子集中標(biāo)志符最大的節(jié)點，反之則用標(biāo)志符最小的節(jié)點），當(dāng)前節(jié)點將從L′中選擇一個L中沒有的活動節(jié)點來替代失效節(jié)點。如果系統(tǒng)檢測出其路由表中某項節(jié)點失效，它將從該項所在的路由表行中選擇另一個節(jié)點，要求該節(jié)點將路由表中對應(yīng)位置的項發(fā)過來。如果當(dāng)前節(jié)點的路由表中對應(yīng)行已經(jīng)沒有可用節(jié)點，那么當(dāng)前節(jié)點將從路由表的下一行中選擇一個節(jié)點。這個過程將繼續(xù)到當(dāng)前節(jié)點能夠得到一個替代失效節(jié)點的節(jié)點號，或者當(dāng)前節(jié)點遍歷了路由表為止。節(jié)點也會周期性地與鄰居節(jié)點集中的節(jié)點交換信息以檢測這些節(jié)點是否仍在。 Pastry 只有在|L|/2個葉子節(jié)點完全失效時才會路由失敗，因此Pastry的容錯性很好。Tapestry在Plaxton的思想上加入了容錯機制，當(dāng)節(jié)點失效時，它的鄰居節(jié)點可以檢測到它失效并對路由表作相應(yīng)調(diào)整，從而可適應(yīng)P2P的動態(tài)變化特點。Kademlia要求每個節(jié)點必須周期性地發(fā)布全部自己存放的〈key，value〉對數(shù)據(jù)，并把這些數(shù)據(jù)緩存在自己的k個最近鄰居處。這樣存放在失效節(jié)點的數(shù)據(jù)會很快被更新到其他新節(jié)點上，因此Kademlia算法具有很好的容錯性。Koorde把首個de Bruijn點的三個前驅(qū)當(dāng)成備份點，當(dāng)首個de Bruijn點和三個備用點失效時才失敗。Viceroy采用Bucket來保存更多的信息，以解決節(jié)點失效問題。

3．2算法擴展性

One－h(huán)op、Kelips、Twins等路由復(fù)雜度為O(1)，是一個常數(shù)，查詢key時路由跳數(shù)不會隨著節(jié)點增多而變大，但是每個節(jié)點要維護所有其他節(jié)點或者組內(nèi)所有節(jié)點的信息，因此新節(jié)點的加入或離開要更新的路由表信息很多，擴展性差。Chord、Pastry協(xié)議的開銷隨著系統(tǒng)規(guī)模(節(jié)點總數(shù)N)的增加而按照O(log N)的比例增加，而且新節(jié)點加入時需要更新的路由表信息也較少，因此它們可以用于大規(guī)模的系統(tǒng)。與Chord和CAN等相比，Tapestry在建立鄰居表時很好地考慮了節(jié)點鄰接性問題，它的節(jié)點動態(tài)加入算法很好地實現(xiàn)了系統(tǒng)的擴展性。Viceroy每個節(jié)點有進出兩種連接，一個節(jié)點的加入或離開要導(dǎo)致所有相關(guān)節(jié)點的狀態(tài)更新。Koorde節(jié)點加入或離開要通知它的前驅(qū)和后繼節(jié)點，更新它們的狀態(tài)并使其連接，但是de Brujin圖首個節(jié)點離開必須要等待系統(tǒng)穩(wěn)定時才可以更新。Cycloid 中節(jié)點離開時要通知它內(nèi)葉集合中的節(jié)點，如果此節(jié)點是所在環(huán)上標(biāo)號最大的節(jié)點，那么還要通知它的外葉集合中的節(jié)點。One－h(huán)op是強聯(lián)通圖，每個節(jié)點的離開要通知其他所有的節(jié)點并更新所有的節(jié)點路由表信息。

3．3負載平衡性

DHT算法設(shè)計的一個重要性能就是平衡查詢負載。Chord、Tapestry、Pastry、Kademlia所有的節(jié)點以同等的概率分擔(dān)系統(tǒng)負荷，從而可以避免某些節(jié)點負載過大的情況，因此負載平衡性好。每個CAN節(jié)點都要保存一張坐標(biāo)路由表，其中包括它的鄰居節(jié)點（相鄰空間區(qū)域中的節(jié)點）的IP地址和其維護的虛擬坐標(biāo)區(qū)域。當(dāng)需要查詢key時，路由的每一步只需將查詢信息發(fā)送給離key值更近的鄰接節(jié)點。維護面積大的節(jié)點的鄰居節(jié)點較多，查詢時負載也大。One－h(huán)op查詢key時只需要一跳，負載平衡且負載較輕。Kelips路由查詢時都要通過超節(jié)點，因此超節(jié)點的負載比普通節(jié)點的負載大。Koorde結(jié)合了Chord環(huán)和de Bruijn圖的特征，標(biāo)志符為m的節(jié)點其de Brujin圖首個de Bruijn點的節(jié)點標(biāo)志符為2m，所以造成標(biāo)志符為偶數(shù)的節(jié)點查詢負載大，而標(biāo)志符為奇數(shù)的節(jié)點查詢負載較輕。Viceroy維護了一個具有常數(shù)度數(shù)和對數(shù)直徑的類似蝴蝶網(wǎng)的連接圖，其所有節(jié)點都要經(jīng)過上行指針到最上層，再由下行指針達到?jīng)]有下行指針的層，所以造成高層節(jié)點查詢負載大而低層節(jié)點查詢負載小。Cycloid中的key 存放在數(shù)值最接近的節(jié)點上。由于在路由的上升階段要保證k≥MSDN，對于環(huán)標(biāo)志符較大的節(jié)點查詢負載較大，環(huán)標(biāo)志符小的節(jié)點查詢負載較小。表2為這些算法從容錯性、擴展性、負載平衡性的比較。

在理論上，文獻[20]證明了Chord、Pastry、Tapestry就路由表的大小而言，它們所獲得的路由效率已經(jīng)在數(shù)量級上達到最優(yōu)。文獻[21]討論了各種算法所使用的拓撲結(jié)構(gòu)和系統(tǒng)對節(jié)點失敗的適應(yīng)性和對鄰選擇的兼容性的關(guān)系。文獻[22]用圖論的觀點比較了Chord、Pastry、Tapestry、CAN的路由性能和容錯性。

4結(jié)束語

本文綜述了在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中占有重要地位的分布P2P搜索算法，對每種算法核心思想進行了描述。基于分布式哈希表的搜索方法一直是研究的熱點，一些新的搜索方法不斷涌現(xiàn)，但是，目前大多數(shù)DHT算法都存在很多問題，歸納起來主要有下面幾點[23]：

a)不支持多關(guān)鍵字查詢。DHT算法通過對文件名進行哈希得到的關(guān)鍵字標(biāo)志，文件的查詢是按關(guān)鍵值標(biāo)志進行的，因此基于 DHT的算法只支持精確查詢，無法進行模糊匹配。由于DHT的精確關(guān)鍵詞映射的特性決定了無法與信息檢索等領(lǐng)域的研究成果結(jié)合，阻礙了基于DHT的P2P系統(tǒng)的大規(guī)模應(yīng)用。現(xiàn)在研究這方面主要考慮的是數(shù)據(jù)存儲方式，如建立多關(guān)鍵字索引等。

b)不支持語義。DHT算法采用相容散列函數(shù)對關(guān)鍵字哈希，散列函數(shù)總是試圖保證生成的哈希值均勻隨機分布，結(jié)果兩個內(nèi)容相似度很高但不完全相同的對象被生成了完全不同的散列值，存放到完全隨機的兩個節(jié)點上，因此目前DHT算法不支持語義。

c)沒有考慮熱點資源對網(wǎng)絡(luò)性能的影響。對于那些比較熱門的資源，查詢和下載最后均路由到存儲該資源的節(jié)點上，這就會造成這些節(jié)點的超載甚至崩潰，進而可能造成整個網(wǎng)絡(luò)的癱瘓。目前對此問題提出的解決方法是緩存和多點復(fù)制。

d)物理位置和邏輯位置關(guān)聯(lián)問題。由于節(jié)點加入系統(tǒng)時節(jié)點標(biāo)志符是隨機分配的，使得兩個標(biāo)志符很近的節(jié)點實際的物理位置可能很遠。節(jié)點之間進行對等通信時，不會優(yōu)先選取距離自己最近的節(jié)點，這就存在請求延遲和下載延遲。目前人們開始研究在原有算法基礎(chǔ)上考慮節(jié)點的實際物理位置，如按物理位置對節(jié)點聚集或分類等，進一步研究還有待深入。

e)安全問題。P2P網(wǎng)絡(luò)中節(jié)點可以隨意加入和離開，但是有些節(jié)點攻擊可能影響系統(tǒng)數(shù)據(jù)搜索功能或給系統(tǒng)返回錯誤數(shù)據(jù)，嚴重時后者可能導(dǎo)致系統(tǒng)癱瘓。目前的DHT算法基本上均未考慮惡意攻擊問題。

參考文獻：

［1］Napster工程[EB/OL]. http://www.napster.com/.

[2]Gnutella工程[EB/OL]. http://gnutella.wego.com.

[3]CLARKE I，SANDERG O，WILEY B，et al. Freenet: a distributed anonymous information storage and retrieval system[C]//Proc ofICSI Workshop on Design Issues in Anonymity and Unobservability. Berkeley：[s.n.]，2000.

[4]STOICA I， MORRIS R， LIBEN－NOWELL D，et al. Chord: a scalable peer－to－peer lookup protocol for Internet applications[J]. IEEE/ACM Trans on Networking， 2003，11(1):17－32.

[5]RATNASAMY S，F(xiàn)RANCIS P，HANDLEY M，et al. A scalable content－addressable network[C]//Proc ofACM SIGCOMM Symposium on Communication，Architecture，and Protocols.2001.

[6] ROWSTORN A，DRUSCHEL P. Pastry:scalable，decentralized object location and routing for large－scale peer－to－peer systems[C]//Proc of the 18th IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001). Heidelberg:[s.n.]，2001.

[7]ZHAO B Y，LING Huang，STRIBLING J， et al. Tapestry:a resilient global－scale overlay for service deployment[J].IEEE Journal on Selected Areas in Communications，2004，22(1): 41－53.

[8]MAYMOUNKOV P，MAZIERES D. Kademlia: a peer－to－peer information system based on the xor metric[C]//Proc of the 1st International Workshop on Peer－to－Peer Systems (IPTPS’02).Cambridge:[s.n.]，2002.

[9]HARVEY N J A，JONES M B，SAROIU S，et al. SkipNet: a scalable overlay network with practical locality properties[C]//Proc of the 4th USENIX Symposium on Internet Technologies and Systems.2003.

[10]MALKHI D，NAOR M，RATAJCZAK D. Viceroy:a scalable and dynamic emulation of the butterfly[C]//Proc of Principles of Distributed Computing.Monterey:[s.n.]，2002.

[11]KAASHOEK M F，KARGER D R. Koorde: a simple degree optimal distributed hash table[C]//Proc of the 2nd International Workshop on P2P Systems.Berkeley:[s.n.]，2003.

[12]SHEN Hai－ying， XU Cheng－zhong， CHEN Gui－h(huán)ai，et al.Cycloid: a new constant－degree and lookup efficient P2P overlay network[C]//Proc of International Parallel and Distributed Symposium. Santa Fe:[s.n.]，2004.

[13]ZHANG Hao，JIN Hai，NIE Jin－wu，et al.Dual－Chord: a more effective distribute hash table[J].Mini－Micro System，2006，27(8):1450－1454.

[14]CHEN Gan， WU Guo－xing，YANG Wang. G－Chord: an improved routing algorithm for Chord[J].Journal of Southeast University: Natural Science Edition，2007，37(1):9－12.

[15]XU Zhi－chen，ZHANG Zheng. Building low－maintenance expressways for P2P systems，HPL－2002－41[R]. Palo Alto:Hewlett－Packard Lab， 2002.

[16]謝瑤，洪佩琳，李津生.HiMCAN:一種新型的基于DHT的P2P內(nèi)容尋址網(wǎng)絡(luò)[EB/OL].(2005).http://www.stanford.edu/~yao－xie/HiMCAN.pdf.

[17]GUPTA I，BIRMAN K，LINGA P，et al. Kelips:building an efficient and stable P2P DHT through increased memory and background overhead[C]//Proc of the 2nd International Workshop on Peer－to－Peer Systems.2003.

[18]GUPTA A，LISKOV B，RODRIGUES R. One－h(huán)op lookups for peer－to－peer overlays[C]//Proc of the 9th Workshop on Hot Topics in Operation System(HOTOS IX).2003.

[19]VIAHA A C，De AMORIM M D，VINIOTIS Y，et al.Twins: a dual addressing space representation for self－organizing networks[J].IEEE Trans on Parallel Distrib Syst，2006，17(12):1468－1481.

[20]XU Jun，KUMAR A，YU Xing－xing. On the fundamental tradeoffs between routing table size and network diameter in peer－to－peer networks[C]//Procof the 22nd Annual Joint Conf of the IEEE Computer and Communications Societies. 2003.

[21]GUMMADI K，GUMMADI R，GRIBBLE S，et al .The impact of DHT routing geometry on resilience and proximity[C]//Proc of SIGCOMM.2003.

[22]LOGUINOV D，KUMAR A，RAI V，et al .Graph－theoretic analysis of structured peer－to－peer systems:routing distances and fault resilience[J]. IEEE/ACM Trans on Networking，2005，13(5):1107－1120.

[23]LI Yun－di，F(xiàn)ENG Yong. Study of data search in DHT P2P networks[J]. Application Research of Computers ，2006，23(10):226－228.

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