一、P2P及DHT網(wǎng)絡(luò)簡(jiǎn)單介紹：

P2P在思想上可以說(shuō)是internet思想/精神/哲學(xué)非常集中的體現(xiàn)，共同的參與，透明的開(kāi)放，平等的分享（讓我想起之前學(xué)習(xí)過(guò)的，現(xiàn)在正在瘋狂熱炒的云計(jì)算的“中央集權(quán)”制度）?；赑2P技術(shù)的應(yīng)用有很多，包括文件分享，即時(shí)通信，協(xié)同處理，流媒體通信等等。通過(guò)這些應(yīng)用的接觸，分析和理解，P2P其本質(zhì)是一種新的網(wǎng)絡(luò)傳播技術(shù)，這種新的傳播技術(shù)打破了傳統(tǒng)的C/S架構(gòu)，逐步地去中心化，扁平化，這或許在一定程度上應(yīng)證了”世界是平的”趨勢(shì)，呵呵。P2P文件分享的應(yīng)用(BTs/eMules等)是P2P技術(shù)最集中的體現(xiàn)，我們這里的研究也是以P2P文件分享網(wǎng)絡(luò)作為入口，P2P文件分享網(wǎng)絡(luò)的發(fā)展大致有以下幾個(gè)階段，包含tracker服務(wù)器的網(wǎng)絡(luò)，無(wú)任何服務(wù)器的純DHT網(wǎng)絡(luò)，?混合型P2P網(wǎng)絡(luò)。DHT網(wǎng)絡(luò)發(fā)展即有“思想/文化”上的“發(fā)展”，也有一定的商業(yè)上的需求（版權(quán)管理）。

DHT全稱(chēng)叫分布式哈希表(Distributed?Hash?Table)，是一種分布式存儲(chǔ)方法，一類(lèi)可由鍵值來(lái)唯一標(biāo)示的信息按照某種約定/協(xié)議被分散地存儲(chǔ)在多個(gè)節(jié)點(diǎn)上，這樣也可以有效地避免“中央集權(quán)式”的服務(wù)器（比如：tracker）的單一故障而帶來(lái)的整個(gè)網(wǎng)絡(luò)癱瘓。實(shí)現(xiàn)DHT的技術(shù)/算法有很多種，常用的有：Chord,?Pastry,?Kademlia等。我們這里要研究的是Kademlia算法，因?yàn)锽T及BT的衍生派（Mainline,?Btspilits,?Btcomet,?uTorrent…），eMule及eMule各類(lèi)Mods(verycd,?easy?emules,?xtreme…)等P2P文件分享軟件都是基于該算法來(lái)實(shí)現(xiàn)DHT網(wǎng)絡(luò)的，BT采用Python的Kademlia實(shí)現(xiàn)叫作khashmir（科什米爾，印巴沖突地帶？），有如下官網(wǎng)。eMule采用C++的Kademlia實(shí)現(xiàn)干脆就叫作Kad，當(dāng)然它們之間有些差別，但基礎(chǔ)都是Kademlia。我們這里以BT-DHT為例進(jìn)行分析介紹，下面說(shuō)到的DHT都可以默認(rèn)是BT-Kademlia-DHT。

官方網(wǎng)站：http://www.tribler.org/trac/wiki/Khashmir

二、Kademlia實(shí)現(xiàn)原理

各種DHT的實(shí)現(xiàn)算法，不論是Chord,?Pastry還是Kademlia，其最直接的目標(biāo)就是以最快的速度來(lái)定位到期望的節(jié)點(diǎn)，在P2P文件分享應(yīng)用中則是以最快的速度來(lái)查找到正在分享某一文件/種子的peers列表信息。因?yàn)槊總€(gè)節(jié)點(diǎn)都是分布式存在于地球的任何角落，如果用地理距離來(lái)衡量?jī)晒?jié)點(diǎn)間的距離則可能給計(jì)算帶來(lái)極大復(fù)雜性甚至不可能進(jìn)行衡量，因此基本所有的DHT算法都是采用某種邏輯上的距離，在Kademlia則采用簡(jiǎn)單的異或計(jì)算來(lái)衡量?jī)晒?jié)點(diǎn)間的距離，它和地理上的距離沒(méi)有任何關(guān)系，但卻具備幾何公式的絕大特征：

（1）節(jié)點(diǎn)和它本身之間的異或距離是0

（2）異或距離是對(duì)稱(chēng)的：即從A到B的異或距離與從B到A的異或距離是等同的

（3）異或距離符合三角形不等式：給定三個(gè)頂點(diǎn)A?B?C，假如AC之間的異或距離最大,那么AC之間的異或距離必小于或等于AB異或距離和BC異或距離之和.

（4）對(duì)于給定的一個(gè)距離，距離A只存在有唯一的一個(gè)節(jié)點(diǎn)B，也即單向性，在查找路徑上也是單向的，這個(gè)和地理距離不同。

Kademlia中規(guī)定所有的節(jié)點(diǎn)都具有一個(gè)節(jié)點(diǎn)iD，該節(jié)點(diǎn)iD的產(chǎn)生方法和種子文件中的info?hash采用相同算法:即sha-1（安全hash算法），因此每個(gè)節(jié)點(diǎn)的id，以及每個(gè)共享文件/種子的info-hash都是唯一的，并且都是20個(gè)字符160bits位組成。兩個(gè)節(jié)點(diǎn)間的距離就是兩個(gè)節(jié)點(diǎn)id的異或結(jié)果，節(jié)點(diǎn)離鍵值（種子）的距離為該節(jié)點(diǎn)的id和該種子文件的info-hash的異或結(jié)果。Kademlia在異或距離度量的基礎(chǔ)上又把整個(gè)DHT網(wǎng)絡(luò)拓?fù)浣M織成一個(gè)二叉前綴樹(shù)（XuanWu系統(tǒng)中arp的實(shí)現(xiàn)則是一個(gè)例子），所有的節(jié)點(diǎn)(所有的正在運(yùn)行的，并且開(kāi)取了DHT功能的Bt,Btspilits應(yīng)用)等作為該二叉前綴樹(shù)的葉子節(jié)點(diǎn)，可以想象這棵二叉樹(shù)可以容納多達(dá)2128個(gè)葉子（節(jié)點(diǎn)），這足以組織任何規(guī)模的網(wǎng)絡(luò)了。對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)按照離自己的遠(yuǎn)近區(qū)域又可以把這棵樹(shù)劃分為160棵子樹(shù)，每一個(gè)子樹(shù)和該節(jié)點(diǎn)都有一個(gè)共同的前綴，共同前綴越少離得越遠(yuǎn)。如下圖所示：

以上圖紅色節(jié)點(diǎn)位例0011位例，它可以把其他的節(jié)點(diǎn)劃分位4棵不同子樹(shù)，離自己越近子樹(shù)和自己有越長(zhǎng)的公共前綴，如果節(jié)點(diǎn)是均勻分布則離自己越近的子樹(shù)含有的葉子節(jié)點(diǎn)更少（兄弟只有一個(gè)即和自己有159個(gè)共同前綴的那個(gè)）。因?yàn)楣?jié)點(diǎn)都位于該樹(shù)最底層的葉子位置，水平看上去則所有的葉子都在一條線上，如果把這條線當(dāng)作2128空間的每一個(gè)點(diǎn)，則更能體現(xiàn)上面的劃分特性（折半拆分）。為了能快速到達(dá)這160棵子樹(shù)，處于DHT網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都記錄了每棵子樹(shù)上的k個(gè)節(jié)點(diǎn)的信息（ip,port,id），在BT中K固定為8，比如上圖中紅色節(jié)點(diǎn)就可能保存有最左邊子樹(shù)的8個(gè)葉子節(jié)點(diǎn)信息，當(dāng)然靠近自己的子樹(shù)可能沒(méi)有8個(gè)葉子，則把所有當(dāng)前存在的葉子記錄上去，這份記錄信息在Kademlia算法中叫作K桶，也叫作“路由表”，當(dāng)然這個(gè)“路由表”的信息和我們IP路由的含義有點(diǎn)不同，它代表的是為了到達(dá)處于距離自己某范圍[?2i?—?2i+1?)的節(jié)點(diǎn)，可以通過(guò)該范圍內(nèi)的選取的k個(gè)節(jié)點(diǎn)來(lái)進(jìn)一步定位，下圖是一個(gè)“路由表”結(jié)構(gòu)：

.注意：這里只是一個(gè)舉例，在實(shí)際的“路有表”中可能是沒(méi)有160份，因?yàn)槁酚杀淼纳蛇^(guò)程是對(duì)半分拆的，最初只有一個(gè)K桶（范圍為:0—2160，且只包括自己），在插如過(guò)程中當(dāng)該K桶節(jié)點(diǎn)大于k(8)時(shí)，則分拆成兩半，一半包括自身節(jié)點(diǎn)，一半不包括自身。循環(huán)往復(fù)下去，則形成一個(gè)動(dòng)態(tài)的大?。?<=len(table)<=160）的“路由表”

每一個(gè)新加入到DHT網(wǎng)絡(luò)的節(jié)點(diǎn)最開(kāi)始這些“路由表”信息都是空的，它有以下幾個(gè)方式可以來(lái)逐步生成和形成自己的“路由表”信息：

1）?如果本節(jié)點(diǎn)曾經(jīng)啟動(dòng)過(guò)程，則從保存的“路由表”文件中直接讀取然后刷新該“路由表“

2）?如果該節(jié)點(diǎn)第一次啟動(dòng)（比如新安裝BTSpilits然后啟動(dòng)），并且該節(jié)點(diǎn)自帶有“超級(jí)節(jié)點(diǎn)“則

通過(guò)這些“超級(jí)節(jié)點(diǎn)“來(lái)間接地生成自己的”路由表“（在Kashmir的某個(gè)版本中有一個(gè)文件保存這些”超級(jí)接點(diǎn)的信息“，BTSplits,?BTcomet,?eMules則內(nèi)嵌有20多個(gè)）

3）如果第一次啟動(dòng)的節(jié)點(diǎn)沒(méi)有這些所謂的“超級(jí)節(jié)點(diǎn)”(比如Mainline則沒(méi)有這個(gè)功能)，則它的路由表生成過(guò)程需要推遲到download文件過(guò)程。它會(huì)從它獲取到的種子文件中提取nodes字段，該字段是做種子（支持DHT網(wǎng)絡(luò)的種子）的時(shí)候生成的，一般nodes字段設(shè)置為該原始種子的ip和port，或者是做種子的節(jié)點(diǎn)離該種子的info-hash最近的k個(gè)節(jié)點(diǎn)。通過(guò)這些nodes字段中的節(jié)點(diǎn)通過(guò)來(lái)間接地生成自己的路由表。

4）動(dòng)態(tài)建立過(guò)程，該過(guò)程為節(jié)點(diǎn)經(jīng)過(guò)上面的初始化后，在下載或者上傳或者無(wú)任務(wù)過(guò)程中有收到任何節(jié)點(diǎn)發(fā)送的任何消息，都會(huì)去檢查當(dāng)前的“路由表”并嘗試按照一定的規(guī)則去建立/刷新路由表。

我們知道DHT網(wǎng)絡(luò)最主要的目標(biāo)是替代Tracker（純P2P網(wǎng)絡(luò)，無(wú)traker）或者說(shuō)作為T(mén)racker的一個(gè)備份（混合型P2P網(wǎng)絡(luò)，當(dāng)前基本所有主流文件分享的應(yīng)用都是該類(lèi)型）。而Tracker最主要功能就是對(duì)每一個(gè)分享文件（種子）維護(hù)一個(gè)peers列表，然后告訴需要下載的詢(xún)問(wèn)者Client。實(shí)現(xiàn)的方法就是把Tracker集中維護(hù)的所有種子的peers-list信息利用DHT的方法散列并保存到所有的DHT網(wǎng)絡(luò)中的節(jié)點(diǎn)上去，然后在此基礎(chǔ)上提供查找的方法?！奥酚斜怼弊饔镁褪菫榱思铀龠@個(gè)查找的過(guò)程的。在DHT實(shí)現(xiàn)中包括兩種類(lèi)型的查找，一種是查找nodes(find_nodes)，另一種是查找peers（get_peers）。查找nodes的過(guò)程主要是為了建立本地的“路由表”，它的最終目的是后面查找peers。查找節(jié)點(diǎn)的過(guò)程大概是這樣，如果節(jié)點(diǎn)x需要查找節(jié)點(diǎn)y，則x首先從xor(x,y)對(duì)應(yīng)的本地K桶中得到k個(gè)比較closer的節(jié)點(diǎn)，然后向這些比較close的k個(gè)節(jié)點(diǎn)繼續(xù)詢(xún)問(wèn)它是否有離y更近的節(jié)點(diǎn)，這些k個(gè)節(jié)點(diǎn)當(dāng)然也從自己的對(duì)應(yīng)的K桶中返回k個(gè)更近的節(jié)點(diǎn)給x，x然后再?gòu)姆祷亟Y(jié)果中選取k個(gè)更more?closer節(jié)點(diǎn)重復(fù)上面的動(dòng)作，直到不能返回更近的節(jié)點(diǎn)為止，則最后找到的k個(gè)節(jié)點(diǎn)即為the?most?closest?nodes，在這個(gè)過(guò)程中返回的任何k個(gè)close的節(jié)點(diǎn)都會(huì)嘗試去插到自己的路由表中去。而x查找peers-list的方法則和上面查找節(jié)點(diǎn)的方法類(lèi)似，不同的是它是以info-hash作為參數(shù)進(jìn)行查找，并且如果在查找過(guò)程中有任何一個(gè)節(jié)點(diǎn)返回了(info-hash,?peers-list)對(duì)則提前結(jié)束查找。當(dāng)一個(gè)節(jié)點(diǎn)通過(guò)上面方法得到了peers-list后，則會(huì)試圖對(duì)每個(gè)peers主動(dòng)發(fā)起TCP的連接繼續(xù)后面真實(shí)的下載過(guò)程（該過(guò)程由peer-peer?protocol協(xié)議規(guī)定），同時(shí)會(huì)把自己的peer信息發(fā)送給先前的告訴者和自己K桶中的k個(gè)最近的節(jié)點(diǎn)存儲(chǔ)該peer-list信息。該信息在該k個(gè)節(jié)點(diǎn)上可以保存24個(gè)小時(shí)，24小時(shí)后如果沒(méi)有收到x發(fā)送的更新消息則失效。因此一個(gè)活動(dòng)的節(jié)點(diǎn)存儲(chǔ)有兩部份的信息，一部分是本地的“路由表”，另一部分則是(info-hash,?peers-list)列表信息（可有多個(gè)）。Info-hash的值當(dāng)然也屬于(0-2160)空間的一部分，但是它和節(jié)點(diǎn)id不同，節(jié)點(diǎn)iD是可以作為那棵無(wú)形的二叉前綴樹(shù)的葉子（為什么是無(wú)形的，因?yàn)槊總€(gè)節(jié)點(diǎn)其實(shí)是沒(méi)有用數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這個(gè)棵的樹(shù)的），而info-hash則只能附著在離它的值最近的node?id上面。

三、kademlia的消息：

為了實(shí)現(xiàn)上面的“路由表”建立，刷新，獲取peers-list,保存peers-list這些功能，kademlia定義四個(gè)最基本的KRPC操作:

（１）ping操作，作用是探測(cè)一個(gè)節(jié)點(diǎn)，用以判斷該節(jié)點(diǎn)是否仍然在線。

（２）store操作，作用是通知一個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)<key,value>對(duì)，以便以后查詢(xún)需要。

（３）find_node操作，作用是從自己的“路由表”對(duì)應(yīng)的K桶中返回k個(gè)節(jié)點(diǎn)信息(IP?address,UDP?port,Node?ID)給發(fā)送者

（４）faind_value?操作，作用是把info-hash作為參數(shù)，如果本操作接收者正好存儲(chǔ)了info-hash的peers則返回peers?list，否則從自己的“路由表“中返回離info-hash更近的k個(gè)節(jié)點(diǎn)信息（同find_node過(guò)程）。

上面只是最基本的操作，一次nodes或者info-hash的查找lookup過(guò)程則需要節(jié)點(diǎn)進(jìn)行若干次上面的find操作的，一個(gè)遞歸查找的過(guò)程。利用上面的操作更精確的描述一次一個(gè)節(jié)點(diǎn)x要查找ID值為t?的節(jié)點(diǎn)，?過(guò)程如下：

1、?計(jì)算到t?的距離：d(x,y)?=?x⊕y

2、?從x?的第[㏒?d]個(gè)K?桶中取出α?個(gè)節(jié)點(diǎn)的信息（各個(gè)實(shí)現(xiàn)α值不一樣，有些是3有些則等于k值），同時(shí)進(jìn)行FIND_NODE?操作。如果這個(gè)K?桶中的信息少于α?個(gè)，則從附近多個(gè)桶中選擇距離最

接近d?的總共α個(gè)節(jié)點(diǎn)。

3、?對(duì)接受到查詢(xún)操作的每個(gè)節(jié)點(diǎn)，如果發(fā)現(xiàn)自己就是t，則回答自己是最接近t?的。否則測(cè)量自己和t?的距離，并從自己對(duì)應(yīng)的K?桶中選擇α?個(gè)節(jié)點(diǎn)的信息給x。

4、?X?對(duì)新接受到的每個(gè)節(jié)點(diǎn)都再次執(zhí)行FIND_NODE?操作，此過(guò)程不斷重復(fù)執(zhí)行，直到

每一個(gè)分支都有節(jié)點(diǎn)響應(yīng)自己是最接近t?的，或者說(shuō)FIND_NODE操作返回的節(jié)點(diǎn)值沒(méi)有都已經(jīng)被查找過(guò)了，即找不到更近的節(jié)點(diǎn)了。

5、?通過(guò)上述查找操作，x?得到了k?個(gè)最接近t?的節(jié)點(diǎn)信息。

注意：這里用“最接近”這個(gè)說(shuō)法，是因?yàn)镮D?值為t?的節(jié)點(diǎn)不一定存在網(wǎng)絡(luò)中，也就是說(shuō)t?沒(méi)有分配給任何一臺(tái)電腦。

查找peers-list的過(guò)程則換成find_value動(dòng)作，但注意前文提到的區(qū)別即可以有類(lèi)似的描述。

上面的四個(gè)原始在BT-DHT的實(shí)現(xiàn)上則進(jìn)行了重命名，定義了如下四類(lèi)信息，它們叫作KRPC（K代表Khashmila/Kademlia），通過(guò)udp進(jìn)行發(fā)送，一個(gè)請(qǐng)求一個(gè)響應(yīng)或者錯(cuò)誤。

（1）?Ping（和Kademlia同名同功能）

Beconded（以BitSprits為例）:

Ping?Request格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxxxxe1:q4:ping1:t4:tttt1:y1:qe

表示的含義：此操作為ping操作請(qǐng)求，參數(shù)為發(fā)送者的id是：xxxxxxxxxxxxxxxxxx

Ping?Reponse格式:

d1:rd2:id20:yyyyyyyyyyyyyyyyyy?e1:t4:1:y1:re

返回的數(shù)據(jù)中只包括有一個(gè)響應(yīng)者的id信息。

（2）?find_node（和Kademlia同名同功能）

Beconded（以BitSprits為例）:

find_node?Request格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxxxxx6:target20:yyyyyyyyyyyyyyyyyyyy1:q9:find_node1:t4:1:y1:qe

表示的含義：此操作為find_node請(qǐng)求，參數(shù)為發(fā)送者id及目標(biāo)節(jié)點(diǎn)的id

find_node?Reponse格式：

d1:rd2:id20:xxxxxxxxxxxxxxxxxxxx5:nodes208:nnnnnnnnnnnnn5:token20:ooooooooooooo1:t4:ttt?1:y1:re

表示的含義是：找到了8個(gè)最近的節(jié)點(diǎn)，nodes208表示8個(gè)node信息（ip,port,id）共208Bytes

（3）?get_peers（對(duì)應(yīng)Kademlia中的find_value消息）

Beconded（以BitSprits為例）:

Get_peers請(qǐng)求格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxxxxx9:info_hash20:zzzzzzzzzzzzzzzzzzzze1:q9:get_peers1:t4:tttt1:y1:qe

表示的含義：此操作為get_peers操作請(qǐng)求，參數(shù)為：發(fā)送者的id和要查詢(xún)種子的info-hash。

Get_peers響應(yīng)格式有兩種，一種是找到了節(jié)點(diǎn)含有該info-hash的peers列表信息，如下格式：

表示的含義：

d1:rd2:id20:xxxxxxxxxxxxxxxxxxx5:token20:ooooooooooooooooooo6:valuesl6:(ip1,port1)+(ip2,port2)+(ipi,porti)…e1:t4:tttt1:y1:re

(values后面跟上的則是peers列表，ip,?port)

另一種是沒(méi)有找到列表信息，如下格式：

d1:rd2:id20:xxxxxxxxxxxxxxxx5:nodes208:nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn?5:token20:ooooooooooooooo1:t4:tttt1:y1:re

表示的含義為：

沒(méi)有找到存有info-hash的節(jié)點(diǎn)，但找到了離該info-hash更近的8個(gè)節(jié)點(diǎn)，nodes208表示8個(gè)node信息（ip,port,id）共208bytes

（4）?announce_peer（對(duì)應(yīng)Kademlia中的store消息）

Beconded（以BitSprits為例）:

announce?_peers請(qǐng)求格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxx9:info_hash20:zzzzzzzzzzzzzzzzzz4:porti10756e5:token20:ooooooooooooooooo1:q13:announce_peer1:t4:tttt1:y1:qe

表示的含義是：此操作為announce_peer請(qǐng)求操作，告訴對(duì)端我這邊對(duì)info-hash文件上傳和下載，可以成為peers?list中的一員，端口號(hào)是10756.

Announce_peer?Reponse格式

d1:rd2:id20:xxxxxxxxxxxxxxxxxxxx2:ip4:pppp1:t4:tttt1:v4:UTb*1:y1:re

附件為抓取的分別為為一簡(jiǎn)單下載過(guò)程/一初始初始化路由表的數(shù)據(jù)包：可以對(duì)照進(jìn)行分析

四、Bttorent?DHT實(shí)現(xiàn)幾個(gè)重要過(guò)程

種子制作：

1）./maketorrent-console參數(shù)use_tracker設(shè)置為false，則不會(huì)產(chǎn)生announce?tracker字段

2）?讀取本地“路由表”文件，并從中找出k個(gè)離info-hash最近的節(jié)點(diǎn)，作為nodes字段

啟動(dòng)過(guò)程：

1）?從routing_table文件中裝載之前保存的”路由表”K桶信息，初始化內(nèi)存“路由表”信息

2）?強(qiáng)制刷新“路由表“中的每一個(gè)K桶，刷新過(guò)程是隨機(jī)產(chǎn)生一id進(jìn)行findNode查找。

刷新路由表的過(guò)程：

1）?啟動(dòng)的時(shí)候進(jìn)行強(qiáng)制刷新

2）?每15分鐘如果K桶中的信息沒(méi)有進(jìn)行更新的話，則進(jìn)行刷新一次K桶，即refreshTable

3）?每5分鐘進(jìn)行一次checkpoint操作，以把當(dāng)前的路由表存放到routing_table文件中

routing_table文件的格式：

{'id':node.id,?'host':node.host,?'port':node.port,?'age':int(node.age)}

有些實(shí)現(xiàn)是用SQLite數(shù)據(jù)庫(kù)來(lái)實(shí)現(xiàn)這部分功能的。

每一個(gè)“路由表”的K桶都有一個(gè)“最近更新時(shí)間“屬性，當(dāng)收到該桶中任何節(jié)點(diǎn)的ping響應(yīng)，或者有任何節(jié)點(diǎn)被加入或者被替換，則該屬性都需保持更新，并且重啟一個(gè)15分鐘的定時(shí)器，如果定時(shí)器超時(shí)（15分鐘內(nèi)該K桶節(jié)點(diǎn)沒(méi)有任何更新操作），則會(huì)對(duì)該K桶進(jìn)行一次refresh操作，操作的過(guò)程是從該K桶范圍選出一隨機(jī)的ID，然后對(duì)該ID進(jìn)行find_node操作?！奥酚杀怼敝械墓?jié)點(diǎn)需要保持live狀態(tài)，即得保證沒(méi)有離線，如果向路由表中的一節(jié)點(diǎn)發(fā)出的連續(xù)3次請(qǐng)求都沒(méi)有收到響應(yīng)，則認(rèn)為該節(jié)點(diǎn)失效。

refreshTable（force=1）過(guò)程：

（1）?如果force=1，則對(duì)當(dāng)前每個(gè)K桶都進(jìn)行刷新

（2）?如果K桶當(dāng)前nodes數(shù)小于k（8），則也進(jìn)行刷新

（3）?如果K桶中存在無(wú)效的節(jié)點(diǎn)，即連續(xù)三個(gè)消息沒(méi)有收到響應(yīng)的節(jié)點(diǎn)

（4）?如果K桶中所有節(jié)點(diǎn)沒(méi)有交互的時(shí)間超過(guò)15分鐘，則也進(jìn)行刷新

當(dāng)一個(gè)節(jié)點(diǎn)收到任何一個(gè)RPC消息（請(qǐng)求和響應(yīng)）后（ping/find/getPeers/announce_peer）都會(huì)去檢查一下該消息的發(fā)送者是否在本地的“路由表“中，如果該發(fā)送者已經(jīng)存在節(jié)點(diǎn)的本地“路由表”中，則會(huì)把該發(fā)送者從其對(duì)應(yīng)的K桶移動(dòng)到該K桶的末尾。如果該發(fā)送者不在節(jié)點(diǎn)的“路由表”中則會(huì)去嘗試插入到本地”路由表“K桶中，這也是“路由表”的動(dòng)態(tài)建立過(guò)程的一種，過(guò)程如下：

（0）??找到該發(fā)送者的對(duì)應(yīng)的K桶

（1）?如果該節(jié)點(diǎn)是響應(yīng)消息中發(fā)現(xiàn)的，則更新該節(jié)點(diǎn)lastSeen?=?time()時(shí)間

（2）?如果該K桶大小小于k（8）則直接插到該K桶后面

（3）?如果該K桶已經(jīng)滿了，則檢查是否有無(wú)效的節(jié)點(diǎn)，如果有則把這些無(wú)效節(jié)點(diǎn)刪除，并把該節(jié)點(diǎn)放入K桶末尾。（但后面會(huì)對(duì)這些早已經(jīng)存在的節(jié)點(diǎn)進(jìn)行再一次的ping操作，來(lái)進(jìn)一步確定是否無(wú)效了，如果收到響應(yīng)，則把這些節(jié)點(diǎn)重新放如K桶）

（4）?如果該K桶已經(jīng)滿了，并且所有的節(jié)點(diǎn)都是有效的，則需要查看自身（本客戶(hù)短）是否在該K桶中（即該K桶是否是自己所在的K桶），如果不是則直接丟棄該節(jié)點(diǎn)

（5）?如果該K桶不是自身所在的K桶，則需要進(jìn)行K桶分拆。拆分的方法即是一個(gè)變?yōu)閮蓚€(gè)等長(zhǎng)K桶，一個(gè)包括自身，一個(gè)不包括。

（6）?對(duì)該節(jié)點(diǎn)添加到分拆后的一個(gè)K桶中去。

findNodes(id,?invalid=True)的過(guò)程是：//該過(guò)程是內(nèi)部過(guò)程，給下面findNode(

（0）?如果該節(jié)點(diǎn)在自己的K桶中，則直接返回，結(jié)束該過(guò)程

（1）?如果invalid=True，則需要排除當(dāng)前無(wú)效的節(jié)點(diǎn)

（2）?如果上面選取該K桶中的所有節(jié)點(diǎn)小于K(8)，則需要從其他桶中補(bǔ)充，如下

（3）?把左右相鄰的兩個(gè)K桶中的節(jié)點(diǎn)補(bǔ)充進(jìn)去，然后把所有這些節(jié)點(diǎn)按照離id距離遠(yuǎn)近進(jìn)行排序，選取最近的K(8)個(gè)節(jié)點(diǎn)

（4）?返回最后得到的最近的K個(gè)節(jié)點(diǎn)。

findNode(id)的過(guò)程是：

（1）?從自己本地的“路由表“取離id最近的K桶，返回k(8)個(gè)nodes信息

（2）?從上面k個(gè)信息中選取a個(gè)（3）個(gè)，然后發(fā)送findNode消息給這3個(gè)節(jié)點(diǎn)

（3）?該3個(gè)節(jié)點(diǎn)查找自己的“路由表“同時(shí)返回k個(gè)nodes信息

（4）?從上面得到的3*k個(gè)節(jié)點(diǎn)在重復(fù)

Keyexpired過(guò)程：

1）?節(jié)點(diǎn)存放的（info-hash，peers-list）如果24小時(shí)沒(méi)有收到原節(jié)點(diǎn)的更新則視作無(wú)效

2）?當(dāng)前仍然活動(dòng)的peer-lists中的節(jié)點(diǎn)需要24小時(shí)向其close節(jié)點(diǎn)進(jìn)行刷新info-hash，peers-list。

3）當(dāng)前仍然活動(dòng)的peer-lists中的節(jié)點(diǎn)如果在自己的路由表中發(fā)現(xiàn)有離info-hash更近的節(jié)點(diǎn)，則會(huì)把自（info-hash，peers-list）announce給它們。

在BT程序中，對(duì)外只有一個(gè)過(guò)程，那就是下面的getPeersAndAnnounce過(guò)程，該過(guò)程的作用就是對(duì)提供的info-hash找到一個(gè)peers?list表，并且把自己作為一個(gè)peer告訴給別人：

getPeersAndAnnounce過(guò)程：

（0）?該過(guò)程包括了getPeers和Announce_peer兩個(gè)過(guò)程

（1）?getPeers的過(guò)程首先是在自己的本地的（info-hash,?peers-list）表中進(jìn)行查找，如果查找到則直接進(jìn)行連接

（2）?如果本地沒(méi)有info-hash的key,values，則需要進(jìn)行遠(yuǎn)程查找，查找的過(guò)程是

（3）?先從info-hash對(duì)應(yīng)的K桶中找k個(gè)節(jié)點(diǎn)，然后分別向它們發(fā)送getpeers原始RPC消息

（4）?分析上面k個(gè)節(jié)點(diǎn)的響應(yīng)信息，如果響應(yīng)信息中存在values字段，則說(shuō)明命中一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)保存有info-hash的peers-list信息，保存起來(lái)。如果響應(yīng)消息中只有nodes字段，則該字段后面跟上的是k（8）個(gè)更接近于info-hash的節(jié)點(diǎn)，判斷這些節(jié)點(diǎn)是否發(fā)送過(guò)，如果沒(méi)有則把這些節(jié)點(diǎn)保存起來(lái)繼續(xù)發(fā)送getPeers?RPC消息，直到收到響應(yīng)消息中帶有values字段，或者響應(yīng)消息中所有的節(jié)點(diǎn)都發(fā)送過(guò)了（沒(méi)有更接近info-hash的節(jié)點(diǎn)了）

（5）?當(dāng)收到節(jié)點(diǎn)對(duì)get_peers響應(yīng)包中包括有(info-hash,peers-list)后，則首先向響應(yīng)者發(fā)送announce，然后向自己K桶中離info-hash最近的k個(gè)節(jié)點(diǎn)發(fā)送announce_peer消息

Ping消息的發(fā)送過(guò)程：

1）?對(duì)于DHT種子文件中nodes逐個(gè)節(jié)點(diǎn)發(fā)送ping消息，有響應(yīng)者則添加到“路由表”中去

2）?當(dāng)插入新節(jié)點(diǎn)到“路由表”中時(shí)，如果該“路由表”K桶已滿，則會(huì)選擇K桶的頭部節(jié)點(diǎn)進(jìn)行ping操作，如果該頭節(jié)點(diǎn)仍然在線，則直接丟棄該節(jié)點(diǎn)（這是基于一種越長(zhǎng)時(shí)間在線則可能以后越長(zhǎng)在線的概率統(tǒng)計(jì)），否則刪除頭節(jié)點(diǎn)，并把新節(jié)點(diǎn)插到K桶尾。

五、參考資料：

１）Kademlia-A-P2P-Information-System.pdf

２）http://www.tribler.org/trac/wiki/Khashmir

3）http://www.bittorrent.org/beps/bep_0005.html

4）BitTorrent-4.4.0代碼