本文首先從P2P的定義出發(fā)，介紹了結構化P2P與非結構化P2P的區別以及結構化P2P的核心技術(shù)DHT。而后，本文深入介紹了幾種主流的DHT算法與協(xié)議并對每種協(xié)議進(jìn)行了討論。文章的最后展望了DHT在未來(lái)的發(fā)展趨勢。
對等網(wǎng)絡(luò )(Peer-to-Peer，簡(jiǎn)稱(chēng)P2P)是目前非常熱門(mén)的應用，自1999年以來(lái)，P2P的研究一直是國外知名學(xué)府(如美國麻省理工學(xué)院，加州大學(xué)伯克利分校和萊斯大學(xué)等)以及知名企業(yè)的研發(fā)機構(如微軟，諾基亞的研究院)關(guān)注的重點(diǎn)。它甚至被美國《財富》雜志稱(chēng)為改變因特網(wǎng)發(fā)展的四大新技術(shù)之一，被認為是代表無(wú)線(xiàn)寬帶互聯(lián)網(wǎng)未來(lái)的關(guān)鍵技術(shù)。
作為一項新興的技術(shù)，目前學(xué)術(shù)界對P2P在技術(shù)層面上的定義尚未統一。Keith W. Ross (PolytechnicUniversity)和Dan Rubenstein(ColumbiaUniversity)在[9]中提到了對P2P系統的3個(gè)基本定義：
相比中央服務(wù)器而言有明顯的自治性(Autonomy)。
利用網(wǎng)絡(luò )邊緣的資源，如存儲/計算能力和信息資源。
網(wǎng)絡(luò )邊緣的資源處在動(dòng)態(tài)的變化中(新的資源加入，已有的資源消失)。
自治性的要求使得P2P系統不再需要特定的中央管理機制，所有節點(diǎn)之間擁有對等的關(guān)系。這一方面為系統帶來(lái)了自組織、容錯性好、可擴展性強等優(yōu)點(diǎn)；另一方面也提出了新的問(wèn)題：如何在沒(méi)有集中管理機制的情況下實(shí)現系統的自組織和自管理？
定義2，3中分布性和動(dòng)態(tài)性的特點(diǎn)使得上述問(wèn)題的實(shí)現具有更大的難度。在分布式系統中，過(guò)多過(guò)快的信息交互可能消耗大量的網(wǎng)絡(luò )資源；而為了實(shí)時(shí)反映系統的變化，又要求節點(diǎn)及時(shí)獲得更新信息，這就需要在節點(diǎn)之間進(jìn)行通信。
為了解決這一對矛盾，已經(jīng)有許多P2P的框架和協(xié)議被提出來(lái)并得到了很好的應用。
結構化與非結構化P2P
依照節點(diǎn)信息存儲與搜索方式的不同，諸多P2P協(xié)議可以分為2大類(lèi)：結構化(Structured)的與非結構化(Unstructured)的系統。
非結構化P2P系統
在非結構化的系統中，每個(gè)節點(diǎn)存儲自身的信息或信息的索引(如指針和IP地址)。當用戶(hù)需要在P2P系統中獲取信息時(shí)，他們預先并不知道這些信息(如某個(gè)文件)會(huì )在那個(gè)節點(diǎn)上存儲。因此，在非結構化P2P系統中，信息搜索的算法難免帶有一定的盲目性，例如最簡(jiǎn)單的泛洪式查找(類(lèi)似于廣播)和擴展環(huán)查找(從最近的n個(gè)節點(diǎn)開(kāi)始，層層轉發(fā)直到找到目標或超出了跳數的上限為止)。
一些典型的應用采用了一些優(yōu)化的辦法。如在Gnutella中，采用了等級制的組成結構：節點(diǎn)被分成超級節點(diǎn)(SuperNode)和普通節點(diǎn)。普通節點(diǎn)必須依附于超級節點(diǎn)，每個(gè)超級節點(diǎn)作為一個(gè)獨立的域管理者，負責處理域內的查詢(xún)操作。在查找的過(guò)程中，查詢(xún)首先在域內進(jìn)行，失敗后才會(huì )擴展到超級節點(diǎn)之間。
非結構化系統的優(yōu)點(diǎn)在于實(shí)現結構簡(jiǎn)單：無(wú)須中央服務(wù)器，節點(diǎn)之間完全平等，網(wǎng)絡(luò )的層次是單一的，而且節點(diǎn)之間無(wú)需維護拓撲信息。
結構化P2P系統
在結構化P2P系統中，每個(gè)節點(diǎn)只存儲特定的信息或特定信息的索引。當用戶(hù)需要在P2P系統中獲取信息時(shí)，他們必須知道這些信息(或索引)可能存在于那些節點(diǎn)中。由于用戶(hù)預先知道應該搜索哪些節點(diǎn)，避免了非結構化P2P系統中使用的泛洪式查找，因此提高了信息搜索的效率。
但是，結構化P2P也引入了新的問(wèn)題：
首先，既然信息是分布存儲的，那么如何將信息分布存儲在重疊網(wǎng)中的節點(diǎn)上？
其次，由于節點(diǎn)動(dòng)態(tài)的加入和離開(kāi)重疊網(wǎng)，如何將拓撲的變更信息通知其它節點(diǎn)？
DHT的引入基本解決了上述問(wèn)題，因此自從DHT協(xié)議出現以后，結構化P2P的應用得到了快速的發(fā)展。目前已經(jīng)有很多較為成熟的DHT協(xié)議被提出并且得到了應用。其中比較有代表性的有：緩沖陣列路由協(xié)議(CARP)；一致性哈希；Chord；內容尋址網(wǎng)絡(luò )；Pastry。
DHT簡(jiǎn)介
DHT使用分布式哈希算法來(lái)解決結構化的分布式存儲問(wèn)題。分布式哈希算法的核心思想是通過(guò)將存儲對象的特征(關(guān)鍵字)經(jīng)過(guò)哈希運算，得到鍵值(HashKey)，對象的分布存儲依據鍵值來(lái)進(jìn)行。具體來(lái)講，大致有以下步驟：
對存儲對象的關(guān)鍵字進(jìn)行哈希運算，得到鍵值。這樣就將所有的對象映射到了一個(gè)具體的數值范圍中。
重疊網(wǎng)中的每個(gè)節點(diǎn)負責數值范圍中的特定段落。例如，節點(diǎn)A負責存儲鍵值從8000到8999的對象；而節點(diǎn)B負責7000~7999的對象。這樣就將對象集合分布地存儲在所有的節點(diǎn)中。
節點(diǎn)可以直接存儲對象本身，如文件中的一個(gè)片段；也可以存儲對象的索引，如該對象所在節點(diǎn)的IP地址。
結構化的分布式存儲問(wèn)題解決后，剩下的問(wèn)題就是用戶(hù)如何才能找到存儲著(zhù)目標信息的節點(diǎn)。在有著(zhù)大量節點(diǎn)(如100萬(wàn)個(gè))的P2P系統中，任何節點(diǎn)都不可能擁有全部的節點(diǎn)?鍵值?內容的對應關(guān)系；因此用戶(hù)獲得了鍵值之后，如何找到該鍵值對應的節點(diǎn)就被稱(chēng)為DHT的路由問(wèn)題。DHT協(xié)議必須定義優(yōu)化的查找(路由)算法來(lái)完成這一搜尋的工作。不同的DHT協(xié)議之間區別很大程度上就在于定義了不同的路由算法。
DHT的應用非常簡(jiǎn)潔----API簡(jiǎn)單到只有一項輸入和一項輸出：
應用層將數據對象(文件、數據塊或索引)通過(guò)哈希算法獲得鍵值，將該鍵值提交給DHT后，返回結果就是鍵值所在節點(diǎn)的IP地址。圖1(來(lái)自[9])顯示了這種應用結構：
 |
| 圖 1 DHT的應用結構 |
在這樣的支持下，可以開(kāi)發(fā)多種P2P的應用程序，如網(wǎng)絡(luò )存儲與文件共享、即時(shí)消息、音頻/視頻等。圖2(來(lái)自[9])顯示了這種應用結構：
 |
| 圖 2 DHT應用的層次 |
主流DHT協(xié)議
緩沖陣列路由協(xié)議(CARP，Cache Array Routing Protocol)
協(xié)議簡(jiǎn)介
CARP是由微軟公司的Vinod Valloppillil和賓西法尼亞大學(xué)的Keith W.Ross在1997年提出的。該協(xié)議可以將URL空間映射到一個(gè)僅有松散關(guān)聯(lián)關(guān)系的Web cache服務(wù)器(在協(xié)議中稱(chēng)為“代理”，Proxy)陣列中。支持該協(xié)議的HTTP客戶(hù)端可以根據要訪(fǎng)問(wèn)的URL智能選擇目標代理。該協(xié)議解決了在代理陣列內分布存儲內容的問(wèn)題，避免了內容的重復存儲，提高了客戶(hù)端訪(fǎng)問(wèn)時(shí)WebCache命中的概率。
哈希算法
哈希使用的關(guān)鍵字有2個(gè)，一個(gè)是代理的標識符(每個(gè)代理均有唯一的標識)，另一個(gè)是URL本身。存儲內容時(shí)，每個(gè)代理負責緩沖哈希鍵值最大的URL。這樣，當緩沖代理陣列發(fā)生少量變化時(shí)(新的代理加入或舊的代理退出)，原有的URL還有可能仍然被映射到原來(lái)的代理上，仍可以按照原有的方式訪(fǎng)問(wèn)。
路由算法
客戶(hù)端(HTTP瀏覽器)首先加載一個(gè)代理配置文件，該文件中存儲了代理的標識符和IP地址等用于哈希的關(guān)鍵參數。瀏覽器在訪(fǎng)問(wèn)網(wǎng)頁(yè)時(shí)，可以根據URL和代理標識獲得代理的位置信息(IP地址)，從而可以直接訪(fǎng)問(wèn)緩沖代理中的頁(yè)面。
討論
CARP的哈希過(guò)程比較簡(jiǎn)單，路由查找更是簡(jiǎn)單到至多只有一跳(O(1))。但是CARP在P2P的應用環(huán)境中有一些致命的缺陷：
每個(gè)節點(diǎn)必須知道其它所有節點(diǎn)的信息。在大規模的重疊網(wǎng)環(huán)境中，由于可能存在大量的(數百萬(wàn))節點(diǎn)，加之節點(diǎn)都是動(dòng)態(tài)加入和退出網(wǎng)絡(luò )，因此這一條件幾乎不可能滿(mǎn)足。
在緩沖陣列發(fā)生較大變化時(shí)(這在P2P網(wǎng)絡(luò )中非常常見(jiàn))，原有的URL和代理之間的對應關(guān)系可能發(fā)生改變，從而使得原有的配置文件失效。
一致性哈希(Consistent Hash)
協(xié)議簡(jiǎn)介
一致性哈希算法在1997年由麻省理工學(xué)院提出(參見(jiàn)0)，設計目標是為了解決因特網(wǎng)中的熱點(diǎn)(Hotpot)問(wèn)題，初衷和CARP十分類(lèi)似。一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來(lái)的問(wèn)題，使得DHT可以在P2P環(huán)境中真正得到應用。
哈希算法
一致性哈希提出了在動(dòng)態(tài)變化的Cache環(huán)境中，哈希算法應該滿(mǎn)足的4個(gè)適應條件：
平衡性(Balance)
平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿(mǎn)足這一條件。
單調性(Monotonicity)
單調性是指如果已經(jīng)有一些內容通過(guò)哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會(huì )被映射到舊的緩沖集合中的其他緩沖區。
簡(jiǎn)單的哈希算法往往不能滿(mǎn)足單調性的要求，如最簡(jiǎn)單的線(xiàn)性哈希：
x → ax + b mod (P)
在上式中，P表示全部緩沖的大小。不難看出，當緩沖大小發(fā)生變化時(shí)(從P1到P2)，原來(lái)所有的哈希結果均會(huì )發(fā)生變化，從而不滿(mǎn)足單調性的要求。
哈希結果的變化意味著(zhù)當緩沖空間發(fā)生變化時(shí)，所有的映射關(guān)系需要在系統內全部更新。而在P2P系統內，緩沖的變化等價(jià)于Peer加入或退出系統，這一情況在P2P系統中會(huì )頻繁發(fā)生，因此會(huì )帶來(lái)極大計算和傳輸負荷。單調性就是要求哈希算法能夠避免這一情況的發(fā)生。
分散性(Spread)
在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過(guò)哈希過(guò)程將內容映射到緩沖上時(shí)，由于不同終端所見(jiàn)的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發(fā)生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。
負載(Load)
負載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那么對于一個(gè)特定的緩沖區而言，也可能被不同的用戶(hù)映射為不同的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。
從表面上看，一致性哈希針對的是分布式緩沖的問(wèn)題，但是如果將緩沖看作P2P系統中的Peer，將映射的內容看作各種共享的資源(數據，文件，媒體流等)，就會(huì )發(fā)現兩者實(shí)際上是在描述同一問(wèn)題。
路由算法
在一致性哈希算法中，每個(gè)節點(diǎn)(對應P2P系統中的Peer)都有隨機分配的ID。在將內容映射到節點(diǎn)時(shí)，使用內容的關(guān)鍵字和節點(diǎn)的ID進(jìn)行一致性哈希運算并獲得鍵值。一致性哈希要求鍵值和節點(diǎn)ID處于同一值域。最簡(jiǎn)單的鍵值和ID可以是一維的，比如從0000到9999的整數集合。
根據鍵值存儲內容時(shí)，內容將被存儲到具有與其鍵值最接近的ID的節點(diǎn)上。例如鍵值為1001的內容，系統中有ID為1000，1010，1100的節點(diǎn)，該內容將被映射到1000節點(diǎn)。
為了構建查詢(xún)所需的路由，一致性哈希要求每個(gè)節點(diǎn)存儲其上行節點(diǎn)(ID值大于自身的節點(diǎn)中最小的)和下行節點(diǎn)(ID值小于自身的節點(diǎn)中最大的)的位置信息(IP地址)。當節點(diǎn)需要查找內容時(shí)，就可以根據內容的鍵值決定向上行或下行節點(diǎn)發(fā)起查詢(xún)請求。收到查詢(xún)請求的節點(diǎn)如果發(fā)現自己擁有被請求的目標，可以直接向發(fā)起查詢(xún)請求的節點(diǎn)返回確認；如果發(fā)現不屬于自身的范圍，可以轉發(fā)請求到自己的上行/下行節點(diǎn)。
為了維護上述路由信息，在節點(diǎn)加入/退出系統時(shí)，相鄰的節點(diǎn)必須及時(shí)更新路由信息。這就要求節點(diǎn)不僅存儲直接相連的下行節點(diǎn)位置信息，還要知道一定深度(n跳)的間接下行節點(diǎn)信息，并且動(dòng)態(tài)地維護節點(diǎn)列表。當節點(diǎn)退出系統時(shí)，它的上行節點(diǎn)將嘗試直接連接到最近的下行節點(diǎn)，連接成功后，從新的下行節點(diǎn)獲得下行節點(diǎn)列表并更新自身的節點(diǎn)列表。同樣的，當新的節點(diǎn)加入到系統中時(shí)，首先根據自身的ID找到下行節點(diǎn)并獲得下行節點(diǎn)列表，然后要求上行節點(diǎn)修改其下行節點(diǎn)列表，這樣就恢復了路由關(guān)系。
討論
一致性哈?；窘鉀Q了在P2P環(huán)境中最為關(guān)鍵的問(wèn)題——如何在動(dòng)態(tài)的網(wǎng)絡(luò )拓撲中分布存儲和路由。每個(gè)節點(diǎn)僅需維護少量相鄰節點(diǎn)的信息，并且在節點(diǎn)加入/退出系統時(shí)，僅有相關(guān)的少量節點(diǎn)參與到拓撲的維護中。所有這一切使得一致性哈希成為第一個(gè)實(shí)用的DHT算法。
但是一致性哈希的路由算法尚有不足之處。在查詢(xún)過(guò)程中，查詢(xún)消息要經(jīng)過(guò)O(N)步(O(N)表示與N成正比關(guān)系，N代表系統內的節點(diǎn)總數)才能到達被查詢(xún)的節點(diǎn)。不難想象，當系統規模非常大時(shí)，節點(diǎn)數量可能超過(guò)百萬(wàn)，這樣的查詢(xún)效率顯然難以滿(mǎn)足使用的需要。換個(gè)角度來(lái)看，即使用戶(hù)能夠忍受漫長(cháng)的時(shí)延，查詢(xún)過(guò)程中產(chǎn)生的大量消息也會(huì )給網(wǎng)絡(luò )帶來(lái)不必要的負荷。
下文中討論的幾種DHT協(xié)議都對路由做出了優(yōu)化，提出了各自的算法。
Chord協(xié)議
Chord在2001年由麻省理工學(xué)院提出(參見(jiàn)0)，其核心思想就是要解決在P2P應用中遇到的基本問(wèn)題：如何在P2P網(wǎng)絡(luò )中找到存有特定數據的節點(diǎn)。與前兩種協(xié)議不同，Chord專(zhuān)門(mén)為P2P應用設計，因此考慮了在P2P應用中可能遇到的特殊問(wèn)題，這些內容將在路由的部分進(jìn)行討論。
哈希算法
Chord使用一致性哈希作為哈希算法。在一致性哈希協(xié)議中并沒(méi)有定義具體的算法，在Chord協(xié)議中將其規定為SHA-1。
路由算法
Chord在一致性哈希的基礎上提供了優(yōu)化的路由算法：
在Chord中，每個(gè)節點(diǎn)同樣需要存儲m個(gè)其他節點(diǎn)的信息，這些信息的集合被稱(chēng)為查詢(xún)表(FingerTable)。一致性哈希中的節點(diǎn)同樣具有這樣的表格，但在Chord中，表格中的節點(diǎn)不再是直接相鄰的節點(diǎn)，它們的間距(ID間隔)將成2i的關(guān)系排列(i 表示表中的數組下標)。這樣形成的節點(diǎn)之間路由關(guān)系實(shí)際上就是折半查找算法需要的排列關(guān)系。
在查詢(xún)的過(guò)程中，查詢(xún)節點(diǎn)將請求發(fā)送到與鍵值最接近的節點(diǎn)上。收到查詢(xún)請求的節點(diǎn)如果發(fā)現自身存儲了被查詢(xún)的信息，可以直接回應查詢(xún)節點(diǎn)(這與一致性哈希完全相同)；如果被查詢(xún)的信息不在本地，就根據查詢(xún)表將請求轉發(fā)到與鍵值最接近的節點(diǎn)上。這樣的過(guò)程一直持續到找到相應的節點(diǎn)為止。不難看出，查詢(xún)過(guò)程實(shí)際上就是折半查找的過(guò)程。
經(jīng)過(guò)Chord的優(yōu)化后，查詢(xún)需要的跳數由O (N)減少到O(log(N))。這樣即使在大規模的P2P網(wǎng)絡(luò )中(例如N＝100,000,000)，查詢(xún)的跳數也僅為O(8)，每個(gè)節點(diǎn)僅需存儲27個(gè)(log2100000000)其他節點(diǎn)的信息。
Chord還考慮到多個(gè)節點(diǎn)同時(shí)加入系統的情況并對節點(diǎn)加入/退出算法作了優(yōu)化。
討論
Chord算法本身具有如下優(yōu)點(diǎn)：
負載平衡
這一優(yōu)點(diǎn)來(lái)自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的節點(diǎn)以同等的概率分擔系統負荷，從而可以避免某些節點(diǎn)負載過(guò)大的情況。
分布性
Chord是純分布式系統，節點(diǎn)之間完全平等并完成同樣的工作。這使得Chord具有很高的魯棒性，可以抵御DoS攻擊。
可擴展性
Chord協(xié)議的開(kāi)銷(xiāo)隨著(zhù)系統規模(結點(diǎn)總數N)的增加而按照O(logN)的比例增加。因此Chord可以用于大規模的系統。
可用性
Chord協(xié)議要求節點(diǎn)根據網(wǎng)絡(luò )的變化動(dòng)態(tài)的更新查詢(xún)表，因此能夠及時(shí)恢復路由關(guān)系，使得查詢(xún)可以可靠地進(jìn)行。
命名的靈活性
Chord并未限制查詢(xún)內容的結構，因此應用層可以靈活的將內容映射到鍵值空間而不受協(xié)議的限制。
Chord在CFS系統中得到了應用，具體的介紹可參見(jiàn)[8]
內容尋址網(wǎng)絡(luò )(Content-Addressable Network，CAN)
CAN在2001年由加州大學(xué)伯克利分校提出(參見(jiàn)[3])。與Chord一樣，CAN也是DHT的一個(gè)變種。
哈希算法
CAN的哈希算法與一致性哈希有所不同。Chord中，哈希得到的鍵值總是一維的，而在CAN中，哈希的結果由d維的笛卡爾空間來(lái)表示。d是一個(gè)由系統規模決定的常量。
路由算法
CAN的路由查詢(xún)將在d維笛卡爾空間中進(jìn)行。
在CAN中，每個(gè)節點(diǎn)自身的ID經(jīng)由哈希后得到的d維向量。經(jīng)過(guò)這樣的映射后，整個(gè)P2P系統將被映射到一個(gè)d維笛卡爾空間中，每個(gè)節點(diǎn)的位置由其自身ID決定。CAN對鄰居節點(diǎn)的定義并不要求成2i的關(guān)系排列，而是改為用在笛卡爾空間上相鄰來(lái)表示：在d維笛卡爾空間中，2個(gè)節點(diǎn)的d維坐標中有d-1維是相等的，剩余的一維是相鄰的節點(diǎn)稱(chēng)之為相鄰節點(diǎn)。
CAN中的節點(diǎn)僅存儲相鄰節點(diǎn)表。由于在d維的空間中最多有2d個(gè)相鄰的節點(diǎn)，因此節點(diǎn)的相鄰節點(diǎn)表最多有2d個(gè)表項。
在查詢(xún)的過(guò)程中，查詢(xún)節點(diǎn)首先計算被查詢(xún)內容的鍵值(d維向量)，然后在節點(diǎn)列表中查找在笛卡爾空間中與該鍵值最為接近的相鄰節點(diǎn)，找到后向該節點(diǎn)發(fā)送查詢(xún)請求(這一策略被稱(chēng)為貪婪策略)。查詢(xún)請求中將攜帶被查詢(xún)內容的鍵值。收到查詢(xún)請求的節點(diǎn)如果發(fā)現自身存儲了被查詢(xún)的信息，可以直接回應查詢(xún)節點(diǎn)(這與一致性哈希完全相同)；如果被查詢(xún)的信息不在本地，就根據相鄰節點(diǎn)表將請求轉發(fā)到與鍵值最接近的節點(diǎn)上。這樣的過(guò)程一直持續到找到相應的節點(diǎn)為止。在查詢(xún)過(guò)程中，被查詢(xún)節點(diǎn)到目標節點(diǎn)的笛卡爾空間距離單調地減少。
如果查詢(xún)節點(diǎn)或轉發(fā)節點(diǎn)發(fā)現鄰居節點(diǎn)表中無(wú)法找到可用的下一跳節點(diǎn)，則采用非結構化P2P常用的擴展環(huán)搜索(ExpandingRing Search，使用無(wú)狀態(tài)，受控的泛洪算法在重疊網(wǎng)中搜索)以找到合適的(符合貪婪策略)下一節點(diǎn)。
經(jīng)過(guò)CAN的優(yōu)化后，查詢(xún)需要的跳數由O (N)減少到均值為(d/4)(n1/d)的隨機制，考慮到d為常數，這一值可以表示為O(n1/d)或O(dn1/d)。
討論
CAN和Chord的主要區別在于路由算法不同。相比之下，在節點(diǎn)數量非常大時(shí)，CAN的平均查詢(xún)跳數要比Chord增加得更快。而且CAN查詢(xún)過(guò)程中需要的運算量也要高于Chord。但CAN使用的d為預先設置的常量，因此并不假設系統節點(diǎn)數量。在節點(diǎn)總數動(dòng)態(tài)變化范圍很大的系統中，CAN的相鄰節點(diǎn)表結構保持穩定，這在P2P的應用中也是很重要的優(yōu)點(diǎn)。
Pastry
Pastry在2001年由位于英國劍橋的微軟研究院和萊斯(Rice)大學(xué)提出(參見(jiàn)[4])。Pastry也是DHT的一個(gè)變種。
哈希算法
Pastry使用一致性哈希作為哈希算法。哈希所得的鍵值為一維(實(shí)際上使用的是128bit的整數空間)。Pastry也沒(méi)有規定具體應該采用何種哈希算法。
路由算法
在Pastry協(xié)議中，每個(gè)節點(diǎn)都擁有一個(gè)128bit的標識(Node Id)。為了保證NodeID的唯一性，一般由節點(diǎn)的網(wǎng)絡(luò )標識(如IP地址)經(jīng)過(guò)哈希得到。
Pastry中的每個(gè)節點(diǎn)擁有一個(gè)路由表R(Routing table)，一個(gè)鄰居節點(diǎn)集M(NeighborhoodSet)和一個(gè)葉子節點(diǎn)集合L(Leaf set)，它們一起構成了節點(diǎn)的狀態(tài)表。
路由表R共有logBN(B =2b為系統參數，典型值為16，N表示系統的節點(diǎn)總數)行，每行包括B-1個(gè)表項，每個(gè)表項記錄了一個(gè)鄰居節點(diǎn)的信息(節點(diǎn)標識、IP地址、當前狀態(tài)等)。這樣就形成了擁有(B-1)logBN個(gè)條目的二維表格。路由表第n行的表項所記錄的鄰居節點(diǎn)的NodeID前n個(gè)數位和當前節點(diǎn)的前n個(gè)數位相同，而第n＋1個(gè)數位則分別取從0到B-1的值(除了與當前節點(diǎn)第n＋1數位的值)。這樣形成的路由表很類(lèi)似IP路由中最長(cháng)掩碼匹配的算法。參數b(或B)大小非常關(guān)鍵：B過(guò)大則節點(diǎn)需要維護很大的路由表，可能超出節點(diǎn)的負載能力，但路由表大些可以存儲更多的鄰居節點(diǎn)，在轉發(fā)時(shí)更為精確。平均每次路由查找需要的跳數在Pastry中計算的結果是logBN，因此B的選擇反映了路由表大小和路由效率之間的折衷。
葉子節點(diǎn)集合L中存放的是在鍵值空間中與當前節點(diǎn)距離最近的|L|個(gè)節點(diǎn)的信息，其中一半節點(diǎn)標識大于當前節點(diǎn)，另一半節點(diǎn)標識小于當前節點(diǎn)。|L|的典型值為2b或者2*2b。
鄰居節點(diǎn)集合M中存放的是在真實(shí)網(wǎng)絡(luò )中與當前節點(diǎn)“距離”最近的|M|個(gè)節點(diǎn)的信息。“距離”的定義在Pastry中非常類(lèi)似IP路由協(xié)議中對距離的定義，也就是考慮到轉發(fā)跳數、傳輸路徑帶寬、QoS等綜合因素后所得的轉發(fā)開(kāi)銷(xiāo)(可以參見(jiàn)OSPF等路由協(xié)議)。Pastry并未提供距離信息的獲取方法，而是假設應用層可以通過(guò)某種手段(人工配制或自動(dòng)協(xié)商)得到信息并配置鄰居節點(diǎn)集合。|M|的典型值為2b或者2*2b。
圖 3給出了一個(gè)Pastry節點(diǎn)狀態(tài)表的例子，該圖來(lái)源于[4]。
在節點(diǎn)狀態(tài)表中，節點(diǎn)本身的ID為10233102。葉子集合中有8項，每一項都代表一個(gè)當前節點(diǎn)已知的其他節點(diǎn)的信息。路由表共有4*8項，可以看出由上至下節點(diǎn)ID重合的位數(前綴)不斷增加。鄰居集合中的節點(diǎn)ID由于來(lái)源于應用層，一般沒(méi)有規律性可循。
Pastry的路由過(guò)程如下：
首先，路由查詢(xún)消息中將攜帶被查詢(xún)對象ID(ObjectId)，又稱(chēng)消息鍵值。當收到路由消息時(shí)，節點(diǎn)首先檢查消息鍵值是否落在葉子節點(diǎn)集合的范圍內。如果是，則直接把消息轉發(fā)給葉子節點(diǎn)集合中節點(diǎn)標識和消息鍵值最接近的節點(diǎn)；否則就從路由表中根據最長(cháng)前綴優(yōu)先的原則選擇一個(gè)節點(diǎn)作為路由目標，轉發(fā)路由消息。如果不存在這樣的節點(diǎn)，當前節點(diǎn)將會(huì )從其維護的所有鄰居節點(diǎn)集合(包括路由表葉子集合及鄰居集合中的節點(diǎn))中選擇一個(gè)距離消息鍵值最近的節點(diǎn)作為轉發(fā)目標。
從上述過(guò)程中可以看出，每一步路由和上一步相比都更靠近目標節點(diǎn)，因此這個(gè)過(guò)程是收斂的。如果路由表不為空，每步路由至少能夠增加一個(gè)前綴匹配數位，因此在路由表始終有效時(shí)，路由的步數至多為logBN。
討論
Pastry的路由利用了成熟的最大掩碼匹配算法，因此實(shí)現時(shí)可以利用很多現成的軟件算法和硬件框架，可以獲得很好的效率。
與Chord和CAN相比，Pastry引入了葉子節點(diǎn)和鄰居節點(diǎn)集合的概念。在應用層能夠及時(shí)準確地獲得這兩個(gè)集合的節點(diǎn)信息時(shí)，可以大大加快路由查找的速度，同時(shí)降低因路由引起的網(wǎng)絡(luò )傳輸開(kāi)銷(xiāo)；不過(guò)在動(dòng)態(tài)變化的P2P網(wǎng)絡(luò )中如何理想地做到這一點(diǎn)的確有很大的難度。
Pastry的典型應用包括PAST(參見(jiàn)[5][6])和SCRIBE(參見(jiàn)[7])。
趨勢分析
目前DHT算法的發(fā)展方向非常多，不斷有新的改進(jìn)算法被提出來(lái)。就筆者目前了解到的信息而言，至少有以下一些方向：
接近性(Proximity)
文中提到的DHT算法中，除了Pasrty以外，均未考慮重疊網(wǎng)絡(luò )拓撲結構與真實(shí)的IP網(wǎng)絡(luò )之間的重合關(guān)系。節點(diǎn)之間進(jìn)行對等通信時(shí)，不會(huì )考慮優(yōu)先選取距離自己最近的節點(diǎn)。這樣就使得最終形成的重疊網(wǎng)結構混亂，效率低下。因此如何讓節點(diǎn)獲得并利用接近性信息就非常重要。
結構化
目前基于DHT的應用尚未大規模展開(kāi)，很多工程上的細節問(wèn)題尚待解決。例如：目前有很多種類(lèi)的P2P應用，如文件存儲和共享、電子郵件、流媒體等。這些應用在處理P2P路由算法、拓撲維護和信息檢索上使用的方法均有很大差別，導致即使是同類(lèi)的應用也無(wú)法實(shí)現互通。如何為各種P2P的應用抽象出一個(gè)通用的層次，也是目前研究的熱點(diǎn)問(wèn)題之一。
信息查詢(xún)
基于分布式哈希表的查詢(xún)是一種單關(guān)鍵字的精確匹配，盡管相對于非結構化系統它使得系統資源可被確定性地查詢(xún)到，但它也極大地限制了查詢(xún)的應用范圍。目前有許多改進(jìn)的結構化查詢(xún)算法已經(jīng)被提出來(lái)。
參考文獻
David Karger, Eric Lehman, Tom Leighton, Matthew Levine, DanielLewin, Rina Panigrahy "Consistent Hashing and RandomTrees:Distributed Caching Protocols for Relieving Hot Spots on theWorld Wide Web". In Proceedings of the 29th Annual ACMSym-posium on Theory of Computing (El Paso, TX, May 1997), pp.654-663.
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, HariBalakrishnan_ "Chord: A Scalable Peertopeer Lookup Service forInternet Applications" SIGCOMM‘01, August 2731, 2001, SanDiego, California, USA.
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp,Scott Shenker "A Scalable Content-Addressable Network"SIGCOMM‘01, August 27-31, 2001, San Diego, California,USA..
Antony Rowstron1 and Peter Druschel "Pastry: Scalable,decentralized object location and routing for large-scalepeer-to-peer systems" Appears in Proc. of the 18th IFIP/ACMInternational Conference on Distributed Systems Platforms(Middleware 2001). Heidelberg, Germany, November 2001.
P. Druschel and A. Rowstron. PAST: A large-scale, persistentpeer-to-peer storage utility. In Proc. HotOS VIII, Schloss Elmau,Germany, May 2001.
A. Rowstron and P. Druschel. Storage management and caching inPAST, a large-scale, persistent peer-to-peer storage utility. InProc. ACM SOSP‘01, Banff, Canada, Oct. 2001.
A. Rowstron, A.-M. Kermarrec, P. Druschel, and M. Castro.Scribe: The design of a large-scale event notificationinfrastructure. Submitted for publication. June 2001.http://www.research.microsoft.com/ antr/SCRIBE/.
F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica.Wide-area cooperative storage with CFS. In Proc. ACM SOSP‘01,Banff, Canada, Oct. 2001.
Keith W. Ross, Dan Rubenstein, "P2P Systems"
寧寧，“對等網(wǎng)絡(luò )組通信機制的位置感知技術(shù)研究Research on Location-Aware Tech-nology inPeer-to-Peer Group Com-municationMechanism”，申請清華大學(xué)工學(xué)碩士學(xué)位論文，May.2005.
李祖鵬，黃建華，唐輝，“基于P2P計算模式的自組織網(wǎng)絡(luò )路由模型”，軟件學(xué)報，1000-9825/2005/16(05)0916
胡進(jìn)鋒，鄭緯民(清華大學(xué)計算機系高性能計算研究所，北京，100084)，“p2p系統結點(diǎn)信息收集算法 NodeCollection Protocol in P2P Systems”
鄒福泰，馬范援(上海交通大學(xué)計算機科學(xué)與工程系)，“基于分布式哈希表的對等系統關(guān)鍵技術(shù)研究RESEARCH ON THE KEYTECHNIQUE OF PEER-TO-PEER SYSTEMS BASED ON DISTRIBUTED HASHTABLE”，申請上海交通大學(xué)博士學(xué)位論文，二零零四年十一月
作者：陳嶺
聯(lián)系客服
