前言
做了一個磁力鏈接和BT種子的搜索引擎 {Magnet & Torrent}像吻，因此把 DHT 協(xié)議重新看了一遍。
原文：DHT Protocol
譯文：BitTorrent DHT 協(xié)議中文翻譯
BitTorrent 使用"分布式哈希表"(DHT)來為無 tracker 的種子(torrents)存儲 peer 之間的聯(lián)系信息勺爱。這樣每個 peer 都成了 tracker晃琳。這個協(xié)議基于 Kademila[1] 網(wǎng)絡并且在 UDP 上實現(xiàn)。
請注意本文檔中使用的術語邻寿，以免混亂蝎土。
"peer" 是在一個 TCP 端口上監(jiān)聽的客戶端/服務器，它實現(xiàn)了 BitTorrent 協(xié)議绣否。
"節(jié)點" 是在一個 UDP 端口上監(jiān)聽的客戶端/服務器誊涯，它實現(xiàn)了 DHT(分布式哈希表) 協(xié)議。
DHT 由節(jié)點組成蒜撮，它存儲了 peer 的位置暴构。BitTorrent 客戶端包含一個 DHT 節(jié)點，這個節(jié)點用來聯(lián)系 DHT 中其他節(jié)點段磨，從而得到 peer 的位置取逾，進而通過 BitTorrent 協(xié)議下載。
概述 Overview
每個節(jié)點有一個全局唯一的標識符苹支，作為 "node ID"砾隅。節(jié)點 ID 是一個隨機選擇的 160bit 空間，BitTorrent infohash[2] 也使用這樣的 160bit 空間债蜜。
"距離"用來比較兩個節(jié)點 ID 之間或者節(jié)點 ID 和 infohash 之間的"遠近"晴埂。節(jié)點必須維護一個路由表究反，路由表中含有一部分其它節(jié)點的聯(lián)系信息。其它節(jié)點距離自己越近時儒洛，路由表信息越詳細精耐。因此每個節(jié)點都知道 DHT 中離自己很"近"的節(jié)點的聯(lián)系信息，而離自己非常遠的 ID 的聯(lián)系信息卻知道的很少琅锻。
在 Kademlia 網(wǎng)絡中卦停，距離是通過異或(XOR)計算的，結果為無符號整數(shù)恼蓬。distance(A, B) = |A xor B|惊完，值越小表示越近。
當節(jié)點要為 torrent 尋找 peer 時滚秩，它將自己路由表中的節(jié)點 ID 和 torrent 的 infohash 進行"距離對比"专执。然后向路由表中離 infohash 最近的節(jié)點發(fā)送請求，問它們正在下載這個 torrent 的 peer 的聯(lián)系信息郁油。如果一個被聯(lián)系的節(jié)點知道下載這個 torrent 的 peer 信息本股，那個 peer 的聯(lián)系信息將被回復給當前節(jié)點。否則桐腌，那個被聯(lián)系的節(jié)點則必須回復在它的路由表中離該 torrent 的 infohash 最近的節(jié)點的聯(lián)系信息拄显。最初的節(jié)點重復地請求比目標 infohash 更近的節(jié)點，直到不能再找到更近的節(jié)點為止案站。查詢完了之后躬审，客戶端把自己作為一個 peer 插入到所有回復節(jié)點中離種子最近的那個節(jié)點中。
請求 peer 的返回值包含一個不透明的值蟆盐，稱之為"令牌(token)"承边。如果一個節(jié)點宣布它所控制的 peer 正在下載一個種子，它必須在回復請求節(jié)點的同時石挂，附加上對方向我們發(fā)送的最近的"令牌(token)"博助。這樣當一個節(jié)點試圖"宣布"正在下載一個種子時，被請求的節(jié)點核對令牌和發(fā)出請求的節(jié)點的 IP 地址痹愚。這是為了防止惡意的主機登記其它主機的種子富岳。由于令牌僅僅由請求節(jié)點返回給收到令牌的同一個節(jié)點，所以沒有規(guī)定他的具體實現(xiàn)拯腮。但是令牌必須在一個規(guī)定的時間內(nèi)被接受窖式，超時后令牌則失效。在 BitTorrent 的實現(xiàn)中动壤，token 是在 IP 地址后面連接一個 secret(可以視為一個隨機數(shù))萝喘，這個 secret 每五分鐘改變一次，其中 token 在十分鐘以內(nèi)是可接受的。
路由表 Routing Table
每一個節(jié)點維護一個路由表保存已知的好節(jié)點蜒灰。路由表中的節(jié)點是用來作為在 DHT 中請求的起始點弦蹂。路由表中的節(jié)點是在不斷的向其他節(jié)點請求過程中，對方節(jié)點回復的强窖。
并不是我們在請求過程中收到得節(jié)點都是平等的，有的節(jié)點是好的削祈，而另一些則不是翅溺。許多使用 DHT 協(xié)議的節(jié)點都可以發(fā)送請求并接收回復，但是不能主動回復其他節(jié)點的請求髓抑。節(jié)點的路由表只包含已知的好節(jié)點咙崎，這很重要。好節(jié)點是指在過去的 15 分鐘以內(nèi)吨拍，曾經(jīng)對我們的某一個請求給出過回復的節(jié)點褪猛，或者曾經(jīng)對我們的請求給出過一個回復(不用在15分鐘以內(nèi))，并且在過去的 15 分鐘給我們發(fā)送過請求羹饰。上述兩種情況都可將節(jié)點視為好節(jié)點伊滋。在 15 分鐘之后，對方?jīng)]有上述 2 種情況發(fā)生队秩，這個節(jié)點將變?yōu)榭梢傻男ν．敼?jié)點不能給我們的一系列請求給出回復時，這個節(jié)點將變?yōu)閴牡拟勺省Ｏ啾饶切┪粗獱顟B(tài)的節(jié)點筒主，已知的好節(jié)點會被給于更高的優(yōu)先級。
路由表覆蓋從 0 到 2^160 全部的節(jié)點 ID 空間鸟蟹。路由表又被劃分為桶(桶s)乌妙，每個桶包含一部分的 ID 空間〗ㄔ浚空的路由表只有一個桶藤韵，它的 ID 范圍從 min=0 到 max=2^160。當 ID 為 N 的節(jié)點插入到表中時锦针，它將被放到 ID 范圍在 min <= N < max 的 桶 中荠察。空的路由表只有一個桶所以所有的節(jié)點都將被放到這個桶中奈搜。每一個桶最多只能保存 K 個節(jié)點悉盆，當前 K=8。當一個桶放滿了好節(jié)點之后馋吗，將不再允許新的節(jié)點加入焕盟，除非我們自身的節(jié)點ID在這個桶的范圍內(nèi)。在這樣的情況下，這個桶將被分裂為 2 個新的桶脚翘，每一個新桶的范圍都是原來舊桶的一半灼卢。原來舊桶中的節(jié)點將被重新分配到這兩個新的桶中。如果一個新表只有一個桶来农，這個包含整個范圍的桶將總被分裂為 2 個新的桶鞋真，第一個的覆蓋范圍從 0..2^159 和 2159..2160。
當桶裝滿了好節(jié)點沃于，新的節(jié)點會被丟棄涩咖。一旦桶中的某一個節(jié)點變?yōu)榱藟牡墓?jié)點，那么我們就用新的節(jié)點來替換這個壞的節(jié)點繁莹。如果桶中有在 15 分鐘內(nèi)都沒有活躍過的節(jié)點檩互，我們將這樣的節(jié)點視為可疑的節(jié)點，這時我們向最久沒有聯(lián)系的節(jié)點發(fā)送 ping咨演。如果被 ping 的節(jié)點給出了回復闸昨，那么我們向下一個可疑的節(jié)點發(fā)送 ping，不斷這樣循環(huán)下去薄风，直到有某一個節(jié)點沒有給出 ping 的回復饵较，或者當前桶中的所有節(jié)點都是好的(也就是所有節(jié)點都不是可疑節(jié)點，他們在過去 15 分鐘內(nèi)都有活動)村刨。如果桶中的某個節(jié)點沒有對我們的 ping 給出回復告抄，我們最好再試一次(再發(fā)送一次 ping，因為這個節(jié)點也許仍然是活躍的嵌牺，但由于網(wǎng)絡擁塞打洼，所以發(fā)生了丟包現(xiàn)象，注意 DHT 的包都是 UDP 的)逆粹，而不是立即丟棄這個節(jié)點或者直接用新節(jié)點來替代它募疮。這樣，我們得路由表將充滿穩(wěn)定的長時間在線的節(jié)點僻弹。
每一個桶都應該維持一個 lastchange 字段來表明桶中節(jié)點的"新鮮"度阿浓。當桶中的節(jié)點被 ping 并給出了回復，或者一個節(jié)點被加入到了桶蹋绽，或者一個節(jié)點被一個新的節(jié)點所替代芭毙，桶的 lastchange 字段都應當被更新。如果一個桶的 lastchange 在過去的 15 分鐘內(nèi)都沒有變化卸耘，那么我們將更新它退敦。這個更新桶操作是這樣完成的：從這個桶所覆蓋的范圍中隨機選擇一個 ID，并對這個 ID 執(zhí)行 find_nodes 查找操作蚣抗。常常收到請求的節(jié)點通常不需要常常更新自己的桶侈百，反之，不常常收到請求的節(jié)點常常需要周期性的執(zhí)行更新所有桶的操作，這樣才能保證當我們用到 DHT 的時候钝域，里面有足夠多的好的節(jié)點讽坏。
在插入第一個節(jié)點到路由表并啟動服務后，這個節(jié)點應試著查找 DHT 中離自己更近的節(jié)點例证，這個查找工作是通過不斷的發(fā)出 find_node 消息給越來越近的節(jié)點來完成的路呜，當不能找到更近的節(jié)點時，這個擴散工作就結束了织咧。路由表應當被啟動工作和客戶端軟件保存（也就是啟動的時候從客戶端中讀取路由表信息拣宰，結束的時候客戶端軟件記錄到文件中）。
BitTorrent 協(xié)議擴展 BitTorrent Protocol Extension
BitTorrent 協(xié)議已經(jīng)被擴展為可以在通過 tracker 得到的 peer 之間互相交換節(jié)點的 UDP 端口號(也就是告訴對方我們的 DHT 服務端口號)烦感，在這樣的方式下，客戶端可以通過下載普通的種子文件來自動擴展 DHT 路由表膛堤。新安裝的客戶端第一次試著下載一個無 tracker 的種子時手趣，它的路由表中將沒有任何節(jié)點，這是它需要在 torrent 文件中找到聯(lián)系信息肥荔。
peers 如果支持 DHT 協(xié)議就將 BitTorrent 協(xié)議握手消息的保留位的第 8 字節(jié)的最后一位置為 1绿渣。這時如果 peer 收到一個 handshake 表明對方支持 DHT 協(xié)議，就應該發(fā)送 PORT 消息燕耿。它由字節(jié) 0x09 開始侍咱，payload 的長度是 2 個字節(jié)唉韭，包含了這個 peer 的 DHT 服務使用的網(wǎng)絡字節(jié)序的 UDP 端口號。當 peer 收到這樣的消息是應當向對方的 IP 和消息中指定的端口號的節(jié)點發(fā)送 ping。如果收到了 ping 的回復皆串，那么應當使用上述的方法將新節(jié)點的聯(lián)系信息加入到路由表中。
Torrent 文件擴展 Torrent File Extensions
一個無 tracker 的 torrent 文件字典不包含 announce 關鍵字难审，而使用一個 nodes 關鍵字來替代沙绝。這個關鍵字對應的內(nèi)容應該設置為 torrent 創(chuàng)建者的路由表中 K 個最接近的節(jié)點⊙窃伲可供選擇的郭膛，這個關鍵字也可以設置為一個已知的可用節(jié)點，比如這個 torrent 文件的創(chuàng)建者氛悬。請不要自動加入 router.bittorrent.com 到 torrent 文件中或者自動加入這個節(jié)點到客戶端路由表中则剃。
nodes = [["", ], ["", ], ...]
nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]
KRPC協(xié)議 KRPC Protocol
KRPC 協(xié)議是由 bencode 編碼組成的一個簡單的 RPC 結構，他使用 UDP 報文發(fā)送如捅。一個獨立的請求包被發(fā)出去然后一個獨立的包被回復棍现。這個協(xié)議沒有重發(fā)。它包含 3 種消息：請求伪朽，回復和錯誤轴咱。對DHT協(xié)議而言，這里有 4 種請求：ping，find_node朴肺，get_peers 和 announce_peer窖剑。
一條 KRPC 消息由一個獨立的字典組成，其中有 2 個關鍵字是所有的消息都包含的戈稿，其余的附加關鍵字取決于消息類型西土。每一個消息都包含 t 關鍵字，它是一個代表了 transaction ID 的字符串類型鞍盗。transaction ID 由請求節(jié)點產(chǎn)生需了，并且回復中要包含回顯該字段，所以回復可能對應一個節(jié)點的多個請求般甲。transaction ID 應當被編碼為一個短的二進制字符串肋乍，比如 2 個字節(jié)，這樣就可以對應 2^16 個請求敷存。另一個每個 KRPC 消息都包含的關鍵字是 y墓造，它由一個字節(jié)組成，表明這個消息的類型锚烦。y 對應的值有三種情況：q 表示請求觅闽，r 表示回復，e 表示錯誤涮俄。
聯(lián)系信息編碼 Contact Encoding
Peers 的聯(lián)系信息被編碼為 6 字節(jié)的字符串蛉拙。又被稱為 "CompactIP-address/port info"，其中前 4 個字節(jié)是網(wǎng)絡字節(jié)序的 IP 地址彻亲，后 2 個字節(jié)是網(wǎng)絡字節(jié)序的端口孕锄。
節(jié)點的聯(lián)系信息被編碼為 26 字節(jié)的字符串。又被稱為 "Compactnode info"睹栖，其中前 20 字節(jié)是網(wǎng)絡字節(jié)序的節(jié)點 ID硫惕，后面 6 個字節(jié)是 peers 的 "CompactIP-address/port info"。
請求 Queries
請求野来，對應于 KPRC 消息字典中的 y 關鍵字的值是 q恼除，它包含 2 個附加的關鍵字 q 和 a。關鍵字 q 是一個字符串類型曼氛，包含了請求的方法名字豁辉。關鍵字 a 一個字典類型包含了請求所附加的參數(shù)。
回復 Responses
回復舀患，對應于 KPRC 消息字典中的 y 關鍵字的值是 r徽级，包含了一個附加的關鍵字 r。關鍵字 r 是一個字典類型聊浅，包含了返回的值餐抢。發(fā)送回復消息是在正確解析了請求消息的基礎上完成的现使。
錯誤 Errors
錯誤，對應于 KPRC 消息字典中的 y 關鍵字的值是 e旷痕，包含一個附加的關鍵字 e碳锈。關鍵字e` 是一個列表類型。第一個元素是一個數(shù)字類型欺抗，表明了錯誤碼售碳。第二個元素是一個字符串類型，表明了錯誤信息绞呈。當一個請求不能解析或出錯時贸人，錯誤包將被發(fā)送。下表描述了可能出現(xiàn)的錯誤碼：
錯誤碼 描述
201 一般錯誤
202 服務錯誤
203 協(xié)議錯誤佃声，比如不規(guī)范的包艺智，無效的參數(shù)，或者錯誤的 token
204 未知方法
錯誤包例子 Example Error Packets:
generic error = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]}
bencoded = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee
DHT 請求 DHT Queries
所有的請求都包含一個關鍵字 id圾亏，它包含了請求節(jié)點的節(jié)點 ID力惯。所有的回復也包含關鍵字id，它包含了回復節(jié)點的節(jié)點 ID召嘶。
ping
最基礎的請求就是 ping。這時 KPRC 協(xié)議中的 "q" = "ping"哮缺。Ping 請求包含一個參數(shù) id弄跌，它是一個 20 字節(jié)的字符串包含了發(fā)送者網(wǎng)絡字節(jié)序的節(jié)點 ID。對應的 ping 回復也包含一個參數(shù) id尝苇，包含了回復者的節(jié)點 ID铛只。
參數(shù):
{"id" : ""}回復:
{"id" : ""}
報文包例子 Example Packets
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 的節(jié)點的聯(lián)系信息。這時 KPRC 協(xié)議中的 "q" == "find_node"糠溜。find_node 請求包含 2 個參數(shù)淳玩，第一個參數(shù)是 id，包含了請求節(jié)點的ID非竿。第二個參數(shù)是 target蜕着，包含了請求者正在查找的節(jié)點的 ID。當一個節(jié)點接收到了 find_node 的請求红柱，他應該給出對應的回復承匣，回復中包含 2 個關鍵字 id 和 nodes，nodes 是一個字符串類型锤悄，包含了被請求節(jié)點的路由表中最接近目標節(jié)點的 K(8) 個最接近的節(jié)點的聯(lián)系信息韧骗。
- 參數(shù):
{"id" : "", "target" : ""} - 回復:
{"id" : "", "nodes" : ""}
報文包例子 Example Packets
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
get_peers 與 torrent 文件的 infohash 有關。這時 KPRC 協(xié)議中的 "q" = "get_peers"零聚。get_peers 請求包含 2 個參數(shù)袍暴。第一個參數(shù)是 id些侍，包含了請求節(jié)點的 ID。第二個參數(shù)是 info_hash政模，它代表 torrent 文件的 infohash岗宣。如果被請求的節(jié)點有對應 info_hash 的 peers，他將返回一個關鍵字 values,這是一個列表類型的字符串览徒。每一個字符串包含了 "CompactIP-address/portinfo" 格式的 peers 信息狈定。如果被請求的節(jié)點沒有這個 infohash 的 peers，那么他將返回關鍵字 nodes习蓬，這個關鍵字包含了被請求節(jié)點的路由表中離 info_hash 最近的 K 個節(jié)點纽什，使用 "Compactnodeinfo" 格式回復。在這兩種情況下躲叼，關鍵字 token 都將被返回芦缰。token 關鍵字在今后的 annouce_peer 請求中必須要攜帶。token 是一個短的二進制字符串枫慷。
- 參數(shù):
{"id" : "", "info_hash" : "<20-byte infohash of target torrent>"} - 回復:
{"id" : "", "token" :"", "values" : ["", ""]} - 或:
{"id" : "", "token" :"", "nodes" : ""}
報文包例子 Example Packets:
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
這個請求用來表明發(fā)出 announce_peer 請求的節(jié)點让蕾，正在某個端口下載 torrent 文件。announce_peer 包含 4 個參數(shù)或听。第一個參數(shù)是 id探孝，包含了請求節(jié)點的 ID；第二個參數(shù)是 info_hash誉裆，包含了 torrent 文件的 infohash顿颅；第三個參數(shù)是 port 包含了整型的端口號，表明 peer 在哪個端口下載足丢；第四個參數(shù)數(shù)是 token粱腻，這是在之前的 get_peers 請求中收到的回復中包含的。收到 announce_peer 請求的節(jié)點必須檢查這個 token 與之前我們回復給這個節(jié)點 get_peers 的 token 是否相同斩跌。如果相同绍些，那么被請求的節(jié)點將記錄發(fā)送 announce_peer 節(jié)點的 IP 和請求中包含的 port 端口號在 peer 聯(lián)系信息中對應的 infohash 下。
參數(shù):
{
"id" : "",
"implied_port": <0 or 1>,
"info_hash" : "<20-byte infohash of target torrent>",
"port" : ,
"token" : ""
}
回復: {"id" : ""}
報文包例子 Example Packets:
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:abcdefghij01234567899: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
References
[1] Peter Maymounkov, David Mazieres, "Kademlia: A Peer-to-peer Information System Based on the XOR Metric", IPTPS 2002.
[2] Use SHA1 and plenty of entropy to ensure a unique ID.
Copyright
This document has been placed in the public domain.
