Petar Maymounkov and David Mazi`eres
fpetar,dmg@cs.nyu.edu
?
摘要
本文我們將描述一個(gè)在容易出錯(cuò)的網(wǎng)絡(luò)環(huán)境中擁有可證實(shí)的穩(wěn)定性和高性能穩(wěn)定性的點(diǎn)對(duì)點(diǎn)(P2P)系統(tǒng)。我們的系統(tǒng)使用一個(gè)很新穎的基于異或運(yùn)算的拓?fù)鋪?lái)發(fā)送查詢并且定位節(jié)點(diǎn), 這簡(jiǎn)化了算法并且使驗(yàn)證更加容易。 這種拓?fù)浣Y(jié)構(gòu)具有以下特性，它能通過(guò)交換消息傳達(dá)和加強(qiáng)節(jié)點(diǎn)間的有用聯(lián)系信息。本系統(tǒng)利用這個(gè)信息來(lái)發(fā)送平行的,異步的查詢消息來(lái)對(duì)付節(jié)點(diǎn)的失效而不會(huì)給用戶帶來(lái)超時(shí)時(shí)延。
?
1
．介紹
???
本論文描述Kademlia , 一個(gè)點(diǎn)對(duì)點(diǎn)（P2P）的<鍵, 值>元組存儲(chǔ)和查詢系統(tǒng)。 Kademlia擁有許多的可喜的特點(diǎn)，這些特點(diǎn)是任何以前的P2P系統(tǒng)所無(wú)法同時(shí)提供的。它減少了節(jié)點(diǎn)必須發(fā)送的用來(lái)相互認(rèn)識(shí)的配置消息的數(shù)量。在做鍵查詢的同時(shí), 配置消息將會(huì)被自動(dòng)傳播。 節(jié)點(diǎn)擁有足夠的知識(shí)和靈活性來(lái)通過(guò)低時(shí)延路徑發(fā)送查詢請(qǐng)求。 Kademlia使用平行的,異步的查詢請(qǐng)求來(lái)避免節(jié)點(diǎn)失效所帶來(lái)的超時(shí)時(shí)延。通過(guò)節(jié)點(diǎn)記錄相互的存在的算法可以抵抗某些基本的拒絕服務(wù)（DoS）攻擊。 最后, 僅僅使用在分布式運(yùn)行時(shí)間上較弱的假設(shè)（通過(guò)對(duì)現(xiàn)有點(diǎn)對(duì)點(diǎn)系統(tǒng)的測(cè)量而確認(rèn)的這些假設(shè)），我們可以正式的證實(shí)Kademlia的許多重要特性。
??? Kademlia
使用了許多點(diǎn)對(duì)點(diǎn)（P2P）系統(tǒng)的基本方法。 鍵是一個(gè)160-bit的隱式數(shù)量(例如, 對(duì)一些大型數(shù)據(jù)進(jìn)行SHA-1哈希的值)。 每個(gè)參與的機(jī)器都擁有一個(gè)節(jié)點(diǎn)ID, 160位的鍵。 <鍵, 值>對(duì)將存儲(chǔ)在那些ID與鍵很‘接近’的節(jié)點(diǎn)上, 這里‘接近’當(dāng)然是按照一個(gè)接近度的概念來(lái)計(jì)算的。最后, 一個(gè)基于節(jié)點(diǎn)ID的路由算法使得任何人可以在一個(gè)目的鍵附近定位到一個(gè)服務(wù)器。
Kademlia
的許多的優(yōu)點(diǎn)都是得益于它使用了一個(gè)很新穎的方法, 那就是用節(jié)點(diǎn)間的鍵作異或運(yùn)算的結(jié)果來(lái)作為節(jié)點(diǎn)間的距離。異或運(yùn)算是對(duì)稱(chēng)的, 允許Kademlia的參與者接收來(lái)自相同分布的并且包含在其路由表中的節(jié)點(diǎn)的查找請(qǐng)求。如果沒(méi)有這個(gè)性質(zhì)，就像Chord一樣，系統(tǒng)無(wú)法從它們收到的查詢請(qǐng)求中學(xué)習(xí)到有用的路由信息。更糟的是， 由于Chord中的運(yùn)算是不對(duì)稱(chēng)的， Chord的路由表更加嚴(yán)格。 Chord節(jié)點(diǎn)的查找表的每一項(xiàng)都必須存儲(chǔ)精確的按ID域的間隔遞增的節(jié)點(diǎn)。在這個(gè)間隔內(nèi)的任何節(jié)點(diǎn)都比這個(gè)間隔內(nèi)的某些鍵大，因此離鍵很遠(yuǎn)。相反，Kademlia 可以在一定的間隔內(nèi)發(fā)送請(qǐng)求給任何節(jié)點(diǎn)， 允許基于時(shí)延來(lái)選擇路由，甚至發(fā)送平行的，異步的查詢。
為了在特定的ID附近定位節(jié)點(diǎn)，Kademlia自始至終使用一個(gè)單程的路由算法。相反，其它一些系統(tǒng)使用一種算法來(lái)接近目標(biāo)ID,然后在最后的幾個(gè)跳數(shù)使用另外一種算法。在現(xiàn)有系統(tǒng)中，Kademlia與pastry的第一階段最像，（雖然作者并沒(méi)有用這種方式來(lái)描述），Kademlia 的異或運(yùn)算可以使當(dāng)前節(jié)點(diǎn)到目標(biāo)ID的距離粗略的持續(xù)減半，以此來(lái)尋找節(jié)點(diǎn)。在第二階段，Pastry不再使用距離運(yùn)算，而是改為比較ID的數(shù)字區(qū)別。它使用第二種，數(shù)字區(qū)別運(yùn)算作為替代。不幸的是，按第二種運(yùn)算計(jì)算的接近比第一種的遠(yuǎn)得多，這造成特定節(jié)點(diǎn)ID值的中斷，降低了性能，并且導(dǎo)致在最差行為下的正式分析的嘗試失敗。
?
2
．系統(tǒng)描述
每個(gè)Kademlia節(jié)點(diǎn)有一個(gè)160位的節(jié)點(diǎn)ID。在Chord系統(tǒng)中，ID是通過(guò)某種規(guī)則構(gòu)造出來(lái)的，但在這片文章中，為了簡(jiǎn)化，我們假設(shè)每臺(tái)機(jī)器在加入系統(tǒng)時(shí)將選擇一個(gè)隨機(jī)的160位值。每條節(jié)點(diǎn)發(fā)送的消息包含它的節(jié)點(diǎn)ID， 同時(shí)允許接收者記錄下發(fā)送者的存在信息，如果有必要的話。
鍵，同樣也是160位的標(biāo)識(shí)符。為了發(fā)布和尋找<鍵，值>對(duì)，Kademlia依賴一個(gè)概念，那就是兩標(biāo)識(shí)符之間的距離的概念。給定兩個(gè)標(biāo)識(shí)符， x和y， Kademlia定義兩者的位異或（XOR）的結(jié)果作為兩者的距離，d(x，y)＝x⊕y。我們首先注意到異或運(yùn)算是一個(gè)有意義的運(yùn)算，雖然不是歐幾里得運(yùn)算。很明顯具有下面的性質(zhì)： d(x，x)＝0；如果x≠y, 則d(x, y)>0；任意的x, y: d(x, y) = d(y, x)。 異或運(yùn)算還滿足三角性質(zhì)：d(x, y) + d(y, z) ≥ d(x, z)。 這個(gè)三角性質(zhì)之所以成立是基于下面這個(gè)事實(shí)： d(x, z) = d(x, y) + d(y, z); 并且任意的a>=0, b≥0: a+b≥a⊕b。
跟Chord的順時(shí)針循環(huán)運(yùn)算一樣，異或運(yùn)算也是單向的。對(duì)于給定的一個(gè)點(diǎn)x以及距離Δ，僅有一個(gè)點(diǎn)y，使得d(x, y) = Δ。 單向性確保所有對(duì)于相同的鍵的查詢將匯聚到相同路徑中來(lái)，而不管是什么起源節(jié)點(diǎn)。因此，在查找路徑上緩存<鍵，值>對(duì)可以減少‘撞車(chē)’的機(jī)會(huì)。跟Pastry而不是Chord一樣， 異或運(yùn)算也是對(duì)稱(chēng)的。（對(duì)所有的x以及y， d(x,y) = d(y,x）)
?
2
．1．節(jié)點(diǎn)狀態(tài)
Kademlia
節(jié)點(diǎn)存儲(chǔ)互相的聯(lián)系信息，以用于路由查詢消息。對(duì)于任何0 =< i < 160, 每個(gè)節(jié)點(diǎn)保存那些到本節(jié)點(diǎn)的距離為2i 到2i＋1之間的節(jié)點(diǎn)信息列表，包括<IP地址，UDP端口， 節(jié)點(diǎn)ID>。我們把這些列表稱(chēng)為K-桶。每個(gè)K-桶中的節(jié)點(diǎn)按最后聯(lián)系的時(shí)間排序――最久未聯(lián)系的節(jié)點(diǎn)放在頭部，最近聯(lián)系的節(jié)點(diǎn)放在尾部。對(duì)于比較小的i值，K-桶通常是空的（因?yàn)闆](méi)有合適的節(jié)點(diǎn)存在于系統(tǒng)中）。對(duì)于比較大的i值，列表節(jié)點(diǎn)數(shù)可以達(dá)到k的大小，k是一個(gè)系統(tǒng)級(jí)別的冗余參數(shù)。k值的選擇必須滿足一個(gè)條件，那就是任意k個(gè)節(jié)點(diǎn)在一個(gè)小時(shí)內(nèi)都失效的可能性很小（例如k =20）。
圖1：
以當(dāng)前已在線時(shí)間的函數(shù)的形式顯示了節(jié)點(diǎn)在接下來(lái)的一小時(shí)后繼續(xù)在線的比例。X軸代表分鐘，y軸代表那些已經(jīng)在線了x分鐘的節(jié)點(diǎn)中將繼續(xù)在線1小時(shí)的比例。
?
當(dāng)一個(gè)Kademlia節(jié)點(diǎn)收到來(lái)自另外一個(gè)節(jié)點(diǎn)的任何消息（請(qǐng)求的或者回復(fù)的），它將更新自己的一個(gè)K-桶，即發(fā)送節(jié)點(diǎn)ID對(duì)應(yīng)的那個(gè)桶。如果發(fā)送節(jié)點(diǎn)已經(jīng)存在于接收者的K-桶中，接收者會(huì)把它移到列表的尾部。如果這個(gè)節(jié)點(diǎn)還沒(méi)有存在于對(duì)應(yīng)的K-桶中并且這個(gè)桶少于k個(gè)節(jié)點(diǎn)，則接收者把發(fā)送者插入到列表的尾部。如果對(duì)應(yīng)的K-桶已經(jīng)滿了，則發(fā)送者將向該K-桶中的最久未聯(lián)系節(jié)點(diǎn)發(fā)送ping命令測(cè)試是否存在，如果最久未聯(lián)系節(jié)點(diǎn)沒(méi)有回復(fù)，則把它從列表中移除，并把新的發(fā)送者插入到列表尾部。如果它回復(fù)了，則新的發(fā)送者信息會(huì)丟棄掉。
K-
桶非常高效的實(shí)現(xiàn)了剔除最久未聯(lián)系節(jié)點(diǎn)的策略，存活的節(jié)點(diǎn)將永遠(yuǎn)不會(huì)從列表中移除。這種偏向保留舊節(jié)點(diǎn)的做法是我們對(duì)由Saroiu等人收集的Gnutella協(xié)議的跟蹤數(shù)據(jù)進(jìn)行分析而得出來(lái)的。圖1以當(dāng)前已存在時(shí)間的函數(shù)的形式顯示了Gnutella節(jié)點(diǎn)在一小時(shí)后繼續(xù)在線的比例。一個(gè)節(jié)點(diǎn)存活的時(shí)間越長(zhǎng)，則這個(gè)節(jié)點(diǎn)繼續(xù)存活一小時(shí)的可能性越大。通過(guò)保留存活時(shí)間最長(zhǎng)的那些節(jié)點(diǎn)，K-桶中存儲(chǔ)的節(jié)點(diǎn)繼續(xù)在線的概率大大提高了。
K-
桶的第二個(gè)優(yōu)點(diǎn)是它提供了對(duì)一定的拒絕服務(wù)（DoS）的攻擊的抵抗。系統(tǒng)中不斷涌入新節(jié)點(diǎn)并不會(huì)造成節(jié)點(diǎn)路由狀態(tài)的更新過(guò)快。Kademlia節(jié)點(diǎn)只有在舊節(jié)點(diǎn)離開(kāi)系統(tǒng)時(shí)才會(huì)向k-桶中插入新節(jié)點(diǎn)。
?
2
．2．Kademlia協(xié)議
Kademlia
協(xié)議由4個(gè)遠(yuǎn)程過(guò)程調(diào)用（RPC）組成：PING，STORE，F(xiàn)IND_NODE, FIND_VALUE。 PING RPC 測(cè)試節(jié)點(diǎn)是否存在。STORE指示一個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)<鍵，值>對(duì)以用于以后的檢索。
FIND_NODE
把160位ID作為變量，RPC的接收者將返回k個(gè)它所知道的最接近目標(biāo)ID的<IP地址，UDP端口，節(jié)點(diǎn)ID>元組。這些元組可以來(lái)自于一個(gè)K-桶，也可以來(lái)自于多個(gè)K-桶（當(dāng)最接近的K-桶沒(méi)有滿時(shí)）。在任何情況下， RPC接收者都必須返回k項(xiàng)（除非這個(gè)節(jié)點(diǎn)的所有的K-桶的元組加起來(lái)都少于k個(gè)，這種情況下RPC接收者返回所有它知道的節(jié)點(diǎn)）
FIND_VALUE
和FIND_NODE行為相似――返回<IP地址，UDP端口，節(jié)點(diǎn)ID>元組。僅有一點(diǎn)是不同的，如果RPC接收者已經(jīng)收到了這個(gè)鍵的STORE RPC,則只需要返回這個(gè)已存儲(chǔ)的值。
在所有RPC中，接收者都必須回應(yīng)一個(gè)160位的隨機(jī)RPC ID,這可以防止地址偽造。PING中則可以為RPC接收者在RPC回復(fù)中捎回以對(duì)發(fā)送者的網(wǎng)絡(luò)地址獲得額外的保證。
Kademlia
參與者必須做的最重要的工作是為一個(gè)給定的節(jié)點(diǎn)ID定位k個(gè)最接近節(jié)點(diǎn)。我們稱(chēng)這個(gè)過(guò)程為節(jié)點(diǎn)查詢。Kademlia使用一種遞歸算法來(lái)做節(jié)點(diǎn)查詢。查詢的發(fā)起者從最接近的非空的K-桶中取出а個(gè)節(jié)點(diǎn)（或者，如果這個(gè)桶沒(méi)有а項(xiàng)，則只取出它所知道的最接近的幾個(gè)節(jié)點(diǎn)）。發(fā)起者然后向選定的а個(gè)節(jié)點(diǎn)發(fā)送平行的，異步的FIND_NODE RPC。а是一個(gè)系統(tǒng)級(jí)別的并行參數(shù)，比如為3。
在這個(gè)遞歸的步驟中，發(fā)起者重新發(fā)送FIND_NODE給那些從上次RPC中學(xué)習(xí)到的節(jié)點(diǎn)（這個(gè)遞歸可以在之前的所有的а個(gè)RPC返回之前開(kāi)始）。在這返回的與目標(biāo)最接近的k個(gè)節(jié)點(diǎn)中，發(fā)起者將選擇а個(gè)還沒(méi)有被詢問(wèn)過(guò)的節(jié)點(diǎn)并且重新發(fā)送FIND_NODE RPC給它們。沒(méi)有立即作出響應(yīng)的節(jié)點(diǎn)將不再予以考慮除非并且直到它們作出響應(yīng)。如果經(jīng)過(guò)一輪的FIND_NODE都沒(méi)有返回一個(gè)比已知最接近的節(jié)點(diǎn)更接近的節(jié)點(diǎn)，則發(fā)起者將重新向所有k個(gè)未曾詢問(wèn)的最接近節(jié)點(diǎn)發(fā)送FIND_NODE。直到發(fā)起者已經(jīng)詢問(wèn)了k個(gè)最接近節(jié)點(diǎn)并且得到了響應(yīng)，這個(gè)查詢才結(jié)束。當(dāng)а＝1時(shí)，查詢算法在消息開(kāi)支和檢測(cè)失效節(jié)點(diǎn)時(shí)的時(shí)延上與Chord非常相似。 然而，Kademlia可以做到低時(shí)延路由因?yàn)樗凶銐虻撵`活性來(lái)選擇k個(gè)節(jié)點(diǎn)中的一個(gè)去做查詢。
按照上面的查詢過(guò)程，大多數(shù)的操作都可以實(shí)現(xiàn)。要存儲(chǔ)一個(gè)<鍵，值>對(duì)，參與者定位k個(gè)與鍵最接近的節(jié)點(diǎn)然后向這些節(jié)點(diǎn)發(fā)送STORE RPC。另外，每個(gè)節(jié)點(diǎn)每個(gè)小時(shí)都會(huì)重新發(fā)布它所有的<鍵，值>對(duì)。這可以以高概率的把握確保<鍵，值>對(duì)的持續(xù)存在于系統(tǒng)中（我們將會(huì)在驗(yàn)證概略一節(jié)中看到）。通常來(lái)說(shuō)，我們還要求<鍵，值>對(duì)的原始發(fā)布者每隔24小時(shí)重新發(fā)布一次。否則，所有的<鍵，值>對(duì)在最原始發(fā)布的24小時(shí)后失效，以盡量減少系統(tǒng)中的陳舊信息。
最后，為了維持<鍵，值>對(duì)在發(fā)布－搜索生命周期中的一致性，我們要求任何時(shí)候節(jié)點(diǎn)w擁有一個(gè)新節(jié)點(diǎn)u，u比w更接近w中的一些<鍵，值>對(duì)。w將復(fù)制這些<鍵，值>對(duì)給u并且不從自己的數(shù)據(jù)庫(kù)中刪除。
為了查找到一個(gè)<鍵，值>對(duì)，節(jié)點(diǎn)首先查找k個(gè)ID與鍵接近的節(jié)點(diǎn)。然而，值查詢使用FIND_VALUE而不是FIND_NODE RPC。 而且，只要任何節(jié)點(diǎn)返回了值，則這個(gè)過(guò)程立即結(jié)束。為了緩存(caching)的緣故，只要一個(gè)查詢成功了，這個(gè)請(qǐng)求節(jié)點(diǎn)將會(huì)把這個(gè)<鍵，值>對(duì)存儲(chǔ)到它擁有的最接近的并且沒(méi)能返回值的節(jié)點(diǎn)上。
由于這個(gè)拓?fù)涞膯蜗蛐裕瑢?duì)相同的鍵的以后的搜索將很有可能在查詢最接近節(jié)點(diǎn)前命中已緩存的項(xiàng)。對(duì)于一個(gè)特定的鍵，經(jīng)過(guò)多次的查找和傳播，系統(tǒng)可能在許多的節(jié)點(diǎn)上都緩存了這個(gè)鍵。為了避免“過(guò)度緩存”，我們?cè)O(shè)計(jì)了一個(gè)<鍵，值>對(duì)在任何節(jié)點(diǎn)的數(shù)據(jù)庫(kù)中的存活時(shí)間與當(dāng)前節(jié)點(diǎn)和與鍵ID最接近的節(jié)點(diǎn)ID之間的節(jié)點(diǎn)數(shù)成指數(shù)級(jí)的反比例關(guān)系。簡(jiǎn)單的剔除最久未聯(lián)系節(jié)點(diǎn)會(huì)導(dǎo)致相似的生存時(shí)間分布，沒(méi)有很自然的方法來(lái)選擇緩存大小，因?yàn)楣?jié)點(diǎn)不能提前知道系統(tǒng)將會(huì)存儲(chǔ)多少個(gè)值。
???
一般來(lái)說(shuō)，由于存在于節(jié)點(diǎn)之間的查詢的通信，桶會(huì)保持不停地刷新。為了避免當(dāng)沒(méi)有通信時(shí)的病態(tài)情況，每個(gè)節(jié)點(diǎn)對(duì)在一個(gè)小時(shí)內(nèi)沒(méi)有做過(guò)節(jié)點(diǎn)查詢的桶進(jìn)行刷新，刷新意味著在桶的范圍內(nèi)選擇一個(gè)隨機(jī)ID然后為這個(gè)ID做節(jié)點(diǎn)搜索。
為了加入到這個(gè)網(wǎng)絡(luò)中，節(jié)點(diǎn)u必須與一個(gè)已經(jīng)加入到網(wǎng)絡(luò)中的節(jié)點(diǎn)w聯(lián)系。u把w加入到合適的桶中，然后u為自己的節(jié)點(diǎn)ID做一次節(jié)點(diǎn)查找。最后，節(jié)點(diǎn)u刷新所有比最接近的鄰居節(jié)點(diǎn)更遠(yuǎn)的K-桶。在這個(gè)刷新過(guò)程中，節(jié)點(diǎn)u進(jìn)行了兩項(xiàng)必需的工作：既填充了自己的K-桶，又把自己插入到了其它節(jié)點(diǎn)的K-桶中。
?
3
．驗(yàn)證概述
為了驗(yàn)證我們系統(tǒng)中的特有的函數(shù)，我們必須證實(shí)絕大多數(shù)的操作花費(fèi)
[
log
n]
+
c
的時(shí)間開(kāi)銷(xiāo)，并且c是一個(gè)比較小的常數(shù)，并且
<
鍵，值>查找將會(huì)以很高的概率返回一個(gè)存儲(chǔ)在系統(tǒng)中的鍵。
我們首先做一些定義。對(duì)于一個(gè)覆蓋距離的范圍為
[
2
i
,
2
i
+1)
的
K-
桶，定義這個(gè)桶的索引號(hào)為i。定義節(jié)點(diǎn)的深度h為160－i，其中i是最小的非空的桶的索引號(hào)。定義在節(jié)點(diǎn)x中節(jié)點(diǎn)y的桶高度為y將插入到x的桶的索引號(hào)減去x的最不重要的空桶的索引號(hào)。由于節(jié)點(diǎn)ID是隨機(jī)選擇的，因此高度的不統(tǒng)一分布是不太可能的。因此，在非常高的概率下，任意一個(gè)給定節(jié)點(diǎn)的高度在log n之內(nèi)，其中n是系統(tǒng)中的節(jié)點(diǎn)數(shù)。而且，對(duì)于一個(gè)ID，最接近節(jié)點(diǎn)在第k接近的節(jié)點(diǎn)中的桶高度很有可能是在常數(shù)log k之內(nèi)。
下一步我們將假設(shè)一個(gè)不變的條件，那就是每個(gè)節(jié)點(diǎn)的每個(gè)K-桶包含至少一個(gè)節(jié)點(diǎn)的聯(lián)系信息，如果這個(gè)節(jié)點(diǎn)存在于一個(gè)合適的范圍中。有了這個(gè)假設(shè)，我們可以發(fā)現(xiàn)節(jié)點(diǎn)的查找過(guò)程是正確的并且時(shí)間開(kāi)銷(xiāo)是指數(shù)級(jí)的。假設(shè)與目標(biāo)ID最接近的節(jié)點(diǎn)的深度是h。如果這個(gè)節(jié)點(diǎn)的h個(gè)最有意義的K-桶都是非空的，查詢過(guò)程在每一步都可以查找到一個(gè)到目標(biāo)節(jié)點(diǎn)的距離更接近一半的節(jié)點(diǎn)（或者說(shuō)距離更近了一個(gè)bit），因此在
h
-
log
k
步后目標(biāo)節(jié)點(diǎn)將會(huì)出現(xiàn)。
如果這個(gè)節(jié)點(diǎn)的一個(gè)K-桶是空的，可能是這樣的一種情況，目標(biāo)節(jié)點(diǎn)恰好在空桶對(duì)應(yīng)的距離范圍之內(nèi)。這種情況下，最后的幾步并不能使距離減半。然而，搜索還是能正確的繼續(xù)下去就像鍵中與空桶相關(guān)的那個(gè)位已經(jīng)被置反了。因此，查找算法總是能在
h
-
log
k
步后
返回最接近節(jié)點(diǎn)。而且，一旦最接近節(jié)點(diǎn)已經(jīng)找到，并行度會(huì)從а擴(kuò)展到k。尋找到剩下的k-1個(gè)最接近節(jié)點(diǎn)的步數(shù)將不會(huì)超過(guò)最接近節(jié)點(diǎn)在第k接近節(jié)點(diǎn)中的桶高度，即不太可能超過(guò)log k加上一個(gè)常數(shù)。
為了證實(shí)前面的不變條件的正確性，首先考慮桶刷新的效果，如果不變條件成立。在被刷新后，一個(gè)桶或者包含k個(gè)有效節(jié)點(diǎn)，或者包含在它范圍內(nèi)的所有節(jié)點(diǎn)，如果少于k個(gè)節(jié)點(diǎn)存在的話（這是從節(jié)點(diǎn)的查找過(guò)程的正確性而得出來(lái)的。）新加入的節(jié)點(diǎn)也會(huì)被插入到任何沒(méi)有滿的桶中去。因此，唯一違反這個(gè)不變條件的方法就是在一個(gè)特別的桶的范圍內(nèi)存在k+1個(gè)活更多的節(jié)點(diǎn)，并且桶中的k個(gè)節(jié)點(diǎn)在沒(méi)有查找或刷新的干涉下全部失效。然而，k值被精確的選擇以保證使所有節(jié)點(diǎn)在一小時(shí)內(nèi)（最大的刷新時(shí)間）全都失效的概率足夠小。
實(shí)際上，失敗的概率比k個(gè)節(jié)點(diǎn)在1小時(shí)內(nèi)全都離開(kāi)的概率小得多，因?yàn)槊總€(gè)進(jìn)入或外出的請(qǐng)求消息都會(huì)更新節(jié)點(diǎn)的桶。這是異或運(yùn)算的對(duì)稱(chēng)性產(chǎn)生的，因?yàn)樵谝淮芜M(jìn)入或外出的請(qǐng)求中，與一個(gè)給定節(jié)點(diǎn)通信的對(duì)端節(jié)點(diǎn)的ID在該節(jié)點(diǎn)的桶范圍之內(nèi)的分布是非常均勻的。
而且，即使這個(gè)不變條件在單個(gè)節(jié)點(diǎn)的單個(gè)桶中的確失效了，這也只影響到運(yùn)行時(shí)間（在某些查詢中添加一個(gè)跳數(shù)），并不會(huì)影響到節(jié)點(diǎn)查找的正確性。只有在查找路徑中的k個(gè)節(jié)點(diǎn)都必須在沒(méi)有查找或刷新的干涉下在相同的桶中丟失k個(gè)節(jié)點(diǎn)，才可能造成一次查找失敗。如果不同的節(jié)點(diǎn)的桶沒(méi)有重疊，這種情況發(fā)生的概率是2-k*k。否則，節(jié)點(diǎn)出現(xiàn)在多個(gè)其它的節(jié)點(diǎn)的桶中，這就很可能會(huì)有更長(zhǎng)的運(yùn)行時(shí)間和更低概率的失敗情況。
現(xiàn)在我們來(lái)考慮下<鍵，值>對(duì)的恢復(fù)問(wèn)題。當(dāng)一個(gè)<鍵，值>對(duì)發(fā)布時(shí)，它將在k個(gè)與鍵接近的節(jié)點(diǎn)中存儲(chǔ)。同時(shí)每隔一小時(shí)將重新發(fā)布一次。因?yàn)榧词故切鹿?jié)點(diǎn)（最不可靠的節(jié)點(diǎn)）都有1/2的概率持續(xù)存活一個(gè)小時(shí)，一個(gè)小時(shí)后<鍵，值>對(duì)仍然存在于k個(gè)最接近節(jié)點(diǎn)中的一個(gè)上的概率是1-2-k
。
這個(gè)性質(zhì)并不會(huì)由于有接近鍵的新節(jié)點(diǎn)的插入而改變，因?yàn)橐坏┯羞@樣的節(jié)點(diǎn)插入，它們?yōu)榱颂畛渌鼈兊耐皩?huì)與他們的最接近的那些節(jié)點(diǎn)交互，從而收到附近的它們應(yīng)該存儲(chǔ)的<鍵，值>對(duì)。當(dāng)然，如果這k個(gè)最接近鍵的節(jié)點(diǎn)都失效了，并且這個(gè)<鍵，值>對(duì)沒(méi)有在其它任何地方緩存，Kademlia將會(huì)丟失這個(gè)<鍵，值>對(duì)。
?
4
．討論
我們使用的基于異或拓?fù)涞穆酚伤惴ㄅcPastry [1], Tapestry [2]的路由算法中的第一步和 Plaxton的分布式搜索算法都非常的相似。然而，所有的這三個(gè)算法，當(dāng)他們選擇一次接近目標(biāo)節(jié)點(diǎn)b個(gè)bit的時(shí)候都會(huì)產(chǎn)生問(wèn)題（為了加速的目的）。如果沒(méi)有異或拓?fù)洌覀冞€需要一個(gè)額外的算法結(jié)構(gòu)來(lái)從與目標(biāo)節(jié)點(diǎn)擁有相同的前綴但是接下來(lái)的b個(gè)bit的數(shù)字不同的節(jié)點(diǎn)找到目標(biāo)節(jié)點(diǎn)。所有的這三個(gè)算法在解決這個(gè)問(wèn)題上采取的方法都是各不相同的，每個(gè)都有其不足之處；它們?cè)诖笮?/span>
O
(2
b
log
2
b
n
)
的主表之外
都
另外
需要
一個(gè)
大小為
O
(2
b
)
的
次要路由表，這增加了自舉和維護(hù)的開(kāi)支，使協(xié)議變的更加復(fù)雜了，而且對(duì)于Pastry和Tapestry來(lái)說(shuō)阻止了正確性與一致性的正式分析。Plaxton雖然可以得到證實(shí)，但在像點(diǎn)對(duì)點(diǎn)（P2P）網(wǎng)絡(luò)中的極易失效的環(huán)境中不太適應(yīng)。
相反，Kademlia則非常容易的以不是2的基數(shù)被優(yōu)化。我們可以配置我們的桶表來(lái)使每一跳b個(gè)bit的速度來(lái)接近目標(biāo)節(jié)點(diǎn)。這就要求滿足一個(gè)條件，那就是任意的
0
< j < 2b
和
0
≤
i <
160
/b
，
在與我們的距離為[j2160-(i+1)b, (j+1)2160-(i+1)b]
的范圍內(nèi)就要有一個(gè)桶，這個(gè)有實(shí)際的項(xiàng)的總量預(yù)計(jì)不會(huì)超過(guò)個(gè)桶。目前的實(shí)現(xiàn)中我們令b＝5。
?
5
．總結(jié)
使用了新穎的基于異或運(yùn)算的拓?fù)洌琄ademlia是第一個(gè)結(jié)合了可證實(shí)的一致性和高性能，最小時(shí)延路由，和一個(gè)對(duì)稱(chēng)，單向的拓?fù)涞狞c(diǎn)對(duì)點(diǎn)(P2P)系統(tǒng)。此外，Kademlia引入了一個(gè)并發(fā)參數(shù)，а，這讓人們可以通過(guò)調(diào)整帶寬的一個(gè)常數(shù)參數(shù)來(lái)進(jìn)行異步最低時(shí)延的跳選擇和不產(chǎn)生時(shí)延的失效恢復(fù)。最后，Kademlia是第一個(gè)利用了節(jié)點(diǎn)失效與它的已運(yùn)行時(shí)間成反比這個(gè)事實(shí)的點(diǎn)對(duì)點(diǎn)（P2P）系統(tǒng)。
?
參考文獻(xiàn)
[1] A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. Accepted for Middleware, 2001, 2001. http://research.microsoft.com/?antr/pastry/.
?
[2] Ben Y. Zhao, John Kubiatowicz, and Anthony Joseph. Tapestry: an infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, U.C. Berkeley, April 2001.
?
[3] Andr′ea W. Richa C. Greg Plaxton, Rajmohan Rajaraman. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the ACM SPAA, pages 311–320, June 1997.
?
[4] Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. Technical Report UW-CSE-01-06-02, University of Washington, Department of Computer Science and Engineering, July 2001.
?
[5] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM ’01 Conference, San Diego, California, August 2001.
posted on 2006-09-11 16:18
CPP&&設(shè)計(jì)模式小屋 閱讀(1990)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
P2P DHT