DHT網絡

@(基礎技術)

現在有一種方法，可以通過磁力鏈接，例如magnet:?xt=urn:btih:0482e0811014fd4cb5d207d08a7be616a4672daa，就可以獲取BT文件。
這個是通過DHT網絡來實現的。
DHT網絡是一個去中心化的，分布式信息存儲系統。
存儲的信息就是bt文件。

一、節點

每一臺電腦，就是一個節點。它既是客戶端，也是服務端。
每個節點都有一個節點ID，IP地址和端口號（節點進程的端口）。
節點ID由160位的二進制字符串組成，也就是長度為32的16進制字符串，跟我們常用的md5一樣。
通過異或算法，可以計算兩個節點ID的距離。例如01和00的異或結果是01，也就是距離是1。

二、路由表

每個節點都會保存一個路由表，保存其他節點的信息，節點信息包括：節點ID，節點的IP地址和端口號。
路由表中，會有多個bucket，例如bucket-1，bucket-2等等。
bucket-i保存的是與自身節點ID距離為[2^i-1,2^i)的節點信息
每個nodeid可以理解為深度是160的二叉樹，二bucket-i就是自身的葉子的第i個父節點的兄弟節點的所有葉子節點（不太嚴謹）
如下圖：
Alt text

所以i最大值是160。

而為什么要這么存了？
這樣存是為了可以快速找到目標節點N2。
例如自身的節點ID是N1，需要尋找N2的IP和端口號。

計算N1和N2的距離D
從bucket-D,找一個節點N3，如果N3=N2，就找到了，否則就向N3發送尋找節點N2的請求
N3接收到請求后，計算N2和N3的距離D1，從N3的路由表里面的bucket-D1，找到一個節點N4，返回N4的信息給N1
N1收到返回后，如果N4=N2，就找到了，否則繼續向N4發送尋找節點N2的請求。一直遞歸。

因為N2和N3會處于同一個bucket，所以他們的距離D1不會超過D/2，所以每一次循環，獲得的節點NN與N2的距離都會比之前的請求縮小1倍。所以時間復雜度是logN。跟二分查找是一樣的。

三、信息發布

當發布者，需要發布信息（例如一個bt文件）到DHT網絡。

發布者會計算信息的md5，M1
通過發布者的路由表，查詢與M1的距離小于等于K的多個節點
向這些節點發送保存信息（Store）的請求，就會把信息存儲在這些節點上

k一般要大于1。不然只會把信息存儲在一個節點上，萬一節點下線，或者退出網絡，就會導致信息不能被找到。

四、數據包

節點與節點之間，通過UDP協議，傳輸數據包來通訊。
DHT網絡的數據包都是json格式。
必須字段：

t:消息的id。因為是UDP傳輸，所以要帶上消息ID，不要就不知道每個包對應是哪個包的回復。
y：數據包的類型，取值可以是：
- q，請求包
- r，回復包
- e，錯誤包，其實也是回復的一種
  
  1. 請求和回復包
  請求包必須字段
q，請求的類型，
- ping 嗅探Node是否可用
- find_node。尋找Node的請求
- get_peers。尋找有資源的Node
- announce_peer ，請求下載資源
a，請求的參數，類型是json里面的字典

回復包必須字段：
*r 回復的內容，字典

1.1ping

請求包
a包含字段

id，請求者的nodeid

包例子

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

回復包
r包含字段

id 回復者的nodeid

包例子

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

1.2find_node

請求包
a包含字段

id，請求者的nodeid
target，需要尋找的Node的nodeid

包例子：

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

回復包
r包含字段

id 回復者的nodeid
nodes 在回復者的路由表中，與請求的target 的nodeid最接近的幾個節點的信息，包含節點的ip，端口，nodeid。

包例子

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

1.3 get_peers

請求包
a包含字段

id，請求者的nodeid
info_hash 尋找的資源的hash
token 密鑰

包例子

{"t":"aa", "y":"q","q":"get_peers", "a":{"id":"abcdefghij0123456789","info_hash":"mnopqrstuvwxyz123456"}}

回復包
如果回復者的路由表中，有存有info_hash資源的節點信息，就返回value，否則返回node，node的值和find_node一樣
r包含字段

id 回復者的nodeid
value，擁有info_hash的節點信息
nodes 和find_node的nodes一樣

包例子

{"t":"aa", "y":"r", "r":{"id":"abcdefghij0123456789", "token":"aoeusnth","values": ["axje.u", "idhtnm"]}}

1.4 announce_peer

請求包
a包含字段

id，請求者的nodeid
info_hash 尋找的資源的hash
token 密鑰
port，下載資源的端口

包例子

{"t":"aa", "y":"q","q":"announce_peer", "a":{"id":"abcdefghij0123456789","info_hash":"mnopqrstuvwxyz123456", "port":6881, "token": "aoeusnth"}}

回復包
r包含字段

id 回復者的nodeid

包例子

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

2. 錯誤包

e 列表類型，第一個元素時錯誤id，第二個是錯誤的說明

{"t":"aa", "y":"e", "e":[201,"A Generic Error Ocurred"]}

錯誤類型有：

201 一般錯誤
202 服務錯誤
203 協議錯誤,比如不規范的包，無效的參數，或者錯誤的token
204 未知方法

五、工作流程

1.初始化

向一個固定的服務器，獲取節點ID，完成冷啟動
不斷向已知的節點發送find_node請求，讓自己的路由表里面的節點更多

2. 根據磁力鏈接，獲取信息（bt文件）

獲取磁力鏈接里面的md5，轉換為二進制M1。
通過路由表，獲取與M1距離最近的節點，然后向它們發送announce_peer 請求。如果節點有我們想要的信息，就會把信息發過來，這樣我們就獲取到了bt文件了。

六、DHT網絡中收集bt文件的原理

向三個固定服務器發送find_node的請求，target是隨機的nodeid或者是自己的nodeid，N1
服務器返回最接近N1的的3個nodeid的信息，這些信息是一個加密了的，固定協議的字符串，里面有node的ip，port和nodeid。自身節點把所有的node存儲到路由表
新開一個線程，對node，再發送find_node請求，這時自己的nodeid是隨機的
這樣，就會導致在很多個DHTNode中，都有我們ip和端口的信息，而且映射到很多不同的nodeid
這樣別人去這些DHTNode中尋找bt資源的時候，這些Node就很可能會返回我們的IP，PORT給別人，那么別人就會向我們發送announce_peer的請求，這樣我們就能拿到bt文件了

初始化，目的是讓自己的nodeid加入到DHT網絡中，并認識盡量多的其他node，放到我們的路由表。
1. 生成自己的nodeid。
2. 向固定的服務器（例如：），發送find_node請求，target是自己的nodeid，這樣，自己的nodeid就會進入到固定服務器的路由表，這樣其他node想固定服務器發送find_node請求的話，固定服務器就會返回我們的nodeid給他們，這樣我們的nodeid就會進入很多其他Node的路由表了。
3. 發送給固定服務器的find_node請求中，會返回我們附近的node的信息，保存到我們自己的路由表
接收其他節點的請求。當我們加入到DHT網絡中，就會有其他節點發送請求給我們。下面的請求處理完后，我們都把請求者加入到我們的路由表中。
1. 當我們收到ping請求，就返回自己的id給它，表示自己在正常運行。
2. 當我們收到find_node請求，就從我們的路由表查找離target最近的N個node的信息，返回給它。
3. 當我們收到get_peers請求，就從我們的路由表中查找擁有該資源的peers信息，返回給它。
4. 當我們收到announce_peer 請求，就從發送info_hash的資源到對應的端口