当前位置:首页 > 短网址资讯 > 正文内容

DHT 爬虫初步研究

www.ft12.com8年前 (2017-07-25)短网址资讯2646

一直想写一个种子搜索引擎,搜集资料开始写后遇到了一个难关:爬虫的效率太低,运行一天也爬不到一条
消息,而且阿里云在我的程序开始运行后一天就无法远程登录,只能重启服务器。一度计划被搁置了下来,直到最近事情出现了转机,我找到了更好的爬虫原型,并且对比之下发现了旧爬虫效率低下的原因,特写下此文记录。

DHT

DHT(Distributed Hash Table,分布式哈希表)。DHT 系统中有三个值,分别是节点标识(节点 ID),对象关键字(key)和对象值(value),节点存储的是对象的 <key,value> 对。

大部分结构式 P2P 网络都使用 DHT 系统。DHT 的主要功能包括3个内容:

  • 标识符的生成和管理

  • 提供重叠网络中的查询定位的路由服务

  • 对提供的服务或文件的信息进行管理

DHT 系统有四个基本操作(以 Kademlia 算法为主):

  • ping 操作。作用是探测一个节点,用以判断该节点是否仍然在线。

  • store 操作,作用是通知一个节点存储一个<key,value>对,以便以后查询需要。

  • find_node 操作,作用是从自己的“路由表”对应的 K 桶中返回 k 个节点信息(IP address, UDP port, Node ID)给发送者。

  • find_value 操作,作用是把 info-hash(key) 作为参数,如果本操作接收者正好存储了 info-hash 的 peers(value) 则返回 peers list,否则从自己的“路由表“中返回离 info-hash 更近的 k 个节点信息(同 find_node 过程)。

Kademlia

DHT 系统有很多资源定位算法,包括 Chord,Pastry,CAN 和 Kademlia 等。其中 bittorrent 中的 DHT 系统选用了 Kademlia 算法作为资源定位算法。

Kademlia 与其他 DHT 算法相同,所有信息均以 <key, value> 对的散列表条目形式加以存储,这些 <key, value> 对分散地存储在各节点上。每个 ID 和关键字值有160bit。为了发布和寻找 <key, value> 对,Kademlia 采用两节点之间距离(Distance)的概念。与其他 DHT 算法相比,两节点距离不依靠物理距离、跳数,而是通过异或算法(XOR)为距离度量基础,建立了一个全新的 DHT 拓扑结果,大大提高了查询速度。

节点 X 要查找 ID 值为 t 的节点 T,过程如下:

  1. 计算 X 到 T 的距离 d(x,t)=x?t

  2. 从 X 的第 [log2d]个 K 桶中取出 α 个节点的信息(各个实现 α 值不一样,有些是3有些则等于k值),同时进行 FIND_NODE 操作。如果这个K 桶中的信息少于 α 个,则从附近多个桶中选择距离最接近d 的总共α个节点。

  3. 对接受到查询操作的每个节点,如果发现自己就是 T,则回答自己是最接近 T 的。否则测量自己和 T 的距离,并从自己对应的 K 桶中选择 α 个节点的信息给 X。

  4. X 对新接受到的每个节点都再次执行 FIND_NODE 操作,此过程不断重复执行,直到每一个分支都有节点响应自己是最接近 T 的,或者说 FIND_NODE 操作返回的节点值没有都已经被查找过了,即找不到更近的节点了。

  5. 通过上述查找操作,X 得到了 k 个最接近 T 的节点信息。

注意:这里用『最接近』这个说法,是因为 ID 值为t 的节点不一定存在网络中,也就是说 t 没有分配给任何一台电脑。

bt-dht 中查找 peers-list 的过程则换成 find_value 动作,但注意前文提到的区别即可以有类似的描述。

注意:Kademlia 算法运行一段时间后,大部分 <key,value> 对象会在节点 X 聚集,其中 X 的 ID 值和 key 的距离很近,也就是 Kademlia 算法查找资源的依据。

DHT 爬虫协议

这里指的 DHT 爬虫主要是指使用 Kademlia 算法的 bt-dht 爬虫。bt-dht 使用 krpc 协议和 bencode 编码。

bt-dht 请求有四种,分别是:

  • ping(回复 pong)

  • find_node(回复 found_node)

  • get_peers(回复 got_peers)

  • announce_peer

基本和 DHT 的四种基本操作一致,这里要介绍的是 announce_peer 请求,该请求表示节点 X 当前正在下载请求中指定的资源,发送的目标节点是之前向 X 发送过 got_peers 的节点,并且携带有 got_peers 中带有的 token 作为验证。bt-dht 爬虫主要搜集的就是 announce_peer 中携带的资源 info_hash 和 get_peers 中的资源 info_hash,可以以此了解资源的热度。

DHT 爬虫实现

在 Github 上已经有很多 DHT 爬虫的实现,简单列举几个我测试过的:

其中两个 simDHT 都是真正的爬虫,而 dhtfck 更接近一个正常的 DHT 节点。不幸的是我一开始采用了 dhtfck 作为参考开发,即使开启了 32 个爬虫进行爬取,收到的 announce 数也寥寥无几。一度爬虫的开发陷入停滞,因为找不到提高爬虫效率的方法,看到网上博客介绍的爬虫效率,我只能无奈,直到发现了 simDHT,这个纯正的 DHT 爬虫。

对比了两个爬虫间的区别,我发现了问题的根源,dhtfck 每次只向数量很少的节点发出 find_node 请求,并一直维护 node 池中的节点,导致最终爬虫只被少数节点记录,收集效率当然不高。而 simDHT 则是以一定频率按顺序向节点列表中的节点发出 find_node 请求,并删除旧的节点,这样发现该爬虫的节点以很快的速度增长,而且不需要定期维护节点池。

获取了 info_hash 后可以从一些种子网站下取对应的种子,如 torcache;也可以构造磁力链接然后用迅雷等工具下载;也可以借助 libtorrent 库下载内容,甚至借助 bittorrent 协议中的 Extension for Peers to Send Metadata Files,通过发出 announce_peer 的节点获取资源。


扫描二维码推送至手机访问。

版权声明:本文由短链接发布,如需转载请注明出处。

本文链接:https://www.ft12.com/article_347.html

标签: DHT爬虫
分享给朋友:

相关文章

奶奶的“漫漫”

奶奶的“漫漫”

昨天下了一天雨,以前习惯跑的路有泥洼,换到马路上去跑了五公里,看见一路的农家乐,招牌菜居然是烤全羊。跑步回来,我奶奶就向组织报告:“后院枣树上还有枣,你妈之前打算给你打了放冰箱的,晓得你要漫漫,我让她给你留了点儿。”她懂我喜欢的浪漫。我回家...

企业三大痛点再也不用怕,智能客服帮你来解决

企业三大痛点再也不用怕,智能客服帮你来解决

[ FT12短网址资讯 ] 客户集体数目大、咨询频次高、疑问重复度高的话,引进高性能的智能客服机器人能极大地节约人工本钱;社会开展到今日,挑选的极大丰富,让用户已习惯于享用各种便当,想得到就要立刻得到,智能客服契合了这一...

玩王者荣耀觉得辅助都是躺赢的,祝你们对手遇到我

玩王者荣耀觉得辅助都是躺赢的,祝你们对手遇到我

我以前玩虚荣的时候,固定打游走的位置,靠着天使奥达基,经常被朋友夸。但也偶尔也被人嫌弃,我有个朋友,总认为辅助就是天生女孩子玩儿的,男人就该往前冲冲冲。他打虚荣的时候,玩豹哥扛着斧头就往前冲,每次打着打着人不见了,对兵矿有谜一样的热情,队伍...

FT12短网址:人与人的差距是怎么拉开的?

疑问:俞老师好,人与人之间的距离是怎么摆开的?每个人都有一个头脑,两只手、两条腿,但随着时刻的推移,即使是同一个社会层次,在同一个校园读书的人,最终的间隔都会拉得越来越大,有的人走向平凡,有的人则不断走向成功,你以为这里面最首要的因素是什么...

赌博、自杀、精神病:FT12短网址带你揭秘重度电竞玩家的真实生活

英国《卫报》日前发表文章称,全球成长速度最快的体育运动项目是什么?许多人可能会认为是足球。其实答案并不是它,而是电子竞技。但越来越多的影响证明,电子竞技对相关人员是有害的。以下为文章内容摘要:  如果过去的四分之一个世纪有人不在地球上,那么...

干货:从0到0.01,如何从知乎神贴找到创业机会

干货:从0到0.01,如何从知乎神贴找到创业机会

从0到1,提的人多。方法论都在讲:创业要判断风口、进入蓝海商场、挖掘用户刚需、找到细分切入点。 然而怎么找到那个最小的切入点,从0到0.01,却鲜有人提。今天咱们来做一个测验,谈论一个完整的从0到0.01的思路:怎么从用户需要挖掘到商品规划...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。