IMFile

DHT（Distributed Hash Table）分布式哈希表 是分布式計算系統中的一個類別，是一種分布式系統，提供類似於哈希表的查找服務。鍵值對存儲在 DHT 分布式哈希表 中，任何參與的節點都可以有效地檢索與給定關聯的鍵值。在 BitTorrent 與 Magnet 的原理與對比 一文中，我們已經介紹了他們的聯繫和區別，現在我們將單獨詳細的說明一下，DHT 協議具體是什麼。

DHT 的主要優點是可以添加或刪除節點，只需最少量的重新分發密鑰工作。鍵值是映射到特定值的唯一標識符，而特定值又可以是從地址到文檔到任意數據的任何內容。 维护从键值到数值的映射的责任分布在节点之间，对所涉及的参与者的任何更改对系统或过程的整体功能产生影响降低到最小程度。这允许 DHT 扩展到非常大量的节点，并处理持续的节点到达、离开和故障。

BitTorrent 使用 “分布式松散哈希表”（DHT）來存儲基於 Trackerless 協議的種子節點聯繫信息。實際上，每個節點都變成了一個 Tracker 。該協議基於 Kademila，並通過 UDP 實現。

請注意本文檔中使用的術語，以避免混淆。 Peer 節點是在實現 BitTorrent 協議的 TCP 端口上偵聽的客戶端 / 伺服器。 Node 節點是偵聽實現分布式哈希表協議的 UDP 端口的 Tracker 客戶端 / 伺服器。 DHT 由 Node 節點和存儲 Peer 的位置節點組成。 BitTorrent 客戶端包括一個 DHT 節點，該節點用於聯繫 DHT 中的其他 Node 節點，以獲取使用 BitTorrent 協議下載的 Peer 節點的位置。

Peer 通常是指參與文件共享的用戶端，也就是下載或上傳特定文件的客戶端程序，它們通常都是位於同一層級的。每個 peer 都可以下載和上傳文件，這使得整個網絡更加去中心化，因為沒有任何一個節點掌握了所有的數據。 Node 則通常指的是 Tracker 伺服器，也就是通過 Tracker 協議來管理和協調各個 Peer 之間的連接和數據傳輸。 Tracker 伺服器會維護一份記錄活躍 Peer 的列表，並將其發送給其他 Peer，以幫助它們建立連接並找到其他可以共享文件的 Peer 。因此，在 BitTorrent 中，Peer 是指下載和上傳文件的客戶端程序，而 Node 則指的是 Tracker 伺服器，用於協調 Peer 之間的連接和文件共享。

每個 Node 節點都有一個全局唯一標識符，稱為 Node ID 。 Node ID 是從與 BitTorrent 信息哈希相同的 160 Bit 空間中隨機選擇的。距離指標用於比較兩個 Node ID ，或 Node ID 和接近度比較的信息哈希。 Node 節點必須維護一個路由表，其中包含少量其他節點的聯繫信息。隨著 ID 越來越接近節點自己的 ID，路由表變得更加詳細。節點知道 DHT 中的許多其他節點，這些節點的 ID 與自己的 ID 接近，但只有少數下載方的 ID 離自己的 ID 很遠。

在 Kademlia 中，距離度量是 XOR，結果被解釋為無符號整數。 distance (A,B) = |A xor B| 值越小越近。

當 Node 節點想要查找種子的 Peer 節點時，它會使用距離指標將種子的信息哈希與其自己的路由表中節點的 ID 進行比較。然後，它使用最接近信息哈希的 ID 聯繫它所知道的節點，並要求他們提供當前下載種子的 Peer 節點的下載信息。如果聯繫的節點知道種子的對等節點，則對等節點聯繫信息將隨響應一起返回。否則，聯繫的節點必須使用其路由表中最接近種子信息哈希的節點的聯繫信息進行響應。原始節點迭代查詢更接近目標信息哈希的節點，直到找不到任何更近的節點。搜索完畢後，客戶端將自身的對等下載方信息插入到具有最接近種子信息哈希的 ID 的響應節點上。

infohash 是一個由 40 個十六進制字符表示的唯一標識符，用於標識一個 torrent 文件。這個標識符是通過將 torrent 文件的元數據哈希生成的，它包括了文件名、文件大小、文件數量等信息。當一個客戶端想要下載一個 torrent 文件時，它會向 tracker 發送包含該文件 infohash 的請求。 Tracker 將回覆一個包含可用種子和對等方的列表，該列表可以幫助客戶端連接到其他客戶端並開始下載文件。因為 infohash 是根據文件的內容生成的，所以即使兩個 torrent 文件的名稱不同，只要它們包含相同的數據，那麼它們的 infohash 就會相同。

Peer 節點查詢的返回值包括一個稱為 token 的不透明值。要使 Node 節點宣布其控制 Peer 節點正在下載種子，它必須在最近的 Peer 節點查詢中提供從同一查詢節點收到的 Token 。當節點嘗試發行種子時，被查詢的節點會根據查詢節點的 IP 地址檢查 Token 。由於 Token 僅由查詢節點返回到它從中接收 Token 的同一節點，Token 必須在分發後的合理時間內被接受。 BitTorrent 實現使用 IP 地址的 SHA1 哈希連接到一個 Token 上，該 Token 每五分鐘更改一次，並接受長達 10 分鐘的 Token 。

在 BitTorrent 中，”Token” 通常指的是一種通過 Tracker 伺服器授權的方式，用於幫助客戶端獲取其他對等方（Peers）和下載所需文件塊的一次性密鑰或令牌。當一個 BitTorrent 客戶端想要加入一個特定的 Torrent 下載時，它首先會向 Tracker 發送請求，以獲取可用的對等方列表。如果 Tracker 需要進行身份驗證，它可能會返回一個 “Token” 給客戶端，作為一次性令牌，該令牌只能用於這個特定的 Torrent 下載。客戶端可以使用這個 Token 向 Tracker 發送更多的請求，包括更新對等方列表和下載文件塊的請求。這個 Token 可以防止未經許可的客戶端或對等方試圖加入下載，並且增強了整個 BitTorrent 網絡的安全性。

路由表 每個節點都維護一個已知良好節點的路由表。路由表中的節點用作 DHT 中查詢的起點。返回路由表中的節點以響應來自其他節點的查詢。

並非我們了解的所有節點都是平等的。有些是好的，有些則不是。許多使用 DHT 的節點能夠發送查詢和接收響應，但無法響應來自其他節點的查詢。重要的是，每個節點的路由表必須僅包含已知良好的節點。一個好的節點是在過去 15 分鐘內響應了我們的一個查詢的節點。如果一個節點曾經響應過我們的一個查詢，並且在過去 15 分鐘內向我們發送了一個查詢，那麼它也很好。處於非活動狀態 15 分鐘後，節點變得有問題。當節點無法連續響應多個查詢時，它們會變得糟糕。我們知道良好的節點優先於狀態未知的節點。

路由表覆蓋從 0 到 2160 的整個節點 ID 空間。路由表細分為 buckets，每個 buckets 覆蓋一部分空間。空表有一個 bucket，其 ID 空間範圍為 min=0, max=2160 。當 ID 為 “N” 的節點插入表中時，該節點將放置在最小值為 <= N < 最大值的存儲桶中。空表只有一個 bucket，因此任何節點都必須適合其中。每個 bucket 只能容納 K 個節點，目前是 8 個節點，然後才能算 “裝滿” 。當 bucket 充滿已知良好的節點時，除非我們自己的節點 ID 在存儲桶的範圍內，否則不能再添加節點。在這種情況下，bucket 將替換為兩個新 buckets，每個 bucket 的範圍是舊 bucket 的一半，並且舊 bucket 中的節點分佈在兩個新 bucket 之間。對於只有一個 bucket 的新表，整個 bucket 始終拆分為兩個新 buckets，範圍為 0..2159 和 2159..2160 。

在 BitTorrent 協議中，Bucket 是指下載器在下載文件時，將下載任務分成多個子任務，並將每個子任務分配給不同的遠程上傳者（peers）來下載的數據塊。這些數據塊被組織成 Bucket，可以看作是一組數據塊的集合。通常情況下，一個 Bucket 包含數百個數據塊，每個數據塊的大小為 16KB 到 64KB 左右。下載器會嘗試從多個上傳者處獲取不同的 Bucket，以便加速下載。這種方式也被稱為多點下載（multi-source downloading），因為下載者從多個源同時下載數據。

當 bucket 中裝滿了良好節點時，新節點將被簡單地丟棄。如果已知 bucket 中的任何節點已損壞，則一個節點將替換為新節點。如果 bucket 中有任何可疑節點在過去 15 分鐘內未被查詢到，則會對最近最少查詢的節點執行 ping 操作。如果 ping 的節點響應，則對下個最近最少查詢的可疑節點進行 ping 操作，直到一個節點無法響應或 bucket 中的所有節點都已知良好。如果 bucket 中的節點無法響應 ping，建議在丟棄該節點並將其替換為新的良好節點之前再試一次。這樣，表中就會填充穩定的長時間運行的節點。

每個 bucket 都應維護一個 “上次更改” 屬性，以指示內容的 “新鮮” 程度。當 bucket 中的節點被 ping 並響應時，或者將節點添加到 bucket ，或者 bucket 中的節點替換為另一個節點時，應更新 bucket 的上次更改屬性。 15 分鐘內未更改的 bucket 應 “刷新” 。這是通過在 bucket 範圍內選擇一個隨機 ID 並對其執行 find_nodes 搜索來完成的。能夠接收來自其他節點的查詢的節點通常不需要經常刷新 bucket 。無法從其他節點接收查詢的節點通常需要定期刷新所有 bucket ，以確保在需要 DHT 時其表中有良好的節點。

將第一個節點插入其路由表後以及此後啟動時，節點應嘗試在 DHT 中查找與自身最近的節點。它通過向越來越近的節點發出 find_node 消息來實現這一點，直到它找不到更近的節點。路由表應在客戶端軟件的調用之間保存。

BitTorrent 協議擴展#

BitTorrent 協議已擴展到在 Tracker 引入的 Peer 節點之間交換節點 UDP 端口號。通過這種方式，客戶端可以通過下載常規種子來自動做種他們的路由表。在第一次嘗試下載 trackerless 種子的新安裝客戶端的路由表中將沒有任何節點，種子文件中也需要節點信息。

支持 DHT 的 Peer 節點設置在 BitTorrent 協議握手中交換的 8 字節保留標誌的最後一位。 Peer 節點收到指示遠程 Peer 節點支持 DHT 的握手時，應發送 PORT 消息。它以字節 0x09 開頭，並具有兩個字節的有效負載，其中包含按網絡字節順序排列的 DHT 節點的 UDP 端口。收到此消息的 Peer 節點應嘗試在遠程 Peer 節點的接收端口和 IP 地址上 ping 節點。如果收到對 ping 的響應，節點應嘗試根據常規規則將新的聯繫信息插入其路由表中。

Torrent 文件擴展名#

一個 Trackerless 種子詞典沒有 “發行” 鍵值。相反，Trackerless 的種子有一個 “節點” 鍵值。此鍵值應設置為種子生成客戶端路由表中的 K 個最近的節點。或者，可以將密鑰設置為已知良好的節點，例如由生成種子的人操作的節點。請不要自動添加 “Router.Bittorrent.Com” 到種子文件或自動將此節點添加到客戶端路由表中。

nodes = [["<host>", <port>], ["<host>", <port>], ...]
nodes = [["127.0.0.1", 6881], ["your.router.node", 4804], ["2001:db8:100:0:d5c8:db3f:995e:c0f7", 1941]]

KRPC 協議#

KRPC 協議是一個簡單的 RPC 機制，由通過 UDP 發送的編碼字典組成。發送單個查詢數據包，並發送單個數據包作為響應，沒有重試。有三種消息類型：查詢、響應和錯誤。對於 DHT 協議，有四個查詢：ping 、 find_node 、 get_peers 和 announce_peer 。

每個 KRPC 消息是單個哈希表，每個消息具有三個通用鍵，並根據消息類型提供其他鍵值。每條消息都有一個鍵 “t”，其字符串值表示事務 ID 。此事務 ID 由查詢節點生成，並在響應中回顧，因此響應可能與對同一節點的多個查詢相關聯。事務 ID 應編碼為一小串二進制數字，通常 2 個字符就足夠了，因為它們涵蓋 2^16 個未完成的查詢。每條消息還有一個鍵 “y”，其中包含描述消息類型的單個字符值。 “y” 鍵的值是 “q” 表示查詢，“r” 表示響應，“e” 表示錯誤。在具有客戶端版本字符串的每條消息中都應包含一個鍵 “v” 。並非所有實現都包含 “v” 鍵，因此客戶端不應假定它的存在。

Contact Encoding 聯繫人編碼#

一種緊湊型表示 Peer 節點聯繫信息的編碼方式，也被稱為 “壓縮 IP 地址 / 端口信息” 。在這種編碼方式下，一個 Peer 節點的聯繫信息被表示成 6 個字節的字符串。其中前 4 個字節表示該 Peer 節點的 IP 地址，並且採用網絡字節序（即大端序）進行編碼；後兩個字節則表示該 Peer 節點的端口號，同樣採用網絡字節序進行編碼。具體地，這 6 個字節的排列順序是先表示 IP 地址，再表示端口號，因此拼接成的字符串就是 IP 地址 + 端口號 的形式。

例如，如果一個 Peer 的 IP 地址是 192.168.1.100，端口號是 6881，那麼它的聯繫信息就可以被表示成一個 6 個字節的字符串：
c0 a8 01 64 1a e1
其中，前 4 個字節 c0 a8 01 64 表示了 IP 地址 192.168.1.100，後 2 個字節 1a e1 則表示了端口號 6881，兩部分按照 IP 地址在前、端口號在後的順序拼接起來，就得到了這個 6 個字節的字符串。

節點信息採用的是不同的編碼方式。聯繫節點的信息被編碼為一個 26 字節的字符串，其中包含了 20 字節的節點 ID 和 6 字節的 IP 地址和端口號信息。這種編碼方式也被稱為” 緊湊型節點信息” 。節點可以使用這些信息來連接其他對等方並進行文件共享。

Queries 查詢#

當發送一個請求時，消息字典的”y” 鍵設置為”q”，表示這是一個查詢請求。此外，消息字典還需要包含”q” 和”a” 兩個鍵。其中”q” 鍵指定具體的查詢類型，”a” 鍵則包含了查詢所需的參數。

Responses 反應#

根據 KRPC 協議規定，消息字典中包含一個”y” 鍵，表示消息類型，如果其值為”r”，則表示這是一個響應消息。在這種情況下，消息字典還必須包含一個額外的”r” 鍵，其值為一個字典，其中包含了命名的返回值。

當節點收到請求消息並成功處理後，它將發送一個響應消息來回覆請求方。這個響應消息採用相同的格式，但”y” 鍵的值為”r”，同時包含一個額外的”r” 鍵，其值為一個字典，包含了響應的返回值。通過這種方式，節點之間可以進行查詢和回覆，實現基本的通信和交互。

Errors 錯誤#

在 KRPC 協議中，當消息字典中的”y” 鍵值為”e” 時，表示這是一個錯誤消息。這種情況下，消息字典會包含一個額外的”e” 鍵，其值為一個列表。該列表的第一個元素是一個整數，表示錯誤代碼，第二個元素是一個字符串，包含了錯誤信息。這種情況通常會出現在節點收到請求消息但無法處理時，或者由於某些原因導致請求無法完成。通過發送錯誤消息，請求方可以了解到錯誤的具體原因，從而採取相應的措施。

下表描述了可能的錯誤代碼：

錯誤數據包示例：

generic error = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]}
bencoded = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee

DHT 查詢#

所有的查詢和響應消息都包含一個”ID” 鍵，並且該鍵的值包含了發出查詢或響應的節點的 ID 。對於查詢消息，請求方會將自己的節點 ID 作為 “ID” 鍵的值附加到消息字典中。當接收方節點收到查詢消息後，它會將自己的節點 ID 作為 “ID” 鍵的值附加到響應消息中，以便請求方在接收到響應後可以確定響應來自哪個節點。

通過使用 “ID” 鍵，節點之間可以建立起基本的通信和交互，使得每個節點都可以識別和跟蹤來自其他節點的查詢和響應消息。

Ping#

最基本的查詢是 ping。 “q” = “ping” 一個 ping 查詢具有單個參數，“id” 該值是一個 20 字節的字符串，包含按網絡字節順序排列的發送方節點 ID 。對 ping 的相應響應具有包含響應節點的節點 ID 的單個鍵 “id” 。

在 KRPC 協議中，“ping” 是最基本的查詢類型之一，用於檢測目標節點是否在線和響應正常。 “ping” 查詢包含一個參數 “ID”，其值為 20 字節的字符串，在網絡字節順序下表示發送方節點的 ID 。當接收到 “ping” 查詢消息後，節點會簡單地回覆一個帶有節點 ID 的響應消息作為確認。該響應消息僅包含一個鍵 “ID”，其值為響應方節點的 ID 。

通過發送”ping” 查詢消息和接收響應消息，節點可以確定目標節點是否處於在線狀態，並且與之建立連接的準備情況。這是建立 P2P 網絡中最基本的通信方式之一。

arguments:  {"id" : "<querying nodes id>"}

response: {"id" : "<queried nodes id>"}

示例數據包

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#

在 KRPC 協議中，“find_node” 用於查找給定節點 ID 的聯繫信息。 “find_node” 查詢包含兩個參數：“ID” 代表請求方節點的 ID，“target” 代表查詢目標節點的 ID 。

當一個節點接收到 “find_node” 查詢消息後，它會根據自己的路由表和查詢目標節點的 ID 來確定響應內容。如果該節點具有查詢目標節點的聯繫信息，則會將其作為字符串格式的緊湊節點信息附加到響應消息的 “nodes” 鍵值中返回。如果該節點沒有查詢目標節點的聯繫信息，則會返回其自身路由表中與查詢目標節點 ID 距離最近的 K（通常為 8）個節點的緊湊節點信息。

通過使用 “find_node” 查詢消息和接收響應，節點可以了解到其他節點的聯繫信息，並且進行網絡拓撲結構的構建和維護。

arguments:  {"id" : "<querying nodes id>", "target" : "<id of target node>"}

response: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}

示例數據包

find_node Query = {"t":"aa", "y":"q", "q":"find_node", "a": {"id":"abcdefghij0123456789", "target":"mnopqrstuvwxyz123456"}}
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#

在 KRPC 協議中，“get_peers” 用於獲取與特定 Torrent 的 infohash 相關聯的節點列表。 “get_peers” 查詢包含兩個參數：“ID” 代表請求方節點的 ID，“info_hash” 代表要查詢的 Torrent 文件的 infohash 。

當一個節點接收到 “get_peers” 查詢消息後，它會根據自己存儲的信息確定響應內容。如果該節點本身有與所查詢 Torrent 的 infohash 相關聯的 peer，則它會將這些 peer 的緊湊格式信息作為字符串附加到響應消息的 “values” 鍵中返回。每個字符串表示一個 peer 的緊湊格式信息。

如果該節點沒有與所查詢 Torrent 的 infohash 相關聯的 peer，則它將返回其自身路由表中與 infohash 距離最近的 K（通常為 8）個節點的緊湊節點信息，其作為字符串格式的聯繫信息附加到響應消息的 “nodes” 鍵值中返回。無論是哪種情況，響應消息都包含了一个 “token” 鍵，其值是一個短的二進制字符串。這個 TOKEN 鍵可以用作未來 “announce_peer” 查詢的必需參數。

通過使用”get_peers” 查詢消息和接收響應，節點可以了解到與特定 Torrent 的 infohash 相關聯的節點列表，並進行相應的連接和交互。

arguments:  {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>"}

response: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "values" : ["<peer 1 info string>", "<peer 2 info string>"]}

or: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "nodes" : "<compact node info>"}

示例數據包：

get_peers Query = {"t":"aa", "y":"q", "q":"get_peers", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe

Response with peers = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "values": ["axje.u", "idhtnm"]}}
bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re

Response with closest nodes = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "nodes": "def456..."}}
bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:t2:aa1:y1:re

Announce_peer#

宣布控制查詢節點的對等方正在端口上下載種子。 announce_peer 有四個參數：“id” 包含查詢節點的節點 ID，“info_hash” 包含種子的信息哈希，“port” 包含端口作為整數，以及響應上個 get_peers 查詢而收到的 “token” 。

一個節點可以向其他節點查詢特定種子文件的 peer 列表，並通過 announce_peer 請求告知其他節點它正在下載該特定種子文件，並提供其端口號和之前收到的 token 以驗證其身份。被查詢的節點需要驗證令牌是否來自相同的 IP 地址，並將查詢節點的 IP 地址和端口號存儲在其 peer 聯繫信息的相應 infohash 下。這樣其他節點就可以向該節點連接來下載該特定種子文件。

一個可選參數 implied_port，其取值為 0 或 1 。若該參數存在且非零，則應忽略 port 參數，並使用 UDP 數據包的源端口作為對等方的端口。這對於位於 NAT 後面的對等方很有用，因為他們可能不知道自己的外部端口，同時支持 uTP 協議，它們在與 DHT 端口相同的端口上接受傳入連接。

arguments:  {"id" : "<querying nodes id>",
  "implied_port": <0 or 1>,
  "info_hash" : "<20-byte infohash of target torrent>",
  "port" : <port number>,
  "token" : "<opaque token>"}

response: {"id" : "<queried nodes id>"}

示例數據包：

announce_peers Query = {"t":"aa", "y":"q", "q":"announce_peer", "a": {"id":"abcdefghij0123456789", "implied_port": 1, "info_hash":"mnopqrstuvwxyz123456", "port": 6881, "token": "aoeusnth"}}
bencoded = d1:ad2:id20:abcdefghij012345678912:implied_porti1e9:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe

Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

參考鏈接#

http://bittorrent.org/beps/bep_0005.html
https://hazelcast.com/glossary/distributed-hash-table/
https://en.wikipedia.org/wiki/Distributed_hash_table