1、前言

英文版官方地址：http://www.bittorrent.org/beps/bep_0005.html

BitTorrent使用一種叫做分布式哈希表(distributedsloppy hashtable)的技術，來實作在無tracker的torrent檔案中peer的聯系資訊存盤，這個時候，每個peer都是一個tracker，這個協議是基于Kademila協議的，并且在UDP協議基礎上實作，

請注意本檔案所使用的術語以免引起混淆，“peer”是一個實作了BT協議，且正在監聽TCP埠的client/server，“node”是實作了DHT協議的，且正在監聽UDP埠的client/server，DHT由nodes組成并保存peer的位置資訊，BitTorrent客戶端也包括DHTnode，這個DHTnode主要是用來聯系DHT中的其他nodes，以得peer的位置資訊，從而通過BitTorrent協議下載，

2、DHT協議介紹

2.1、概述

每一個node都有一個全域的唯一標識“nodeID”，NodeIDS的產生是隨機的，且使用與BitTorrent的infohashes相同的160-bit空間，“distancemetric”用來比較2個nodeIDs或者nodeID與infohash的接近程度，Nodes必須維護一個路由表，其中保存了一部分其他nodes的聯系資訊，越接近自身節點時，路由表的資訊會更加詳細，nodes保存了很多接近自己的節點，但是離自己很遠的節點的聯系資訊確知道得很少，

在Kademlia中，“distancemetric”采用XOR異或計算，并轉換為一個無符號整數，distance(A,B)= |A xor B| ，并且距離越小表示2個節點越接近，

當一個node想得到某個torrent檔案的peers，它首先使用distancemetric來比較torrent檔案的info_hash和路由表中節點的nodeID，接下來向路由表中nodeID與info_hash最接近的那些節點發送請求，得到當前正在下載這個torrent檔案資料的peers的聯系資訊，如果被請求的節點知道這個torrent檔案的peers，那么peer的聯系資訊將包含在回復中，否則，被請求的節點必須回傳他的路由表中更接近info_hash得那些節點，原始的請求node不斷向新獲得的那些node中，更接近目標info_hash的那些node發送請求，直到不能獲得更近的nodes，當查找結束時，client將自己的資訊作為一個peer插入到在剛才請求中給出回復的那些節點中，nodeid與info_hash最接近的哪個節點上，這樣，哪個節點又多保存了一個peer資訊，

在請求peers的時候，對方給我們的回復必須還包含一個不透明的令牌，我們稱他為“token”，這樣當我們宣布我們正在下載某個torrent，想讓對方保存我們的資訊時，我們必須使用對方向我們發送的最近的一個token，這樣當我們宣布我們在下載一個torrent時，被請求的node檢查這個token和IP是否與之前他們向我們回復的一樣，這樣是為了防止惡意的攻擊，由于token僅僅由請求的節點回傳，所以我們不規定他的具體實作，但是token必須有一個可接受的時間范圍，超過這個時間，token將失效，在BitTorrent的實作中，token是在IP地址后面連接一個secret(可以視為一個亂數)，這個secret每五分鐘改變一次，其中token在十分鐘以內是可接受的，

2.2、路由表

每一個node維護一個路由表保存已知的好節點，這些路由表中的nodes被作為DHT請求的起始節點，路由表中的nodes是在不斷的向其他node請求程序中，對方節點回復的，

并不是我們在請求程序中收到得節點都是平等的，有的node是好的，而有的node是死掉的，很多使用DHT協議的nodes都可以發送請求并接識訓復，但是不能主動回復其他節點的請求(我認為這是由于防火墻或者NAT的原因)，對每一個node的路由表，只包含好的nodes是很重要的，好的node是指在過去的15分鐘以內，曾經對我們的某一個請求給出過回復的節點；或者曾經對我們的請求給出過一個回復(不用在15分鐘以內)，并且在過去的15分鐘給我們發送過請求，上述兩種情況都可將node視為好的node，在15分鐘之后，對方沒有上述2種情況發生，這個node將變為可疑的，當nodes不能給我們的一系列請求給出回復時，這個節點將變為壞的，相比未知狀態的nodes，我們將給好的節點更高的優先權，

路由表覆寫從0到2160完整的nodeID空間，路由表又被劃分為buckets(桶)，每一個bucket包含一個子部分的nodeID空間，一個空的路由表只有一個bucket，它的ID范圍從min=0到max=2160，當一個nodeID為“N”的node插入到表中時，它將被放到ID范圍在min<=N<max的bucket中，一個空的路由表只有一個bucket所以所有的node都將被放到這個bucket中，每一個bucket最多只能保存K個nodes，當前K=8，當一個bucket放滿了好的nodes之后，將不再允許新的節點加入，除非我們自身的nodeID在這個bucket的范圍內，在這樣的情況下，這個bucket將被分裂為2個新的buckets，每一個新桶的范圍都是原來舊桶的一半，原來舊桶中的nodes將被重新分配到這兩個新的buckets中，如果是一個只有一個bucket的新表，這個包含整個范圍的bucket將總被分裂為2個新的buckets，第一個的覆寫范圍從0…2159，第二個的范圍從2159…2160，

當bucket裝滿了好的nodes，那么新的node將被丟棄，一旦bucket中的某一個node變為了壞的node，那么我們就用新的node來替換這個壞的node，如果bucket中有在15分鐘內都沒有活躍過的節點，我們將這樣的節點視為可疑的節點，這時我們向最久沒有聯系的節點發送ping，如果被pinged的節點給出了回復，那么我們向下一個可疑的節點發送ping，不斷這樣回圈下去，直到有某一個node沒有給出ping的回復，或者當前bucket中的所有nodes都是好的(也就是所有nodes都不是可疑nodes，他們在過去15分鐘內都有活動)，如果bucket中的某個node沒有對我們的ping給出回復，我們最好再試一次(再發送一次ping，因為這個node也許仍然是活躍的，但由于網路擁塞，所以發生了丟包現象，注意DHT的包都是UDP的)，而不是立即丟棄這個node或者直接用新node來替代它，這樣，我們得路由表將充滿穩定的長時間在線的nodes，

每一個bucket都應該維持一個“lastchange”欄位來表明bucket中的nodes有多新鮮，當一個bucket中的node被ping并給出了回復，或者一個node被加入到了bucket，或者一個node被一個新的node所替代，bucket的“lastchanged”欄位都應當被更新，如果一個bucket的“lastchange”在過去的15分鐘內都沒有變化，那么我們將更新它，這個更新bucket操作是這樣完成的：從這個bucket所覆寫的范圍中隨機選擇一個ID，并對這個ID執行find_nodes查找操作，常常收到請求的nodes通常不需要常常更新自己的buckets，反之，不常常收到請求的nodes常常需要周期性的執行更新所有buckets的操作，這樣才能保證當我們用到DHT的時候，里面有足夠多的好的nodes，

在第一個node插入路由表并開始服務后，這個node應該試著查找離自身更近的node，這個查找作業是通過不斷的發布find_node訊息給越來越近的nodes來完成的，當不能找到更近的節點時，這個擴散作業就結束了，路由表應當被啟動作業和客戶端軟體保存（也就是啟動的時候從客戶端中讀取路由表資訊，結束的時候客戶端軟體記錄到檔案中），

2.3、BitTorret協議擴展

BitTorrent協議已經被擴展為可以在通過tracker得到的peer之間互相交換nodeUDP埠號(也就是告訴對方我們的DHT服務埠號)，在這樣的方式下，客戶端可以通過下載普通的種子檔案來自動擴展DHT路由表，新安裝的客戶端第一次試著下載一個無tracker的種子時，它的路由表中將沒有任何nodes，這是它需要在torrent檔案中找到聯系資訊，

peers如果支持DHT協議就將BitTorrent協議握手訊息的保留位的第八位元組的最后一位置為1，這時如果peer收到一個handshake表明對方支持DHT協議，就應該發送PORT訊息，它由位元組0x09開始，payload的長度是2個位元組，包含了這個peer的DHT服務使用的網路位元組序的UDP埠號，當peer收到這樣的訊息是應當向對方的IP和訊息中指定的埠號的node發送ping，如果收到了ping的回復，那么應當使用上述的方法將新node的聯系資訊加入到路由表中，

2.4、Torrent檔案擴展

一個無tracker的torrent檔案字典不包含announce關鍵字，而使用一個nodes關鍵字來替代，這個關鍵字對應的內容應該設定為torrent創建者的路由表中K個最接近的nodes，可供選擇的，這個關鍵字也可以設定為一個已知的可用節點，比如這個torrent檔案的創建者，請不要自動加入router.bittorrent.com到torrent檔案中或者自動加入這個node到客戶端路由表中，

nodes= [["", ], ["",], …]

nodes= [[“127.0.0.1”, 6881], [“your.router.node”, 4804]]

2.5、KRPC協議

KRPC協議是由B編碼組成的一個簡單的RPC結構，他使用UDP報文發送，一個獨立的請求包被發出去然后一個獨立的包被回復，這個協議沒有重發，它包含3種訊息：請求，回復和錯誤，對DHT協議而言，這里有4種請求：ping，find_node,get_peers,和announce_peer，

一個KRPC訊息由一個獨立的字典組成，其中有2個關鍵字是所有的訊息都包含的，其余的附加關鍵字取決于訊息型別，每一個訊息都包含t關鍵字，它是一個代表了transactionID的字串型別，transactionID由請求node產生，并且回復中要包含回顯該欄位，所以回復可能對應一個節點的多個請求，transactionID應當被編碼為一個短的二進制字串，比如2個位元組，這樣就可以對應2^16個請求，另一個每個KRPC訊息都包含的關鍵字是y，它由一個位元組組成，表明這個訊息的型別，y對應的值有三種情況：q表示請求，r表示回復，e表示錯誤，

2.6、聯系資訊編碼

Peers的聯系資訊被編碼為6位元組的字串，又被稱為"CompactIP-address/port info"，其中前4個位元組是網路位元組序的IP地址，后2個位元組是網路位元組序的埠，

Nodes的聯系資訊被編碼為26位元組的字串，又被稱為"Compactnode info"，其中前20位元組是網路位元組序的nodeID，后面6個位元組是peers的"CompactIP-address/port info"，

請求
請求，對應于KPRC訊息字典中的“y”關鍵字的值是“q”，它包含2個附加的關鍵字“q”和“a”，關鍵字“q”是一個字串型別，包含了請求的方法名字，關鍵字“a”一個字典型別包含了請求所附加的引數，

回復
回復，對應于KPRC訊息字典中的“y”關鍵字的值是“r”，包含了一個附加的關鍵字r，關鍵字“r”是一個字典型別，包含了回傳的值，發送回復訊息是在正確決議了請求訊息的基礎上完成的，

錯誤
錯誤，對應于KPRC訊息字典中的y關鍵字的值是“e”，包含一個附加的關鍵字e，關鍵字“e”是一個串列型別，第一個元素是一個數字型別，表明了錯誤碼，第二個元素是一個字串型別，表明了錯誤資訊，當一個請求不能決議或出錯時，錯誤包將被發送，下表描述了可能出現的錯誤碼：

2.7、DHT請求

所有的請求都包含一個關鍵字id，它包含了請求節點的nodeID，所有的回復也包含關鍵字id，它包含了回復節點的nodeID，

2.7.1、ping

ping是最基礎的請求，此時KPRC協議中的“q”=“ping”，Ping請求包含一個引數id，它是一個20位元組的字串包含了發送者網路位元組序的nodeID，對應的ping回復也包含一個引數id，包含了回復者的nodeID，

請求引數：{“id” : “<querying nodes id>”}
回復引數：{“id” : “<queried nodes id>”}

報文包例子：

請求：{“t”:“aa”, “y”:“q”, “q”:“ping”, “a”:{“id”:“abcdefghij0123456789”}}
對應的B編碼：d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe

回復：{“t”:“aa”, “y”:“r”, “r”:{“id”:“mnopqrstuvwxyz123456”}}
對應的B編碼：d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

2.7.2、find_node

find_node被用來查找給定ID的node的聯系資訊，此時KPRC協議中的q=“find_node”，find_node請求包含2個引數，第一個引數是id，包含了請求node的nodeID，第二個引數是target，包含了請求者正在查找的node的nodeID，當一個node接收到了find_node的請求，他應該給出對應的回復，回復中包含2個關鍵字id和nodes，nodes是一個字串型別，包含了被請求節點的路由表中最接近目標node的K(8)個最接近的nodes的聯系資訊，

請求引數：{“id”:"<querying nodes id>", “target”:"<id of target node>"}
回復引數：{“id”:"<queried nodes id>", “nodes”:"<compact node info>"}

報文包例子

請求：{“t”:“aa”, “y”:“q”, “q”:“find_node”, “a”:{“id”:“abcdefghij0123456789”, “target”:“mnopqrstuvwxyz123456”}}
對應的B編碼：d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe

回復：{“t”:“aa”, “y”:“r”, “r”:{“id”:“0123456789abcdefghij”, “nodes”:“def456…”}}
對應的B編碼：d1:rd2:id20:0123456789abcdefghij5:nodes9:def456…e1:t2:aa1:y1:re

2.7.3、get_peers

get_peers與torrent檔案的info_hash有關，此時KPRC協議中的q=”get_peers”，get_peers請求包含2個引數，第一個引數是id，包含了請求node的nodeID，第二個引數是info_hash，它代表torrent檔案的infohash，如果被請求的節點有對應info_hash的peers，他將回傳一個關鍵字values,這是一個串列型別的字串，每一個字串包含了"CompactIP-address/portinfo"格式的peers資訊，如果被請求的節點沒有這個infohash的peers，那么他將回傳關鍵字nodes，這個關鍵字包含了被請求節點的路由表中離info_hash最近的K個nodes，使用"Compactnodeinfo"格式回復，在這兩種情況下，關鍵字token都將被回傳，token關鍵字在今后的annouce_peer請求中必須要攜帶，token是一個短的二進制字串，

請求引數：{“id”:"<querying nodes id>", “info_hash”:"<20-byte infohash of targettorrent>"}
回復引數：{“id”:"<queried nodes id>", “token”:"<opaque write token>", “values”:["<peer 1 info string>", “<peer 2 info string>”]}
或：{“id”:"<queried nodes id>", “token”:"<opaque write token>", “nodes”:"<compact node info>"}

報文包例子

請求：{“t”:“aa”, “y”:“q”, “q”:“get_peers”, “a”:{“id”:“abcdefghij0123456789”,“info_hash”:“mnopqrstuvwxyz123456”}}
對應的B編碼：d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe

一般回復：{“t”:“aa”, “y”:“r”, “r”:{“id”:“abcdefghij0123456789”, “token”:“aoeusnth”, “values”: [“axje.u”, “idhtnm”]}}
對應的B編碼：d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re

回復最接近的nodes： {“t”:“aa”, “y”:“r”, “r”:{“id”:“abcdefghij0123456789”, “token”:“aoeusnth”, “nodes”: “def456…”}}
對應的B編碼：d1:rd2:id20:abcdefghij01234567895:nodes9:def456…5:token8:aoeusnthe1:t2:aa1:y1:re

2.7.4、announce_peer

這個請求用來表明發出announce_peer請求的node，正在某個埠下載torrent檔案，announce_peer包含4個引數，第一個引數是id，包含了請求node的nodeID；第二個引數是info_hash，包含了torrent檔案的infohash；第三個引數是port包含了整型的埠號，表明peer在哪個埠下載；第四個引數數是token，這是在之前的get_peers請求中收到的回復中包含的，收到announce_peer請求的node必須檢查這個token與之前我們回復給這個節點get_peers的token是否相同，如果相同，那么被請求的節點將記錄發送announce_peer節點的IP和請求中包含的port埠號在peer聯系資訊中對應的infohash下，

請求引數：{“id”:"<querying nodes id>", “info_hash”:"<20-byte infohash of target torrent>", “port”:<port number>, “token”:"<opaque token>"}
回復引數：{“id”:"<queried nodes id>"}

報文包例子

請求：{“t”:“aa”, “y”:“q”, “q”:“announce_peer”, “a”:{“id”:“abcdefghij0123456789”, “info_hash”:“mnopqrstuvwxyz123456”, “port”:6881, “token”: “aoeusnth”}}
對應的B編碼：d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe

回復：{“t”:“aa”, “y”:“r”, “r”:{“id”:“mnopqrstuvwxyz123456”}}
對應的B編碼：d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re