Kademlia

Kademlia 是由 Petar Maymounkov 與 David Mazières 所設計的P2P 重疊網路傳輸協定，以構建分散式的P2P電腦網路。是一種基於異或運算的P2P信息系統。它制定了網路的結構及規範了節點間通訊和交換資訊的方式。

基本介紹

• 中文名：Kademlia 網路傳輸協定
• 外文名：Kademlia

節點間簡介

Kademlia 節點間使用傳輸通訊協定 UDP 溝通。Kademlia 節點利用分散式散列表 (DHT) 儲存資料索引。透過現有的區域網路/廣域網( LAN/WAN)，建立起一個新的虛擬網路或重疊網路。

一個想要加入網路的節點需要先經過啟動過程。在這個階段，該節點需要知道另一個已經在 Kademlia 網路中註冊的節點的 IP 地址 （通過另一個使用者或儲存的清單取得）。如果啟動中的節點還不是網路的一部分，它便會計算一個尚未指定給其他節點的隨機ID（160比特）編號。這個ID是由節點的對外IP位址跟連線埠號經過SHA-1算法散列之後得到的。這個 ID 會一直使用到離開網路為止。

Kademlia 內的資訊都儲存在稱為“值（value）”的東西內，每個值都連線著一個“鍵（key）”。每一條<鍵，值>對作為Kad網路的基本信息結構被存儲在本地資料庫當中。

簡單的說，擁有要分享的檔案網路節點，會先處理檔案的內容，並從內容計算出一組數字（散列），這組數字將會在檔案分享網路中辨識這個檔案。散列與節點 ID 的長度相同。接著會查找幾個 ID 與散列值相近、且節點內有儲存著自己 IP 地址的節點。搜尋的用戶會使用 Kademlia 來搜尋網路上節點ID離自己最近距離的節點來取得檔案的散列值，然後會取得在該節點上的路由清單。 當節點聯入和聯出時，這份存儲在網路上的路由清單也將保持不變。因為內嵌的冗餘存儲算法，路由清單將複製在多個節點上。

在Kad網路中，每個節點只負責處理一小部分搜尋和查找源的工作。分配這些工作的時候，通過我們每個用戶端的唯一的ID和搜尋檔案的Hash值之間的匹配來決定。

協定原理簡介

一、前言

Kademlia協定（以下簡稱Kad）是美國紐約大學的PetarP. Maymounkov和David Mazieres.在2002年發布的一項研究結果《Kademlia: A peerto -peer information system based onthe XOR metric》。

簡單的說，Kad 是一種分散式哈希表（DHT）技術，不過和其他DHT 實現技術比較，如Chord、CAN、Pastry 等，Kad通過獨特的以異或算法（XOR）為距離度量基礎，建立了一種全新的DHT拓撲結構，相比於其他算法，大大提高了路由查詢速度。

在2005 年5 月著名的BiTtorrent 在4.1.0 版實現基於Kademlia 協定的DHT 技術後，很快國內的BitComet 和BitSpirit 也實現了和BitTorrent 兼容的DHT 技術，實現trackerless下載方式。

另外，emule 中也很早就實現了基於Kademlia類似的技術（BT中叫DHT，emule中也叫Kad，注意和本文簡稱的Kad 區別），和BT 軟體使用的Kad 技術的區別在於key、value 和node ID 的計算方法不同。

二、節點狀態

在Kad網路中，所有節點都被當作一顆二叉樹的葉子，並且每一個節點的位置都由其ID值的最短前綴唯一的確定。

對於任意一個節點，都可以把這顆二叉樹分解為一系列連續的，不包含自己的子樹。最高層的子樹，由整顆樹不包含自己的樹的另一半組成；下一層子樹由剩下部分不包含自己的一半組成；依此類推，直到分割完整顆樹。圖1就展示了節點0011如何進行子樹的劃分：

圖1：節點0011的子樹劃分

虛線包含的部分就是各子樹，由上到下各層的前綴分別為0，01，000，0010。

Kad協定確保每個節點知道其各子樹的至少一個節點，只要這些子樹非空。在這個前提下，每個節點都可以通過ID值來找到任何一個節點。這個路由的過程是通過所謂的XOR（異或）距離得到的。

圖2就演示了節點0011如何通過連續查詢來找到節點1110的。節點0011通過在逐步底層的子樹間不斷學習並查詢最佳節點，獲得了越來越接近的節點，最終收斂到目標節點上。

圖2：通過ID值定位目標節點

需要說明的是，只有第一步查詢的節點101，是節點0011已經知道的，後面各步查詢的節點，都是由上一步查詢返回的更接近目標的節點，這是一個遞歸操作的過程。

三、節點間距離

Kad 網路中每個節點都有一個160bit的ID值作為標誌符，Key也是一個160bit的標誌符，每一個加入Kad網路的計算機都會在160bit的key 空間被分配一個節點ID（node ID）值（可以認為ID是隨機產生的），<key,value>對的數據就存放在ID值“最”接近key值的節點上。

判斷兩個節點x,y的距離遠近是基於數學上的異或的二進制運算，d(x,y) = x？y，既對應位相同時結果為0，不同時結果為1。例如：

010101

XOR 110001

-------------

100100

則這兩個節點的距離為32+4=36。

顯然，高位上數值的差異對結果的影響更大。

對於異或操作，有如下一些數學性質：

? d(x, x) = 0

? d(x, y) > 0， if x ≠ y

? ∨x, y : d(x, y) = d(y, x)

? d(x, y) + d(y, z) ≧ d(x, z)

? d(x, y) ？ d(y, z) = d(x, z)

? ∨a≧ 0, b≧ 0, a + b≧ a ？ b

正如Chord的順時針旋轉的度量一樣，異或操作也是單向性的。對於任意給定的節點x和距離⊿≧0，總會存在一個精確的節點y，使得d(x,y)= ⊿。另外，單向性也確保了對於同一個key值的所有查詢都會逐步收斂到同一個路徑上，而不管查詢的起始節點位置如何。這樣，只要沿著查詢路徑上的節點都快取這個<key,value>對，就可以減輕存放熱門key值節點的壓力，同時也能夠加快查詢回響速度。

四、K桶

Kad的路由表是通過一些稱之為K桶的表格構造起來的。這有點類似Tapestry技術，其路由表也是通過類似的方法構造的。

對 每一個0≦i≦160，每個節點都保存有一些和自己距離範圍在區間 內的一些節點信息，這些信息由一些(IP address,UDP port,Node ID)數據列表構成（Kad網路是靠UDP協定交換信息的）。每一個這樣的列表都稱之為一個K桶，並且每個K桶內部信息存放位置是根據上次看到的時間順序排列，最近（least-recently）看到的放在頭部，最後（most-recently）看到的放在尾部。每個桶都有不超過k個的數據項。

一個節點的全部K桶列表如表1所示：

I 距離 鄰居

0 0 1[2 , 2) 0-1 (IP address,UDP port,Node ID) ......

0-k (IP address,UDP port,Node ID)

1 1 2[2 , 2) 1-1 (IP address,UDP port,Node ID) ......

1-k (IP address,UDP port,Node ID)

2 2 3[2 , 2) (IP address,UDP port,Node ID) ...... 2-1

(IP address,UDP port,Node ID) 2-k

……

i 1[2 , 2) i i+ i-1 (IP address,UDP port,Node ID) ......

i-k (IP address,UDP port,Node ID)

……

表1：K桶結構

不過通常來說當i值很小時，K桶通常是空的（也就是說沒有足夠多的節點，比如當i=0時，就最多可能只有1項）；而當i值很大時，其對應K桶的項數又很可能會超過k個（當然，覆蓋距離範圍越廣，存在較多節點的可能性也就越大），這裡k是為平衡系統性能和網路負載而設定的一個常數，但必須是偶數，比如k=20。在BitTorrent的實現中，取值為k=8。

由於每個K桶覆蓋距離的範圍呈指數關係增長，這就形成了離自己近的節點的信息多，離自己遠的節點的信息少，從而可以保證路由查詢過程是收斂。因為是用指數方式劃分區間，經過證明，對於一個有N個節點的Kad網路，最多只需要經過logN步查詢，就可以準確定位到目標節點。這個特性和Chord網路上節點的finger table劃分距離空間的原理類似。

當節點x收到一個PRC訊息時，傳送者y的IP位址就被用來更新對應的K桶，具體步驟如下：

1．計算自己和傳送者的距離：d(x,y) = x？y，注意：x和y是ID值，不是IP位址

2．通過距離d選擇對應的K桶進行更新操作。

3．如果y的IP位址已經存在於這個K桶中，則把對應項移到該該K桶的尾部

4．如果y的IP位址沒有記錄在該K桶中

⑴如果該K桶的記錄項小於k個，則直接把y的(IP address,UDP port,Node ID)信息插入佇列尾部

⑵如果該K桶的記錄項大於k個，則選擇頭部的記錄項（假如是節點z）進行RPC_PING操作

①如果z沒有回響，則從K桶中移除z的信息，並把y的信息插入佇列尾部

②如果z有回響，則把z的信息移到佇列尾部，同時忽略y的信息。

K桶的更新機制非常高效的實現了一種把最近看到的節點更新的策略，除非線上節點一直未從K桶中移出過。也就是說線上時間長的節點具有較高的可能性繼續保留在K桶列表中。

採用這種機制是基於對Gnutella網路上大量用戶行為習慣的研究結果，既節點的失效機率和線上時長成反比關係，如圖3（橫坐標為分鐘，縱坐標為機率）：

圖3：Gnutella網路中線上時長和繼續線上的機率關係

可以明顯看出，用戶線上時間越長，他在下一時段繼續線上的可能性就越高。

所以，通過把線上時間長的節點留在K桶里，Kad就明顯增加K桶中的節點在下一時間段仍然線上的機率，這對應Kad網路的穩定性和減少網路維護成本（不需要頻繁構建節點的路由表）帶來很大好處。

這種機制的另一個好處是能在一定程度上防禦DOS攻擊，因為只有當老節點失效後，Kad才會更新K桶的信息，這就避免了通過新節點的加入來泛洪路由信息。

為了防止K桶老化，所有在一定時間之內無更新操作的K桶，都會分別從自己的K桶中隨機選擇一些節點執行RPC_PING操作。

上述這些K桶機制使Kad緩和了流量瓶頸（所有節點不會同時進行大量的更新操作），同時也能對節點的失效進行迅速回響。

五、Kademlia協定操作類型

Kademlia協定包括四種遠程操作：PING、STORE、FIND_NODE、FIND_VALUE。

1、PING操作的作用是探測一個節點，用以判斷其是否仍然線上。

2、STORE操作的作用是通知一個節點存儲一個<key,value>對，以便以後查詢需要。

3、FIND_NODE操作使用一個160bit的ID作為參數。本操作的接受者返回它所知道的更接近目標ID的K個節點的(IP address,UDP port,Node ID)信息。

這些節點的信息可以是從一個單獨的K桶獲得，也可以從多個K桶獲得（如果最接近目標ID的K桶未滿）。不管是哪種情況，接受者都將返回K個節點的信息給操作發起者。但如果接受者所有K桶的節點信息加起來也沒有K個，則它會返回全部節點的信息給發起者。

4、FIND_VALUE操作和FIND_NODE操作類似，不同的是它只需要返回一個節點的(IP address,UDP port,Node ID)信息。如果本操作的接受者收到同一個key的STORE操作，則會直接返回存儲的value值。

註：在Kad網路中，系統存儲的數據以<key,value>對形式存放。根據筆者的分析，在BitSpirit的DHT實現中，其key值為torrent檔案的info_hash串，其value值則和torrent檔案有密切關係。

為了防止偽造地址，在所有RPC操作中，接受者都需要回響一個隨機的160bit的ID值。另外，為了確信傳送者的網路地址，PING操作還可以附帶在接受者的RPC回覆信息中。

六、路由查詢機制

Kad技術的最大特點之一就是能夠提供快速的節點查找機制，並且還可以通過參數進行查找速度的調節。

假如節點x要查找ID值為t的節點，Kad按照如下遞歸操作步驟進行路由查找：

1、 計算到t的距離：d(x,y) = x？y

2、 從x的第[㏒d]個K桶中取出α個節點的信息（“[”“]”是取整符號），同時進行FIND_NODE操作。如果這個K桶中的信息少於α個，則從附近多個桶中選擇距離最接近d的總共α個節點。

3、 對接受到查詢操作的每個節點，如果發現自己就是t，則回答自己是最接近t的；否則測量自己和t的距離，並從自己對應的K桶中選擇α個節點的信息給x。

4、 X對新接受到的每個節點都再次執行FIND_NODE操作，此過程不斷重複執行，直到每一個分支都有節點回響自己是最接近t的。

5、 通過上述查找操作，x得到了k個最接近t的節點信息。

注意：這裡用“最接近”這個說法，是因為ID值為t的節點不一定存在網路中，也就是說t沒有分配給任何一台電腦。

這裡α也是為系統最佳化而設立的一個參數，就像K一樣。在BitTorrent實現中，取值為α=3。

當α=1時，查詢過程就類似於Chord的逐跳查詢過程，如圖4。

圖4：α=1時的查詢過程

整個路由查詢過程是遞歸操作的，其過程可用數學公式表示為：

這個遞歸過程一直持續到 Nl =t，或者 Nl 的路由表中沒有任何關於t 的信息，即查詢

失敗。

由於每次查詢都能從更接近t的K桶中獲取信息，這樣的機制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，從而保證整個查詢過程的收斂速度為O(logN)，這裡N為網路全部節點的數量。

當節點x要查詢<key,value>對時，和查找節點的操作類似，x選擇k個ID值最接近key值的節點，執行FIND_VALUE操作，並對每一個返回的新節點重複執行FIND_VALUE操作，直到某個節點返回value值。

一旦FIND_VALUE操作成功執行，則<key,value>對數據會快取在沒有返回value值的最接近的節點上。這樣下一次查詢相同的 key時就會更加快速的得到結果。通過這樣的方式，熱門<key,value>對數據的快取範圍就逐步擴大，使系統具有極佳的回響速度，如圖 5所示。

圖5：快取原則

七、數據存放

存放<key,value>對數據的過程為：

1、 發起者首先定位k個ID值最接近key的節點；

2、 發起者對這k個節點發起STORE操作

3、 執行STORE操作的k個節點每小時重發布自己所有的<key,value>對數據。

4、 為了限制失效信息，所有<key,value>對數據在初始發布24小時後過期。

另外，為了保證數據發布、搜尋的一致性，規定在任何時候，當節點w發現新節點u比w上的某些<key,value>對數據更接近，則w把這些<key,value>對數據複製到u上，但是並不會從w上刪除。

八、節點加入和離開

如果節點u要想加入Kad網路，它必須要和一個已經在Kad網路的節點，比如w，取得聯繫。

u首先把w插入自己適當的K桶中，然後對自己的節點ID執行一次FIND_NODE操作，然後根據接收到的信息更新自己的K桶內容。通過對自己鄰近節點由近及遠的逐步查詢，u完成了仍然是空的K桶信息的構建，同時也把自己的信息發布到其他節點的K桶中。

在Kad網路中，每個節點的路由表都表示為一顆二叉樹，葉子節點為K桶，K桶存放的是有相同ID前綴的節點信息，而這個前綴就是該K桶在二叉樹中的位置。這樣，每個K桶都覆蓋了ID空間的一部分，全部K桶的信息加起來就覆蓋了整個160bit的ID空間，而且沒有重疊。

以節點u為例，其路由表的生成過程為：

1． 最初，u的路由表為一個單個的K桶，覆蓋了整個160bitID空間，如圖6最上面的路由表；

2． 當學習到新的節點信息後，則u會嘗試把新節點的信息，根據其前綴值插入到對應的K桶中：

① 如果該K桶沒有滿，則新節點直接插入到這個K桶中；

② 如果該K桶已經滿了，

⑴ 如果該K桶覆蓋範圍包含了節點u的ID，則把該K桶分裂為兩個大小相同的新K桶，並對原K桶內的節點信息按照新的K桶前綴值進行重新分配

⑵ 如果該K桶覆蓋範圍沒有包節點u的ID，則直接丟棄該新節點信息

3． 上述過程不斷重複，最終會形成表1結構的路由表。達到距離近的節點的信息多，距離遠的節點的信息少的結果，保證了路由查詢過程能快速收斂。

圖6：節點000的路由表生成演化

在圖7 中，演示了當覆蓋範圍包含自己ID 值的K 桶是如何逐步分裂的。

圖7：節點0100的K桶分裂過程

當K桶010滿了之後，由於其覆蓋範圍包含了節點0100的ID，故該K桶分裂為兩個新的K桶：0101 和0100，原K桶010的信息會根據其其前綴值重新分布到這兩個新的K桶中。注意，這裡並沒有使用160bit的ID值表示法，只是為了方便原理的演示，實際Kad網路中的ID值都是160bit的。

節點離開Kad網路不需要發布任何信息，Kademlia協定的目標之一就是能夠彈性工作在任意節點隨時失效的情況下。為此，Kad要求每個節點必須周期性的發布全部自己存放的<key,value>對數據，並把這些數據快取在自己的k個最近鄰居處，這樣存放在失效節點的數據會很快被更新到其他新節點上。