前言

前兩篇介紹的Distributed Hash Table的Hashing Space是對應到一個圓，今天我們要來介紹另一種對應到Tree Structure的演算法 - Kademlia

這個演算法也是廣為應用在P2P領域，如果你曾經用過Emule、BitTorrent (透露年紀) ，那麼他底層的Data Partitioning就是用Kademlia這個演算法。

Kademlia

與CHORD一樣的是透過Hash Function將NodeID、Key對應到m-bit string，一般也是採SHA-1轉成160bits。

但是Kademlia建立了一個Binary Tree，搭配0與1將每一個NodeID放在Tree的Leaf上。

如下圖所示:

• 每一個Node儲存自己的NodeIP、NodePort
• Data一樣放在距離最近的Node上，所以Node也會儲存自已手上有的(Key, Value)

與CHORDㄧ樣，Kademlia也設計了一個自己Routing方法
先來看看什麼是 Distance 和 K-buckets 吧

Distance - XOR

在這裡我們定義 Distance 就是兩個ID做XOR的結果

E.g.
NodeA = 2 = 0010
NodeB =14 = 1110
XOR(A,B) = 1100 = 12

我們定義這個 1100 = 12 就是他的Distance，我們等等會看到這個的意義

Neighbors - K-buckets

在Kademlia裡，每一個Node維護了K-buckets作為Routing Table。

而 K-buckets 就是以 Distance 來做分層

• Bucket i 裡面存 2^i ~ 2^(i+1)-1 距離範圍內的Nodes，i = 0~m-1 (m-bits)
• K是一個可以調整的參數，表示每一個Bucket可以存多少個Neighbor Node資訊

E.g.

Bucket 0 存距離 0~1 之間範圍內的Nodes
Bucket 1 存距離 2~3 之間範圍內的Nodes
Bucket 2 存距離 4~7 之間範圍內的Nodes
...

直接看一個圖

對於Node 0010來說，Node 0000應該存在哪一個Bucket呢?

• (Node 0010) XOR (Node 0000) = 0010 = 2

• 應該放在放在k-bucket 1中因為距離是2~3之間，i=1

• 而K就是每個Bucket可以存多少個Nodes

我們可以從另一個角度來看這個關係，其實他採用XOR就是在說明bits到第幾位開始不同

例如0011與0010是到最後一位才不同放在 Bucket0
例如0000/0001與0010是第二位開始不同，放在Bucket1。
例如0100/0110/0101/0111與0010是第三位開始不同，放在Bucket2

他的Bucket距離區間( 2^i ~ 2^(i+1)-1 )從二進位來看就是第幾位開始不同

但是你會發現當i越大，比方說到Bucket159，他可能存的Node是在2^159 ~ 2^(160)-1之間，可能有超多Nodes，
所以才要用K-bucket，規定每個Bucket只能存K個，
距離越遠我可以用hops的方法去找去逼近到而不用全部記下來。

Lookup

直接從例子來看
假設 NodeID 0010 要尋找 NodeID 1110

核心思想就是每一次找都找最接近的

比方說 NodeID 1110 應該是要在 NodeID 0010 [8,15]這個區間的Bucket，但是不在裡面。
但是 NodeID 1110 一定跟其他已經記錄在NodeID 0010 [8,15]這個區間的Neighbors Nodes比較近
因此先從[8,15]開始找

1. NodeID 0010 XOR NodeID 1110 = 12 在 [8,15]區間

2. 因為在自己的Bucket裡面沒有記錄NodeID 1110，因此發送訊息詢問有記錄的Nodes，比方說Node 1000與Node 1010。一次詢問多少人也是可調參數，這邊假設可以從Bucket挑出最多2人詢問。

3. 因此 NodeID 0010 -> Node 1000與Node 1010 詢找NodeID 1110

4. Node 1010 XOR NodeID 1110 發現 NodeID 1110 應該要在自己的 [4,7]區間，發現沒記錄。於是從Bucket [4,7]區間再挑出2人詢問

5. Node 1010 -> Node 1100與Node 1101 詢找NodeID 1110

6. 而Node 1101 XOR NodeID 1110 發現 NodeID 1110 應該要在自己的 [2,3]區間，且的確有記錄他的資訊，因此回傳找到

小結

你可以發現尋找的過程中，他是不斷的一次跳到距離目標節點最近的Bucket裡面的 Neighbor Nodes 去詢問。
而他的換個角度看會發現，這個概念是一個bit一個bit去逼近target。

因為採用SHA-1 Hash成2進位表示，所以每次前進一個bit都可以視為除一次2（更正後）。

因此尋找的複雜度就像二分搜尋法那樣，為O(lgN)。

是一個很精妙的設計

Reference

• TU Dresden - Internet and Web Application
• 寫得很好的部落格 - https://www.jianshu.com/p/f2c31e632f1d