概要

Kademlia協議（以下簡稱Kad） 是美國紐約大學的PetarP. Maymounkov和David Mazieres. 在2002年發布的一項研究結果《Kademlia: A peerto -peer information system based on the XOR metric》。
在Kad網絡中所有的信息都是以哈希表的形式存儲的，并分散在不同的節點中。

查詢過程

相信很多人都用過eMula吧，我們來看下eMula的運行原理。
eMula有一個關鍵字字典的哈希表（key是關鍵字的哈希值(160位)，value是文件信息列表，文件信息包括文件名字，文件長度，文件哈希(160位)。）
當我們要查詢一個關鍵字的時候會從這個字典中找到文件信息列表，然后根據文件信息里的文件哈希從文件索引字典里面找到文件的擁有者。(文件索引字典的key是文件哈希，value是文件所有者列表，文件所有者包括node-id）。

字典存儲

上面提到了關鍵字字典和文件索引字典這2個字典，那么這2個字典是如何存儲的呢，在Kad網絡中是根據一定的規則存儲在各個P2P節點中，下面我們就說下這個規則。
這2個字典的key都是160位的哈希值，在Kad網絡中每個節點都有一個node-id,也是160位的哈希值，key-value就存儲在node-id最接近key的n個節點上。之所有要重復保存n份，是考慮到Kad網絡的穩定而產生的冗余。
可以看出在Kad網絡中越靠近key的區域，存儲得越集中。為了信息的實效性，離目標節點越近保存的時間越長。

判斷2個節點x，y的距離就是這2個節點的異或d(x,y)=x⊕y，當d(x,y)大時說明2個節點距離遠，反之說明2個節點距離近。說通俗點就是x,y的高位越相同距離就越近。比如：

x是0x1234567891234567891234567891234567891234 y是0x1234567890123456789012345678901234567890 z是0x1234567801234567890123456789012345678901 其中x，y的前9個高位是一樣的，x和z的前8個高位是一樣的，說明x，y的距離比x，z的距離近。

為了保證數據搜索的一致性，在任何時候節點w發現新節點u比w上的某些key，value對數據更接近，則w把這些key，value對復制到u上，但是不會從w上刪除。

找到節點的網絡信息

在查詢過程章節中我們找到了node-ID，我們這里就來講解如何根據node-ID找到節點的網絡信息(包括IP，端口）。
在Kad網絡中每個節點都維護了160個list，每個list都稱為一個k-bucket,在第i個 list中，記錄了當前節點已知的與自身距離為2^i~2(i+1)的一些其他對端節點的網絡信息(IP，端口)，每一個list中最多存放k個節點信息(不包括自身節點)。比如:
x是01010101010101…
第160個k-bucket記錄了高位是0的k個節點信息
第159個k-bucket記錄了高位是01的k個節點信息
第158個k-bucket記錄了高位是010的k個節點信息
第i個k-bucket記錄了前(160-i)位和x的前(160-i)位一致的k個節點信息
每一個 list中的對端節點信息均按訪問時間排序，最早訪問的在list頭部，而最近新訪問的則放在list的尾部。
Kad的查找過程：

查詢者從自己的k-bucket中找到離目標節點最近的n個節點，然后異步向這n個節點發起查詢請求

被查詢節點收到請求后從自己的k-bucket里找到離目標節點最近的n個節點返回給查詢者。

查詢者收到結果后重復步驟1.
這其實就是個不斷收斂的過程，例如：
查詢節點x是01010101010101…
目標節點y是01010100011010…
x和y的前7個高位是一致的，至少x的第153個k-bucket記錄了高位是01010100(8位)的k個節點信息，x向這k個節點發送查詢請求。這k個節點的k-bucket里面至少記錄了高位是010101000(9位）的k個節點信息。不斷的收斂最終就找到了目標節點y。

新節點的加入

新節點u加入Kad網絡的時候首先隨機生成自己的node-ID，然后獲取一個已經加入Kad網絡的節點信息w。

u把w插入到自己合適的k-bucket中，然后對自己的節點ID進行查詢。

根據接受到的信息更新自己的v-bucket。

對接受到的消息的節點ID進行查詢，直到自己的k-bucket有足夠多的信息。

協議消息

在KAD協議中，有4個指令

Ping 用來測試節點是否在線

Store 在某個節點存儲key-value

FindNode 消息請求的接收者將返回自己桶中離請求鍵值最近的K個節點

FindValue 與FindNode一樣，不過當請求的接收者存有請求者所請求的鍵的時候，它將返回相應鍵的值。

總結

以上是生活随笔為你收集整理的理解Kademlia协议原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。