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