一、文件共享網絡

第一代

中央服務器。以文件服務器作為中心，典型的提供FTP的服務器。這種方式對服務器帶寬壓力和機器性能壓力巨大。而且，這種單點集權的模式風險非常大，一旦出現故障，整個服務將停止。

第二代

泛洪式查詢。網絡中每一個節點都向他鄰居節點詢問是否擁有資源，如果沒有，鄰居繼續向他的鄰居詢問。這種廣播式的查詢缺點明顯，每次向外傳播都是指數級，很容易就形成蝴蝶效應般的影響，對網絡資源消耗非常大，而且容易形成網絡風暴。以至于要對廣播的廣度和深度進行限制。

典型的例子是Gnutella，2000年的一種文件共享網絡。廣播廣度被限制在5個鄰居，深度不大于7跳。但5^7=78125這個數量也是很驚人。盡管它沒有直接查詢中心節點有效率，但它不再依賴一個中心化的索引節點。

第三代

BTtorrent-tracker。BT的網絡架構中存在一個中心服務器Tracker，用來保存BT網絡巾各節點的IP地址和端口等信息。下載節點剛加入網絡時從Trakcer上獲得其他節點的地址信息，同時在tracker中注冊自己的信息成為一個peer。實現一個節點同時與多個節點交互。

第四代

Bttorrent-DHT。雖然第三代文件共享網絡實現了P2P，但也有個缺點，如果tracker被屏蔽或者被黑，那么新節點無法注冊，也無法獲得peer列表，整個P2P網絡就癱瘓。DHT(分布式哈希表)網絡的出現，作為BT協議強而有力的拓展，解決了以上問題。

DHT全稱?Distributed Hash Table，中文翻譯分布式哈希表。它是一種去中心化的分布式系統，特點主要有自動去中心化，強大的容錯能力，支持擴展。另外它規定了自己的架構，包括keyspace和overlay network(覆蓋網絡)兩部分。但是他沒有規定具體的算法細節，所以出現了很多不同的實現方式，比如Chord，Pastry，Kademlia等。BitTorrent中的DHT是基于Kademlia的一種變形。本文也是根據Kademlia協議描述DHT網絡。

二、相關名詞

peer：一個實現了BT協議并且開啟了tcp監聽端口的bt客戶端或者服務器

node：一個實現了DHT協議并且開啟了udp監聽端口的bt客戶端或者服務器

tracker：最終指引請求者找到目標peer的主機。在DHT網絡中，存儲了peer信息的node充當一個虛擬tracker的角色。

info_hash：一個由40位16進制數字組成的字符串，總共有160bit。由SHA-1計算torrent文件中的info得出的作為資源的唯一標識。

B編碼(Bencode編碼)：一種torrent文件信息存儲格式

哈希表：也稱散列表。根據關鍵碼值(Key value)而直接進行訪問的數據結構。這個映射函數叫哈希函數，存放記錄的數組叫哈希表。

三、Kademlia協議(簡稱 Kad)

1.兩個關鍵的id：

nodeid，節點id。節點包含了網絡ip地址和端口號，由唯一的節點id指向這一個節點。節點id為160位的二進制表示。

key。網絡中的資源名索引和資源名以key-value鍵值對的形式表示，資源名經過哈希函數計算，轉為160位的key。

2.異或距離：

由上述的兩個id，把資源放置在nodeid與key的距離相近的節點上，就能實現資源的定位。也就是我們可以根據key去匹配距離相近的nodeid，然后找到在該節點上與key對應的資源value。

其中的距離指的是異或距離。也就是對兩個id進行異或運算，可以是nodeid與nodeid，定位節點。或者nodeid與key，定位資源。

舉個例子：00110 與 00011 的異或距離為 00101，也就是5。(0⊕0=0，1⊕0=1，1⊕1=0)

3.異或特性:

x ⊕ x = 0，節點與它本身的異或距離為0。

x ⊕ y > 0 , if x != y，不同節點異或距離一定大于0。

x ⊕ y =? y ⊕ x，異或距離是對稱的。

x ⊕ y + y ⊕ z >=? x ⊕ z，類似于三角形不等式，第三邊的距離小于等于另外兩邊的距離之和。

x ⊕ y ⊕ y ⊕ z =? x ⊕ z

x + y >= x ⊕ y

4.路由表，與k-bucket:

由于節點id是一串二進制數，每一位的取值只有0或1，因此我們可以把節點id表示為二叉樹的形式。以100為例，第一位是1，(從上到下)往右子樹，第二位是0，往左子樹，第三位是0，再往左子樹。最終的葉子節點即為100。類似于文件夾的路徑。

k-bucket

k-buckst樹形結構

我們把同一個灰色部分的節點放置在同一個列表，這個列表稱為k-bucket，k桶。k桶中的k指的是每一個列表所能容納的節點的最大個數。

劃分k桶是有規律的。k桶的個數跟節點id的位數有關，假設節點id的位數為n，則最多有n個k桶。第1個k桶中的節點與本地節點前n-1位id是相同，第2個k桶中的節點與本地節點前n-2位id是相同，以此類推，最后第n個k桶中的節點與本地節點第1位id就不一樣了。

所有的k桶合起來也就是一個節點的路由表。

這里以nodeid為110的節點為例，共有3個k桶。第i個k桶中異或距離的范圍為[2^i,2^(i+1))。

可以類比為國家的行政區域劃分來理解。

節點距離

節點id為110的路由表

5.協議消息:

PING — 驗證遠程節點是否在線。

STORE — 在某個節點上存儲 key-value 鍵值對。在節點上存儲資源。

FIND_NODE — 查找節點，給定一個nodeid，被請求的節點返回與nodeid相近的k個節點。

FIND_VALUE — 查找資源，給定一個key，被請求的節點的nodeid與key相近，并且具有該key，返回與key對應的value。

四、BitTorrent基于Kad協議的實現

KRPC協議

KRPC是BitTorrent在Kademlia理論基礎之上定義的一個通信消息格式協議,是由B編碼組成的一個簡單的RPC結構，有4種請求：ping、find_node、get_peers 和 announce_peer。一條 KRPC 消息即可能是request，也可能是response

KRPC字典基本組成元素

1. t關鍵字: 每條消息都包含 t 關鍵字，它是一個代表了 transaction ID 的字符串。transaction ID 由請求節點產生，并且回復中要包含回顯該字段(挑戰-響應模型)，所以回復可能對應一個節點的多個請求。transaction ID 應當被編碼為一個短的二進制字符串，比如 2 個字節，這樣就可以對應 2^16 個請求

2. y關鍵字: 它由一個字節組成，表明這個消息的類型。y 對應的值有三種情況

1) q 表示請求(請求Queries): q類型的消息它包含 2 個附加的關鍵字 q 和 a

1.1) 關鍵字 q: 是字符串類型，包含了請求的方法名字(get_peers/announce_peer/ping/find_node)

1.2) 關鍵字 a: 一個字典類型包含了請求所附加的參數(info_hash/id..)

2) r 表示回復(回復 Responses): 包含了返回的值。發送回復消息是在正確解析了請求消息的基礎上完成的，包含了一個附加的關鍵字 r。關鍵字 r 是字典類型

2.1) id: 當前節點id，peer節點id號或者下一跳DHT節點

2.2) nodes: ""

2.3) token: token

3) e 表示錯誤(錯誤 Errors): 包含一個附加的關鍵字 e，關鍵字 e 是列表類型

3.1) 第一個元素是數字類型，表明了錯誤碼，當一個請求不能解析或出錯時，錯誤包將被發送。下表描述了可能出現的錯誤碼

201: 一般錯誤

202: 服務錯誤

203: 協議錯誤，比如不規范的包，無效的參數，或者錯誤的 toke

204: 未知方法

3.2) 第二個元素是字符串類型，表明了錯誤信息

ping報文

檢測節點是否可達，請求包含一個參數id，代表該節點的nodeID。對應的回復也應該包含回復者的nodeID

ping Query = {"t":"aa","y":"q","q":"ping","a":{"id":"abcdefghij0123456789"}}

bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe

Response = {"t":"aa","y":"r","r": {"id":"mnopqrstuvwxyz123456"}}

bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

find_node報文

find_node 被用來查找給定 ID 的DHT節點的聯系信息，該請求包含兩個參數id(代表該節點的nodeID)和target。回復中應該包含被請求節點的路由表中距離target最接近的K個nodeID以及對應的nodeINFO。應用在定位node的位置，初始化或更新自己的K桶列表。

find_node 請求包含 2 個參數，第一個參數是 id，包含了請求節點的ID。第二個參數是 target，包含了請求者正在查找的節點的 ID

當一個節點接收到了 find_node 的請求，他應該給出對應的回復，回復中包含 2 個關鍵字 id(被請求節點的id) 和 nodes，nodes 是字符串類型，包含了被請求節點的路由表中最接近目標節點的 K(8) 個最接近的節點的聯系信息(被請求方每次都統一返回最靠近目標節點的節點列表K捅)

find_node Query = {"t":"aa","y":"q","q":"find_node","a": {"id":"abcdefghij0123456789","target":"mnopqrstuvwxyz123456"}}

# "id"containing the node ID of the querying node, and"target" containing the ID of the node sought by the queryer.

bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe

Response = {"t":"aa","y":"r","r": {"id":"0123456789abcdefghij","nodes":"def456..."}}

bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re

get_peers報文(相當于find_value)

1.get_peers 請求包含2 個參數(id請求節點ID，info_hash代表torrent文件的infohash，infohash為種子文件的SHA1哈希值，也就是磁力鏈接的btih值)

2. response get_peer:

1) 如果被請求的節點有對應 info_hash 的 peers，他將返回一個關鍵字 values，這是一個列表類型的字符串。每一個字符串包含了"nodeid-ip-port"格式的 peers 信息。關鍵字 token 都將被返回。token 關鍵字在今后的 annouce_peer 請求中必須要攜帶。

2) 如果被請求的節點沒有這個 info_hash 的 peers，那么他將返回關鍵字 nodes，這個關鍵字包含了被請求節點的路由表中離 info_hash 最近的 K 個節點(我這里沒有該節點，去別的節點試試運氣)。

announce_peer 報文(相當于store)

announce_peer: 這個請求用來表明發出 announce_peer 請求的節點，正在某個端口下載 torrent 文件

announce_peer 包含 4 個參數

1. 第一個參數是 id: 包含了請求節點的 ID

2. 第二個參數是 info_hash: 包含了 torrent 文件的 infohash

3. 第三個參數是 port: 包含了整型的端口號，表明 peer 在哪個端口下載

4. 第四個參數數是 token: 這是在之前的 get_peers 請求中收到的回復中包含的。收到 announce_peer 請求的節點必須檢查這個 token 與之前我們回復給這個節點 get_peers 的 token 是否相同(也就說，所有下載者/發布者都要參與檢測新加入的發布者是否偽造了該資源)

如果相同，那么被請求的節點將記錄發送 announce_peer 節點的 IP 和請求中包含的 port 端口號在 peer 聯系信息中對應的 infohash 下，這意味著一個一個事實: 當前這個資源有一個新的peer提供者了，下一次有其他節點希望或者這個資源的時候，會把這個新的(前一次請求下載資源的節點)也當作一個peer返回給請求者，這樣，資源的提供者就越來越多，資源共享速度就越來越快。

一個peer正在下載某個資源，意味著該peer有能夠訪問到該資源的渠道，且該peer本地是有這份資源的全部或部分拷貝的，它需要向DHT網絡廣播announce消息，告訴其他節點這個資源的下載地址

五、DHT網絡的其他應用

1、以太坊

2、洋蔥網絡

六、一些數字比較

為了讓大家能更直觀的了解DHT網絡的節點空間容量，我翻了一些數據作為比較。

1、DHT網絡有160bit，可以容納2^160個節點，也就約等于 10^48個節點。

2、地球的總人數70億，四舍五入100億(10^10)

3、原子核直徑10^-14米。

4、銀河系最長直徑1.7029e+21米。本星系群9.4607e+22米 。室女座超星系團 9.4607e+23(約10^24)米。

那么假如每個人都成為DHT網絡中的節點，就只占據整個網絡的 10^38分之一；這個尺度就相當于一顆原子核相對于室女座超星系團那么大。哈希碰撞基本不用考慮。

但神奇的是，在那么大的網絡中，尋找其中任意一點，最多只需要160次find_node就可以完成。這與六度人脈理論異曲同工。

七、留下思考問題

為什么BT協議實現DHT網絡要用二叉樹呢？如果用16叉樹會怎樣？

參考資料

總結

以上是生活随笔為你收集整理的dht网络协议 服务器,概述DHT网络的全部內容，希望文章能夠幫你解決所遇到的問題。

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