高性能网页抓取调度策略.docx
《高性能网页抓取调度策略.docx》由会员分享，可在线阅读，更多相关《高性能网页抓取调度策略.docx（13页珍藏版）》请在冰点文库上搜索。
高性能网页抓取调度策略
高性能网页抓取调度策略
FengyunCaoDongmingJiangJaswinderPalSingh
{fcao,dj,jps}@cs.princeton.edu
DepartmentofComputerScience,PrincetonUniversity
Princeton,NJ08540,USA
摘要
网络爬虫是搜索引擎、数据挖掘等互联网应用的重要组成部分。
对Web页面下载调度是爬虫的一个重要方面。
以前基于Web抓取的研究侧重于优化爬行速度和下载网页的质量。
虽然这两个指标是重要的，但若只考虑其中之一是不够的，也许会使整个抓取过程出现偏差。
本文探讨了抓取调度的设计准则，以平衡性能和质量为目的并优化全网抓取的效率。
我们设计了一个网络高效的调度框架，并用它来评估各种调度策略。
我们还定义了一个新的调度算法，将网络性能和网页质量纳入调度决策。
实际的实验清楚地证明了两级调度方案的有效性，以及新算法对于整体爬行效率的提高作用。
实验还表明，爬行调度设计总能根据对应用性质有充分的了解而进行优化。
1.引言
网络爬虫是搜索引擎，数据挖掘等互联网应用的重要组成部分。
递归下载网页入本地存储，如图1中的操作可以被简单地描述为以下四个步骤：
a.取一组种子URL作为首要任务的URL。
b.从URL集合中选取一个URL，并从网上下载页面。
c.提取网页中的超链接，如果URL符合要求，则将其添加到URL任务集合中。
d.重复步骤b和c，直到URL任务集合成为空或应用程序停止。
抓取调度策略就是要确定URL任务序列的顺序。
给定时间窗T，不同的调度策略在T之内将抓取到完全不同的页面集合。
图1.网络爬虫的运行模式。
（控制流由实线表示，数据流由虚线表示）。
由于万维网的爆炸式增长，抓取一个有效的哪怕是具有显著特点的页面也变得非常有挑战性：
各大搜索引擎抓取十亿网页的典型时间是一个多星期[14][15]；与此同时，大量的新的页面被创建，而许多已抓取的网页已经变更[2][9]。
因此，网络爬虫只能访问那些早期被调度的页面。
在本文中，我们定义一个网络爬虫的整体效率为有限的时间内抓取的页面总的内容。
基于上述原因，这个指标是非常重要的并具有普遍性。
为了实现整体效率，爬虫面临着两大挑战：
它应该以较高的速度下载网页，并且还选择性地优先抓取最有价值的网页。
我们将它们称为性能指标和质量指标。
这些指标大多数时候是被独立分开地研究的。
虽然这两个指标很重要，但若仅独立地考虑其中一方面则可能导致极大的偏差。
例如，若只考虑性能指标，则可能导致爬虫拥有良好的连接速度却只能抓取到大量无用网页，而一味考虑爬行质量则可能因为偶然的几个高质量但速度极低网页而阻塞整个进程。
这些情况从全局效率的角度来看都是不可接受的。
在本文中，我们将探讨网络抓取调度的设计准则，优化了全局抓取的效率。
在下一节，我们简要回顾一下网页检索相关的研究工作。
在第3节中，我们提出了一种两级调度架构。
在第4节中，我们定义了三种调度算法，分别表示广度优先调度、性能优先调度和质量优先调度。
我们还设计了一个新的全局策略，称为基于抓取能力调度，其同时考虑了性能和质量两方面的影响。
我们实现了一个两级调度策略的网络爬虫，并对其进行了实验。
在第5节，我们提出了实验结果和分析，证明了该算法在相应的度量下能有效提高抓取效率。
事实上，新策略的提出，比以往任何算法都更有效地提高了总体效率。
最后在第6节我们得出了结论并提出了未来的研究方向。
2.相关工作
关于Web抓取的文献大致可以分为两类：
各大搜索引擎[4][15]设计的可以在单位时间内下载大量的页面的高性能爬虫。
虽然形如PageRank[4][21]等网页排名网站对于搜索程序是非常重要的，但目前尚不清楚它们是否对搜索引擎的抓取有作用，以及如果有，是怎样的作用。
其他的研究工作主要集中在网页的调度方面（下载这些页面之前，他们通过在抓取任务列表中的网址表示），通过它们的质量排名来进行：
网页对于程序更有价值的排名较高，并且先于那些价值较低的网页被下载。
网页质量的定义通过特定应用程序的需求来计算。
在文献[6]中，聚焦爬虫寻求出相关的一组预定义主题的页面。
在文献[8]中，由超链接引用的网页被认为是重要的，并给予较高的排名。
其他网页的质量测量包括新鲜页[9][10]，以及用户定义的任意谓词[1]。
文献[11]研究了一个URL排序的多个并行的抓取过程。
虽然实验表明这些研究在早期对于下载高质量的网页非常有效，但目前还不清楚他们在时间限制下表现如何，以及是否结合了页面的质量优先等级来进一步提高抓取的全局效率。
事实上，许多实验只是在本地的Web页面集合进行了“虚拟抓取”的模拟，因此，我们无法知道这些算法在实际的应用中会有怎样的表现。
3.结构设计
在本节中，我们提出我们的调度框架设计。
我们首先回顾一下网络协议的功能，以便能够理解，对于调度策略来说，清晰地了解服务器状态和网络环境以度量网络开销是非常重要的。
基于这种认识，我们提出了同时对Web服务器（TCP连接）级和网页（具体网址）级进行网页抓取调度。
3.1.网络协议的启示
网络爬虫通过建立在TCP连接之上的HTTP协议下载网页。
传统的HTTP1.0协议有著名的性能问题[20]：
一个单独的TCP连接打开每个HTTP请求和关闭接收响应后，由于HTTP消息都比较小，网络流量的很大一部分是TCP管理报文。
另外，TCP连接在其缓慢的起步阶段始终运行，导致网络容量利用不足。
为了解决这些问题，HTTP1.1协议提供了两种性能优化技术：
一个是持久连接，它允许TCP连接在相同的客户机和服务器之间保持开启状态，第二个是流水线传输，其允许客户端接收应答之前发送更多的HTTP请求。
很明显，高性能的爬虫应利用HTTP1.1的优点来进行优化。
为了减少连接管理开销和慢启动的影响，抓取工具应该鼓励多个网页在一个TCP连接的批量下载。
下载网页的时间成本不仅应包括发送URL请求和接收来自服务器的响应所耗时间，也用于打开和关闭连接时——如果需要这样的操作——的时间。
因此，一个已经连接到Web服务器的URL，应当有比没有连接服务器的URL更快或“更低成本”的速度。
总之，对于爬虫调度性能的考虑应当基于TCP连接，而不是基于单个URL。
3.2.两级调度
图2.在两级调度中URL任务分为两个级别。
为了适应底层网络的性能特点，我们提出两个层次的新型调度架构：
调度是在两个URL级别和Web服务器级别上完成的。
在图2中，我们重新绘制在图1中的URL的任务调度循环，即对于已发现但尚未下载的进行排序，并指定在其Web服务器的相关URL网址队列。
反过来，Web服务器在服务器队列中对它们进行排名和分类。
URL队列和服务器队列都被作为优先级队列，为抓取策略提供排名参考。
我们将呈现四个这样的策略，并在下一节介绍两级排名算法。
调度工作流程如下：
爬虫在同一时间从多个Web服务器进行抓取，以实现网络和计算的并行性，同时打开的TCP连接的最大数目保持在一个系统特定的恒定水平。
当旧的连接关闭，爬虫打开全局排名第一的未连接服务器的新的连接，并从该服务器下载最靠前的网址。
对下载的网页进行分析，提取其URL进行排名并插入相应的URL队列。
URL队列更新还可能引发相应的Web服务器排名的更新。
为了避免与服务器之间进行交换开销过多的危险，服务器级调度在通过非抢占方式实现：
一个已经建立好的连接不会因为一个未建立的排名更高的连接而被关闭。
Web服务器通常允许一个连接内的不大于固定数量的多个Web页面的传输。
这个数量是由服务器配置参数决定的，这将在第5节进一步讨论。
爬虫在一次连接中抓取网页的数量实际上是由一个能平衡性能优化的配置参数决定的。
将这个参数设定为1意味着严格的URL排序和HTTP1.1性能优势的丧失。
在我们的研究中，我们让爬虫尽可能地下载服务器所允许的最大数量的网页，而这个参数的设定将是未来一项有趣的工作。
4.调度策略
在本节中，我们为四种优化指标不同的抓取策略定义了两级排序算法。
具体来说，这四种策略分别是：
广度优先抓取策略、性能优先策略、网页质量优先策略，以及有限时间内的网页质量总和优先策略。
4.1.广度优先调度
在广度优先调度中，按照网页的URL序列进行抓取。
因此，我们将URL队列和服务器队列都设为先进先出（FIFO）的方式。
广度优先策略没有明确的调度偏好，但能显示出良好的网页链接质量。
因此，我们把它作为一个有意义的研究基础。
4.2.性能优先调度
基于性能调度的目的是在单位时间内抓取尽可能多的网页。
抓取过程中优先考虑连接速度快的网页而不考虑网页质量。
一台Web服务器s通过下列算法来确定它的下一个TCP连接（一般地，我们假设它是服务器s的第i个连接）：
其中，P（s,i）是从服务器在第i个TCP连接下载的页面数，T（s,i）是下载它们的时间。
高排名的服务器可能会在短时间内提供大量的页面。
需要注意的是，为了避免Web服务器过载，爬虫程序对一个服务器在任何时候都不会打开多于一个连接。
显然，P（s,i）和R（s,i）只能在实际完成下载后才能确定。
为了达到目的我们需要预先估计它的值。
如果服务器的性能和网络条件不断变化，这将是具有挑战性的。
我们定义
P（s,i）被设置为两个数中的较小值：
ReqestsPerConnection（s,i）是服务器s在一个TCP连接内的URL请求数，它由之前在此服务器连接中的情况而估计出来。
对于一个新的服务器，它被设为一个默认值50。
TaskURLs（s,i）是服务器s中URL队列的长度。
T（s,i）由打开和关闭连接（2*ConnectionTime（s,i））以及传输P（s,i）个Web页面的总时间构成。
p是一个为支持HTTP1.1的服务器设置的保留参数。
在我们的实验中，p被设置为了1.2。
ConnectionTime和ResponseTime被预估为：
其中ConnectionTime（s,i-1）和ResponseTime（s,i-1）是上一次的估计值，MeasureConnectionTime和MeasureResponseTime是新的观测值。
我们设置一个参数α为0.8以平滑估计。
在基于性能的调度中，服务器队列由每个服务器的R（s,i）进行排序，而URL在每个URL队列排序为FIFO方式。
4.3.质量优先调度
基于质量优先的抓取策略将网页严格地按照其质量的好坏进行排序。
为了使实验具有简单性和一般性，我们假设网页质量由一个专有的程序进行评估并且这个过程是透明的。
我们还假设一个网页质量在其URL被发现并且可用后就在调度阶段保持不变。
尽管随着爬虫程序获取到的数据增多，网页的质量可能会出现变化，但这种变化与调度策略呈正交关系。
在本文中，这种变化不做讨论。
在基于质量的抓取策略中，URL序列根据其质量来排序，Web服务器则根据其质量最好的URL来进行排名：
通过这种方式，爬虫程序总是能将质量最好的网页最先抓取下来。
4.4.基于抓取能力调度
最后，我们设计了一种算法，在排序调度中能够综合考虑质量和性能两个元素，我们定义一个服务器的“抓取能力”为：
其中，
P（s,i）和T（s,i）已经在4.2.节中定义了。
C（s,i）反映了爬虫程序期望在平均时间内从服务器s抓取到的网页的质量和。
高“抓取能力”能够表明服务器能够快速地提供高质量的网页。
需要注意的是，本文仅使用简单的代数和来表示网页的质量总和。
关于这种质量总和的其它定义，将是未来一项有趣的工作。
在基于抓取能力的调度策略中，服务器按照其“抓取能力”进行排名，URL按照其质量进行排序。
5.实验与评估
在本节中，我们给出两级调度算法的实现，以及基于第4节定义的四种调度策略的爬虫实验。
5.1.实验设置
5.1.1.程序模式
一个高性能爬虫可以同时从多个Web服务器抓取数据。
有两种备选方案来实现这种并行性：
一种是单线程事件驱动模型（STED），如[4]中使用的那样；另一种是[15]中用到的线程模型。
我们选择STED模式，以避免上下文切换和线程同步带来的开销，其缺点是可能导致更复杂的程序结构。
爬虫程序通过一个单线程的事件循环来实现。
异步的网络事件通过UNIX的选择系统进行注册并通过回调函数来处理。
为了避免被充分证明过的DNS查找瓶颈，我们添加了另一个线程来启用异步DNS查找，以将主机名解析为IP地址。
对下载的网页进行分析并对提取出的URL进行排名，将其插入到URL队列，然后页面被丢弃。
保存最近使用过的URL的hash值，使得同一网页不会在短时间内再次下载。
5.1.2.硬件环境
我们的爬虫程序基于C语言编写，运行于有512MRAM和100Mbps以太网接入的奔腾III700MHz的PC上。
我们实验的以太网以100Mbps的网关接入校园网，通过45Mbps的网关[13]连接到互联网。
我们的一些网络协议管理功能通过由万维网联盟（W3C）提供的LibWWW库的协议模块[22]修改而来。
5.1.3.数据集
为了得到基于各种调度策略可比较的结果，爬虫实验需要具备以下要求：
（1）所有爬虫都应该访问一组相同的页面。
（2）每个页面都应该有相同的质量。
（3）在每个爬虫运行期间网络流量和Web服务器的负载应该是可比的。
各种测试之后，我们发现，大学网站服务器以较少的动态生成和频繁更改的页面，相对大多数商业网站而言对爬虫程序更稳定，更友好。
我们选择了一所大学来自另一个海岸的大型大学Web域——Stanford.edu，作为我们的测试集。
域中有500多个Web服务器以及超过30,000个网页。
我们知道，与典型商业Web爬虫相比，我们的测试集会显得工作量比较小；但是，其允许重复的实验以及调度算法的详细特征分析。
由于本文提出的调度方案是比较新的，我们相信，这样详细的分析和深入的了解是非常重要的。
使我们的实验朝着更大规模发展是未来一个重要的工作。
我们还检查了可能会影响到调度效果的各种Web服务器的性能。
例如，我们收集每一个由Web服务器的HTTP连接支持的URL请求的数量配置。
斯坦福的500个服务器的数量配置分布见于图3（a）：
服务器中的24%在单个连接中仅支持一个请求，这意味着它们正在运行HTTP1.0；服务器中的66%在单个连接中支持100个请求，这是HTTP1.1的典型配置。
此分布表明，大量的Web服务器的使用HTTP1.1协议，并预计该比例在未来继续增长。
因此，利用HTTP1.1的性能优化技术将是非常重要的。
在图3（b）中，我们给出了在雅虎网站目录中列出的3500个Web服务器的相同配置。
其分布非常类似于图3（a）。
从这个角度来看，我们可以认为Stanford.edu域也将是大型爬虫调度策略应用的一个典型代表。
图3.Web服务器在单个连接中支持的URL请求的数量比例
5.2.广度优先调度性能分析
5.2.1.广度优先调度在测试集上的应用
为了更好地理解爬虫的性能表现以及网络条件的影响，我们首先在不同协议配置下实现广度优先调度策略。
特别地，我们使用了HTTP1.0，HTTP1.1单模式（具有持续连接但没有流水线技术），和HTTP1.1流水线模式（具有两个永久连接和流水线技术）。
我们也使爬虫在用一时间打开TCP连接的数量保持变化。
结果见于图4。
在相同的并行性下，在HTTP1.1上的抓取速度是HTTP1.0上的两倍。
流水线技术能够进一步提高性能，但没有预期中的那样大。
对详细的跟踪数据进行分析发现，其原因是相对服务器响应请求所耗的时间，HTTP的请求连接的往返时延较小。
这其中可能包括访问硬盘的时间，以及提供其它连接的时间。
图4还显示了爬虫的吞吐率随着打开的TCP连接数的增加而提高。
但是，这种提高在连接数超过96后便没有了。
图4.广度优先调度在各种配置上的性能
5.2.2.快速服务器上的综合爬虫测试
为了全面了解爬虫行为，我们设计了一个在斯坦福的20个“快速”服务器上的综合测试。
其响应时间皆在100毫秒之内，且在一个TCP连接内可以响应100个URL请求。
爬虫程序仅仅在这些快速服务器上进行抓取，以避免低速服务器可能产生的影响会拉低整体的抓取性能。
在快速服务器上的抓取实验结果见于图5。
相对于图4中的96个连接，在图5（a）中仅使用了14个TCP连接即达到了爬虫的最大吞吐量8.4Mbps。
图5（b）显示了图5（a）中每一个条形的时间分解。
总的抓取时间被分为三个部分：
系统时间是操作系统内核所占用的CPU时间，用户时间是用户程序所占用的CPU时间，网络时间是CPU在空闲时等待异步的I/O操作所花费的时间。
显然，CPU空闲时间随着连接数量的增多而减少。
在具有16个TCP连接时，CPU变得饱和。
在这之后，更多的TCP连接只会因增加了更多的管理开销和内存空间而降低了性能。
此外，我们发现CPU饱和会降低爬虫的响应能力——大量来自服务器的响应被丢弃，甚至一些连接因为超时而被Web服务器切断。
总之，综合研究告诉我们，爬虫性能的瓶颈在于CPU，且增加TCP连接数不是总能提高性能。
相反，与第5.2.1节比较表明，不同的任务集可以导致完全不同的抓取性能。
图5.综合测试的性能分析
5.3.调度策略评估
接下来，我们给出了在第4节中提到的四种调度策略的抓取结果。
为了避免CPU饱和，爬虫保持在用一时间打开连接数不超过64个。
评估指标包括：
（1）抓取速度，即一段时间内下载的页面数量。
（2）网页质量，即所下载页面的质量总和。
（3）整体效率，即一段时间内下载页面的质量总和。
如前面提到的那样，我们相信指标（3）是最具实用性的，指标
（1）和指标
（2）也可以根据各种实际应用被关注。
关于网页质量的定义，因实际应用不同而有PageRank[21]和齐普夫分布实验[3][18]两种。
正如在4.3节所述，网页的质量是预先计算好且在抓取过程中保持不变的。
5.3.1.基于PageRank的网页质量
PageRank是一种流行的网页质量评估[4][8][19][21]。
谷歌使用PageRank来对用户查询的搜索结果进行排名。
文献[8]表明，PageRank也可以作为一个很好的抓取指标来发现“重要”的网址。
一个网页的PageRank是由所有包含指向这个网页URL的网页的PageRank加权和来递归定义的。
具体而言，令u是一个网页。
然后令Fu是u指向的页面集合，Bu是指向u的页面集合。
令Cu=|Fu|为u的链接数量，且令0假设Web上一共有T个页面。
则u的PageRankR被定义为：
四种调度策略的抓取结果如图6所示：
图6.基于PageRank质量评估的调度性能
如图6（a）所示，性能优先调度和基于抓取能力的调度比其他两种策略具有更高的吞吐率，尤其是在抓取早期阶段。
具体来说，性能优先调度策略在一半的时间点时已经比广度优先调度策略多下载了50%的页面。
这表明这两种调度策略会优先选择速度快的服务器进行抓取。
与性能优先调度策略相比，基于抓取能力的调度受限于同时要考虑网页质量的排名。
前面已经提到，一个爬虫程序不可能抓取到Web上的所有页面，因此可以一直被认为是运行在“早期阶段”。
因此，提高一个爬虫在早期阶段的性能事实上可以提高其有限生命周期内的性能。
有趣的是，在图6（b）显示的网页质量评估中，质量优先调度和基于抓取能力调度相对于其它两种策略表现出了大规模的领先。
它们在一开始优先选择高质量的网页，并且在一半的网页被下载后就已获得了80%的网页质量总和。
对数据进行更详细的研究，我们发现其提高的意义可以归因于PageRank的一个特殊的功能：
研究[7][16]发现，一个网页的参照页面来自同一服务器的几率比来自不同服务器的高。
我们称其为超链接的“服务器局部性”。
当我们使用像PageRank这样的基于引用页质量的方法时，在同一服务器上的网页往往会获得类似的质量值。
因此，质量优先调度策略为了积极地寻找高质量的网页，往往会在一个服务器内调度多个高质量网页，也就是说这些网页会在同一个连接内被下载。
与此同时，鉴于网页质量的偏态分布，对具有更好质量的服务器的调度就变得非常重要。
图6（c）表示，基于抓取能力调度在综合指标下整体效率表现最佳，质量优先调度紧随其后。
这两种调度都能在少于抓取所有页面总时间的30%内获得高于80%的页面质量总和。
性能优先调度也能在一半的时间时有效地领先广度优先调度大约50%。
图6的结果表明调度策略对于改善一个爬虫程序的优化指标来说影响非常大。
然而，我们还发现，改善的幅度与PageRank特殊的“服务器局部性”属性有关。
为了了解在没有这种属性的情况下调度策略会如何影响网页的质量指标，我们进行另一个页面质量评估实验。
5.3.2.基于齐普夫分布的网页质量
齐普夫定律是一个经典的观测一个事件（P）发生频率的方法，可用于确定一个由发生频率决定的排名（i），是一个以a为指数的幂律函数：
最近的一些研究（[3,17]）发现齐普夫分布特征的Web访问模式对互联网应用有极大的意义。
在这个实验中，我们对所有网页随机分配质量值，使整体质量分布服从齐普夫分布（a被设置为1）。
和PageRank不同，以这种方式分配的页面质量是相互独立的，也不再具有“服务器局部性”。
图7显示了基于这种质量度量的抓取结果。
正如预期的那样，由于性能的度量与网页质量度量是正交的，图7（a）的结果与图6（a）相类似。
而在图7（b）中，与直觉相反的是，基于抓取能力调度甚至比质量优先调度表现更佳。
其原因是当质量优先调度在抓取质量最佳的页面时，与5.3.1节描述的不同，同一连接下载的其它页面不再表现出较高的质量。
相比之下，基于抓取能力调度会将根据一个连接下载的页面质量总和来对服务器排名，因而能优先调度具有许多高质量页面的服务器。
图7（c）显示了基于抓取能力调度在总体效率方面再一次领先其它的调度策略。
它在三分之一的时间内获得了60%的网页质量和，而这个数字在一半的时间内达到了80%。
性能或质量优先的调度策略也略微比广度优先调度表现更好。
由于“服务器局部性”的消失，质量优先调度失去了它相对于性能优先调度的优势。
由于基于抓取能力调度在提高整体效率方面具有稳定的成效，我们认为它在平衡抓取质量和性能方面是一个很好的抓取策略。
图7.基于齐普夫分布质量的抓取效率
6.总结与展望
在本文中，我们研究了如何调度网页抓取以获得更好的性能和质量。
基于对基础网络性能特点的认识，我们提出了一种新的调度框架，能够同时基于Web服务器级别和单个URL级别进行抓取调度。
该框架是灵活的，可以适应各种调度策略。
然后，我们定义了几种两级排序算法，分别为广度优先调度、性能优先调度、质量优先调度。
我们同时定义了一种新的“基于抓取能力”的调度策略，其结合了性能和质量两个方面来进行考虑。
我们实现了一个两级调度的爬虫，并对四种调度策略进行了评估。
实验结果表明，所有的智能调度策略，都能使爬虫有效地基于它们的优化目标得到提升，尤其是在爬虫的早期阶段。
在这些策略中，基于抓取能力调度能够领先于其它策略而在有限时间内抓取到更多的高质量页面。
因此，我们认为它在平衡抓取质量和性能方面是一个很好的抓取策略。
在我们的实验中，我们发现抓取行为可能受特定应用的因素影响，例如网络状态或网页质量的定义。
因此，抓取调度策略的设计总是可以根据对实际应用的充分了解而进行优化。
在我们的研究中还有一些额外的有趣现象。
在第4节中，我们提出一种估计Web服务器性能和网络条件的方式。
对关于计算开销与估计精度之间的权衡进行进一步研究将是一项有趣的工作。
在基于抓取能力调度算法中，我们用代数求和的方式计算网页质量的总和。
而在实际应用中页面的质量是彼此相关的，这可能无法很好地反
升级会员 