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