高性能网页抓取调度策略

高性能网页抓取调度策略FengyunCaoDongmingJiangJaswinderPalSingh{fcao,dj,jps}@DepartmentofComputerScience,PrincetonUniversityPrinceton,NJ08540,USA摘要Web页面下载调度是爬虫的Web用。实验还表明，爬行调度设计总能根据对应用性质有充分的了解而进行优化。引言网络爬虫是搜索引擎，数据挖掘等互联网应用的重要组成部分。递归下载网页入本地存储，如图1中的操作可以被简单地描述为以下四个步骤：取一组种子URL作为首要任务的。URL集合中选取一个URL，并从网上下载页面。提取网页中的超链接，如果URL符合要求，则将其添加到URL任务集合中。重复步骤bc，直到URL任务集合成为空或应用程序停止。抓取调度策略就是要确定URLT取到完全不同的页面集合。图1.网络爬虫的运行模式。（控制流由实线表示，数据流由虚线表示。由于万维网的爆炸式增长，抓取一个有效的哪怕是具有显著特点的页面也变得非常有挑战性：[14][15][2][9]。因此，网络爬虫只能访问那些早期被调度的页面。指标。这些指标大多数时候是被独立分开地研究的。都是不可接受的。在本文中，我们将探讨网络抓取调度的设计准则，优化了全局抓取的效率。在下一节，我们简34我们定义了三种调度算法，分别表示广度优先调度、性能优先调度和质量优先调度。我们还设计了一个新的全局策略，称为基于抓取能力调度，其同时考虑了性能和质量两方面的影响。我们实现了一个两级调度策略的网络爬虫，并对其进行了实验。在第5节，我们提出了实验结果和分析，证明了该算法在相应的度量下能有效提高抓取效率。事实上，新策略的提出，比以往任何算法都更有效地6节我们得出了结论并提出了未来的研究方向。相关工作关于Web抓取的文献大致可以分为两类：各大搜索引擎[4][15]设计的可以在单位时间内下载大量的页面的高性能爬虫。虽然形如PageRank[4]等网页排名网站对于搜索程序是非常重要的的抓取有作用，以及如果有，是怎样的作用。其他的研究工作主要集中在网页的调度方面（的网址表示，通过它们的质量排名来进行：网页对于程序更有价值的排名较高，并且先于那些价[6]中，聚焦爬虫寻[8][9][10][1]研究了一个URL排序的多个并行的抓取过程。虽然实验表明这些研究在早期对于下载高质量的网页非常Web“的模拟，因此，我们无法知道这些算法在实际的应用中会有怎样的表现。结构设计识，我们提出了同时对Web服务器（TCP连接）级和网页（具体网址）级进行网页抓取调度。网络协议的启示网络爬虫通过建立在TCP连接之上的HTTP协议下载网页。传统的HTTP1.0协议有著名的性能问题[20]：一个单独的TCP连接打开每个HTTP请求和关闭接收响应后，由于HTTP消息都比较小，网络流量的很大一部分是TCPHTTP1.1它允许TCPHTTP请求。HTTP1.1TCP送URL——如果需要这样的操作——的时间。因此，一个已经连接到Web服务器的URL，应当有比没有连接服务器的URL更快或“”的速度。总之，对于爬虫调度性能的考虑应当基于TCP连接，而不是基于单个两级调度图2.在两级调度中URL任务分为两个级别。为了适应底层网络的性能特点，我们提出两个层次的新型调度架构：调度是在两个URL级别Web21URL已发现但尚未下载的进行排序，并指定在其Web服务器的相关URL服务URLWeb同时打开的TCPURLURLURLWeb服务器排名的更新。为了避免与服务器之间进行交换开销过多的危险，服务器级调度在通过非抢占方式实现：一个已经建立好的连接不会因为一个未建立的排名更高的连接而被关闭。Web服务器通常允许一个连接内的不大于固定数量的多个Web5节进一步讨论。爬虫在一次连接中抓取网页的数量实际上是由一个能平衡性能优化的配置参数决定的。将这个参数设定为1意味着严格的URL排序和HTTP1.1性能参数的设定将是未来一项有趣的工作。调度策略优先策略。广度优先调度在广度优先调度中，按照网页的URL序列进行抓取。因此，我们将URL队列和服务器队列都设为先进先出量。因此，我们把它作为一个有意义的研究基础。性能优先调度基于性能调度的目的是在单位时间内抓取尽可能多的网页。抓取过程中优先考虑连接速度快的网页而不考虑网页质量。一台Webs通过下列算法来确定它的下一个TCP连接（的第i个连接：其中，P(s,i)i个TCPWeb一个服务器在任何时候都不会打开多于一个连接。i)和R(s,i)如果服务器的性能和网络条件不断变化，这将是具有挑战性的。我们定义P(s,i)被设置为两个数中的较小值：ReqestsPerConnection(s,i)s在一个TCP连接内的URL50。TaskURLs(s,s中URL队列的长度。T(s,i)(2*ConnectionTime(s,i))P(s,i)Webp是一个为支持HTTP1.1的服务器设置的保留参数。在我们的实验中，p被设置为了1.2ConnectionTimeResponseTime被预估为：其中ConnectionTime(s,i-1)和ResponseTime(s,i-1)是上一次的估计值，MeasureConnectionTimeMeasureResponseTime是新的观测值。我们设置一个参数0.8以平滑估计。在基于性能的调度中，服务器队列由每个服务器的R(s,i)进行排序，而URL在每个URL排序为FIFO方式。质量优先调度页质量在其URL被发现并且可用后就在调度阶段保持不变服务器则根据其质量最好的URL来进行排名：通过这种方式，爬虫程序总是能将质量最好的网页最先抓取下来。基于抓取能力调度最后，我们设计了一种算法，在排序调度中能够综合考虑质量和性能两个元素，我们定义一个服务器的“抓取能力”为：其中，P(s,i)和T(s,i)已经在4.2.节中定义了。C(s,i)反映了爬虫程序期望在平均时间内从服务器s“”能够质量总和。关于这种质量总和的其它定义，将是未来一项有趣的工作。在基于抓取能力的调度策略中，服务器按照其“抓取能力”进行排名，URL按照其质量进行排序。实验与评估在本节中，我们给出两级调度算法的实现，以及基于第4节定义的四种调度策略的爬虫实验。实验设置程序模式一个高性能爬虫可以同时从多个Web种是单线程事件驱动模型STE，如[4[15中用到的线程模型。我们选择STED程序通过一个单线程的事件循环来实现。异步的网络事件通过UNIX的选择系统进行注册并通过回调函数来处理。为了避免被充分证明过的DNS查找瓶颈，我们添加了另一个线程来启用异步DNS查找，以将主机名解析为IP地址。对下载的网页进行分析并对提取出的URLURL保存最近使用过的URLhash值，使得同一网页不会在短时间内再次下载。硬件环境我们的爬虫程序基于C512MRAM100Mbps以太网接入的奔腾III700MHz的PC上。我们实验的以太网以100Mbps45Mbps[13]连接到互联网。我们的一些网络协议管理功能通过由万维网联盟提供的LibWWW[22]修改而来。数据集为了得到基于各种调度策略可比较的结果，爬虫实验需要具备以下要求：所有爬虫都应该访问一组相同的页面。每个页面都应该有相同的质量。在每个爬虫运行期间网络流量和Web服务器的负载应该是可比的。Web域——S500Web30,000个网页。我们知道，与典型商业Web及调度算法的详细特征分析。由于本文提出的调度方案是比较新的，我们相信，这样详细的分析和深入的了解是非常重要的。使我们的实验朝着更大规模发展是未来一个重要的工作。我们还检查了可能会影响到调度效果的各种WebHTTPURL500个服务器的数量配置分布见于图3(a)：服务器中的24%在单个连接中仅支持一个请求，这意味着它们正在运行HTTP1.0；服务器中66%100个请求，这是HTTP1.1的典型配置。此分布表明，大量的Web服务器的使用HTTP1.1协议，并预计该比例在未来继续增长。因此，利用HTTP1.1的性能优化技术将3(b)3500个Web服务器的相同配置。其分布非常类似于图3(a)。从这个角度来看，我们可以认为S域也将是大型爬虫调度策略应用的一个典型代表。图3.Web服务器在单个连接中支持的URL请求的数量比例广度优先调度性能分析广度优先调度在测试集上的应用HTTP1.HTTP1.1（具有持续连接但没有流水线技术，HTTP1.1（具有两个永久连接和流水线技术TCP连接的数量保持变化。4。在相同的并行性下，在HTTP1.1上的抓取速度是HTTP1.0上的两倍。流水线技术能够进一步提高性能，但没有预期中的那样大。对详细的跟踪数据进行分析发现，其原因是相的请求连接的往返时延较小。这其中可能包括访问硬盘的时4还显示了爬虫的吞吐率随着打开的TCP96后便没有了。图4.广度优先调度在各种配置上的性能快速服务器上的综合爬虫测试20个“100毫秒之内，且在一个TCP100URL请求。爬虫程序仅仅在这些快。4965(a)14个TCP连接即达到了爬虫的最大吞吐量8.4Mbps。图5(b)显示了图5(a)操作系统内核所占用的CPUCPUCPU在空闲时等待异步的I/O空闲时间随着连接数量的增多而减少。在具有16个TCP变得饱和。在这之后，更多的TCP连接只会因增加了更多的管理开销和内CPU——大量来自服务器的响应被丢弃，甚至一些连接因为超时而被Web服务器切断。TCP5.2.1节比较表明，不同的任务集可以导致完全不同的抓取性能。

图5.综合测试的性能分析4CPU64个。评估指标包括：抓取速度，即一段时间内下载的页面数量。网页质量，即所下载页面的质量总和。整体效率，即一段时间内下载页面的质量总和。如前面提到的那样，我们相信指标(3)是最具实用性的，指标(1)和指标(2)也可以根据各种实际应用被关注。关于网页质量的定义，因实际应用不同而有PageRank[21][3][18]4.3节所述，网页的质量是预先计算好且在抓取过程中保持不变的。PageRank的网页质量PageRank[4][8][19][21]。谷歌使用PageRank[8]表明，PageRank“”的网址。PageRank是由所有包含指向这个网页URLPageRank加权和来递归定义u u uFuuuC=|Fu u u0<d<WebTu的PageRankR被定义为：四种调度策略的抓取结果如图6所示：图6.基于PageRank质量评估的调度性能如图6(a)所示，性能优先调度和基于抓取能力的调度比其他两种策略具有更高的吞吐率，尤其是在抓取早期阶段。具体来说，性能优先调度策略在一半的时间点时已经比广度优先调度策略多下载了50%的页面。这表明这两种调度策略会优先选择速度快的服务器进行抓取。与性能优先调度策略相比，基于抓取能力的调度受限于同时要考虑网页质量的排名。前面已经提到，一个爬虫程序不可能抓取到Web上的所有页面，因此可以一直被认为是运行在“早期阶段”。因此，提高一个爬虫在早期阶段的性能事实上可以提高其有限生命周期内的性能。有趣的是，在图6(b)显示的网页质量评估中，质量优先调度和基于抓取能力调度相对于其它两就已获得了80%的网页质量总和。对数据进行更详细的研究，我们发现其提高的意义可以归因于PageRank[7][16]PageRank这样的基于引用页常重要。图6(c)表示，基于抓取能力调度在综合指标下整体效率表现最佳，质量优先调度紧随其后。这两种调度都能在少于抓取所有页面总时间的30%内获得高于80%的页面质量总和。性能优先调度也能在一半的时间时有效地领先广度优先调度大约50%。图6PageRank基于齐普夫分布的网页质量排名(i)a为指数的幂律函数：([3,17])发现齐普夫分布特征的Weba被设置为1PageRank“。图7是正交的，图7(a)的结果与图6(a)相类似。而在图7(b)中，与直觉相反的是，基于抓取能力调度甚至比质量优先调度表现更佳。其原因是当质量优先调度在抓取质量最佳的页面时，与5.3.1节描述一个连接下载的页面质量总和来对服务器排名，因而能优先调度具有许多高质量页面的服务器。图7(c)时间内获得了60%的网页质量和，而这个数字在一半的时间内达到了80%。性能或质量优先的调度”的消失，质量优先调度失去了它相对于性能优先调度的优势。由于基于抓取能力调度在提高整体效率方面具有稳定的成效，我们认为它在平衡抓取质量和性能方面是一个很好的抓取策略。

图7.基于齐普夫分布质量的抓取效率的认识，我们提出了一种新的调度框架，能够同时基于Web服务器级别和单个URL级别进行抓取“的调度策略，在我们的实验中，我们发现抓取行为可能受特定应用的因素影响，例如网络状态或网页质量的定义。因此，抓取调度策略的设计总是可以根据对实际应用的充分了解而进行优化。4Web服务器性能和模。参考文献C.Aggarwal,F.Al-Garawi,P.IntelligentcrawlingontheWorldWideWebwitharbitrarypredicates.InProceedingsofthe9thInternationalWorldWideWebConferenceA.Arasu,J.Cho,L.Molina,etal.SearchingtheWeb.InACMTransactionsonInternet1(1),June2001L.Breslau,P.Cao,L.Fan, G.Phillips,andS.Shenker.Webcaching,andZipf-likedistributions:Evidence,andImplications,InProceedingsofIEEE1999.S.BrinandL.Page.Theanatomyofalarge-scalehypertextualwebsearchengine.In ofthe7thWorldWideWebConference1998.M.Burner.CrawlingtowardsEternity:BuildinganarchiveoftheWorldWideWeb.TechniquesMagazine,2(5),May1997S.ChakrabartiandM.Berg,B.Dom.Focusedcrawling:Anewapproachtotopic-specificresourcediscovery.InProceedingsofthe8thInternationalWorldWideWebConference(WWW8),1999S.Chakrabartietal.MiningtheWeb'slinkstructure.InIEEEComputer,32(8):60-67,August1999.J.Cho,H.Garcia-Molina,andL.Page.EfficientcrawlingthroughURLordering.InProceedingsofthe7thInternationalWorldWideWebConference1998J.Cho,H.Molina.TheevolutionoftheWebandimplicationsforanincrementalcrawler.InProceedingsof26thInternationalConferenceonVeryLargeDatabases2000J.Cho,H.Garcia-Molina.Synchronizingadatabasetoimprovefreshness.InProceedingsoftheACMSIGMOD2000J.ChoandH.Garcia-Molina.Parallelcrawlers.InProceedingsoftheEleventhInternationalWorldWideWeb2002.M.Diligenti,F.M.Coetzee,S.Lawrence,C.L.Giles,M.Gori,Focusedcrawlingusingcontextgraphs,ProceedingsofInternationalConferenceonLargeDatabases(VLDB),2000,pp.527-534GlobalInternetServiceatPrincetonUniversity,/internet.htmlGoogleInc.pressrelease:“Googlelaunchesworld’slargestsearchengine.”June26,2000.Availableat/press/pressrel/pressrelease26.htmlA.Heydon,M.Najork.Mercator:Ascalable,extensibleWebcrawler.InProceed