Kad的出現 結束了edonkey時代
2012年02月09日 點擊數: 19014 字體: 大 中 小
Kad是Kademlia的簡稱，eMule的官方網站在2004年2月27日正式發布的 eMule v0.42b中，Kad開始正式內嵌成為eMule的一個功能模塊，可以說從這個版本開始eMule便開始支持Kad網絡了。
Kad的出現，結束了之前edonkey時代，在ed圈里只存在著ED2K一種網絡的模式，它通過新的協議開創并形成了自己的kad網絡，使之和ED2K網絡并駕齊驅，而且它還完全支持兩種網絡，可以在兩種網絡之間通用。Kad同樣也屬于開源的自由軟件。它的程序和源代碼可以在官方網站http://www.emule-project.net上下載。
Kad網絡拓撲的最大特點在于它完全不需要服務器，我們都知道傳統的ed2k網絡需要服務器支持作為中轉和存儲hash列表信息，kad可以不通過服務器同樣完成ed2k網絡的一切功能，你唯一要做的就是連線上網，然后打開kad。Kad需要UDP端口的支持，之后Emule會自動按照客戶端的要求，來判斷它能否自由連線，然后同樣也會分配給你一個id，這個過程和我們ed2k的高id和低id檢查很像，不過這個id所代表的意義不同于ed2k網絡，它代表一個是否“freely”的狀態。
Kad和ed2k網絡有著完全不同的觀念但是相同的目的: 都是搜索和尋找文件的源。 Kad網絡的主要的目標是做到不需要服務器和改善可量測性。相對于傳統的ed2k服務器只能處理一定數量的使用者(我們在服務器列表也都看到了,每個服務器都有最大人數限制)，而且如果服務器比較大連接人數過多,還會嚴重的的拖垮網絡。而Kad能夠自我組織,并且自我調節最佳的使用者數量以及他們的連接效果。因此, 它更能使網絡的損失達到最小。由于具備了以上所敘述的功能，Kad也被稱之為Serverless network（無服務器網絡）。雖然目前一直處于開發階段(alpha stage) 。但毫無疑問，它無可比擬的優勢,將會使它成為p2p的明天。
可能很多朋友會關注， kad網絡沒有高低id的計算原則，是否對于低id來言就暢通無阻了呢？
我們大家知道在ed2k網絡里面，我們的id是通過ip進行如下的算法計算得出的
設我們的IP = A.B.C.D
那么我們的ID number= A + 256*B + 256*256*C + 256*256*256*D
low ID的產生是由于我們的ID計算結果小于16777216.
即 ID number= A + 256*B + 256*256*C + 256*256*256*D < 16777216
Kad的 id計算原則并不是象上面那樣，他更關注我們是否open和freely。
但是kad里面是如何計算我們的id呢？
事實上它的計算方法是這樣
ID number=256*256*256*A+256*256*B+256*C+D
所以kad其實也有高低id的分別。所以內網用戶在使用的時候依舊無法達到內網用戶完全穿透網絡的效果，而且目前來看，還存在著kad模塊引入,導致占用系統資源會變大以及會突然產生Memory Leak的問題，對于內存的控制，目前emule做的效果還是不好。
其實kad本身有一個nodes.dat文件，也叫做節點文件，這里面存放了我們在Kad網絡中的鄰居節點，我們都是通過這些節點來進入Kad網絡的。其實kad的網絡倒更像是overnet和Kazaa網絡，有興趣的朋友大家可以對比看看。Kad網絡提供了幫助尋找節點以及記錄節點的機制。
下面我們來說說這個機制的原理：
Kad擁有一個160bit的ID，每一個節點送出的訊息都必須包含此ID。每一個節點都必須記錄一個資料來保存已經存在的節點，資料的格式是 (IP address, UDP port, Node ID)，節點所必須負責的范圍是2的i次方及2的i+1次方，i的范圍是0 < i <160，這個結構叫做k-bucket，該結構會形成一個tree的形狀，每一次接收到新的信息時，各個節點都必須更新k-bucket內的資料，透過k-bucket結構我們可以保證所有的節點狀態都是新的，而且一定會知道這個節點在哪里。
Kademlia網絡提供四種Potocol(RPC)
(1)PING 測試是否節點存在
(2)STORE存儲通知的資料
(3)FIND_NODE 通知其他節點幫助尋找node
(4)FIND_VALUE 通知其他節點幫助尋找Value
而當每一個指令被接受到后，每一個節點都會到k-bucket上搜尋，通過這樣的結構，kad提供一個方便快速且可以被保證在logN次數下找到所需的節點。
通俗的來講就是在kad網絡中，我們每個emule用戶端只負責處理一小部分搜索和查找源的工作。分配這些工作的時候，通過我們每個用戶端的唯一的ID和搜索文件的hash值之間的匹配來決定。比如像我猜我猜我猜猜.rm這個文件由用戶小王來負責（通過該文件的hash值來決定），那么任何其他用戶在下載這個文件的時候都會告訴其他用戶,小王有這個文件，其他用戶去下載這個文件的時候也會詢問小王，小王也會告訴他們誰正在共享這個文件，這樣kad找源的工作就完成了。搜索時候的方法也差不多，只不過是每個人負責一個關鍵字。
整個過程有點像在照線索循序問路而找到正確方向，而不是路上隨便到處抓人在問路。而每個地方里的網絡相關信息，則會隨著電腦及文件的加入而持續更新。好處在于讓你可以搜索整個網絡，而不只是在某一地區。目前來講，這個機制和算法是絕對領先而且非常優秀的。
如何找到用戶小王則是通過將用戶id異或的方式，兩個id的二進位異或值決定他們之間的邏輯距離，如1100距離1101要比距離1001近。那么當一個用戶加入kad后，首先通過一個已知的用戶找到一批用戶的id和ip地址和端口。當該用戶要尋找一個特定用戶A的時候，該用戶先詢問幾個已知的邏輯距離較A較近的用戶，如B用戶,C用戶,D用戶，B，C，D會告訴該用戶他們知道的更加近的用戶的id和ip地址和端口，同理類推，這個用戶最終就能找到A。所以尋找的次數會在logN數量級，這里N代表詢問的人數。
其實也就是一種分散式雜湊的方法，基本上是對網絡上某一特定時刻的文件進行快照(snapshot)，然后將這些信息分散到整個網絡里。 為了找到特定的文件，搜索的要求先到達網絡上的任何一臺電腦上，然后這臺電腦就會再將它轉到另一臺有更多文件信息的電腦。第三臺電腦可能就擁有文件本身──或者也可能再繼續轉到其他有正確信息的電腦。采用這種方法，通常只需要跳轉兩到三次，便可以輕松查找到所需文件。
以上幾個部分，便是對于kad作用原理以及算法的分析，可能好多人看了之后頭大，那么我們普通用戶到底該注意些什么呢？
很簡單，你要作的就是再使用emule的時候打開kad，你會發現有兩個明顯的特點
(1)你的下載速度會加快
(2)你的下載文件的源會增加
以上兩條對于lowid和經常下載源在國外的文件用戶，效果就更為突出，特別對于在ed2k網絡中只有幾個源或者沒有源的文件，在kad網絡中，一般都能找到源，所以說你使用了emule下載文件，基本上不會出現沒有源的請況，無論多長時間，差別只是源的多少個數問題，由于kad網絡都是自動配置的，所以你絲毫不用分心，那么索性我們就打開它，何樂而不為呢？
另外對于我們搜索的時候，如果采用kad網絡搜索,多數情況下找到的文件源會遠遠多于ed2k的全局搜索，對于大家都是一個明智的選擇。
1. ID and Key
Node ID：160 bit （每一個Node擁有一個ID，隨機產生）
Key：160 bit （Key也許是某個很大的數據的SHA-1 hash值）
(Key,Value)這一對數據保存在ID最“接近”Key的Node上。
“接近”的意思是Key和ID之間的“距離”很短。
Kad網絡中“距離”的定義是：d(x,y) = x XOR y，也就是x和y的異或值。
* 選擇XOR作為衡量距離的尺度，是因為XOR有xxx,yyy,zzz,...等特性，具體請看Kademlia的paper [1] section 2.1。
2. k-bucket
每一個Node保持160個 list。對于第 i (0 <= i < 160) 個 list，此 list 中保存著和該 Node 距離為 2*i ~ 2*(i+1) 【2的 i 次方到 2的 i+1 次方】的一些 Node 的信息（Node ID，IP地址，UDP端口）。這些 list 叫做 k-bucket 。k是每一個 listk 中保存的 Node 的最大
個數（比如，20）。
+------------------------+
list 0: | | 距離為[1,2)的node
+------------------------+
（ID前159 bit相同，第160 bit一定不同的node: 1個）
+------------------------+
list 1: | | 距離為[2,4)的node
+------------------------+
（ID前158 bit相同，第159 bit一定不同的node: 2個）
+------------------------+
list 2: | | 距離為[4,8)的node
+------------------------+
（ID前157 bit相同，第158 bit一定不同的node: 4個）
+------------------------+
list 3: | | 距離為[8,16)的node
+------------------------+
（ID前156 bit相同，第157 bit一定不同的node: 8個）
+------------------------+
list 4: | | 距離為[16,32)的node
+------------------------+
（ID前155 bit相同，第156 bit一定不同的node: 16個）
。
。
。
+------------------------+
list 159: | | 距離為[2*159,2*160)的node
+------------------------+
（ID第1 bit不同的node: 2*159個。此list中最多保存最近訪問的k個）
每一個list （k-bucket）中的node按照訪問的時間順序排列，最先訪問的在list頭部，最近訪問的在list的尾部：
Head Tail
| |
V V
+--+ +--+ +--+ +--+ +--+ +--+
| |-->| |-->| |-->| |-->| |--> ... --> | |
+--+ +--+ +--+ +--+ +--+ +--+
Node0 Node1 ... Node[N]
A A
| |
least-recently most-recently
3.k-bucket的刷新
當一個Node收到另一個Node發來的消息的時候，它根據以下規則（least-recently seen eviction policy）來刷新相應的k-bucket:
1) 如果發送者已經在某一個k-bucket中，將它在該 k-bucket 中移動到尾部
2) 如果發送者不在其對應的k-bucket中，并且該 k-bucket 還不滿 k 個Node，將這個發送者加入到 k-bucket 的尾部
如果該 k-bucket 已經滿了（有k個Node），那么接受消息的 Node 向該 k-bucket 中最老的（也就是頭部的）Node發送一個 ping 消息
如果這個最老的 Node 沒有響應，則將它從 k-bucket 中刪除，將新的發送消息的 Node 加入到 k-bucket 的尾部
如果這個最老的 Node 響應了，則將它移動到 k-bucket 的尾部，并拋棄新的 Node 的信息
* 為什么要采取這樣的規則，請看Kademlia的paper [1] section 2.2
4. 基本協議(protocol)
四種基本的RPC：PING, STORE, FIND_NODE, FIND_VALUE
1) PING
PING 探測一個Node是否在線
2) STORE
STORE 以(Key,Value)為參數。指示另一個Node（消息接收者）保存一個(Key, Value)對，以供以后取用。
3) FIND_NODE
FIND_NODE 以一個160 bit的ID作為參數。接收者返回它所知道的最接近該ID的 k 個 Node 的 Contact 信息（ID,UPD Port,IP）。這些 Node 不一定要從同一個 k-bucket 中產生。除非它所有的 k-bucket 中所有的 Node 加在一起都不到 k 個，否則它必需湊足 k 個。
4) FIND_VALUE
FIND_VALUE 以一個160 bit的ID/Key作為參數。如果接收者先前已經收到一個 STORE RPC，而且 STORE 的參數之一 Key 就是當前 FIND_VALUE 的參數，那么，接收者將 STORE 的另一個參數 Value 返回給發送者。否則，FIND_VALUE 和 FIND_NODE 一樣，返回它所知道的最接近該ID的 k 個 Node 的 Contact 信息（ID,UPD Port,IP）。
FIND_VALUE 的意思就是：如果接收者有發送著所要的 Value，就將該 Value 返回。否則，接收者就幫忙找更接近該 ID/Key 的 Node。
所有的 RPC 消息都帶有一個 160 bit的隨機 RPC ID，由發送者產生，接收者在響應每一個消息的時候，返回的消息里面都必需拷貝此 RPC ID。目的是防止地址偽造。PING 消息可以在 RPC 響應里使用捎帶確認機制來獲得發送者網絡地址（原文：pings can also be piggy-backed on RPC replies for the RPC recipient to obtain additional assurance of the sender's network address.）。
* piggyback
捎帶確認(法)
A technique used to return acknowledgement information across a full-duplex (two-way simultaneous) data link without the use of special (acknowledgement) message. The acknowledgement information relating to the flow of message in one direction is embedded (piggybacked) into normal data-carrying message flowing in the reverse direction.
經全雙工(雙向同時)數據鏈路,不用專門(確認)報文返回確認信息所用的技術。與一個方向的報文流有關的確認信息鉗在反方向正常攜帶數據的報文流中。
[1] Kadmelia的paper：<http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf>
5. 節點查找(node lookup)
node lookup:找到距離給定的 ID 最近的 k 個 node
定義 a:系統范圍內的并發參數，比如3。
步驟：
1) 從最近的 k-bucket 里面取出 a 個最近的 node，然后向這 a 個 node 發送并行的、異步的 FIND_NODE RPC。
2) 再次發送 FIND_NODE RPC 給從前一步返回的 node（這一步可以不必等到前一步中所有 a 個 PRC 都返回之后才開始）：
從發送者已知的 k 個最接近目標的 node 當中，取出 a 個還沒有查詢的 node，向這 a 個 node 發送 FIND_NODE RPC。
沒有迅速響應的 node 將被排除出考慮之列，直到其響應。
如果一輪 FIND_NODE RPC 沒有返回一個比已知的所有 node 更接近目標的 node，發送者將再向 k 個最接近目標的、還沒有查詢的 node 發送 FIND_NODE RPC。
3) 查找結束的條件：發送者已經向 k 個最近的 node 發送了查詢，并且也得到了響應。
6. 存儲
步驟：
1) 使用node lookup算法，找到距離 Key 最近的 k 個 node
2) 向這 k 個 node 發送 STORE RPC
3) 每一個 node 必要的時候重新發布(re-publish)所有的
（對于當前的 Kademlia 應用(文件共享)，每一個
7. 搜索
步驟：
1) 使用 FIND_VALUE 代替 FIND_NODE 進行"node lookup"過程。一旦任何其他 node 返回了所要的 Value，搜索的過程就結束。
2) cache: 如果搜索成功，搜索的發起者將這個
顯然，有了cache之后，以后對于該
如果一個
為了避免過度緩存(over-caching)，每一個
8. 刷新bucket (refresh bucket)
所有的 bucket 通過node之間的請求來刷新。
如果某一個bucket在過去一個小時之內沒有任何的node lookup操作，那么這個node就隨機搜索一個在這個bucket覆蓋范圍內的ID。
9. node加入網絡
步驟：
1) 一個新加入的node（假設為u）必需首先獲得一個已經在網絡中的node（比如為w）的contact信息。
2) u 首先將 w 加入到其對應的 k-bucket 中
3) u 執行一個對自己ID的 node lookup 操作
4) u 刷新所有的 k-bucket
