結構化的p2p網(wǎng)絡是基于DHT（分布式哈希表）實現(xiàn)的。kad算法是DHT的一種實現(xiàn)。kad算法給每個節(jié)點分配了一個節(jié)點id，根據(jù)節(jié)點id之間的異或距離建立路由表。給資源設置了一個key，根據(jù)key與節(jié)點id的異或距離查找資源。

kad相關概念

• 1.兩個關鍵的id：

  • nodeid，節(jié)點id。節(jié)點包含了網(wǎng)絡ip地址和端口號，由唯一的節(jié)點id指向這一個節(jié)點。節(jié)點id為160位的二進制表示。
  • key。網(wǎng)絡中的資源名索引和資源名以key-value鍵值對的形式表示，資源名經(jīng)過哈希函數(shù)計算，轉(zhuǎn)為160位的key。

• 2.異或距離：
  由上述的兩個id，把資源放置在nodeid與key的距離相近的節(jié)點上，就能實現(xiàn)資源的定位。也就是我們可以根據(jù)key去匹配距離相近的nodeid，然后找到在該節(jié)點上與key對應的資源value。
  其中的距離指的是異或距離。也就是對兩個id進行異或運算，可以是nodeid與nodeid，定位節(jié)點?；蛘?strong>nodeid與key，定位資源。

  舉個例子：00110 與 00011 的異或距離為 00101，也就是5。（0⊕0=0，1⊕0=1，1⊕1=0）

• 3.異或特性:
  x ⊕ x = 0，節(jié)點與它本身的異或距離為0。
  x ⊕ y > 0 , if x != y，不同節(jié)點異或距離一定大于0。
  x ⊕ y = y ⊕ x，異或距離是對稱的。
  x ⊕ y + y ⊕ z >= x ⊕ z，類似于三角形不等式，第三邊的距離小于等于另外兩邊的距離之和。
  x ⊕ y ⊕ y ⊕ z = x ⊕ z
  x + y >= x ⊕ y

• 4.路由表，與k-bucket:
  由于節(jié)點id是一串二進制數(shù)，每一位的取值只有0或1，因此我們可以把節(jié)點id表示為二叉樹的形式。以100為例，第一位是1，（從上到下）往右子樹，第二位是0，往左子樹，第三位是0，再往左子樹。最終的葉子節(jié)點即為100。
  

  k-buckst樹形結構
  
  我們把同一個灰色部分的節(jié)點放置在同一個列表，這個列表稱為k-bucket，k桶。k桶中的k指的是每一個列表所能容納的節(jié)點的最大個數(shù)。

  劃分k桶是有規(guī)律的。k桶的個數(shù)跟節(jié)點id的位數(shù)有關，假設節(jié)點id的位數(shù)為n，則最多有n個k桶。第1個k桶中的節(jié)點與本地節(jié)點前n-1位id是相同，第2個k桶中的節(jié)點與本地節(jié)點前n-2位id是相同，以此類推，最后第n個k桶中的節(jié)點與本地節(jié)點第1位id就不一樣了。

  所有的k桶合起來也就是一個節(jié)點的路由表。

  這里以nodeid為110的節(jié)點為例，共有3個k桶。第i個k桶中異或距離的范圍為 。(i從0開始。）應用了上面說的規(guī)律，第1個k桶中的111與110的前2位是相同的，第2個k桶種的100、101與110的前1位是相同的。
  

  節(jié)點id為110的路由表

• 5.協(xié)議消息:

  • PING — 驗證遠程節(jié)點是否在線。
  • STORE — 在某個節(jié)點上存儲 key-value 鍵值對。在節(jié)點上存儲資源。
  • FIND_NODE — 查找節(jié)點，給定一個nodeid，被請求的節(jié)點返回與nodeid相近的k個節(jié)點。
  • FIND_VALUE — 查找資源，給定一個key，被請求的節(jié)點的nodeis與key相近，并且具有該key，返回與key對應的value。

kad實現(xiàn)的功能

• 1.查找節(jié)點
  需要用到的參數(shù)：，每次同時向個節(jié)點發(fā)出請求；nodeid，需要查找的節(jié)點id；k，每次查找，返回k個節(jié)點的信息。

  查找過程：

  • 1.請求節(jié)點，向自己的k桶中的個節(jié)點發(fā)起 FIND_NODE 請求。需要給定nodeid。
  • 2.接收節(jié)點收到請求后，查看自己的k桶，返回k個與nodeid相近的節(jié)點。
  • 3.請求節(jié)點在這些返回的節(jié)點里，取出k個距離最近的節(jié)點，更新結果列表。
  • 4.請求節(jié)點向結果列表里的k個節(jié)點發(fā)起 FIND_NODE 請求。
  • 回到步驟2。

  循環(huán)上述過程，迭代結束后，結果列表中的k個節(jié)點便是整個網(wǎng)絡中最接近nodeid的節(jié)點。

• 2.查找資源
  類似于查找節(jié)點的過程。資源為value，有唯一的key對應value，key與nodeid相似，所以查找到離key最接近的nodeid，在節(jié)點處匹配到key，返回key對應的value。

• 3.維護k桶
  （查找節(jié)點，是主動的更新路由表，維護k桶，是被動的更新路由表。）
  當節(jié)點收到另一個節(jié)點（設為節(jié)點A）發(fā)來的任何消息（請求或是響應）時，都會更新該節(jié)點id對應的k桶。k桶中最新的節(jié)點置于最底部。

  • 1.如果節(jié)點A已經(jīng)存在于k桶中，將節(jié)點A移到k桶的底部。
  • 2.如果節(jié)點A不存在于k桶中，k桶中節(jié)點的數(shù)量少于k個，將節(jié)點A添加到k桶的底部。
  • 3.如果k桶已經(jīng)滿了，向k桶最上面的節(jié)點B發(fā)送ping
    • 節(jié)點B無響應，移除節(jié)點B，將節(jié)點A加入到k桶底部。
    • 節(jié)點B有響應，將節(jié)點B移到k桶底部。丟棄節(jié)點A。