DHT網絡爬蟲基于DHT網絡構建了一個P2P資源搜索引擎。這個搜索引擎不但可以用于構建DHT網絡中活躍的資源索引（活躍的資源意味著該網絡中肯定有人至少持有該資源的部分數據），還可以分析出該網絡中的熱門分享資源。小蝦不久前發布了一個這樣的搜索引擎：磁力搜索。他也寫博客對此稍作了介紹：寫了個磁力搜索的網頁 － 收錄最近熱門分享的資源。網絡上其實也有其他人做了類似的應用：DHT monitoring，Crawling Bittorrent DHT
但是他的這篇文章僅介紹了DHT網絡的大致工作原理，并且這個爬蟲的具體工作原理也沒有提到。對此我查閱了些文章及代碼，雖然從原理上梳理出了整個實現方案，但很多細節還是不甚清楚。所以本文僅作概要介紹。
DHT/Magnet/Torrent
在P2P網絡中，要通過種子文件下載一個資源，需要知道整個P2P網絡中有哪些計算機正在下載/上傳該資源。這里將這些提供某個資源下載的計算機定義為peer。傳統的P2P網絡中，存在一些tracker服務器，這些服務器的作用主要用于跟蹤某個資源有哪些關聯的peer。下載這個資源當然得首先取得這些peer。
DHT的出現用于解決當tracker服務器不可用時，P2P客戶端依然可以取得某個資源的peer。DHT解決這個問題，是因為它將原來tracker上的資源peer信息分散到了整個網絡中。這里將實現了DHT協議的計算機定義為節點(node)。通常一個P2P客戶端程序既是peer也是節點。DHT網絡有多種實現算法，例如Kademlia。
當某個P2P客戶端通過種子文件下載資源時，如果沒有tracker服務器，它就會向DHT網絡查詢這個資源對應的peer列表。資源的標識在DHT網絡中稱為infohash，是一個20字節長的字符串，一般通過sha1算法獲得，也就是一個類似UUID的東西。
實際上，種子文件本身就對應著一個infohash，這個infohash是通過種子文件的文件描述信息動態計算得到。一個種子文件包含了對應資源的描述信息，例如文件名、文件大小等。Magnet，這里指的是磁力鏈接，它是一個類似URL的字符串地址。P2P軟件通過磁力鏈接，會下載到一個種子文件，然后根據該種子文件繼續真實資源的下載。
磁力鏈接中包含的最重要的信息就是infohash。這個infohash一般為40字節或32字節，它其實只是資源infohash（20字節）的一種編碼形式。
Kademlia
Kademlia是DHT網絡的一種實現。網絡上關于這個算法的文章，主要是圍繞整個DHT網絡的實現原理進行論述。個人覺得這些文章很蛋疼，基本上讀了之后對于要如何去實現一個DHT客戶端還是沒有概念。這里主要可參考P2P中DHT網絡介紹，以及BitTorrent網站上的DHT協議描述
Kad的主要目的是用于查詢某個資源對應的peer列表，而這個peer列表實際上是分散在整個網絡中。網絡中節點數量很大，如果要獲得peer列表，最簡單的做法無非就是依次詢問網絡中的每個節點。這當然不可行。所以在Kad算法中，設立了一個路由表。每一個節點都有一份路由表。這個是按照節點之間的距離關系構建出來的。節點之間的距離當然也有特定的算法定義，在Kad中通過對兩個節點的ID進行異或操作得到。節點的ID和infohash通過相同算法構建，都是20字節長度。節點和infohash之間也有距離關系，實際上表示的是節點和資源的距離關系。
有了這個路由表之后，再通過一個基于距離關系的查找算法，就可以實現不用挨個遍歷就找到特定的節點。而查找資源peer這個操作，正是基于節點查找這個過程。
路由表的實現，按我的理解，有點類似一般的hash表結構。在這個表中有160個桶，稱為K桶，這個桶的數量在實現上可以動態增長。每個桶保存有限個元素，例如K取值為8，指的就是這個桶最多保存8個元素。每個元素就是一個節點，節點包含節點ID、地址信息以及peer信息。這些桶可以通過距離值索引得到，即距離值會經過一個hash算法，使其值落到桶的索引范圍內。
要加入一個DHT網絡，需要首先知道這個網絡中的任意一個節點。如何獲得這個節點？在一些開源的P2P軟件中，會提供一些節點地址，例如transmission中提供的dht.transmissionbt.com:6881。
協議
Kad定義了節點之間的交互協議。這些協議支撐了整個DHT網絡里信息分布式存儲的實現。這些協議都是使用UDP來傳送。其協議格式使用一種稱為bencode的編碼方式來編碼協議數據。bencode是一種文本格式的編碼，它還用于種子文件內的信息編碼。
Kad協議具體格式可參考BitTorrent的定義：DHT Protocol。這些協議包括4種請求：ping，find_node，get_peer，announce_peer。在有些文檔中這些請求的名字會有不同，例如announce_peer又被稱為store，get_peer被稱為find_value。這4種請求中，都會有對應的回應消息。其中最重要的消息是get_peer，其目的在于在網絡中查找某個資源對應的peer列表。
值得一提的是，所有這些請求，包括各種回應，都可以用于處理該消息的節點構建路由表。因為路由表本質就是存儲網絡中的節點信息。
ping
用于確定某個節點是否在線。這個請求主要用于輔助路由表的更新。
find_node
用于查找某個節點，以獲得其地址信息。當某個節點接收到該請求后，如果目標節點不在自己的路由表里，那么就返回離目標節點較近的K個節點。這個消息可用于節點啟動時構建路由表。通過find_node方式構建路由表，其實現方式為向DHT網絡查詢自己。那么，接收該查詢的節點就會一直返回其他節點了列表，查詢者遞歸查詢，直到無法查詢為止。那么，什么時候無法繼續查詢呢？這一點我也不太清楚。每一次查詢得到的都是離目標節點更接近的節點集，那么理論上經過若干次遞歸查詢后，就無法找到離目標節點更近的節點了，因為最近的節點是自己，但自己還未完全加入網絡。這意味著最后所有節點都會返回空的節點集合，這樣就算查詢結束？
實際上，通過find_node來構建路由表，以及順帶加入DHT網絡，這種方式什么時候停止在我看來并不重要。路由表的構建并不需要在啟動時構建完成，在以后與其他節點的交互過程中，路由表本身就會慢慢地得到構建。在初始階段盡可能地通過find_node去與其他節點交互，最大的好處無非就是盡早地讓網絡中的其他節點認識自己。
get_peer
通過資源的infohash獲得資源對應的peer列表。當查詢者獲得資源的peer列表后，它就可以通過這些peer進行資源下載了。收到該請求的節點會在自己的路由表中查找該infohash，如果有收錄，就返回對應的peer列表。如果沒有，則返回離該infohash較近的若干個節點。查詢者若收到的是節點列表，那么就會遞歸查找。這個過程同find_node一樣。
值得注意的是，get_peer的回應消息里會攜帶一個token，該token會用于稍后的announce_peer請求。
announce_peer
該請求主要目的在于通知，通知其他節點自己開始下載某個資源。這個消息用于構建網絡中資源的peer列表。當一個已經加入DHT網絡的P2P客戶端通過種子文件開始下載資源時，首先在網絡中查詢該資源的peer列表，這個過程通過get_peer完成。當某個節點從get_peer返回peer時，查詢者開始下載，然后通過announce_peer告訴返回這個peer的節點。
announce_peer中會攜帶get_peer回應消息里的token。關于這一點，我有一個疑問是，在P2P中DHT網絡介紹文檔中提到：
(announce_peer)同時會把自己的peer信息發送給先前的告訴者和自己K桶中的k個最近的節點存儲該peer-list信息
不管這里提到的K的最近的節點是離自己最近，還是離資源infohash最近的節點，因為處理announce_peer消息時，有一個token的驗證過程。但是這K個節點中，并沒有在之前創建對應的token。我通過transmission中的DHT實現做了個數據收集，可以證明的是，announce_peer消息是不僅僅會發給get_peer的回應者的。
DHT爬蟲
DHT爬蟲是一個遵循Kad協議的假節點程序。具體可以參考小蝦發布的那個網站應用：磁力搜索。
這個爬蟲的實現方式，主要包含以下內容：
- 通過其他節點的announce_peer發來的infohash確認網絡中有某個資源可被下載
- 通過從網絡中獲取這個資源的種子文件，來獲得該資源的描述
通過累計收集得到的資源信息，就可以提供一個資源搜索引擎，或者構建資源統計信息。以下進一步描述實現細節。整個爬蟲的實現依賴了一個很重要的信息，那就是資源的infohash實際上就是一個磁力鏈接（當然需要包裝一下數據）。這意味著一旦我們獲得了一個infohash，我們就等于獲得了一個種子。
獲得資源通知
當爬蟲程序加入DHT網絡后，它總會收到其他節點發來的announce_peer消息。announce_peer消息與get_peer消息里都帶了資源的infohash，但是get_peer里的infohash對應的資源在該網絡中不一定存在，即該資源沒有任何可用peer。而announce_peer則表示已經確認了該網絡中有節點正在下載該資源，也即該資源的數據確實存在該網絡中。
所以，爬蟲程序需要盡最大努力地獲取其他節點發來的announce_peer消息。如果announce_peer消息會發送給離消息發送節點較近的節點，那么，一方面，爬蟲程序應該將自己告訴網絡中盡可能多的節點。這可以通過一次完整的find_node操作實現。另一方面，爬蟲程序內部實現可以部署多個DHT節點，總之目的在于盡可能地讓爬蟲程序稱為其他節點的較近者。
當收集到infohash之后，爬蟲程序還需要通過該infohash獲得對應資源的描述信息。
獲取資源信息
獲得資源描述信息，其實就是通過infohash獲得對應的種子文件。這需要實現P2P協議里的文件分享協議。種子文件的獲取其實就是一個文件下載過程，下載到種子文件之后，就可以獲取到資源描述。這個過程一種簡單的方法，就是從infohash構建出一個磁力鏈接，然后交給一個支持磁力下載的程序下載種子。
從infohash構建出磁力鏈接非常簡單，只需要將infohash編碼成磁力鏈接的xt字段即可，構建實現可以從transmission源碼里找到：
/* 這個算法其實和printf("%02x", sha1[i])一樣 */
void tr_sha1_to_hex (char *out, const unsigned char *sha1)
{
int i;
static const char hex[] = "0123456789abcdef";
for (i=0; i<20; ++i) {
const unsigned int val = *sha1++;
*out++ = hex[val >> 4];
*out++ = hex[val & 0xf];
}
*out = '\0';
}
void appendMagnet(FILE *fp, const unsigned char *info_hash) {
char out[48];
tr_sha1_to_hex(out, info_hash);
fprintf(fp, "magnet:?xt=urn:btih:%s", out);
}
現在你就可以做一個實驗，在transmission的DHT實現中，在announce_peer消息的處理代碼中，將收到的infohash通過上面的appendMagnet轉換為磁力鏈接輸出到日志文件里。然后，可以通過支持磁力鏈接的程序（例如QQ旋風）直接下載。有趣的是，當QQ旋風開始下載該磁力鏈接對應的種子文件時，你自己的測試程序能收到QQ旋風程序發出的announce_peer消息。當然，你得想辦法讓這個測試程序盡可能地讓其他節點知道你，這可以通過很多方式實現。
總結
最終的DHT爬蟲除了需要實現DHT協議之外，還需要實現P2P文件下載協議，甚至包括一個種子文件解析模塊。看起來包含不小的工作量。而如果要包裝為一個資源搜索引擎，還會涉及到資源存儲以及搜索，更別說前端呈現了。這個時候，如果你使用的語言不包含這些工具庫，那實在是太悲劇了。沒錯，我就沒找到一個erlang DHT庫（倒是有erlang實現的BT客戶端，懶得去剝了）。
UPDATE
通過詳細閱讀transmission里的DHT實現，一些之前的疑惑隨之解開。
announce_peer會發給哪些節點
在一次對infohash的查詢過程中，所有對本節點發出的get_peer作出回應的節點（不論這個回應節點回應的是nodes還是peers），當本節點取得peer信息時，就會對所有這些節點發出announce_peer。get_peer的回應消息里，不論是peer還是node，都會攜帶一個token，這樣在將來收到對方的announce_peer時，就可以驗證該token。
節點和bucket狀態
在本地的路由表中，保存的node是有狀態之分的。狀態分為三種：good/dubious/bad。good節點基本可以斷定該節點是一個在線的并且可以正常回應消息的節點；而bad節點則是可確定的無效節點，通常會盡快從路由表中移除；而dubious則是介于good和bad節點之間，表示可能有問題的節點，需要進一步發送例如ping消息來確認其狀態。路由表中應該盡可能保證保存的是good節點，對查詢消息的回應里也需攜帶好的節點。
bucket也是有狀態的，當一個bucket中的所有節點在一定時間之內都沒有任何活動的時候，該bucket則應該考慮進行狀態的確認，確認方式可以隨機選擇該bucket中的節點進行find_node操作（這也是find_node除了用于啟動之外的唯一作用，但具體實現不見得使用這種方式）。沒有消息來往的bucket則應該考慮移除。DHT中幾乎所有操作都會涉及到bucket的索引，如果索引到一個所有節點都有問題的bucket，那么該操作可能就無法完成。
search在何時停止
首先，某次發起的search，無論是對node還是對peer，都可能導致進一步產生若干個search。這些search都是基于transaction id來標識的。由一次search導致產生的所有子search都擁有相同的transaction id，以使得在該search成功或失敗時可以通過該transaction id來刪除對應的所有search。transaction id也就是DHT中每個消息消息頭”t”的值。
但是search何時停止？transmission中是通過超時機制來停止。在search過程中，如果長時間沒有收到跟該search關聯的節點發來的回應消息，那么就撤銷該search，表示搜索失敗。
參考資料