對(duì)等網(wǎng)絡(luò)中主流分布式哈希算法比較分析

1、本文首先從P2P的定義出發(fā)，介紹了結(jié)構(gòu)化P2P與非結(jié)構(gòu)化P2P的區(qū)別以及結(jié)構(gòu)化P2P的核心技術(shù)DHT。而后，本文深入介紹了幾種主流的DHT算法與協(xié)議并對(duì)每種協(xié)議進(jìn)行了討論。文章的最后展望DHT在未來的發(fā)展趨勢(shì)。對(duì)等網(wǎng)絡(luò)（Peer-to-Peer，簡(jiǎn)稱P2P）是目前非常熱門的應(yīng)用，自1999年以來，P2P的研究一直是國(guó)外知名學(xué)府（如美國(guó)麻省理工學(xué)院，加州大學(xué)伯克利分校和萊斯大學(xué)等）以及知名企業(yè)的研發(fā)機(jī)構(gòu)（如微軟，諾基亞的研究院）關(guān)注的重點(diǎn)。它甚至被美國(guó)財(cái)富雜志稱為改變因特網(wǎng)發(fā)展的四大新技術(shù)之一，被認(rèn)為是代表無線寬帶互聯(lián)網(wǎng)未來的關(guān)鍵技術(shù)。作為一項(xiàng)新興的技術(shù)，目前學(xué)術(shù)界對(duì)P2P在技術(shù)層面上的定義尚未

2、統(tǒng)一。KeithW.Ross（PolytechnicUniversity）和DanRubenstein（ColumbiaUniversity）在9中提到了對(duì)P2P系統(tǒng)的3個(gè)基本定義：相比中央服務(wù)器而言有明顯的自治性（Autonomy）。利用網(wǎng)絡(luò)邊緣的資源，如存儲(chǔ)/計(jì)算能力和信息資源。網(wǎng)絡(luò)邊緣的資源處在動(dòng)態(tài)的變化中（新的資源加入，已有的資源消失）。自治性的要求使得P2P系統(tǒng)不再需要特定的中央管理機(jī)制，所有節(jié)點(diǎn)之間擁有對(duì)等的關(guān)系。這一方面為系統(tǒng)帶來了自組織、容錯(cuò)性好、可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)；另一方面也提出了新的問題：如何在沒有集中管理機(jī)制的情況下實(shí)現(xiàn)系統(tǒng)的自組織和自管理？定義2，3中分布性和動(dòng)態(tài)性的特點(diǎn)

3、使得上述問題的實(shí)現(xiàn)具有更大的難度。在分布式系統(tǒng)中，過多過快的信息交互可能消耗大量的網(wǎng)絡(luò)資源；而為了實(shí)時(shí)反映系統(tǒng)的變化，又要求節(jié)點(diǎn)及時(shí)獲得更新信息，這就需要在節(jié)點(diǎn)之間進(jìn)行通信。為了解決這一對(duì)矛盾，已經(jīng)有許多P2P的框架和協(xié)議被提出來并得到了很好的應(yīng)用。結(jié)構(gòu)化與非結(jié)構(gòu)化P2P依照節(jié)點(diǎn)信息存儲(chǔ)與搜索方式的不同，諸多P2P協(xié)議可以分為2大類：結(jié)構(gòu)化（Structured）的與非結(jié)構(gòu)化（Unstructured）的系統(tǒng)。非結(jié)構(gòu)化P2P系統(tǒng)在非結(jié)構(gòu)化的系統(tǒng)中，每個(gè)節(jié)點(diǎn)存儲(chǔ)自身的信息或信息的索引（如指針和IP地址）。當(dāng)用戶需要在P2P系統(tǒng)中獲取信息時(shí)，他們預(yù)先并不知道這些信息（如某個(gè)文件）會(huì)在那個(gè)節(jié)點(diǎn)上存儲(chǔ)

4、。因此，在非結(jié)構(gòu)化P2P系統(tǒng)中，信息搜索的算法難免帶有一定的盲目性，例如最簡(jiǎn)單的泛洪式查找（類似于廣播）和擴(kuò)展環(huán)查找（從最近的n個(gè)節(jié)點(diǎn)開始，層層轉(zhuǎn)發(fā)直到找到目標(biāo)或超出了跳數(shù)的上限為止）。一些典型的應(yīng)用采用了一些優(yōu)化的辦法。如在Gnutella中，采用了等級(jí)制的組成結(jié)構(gòu)：節(jié)點(diǎn)被分成超級(jí)節(jié)點(diǎn)（SuperNode）和普通節(jié)點(diǎn)。普通節(jié)點(diǎn)必須依附于超級(jí)節(jié)點(diǎn)，每個(gè)超級(jí)節(jié)點(diǎn)作為一個(gè)獨(dú)立的域管理者，負(fù)責(zé)處理域內(nèi)的查詢操作。在查找的過程中，查詢首先在域內(nèi)進(jìn)行，失敗后才會(huì)擴(kuò)展到超級(jí)節(jié)點(diǎn)之間。非結(jié)構(gòu)化系統(tǒng)的優(yōu)點(diǎn)在于實(shí)現(xiàn)結(jié)構(gòu)簡(jiǎn)單：無須中央服務(wù)器，節(jié)點(diǎn)之間完全平等，網(wǎng)絡(luò)的層次是單一的，而且節(jié)點(diǎn)之間無需維護(hù)拓?fù)湫畔?。結(jié)構(gòu)

5、化P2P系統(tǒng)在結(jié)構(gòu)化P2P系統(tǒng)中，每個(gè)節(jié)點(diǎn)只存儲(chǔ)特定的信息或特定信息的索引。當(dāng)用戶需要在P2P系統(tǒng)中獲取信息時(shí)，他們必須知道這些信息（或索引）可能存在于那些節(jié)點(diǎn)中。由于用戶預(yù)先知道應(yīng)該搜索哪些節(jié)點(diǎn)，避免了非結(jié)構(gòu)化P2P系統(tǒng)中使用的泛洪式查找，因此提高了信息搜索的效率。但是，結(jié)構(gòu)化P2P也引入了新的問題：首先，既然信息是分布存儲(chǔ)的，那么如何將信息分布存儲(chǔ)在重疊網(wǎng)中的節(jié)點(diǎn)上？其次，由于節(jié)點(diǎn)動(dòng)態(tài)的加入和離開重疊網(wǎng)，如何將拓?fù)涞淖兏畔⑼ㄖ渌?jié)點(diǎn)？DHT的引入基本解決了上述問題，因此自從DHT協(xié)議出現(xiàn)以后，結(jié)構(gòu)化P2P的應(yīng)用得到了快速的發(fā)展。目前已經(jīng)有很多較為成熟的DHT協(xié)議被提出并且得到了應(yīng)用。其

6、中比較有代表性的有：緩沖陣列路由協(xié)議（CARP）；致性哈希；Chord；內(nèi)容尋址網(wǎng)絡(luò)；Pastry。DHT簡(jiǎn)介DHT使用分布式哈希算法來解決結(jié)構(gòu)化的分布式存儲(chǔ)問題。分布式哈希算法的核心思想是通過將存儲(chǔ)對(duì)象的特征（關(guān)鍵字）經(jīng)過哈希運(yùn)算，得到鍵值（HashKey），對(duì)象的分布存儲(chǔ)依據(jù)鍵值來進(jìn)行。具體來講，大致有以下步驟：對(duì)存儲(chǔ)對(duì)象的關(guān)鍵字進(jìn)行哈希運(yùn)算，得到鍵值。這樣就將所有的對(duì)象映射到了一個(gè)具體的數(shù)值范圍中。重疊網(wǎng)中的每個(gè)節(jié)點(diǎn)負(fù)責(zé)數(shù)值范圍中的特定段落。例如，節(jié)點(diǎn)A負(fù)責(zé)存儲(chǔ)鍵值從8000到8999的對(duì)象；而節(jié)點(diǎn)B負(fù)責(zé)70007999的對(duì)象。這樣就將對(duì)象集合分布地存儲(chǔ)在所有的節(jié)點(diǎn)中。節(jié)點(diǎn)可以直接存儲(chǔ)對(duì)

7、象本身，如文件中的一個(gè)片段；也可以存儲(chǔ)對(duì)象的索引，如該對(duì)象所在節(jié)點(diǎn)的IP地址。結(jié)構(gòu)化的分布式存儲(chǔ)問題解決后，剩下的問題就是用戶如何才能找到存儲(chǔ)著目標(biāo)信息的節(jié)點(diǎn)。在有著大量節(jié)點(diǎn)（如100萬個(gè)）的P2P系統(tǒng)中，任何節(jié)點(diǎn)都不可能擁有全部的節(jié)點(diǎn)?鍵值?內(nèi)容的對(duì)應(yīng)關(guān)系；因此用戶獲得了鍵值之后，如何找到該鍵值對(duì)應(yīng)的節(jié)點(diǎn)就被稱為DHT的路由問題。DHT協(xié)議必須定義優(yōu)化的查找（路由）算法來完成這一搜尋的工作。不同的DHT協(xié)議之間區(qū)別很大程度上就在于定義了不同的路由算法。DHT的應(yīng)用非常簡(jiǎn)潔-API簡(jiǎn)單到只有一項(xiàng)輸入和一項(xiàng)輸出：應(yīng)用層將數(shù)據(jù)對(duì)象（文件、數(shù)據(jù)塊或索引）通過哈希算法獲得鍵值，將該鍵值提交給DHT后，

8、返回結(jié)果就是鍵值所在節(jié)點(diǎn)的IP地址。圖1（來自9）顯示了這種應(yīng)用結(jié)構(gòu)：賈任節(jié)點(diǎn)鹽值重迎.網(wǎng)麗擁旺貶口圖1DHT的應(yīng)用結(jié)構(gòu)應(yīng)用程序DHT抽象屠應(yīng)月程序捺口府用程序應(yīng)用pi=rJIDHT抽隊(duì)展接口J在這樣的支持下，可以開發(fā)多種P2P的應(yīng)用程序，如網(wǎng)絡(luò)存儲(chǔ)與文件共享、即時(shí)消息、音頻/視頻等。圖2(來自9)顯示了這種應(yīng)用結(jié)構(gòu)：Nodetd1咔子聲合10233035W25M2110233031102330CH3隱由表-0-2212102101-100123310-0-31203101-32102102-0-0230102-1-13021023-0-3221023-1-00010233-00110鄰居秦合

9、13021022102002300221210222012051023314)210235120102331221023323010233232I-2-230120S-3-12032031-2-2302031-3-021022210-323302102-2-230231021-2-1213I10233c厶321O2S31-2-021130123331301233|3120320333213321圖2DHT應(yīng)用的層次主流DHT協(xié)議緩沖陣列路由協(xié)議(CARP，CacheArrayRoutingProtocol)協(xié)議簡(jiǎn)介CARP是由微軟公司的VinodValloppillil和賓西法尼亞大學(xué)的Kei

10、thW.Ross在1997年提出的。該協(xié)議可以將URL空間映射到一個(gè)僅有松散關(guān)聯(lián)關(guān)系的Webcache服務(wù)器（在協(xié)議中稱為“代理”，Proxy）陣列中。支持該協(xié)議的HTTP客戶端可以根據(jù)要訪問的URL智能選擇目標(biāo)代理。該協(xié)議解決了在代理陣列內(nèi)分布存儲(chǔ)內(nèi)容的問題，避免了內(nèi)容的重復(fù)存儲(chǔ)，提高了客戶端訪問時(shí)WebCache命中的概率。哈希算法哈希使用的關(guān)鍵字有2個(gè)，一個(gè)是代理的標(biāo)識(shí)符（每個(gè)代理均有唯一的標(biāo)識(shí)），另一個(gè)是URL本身。存儲(chǔ)內(nèi)容時(shí)，每個(gè)代理負(fù)責(zé)緩沖哈希鍵值最大的URL。這樣，當(dāng)緩沖代理陣列發(fā)生少量變化時(shí)（新的代理加入或舊的代理退出），原有的URL還有可能仍然被映射到原來的代理上，仍可以按照

11、原有的方式訪問。路由算法客戶端（HTTP瀏覽器）首先加載一個(gè)代理配置文件，該文件中存儲(chǔ)了代理的標(biāo)識(shí)符和IP地址等用于哈希的關(guān)鍵參數(shù)。瀏覽器在訪問網(wǎng)頁(yè)時(shí)，可以根據(jù)URL和代理標(biāo)識(shí)獲得代理的位置信息（IP地址），從而可以直接訪問緩沖代理中的頁(yè)面。討論CARP的哈希過程比較簡(jiǎn)單，路由查找更是簡(jiǎn)單到至多只有一跳（0（1）。但是CARP在P2P的應(yīng)用環(huán)境中有一些致命的缺陷：每個(gè)節(jié)點(diǎn)必須知道其它所有節(jié)點(diǎn)的信息。在大規(guī)模的重疊網(wǎng)環(huán)境中，由于可能存在大量的（數(shù)百萬）節(jié)點(diǎn)，加之節(jié)點(diǎn)都是動(dòng)態(tài)加入和退出網(wǎng)絡(luò)，因此這一條件幾乎不可能滿足。在緩沖陣列發(fā)生較大變化時(shí)（這在P2P網(wǎng)絡(luò)中非常常見）,原有的URL和代理之間的對(duì)

12、應(yīng)關(guān)系可能發(fā)生改變，從而使得原有的配置文件失效。一致性哈希（ConsistentHash）協(xié)議簡(jiǎn)介一致性哈希算法在1997年由麻省理工學(xué)院提出（參見0）,設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)（Hotpot）問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來的問題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。哈希算法一致性哈希提出了在動(dòng)態(tài)變化的Cache環(huán)境中，哈希算法應(yīng)該滿足的4個(gè)適應(yīng)條件：平衡性（Balance）平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。單調(diào)性(Monotonicity)單調(diào)性

13、是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。簡(jiǎn)單的哈希算法往往不能滿足單調(diào)性的要求，如最簡(jiǎn)單的線性哈希：xax+bmod（P）在上式中，P表示全部緩沖的大小。不難看出，當(dāng)緩沖大小發(fā)生變化時(shí)（從P1到P2），原來所有的哈希結(jié)果均會(huì)發(fā)生變化，從而不滿足單調(diào)性的要求。哈希結(jié)果的變化意味著當(dāng)緩沖空間發(fā)生變化時(shí)，所有的映射關(guān)系需要在系統(tǒng)內(nèi)全部更新。而在P2P系統(tǒng)內(nèi)，緩沖的變化等價(jià)于Peer加入或退出系統(tǒng)，這一情況在P2P系統(tǒng)中會(huì)頻繁發(fā)生，因此會(huì)帶來極大計(jì)算和傳輸負(fù)荷。

14、單調(diào)性就是要求哈希算法能夠避免這一情況的發(fā)生。分散性（Spread）在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時(shí)，由于不同終端所見的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應(yīng)該避免的，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不同緩沖中去，降低了系統(tǒng)存儲(chǔ)的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。負(fù)載（Load）負(fù)載問題實(shí)際上是從另一個(gè)角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩

15、沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。從表面上看，一致性哈希針對(duì)的是分布式緩沖的問題，但是如果將緩沖看作P2P系統(tǒng)中的Peer，將映射的內(nèi)容看作各種共享的資源（數(shù)據(jù)，文件，媒體流等），就會(huì)發(fā)現(xiàn)兩者實(shí)際上是在描述同一問題。路由算法在一致性哈希算法中，每個(gè)節(jié)點(diǎn)（對(duì)應(yīng)P2P系統(tǒng)中的Peer）都有隨機(jī)分配的ID。在將內(nèi)容映射到節(jié)點(diǎn)時(shí)，使用內(nèi)容的關(guān)鍵字和節(jié)點(diǎn)的ID進(jìn)行一致性哈希運(yùn)算并獲得鍵值。一致性哈希要求鍵值和節(jié)點(diǎn)ID處于同一值域。最簡(jiǎn)單的鍵值和ID可以是一維的，比如從0000到9999

16、的整數(shù)集合。根據(jù)鍵值存儲(chǔ)內(nèi)容時(shí)，內(nèi)容將被存儲(chǔ)到具有與其鍵值最接近的ID的節(jié)點(diǎn)上。例如鍵值為1001的內(nèi)容，系統(tǒng)中有ID為1000，1010，1100的節(jié)點(diǎn)，該內(nèi)容將被映射到1000節(jié)點(diǎn)。為了構(gòu)建查詢所需的路由，一致性哈希要求每個(gè)節(jié)點(diǎn)存儲(chǔ)其上行節(jié)點(diǎn)（ID值大于自身的節(jié)點(diǎn)中最小的）和下行節(jié)點(diǎn)（ID值小于自身的節(jié)點(diǎn)中最大的）的位置信息（IP地址）。當(dāng)節(jié)點(diǎn)需要查找內(nèi)容時(shí)，就可以根據(jù)內(nèi)容的鍵值決定向上行或下行節(jié)點(diǎn)發(fā)起查詢請(qǐng)求。收到查詢請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自己擁有被請(qǐng)求的目標(biāo)，可以直接向發(fā)起查詢請(qǐng)求的節(jié)點(diǎn)返回確認(rèn)；如果發(fā)現(xiàn)不屬于自身的范圍，可以轉(zhuǎn)發(fā)請(qǐng)求到自己的上行/下行節(jié)點(diǎn)。為了維護(hù)上述路由信息，在節(jié)點(diǎn)加入

17、/退出系統(tǒng)時(shí)，相鄰的節(jié)點(diǎn)必須及時(shí)更新路由信息。這就要求節(jié)點(diǎn)不僅存儲(chǔ)直接相連的下行節(jié)點(diǎn)位置信息，還要知道一定深度(n跳)的間接下行節(jié)點(diǎn)信息，并且動(dòng)態(tài)地維護(hù)節(jié)點(diǎn)列表。當(dāng)節(jié)點(diǎn)退出系統(tǒng)時(shí)，它的上行節(jié)點(diǎn)將嘗試直接連接到最近的下行節(jié)點(diǎn)，連接成功后，從新的下行節(jié)點(diǎn)獲得下行節(jié)點(diǎn)列表并更新自身的節(jié)點(diǎn)列表。同樣的，當(dāng)新的節(jié)點(diǎn)加入到系統(tǒng)中時(shí)，首先根據(jù)自身的ID找到下行節(jié)點(diǎn)并獲得下行節(jié)點(diǎn)列表，然后要求上行節(jié)點(diǎn)修改其下行節(jié)點(diǎn)列表，這樣就恢復(fù)了路由關(guān)系。討論一致性哈?；窘鉀Q了在P2P環(huán)境中最為關(guān)鍵的問題一一如何在動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯?chǔ)和路由。每個(gè)節(jié)點(diǎn)僅需維護(hù)少量相鄰節(jié)點(diǎn)的信息，并且在節(jié)點(diǎn)加入/退出系統(tǒng)時(shí)，僅有相關(guān)的少

18、量節(jié)點(diǎn)參與到拓?fù)涞木S護(hù)中。所有這一切使得一致性哈希成為第一個(gè)實(shí)用的DHT算法。但是一致性哈希的路由算法尚有不足之處。在查詢過程中，查詢消息要經(jīng)過O(N)步(0(N)表示與N成正比關(guān)系，N代表系統(tǒng)內(nèi)的節(jié)點(diǎn)總數(shù))才能到達(dá)被查詢的節(jié)點(diǎn)。不難想象，當(dāng)系統(tǒng)規(guī)模非常大時(shí)，節(jié)點(diǎn)數(shù)量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。換個(gè)角度來看，即使用戶能夠忍受漫長(zhǎng)的時(shí)延，查詢過程中產(chǎn)生的大量消息也會(huì)給網(wǎng)絡(luò)帶來不必要的負(fù)荷。下文中討論的幾種DHT協(xié)議都對(duì)路由做出了優(yōu)化，提出了各自的算法。Chord協(xié)議Chord在2001年由麻省理工學(xué)院提出(參見0),其核心思想就是要解決在P2P應(yīng)用中遇到的基本問題：如何在

19、P2P網(wǎng)絡(luò)中找到存有特定數(shù)據(jù)的節(jié)點(diǎn)。與前兩種協(xié)議不同，Chord專門為P2P應(yīng)用設(shè)計(jì)，因此考慮了在P2P應(yīng)用中可能遇到的特殊問題，這些內(nèi)容將在路由的部分進(jìn)行討論。哈希算法Chord使用一致性哈希作為哈希算法。在一致性哈希協(xié)議中并沒有定義具體的算法，在Chord協(xié)議中將其規(guī)定為SHA-1。路由算法Chord在一致性哈希的基礎(chǔ)上提供了優(yōu)化的路由算法：在Chord中，每個(gè)節(jié)點(diǎn)同樣需要存儲(chǔ)m個(gè)其他節(jié)點(diǎn)的信息，這些信息的集合被稱為查詢表(FingerTable)。一致性哈希中的節(jié)點(diǎn)同樣具有這樣的表格，但在Chord中，表格中的節(jié)點(diǎn)不再是直接相鄰的節(jié)點(diǎn)，它們的間距(ID間隔)將成2i的關(guān)系排列(i表示表中

20、的數(shù)組下標(biāo))。這樣形成的節(jié)點(diǎn)之間路由關(guān)系實(shí)際上就是折半查找算法需要的排列關(guān)系。在查詢的過程中，查詢節(jié)點(diǎn)將請(qǐng)求發(fā)送到與鍵值最接近的節(jié)點(diǎn)上。收到查詢請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自身存儲(chǔ)了被查詢的信息，可以直接回應(yīng)查詢節(jié)點(diǎn)(這與一致性哈希完全相同)；如果被查詢的信息不在本地，就根據(jù)查詢表將請(qǐng)求轉(zhuǎn)發(fā)到與鍵值最接近的節(jié)點(diǎn)上。這樣的過程一直持續(xù)到找到相應(yīng)的節(jié)點(diǎn)為止。不難看出，查詢過程實(shí)際上就是折半查找的過程。經(jīng)過Chord的優(yōu)化后，查詢需要的跳數(shù)由0(N)減少到O(log(N)。這樣即使在大規(guī)模的P2P網(wǎng)絡(luò)中(例如N=100,000,000)，查詢的跳數(shù)也僅為O(8),每個(gè)節(jié)點(diǎn)僅需存儲(chǔ)27個(gè)(log21000000

21、00)其他節(jié)點(diǎn)的信息。Chord還考慮到多個(gè)節(jié)點(diǎn)同時(shí)加入系統(tǒng)的情況并對(duì)節(jié)點(diǎn)加入/退出算法作了優(yōu)化。討論Chord算法本身具有如下優(yōu)點(diǎn)：負(fù)載平衡這一優(yōu)點(diǎn)來自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的節(jié)點(diǎn)以同等的概率分擔(dān)系統(tǒng)負(fù)荷從而可以避免某些節(jié)點(diǎn)負(fù)載過大的情況。分布性Chord是純分布式系統(tǒng)，節(jié)點(diǎn)之間完全平等并完成同樣的工作。這使得Chord具有很高的魯棒性，可以抵御DoS攻擊?？蓴U(kuò)展性Chord協(xié)議的開銷隨著系統(tǒng)規(guī)模(結(jié)點(diǎn)總數(shù)N)的增加而按照O(logN)的比例增加。因此Chord可以用于大規(guī)模的系統(tǒng)?？捎眯訡hord協(xié)議要求節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)的變化動(dòng)態(tài)的更新查詢表，因此能夠及時(shí)恢復(fù)路由關(guān)

22、系，使得查詢可以可靠地進(jìn)行。命名的靈活性Chord并未限制查詢內(nèi)容的結(jié)構(gòu)，因此應(yīng)用層可以靈活的將內(nèi)容映射到鍵值空間而不受協(xié)議的限制。Chord在CFS系統(tǒng)中得到了應(yīng)用，具體的介紹可參見8內(nèi)容尋址網(wǎng)絡(luò)(Content-AddressableNetwork，CAN)CAN在2001年由加州大學(xué)伯克利分校提出(參見)。與Chord一樣，CAN也是DHT的一個(gè)變種。哈希算法CAN的哈希算法與一致性哈希有所不同。Chord中，哈希得到的鍵值總是一維的，而在CAN中，哈希的結(jié)果由d維的笛卡爾空間來表示。d是一個(gè)由系統(tǒng)規(guī)模決定的常量。路由算法CAN的路由查詢將在d維笛卡爾空間中進(jìn)行。在CAN中，每個(gè)節(jié)點(diǎn)自身

23、的ID經(jīng)由哈希后得到的d維向量。經(jīng)過這樣的映射后，整個(gè)P2P系統(tǒng)將被映射到一個(gè)d維笛卡爾空間中，每個(gè)節(jié)點(diǎn)的位置由其自身ID決定。CAN對(duì)鄰居節(jié)點(diǎn)的定義并不要求成2i的關(guān)系排列，而是改為用在笛卡爾空間上相鄰來表示：在d維笛卡爾空間中，2個(gè)節(jié)點(diǎn)的d維坐標(biāo)中有d-1維是相等的，剩余的一維是相鄰的節(jié)點(diǎn)稱之為相鄰節(jié)點(diǎn)。CAN中的節(jié)點(diǎn)僅存儲(chǔ)相鄰節(jié)點(diǎn)表。由于在d維的空間中最多有2d個(gè)相鄰的節(jié)點(diǎn)，因此節(jié)點(diǎn)的相鄰節(jié)點(diǎn)表最多有2d個(gè)表項(xiàng)。在查詢的過程中，查詢節(jié)點(diǎn)首先計(jì)算被查詢內(nèi)容的鍵值(d維向量)，然后在節(jié)點(diǎn)列表中查找在笛卡爾空間中與該鍵值最為接近的相鄰節(jié)點(diǎn)，找到后向該節(jié)點(diǎn)發(fā)送查詢請(qǐng)求(這一策略被稱為貪婪策略)。

24、查詢請(qǐng)求中將攜帶被查詢內(nèi)容的鍵值。收到查詢請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自身存儲(chǔ)了被查詢的信息，可以直接回應(yīng)查詢節(jié)點(diǎn)(這與一致性哈希完全相同)；如果被查詢的信息不在本地，就根據(jù)相鄰節(jié)點(diǎn)表將請(qǐng)求轉(zhuǎn)發(fā)到與鍵值最接近的節(jié)點(diǎn)上。這樣的過程一直持續(xù)到找到相應(yīng)的節(jié)點(diǎn)為止。在查詢過程中，被查詢節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的笛卡爾空間距離單調(diào)地減少。如果查詢節(jié)點(diǎn)或轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)現(xiàn)鄰居節(jié)點(diǎn)表中無法找到可用的下一跳節(jié)點(diǎn)，則采用非結(jié)構(gòu)化P2P常用的擴(kuò)展環(huán)搜索(ExpandingRingSearch，使用無狀態(tài)，受控的泛洪算法在重疊網(wǎng)中搜索)以找到合適的(符合貪婪策略)下一節(jié)點(diǎn)。經(jīng)過CAN的優(yōu)化后，查詢需要的跳數(shù)由0(N)減少到均值為(d/4)(

25、n1/d)的隨機(jī)制，考慮到d為常數(shù)，這一值可以表示為O(n1/d)或O(dnl/d)。討論CAN和Chord的主要區(qū)別在于路由算法不同。相比之下，在節(jié)點(diǎn)數(shù)量非常大時(shí)，CAN的平均查詢跳數(shù)要比Chord增加得更快。而且CAN查詢過程中需要的運(yùn)算量也要高于Chord。但CAN使用的d為預(yù)先設(shè)置的常量，因此并不假設(shè)系統(tǒng)節(jié)點(diǎn)數(shù)量。在節(jié)點(diǎn)總數(shù)動(dòng)態(tài)變化范圍很大的系統(tǒng)中，CAN的相鄰節(jié)點(diǎn)表結(jié)構(gòu)保持穩(wěn)定，這在P2P的應(yīng)用中也是很重要的優(yōu)點(diǎn)。PastryPastry在2001年由位于英國(guó)劍橋的微軟研究院和萊斯(Rice)大學(xué)提出(參見4)。Pastry也是DHT的一個(gè)變種。哈希算法Pastry使用一致性哈希作為

26、哈希算法。哈希所得的鍵值為一維(實(shí)際上使用的是128bit的整數(shù)空間)。Pastry也沒有規(guī)定具體應(yīng)該采用何種哈希算法。路由算法在Pastry協(xié)議中，每個(gè)節(jié)點(diǎn)都擁有一個(gè)128bit的標(biāo)識(shí)(NodeId)。為了保證NodeID的唯一性，一般由節(jié)點(diǎn)的網(wǎng)絡(luò)標(biāo)識(shí)(如IP地址)經(jīng)過哈希得到。Pastry中的每個(gè)節(jié)點(diǎn)擁有一個(gè)路由表R(Routingtable),個(gè)鄰居節(jié)點(diǎn)集“(NeighborhoodSet)和一個(gè)葉子節(jié)點(diǎn)集合L(Leafset)，它們一起構(gòu)成了節(jié)點(diǎn)的狀態(tài)表。路由表R共有l(wèi)ogBN（B=2b為系統(tǒng)參數(shù)，典型值為16,N表示系統(tǒng)的節(jié)點(diǎn)總數(shù)）行，每行包括B-1個(gè)表項(xiàng)，每個(gè)表項(xiàng)記錄了一個(gè)鄰居節(jié)點(diǎn)

27、的信息（節(jié)點(diǎn)標(biāo)識(shí)、IP地址、當(dāng)前狀態(tài)等）。這樣就形成了擁有（B-l）logBN個(gè)條目的二維表格。路由表第n行的表項(xiàng)所記錄的鄰居節(jié)點(diǎn)的NodeID前n個(gè)數(shù)位和當(dāng)前節(jié)點(diǎn)的前n個(gè)數(shù)位相同，而第n+1個(gè)數(shù)位則分別取從0到B-1的值（除了與當(dāng)前節(jié)點(diǎn)第n+1數(shù)位的值）。這樣形成的路由表很類似IP路由中最長(zhǎng)掩碼匹配的算法。參數(shù)b（或B）大小非常關(guān)鍵：B過大則節(jié)點(diǎn)需要維護(hù)很大的路由表，可能超出節(jié)點(diǎn)的負(fù)載能力，但路由表大些可以存儲(chǔ)更多的鄰居節(jié)點(diǎn)，在轉(zhuǎn)發(fā)時(shí)更為精確。平均每次路由查找需要的跳數(shù)在Pastry中計(jì)算的結(jié)果是logBN，因此B的選擇反映了路由表大小和路由效率之間的折衷。葉子節(jié)點(diǎn)集合L中存放的是在鍵值空間

28、中與當(dāng)前節(jié)點(diǎn)距離最近的ILI個(gè)節(jié)點(diǎn)的信息，其中一半節(jié)點(diǎn)標(biāo)識(shí)大于當(dāng)前節(jié)點(diǎn)，另一半節(jié)點(diǎn)標(biāo)識(shí)小于當(dāng)前節(jié)點(diǎn)。|L|的典型值為2b或者2*2b。鄰居節(jié)點(diǎn)集合M中存放的是在真實(shí)網(wǎng)絡(luò)中與當(dāng)前節(jié)點(diǎn)“距離”最近的|M|個(gè)節(jié)點(diǎn)的信息?！熬嚯x”的定義在Pastry中非常類似IP路由協(xié)議中對(duì)距離的定義，也就是考慮到轉(zhuǎn)發(fā)跳數(shù)、傳輸路徑帶寬、QoS等綜合因素后所得的轉(zhuǎn)發(fā)開銷（可以參見OSPF等路由協(xié)議）。Pastry并未提供距離信息的獲取方法，而是假設(shè)應(yīng)用層可以通過某種手段（人工配制或自動(dòng)協(xié)商）得到信息并配置鄰居節(jié)點(diǎn)集合。|M|的典型值為2b或者2*2b。圖3給出了一個(gè)Pastry節(jié)點(diǎn)狀態(tài)表的例子，該圖來源于4。在節(jié)點(diǎn)狀

29、態(tài)表中，節(jié)點(diǎn)本身的ID為10233102。葉子集合中有8項(xiàng)，每一項(xiàng)都代表一個(gè)當(dāng)前節(jié)點(diǎn)已知的其他節(jié)點(diǎn)的信息。路由表共有4*8項(xiàng)，可以看出由上至下節(jié)點(diǎn)ID重合的位數(shù)（前綴）不斷增加。鄰居集合中的節(jié)點(diǎn)ID由于來源于應(yīng)用層，一般沒有規(guī)律性可循。Pastry的路由過程如下：首先，路由查詢消息中將攜帶被查詢對(duì)象ID（ObjectId）,又稱消息鍵值。當(dāng)收到路由消息時(shí)，節(jié)點(diǎn)首先檢查消息鍵值是否落在葉子節(jié)點(diǎn)集合的范圍內(nèi)。如果是，則直接把消息轉(zhuǎn)發(fā)給葉子節(jié)點(diǎn)集合中節(jié)點(diǎn)標(biāo)識(shí)和消息鍵值最接近的節(jié)點(diǎn)；否則就從路由表中根據(jù)最長(zhǎng)前綴優(yōu)先的原則選擇一個(gè)節(jié)點(diǎn)作為路由目標(biāo)，轉(zhuǎn)發(fā)路由消息。如果不存在這樣的節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)將會(huì)從其維護(hù)

30、的所有鄰居節(jié)點(diǎn)集合（包括路由表葉子集合及鄰居集合中的節(jié)點(diǎn)）中選擇一個(gè)距離消息鍵值最近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)目標(biāo)。從上述過程中可以看出，每一步路由和上一步相比都更靠近目標(biāo)節(jié)點(diǎn)，因此這個(gè)過程是收斂的。如果路由表不為空，每步路由至少能夠增加一個(gè)前綴匹配數(shù)位，因此在路由表始終有效時(shí)，路由的步數(shù)至多為logBN。討論P(yáng)astry的路由利用了成熟的最大掩碼匹配算法，因此實(shí)現(xiàn)時(shí)可以利用很多現(xiàn)成的軟件算法和硬件框架，可以獲得很好的效率。與Chord和CAN相比，Pastry引入了葉子節(jié)點(diǎn)和鄰居節(jié)點(diǎn)集合的概念。在應(yīng)用層能夠及時(shí)準(zhǔn)確地獲得這兩個(gè)集合的節(jié)點(diǎn)信息時(shí)，可以大大加快路由查找的速度，同時(shí)降低因路由引起的網(wǎng)絡(luò)傳輸開銷

31、；不過在動(dòng)態(tài)變化的P2P網(wǎng)絡(luò)中如何理想地做到這一點(diǎn)的確有很大的難度。Pastry的典型應(yīng)用包括PAST（參見5）和SCRIBE（參見7）。趨勢(shì)分析目前DHT算法的發(fā)展方向非常多，不斷有新的改進(jìn)算法被提出來。就筆者目前了解到的信息而言，至少有以下一些方向：接近性(Proximity)文中提到的DHT算法中，除了Pasrty以外，均未考慮重疊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與真實(shí)的IP網(wǎng)絡(luò)之間的重合關(guān)系。節(jié)點(diǎn)之間進(jìn)行對(duì)等通信時(shí)，不會(huì)考慮優(yōu)先選取距離自己最近的節(jié)點(diǎn)。這樣就使得最終形成的重疊網(wǎng)結(jié)構(gòu)混亂，效率低下。因此如何讓節(jié)點(diǎn)獲得并利用接近性信息就非常重要。結(jié)構(gòu)化目前基于DHT的應(yīng)用尚未大規(guī)模展開，很多工程上的細(xì)節(jié)問題尚

32、待解決。例如：目前有很多種類的P2P應(yīng)用，如文件存儲(chǔ)和共享、電子郵件、流媒體等。這些應(yīng)用在處理P2P路由算法、拓?fù)渚S護(hù)和信息檢索上使用的方法均有很大差別，導(dǎo)致即使是同類的應(yīng)用也無法實(shí)現(xiàn)互通。如何為各種P2P的應(yīng)用抽象出一個(gè)通用的層次，也是目前研究的熱點(diǎn)問題之一。信息查詢基于分布式哈希表的查詢是一種單關(guān)鍵字的精確匹配，盡管相對(duì)于非結(jié)構(gòu)化系統(tǒng)它使得系統(tǒng)資源可被確定性地查詢到，但它也極大地限制了查詢的應(yīng)用范圍。目前有許多改進(jìn)的結(jié)構(gòu)化查詢算法已經(jīng)被提出來。參考文獻(xiàn)DavidKarger,EricLehman,TomLeighton,MatthewLevine,DanielLewin,RinaPanig

33、rahyConsistentHashingandRandomTrees:DistributedCachingProtocolsforRelievingHotSpotsontheWorldWideWeb.InProceedingsofthe29thAnnualACMSym-posiumonTheoryofComputing(ElPaso,TX,May1997),pp.654-663.IonStoica,RobertMorris,DavidKarger,M.FransKaashoek,HariBalakrishnan_Chord:AScalablePeertopeerLookupServicefo

34、rInternetApplicationsSIGCOMM01,August2731,2001,SanDiego,California,USA.SylviaRatnasamy,PaulFrancis,MarkHandley,RichardKarp,ScottShenkerAScalableContent-AddressableNetworkSIGCOMM01,August27-31,2001,SanDiego,California,USA.AntonyRowstron1andPeterDruschelPastry:Scalable,decentralizedobjectlocationandroutingforlarge-scalepeer-to-peersystemsAppearsinProc