Kad是Kademlia的縮寫，Kad是一個廣泛被實做的DHT protocol，目前最流行的BT和eMule都實做了Kad
DHT的目的就是為了實現沒有server的目標（decentralized)，更準確的說就是人人都是server，人人都是 client
理論上，p2p在實做Kad後，可以在沒有tracker (BT)或是server (eMule)的情況下，搜尋檔案或是找到抓同一個檔案的peer，在知道哪些peer在抓同一個檔案後，就可以開始p2p了，eMule和BT都是用udp實做Kad
Kad使用了xor (exclusive or)的方法去計算距離，需要注意的是，如果把Kad network視為overlay network，那麼Kad計算的是ovlay network上邏輯上的距離，而非真的實體距離
在暸解Kad之前，必需先暸解何為DHT（在BitTorrent的main line中，他只有DHT這個選項而沒有Kad這個選項，儘管他是Kad實作DHT）
我所理解的DHT
DHT是Distributed Hash Table的縮寫，在我的理解中，Table是一個2-column table，每一筆entry就是
在這個過程中，hash的value稱為key是因為，所有人只要有key就能找到同一臺電腦
在這我們稱該臺被找到的電腦為"負責人"，所有有同一個檔案的人都可以得到同一把key，然後全都可以告訢該負責人"他們都有這個檔案"，而所有要抓檔案的人只要有key都可以找到負責人問出"哪些人有這個檔案"，所有key是關鍵，而key又是經由hash得到的，而對DHT而言，"如何依照特定的方法找到負責人"才是研究的人要關心的，Kad就是這樣的一個方法，而Kad的前輩chord，也是一個方法
我所理解的chord
Kad和chord很像，暸解了chord，你就知道Kad怎運作
在chord中，每一個node的IP就是本身的ID，chord把一個object（object可以為實體的檔案，如歌、電影、文件之類的，也可以為任何邏輯上的物件）投影（就是hash，但是我認為hash的邏輯上的意義就是投影）到和4Byte(32bit)IP相同的空間
我們令投影的結果，也就是hash value為key，而value就是有這個object的node的IP，所有的P2P中server負責的任務不過就是讓所以query的人知道有這個檔案的IP是哪些，於是他就可以跟這些IP交換這個檔案，而DHT就是把這個工均攤到所有人身上，換句話說，在將object hash得到key，而有這個object的電腦的IP的value，於是我們就會有一對
假設所有的IP都存在於chord network中（這裡不考慮private IP的3段range），那麼最理想的狀況是，所有的key都找得到人負責，而且是1-to-1 mapping（別忘了，key落在IP的space，而每個IP都存在），所以這時的狀況就很簡單，誰的IP等於該key，那麼誰就是該key的負責人
遺憾的是，這種事不會發生，大部份的情況下，擁有該key的IP的node都不存在，那麼怎麼辦？參考下圖，我們將32bit的space想像是一個有方向性的圓，而且是單方向性（uni-directional）的圓，IP過了(2^32-1)會wrap around回0，於是可以存在一個很簡單的邏輯，那就是若不存在IP == key的node，那麼就從key往下搜尋（也就是IP++，incremental），直到遇到的第一個活著的node，那麼他就是負責人，依照這個邏輯，publish和query都可以輕易的找到同一個負責人，大概就如下圖所示的方法
大致流程可以這樣想像
假設，有三臺電腦分別為a, b, c，他們都有一條歌叫hero.mp3，假設hero.mp3的hash value為x，也就是說hero.mp3的key = x，於是在a, b, c進入chord network時，他們必需做publish這個動作
publish指的就是告訴別人你有什麼檔案，也就是說，如果你有10個檔案要分享，那麼你必需將這三個檔案publish出去，將10個檔案的
於是a, b, c會而用key x找到一個負責人y，然後a, b, c會將
現在有一臺腦z想要抓hero.mp3這首歌，而z也算出hero.mp3的key = x，於是z利用x找到負責人y，y再將table中的3個entry傳回，於是z就知道a, b, c都有這首歌，也就可以跟他們抓了
Kademlia
Kadd的paper只有6頁，很短 ，paper的全名為Kademlia: A Peer-to-peer Information System Based on the XOR Metric
Kad的想法很簡單，就是找出利XOR計算出任二點在Kad network上邏輯的距離，有了這個距離後，一個key就讓距離該key最近的K個node負責，同理，query時也是同時query距離該key最近的K個node，k是一個系統參數
Kad的paper中，他把NodeID和Key的space定為160bit，並且強調你可以認為Kad中的node是用類似random的方式產生，實際上，每個人實做或多或少都會修改，比如eMule的Kad就是使用128bit的space實做，而非paper中的160bit
有了NodeID後，Kad利用對NodeID和key使用xor計算出距離，這是xor的特性能夠保證結果唯一，xor具備以下特徵
若令d(a, b) = a xor b，則
d(a, a) = 0
對任意b!=a，則d(a, b) = d(b, a) != 0
且xor也有類似三角形兩邊之合大於第三邊的特質
d(a, b) + d(b, c) > d(a, c)
所以在Kad中，每個進入Kad network的人都會有一個160bit的NodeID，而每個object經過hash也會得到一個160bit的key
然後每一個node和key的距離就等於 distance between node and key = d(NodeID, key)，也就是NodeID xor key
然後，有檔案的人就把
整個Kad就像下圖所示
eMule的實做
eMule的Kad實做採用udp（BT也是），不同的是eMule是採用128bit(16Byte)的space，為什麼？
因為
1.eMule的NodeID剛好就是16Byte
2.eMule本來就是使用MD5來辨認file，而非檔名，而MD5 value剛好也是16Byte
於是一切就水到渠成，接下來Kad的實做就跟Kad的paper一樣了
但是由於eMule是對file content做MD5得到MD5 hash value(也就是key)，這樣會有個問題，沒有該檔案或是完整檔案的人沒法算出MD5，沒有key，就不能找到負責人，也就無法抓檔，這一點，除了透過論譠的ed2k連結來解決之外（eMule的ed2k連結中包合了檔名，檔案大小，以及MD5等欄位），還有另一種解法，也就是keyword search
簡單的說，keyword search要用Kad找兩次，第一次利用keyword找出要抓的檔案的MD5 hash，第二次才是找出哪些人有檔案
舉例來說，如果有一臺電腦a有一首歌the power of love.mp3，它的MD5為x，那麼他必需publish兩次，一次是file hash的publish，也就是
以the power of love中，關鍵字(keyword)有兩個，也就是power和love，假設power和love一樣做hash（看高興用什麼就用什麼，也可以padding再MD5）得到兩個key，分別為y和z，那麼a就必需將file hash關聯到keyword的
於是今天我們想要抓the power of love這首歌，我們輸入the power of love給程式搜尋，程式判斷出keyword為power和love，同時算出key為y和z，做Kad query，離y和z最近的k臺電腦會傳回所有data，也就是file name和file hash的組合，程式再進行比對哪一組pair的file name等於the power of love，找到後就得到the power of love的file hash，有了file hash後於是就進入正常的kad流程了
keyword search中value必需包合file name是因為一個關鍵字會關聯到太多file name，所以必需再加入file name做篩選，比如說，power關鍵字可能還關聯到power supply，power point，power planet等相關檔名，而這些都會以power做關鍵字，所以value中才必需加入file name以做進一步的篩選
Kad的優缺點如下：
優點：
可平行處理
快速，paper 中證明只需要 (logn 取上高斯) + c 次就可找到，其中c是一個小的常數
缺點：
至少要認識一個Kad node才能進入Kad network，而該node就擔任bootstrap的角色
不平均的loading，雖然是達到把server的effort分散的效果，可是不保證loading是平均，舉例來說，若有人的NodeID剛好在某個熱門檔案的k個最近node的範圍內，那他的loading肯定會比某些只負責小檔案的node大很多
這是我present的ppt
沒有留言:
張貼留言