研究DHT,正好看到一个写的很不错的文章,直接转过来了
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客户端,懒得去剥了)。

参考资料

DHT Protocol
P2P中DHT网络介绍
Torrent文件结构解析
BitDHT源码
Transmission DHT源码
bencode
magnet
Crawling Bittorrent DHT
原文地址:http://codemacro.com/2013/05/19/crawl-dht/