广域网分布式Web爬虫

广域网分布式Web 爬虫滕千红(湖工，管院，1010831119）摘要：分析了广域网分布式Web 爬虫相对于局域网爬虫的诸多优势，提出了广域网分布式Web 爬虫的3个核心问题：Web 划分、Agent

广域网分布式Web 爬虫

滕千红

(湖工，管院，1010831119）

摘要：分析了广域网分布式Web 爬虫相对于局域网爬虫的诸多优势，提出了广域网分布式Web 爬虫的3个核心问题：Web 划分、Agent 协同和Agent 部署周绕这3个问题，对目前学术界和商业界出现的多种实现方案和策略进行了全面的综述，深入讨论了研究中遇到的问题与挑战，并论述了广域网分布式Web 爬虫的评价模型．最后，对未来的研究方向进行了总结。

关键词：搜索引擎；广域网分布式爬虫；Web 划分；Agent 协同；Agent 部属。

搜索引擎作为互联网上一种有效的信息获取渠道，与电子邮件、即时通信并称为互联网三大基础应用。在人们的日常生活中发挥着重要的作用．然而，互联网的飞速发展使搜索引擎面临巨大的挑战．2008年1月发布的《第21次中国互联网络发展状况统计报告》显示，中国网站数量已达150万个，比去年同期增长了66万个，增长率达到78．4％：中国总网页数为84．7亿个，年增长率达到89．4％；网站总字节数已经达到198 348GB．按照目前的统计数字，假设搜索引擎爬虫系统的网络接入总带宽为lOOMb ／s ，即使这些带宽被完全利用，仅下载中国的网页就需要近200天．如此巨大的数据量，使得对网页内容和链接关系的处理必须由多机并行完成。分布式Web 爬虫是

由多个可并发获取Web 信息的Agent 构成的Web 爬虫系统，每个Agent 运行于不同的计算资源之上，这些资源或集中部署在同一个局域网(10cal area network，简称LAN) 内部，或分布在广域l 网(wide area network。简称WAN) 的不同地理位置和网络位置，每个Agent 以多进程或多线程方式通过并发保持多个TCP 链接获取Web 信息．部署于LAN 上的分布式Web 爬虫受到带宽等因素的制约，已经不能对Web 进行快速而有效的抓取．基于广域网的分布式爬虫实现方案具有多点接入总带宽较高、对Internet 负载较小、容易实现就近高效抓取以及可扩展性强等优点，已经成为学术界、商业界和开源社区爬虫系统实现的优选方案。广域网分布式爬虫融合了分布式系统、并行计算及网络测量等主题，具有很强的应用价值与理论研究意义。

1、引言

在分布式Web 爬虫领域，商业界与学术界各自为战，许多优秀的实现方法不是源自于学术界，而是来自于一些公司．出于商业因素的考虑，公司成果一般不通过论文公开发表；而学术界的研究成果虽然公开，但是被大规模采用的并不多；另外，还有一些组织和个人以GPL(GNU general public license) 的方式开发和发布自己的系统．遗憾的是，这类系统也很少以论文形式发表．部署在LAN 上的分布式Web 爬虫率先被提出，并得到广泛的使用．较为著名的有早期的Google[舶，AltaVista 的Intnet Archive Crawlert31，Mercatert4I 等．但是，由于受到带宽等瓶颈因素的制约，此种系统即使软硬件的规模不断扩大，也只能获取全体Web 信息中相对较小的一部分．为了

解决上述问题，人们提出了部署于广域网环境的分布式Web 爬虫．

1．1相关工作

近几年来，商业界和开源社区出现了一些广域网分布式爬虫系统(或搜索引擎) ，其思路一般是公司或组织向用户提供爬虫程序．一方面，分布在各地的用户运行自己机器上的爬虫程序为公司提供数据；另一方面，公司为安装有爬虫的用户提供各种检索服务，如Yacy(http：／／yaey ．net ／) 的个性化匿名检索，甚至将利润反馈给用户(如 Faroo(http：／／www ．faroo ．corn ／)) ．在实现方面，这些系统有的是类似于SETI@Home那样的主从式结构(如Majestic(http：／／www ．majesticl2．co ．uk0) ，属于有调度中心的Agent 协同；有的是P2P 方式进行分布式调度(如Faroo) ，即无调度中心的Agent 协同．这些系统的实现五花八门，但是由于发展时间较短，规模相对较小．在学术方面，Cho 等人首次给出了分布式爬虫的分类方法、评价指标等一系列基本概念，并提出基于广域网分布式爬虫与部署于LAN 的系统相比，具有高可扩展性和减少Internet 负载的优点，为广域网分布式爬虫的研究奠定了基础．UbiCrawert 扩展了一些概念，并声称可以支持基于广域网的分布式平台．Dustin B

等人对多种分布式爬虫进行了比较，提出广域网爬虫是解决爬虫系统带宽瓶颈的有效方法．Yahoo 研究院的Baeza ．Yates 等人在其综述中将分布式爬虫定义为“原则上某些节点可以分布于不同的地理或网络位置”．2003年后，很多研究开始关注广域网分布式爬虫，代表性的有，IPMicrat 第～个基于位置信息调度的分布式爬虫，SE4SEE 实

现了基于网格的分布式爬虫，Apoideatl 实现了基于P2P 协议的完全分布式爬虫．国内学术界对分布式爬虫研究得较少，代表性的有北京大学的天网搜索引擎[14J的爬虫系统，这是一个基于LAN 的爬虫，已经开始商业化运作；上海交通大学的Igloo 爬虫实现了基于网格服务的分布式爬虫(IglooG)，万方网格的特性使其能够支持广域网部署．

1．2分布式爬虫的基本结构和工作流程

由于爬虫要下载多个网页，而各个网页的下载过程之间依赖性较小，因此可以被并行化．为了高效地下载网页，爬虫程序一般被设计为多线程和多进程协同的方式，而分布式爬虫是将多个具有抓取网页功能的Agent 分别部署于多个计算资源之上的爬虫程序．以下是分布式爬虫中每个Agent 的大致工作流程(其中，左侧带 号的两行代码可能需要多机协同完成) ．为了突出Agent 对URL 的处理，算法描述省略了域名解析、对网页和URL 的预处理以及解析网站的Robots ．txt 文件的过程．

URL Seen：用于存储已经抓取过的URL ．

URL 队列：用于存储待抓取的URL ．

输入：初始URL 列表．

Agent(初始URL 列表){

将初始URL 列表中的URL 放入URL 队列；

while(ERE队列不为空){

从URL 队列中取出一个URL ；

将URL 存入URLSeen ；

下载URL 指向的网页：

提取网页中含有的URL ；

for(每一个新发现的URL){

if(URL应由本Agent 负责){

if(URL不在URLSeen 中&&URL不在URL 队列中)

将URL 放入URL 队列： )else{

· 通过一定的Web 划分方法选择负责当前URL 的Agent ；

· 将URL 发送至此Agent ； } ) ) }

1．3广域网分布式Web 爬虫的优势和挑战

广域网分布式Web 爬虫与基于LAN 的分布式爬虫或称局域网爬虫相比具有诸多优势：

(1)可扩展性

可扩展性是局域网爬虫的致命缺点，也是提出广域网分布式爬虫的主要原因．首先，广域网系统能够容纳更多的计算资源，拥有更多的网络接入点．理论上，整体吞吐量可以无限扩展；局域网爬虫因其计算资源数量受到LAN 的限制，很难扩展到较大的规模，从而限制了系统整体吞吐量．其次，广域网系统是由若干个相对较小的机群甚至单机节点组成，这使得资源添加和系统维护都变得相对简单．如果能

够进一步利用分布在Intemet 上的个人计算资源，则维护开销将大为降低；相比之下，在LAN 中维护大规模机群的代价则非常昂贵，需要解决数据存储、系统互连、机架结构、电源、散热等诸多问题．

(2)多网络接入点

爬虫在抓取网页时，HTTP 请求和下载网页的过程需要占用系统网络接入点的大部分带宽．对基于LAN 的系统，随着机群规模的扩大，接入带宽将变为系统瓶颈．如果爬虫程序分布在不同的网络位置，就可以使用多个网络接入点，理论上可以获得相当于这些接入点加和的总带宽．并且随着网络接入点数量的增加，系统的总带宽也会相应增加，理论上带宽可以无限扩展．(31减少对Intemet 的网络负载 爬虫程序在发出HTTP 请求并下载网页时，大量数据报文的传播增加了Internet 的负载，在一定程度上影响了Intemet 的服务质量．如果能够实现就近抓取，即布置在不同地域的分布式爬虫仅负责抓取距离自己相对较近的网站，则广域网分布式爬虫可以将系统带给Internet 的网络负载控制在局部．而对于基于LAN 的爬虫，由于其 网络接入点单一，大量数据包要经过较长的路径才能到达目的地，从而给路径上的所有网络资源(如路由器、交换机、网关等) 带来压力． 广域网尤其是Intemet 环境比局域网要复杂得多，系统一旦架设到广域网环境就会受到诸多限制．如何有效利用广域网资源同时又能消除广域网环境的不利影响，是广域网分布式爬虫研究所面临的重大挑战．本文针对当前广域网分布式Web 爬虫的研究和实践，总结出这一领域的3个关键问题：

(1)Web划分：如何将抓取Web 这个巨大的任务切分成多份，交予系统中的多个Agent 执行．

(2)Agent协同：多个Agent 之间应该如何进行协同工作，如何进行互联与通信．

(3)Agent部署：如何利用现有硬件和网络资源构建广域网分布式爬虫系统．

这3个关键问题在广域网分布式Web 爬虫研究中的层次结构如图l 所示：最上层的Web 划分强调的是逻辑问题，相当于决策层；最下层的Agent 部署强调的是物理问题，它作为系统的基础是工程性很强的一层；Agent 协同则既涉及物理又涉及逻辑，包含了程序实现和网络环境分析等多方面的问题．

2 、Web 划分

系统中各个Agent 在抓取过程中会不断地发现新的URL ，而这些URL 中存在大量的重复．如果将这些新URL 直接交由发现它的Agent 抓取，那么将会引起多个Agent 下载相同的网页，从而引起重复工作，降低整体的网页抓取效率．因此，需要一种为各个Agent 分配URL 的策略，由此提出Web 划分的概念．

2．1 Web划分的定义

定义l(Web划分集合和Web 划分集合的分类) ．设分布式Web 爬虫由Ⅳ个Agent 组成，Web 上所有网页的集合

2．2 Web划分单元

Web划分单元的选取是实现W 曲划分时必须考虑的问题．Web

划分单元是Agent 在工作过程中所负责抓取的最小集合，凡是包含于划分单元的网页，全部由一个Agent 负责抓取．用于w 曲划分单元的某些属性的集合称为划分属性，用于指导对Web 划分单元的分类．这些属性可以来自URL 字符串本身。也可以来自与URL 相关的某些事物，如网站IP 地址、网页内容、第三方信息等．根据广域网环境下实验的经验，广域网分布式系统在进行任务划分时粒度必须适当地大，以保证各个节点具有较高的计算通信比，尽量降低信息交换引发的时间开销．Web 划分单元对应任务粒度的概念，因此这样的结论同样适用于广域网分布式爬虫．下面讨论两个典型的Web 划分单元(以下简称为单元) ，并对其划分属性及优缺点进行论述．

(1)链接(URL)

URL是Web 爬虫研究中最小的Web 划分单元，优点是简单、直观，缺点是粒度太细．由于Web 上存在的链

接比网站总数要多得多，对URL 进行分类的工作量是十分巨大的．与主机名相比，URL 所携带的划分属性比较

少。仅能显示文件类型等信息．

(2)主机(host)

以URL 中的主机名(即hostname ，比如URL ：http ：／／www ．sina ．corn ／index ．html 的主机名为www ．sina ．corn) 为 Web 划分单元，是大部分分布式Web 爬虫的首选．相对于以URL 为单元而言，本方法产生的跨分区链接较少．因为处于同一个主机的URL 必然会被分配到同一个划分集合中；而在以URL 为单元的情况下，这

些URL 可能会被分配到很多不同的Web 划分集合中，这样，主机内部的链接也变成了跨分区链接．对主机名的一种延伸是域名，由于一个域名下可能拥有若干主机，因此域名是一种粒度更大的Web 划分单元．主机所具有的划分属性主要有IP 地址、网站类型等。除了以上两种单元以外，由于RIRs(regional intemet registries)的存在，通过主机的IP 地址等信息还可以得到网站所在国家、地区及运营商等信息，给Web 划分单元提供了更多的可选方案。

2．3 Web划分策略

根据定义2，在系统中含有Ⅳ个Agent 的情况下，Web 划分的前提是找出Web 全集的一个大小为Ⅳ的子集(Web划分集合) 的集合．采用何种方法将所有Web 划分单元分类成Ⅳ个Web 划分集合，并实现其与Ⅳ个Agent 的一一映射。构成了分布式Web 爬虫的Web 划分策略．下面介绍目前已经提出的几种Web 划分策略，对其原理和优、缺点进行详细论述．

(1)基于随机哈希

基于随机哈希的方法是采用得最多的Web 划分方法．最早的分布式爬虫系统大多是建立在对在对URL 或主机名哈希的基础之上的．首先，这种方法非常容易计算，用于调度的系统开销较小；其次，由于哈希函数的随机性，保证了各个Agent 间负载均衡；另外，这种将字符串映射为随机数的方法非常易于与采用DHT 的P2P 系统集成，如UbiCrawler(并没有声称自己是P2P 系统，但是最早使用了类DHT 方法：consistent hashing，Apoidea 等。

基于哈希的方法遇到的最大问题是，结构简单的哈希值无法体现出主机所具有的类型、地理位置、网络距离等信息，也就无法利用这些属性提高分类质量。

(2)基于域名后缀及文件类型

有的爬虫根据主机或网站的域名后缀不同，将Web 划分单元分配到不同的Web 划分集合．比如，根据网站域名中诸如．net ，．org ，．corn ，．edu 这些表示组织性质的后缀进行分类；还可以根据URL 字符串中的文件类型如．html ，．rap3等进行分类．以上两种分类方法更加注重对网页内容的分类．SE4SEE 提出根据表示语言类型或国家、区域的域名后缀，如．cn ，jp ，．fr 等进行分类，这样不仅实现了按照网页内容分类，而且由于每种语言群体的地理分布基本都不相同，也部分地实现了按地理位置划分，为爬虫就近抓取创造了一定的条件．这种方法的优点是，Web 数据在抓取时就已经进行了初步的分类，为以后的数据分析工作奠定了比较好的基础．但它仍然存在诸多缺陷：首先，并非每个URL 或域名都遵守传统的后缀命名规范，如有的学校的域名就是．corn 而不是大家普遍认同的．edu ；样，也有很多．cn(中文) 后缀的网站其实含有大量英语内容；其次，由于各种类型的网站的数量或文件的数量分布不均，将造成系统中各个Agent 的负载不均，比如，按照语言类型分类，小语种网站的数量非常少，而拥有诸如．en ，．de 这类域名后缀的网站数量则非常大．跨越较大的地理范围和网络范围是广域网分布式系统天生的优势，可以利用这个优势实现Agent 对网站的就近抓取。即对每个网站由距离它