一、P2P及DHT網絡簡單介紹：

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

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

官方網站：http://www.tribler.org/trac/wiki/Khashmir

二、Kademlia實現原理

各種DHT的實現算法，不論是Chord,?Pastry還是Kademlia，其最直接的目標就是以最快的速度來定位到期望的節點，在P2P文件分享應用中則是以最快的速度來查找到正在分享某一文件/種子的peers列表信息。因為每個節點都是分布式存在于地球的任何角落，如果用地理距離來衡量兩節點間的距離則可能給計算帶來極大復雜性甚至不可能進行衡量，因此基本所有的DHT算法都是采用某種邏輯上的距離，在Kademlia則采用簡單的異或計算來衡量兩節點間的距離，它和地理上的距離沒有任何關系，但卻具備幾何公式的絕大特征：

（1）節點和它本身之間的異或距離是0

（2）異或距離是對稱的：即從A到B的異或距離與從B到A的異或距離是等同的

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

（4）對于給定的一個距離，距離A只存在有唯一的一個節點B，也即單向性，在查找路徑上也是單向的，這個和地理距離不同。

Kademlia中規定所有的節點都具有一個節點ID，該節點ID的產生方法和種子文件中的info?hash采用相同算法:即sha-1（安全hash算法），因此每個節點的id，以及每個共享文件/種子的info-hash都是唯一的，并且都是20個字符160bits位組成。兩個節點間的距離就是兩個節點id的異或結果，節點離鍵值（種子）的距離為該節點的id和該種子文件的info-hash的異或結果。Kademlia在異或距離度量的基礎上又把整個DHT網絡拓撲組織成一個二叉前綴樹（XuanWu系統中arp的實現則是一個例子），所有的節點(所有的正在運行的，并且開取了DHT功能的Bt,Btspilits應用)等作為該二叉前綴樹的葉子節點，可以想象這棵二叉樹可以容納多達2128個葉子（節點），這足以組織任何規模的網絡了。對于每個節點來說按照離自己的遠近區域又可以把這棵樹劃分為160棵子樹，每一個子樹和該節點都有一個共同的前綴，共同前綴越少離得越遠。如下圖所示：

（注意：上圖只是一個劃分子樹的例子，節點都沒有位于同一層的葉子上面）

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

.注意：這里只是一個舉例，在實際的“路有表”中可能是沒有160份，因為路由表的生成過程是對半分拆的，最初只有一個K桶（范圍為:0—2160，且只包括自己），在插如過程中當該K桶節點大于k(8)時，則分拆成兩半，一半包括自身節點，一半不包括自身。循環往復下去，則形成一個動態的大小（1<=len(table)<=160）的“路由表”

每一個新加入到DHT網絡的節點最開始這些“路由表”信息都是空的，它有以下幾個方式可以來逐步生成和形成自己的“路由表”信息：

1）?如果本節點曾經啟動過程，則從保存的“路由表”文件中直接讀取然后刷新該“路由表“

2）?如果該節點第一次啟動（比如新安裝BTSpilits然后啟動），并且該節點自帶有“超級節點“則

通過這些“超級節點“來間接地生成自己的”路由表“（在Kashmir的某個版本中有一個文件保存這些”超級接點的信息“，BTSplits,?BTcomet,?eMules則內嵌有20多個）

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

4）動態建立過程，該過程為節點經過上面的初始化后，在下載或者上傳或者無任務過程中有收到任何節點發送的任何消息，都會去檢查當前的“路由表”并嘗試按照一定的規則去建立/刷新路由表。

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

三、kademlia的消息：

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

（１）ping操作，作用是探測一個節點，用以判斷該節點是否仍然在線。

（２）store操作，作用是通知一個節點存儲一個<key,value>對，以便以后查詢需要。

（３）find_node操作，作用是從自己的“路由表”對應的K桶中返回k個節點信息(IP?address,UDP?port,Node?ID)給發送者

（４）faind_value?操作，作用是把info-hash作為參數，如果本操作接收者正好存儲了info-hash的peers則返回peers?list，否則從自己的“路由表“中返回離info-hash更近的k個節點信息（同find_node過程）。

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

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

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

接近d?的總共α個節點。

3、?對接受到查詢操作的每個節點，如果發現自己就是t，則回答自己是最接近t?的。否則測量自己和t?的距離，并從自己對應的K?桶中選擇α?個節點的信息給x。

4、?X?對新接受到的每個節點都再次執行FIND_NODE?操作，此過程不斷重復執行，直到

每一個分支都有節點響應自己是最接近t?的，或者說FIND_NODE操作返回的節點值沒有都已經被查找過了，即找不到更近的節點了。

5、?通過上述查找操作，x?得到了k?個最接近t?的節點信息。

注意：這里用“最接近”這個說法，是因為ID?值為t?的節點不一定存在網絡中，也就是說t?沒有分配給任何一臺電腦。

查找peers-list的過程則換成find_value動作，但注意前文提到的區別即可以有類似的描述。

上面的四個原始在BT-DHT的實現上則進行了重命名，定義了如下四類信息，它們叫作KRPC（K代表Khashmila/Kademlia），通過udp進行發送，一個請求一個響應或者錯誤。

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

Beconded（以BitSprits為例）:

Ping?Request格式：

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

表示的含義：此操作為ping操作請求，參數為發送者的id是：xxxxxxxxxxxxxxxxxx

Ping?Reponse格式:

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

返回的數據中只包括有一個響應者的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請求，參數為發送者id及目標節點的id

find_node?Reponse格式：

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

表示的含義是：找到了8個最近的節點，nodes208表示8個node信息（ip,port,id）共208Bytes

（3）?get_peers（對應Kademlia中的find_value消息）

Beconded（以BitSprits為例）:

Get_peers請求格式：

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

表示的含義：此操作為get_peers操作請求，參數為：發送者的id和要查詢種子的info-hash。

Get_peers響應格式有兩種，一種是找到了節點含有該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)

另一種是沒有找到列表信息，如下格式：

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

表示的含義為：

沒有找到存有info-hash的節點，但找到了離該info-hash更近的8個節點，nodes208表示8個node信息（ip,port,id）共208bytes

（4）?announce_peer（對應Kademlia中的store消息）

Beconded（以BitSprits為例）:

announce?_peers請求格式：

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

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

Announce_peer?Reponse格式

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

附件為抓取的分別為為一簡單下載過程/一初始初始化路由表的數據包：可以對照進行分析

四、Bttorent?DHT實現幾個重要過程

種子制作：

1）./maketorrent-console參數use_tracker設置為false，則不會產生announce?tracker字段

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

啟動過程：

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

2）?強制刷新“路由表“中的每一個K桶，刷新過程是隨機產生一id進行findNode查找。

刷新路由表的過程：

1）?啟動的時候進行強制刷新

2）?每15分鐘如果K桶中的信息沒有進行更新的話，則進行刷新一次K桶，即refreshTable

3）?每5分鐘進行一次checkpoint操作，以把當前的路由表存放到routing_table文件中

routing_table文件的格式：

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

有些實現是用SQLite數據庫來實現這部分功能的。

每一個“路由表”的K桶都有一個“最近更新時間“屬性，當收到該桶中任何節點的ping響應，或者有任何節點被加入或者被替換，則該屬性都需保持更新，并且重啟一個15分鐘的定時器，如果定時器超時（15分鐘內該K桶節點沒有任何更新操作），則會對該K桶進行一次refresh操作，操作的過程是從該K桶范圍選出一隨機的ID，然后對該ID進行find_node操作?！奥酚杀怼敝械墓濣c需要保持live狀態，即得保證沒有離線，如果向路由表中的一節點發出的連續3次請求都沒有收到響應，則認為該節點失效。

refreshTable（force=1）過程：

（1）?如果force=1，則對當前每個K桶都進行刷新

（2）?如果K桶當前nodes數小于k（8），則也進行刷新

（3）?如果K桶中存在無效的節點，即連續三個消息沒有收到響應的節點

（4）?如果K桶中所有節點沒有交互的時間超過15分鐘，則也進行刷新

當一個節點收到任何一個RPC消息（請求和響應）后（ping/find/getPeers/announce_peer）都會去檢查一下該消息的發送者是否在本地的“路由表“中，如果該發送者已經存在節點的本地“路由表”中，則會把該發送者從其對應的K桶移動到該K桶的末尾。如果該發送者不在節點的“路由表”中則會去嘗試插入到本地”路由表“K桶中，這也是“路由表”的動態建立過程的一種，過程如下：

（0）??找到該發送者的對應的K桶

（1）?如果該節點是響應消息中發現的，則更新該節點lastSeen?=?time()時間

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

（3）?如果該K桶已經滿了，則檢查是否有無效的節點，如果有則把這些無效節點刪除，并把該節點放入K桶末尾。（但后面會對這些早已經存在的節點進行再一次的ping操作，來進一步確定是否無效了，如果收到響應，則把這些節點重新放如K桶）

（4）?如果該K桶已經滿了，并且所有的節點都是有效的，則需要查看自身（本客戶短）是否在該K桶中（即該K桶是否是自己所在的K桶），如果不是則直接丟棄該節點

（5）?如果該K桶不是自身所在的K桶，則需要進行K桶分拆。拆分的方法即是一個變為兩個等長K桶，一個包括自身，一個不包括。

（6）?對該節點添加到分拆后的一個K桶中去。

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

（0）?如果該節點在自己的K桶中，則直接返回，結束該過程

（1）?如果invalid=True，則需要排除當前無效的節點

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

（3）?把左右相鄰的兩個K桶中的節點補充進去，然后把所有這些節點按照離id距離遠近進行排序，選取最近的K(8)個節點

（4）?返回最后得到的最近的K個節點。

findNode(id)的過程是：

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

（2）?從上面k個信息中選取a個（3）個，然后發送findNode消息給這3個節點

（3）?該3個節點查找自己的“路由表“同時返回k個nodes信息

（4）?從上面得到的3*k個節點在重復

Keyexpired過程：

1）?節點存放的（info-hash，peers-list）如果24小時沒有收到原節點的更新則視作無效

2）?當前仍然活動的peer-lists中的節點需要24小時向其close節點進行刷新info-hash，peers-list。

3）當前仍然活動的peer-lists中的節點如果在自己的路由表中發現有離info-hash更近的節點，則會把自（info-hash，peers-list）announce給它們。

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

getPeersAndAnnounce過程：

（0）?該過程包括了getPeers和Announce_peer兩個過程

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

（2）?如果本地沒有info-hash的key,values，則需要進行遠程查找，查找的過程是

（3）?先從info-hash對應的K桶中找k個節點，然后分別向它們發送getpeers原始RPC消息

（4）?分析上面k個節點的響應信息，如果響應信息中存在values字段，則說明命中一個節點，該節點保存有info-hash的peers-list信息，保存起來。如果響應消息中只有nodes字段，則該字段后面跟上的是k（8）個更接近于info-hash的節點，判斷這些節點是否發送過，如果沒有則把這些節點保存起來繼續發送getPeers?RPC消息，直到收到響應消息中帶有values字段，或者響應消息中所有的節點都發送過了（沒有更接近info-hash的節點了）

（5）?當收到節點對get_peers響應包中包括有(info-hash,peers-list)后，則首先向響應者發送announce，然后向自己K桶中離info-hash最近的k個節點發送announce_peer消息

Ping消息的發送過程：

1）?對于DHT種子文件中nodes逐個節點發送ping消息，有響應者則添加到“路由表”中去

2）?當插入新節點到“路由表”中時，如果該“路由表”K桶已滿，則會選擇K桶的頭部節點進行ping操作，如果該頭節點仍然在線，則直接丟棄該節點（這是基于一種越長時間在線則可能以后越長在線的概率統計），否則刪除頭節點，并把新節點插到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代碼

總結

以上是生活随笔為你收集整理的P2P中DHT网络介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。