Kademlia

Kademlia是一種通過分散式雜湊表實現的協定演算法，它是由Petar Maymounkov與David Mazières為非集中式P2P電腦網路而設計的。Kademlia規定了網路的結構，也規定了通過節點查詢進行資訊交換的方式。參與通訊的所有節點形成一張虛擬網（或者叫做覆蓋網）。這些節點通過一組數字（或稱為節點ID）來進行身分標識。節點ID不僅可以用來做身分標識，還可以用來進行值定位（值通常是檔案的雜湊或者關鍵詞）。其實，節點ID與檔案雜湊直接對應，它所表示的那個節點儲存著哪兒能夠取得檔案和資源的相關資訊。當我們在網路中搜尋某些值（即通常搜尋儲存檔案雜湊或關鍵詞的節點）的時候，Kademlia演算法需要知道與這些值相關的鍵，然後分步在網路中開始搜尋。每一步都會找到一些節點，這些節點的ID與鍵更為接近，如果有節點直接返回搜尋的值或者再也無法找到與鍵更為接近的節點ID的時候搜尋便會停止。這種搜尋值的方法是非常高效的：與其他的分散式雜湊表的實現類似，在一個包含n個節點的系統的值的搜尋中，Kademlia僅訪問O(log(n))個節點。非集中式網路結構還有更大的優勢，那就是它能夠顯著增強抵禦阻斷服務攻擊的能力。即使網路中的一整批節點遭受泛洪攻擊，也不會對網路的可用性造成很大的影響，通過繞過這些漏洞（被攻擊的節點）來重新編織一張網路，網路的可用性就可以得到恢復。

系統細節

第一代P2P檔案分享網路，像Napster，依賴於中央資料庫來協調網路中的查詢，第二代P2P網路，像Gnutella，使用氾濫式查詢（query flooding）來查詢檔案，它會搜尋網路中的所有節點，第三代p2p網路使用分散式雜湊表來查詢網路中的檔案，分散式雜湊表在整個網路中儲存資源的位置，這些協定追求的主要目標就是快速定位期望的節點。Kademlia基於兩個節點之間的距離計算，該距離是兩個網路節點ID號的互斥或（ XOR distance ），計算的結果最終作為整型數值返回。關鍵字和節點ID有同樣的格式和長度，因此，可以使用同樣的方法計算關鍵字和節點ID之間的距離。節點ID一般是一個大的亂數，選擇該數的時候所追求的一個目標就是它的唯一性（希望在整個網路中該節點ID是唯一的）。互斥或距離跟實際上的地理位置沒有任何關係，只與ID相關。因此很可能來自德國和澳大利亞的節點由於選擇了相似的隨機ID而成為鄰居。選擇互斥或是因為通過它計算的距離享有幾何距離公式的一些特徵，尤其體現在以下幾點：節點和它本身之間的互斥或距離是0；互斥或距離是對稱的：即從A到B的互斥或距離與從B到A的互斥或距離是等同的；互斥或距離符合三角不等式：三個頂點A B C，AC互斥或距離小於或等於AB互斥或距離和BC互斥或距離之和。由於以上的這些屬性，在實際的節點距離的度量過程中計算量將大大降低。Kademlia搜尋的每一次迭代將距目標至少更近1 bit。一個基本的具有2的n次方個節點的Kademlia網路在最壞的情況下只需花n步就可找到被搜尋的節點或值。

路由表

為了說明簡單，本部分基於單個bit構建路由表，如需關於實際路由表的更多資訊，請看「查詢加速」部分。

Kademlia路由表由多個列表組成，每個列表對應節點ID的一位（例如：假如節點ID共有128位元，則節點的路由表將包含128個列表），包含多個條目，條目中包含定位其他節點所必要的一些資料。列表條目中的這些資料通常是由其他節點的IP位址，埠和節點ID組成。每個列表對應於與節點相距特定範圍距離的一些節點，節點的第n個列表中所找到的節點的第n位與該節點的第n位肯定不同，而前n-1位相同，這就意味著很容易使用網路中遠離該節點的一半節點來填充第一個列表（第一位不同的節點最多有一半），而用網路中四分之一的節點來填充第二個列表（比第一個列表中的那些節點離該節點更近一位），依次類推。如果ID有128個位元，則網路中的每個節點按照不同的互斥或距離把其他所有的節點分成了128類，ID的每一位對應於其中的一類。隨著網路中的節點被某節點發現，它們被逐步加入到該節點的相應的列表中，這個過程中包括向節點列表中存資訊和從節點列表中取資訊的操作，甚至還包括當時協助其他節點尋找相應鍵對應值的操作。這個過程中發現的所有節點都將被加入到節點的列表之中，因此節點對整個網路的感知是動態的，這使得網路一直保持著頻繁地更新，增強了抵禦錯誤和攻擊的能力。

在Kademlia相關的論文中，列表也稱為K桶，其中K是一個系統變數，如20，每一個K桶是一個最多包含K個條目的列表，也就是說，網路中所有節點的一個列表（對應於某一位，與該節點相距一個特定的距離）最多包含20個節點。隨著對應的bit位變低（即對應的互斥或距離越來越短），K桶包含的可能節點數迅速下降（這是由於K桶對應的互斥或距離越近，節點數越少），因此，對應於更低bit位的K桶顯然包含網路中所有相關部分的節點。由於網路中節點的實際數量遠遠小於可能ID號的數量，所以對應那些短距離的某些K桶可能一直是空的（如果互斥或距離只有1，可能的數量就最大只能為1，這個互斥或距離為1的節點如果沒有發現，則對應於互斥或距離為1的K桶則是空的）。

Network partition for node 110

讓我們看右邊的那個簡單網路，該網路最大可有2^3，即8個關鍵字和節點，目前共有7個節點加入，每個節點用一個小圈表示（在樹的底部）。我們考慮那個用黑圈標註的節點6，它共有3個K桶，節點0，1和2（二進制表示為000，001和010）是第一個K桶的候選節點，節點3目前（二進制表示為011）還沒有加入網路，節點4和節點5（二進制表示分別為100和101）是第二個K桶的候選節點，只有節點7（二進制表示為111）是第3個K桶的候選節點。圖中，3個K桶都用灰色圈表示，假如K桶的大小（即K值）是2，那麼第一個K桶只能包含3個節點中的2個。眾所周知，那些長時間線上連接的節點未來長時間線上的可能性更大，基於這種靜態統計分布的規律，Kademlia選擇把那些長時間線上的節點存入K桶，這一方法增長了未來某一時刻有效節點的數量，同時也提供了更為穩定的網路。當某個K桶已滿，而又發現了相應於該桶的新節點的時候，那麼，就首先檢查K桶中最早訪問的節點，假如該節點仍然存活，那麼新節點就被安排到一個附屬列表中（作為一個替代快取）.只有當K桶中的某個節點停止回應的時候，替代cache才被使用。換句話說，新發現的節點只有在老的節點消失後才被使用。

協定訊息

Kademlia協定共有四種訊息。

• PING訊息—用來測試節點是否仍然線上。
• STORE訊息—在某個節點中儲存一個鍵值對。
• FIND_NODE訊息—訊息請求的接收者將返回自己桶中離請求鍵值最近的K個節點。
• FIND_VALUE訊息，與FIND_NODE一樣，不過當請求的接收者存有請求者所請求的鍵的時候，它將返回相應鍵的值。每一個RPC訊息中都包含一個發起者加入的隨機值，這一點確保回應訊息在收到的時候能夠與前面傳送的請求訊息匹配。

定位節點

節點查詢可以非同步進行，也可以同時進行，同時查詢的數量由α表示，一般是3。在節點查詢的時候，它先得到它K桶中離所查詢的鍵值最近的K個節點，然後向這K個節點發起FIND_NODE訊息請求，訊息接收者收到這些請求訊息後將在他們的K桶中進行查詢，如果他們知道離被查鍵更近的節點，他們就返回這些節點（最多K個）。訊息的請求者在收到回應後將使用它所收到的回應結果來更新它的結果列表，這個結果列表總是保持K個回應FIND_NODE訊息請求的最佳節點（即離被搜尋鍵更近的K個節點）。然後訊息發起者將向這K個最佳節點發起查詢，不斷地迭代執行上述查詢過程。因為每一個節點比其他節點對它周邊的節點有更好的感知能力，因此回應結果將是一次一次離被搜尋鍵值越來越近的某節點。如果本次回應結果中的節點沒有比前次回應結果中的節點離被搜尋鍵值更近了，這個查詢迭代也就終止了。當這個迭代終止的時候，回應結果集中的K個最佳節點就是整個網路中離被搜尋鍵值最近的K個節點（從以上過程看，這顯然是局部的，而非整個網路）。

節點資訊中可以增加一個往返時間，或者叫做RTT的參數，這個參數可以被用來定義一個針對每個被查詢節點的逾時設定，即當向某個節點發起的查詢逾時的時候，另一個查詢才會發起，當然，針對某個節點的查詢在同一時刻從來不超過α個。

定位資源

通過把資源資訊與鍵進行對映，資源即可進行定位，雜湊表是典型的用來對映的手段。由於以前的STORE訊息，儲存節點將會有對應STORE所儲存的相關資源的資訊。定位資源時，如果一個節點存有相應的資源的值的時候，它就返回該資源，搜尋便結束了，除了該點以外，定位資源與定位離鍵最近的節點的過程相似。

考慮到節點未必都線上的情況，資源的值被存在多個節點上（節點中的K個），並且，為了提供冗餘，還有可能在更多的節點上儲存值。儲存值的節點將定期搜尋網路中與儲存值所對應的鍵接近的K個節點並且把值複製到這些節點上，這些節點可作為那些下線的節點的補充。另外，對於那些普遍流行的內容，可能有更多的請求需求，通過讓那些訪問值的節點把值儲存在附件的一些節點上（不在K個最近節點的範圍之類）來減少儲存值的那些節點的負載，這種新的儲存技術就是快取技術。通過這種技術，依賴於請求的數量，資源的值被儲存在離鍵越來越遠的那些節點上，這使得那些流行的搜尋可以更快地找到資源的儲存者。由於返回值的節點的NODE_ID遠離值所對應的關鍵字，網路中的「熱點」區域存在的可能性也降低了。依據與鍵的距離，快取的那些節點在一段時間以後將會刪除所儲存的快取值。分散式雜湊表的某些實現（如Kad）即不提供冗餘（複製）節點也不提供快取，這主要是為了能夠快速減少系統中的陳舊資訊。在這種網路中，提供檔案的那些節點將會周期性地更新網路上的資訊（通過FIND_NODE訊息和STORE訊息）。當存有某個檔案的所有節點都下線了，關於該檔案的相關的值（源和關鍵字）的更新也就停止了，該檔案的相關資訊也就從網路上完全消失了。

加入網路

想要加入網路的節點首先要經歷一個引導過程。在引導過程中，節點需要知道其他已加入該網路的某個節點的IP位址和埠號（可從使用者或者儲存的列表中獲得）。假如正在引導的那個節點還未加入網路，它會計算一個目前為止還未分配給其他節點的隨機ID號，直到離開網路，該節點會一直使用該ID號。

正在加入Kademlia網路的節點在它的某個K桶中插入引導節點（負責加入節點的初始化工作），然後向它的唯一鄰居（引導節點）發起FIND_NODE操作請求來定位自己，這種「自我定位」將使得Kademlia的其他節點（收到請求的節點）能夠使用新加入節點的Node Id填充他們的K桶，同時也能夠使用那些查詢過程的中間節點（位於新加入節點和引導節點的查詢路徑上的其他節點）來填充新加入節點的K桶。這一自查詢過程使得新加入節點自引導節點所在的那個K桶開始，由遠及近，逐個得到重新整理，這種重新整理只需通過位於K桶範圍內的一個隨機鍵的定位便可達到。

最初的時候，節點僅有一個K桶（覆蓋所有的ID範圍），當有新節點需要插入該K桶時，如果K桶已滿，K桶就開始分裂，（參見APeer-to-peer Information System 2.4）分裂發生在節點的K桶的覆蓋範圍（表現為二元樹某部分從左至右的所有值）包含了該節點本身的ID的時候。對於節點內距離節點最近的那個K桶，Kademlia可以放鬆限制（即可以到達K時不發生分裂），因為桶內的所有節點離該節點距離最近，這些節點個數很可能超過K個，而且節點希望知道所有的這些最近的節點。因此，在路由樹中，該節點附近很可能出現高度不平衡的二元子樹。假如K是20，新加入網路的節點ID為「xxx000011001」，則字首為「xxx0011……」的節點可能有21個，甚至更多，新的節點可能包含多個含有21個以上節點的K桶。（位於節點附近的k桶）。這點保證使得該節點能夠感知網路中附近區域的所有節點。（參見A Peer-to-peer Information System 2.4）

查詢加速

Kademlia使用互斥或來定義距離。兩個節點ID的互斥或（或者節點ID和關鍵字的互斥或）的結果就是兩者之間的距離。對於每一個位元來說，如果相同，互斥或返回0，否則，互斥或返回1。互斥或距離滿足三角形不等式：任何一邊的距離小於（或等於）其它兩邊距離之和。

互斥或距離使得Kademlia的路由表可以建在單個bit之上，即可使用位組（多個位聯合）來構建路由表。位組可以用來表示相應的K桶，它有個專業術語叫做字首，對一個m位的字首來說，可對應2^m-1個K桶。（m位的字首本來可以對應2^m個K桶）另外的那個K桶可以進一步擴充為包含該節點本身ID的路由樹。一個b位的字首可以把查詢的最大次數從logn減少到logn/b.這只是查詢次數的最大值，因為自己K桶可能比字首有更多的位與目標鍵相同，（這會增加在自己K桶中找到節點的機會，假設字首有m位，很可能查詢一個節點就能匹配2m甚至更多的位組），所以其實平均的查詢次數要少的多。（參考Improving Lookup Performance over a Widely-DeployedDHT第三部分）

節點可以在他們的路由表中使用混合字首，就像eMule中的Kad網路。如果以增加查詢的複雜性為代價，Kademlia網路在路由表的具體實現上甚至可以是有異構的。

學術意義

儘管互斥或標準對於理解Kademlia並不是必要，但是對於協定的分析卻至關重要。互斥或運算形成了允許閉合分析的迴圈群，為了能夠預見網路的行為和正確性，其他的一些分散式雜湊表協定和演算法都要求類比或複雜的形式分析，而Kademlia並不需要，另外，把位組作為路由資訊也簡化了Kademlia演算法。

在檔案分享網路中的應用

Kademlia可在檔案分享網路中使用，通過製作Kademlia關鍵字搜尋，我們能夠在檔案分享網路中找到我們需要的檔案以供我們下載。由於沒有中央伺服器儲存檔案的索引，這部分工作就被平均地分配到所有的客戶端中去：假如一個節點希望分享某個檔案，它先根據檔案的內容來處理該檔案，通過運算，把檔案的內容雜湊成一組數字，該數字在檔案分享網路中可被用來標識檔案。這組雜湊數字必須和節點ID有同樣的長度，然後，該節點便在網路中搜尋ID值與檔案的雜湊值相近的節點，並把它自己的IP位址儲存在那些搜尋到的節點上，也就是說，它把自己作為檔案的源進行了發布。正在進行檔案搜尋的客戶端將使用Kademlia協定來尋找網路上ID值與希望尋找的檔案的雜湊值最近的那個節點，然後取得儲存在那個節點上的檔案源列表。

由於一個鍵可以對應很多值，即同一個檔案可以有多個源，每一個儲存源列表的節點可能有不同的檔案的源的資訊，這樣的話，源列表可以從與鍵值相近的K個節點獲得。 檔案的雜湊值通常可以從其他的一些特別的Internet連結的地方獲得，或者被包含在從其他某處獲得的索引檔案中。

檔名的搜尋可以使用關鍵詞來實現，檔名可以分割成連續的幾個關鍵詞，這些關鍵詞都可以雜湊並且可以和相應的檔名和檔案雜湊儲存在網路中。搜尋者可以使用其中的某個關鍵詞，聯絡ID值與關鍵詞雜湊最近的那個節點，取得包含該關鍵詞的檔案列表。由於在檔案列表中的檔案都有相關的雜湊值，通過該雜湊值就可利用上述通常取檔案的方法獲得要搜尋的檔案。

參考資料

• http://blog.csdn.net/cz_hyf/archive/2009/12/25/5076988.aspx（頁面存檔備份，存於網際網路檔案館）
• http://blog.csdn.net/cz_hyf/archive/2010/01/11/5178330.aspx（頁面存檔備份，存於網際網路檔案館）
• 《Kademlia: A of Peer to peer information system Based on the XOR Metric》*https://web.archive.org/web/20051211011605/http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf