example:

節點的要素

Node ID : node獨一無二的代號
IP Address, port : 代表node真正的地址
Key : data 的hash
Value : data 路由表, K-bucket : 每個人手上的通訊錄, 記錄著部份node的(Node ID, IP address, port)

文件的查找

這邊我捨棄下面網站node id必須和key一樣的說法
假設data在00010000的人手上
但必須考慮萬一00010000的人下線了怎麼辦
所以要求這data還必須同時存儲在離00010000最近的k個人身上
00010001, 00010010, 00010011......的人身上都有這個data

當拿到種子的時候, 裡面會記載這個data在誰手上
所以就知道要去找誰拿這個data了
剩下的問題就變成怎麼找, 總不可能全部的節點都問一遍

節點的XOR距離

這時候看看手上的通訊錄, 很有可能並沒有00010000的人的地址
一個想法就是在通訊裡面找一個擁有 目標Z 的地址的人
因為通訊錄都是按距離分層的
算法的設計是
如果一個人的XOR距離離你越近, 那你通訊錄有他的地址機率越大
所以當你知道 目標Z 跟你之間的距離, 就可以在通訊錄上先找到一個認為跟 目標Z 最接近的人
再請他去幫你找 目標Z

01010000與01010010的距離 = 00000010 = 2
01000000與00000001的距離 = 01000001 = 65

那麼通訊錄是怎麼分層的呢
基本上是按位數分層

如果一個節點的ID前面所有位數都與他相同, 只有最後1位不同, 這樣的節點只會有一個, 這樣的節點為k-bucket 1
只有最後2位不同, 這樣的歸類為k-bucket2
最後i位不同, 歸類為k-bucket i

現在來仔細看一下完整的搜尋過程

1. A (0000110)想找Z (00010000)的人要data
2. Z XOR A = 00010110, 所以Z可能在k-bucket5中
3. 然後A看看自己的k-bucket5有沒有Z
   -> 有, 直接聯繫到Z
   -> 沒有, 在k-bucket5隨便找一個B, 請B在自己的通訊錄按同樣的方法找Z, 依此類推直到找到Z

Kedemlia的三個參數

keyspace : ID有多少位, 決定每個節點的通訊錄有幾層
k : 每一層k-bucket裡面裝k個node, 離有data的k個節點會被要求存儲這個data
a : 每次向其他node請求查找某個node時, 會向a個node發出請求

Kademlia Kademlia算法