KAD

**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 桶則是空的）。

讓我們看右邊的那個簡單網路，該網路最大可有 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