現有的P2P實(shí)現可以分為三種類(lèi)型。它們分別是：基于目錄服務(wù)器P2P，非結構化P2P和結構化P2P。基于目錄服務(wù)器這一類(lèi)系統中設置目錄服務(wù)器，用于保存用戶(hù)節點(diǎn)的地址信息和該節點(diǎn)上共享文件的描述信息，文件本身是分散存貯在各個(gè)節點(diǎn)上的，實(shí)際的文件傳輸也是在對等節點(diǎn)之間進(jìn)行，目錄服務(wù)器僅僅起到中介作用，為節點(diǎn)提供發(fā)布和查詢(xún)文件索引服務(wù)。鑒于集中式目錄服務(wù)器不僅可能成為系統的瓶頸，而且還可能引發(fā)法律糾紛，因此出現了以Gnutella為代表的非結構化P2P系統，在這種P2P結構中，文件索引信息不再由集中式的目錄服務(wù)器存儲和管理，而是分散到網(wǎng)絡(luò )中，由節點(diǎn)自己保存，該類(lèi)系統采用分布式的索引查找策略，為了查找網(wǎng)絡(luò )中的文件，節點(diǎn)要隨機地維護網(wǎng)絡(luò )中的其他一些節點(diǎn)作為鄰居，以便通過(guò)鄰居節點(diǎn)廣播查詢(xún)報文。非結構化P2P系統中由于不存在目錄服務(wù)器，所以沒(méi)有單點(diǎn)瓶頸問(wèn)題，不存在單一故障點(diǎn)。然而其缺點(diǎn)也是明顯的：在網(wǎng)絡(luò )中廣播查詢(xún)報文加重了網(wǎng)絡(luò )通信負擔，其查詢(xún)機制在系統規模擴大時(shí)不具有可擴展性。另外，由于查詢(xún)報文被限制在特定的范圍內，所以并不能保證一定可以找到網(wǎng)絡(luò )中存在的目的數據。上面介紹的兩類(lèi)P2P系統都缺乏有效的、可擴展的索引查找機制。為此，近年來(lái)許多研究小組在設計可擴展的查找機制方面做了大量的研究工作，提出了Chord、Pastry、CAN和Tapestry等用于構建結構化P2P的分布式哈希表系統（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每條文件索引被表示成一個(gè)(K, V)對，K稱(chēng)為關(guān)鍵字，可以是文件名（或文件的其他描述信息）的哈希值，V是實(shí)際存儲文件的節點(diǎn)的IP地址（或節點(diǎn)的其他描述信息）。所有的文件索引條目(即所有的（K, V）對)組成一張大的文件索引哈希表，只要輸入目標文件的K值，就可以從這張表中查出所有存儲該文件的節點(diǎn)地址。然后，再將上面的大文件哈希表分割成很多局部小塊，按照特定的規則把這些小塊的局部哈希表分布到系統中的所有參與節點(diǎn)上，使得每個(gè)節點(diǎn)負責維護其中的一塊。這樣，節點(diǎn)查詢(xún)文件時(shí)，只要把查詢(xún)報文路由到相應的節點(diǎn)即可（該節點(diǎn)維護的哈希表分塊中含有要查找的(K,V)對）。這里面有個(gè)很重要的問(wèn)題，就是節點(diǎn)要按照一定的規則來(lái)分割整體的哈希表，進(jìn)而也就決定了節點(diǎn)要維護特定的鄰居節點(diǎn)，以便路由能順利進(jìn)行。這個(gè)規則因具體系統的不同而不同，CAN，Chord，Pastry和Tapestry都有自己的規則，也就呈現出不同的特性?；诜植际焦１恚?/span>DHT）的分布式檢索和路由算法因為具有查找可確定性、簡(jiǎn)單性和分布性等優(yōu)點(diǎn)，正成為國際上結構化P2P網(wǎng)絡(luò )研究和應用的熱點(diǎn)。自2002年起，美國國家科學(xué)基金會(huì )（NSF）提供了1200萬(wàn)美元的資金啟動(dòng)了一個(gè)為期5年的研究項目IRIS，該項目集中了MIT和UC Berkeley等5所著(zhù)名高等院校的強大科研力量，為下一代大規模分布式應用研制基于DHT的新型基礎設施。
分布式哈希表在節點(diǎn)失效、遭受攻擊和突發(fā)性高負載面前都能表現出很好的健壯性；它具有良好的可擴展性，能以較低系統開(kāi)銷(xiāo)獲得較大的系統規模；可以自我配置，不需要手工干預就可以自動(dòng)把新加入節點(diǎn)合并到系統中；能提供簡(jiǎn)單靈活的接口，可以為多個(gè)P2P應用同時(shí)使用。
1 Chord
Chord是UC Berkeley和MIT共同提出的一種分布式查找算法，目的是為了能在P2P網(wǎng)絡(luò )中查找數據。給定一個(gè)關(guān)鍵字，Chord可以有效地把該關(guān)鍵字映射到網(wǎng)絡(luò )中某個(gè)節點(diǎn)上。因而在P2P網(wǎng)絡(luò )中只要給每個(gè)數據V都賦予一個(gè)關(guān)鍵字K，就可以利用Chord在該關(guān)鍵字映射的節點(diǎn)上存儲或提取相應的(K, V)對。Chord的突出特點(diǎn)是算法簡(jiǎn)單，而且可擴展 － 查詢(xún)過(guò)程的通信開(kāi)銷(xiāo)和節點(diǎn)維護的狀態(tài)隨著(zhù)系統總節點(diǎn)數增加成指數關(guān)系。Chord的路由性能優(yōu)于CAN，而節點(diǎn)加入過(guò)程和維護開(kāi)銷(xiāo)又優(yōu)于Tapestry和Pastry。
Chord的設計:Chord中每個(gè)關(guān)鍵字和節點(diǎn)都分別擁有一個(gè)m比特的標識符。關(guān)鍵字標識符K通過(guò)哈希關(guān)鍵字本身得到，而節點(diǎn)標識符N則通過(guò)哈希節點(diǎn)的IP地址得到。哈希函數可以選用SHA-1。所有節點(diǎn)按照其節點(diǎn)標識符從小到大（取模2m后）沿著(zhù)順時(shí)針?lè )较蚺帕性谝粋€(gè)邏輯的標識圓環(huán)上（稱(chēng)為Chord環(huán)）。Chord的映射規則是：關(guān)鍵字標識為K的(K, V)對存儲在這樣的節點(diǎn)上，該節點(diǎn)的節點(diǎn)標識等于K或者在Chord環(huán)上緊跟在K之后，這個(gè)節點(diǎn)被稱(chēng)為K的后繼節點(diǎn)，表示為successor(K)。因為標識符采用m位二進(jìn)制數表示，并且從0到2m－1順序排列成一個(gè)圓圈，succesor(K)就是從K開(kāi)始順時(shí)針?lè )较蚓嚯xK最近的節點(diǎn)。
上圖給出了一個(gè)m=6的Chord環(huán)，環(huán)中分布了10個(gè)節點(diǎn)，存儲了5個(gè)關(guān)鍵字，節點(diǎn)標識前加上N而關(guān)鍵字前加上K以示區別。因為successor(10)=14，所以關(guān)鍵字10存儲到節點(diǎn)14上。同理，關(guān)鍵字24和30存儲到節點(diǎn)32上，關(guān)鍵字38存儲到節點(diǎn)38上，而關(guān)鍵字54則存儲到節點(diǎn)56上。當網(wǎng)絡(luò )中的參與節點(diǎn)發(fā)生變動(dòng)時(shí)，上面的映射規則仍然要成立。為此，當某節點(diǎn)n加入網(wǎng)絡(luò )時(shí)，某些原來(lái)分配給n的后繼節點(diǎn)的關(guān)鍵字將分配給n。當節點(diǎn)n離開(kāi)網(wǎng)絡(luò )時(shí)，所有分配給它的關(guān)鍵字將重新分配給n的后繼節點(diǎn)。除此之外，網(wǎng)絡(luò )中不會(huì )發(fā)生其他的變化。以上圖為例，當標識為26的節點(diǎn)接入時(shí)，原有標識為32的節點(diǎn)負責的標識為24的關(guān)鍵字將轉由新節點(diǎn)存儲。顯然，為了能在系統中轉發(fā)查詢(xún)報文，每個(gè)節點(diǎn)要了解并維護chord環(huán)上相鄰節點(diǎn)的標識和IP地址，并用這些信息構成自身的路由表。有了這張表，Chord就可以在環(huán)上任意兩點(diǎn)間進(jìn)行尋路。
Chord的路由：Chord中每個(gè)節點(diǎn)只要維護它在環(huán)上的后繼節點(diǎn)的標識和IP地址就可以完成簡(jiǎn)單的查詢(xún)過(guò)程。對特定關(guān)鍵字的查詢(xún)報文可以通過(guò)后繼節點(diǎn)指針在圓環(huán)上傳遞，直到到達這樣一個(gè)節點(diǎn)：關(guān)鍵字的標識落在該節點(diǎn)標識和它的后繼節點(diǎn)標識之間，這里的后繼節點(diǎn)就是存儲目標(K, V)對的節點(diǎn)。
上圖給出了一個(gè)示例，節點(diǎn)8發(fā)起的查找關(guān)鍵字54的請求，通過(guò)后繼節點(diǎn)依次傳遞，最后定位到存儲有關(guān)鍵字54的節點(diǎn)56。在這種簡(jiǎn)單查詢(xún)方式中，每個(gè)節點(diǎn)需要維護的狀態(tài)信息很少，但查詢(xún)速度太慢。若網(wǎng)絡(luò )中有N個(gè)節點(diǎn)，查詢(xún)的代價(jià)就為O（N）數量級。因而在網(wǎng)絡(luò )規模很大時(shí)，這樣的速度是不能接受的。
為了加快查詢(xún)的速度，Chord使用擴展的查詢(xún)算法。為此，每個(gè)節點(diǎn)需要維護一個(gè)路由表，稱(chēng)為指針表（finger table）。如果關(guān)鍵字和節點(diǎn)標識符用m位二進(jìn)制位數表示，那么指針表中最多含有m個(gè)表項。節點(diǎn)n的指針表中第i項是圓環(huán)上標識大于或等于n+2i-1的第一個(gè)節點(diǎn)（比較是以2m為模進(jìn)行的）。例如若s=successor(n+2i-1), 1≤i≤m，則稱(chēng)節點(diǎn)s為節點(diǎn)n的第i個(gè)指針，記為n.finger[i]。n.finger[1]就是節點(diǎn)n的后繼節點(diǎn)。指針表中每一項既包含相關(guān)節點(diǎn)的標識，又包含該節點(diǎn)的IP地址（和端口號）。
上圖給出了節點(diǎn)8的指針表，例如節點(diǎn)14是環(huán)上緊接在(8+20) mod 26=9之后的第一個(gè)節點(diǎn)，所以節點(diǎn)8的第一個(gè)指針是節點(diǎn)14；同理因為節點(diǎn)42是環(huán)上緊接在(8+25) mod 26=40之后的第一個(gè)節點(diǎn)，所以節點(diǎn)8的第6個(gè)指針是節點(diǎn)42。維護指針表使得每個(gè)節點(diǎn)只需要知道網(wǎng)絡(luò )中一小部分節點(diǎn)的信息，而且離它越近的節點(diǎn)，它就知道越多的信息。但是，對于任意一個(gè)關(guān)鍵字K，節點(diǎn)通常無(wú)法根據自身的指針表確定的K的后繼節點(diǎn)。例如，下圖中的節點(diǎn)8就不能確定關(guān)鍵字34的后繼節點(diǎn)，因為環(huán)上34的后繼節點(diǎn)是38，而節點(diǎn)38并沒(méi)有出現在節點(diǎn)8的指針表中。 擴展的查詢(xún)過(guò)程是：任何一個(gè)節點(diǎn)收到查詢(xún)關(guān)鍵字K的請求時(shí)，首先檢查關(guān)K是否落在該節點(diǎn)標識和它的后繼節點(diǎn)標識之間，如果是的話(huà)，這個(gè)后繼節點(diǎn)就是存儲目標(K, V)對的節點(diǎn)。否則，節點(diǎn)將查找它的指針表，找到表中節點(diǎn)標識符最大但不超過(guò)K的第一個(gè)節點(diǎn)，并將這個(gè)查詢(xún)請求轉發(fā)給該節點(diǎn)。通過(guò)重復這個(gè)過(guò)程，最終可以定位到K的后繼節點(diǎn)，即存儲有目標(K, V)對的節點(diǎn)。
節點(diǎn)加入和退出：為了應對系統的變化，每個(gè)節點(diǎn)都周期性地運行探測協(xié)議來(lái)檢測新加入節點(diǎn)或失效節點(diǎn)，從而更新自己的指針表和指向后繼節點(diǎn)的指針。新節點(diǎn)n加入時(shí)，將通過(guò)系統中現有的節點(diǎn)來(lái)初始化自己的指針表。也就是說(shuō)，新節點(diǎn)n將要求已知的系統中某節點(diǎn)為它查找指針表中的各個(gè)表項。在其他節點(diǎn)運行探測協(xié)議后，新節點(diǎn)n將被反映到相關(guān)節點(diǎn)的指針表和后繼節點(diǎn)指針中。這時(shí)，系統中一部分關(guān)鍵字的后繼節點(diǎn)也變?yōu)樾鹿濣c(diǎn)n，因而先前的后繼節點(diǎn)要將這部分關(guān)鍵字轉移到新節點(diǎn)上。當節點(diǎn)n失效時(shí)，所有指針表中包括n的節點(diǎn)都必須把它替換成n的后繼節點(diǎn)。為了保證節點(diǎn)n的失效不影響系統中正在進(jìn)行的查詢(xún)過(guò)程，每個(gè)Chord節點(diǎn)都維護一張包括r個(gè)最近后繼節點(diǎn)的后繼列表。如果某個(gè)節點(diǎn)注意到它的后繼節點(diǎn)失效了，它就用其后繼列表中第一個(gè)正常節點(diǎn)替換失效節點(diǎn)。
2 Pastry
Microsoft研究院和Rice大學(xué)共同提出的Pastry是用于廣域P2P應用的分布式查找和路由系統。Pastry系統中的每個(gè)節點(diǎn)都有一個(gè)唯一的節點(diǎn)號（nodeId），每條消息都有一個(gè)關(guān)鍵字。Pastry可以把消息路由到nodeId和關(guān)鍵字在數值上最接近的那個(gè)節點(diǎn)。每個(gè)Pastry節點(diǎn)維護節點(diǎn)號空間中和它直接相鄰的鄰居節點(diǎn)信息。當發(fā)生新節點(diǎn)加入、已有節點(diǎn)失效或恢復事件時(shí)，Pastry節點(diǎn)會(huì )通知上層應用。Pastry是完全分布式的、可擴展的和自組織的，它能夠自動(dòng)應對節點(diǎn)加入、離開(kāi)和失效。
Pastry的設計：Pastry是自組織的重疊網(wǎng)絡(luò )，每個(gè)節點(diǎn)都被分配一個(gè)128位的nodeId。nodeId用于在圓形的節點(diǎn)空間中（從0到2128－1）標識節點(diǎn)的位置，它是在節點(diǎn)加入系統時(shí)隨機分配的，隨機分配的結果是使得所有的nodeId在128位的節點(diǎn)號空間中均勻分布。nodeId可以通過(guò)計算節點(diǎn)公鑰或者IP地址的哈希函數值來(lái)獲得。
假設網(wǎng)絡(luò )包含N個(gè)節點(diǎn)，Pastry可以把一個(gè)給定的關(guān)鍵字路由到nodeId和該關(guān)鍵字最接近的節點(diǎn)。即使同時(shí)發(fā)生節點(diǎn)失效，Pastry也可以保證關(guān)鍵字送達目標節點(diǎn)，除非nodeId和關(guān)鍵字臨近的節點(diǎn)中有|L|/2個(gè)同時(shí)失效（|L|是配置參數，典型值取16或32）。為了進(jìn)行路由，Pastry把nodeId和關(guān)鍵字表示為一串以2b為基的數，查詢(xún)消息被路由到nodeId和關(guān)鍵字在數值上最接近的節點(diǎn)。方法是：每個(gè)節點(diǎn)把查詢(xún)消息轉發(fā)給下一個(gè)節點(diǎn)時(shí)，要保證這個(gè)節點(diǎn)的nodeId和關(guān)鍵字的相同前綴至少要比當前節點(diǎn)的nodeId和關(guān)鍵字的相同前綴長(cháng)一個(gè)數位（即b個(gè)比特）。如果找不到這樣的鄰居節點(diǎn)，消息將轉發(fā)給前綴長(cháng)度相同但是節點(diǎn)號數值更接近關(guān)鍵字的節點(diǎn)。為此，每個(gè)Pastry節點(diǎn)都需要維護狀態(tài)表：一張路由表，一個(gè)鄰居節點(diǎn)集和一個(gè)葉子節點(diǎn)集。
nodeId為10233102的Pastry節點(diǎn)維護的狀態(tài)示意圖
上圖給出了一個(gè)節點(diǎn)維護的數據示意圖，b取值為2，所有的數均是4進(jìn)制的。其中路由表的最上面一行是第0行。路由表中每行的陰影項表示當前節點(diǎn)號中相應的數位。路由表中每項節點(diǎn)的nodeId表示格式是“相同前綴 ＋ 下一數位 ＋ nodeId的剩余位”。圖中沒(méi)有列出相關(guān)節點(diǎn)的IP地址。
路由表每行包括2b-1個(gè)表項。第n行的2b-1個(gè)表項中，每個(gè)節點(diǎn)nodeId的前n個(gè)數位和當前節點(diǎn)nodeId的前n個(gè)數位相同，而第n＋1個(gè)數位和當前節點(diǎn)不同。b的取值是路由表大小和任意兩節點(diǎn)間需要的最大路由跳數之間的折衷。例如，當b取4而網(wǎng)絡(luò )中有106 個(gè)節點(diǎn)時(shí)，每個(gè)節點(diǎn)的路由表平均包括75個(gè)表項，預期的路由跳數是5。如果網(wǎng)絡(luò )中有109個(gè)節點(diǎn)，則路由表平均會(huì )有105項，而預期的路由步數也將增加到7。
葉子節點(diǎn)集維護的是nodeId和本節點(diǎn)最接近的節點(diǎn)，其中一半是nodeId大于當前節點(diǎn)的，另一半是nodeId小于當前節點(diǎn)的。葉子節點(diǎn)集在路由時(shí)需要用到。鄰居節點(diǎn)集維護按給定的評測指標距離本節點(diǎn)最近的節點(diǎn)，正常的路由過(guò)程并不使用鄰居節點(diǎn)集，它的主要作用是維護路由的本地性。通常這兩個(gè)集合的大小分別為2b或者2×2b。
Pastry的路由過(guò)程是：節點(diǎn)收到一條查詢(xún)消息時(shí)，首先檢查該消息的關(guān)鍵字是否落在葉子節點(diǎn)集范圍內。如果是，則直接把消息轉發(fā)給對應的節點(diǎn)，也就是葉子節點(diǎn)集中nodeId和關(guān)鍵字最接近的節點(diǎn)。如果關(guān)鍵字沒(méi)有落在葉子節點(diǎn)集范圍內，節點(diǎn)就會(huì )把消息轉發(fā)給路由表中的一個(gè)節點(diǎn)，該節點(diǎn)的nodeId和關(guān)鍵字的相同前綴至少要比當前節點(diǎn)的nodeId和關(guān)鍵字的相同前綴長(cháng)一個(gè)數位。如果路由表中相應的表項為空，或者表項中對應的節點(diǎn)不可達，這時(shí)候查詢(xún)消息將被轉發(fā)給前綴長(cháng)度相同但是節點(diǎn)號數值更接近關(guān)鍵字的節點(diǎn)。除非消息已經(jīng)到達目的節點(diǎn)，否則這樣的節點(diǎn)一定位于葉子節點(diǎn)集中。而且，只要葉子節點(diǎn)集中一半以上的節點(diǎn)不同時(shí)失效，就一定可以找到滿(mǎn)足要求的節點(diǎn)。很明顯，路由的每一步都比上一步向目標節點(diǎn)前進(jìn)了一步，因此路由過(guò)程總是收斂的。
節點(diǎn)加入和退出
新節點(diǎn)加入時(shí)需要初始化自身的狀態(tài)表，并通知其他節點(diǎn)自己已經(jīng)加入系統。假定新加入節點(diǎn)的nodeId為X，同時(shí)假定X在加入Pastry之前知道系統中和自己距離相近的節點(diǎn)A。新節點(diǎn)X首先請求A路由一條“加入”消息，消息的關(guān)鍵字就是X。這條消息最終會(huì )到達nodeId和X最接近的節點(diǎn)Z。作為應答，節點(diǎn)A、節點(diǎn)Z以及從A到Z的路徑上所有經(jīng)過(guò)的節點(diǎn)都會(huì )把自己的狀態(tài)表發(fā)送給節點(diǎn)X。節點(diǎn)X利用這些信息初始化自己的狀態(tài)表，然后節點(diǎn)X再通知其他節點(diǎn)它已經(jīng)加入了系統。從交換的消息數量上說(shuō)，節點(diǎn)加入操作的復雜度為O（log2bN）。
Pastry中節點(diǎn)很可能失效或者突然離開(kāi)系統。若nodeId空間中的相鄰節點(diǎn)無(wú)法和某個(gè)節點(diǎn)通信時(shí)，就認為該節點(diǎn)失效了。一旦節點(diǎn)檢測出其葉子節點(diǎn)集L中的某個(gè)節點(diǎn)失效，它就會(huì )請求該集合中nodeId最大或最小的節點(diǎn)把其葉子節點(diǎn)集L’發(fā)送過(guò)來(lái)。（如果失效節點(diǎn)的nodeId比當前節點(diǎn)的nodeId大，則用葉子集中nodeId最大的節點(diǎn)，反之則用nodeId最小的節點(diǎn)。）當前節點(diǎn)將從L’中選擇一個(gè)L中沒(méi)有的活動(dòng)節點(diǎn)來(lái)替代失效節點(diǎn)。如果節點(diǎn)檢測出其路由表中某項對應的節點(diǎn)失效，它將從該項所在的路由表行中選擇另一個(gè)節點(diǎn)，要求該節點(diǎn)把路由表中對應位置的項發(fā)過(guò)來(lái)。如果當前節點(diǎn)的路由表中對應行已經(jīng)沒(méi)有可用節點(diǎn)了，那么當前節點(diǎn)將從路由表的下一行中選擇一個(gè)節點(diǎn)，這個(gè)過(guò)程將繼續到當前節點(diǎn)能夠得到一個(gè)替代失效節點(diǎn)的節點(diǎn)號，或者當前節點(diǎn)遍歷了路由表為止。節點(diǎn)也會(huì )周期性地和鄰居節點(diǎn)集中的節點(diǎn)交換信息以檢測這些節點(diǎn)是否仍在Pastry系統中，如果節點(diǎn)檢測出其鄰居節點(diǎn)集中的某個(gè)節點(diǎn)失效，它將請求其他鄰居節點(diǎn)把其鄰居節點(diǎn)集發(fā)送過(guò)來(lái)并從中選擇一個(gè)新的鄰居節點(diǎn)替換失效節點(diǎn)。
3 CAN
UC Berkeley提出的CAN（Content Addressable Network，內容尋址網(wǎng)絡(luò )）實(shí)現了文件索引和存放位置的有效映射，不需要任何形式的中央控制點(diǎn)，節點(diǎn)只需要維護少量的控制狀態(tài)而且狀態(tài)數量獨立于系統中的節點(diǎn)數量，具有完全自組織和分布式的結構，并且有良好的可擴展性和容錯性。
CAN的設計
CAN的設計基于虛擬的d維笛卡兒坐標空間，這個(gè)坐標空間完全是邏輯的，和任何物理坐標系統都沒(méi)有關(guān)系。在任何時(shí)候，整個(gè)坐標空間動(dòng)態(tài)地分配給系統中的所有節點(diǎn)，每個(gè)節點(diǎn)負責維護獨立的互不相交的一塊區域。CAN中的節點(diǎn)自組織成一個(gè)代表這個(gè)虛擬坐標空間的重疊網(wǎng)絡(luò )（overlay network）。每個(gè)節點(diǎn)要了解并維護相鄰區域中節點(diǎn)的IP地址,用這些鄰居信息構成自身的坐標路由表。有了這張表，CAN可以在坐標空間中任意兩點(diǎn)間進(jìn)行尋路。
下圖給出了一個(gè)2維的[0, 1]×[0, 1]的笛卡兒坐標空間劃分成五個(gè)節點(diǎn)區域的情況。虛擬坐標空間采用下面的方法保存（K, V）對。當保存（K1, V1）時(shí)，使用統一的哈希函數把關(guān)鍵字K1映射成坐標空間中的點(diǎn)P。那么這個(gè)值將被保存在該點(diǎn)所在區域的節點(diǎn)中。當需要查詢(xún)關(guān)鍵字K1對應的值時(shí)，任何節點(diǎn)都可以使用同樣的哈希函數找到K1對應的點(diǎn)P，然后從該點(diǎn)對應的節點(diǎn)取出相應的值V1。如果此節點(diǎn)不是發(fā)起查詢(xún)請求的節點(diǎn)，CAN將負責將此查詢(xún)請求轉發(fā)到P所在區域的節點(diǎn)上。因此，有效的路由機制是CAN中的一個(gè)關(guān)鍵問(wèn)題。
五個(gè)節點(diǎn)維護的CAN虛平面
CAN的路由
CAN中的路由很簡(jiǎn)單，沿著(zhù)坐標空間中從發(fā)起請求的點(diǎn)到目的點(diǎn)之間的一條路徑轉發(fā)即可。為此，每個(gè)CAN節點(diǎn)都要保存一張坐標路由表，其中包括它的鄰居節點(diǎn)的IP地址和其維護的虛擬坐標區域。兩個(gè)節點(diǎn)互為鄰居是指：在d維坐標空間中，兩個(gè)節點(diǎn)維護的區域在d－1維的坐標上有重疊而在剩下的一維坐標上相互鄰接。例如，圖2.6中D和E是鄰接節點(diǎn)，而D和B就不是鄰接節點(diǎn), 因為D和B在X軸和Y軸上都鄰接。每條CAN消息都包括目的點(diǎn)坐標。路由時(shí)節點(diǎn)只要朝著(zhù)目標節點(diǎn)的方向把消息轉發(fā)給自己的鄰居節點(diǎn)即可。下圖給出了查找過(guò)程的一個(gè)簡(jiǎn)單的例子。
如果一個(gè)d維空間劃分成n個(gè)相等的區域，那么平均路由長(cháng)度是(d/4)(n1/d)，每個(gè)節點(diǎn)只需要維護2d個(gè)鄰居節點(diǎn)的信息。這個(gè)結果表明CAN的可擴展性很好，節點(diǎn)數增加時(shí)每個(gè)節點(diǎn)維護的狀態(tài)信息不變，而路由長(cháng)度只是以O（n1/d）的數量級增長(cháng)。因為坐標空間中兩點(diǎn)之間可以有許多條不同的路徑，所以單個(gè)節點(diǎn)的失效對CAN基本上沒(méi)有太大的影響。遇到失效節點(diǎn)時(shí)，CAN會(huì )自動(dòng)沿著(zhù)其他的路徑進(jìn)行路由。
節點(diǎn)加入和退出
因為整個(gè)CAN空間要分配給系統中現有的全部節點(diǎn)，當一個(gè)新的節點(diǎn)加入網(wǎng)絡(luò )時(shí)必須得到自己的一塊坐標空間。CAN通過(guò)分割現有的節點(diǎn)區域實(shí)現這一過(guò)程。它把某個(gè)現有節點(diǎn)的區域分裂成同樣大小的兩塊，自己保留其中的一塊而另一塊分給新加入的節點(diǎn)。整個(gè)過(guò)程分為以下三步：
1. 新節點(diǎn)首先找到一個(gè)已經(jīng)在CAN中的節點(diǎn)。
2. 新節點(diǎn)使用CAN的路由機制找到一個(gè)區域將要被分割的節點(diǎn)。
3. 執行分割操作，然后原有區域的鄰接區域必須被告知發(fā)生了分割，這樣新節點(diǎn)才能被別的節點(diǎn)路由到。
當節點(diǎn)離開(kāi)CAN時(shí)，必須保證它的區域被系統中剩余的節點(diǎn)接管，也即分配給其他仍然在系統中的節點(diǎn)。一般是由某個(gè)鄰居節點(diǎn)來(lái)接管這個(gè)區域和所有的索引數據（K，V）對。如果某個(gè)鄰居節點(diǎn)負責的區域可以和離開(kāi)節點(diǎn)負責的區域合并形成一個(gè)大的區域，那么將由這個(gè)鄰居節點(diǎn)執行合并操作。否則，該區域將交給其鄰居節點(diǎn)中區域最小的節點(diǎn)負責。也就是說(shuō)，這個(gè)節點(diǎn)將臨時(shí)負責兩個(gè)區域。
正常情況下，每個(gè)節點(diǎn)向其所有鄰居節點(diǎn)發(fā)送周期性的更新消息，消息中包括自身的區域范圍、它的鄰居列表以及這些鄰居節點(diǎn)負責的區域范圍。如果多次沒(méi)有接收到某個(gè)鄰居的更新消息，那么節點(diǎn)就認為這個(gè)鄰居失效了。這時(shí)，節點(diǎn)將啟動(dòng)接管機制，并啟動(dòng)一個(gè)時(shí)鐘。失效節點(diǎn)的每個(gè)鄰居節點(diǎn)相互獨立地執行該過(guò)程，每個(gè)時(shí)鐘大小都和相應節點(diǎn)負責的區域面積成比例。如果時(shí)鐘超時(shí)，節點(diǎn)將向失效節點(diǎn)的所有鄰居節點(diǎn)發(fā)送接管消息，該消息中包括它自己的區域面積信息。當某個(gè)節點(diǎn)接收到接管消息后，如果它的區域面積比發(fā)出消息的節點(diǎn)大，那么它將取消接管操作。否則它將發(fā)出自己的取代消息。采用這種機制可以有效地選擇面積最小的鄰居節點(diǎn)來(lái)接管失效節點(diǎn)。在特殊情況下，還有可能出現多個(gè)相鄰的節點(diǎn)同時(shí)失效的情況。例如，節點(diǎn)檢測到某個(gè)節點(diǎn)失效，但是失效節點(diǎn)地鄰居中超過(guò)一半可能都不可達。這時(shí)，如果讓該節點(diǎn)接管失效節點(diǎn)地區域，就有可能導致CAN中狀態(tài)不一致。所以在這種情況下，CAN在執行修復操作之前，會(huì )搜索失效區域附近的節點(diǎn)，搜索逐步擴大直至獲得足夠的鄰居狀態(tài)，以便安全地開(kāi)始接管過(guò)程。
4 Tapestry
Tapestry是UC Berkeley提出的一種新型的P2P網(wǎng)絡(luò )定位和路由算法。該算法可以對消息進(jìn)行與位置無(wú)關(guān)的路由，把查詢(xún)消息傳遞到最近的存儲有目標對象拷貝的節點(diǎn)。Tapestry具有自組織、容錯和負載平衡等特點(diǎn)。每個(gè)Tapestry 節點(diǎn)只需維護O（log N）大小的路由表信息，路由最多在O（log N）跳數內完成。
Tapestry的設計
Tapestry從一個(gè)標識符空間中為每個(gè)節點(diǎn)隨機分配一個(gè)節點(diǎn)標識符nodeID，對象也從同一個(gè)標識符空間中分配一個(gè)全局唯一標識符GUID（globally unique identifier）。Tapestry使用SHA-1來(lái)產(chǎn)生標識符，使得nodeID和GUID均勻分布在標識符空間中。為了討論問(wèn)題的方便，用Nid來(lái)表示節點(diǎn)N的標識符，用OG表示對象O的標識符。Tapestry目前使用160比特的標識符空間，標識符用一個(gè)全局統一的進(jìn)制表示（例如使用16進(jìn)制，則標識符是一個(gè)40位的數字），所有的節點(diǎn)依據標識符自組織成一個(gè)重疊網(wǎng)絡(luò )。
Tapestry動(dòng)態(tài)地把每個(gè)標識符G映射到當前系統中一個(gè)節點(diǎn)上，該節點(diǎn)稱(chēng)為G的根節點(diǎn)，表示為GR。如果某節點(diǎn)的Nid＝G，則這個(gè)節點(diǎn)就是G的根節點(diǎn)。為了轉發(fā)查詢(xún)消息，每個(gè)節點(diǎn)需要維護一個(gè)鄰居映射表，每個(gè)表項包括一個(gè)鄰居節點(diǎn)的標識符和IP地址。往GR路由時(shí)，消息將沿著(zhù)鄰居指針向節點(diǎn)標識符在標識符空間中更接近G的節點(diǎn)轉發(fā)（例如，匹配更大的前綴）。
Tapestry中的每個(gè)節點(diǎn)都保存有鄰居映射表。鄰居映射表可以用于把消息按照目的地址一位一位地向前傳遞，比如從4***=>42**98=>42A*=>目的節點(diǎn)42AD（這里*表示通配符）。這種方式類(lèi)似于IP分組轉發(fā)過(guò)程中的最長(cháng)前綴匹配。節點(diǎn)N的鄰居映射表分為多個(gè)級別，每個(gè)級別包含的鄰居節點(diǎn)的數量等于標識符表示法的基數，而每個(gè)級別中鄰居節點(diǎn)標識符和本節點(diǎn)標識符的相同前綴都比前一級別多一個(gè)數位。也就是說(shuō)，第j級鄰居表的第i項是標識符以prefix(N, j-1) ＋ “i”為前綴而且離當前節點(diǎn)最近的鄰居節點(diǎn)。例如，節點(diǎn)325AE的鄰居映射表中第4級第9項是系統中標識符以325 + “9” =3259為前綴的某個(gè)節點(diǎn)。
上圖給出了一個(gè)節點(diǎn)的鄰居指針實(shí)例，從圖中可以看到第一級的鄰居節點(diǎn)標識和本節點(diǎn)標識沒(méi)有共同前綴，而第二級的鄰居節點(diǎn)標識都以4開(kāi)頭，即和本節點(diǎn)標識具有相同的一個(gè)數位的前綴。
Tapestry采用的基本查找和路由機制：當一條查找消息到達傳遞過(guò)程中的第n個(gè)節點(diǎn)時(shí)，該節點(diǎn)和目的節點(diǎn)的共同前綴長(cháng)度至少大于n。為了進(jìn)行轉發(fā)，該節點(diǎn)將查找鄰居映射表的第n+1級中和目的標識符下一數位相匹配的鄰居節點(diǎn)。轉發(fā)過(guò)程將在每個(gè)節點(diǎn)中依次進(jìn)行直到到達目的節點(diǎn)。這種方法可以保證路由至多經(jīng)過(guò)logbN個(gè)節點(diǎn)就可以到達目的節點(diǎn)，這里N是節點(diǎn)標識符名字空間的大小，而b是標識符使用的基數。同樣，由于每個(gè)節點(diǎn)的鄰居映射表的每個(gè)級別只需要保存b個(gè)表項，因此，鄰居映射表的空間為blogbN。
上圖給出了Tapestry中一個(gè)查詢(xún)消息轉發(fā)的例子。圖中節點(diǎn)標識符的基數是4，查詢(xún)消息從5230發(fā)出，目的節點(diǎn)是42AD。
Tapestry中的節點(diǎn)在共享數據時(shí)被稱(chēng)為服務(wù)器，請求數據時(shí)被稱(chēng)為客戶(hù)，轉發(fā)消息時(shí)被稱(chēng)為路由器。也就是說(shuō)每個(gè)節點(diǎn)可以同時(shí)具有客戶(hù)、服務(wù)器和路由器的功能。
服務(wù)器S通過(guò)向對象O（GUID為OG）的根節點(diǎn)OR定期的發(fā)送消息來(lái)報告S保存有對象O。在這條發(fā)布路徑上的每個(gè)節點(diǎn)都保存關(guān)于這個(gè)對象O的位置信息指針<OG, S>，這里的位置信息只是一個(gè)指向S的指針，而并不是對象O的拷貝。當多個(gè)都存有同一對象拷貝的服務(wù)器分別向根結點(diǎn)發(fā)布消息時(shí)，路徑上的每個(gè)節點(diǎn)按各個(gè)服務(wù)器離自己的網(wǎng)絡(luò )時(shí)延遞增的順序保存這些位置指針列表。
當需要定位一個(gè)對象O時(shí)，客戶(hù)向對象O的根節點(diǎn)發(fā)出查詢(xún)消息，查詢(xún)消息轉發(fā)路徑上的每個(gè)節點(diǎn)都檢查自己是否存有對象O的位置指針，如果有，該節點(diǎn)直接把查詢(xún)消息轉發(fā)個(gè)服務(wù)器S，否則，消息將到達O的根節點(diǎn)，然后由根節點(diǎn)把查詢(xún)消息轉發(fā)給服務(wù)器。
Tapestry有一個(gè)重要的特性是：查詢(xún)消息可以被轉發(fā)到距離客戶(hù)最近的存有對象拷貝的服務(wù)器上。在Tapestry中，從兩個(gè)臨近節點(diǎn)向同一個(gè)目的節點(diǎn)OR發(fā)出兩條消息時(shí)，它們的轉發(fā)路徑很快就會(huì )交叉，這是因為路由過(guò)程的每一步都是使得下一個(gè)節點(diǎn)標識符和OR具有更長(cháng)的相同前綴；到根結點(diǎn)的路徑只是目的標識符的函數，而不是消息發(fā)起節點(diǎn)標識符的函數；而且，路由過(guò)程中的下一跳鄰居節點(diǎn)是根據網(wǎng)絡(luò )距離選擇的，因而客戶(hù)離服務(wù)器越近，那么查詢(xún)路徑碰到發(fā)布路徑的速度就越快。也就是說(shuō)，查詢(xún)消息會(huì )被轉發(fā)到最近的服務(wù)器上。
節點(diǎn)加入和退出：Tapestry的節點(diǎn)加入算法和Pastry類(lèi)似。節點(diǎn)N在加入Tapestry網(wǎng)絡(luò )之前，也需要知道一個(gè)已經(jīng)在網(wǎng)絡(luò )中的節點(diǎn)G。然后N通過(guò)G發(fā)出路由自己的節點(diǎn)ID的請求，根據經(jīng)過(guò)的節點(diǎn)的對應的鄰居節點(diǎn)表構造自己的鄰居節點(diǎn)表。構造過(guò)程中還需要進(jìn)行一些優(yōu)化工作。構造完自己的數據結構后，節點(diǎn)N將通知網(wǎng)絡(luò )中的其他節點(diǎn)自己已經(jīng)加入網(wǎng)絡(luò )。通知只針對在N的鄰居映射表中的主鄰居節點(diǎn)和二級鄰居節點(diǎn)進(jìn)行。
Tapestry采用兩種機制處理節點(diǎn)的退出。一種情況是節點(diǎn)從網(wǎng)絡(luò )中自行消失（主要原因是節點(diǎn)失效），在這種情況下，它的鄰居可以檢測到它已經(jīng)退出網(wǎng)絡(luò )并可以相應的調整路由表。另一種機制是節點(diǎn)在退出系統之前通過(guò)后向指針通過(guò)所有把它作為鄰居的節點(diǎn)，這些節點(diǎn)會(huì )相應調整路由表并通知對象服務(wù)器該節點(diǎn)已經(jīng)退出網(wǎng)絡(luò )。檢測正常操作過(guò)程中的鏈路和服務(wù)器失效，可以使用TCP連接超時(shí)機制。除此之外，每個(gè)Tapestry節點(diǎn)都使用后向指針周期性的發(fā)送“心跳”(heartbeats)UDP分組給把自己加入鄰居映射表的節點(diǎn)。每個(gè)節點(diǎn)都可以根據自己收到的心跳分組來(lái)決定自己的鄰居映射表中是否有節點(diǎn)失效。在鄰居節點(diǎn)表中，除了主鄰居節點(diǎn)（最近的鄰居）之外，每個(gè)路由項還保存了兩個(gè)備份的鄰居節點(diǎn)，當檢測到主鄰居節點(diǎn)失效后，鄰居節點(diǎn)表將順序選擇備份鄰居節點(diǎn)。
