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

1、對等網(wǎng)絡(luò)(P2P)中主流分布式哈希算法比較分析關(guān)鍵詞:P2P,對等網(wǎng)絡(luò),Peer-to-Peer,摘要：本文首先從P2P的定義出發(fā)，介紹了結(jié)構(gòu)化P2P與非結(jié)構(gòu)化P2P的區(qū)別以 及結(jié)構(gòu)化P2P的核心技術(shù)DHT而后，本文深入介紹了幾種主流的 DHT算法與協(xié) 議并對每種協(xié)議進行了討論。文章的最后展望了 DHT在未來的發(fā)展趨勢。對等網(wǎng)絡(luò)(Peer-to-Peer，簡稱 P2P)是目前非常熱門的應(yīng)用，自1999年以來，P 2P的研究一直是國外知名學(xué)府(如美國麻省理工學(xué)院，加州大學(xué)伯克利分校和萊斯大學(xué)等)以及知名企業(yè)的研發(fā)機構(gòu)(如微軟，諾基亞的研究院)關(guān)注的重點。它 甚至被美國財富雜志稱為改變因特網(wǎng)發(fā)展的

2、四大新技術(shù)之一， 被認(rèn)為是代表 無線寬帶互聯(lián)網(wǎng)未來的關(guān)鍵技術(shù)。作為一項新興的技術(shù)，目前學(xué)術(shù)界對P2P在技術(shù)層面上的定義尚未統(tǒng)一。KeithW. Ross (Polytechnic University)和 Dan Rubenstein(Columbia University)在9中提到了對P2P系統(tǒng)的3個基本定義：相比中央服務(wù)器而言有明顯的自治性(Auto nomy)。利用網(wǎng)絡(luò)邊緣的資源，如存儲/計算能力和信息資源。網(wǎng)絡(luò)邊緣的資源處在動態(tài)的變化中(新的資源加入，已有的資源消失)。自治性的要求使得P2P系統(tǒng)不再需要特定的中央管理機制，所有節(jié)點之間擁有對 等的關(guān)系。這一方面為系統(tǒng)帶來了自組織、容錯

3、性好、可擴展性強等優(yōu)點；另一 方面也提出了新的問題：如何在沒有集中管理機制的情況下實現(xiàn)系統(tǒng)的自組織和 自管理？定義 2，3中分布性和動態(tài)性的特點使得上述問題的實現(xiàn)具有更大的難度。在分 布式系統(tǒng)中，過多過快的信息交互可能消耗大量的網(wǎng)絡(luò)資源； 而為了實時反映系 統(tǒng)的變化，又要求節(jié)點及時獲得更新信息，這就需要在節(jié)點之間進行通信。為了解決這一對矛盾，已經(jīng)有許多P2P的框架和協(xié)議被提出來并得到了很好的應(yīng) 用。結(jié)構(gòu)化與非結(jié)構(gòu)化 P2P依照節(jié)點信息存儲與搜索方式的不同，諸多P2P協(xié)議可以分為2大類：結(jié)構(gòu)化(S tructured)的與非結(jié)構(gòu)化(Unstructured)的系統(tǒng)。非結(jié)構(gòu)化P2P系統(tǒng)在非結(jié)構(gòu)化的

4、系統(tǒng)中，每個節(jié)點存儲自身的信息或信息的索引 （ 如指針和 IP 地 址）。當(dāng)用戶需要在P2P系統(tǒng)中獲取信息時，他們預(yù)先并不知道這些信息（如某個 文件）會在那個節(jié)點上存儲。因此，在非結(jié)構(gòu)化 P2P系統(tǒng)中，信息搜索的算法難 免帶有一定的盲目性，例如最簡單的泛洪式查找（類似于廣播）和擴展環(huán)查找（從 最近的 n 個節(jié)點開始，層層轉(zhuǎn)發(fā)直到找到目標(biāo)或超出了跳數(shù)的上限為止 ）。一些典型的應(yīng)用采用了一些優(yōu)化的辦法。如在 Gnutella 中，采用了等級制的組 成結(jié)構(gòu)：節(jié)點被分成超級節(jié)點（Super Node）和普通節(jié)點。 普通節(jié)點必須依附于超 級節(jié)點， 每個超級節(jié)點作為一個獨立的域管理者， 負(fù)責(zé)處理域內(nèi)的查詢

5、操作。 在 查找的過程中，查詢首先在域內(nèi)進行，失敗后才會擴展到超級節(jié)點之間。非結(jié)構(gòu)化系統(tǒng)的優(yōu)點在于實現(xiàn)結(jié)構(gòu)簡單：無須中央服務(wù)器，節(jié)點之間完全平等， 網(wǎng)絡(luò)的層次是單一的，而且節(jié)點之間無需維護拓?fù)湫畔?。結(jié)構(gòu)化P2P系統(tǒng)在結(jié)構(gòu)化P2P系統(tǒng)中，每個節(jié)點只存儲特定的信息或特定信息的索引。 當(dāng)用戶需 要在P2P系統(tǒng)中獲取信息時，他們必須知道這些信息（或索引）可能存在于那些節(jié) 點中。由于用戶預(yù)先知道應(yīng)該搜索哪些節(jié)點， 避免了非結(jié)構(gòu)化P2P系統(tǒng)中使用的 泛洪式查找，因此提高了信息搜索的效率。但是，結(jié)構(gòu)化P2P也引入了新的問題：首先，既然信息是分布存儲的， 那么如何將信息分布存儲在重疊網(wǎng)中的節(jié)點上？ 其次，由于

6、節(jié)點動態(tài)的加入和離開重疊網(wǎng)，如何將拓?fù)涞淖兏畔⑼ㄖ渌?jié)點？DHT勺引入基本解決了上述問題，因此自從 DHT協(xié)議出現(xiàn)以后，結(jié)構(gòu)化P2P的應(yīng) 用得到了快速的發(fā)展。目前已經(jīng)有很多較為成熟的 DHT*議被提出并且得到了應(yīng) 用。其中比較有代表性的有：緩沖陣列路由協(xié)議（CARP） 一致性哈希；Chord; 內(nèi)容尋址網(wǎng)絡(luò)； Pastry 。DHT簡介DHT使用分布式哈希算法來解決結(jié)構(gòu)化的分布式存儲問題。分布式哈希算法的核 心思想是通過將存儲對象的特征（關(guān)鍵字）經(jīng)過哈希運算，得到鍵值（Hash Key）， 對象的分布存儲依據(jù)鍵值來進行。具體來講，大致有以下步驟：對存儲對象的關(guān)鍵字進行哈希運算， 得到鍵值。

7、 這樣就將所有的對象映射到了一 個具體的數(shù)值范圍中。重疊網(wǎng)中的每個節(jié)點負(fù)責(zé)數(shù)值范圍中的特定段落。 例如，節(jié)點A負(fù)責(zé)存儲鍵值從 8000到8999的對象；而節(jié)點B負(fù)責(zé)70007999的對象。這樣就將對象集合分布 地存儲在所有的節(jié)點中。節(jié)點可以直接存儲對象本身，如文件中的一個片段；也可以存儲對象的索引，如 該對象所在節(jié)點的IP地址。結(jié)構(gòu)化的分布式存儲問題解決后，剩下的問題就是用戶如何才能找到存儲著目標(biāo) 信息的節(jié)點。在有著大量節(jié)點（如100萬個）的P2P系統(tǒng)中，任何節(jié)點都不可能擁 有全部的節(jié)點?鍵值?內(nèi)容的對應(yīng)關(guān)系； 因此用戶獲得了鍵值之后，如何找到該鍵 值對應(yīng)的節(jié)點就被稱為DHT勺路由問題。DHT

8、協(xié)議必須定義優(yōu)化的查找（路由）算 法來完成這一搜尋的工作。不同的DHT*議之間區(qū)別很大程度上就在于定義了不 同的路由算法。DHT勺應(yīng)用非常簡潔-API 簡單到只有一項輸入和一項輸出：應(yīng)用層將數(shù)據(jù)對象（文件、數(shù)據(jù)塊或索引）通過哈希算法獲得鍵值， 將該鍵值提交 給DHT后，返回結(jié)果就是鍵值所在節(jié)點的IP地址。圖1（來自9）顯示了這種應(yīng) 用結(jié)構(gòu)：在這樣的支持下，可以開發(fā)多種P2P的應(yīng)用程序，如網(wǎng)絡(luò)存儲與文件共享、即時 消息、音頻/視頻等。圖2（來自9）顯示了這種應(yīng)用結(jié)構(gòu)：Nodeld 10233102葉子集合校天110233033102330211023312010233122|1023300110

9、2330001023323010233232路由表-0-2212102-2-2301203-3-1203203r s1-1-3012331-2-2302031-3-02102210-0-3120310-1-32102210-3-23302102-04)230102-1-1302102-2-23023I1023-0-3221023-1-0001023-2-121 I31102330-01110233-2-32o102331-2-02鄰居集合130210221020023011301233313012330221210222301203 13120320333213321圖2 DHT應(yīng)用的層次主流

10、DHT協(xié)議緩沖陣列路由協(xié)議（CARP Cache Array Routing Protocol）協(xié)議簡介CARPI由微軟公司的 Vi nod Valloppillil和賓西法尼亞大學(xué)的 Keith W. Ross在1997年提出的。該協(xié)議可以將URL空間映射到一個僅有松散關(guān)聯(lián)關(guān)系的 Web cache服務(wù)器（在協(xié)議中稱為“代理”，Proxy）陣列中。支持該協(xié)議的HTTP客戶端可以根據(jù)要訪問的URL智能選擇目標(biāo)代理。該協(xié)議解決了在代理陣列內(nèi)分布存 儲內(nèi)容的問題，避免了內(nèi)容的重復(fù)存儲，提高了客戶端訪問時 Web Cache命中的 概率。哈希算法哈希使用的關(guān)鍵字有2個，一個是代理的標(biāo)識符（每個代理均

11、有唯一的標(biāo)識），另一個是URL本身。存儲內(nèi)容時，每個代理負(fù)責(zé)緩沖哈希鍵值最大的URL這樣，當(dāng)緩沖代理陣列發(fā)生少量變化時（新的代理加入或舊的代理退出），原有的URL還有可能仍然被映射到原來的代理上，仍可以按照原有的方式訪問。路由算法客戶端（HTTP瀏覽器）首先加載一個代理配置文件，該文件中存儲了代理的標(biāo)識 符和IP地址等用于哈希的關(guān)鍵參數(shù)。瀏覽器在訪問網(wǎng)頁時，可以根據(jù)URL和代理標(biāo)識獲得代理的位置信息（IP 地址），從而可以直接訪問緩沖代理中的頁面。討論CARP勺哈希過程比較簡單，路由查找更是簡單到至多只有一跳(0(1)。但是 CA RP在P2P的應(yīng)用環(huán)境中有一些致命的缺陷：每個節(jié)點必須知道其它

12、所有節(jié)點勺信息。 在大規(guī)模勺重疊網(wǎng)環(huán)境中， 由于可能存 在大量的(數(shù)百萬)節(jié)點， 加之節(jié)點都是動態(tài)加入和退出網(wǎng)絡(luò)， 因此這一條件幾乎 不可能滿足。在緩沖陣列發(fā)生較大變化時(這在 P2P網(wǎng)絡(luò)中非常常見)，原有的URL和代理之間 的對應(yīng)關(guān)系可能發(fā)生改變，從而使得原有的配置文件失效。一致性哈希(Con siste nt Hash)協(xié)議簡介一致性哈希算法在 1 997年由麻省理工學(xué)院提出(參見 0)，設(shè)計目標(biāo)是為了解決 因特網(wǎng)中的熱點(Hot pot)問題，初衷和 CAR葉分類似。一致性哈希修正了 CAR P使用的簡單哈希算法帶來的問題，使得 DHT可以在P2P環(huán)境中真正得到應(yīng)用。哈希算法一致性哈希提

13、出了在動態(tài)變化的 Cache環(huán)境中，哈希算法應(yīng)該滿足的4個適應(yīng)條件：平衡性(Bala nee)平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去， 這樣可以使得所有的 緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。單調(diào)性(Mo noton icity)單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中， 又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖 中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。簡單的哈希算法往往不能滿足單調(diào)性的要求，如最簡單的線性哈希：x ax + b mod (P)在上式中，P表示全部緩沖的大小。不難看出，當(dāng)緩沖大小發(fā)生變

14、化時(從P1到P2)，原來所有的哈希結(jié)果均會發(fā)生變化，從而不滿足單調(diào)性的要求。哈希結(jié)果的變化意味著當(dāng)緩沖空間發(fā)生變化時， 所有的映射關(guān)系需要在系統(tǒng)內(nèi)全 部更新。而在P2P系統(tǒng)內(nèi)，緩沖的變化等價于 Peer加入或退出系統(tǒng)，這一情況 在 P2P 系統(tǒng)中會頻繁發(fā)生， 因此會帶來極大計算和傳輸負(fù)荷。 單調(diào)性就是要求哈 希算法能夠避免這一情況的發(fā)生。分散性(Spread) 在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。 當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時， 由于不同終端所見的緩沖范圍 有可能不同， 從而導(dǎo)致哈希的結(jié)果不一致， 最終的結(jié)果是相同的內(nèi)容被不同的終 端映射到不同

15、的緩沖區(qū)中。 這種情況顯然是應(yīng)該避免的， 因為它導(dǎo)致相同內(nèi)容被 存儲到不同緩沖中去， 降低了系統(tǒng)存儲的效率。 分散性的定義就是上述情況發(fā)生 的嚴(yán)重程度。 好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生， 也就是盡量降低 分散性。負(fù)載（Load）負(fù)載問題實際上是從另一個角度看待分散性問題。 既然不同的終端可能將相同的 內(nèi)容映射到不同的緩沖區(qū)中， 那么對于一個特定的緩沖區(qū)而言， 也可能被不同的 用戶映射為不同的內(nèi)容。 與分散性一樣， 這種情況也是應(yīng)當(dāng)避免的， 因此好的哈 希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。從表面上看，一致性哈希針對的是分布式緩沖的問題，但是如果將緩沖看作 P2P 系統(tǒng)中的Peer,將映射

16、的內(nèi)容看作各種共享的資源（數(shù)據(jù)，文件，媒體流等）, 就會發(fā)現(xiàn)兩者實際上是在描述同一問題。路由算法 在一致性哈希算法中，每個節(jié)點（對應(yīng) P2P系統(tǒng)中的Peer）都有隨機分配的ID。 在將內(nèi)容映射到節(jié)點時，使用內(nèi)容的關(guān)鍵字和節(jié)點的 ID 進行一致性哈希運算并 獲得鍵值。一致性哈希要求鍵值和節(jié)點 ID 處于同一值域。最簡單的鍵值和 ID 可以是一維的，比如從 0000到 9999的整數(shù)集合。根據(jù)鍵值存儲內(nèi)容時，內(nèi)容將被存儲到具有與其鍵值最接近的 ID 的節(jié)點上。例 如鍵值為 1001的內(nèi)容，系統(tǒng)中有 ID 為 1000， 1010， 1100 的節(jié)點，該內(nèi)容將被 映射到 1000 節(jié)點。為了構(gòu)建查詢

17、所需的路由，一致性哈希要求每個節(jié)點存儲其上行節(jié)點（ID 值大于 自身的節(jié)點中最小的）和下行節(jié)點（ID 值小于自身的節(jié)點中最大的）的位置信息 （IP 地址）。當(dāng)節(jié)點需要查找內(nèi)容時，就可以根據(jù)內(nèi)容的鍵值決定向上行或下行 節(jié)點發(fā)起查詢請求。 收到查詢請求的節(jié)點如果發(fā)現(xiàn)自己擁有被請求的目標(biāo)， 可以 直接向發(fā)起查詢請求的節(jié)點返回確認(rèn)； 如果發(fā)現(xiàn)不屬于自身的范圍， 可以轉(zhuǎn)發(fā)請 求到自己的上行/ 下行節(jié)點。為了維護上述路由信息，在節(jié)點加入/退出系統(tǒng)時，相鄰的節(jié)點必須及時更新路 由信息。這就要求節(jié)點不僅存儲直接相連的下行節(jié)點位置信息， 還要知道一定深 度（n 跳）的間接下行節(jié)點信息，并且動態(tài)地維護節(jié)點列表。當(dāng)

18、節(jié)點退出系統(tǒng)時， 它的上行節(jié)點將嘗試直接連接到最近的下行節(jié)點， 連接成功后， 從新的下行節(jié)點 獲得下行節(jié)點列表并更新自身的節(jié)點列表。 同樣的，當(dāng)新的節(jié)點加入到系統(tǒng)中時， 首先根據(jù)自身的 ID 找到下行節(jié)點并獲得下行節(jié)點列表，然后要求上行節(jié)點修改 其下行節(jié)點列表，這樣就恢復(fù)了路由關(guān)系。討論致性哈希基本解決了在P2P環(huán)境中最為關(guān)鍵的冋題如何在動態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯吐酚伞?每個節(jié)點僅需維護少量相鄰節(jié)點的信息， 并且在節(jié)點加入 /退出系統(tǒng)時，僅有相關(guān)的少量節(jié)點參與到拓?fù)涞木S護中。所有這一切使得一致 性哈希成為第一個實用的DHT算法。但是一致性哈希的路由算法尚有不足之處。 在查詢過程中，查詢消息要經(jīng)

19、過 O（N） 步（0（N）表示與N成正比關(guān)系，N代表系統(tǒng)內(nèi)的節(jié)點總數(shù)）才能到達被查詢的節(jié)點。 不難想象， 當(dāng)系統(tǒng)規(guī)模非常大時， 節(jié)點數(shù)量可能超過百萬， 這樣的查詢效率顯然 難以滿足使用的需要。 換個角度來看， 即使用戶能夠忍受漫長的時延， 查詢過程 中產(chǎn)生的大量消息也會給網(wǎng)絡(luò)帶來不必要的負(fù)荷。下文中討論的幾種DHT議都對路由做出了優(yōu)化，提出了各自的算法。Chord 協(xié)議Chord在2001年由麻省理工學(xué)院提出（參見0），其核心思想就是要解決在 P2P 應(yīng)用中遇到的基本問題：如何在P2P網(wǎng)絡(luò)中找到存有特定數(shù)據(jù)的節(jié)點。與前兩種 協(xié)議不同，Chord專門為P2P應(yīng)用設(shè)計，因此考慮了在P2P應(yīng)用中可能

20、遇到的特 殊問題，這些內(nèi)容將在路由的部分進行討論。哈希算法Chord 使用一致性哈希作為哈希算法。 在一致性哈希協(xié)議中并沒有定義具體的算 法，在Chord協(xié)議中將其規(guī)定為 SHA-1路由算法Chord 在一致性哈希的基礎(chǔ)上提供了優(yōu)化的路由算法：在Chord中，每個節(jié)點同樣需要存儲m個其他節(jié)點的信息，這些信息的集合被稱 為查詢表（F in ger Table）。一致性哈希中的節(jié)點同樣具有這樣的表格，但在Chord 中，表格中的節(jié)點不再是直接相鄰的節(jié)點，它們的間距 （ID間隔）將成 2i 的關(guān)系排列（i表示表中的數(shù)組下標(biāo)）o這樣形成的節(jié)點之間路由關(guān)系實際上就是折 半查找算法需要的排列關(guān)系。在查詢的

21、過程中，查詢節(jié)點將請求發(fā)送到與鍵值最接近的節(jié)點上。收到查詢請求 的節(jié)點如果發(fā)現(xiàn)自身存儲了被查詢的信息，可以直接回應(yīng)查詢節(jié)點 （這與一致性 哈希完全相同）；如果被查詢的信息不在本地，就根據(jù)查詢表將請求轉(zhuǎn)發(fā)到與鍵值最接近的節(jié)點上。 這樣的過程一直持續(xù)到找到相應(yīng)的節(jié)點為止。 不難看出， 查 詢過程實際上就是折半查找的過程。經(jīng)過Chord的優(yōu)化后，查詢需要的跳數(shù)由0 ( N)減少到O(log(N)。這樣即使在 大規(guī)模的P2P網(wǎng)絡(luò)中(例如N= 100,000,000)，查詢的跳數(shù)也僅為 0(8),每個節(jié) 點僅需存儲27個(log2100000000)其他節(jié)點的信息。Chord還考慮到多個節(jié)點同時加入系統(tǒng)

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

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

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

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

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

27、種。哈希算法Pastry 使用一致性哈希作為哈希算法。 哈希所得的鍵值為一維（實際上使用的是 128bit 的整數(shù)空間） 。 Pastry 也沒有規(guī)定具體應(yīng)該采用何種哈希算法。路由算法在Pastry協(xié)議中，每個節(jié)點都擁有一個 128bit的標(biāo)識（Node Id）。為了保證 No de ID的唯一性，一般由節(jié)點的網(wǎng)絡(luò)標(biāo)識（如IP地址）經(jīng)過哈希得到。Pastry 中的每個節(jié)點擁有一個路由表 R（Routing table） ， 一個鄰居節(jié)點集 M（Ne ighborhood Set） 和一個葉子節(jié)點集合 L（Leaf set） ，它們一起構(gòu)成了節(jié)點的狀 態(tài)表。路由表R共有l(wèi)ogBN（B = 2b為

28、系統(tǒng)參數(shù)，典型值為16, N表示系統(tǒng)的節(jié)點總數(shù)） 行，每行包括B-1個表項，每個表項記錄了一個鄰居節(jié)點的信息（節(jié)點標(biāo)識、IP 地址、當(dāng)前狀態(tài)等）。這樣就形成了擁有（B-1）logBN個條目的二維表格。路由表第n行的表項所記錄的鄰居節(jié)點的Node ID前n個數(shù)位和當(dāng)前節(jié)點的前n個數(shù) 位相同，而第n+1個數(shù)位則分別取從0到B-1的值（除了與當(dāng)前節(jié)點第n+1數(shù) 位的值）。這樣形成的路由表很類似IP路由中最長掩碼匹配的算法。參數(shù)b（或B） 大小非常關(guān)鍵：B過大則節(jié)點需要維護很大的路由表，可能超出節(jié)點的負(fù)載能力， 但路由表大些可以存儲更多的鄰居節(jié)點， 在轉(zhuǎn)發(fā)時更為精確。 平均每次路由查找 需要的跳數(shù)在P

29、astry中計算的結(jié)果是logBN,因此B的選擇反映了路由表大小 和路由效率之間的折衷。葉子節(jié)點集合L中存放的是在鍵值空間中與當(dāng)前節(jié)點距離最近的|L|個節(jié)點的信 息，其中一半節(jié)點標(biāo)識大于當(dāng)前節(jié)點，另一半節(jié)點標(biāo)識小于當(dāng)前節(jié)點。 |L| 的典 型值為2b或者2*2b。鄰居節(jié)點集合M中存放的是在真實網(wǎng)絡(luò)中與當(dāng)前節(jié)點“距離”最近的|M|個節(jié)點 的信息。 “距離”的定義在 Pastry 中非常類似 IP 路由協(xié)議中對距離的定義，也 就是考慮到轉(zhuǎn)發(fā)跳數(shù)、傳輸路徑帶寬、 QoS 等綜合因素后所得的轉(zhuǎn)發(fā)開銷（可以 參見OSPF等路由協(xié)議）。Pastry并未提供距離信息的獲取方法，而是假設(shè)應(yīng)用 層可以通過某種手

30、段（人工配制或自動協(xié)商）得到信息并配置鄰居節(jié)點集合。 |M| 的典型值為2b或者2*2b。圖 3 給出了一個 Pastry 節(jié)點狀態(tài)表的例子，該圖來源于4 。在節(jié)點狀態(tài)表中，節(jié)點本身的 ID 為 10233102。葉子集合中有 8項，每一項都代 表一個當(dāng)前節(jié)點已知的其他節(jié)點的信息。 路由表共有 4*8 項，可以看出由上至下 節(jié)點 ID 重合的位數(shù)（前綴）不斷增加。鄰居集合中的節(jié)點 ID 由于來源于應(yīng)用層， 一般沒有規(guī)律性可循。Pastry 的路由過程如下： 首先，路由查詢消息中將攜帶被查詢對象 ID(Object Id) ，又稱消息鍵值。當(dāng)收 到路由消息時，節(jié)點首先檢查消息鍵值是否落在葉子節(jié)點

31、集合的范圍內(nèi)。 如果是， 則直接把消息轉(zhuǎn)發(fā)給葉子節(jié)點集合中節(jié)點標(biāo)識和消息鍵值最接近的節(jié)點； 否則就 從路由表中根據(jù)最長前綴優(yōu)先的原則選擇一個節(jié)點作為路由目標(biāo)，轉(zhuǎn)發(fā)路由消 息。如果不存在這樣的節(jié)點，當(dāng)前節(jié)點將會從其維護的所有鄰居節(jié)點集合 ( 包括 路由表葉子集合及鄰居集合中的節(jié)點)中選擇一個距離消息鍵值最近的節(jié)點作為 轉(zhuǎn)發(fā)目標(biāo)。從上述過程中可以看出， 每一步路由和上一步相比都更靠近目標(biāo)節(jié)點， 因此這個 過程是收斂的。如果路由表不為空，每步路由至少能夠增加一個前綴匹配數(shù)位， 因此在路由表始終有效時，路由的步數(shù)至多為 logBN。討論Pastry 的路由利用了成熟的最大掩碼匹配算法，因此實現(xiàn)時可以利

32、用很多現(xiàn)成 的軟件算法和硬件框架，可以獲得很好的效率。與Chord和CAN®比，Pastry弓I入了葉子節(jié)點和鄰居節(jié)點集合的概念。在應(yīng)用 層能夠及時準(zhǔn)確地獲得這兩個集合的節(jié)點信息時，可以大大加快路由查找的速 度,同時降低因路由引起的網(wǎng)絡(luò)傳輸開銷； 不過在動態(tài)變化的P2P網(wǎng)絡(luò)中如何理 想地做到這一點的確有很大的難度。Pastry的典型應(yīng)用包括 PAST參見56)和 SCRIBE參見7)趨勢分析 目前DHT算法的發(fā)展方向非常多，不斷有新的改進算法被提出來。就筆者目前了解到的信息而言，至少有以下一些方向：接近性(Proximity)文中提到的DHT算法中，除了 Pasrty以外，均未考慮重

33、疊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與真實的 IP 網(wǎng)絡(luò)之間的重合關(guān)系。節(jié)點之間進行對等通信時，不會考慮優(yōu)先選取距離 自己最近的節(jié)點。 這樣就使得最終形成的重疊網(wǎng)結(jié)構(gòu)混亂， 效率低下。 因此如何 讓節(jié)點獲得并利用接近性信息就非常重要。結(jié)構(gòu)化目前基于DHT勺應(yīng)用尚未大規(guī)模展開，很多工程上的細節(jié)問題尚待解決。例如： 目前有很多種類的P2P應(yīng)用，如文件存儲和共享、電子郵件、流媒體等。這些應(yīng) 用在處理P2P路由算法、拓?fù)渚S護和信息檢索上使用的方法均有很大差別，導(dǎo)致即使是同類的應(yīng)用也無法實現(xiàn)互通。如何為各種P2P的應(yīng)用抽象出一個通用的層 次，也是目前研究的熱點問題之一。信息查詢 基于分布式哈希表的查詢是一種單關(guān)鍵字的精確匹配

34、， 盡管相對于非結(jié)構(gòu)化系統(tǒng) 它使得系統(tǒng)資源可被確定性地查詢到， 但它也極大地限制了查詢的應(yīng)用范圍。 目 前有許多改進的結(jié)構(gòu)化查詢算法已經(jīng)被提出來。參考文獻David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy "Consistent Hashing and Random Trees:Distributed Cach ing Protocols for Relieving Hot Spots on the World Wide Web". In Proc eed

35、ings of the 29th Annual ACM Sym-posium on Theory of Computing (El Paso, TX, May 1997), pp. 654-663.Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Bala krishnan_ "Chord: A Scalable Peertopeer Lookup Service for Internet A pplications" SIGCOMM'01, August 2731, 2001, San

36、 Diego, California, US A.Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott She nker "A Scalable Content-Addressable Network" SIGCOMM'01, August 27-3 1, 2001, San Diego, California, USA.Antony Rowstron1 and Peter Druschel "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems" App ears in Proc. of the 18th IFIP/ACM International Conference on Distri buted Systems Platforms (Middleware