高性能網(wǎng)頁抓取調(diào)度策略

1、高性能網(wǎng)頁抓取調(diào)度策略Fengyun Cao Dongming Jiang Jaswinder Pal Singhfcao, dj, Department of Computer Science, Princeton UniversityPrinceton, NJ 08540, USA摘要網(wǎng)絡(luò)爬蟲是搜索引擎、數(shù)據(jù)挖掘等互聯(lián)網(wǎng)應(yīng)用的重要組成部分。對Web頁面下載調(diào)度是爬蟲的一個重要方面。以前基于Web抓取的研究側(cè)重于優(yōu)化爬行速度和下載網(wǎng)頁的質(zhì)量。雖然這兩個指標(biāo)是重要的，但若只考慮其中之一是不夠的，也許會使整個抓取過程出現(xiàn)偏差。本文探討了抓取調(diào)度的設(shè)計準(zhǔn)則，以

2、平衡性能和質(zhì)量為目的并優(yōu)化全網(wǎng)抓取的效率。我們設(shè)計了一個網(wǎng)絡(luò)高效的調(diào)度框架，并用它來評估各種調(diào)度策略。我們還定義了一個新的調(diào)度算法，將網(wǎng)絡(luò)性能和網(wǎng)頁質(zhì)量納入調(diào)度決策。實際的實驗清楚地證明了兩級調(diào)度方案的有效性，以及新算法對于整體爬行效率的提高作用。實驗還表明，爬行調(diào)度設(shè)計總能根據(jù)對應(yīng)用性質(zhì)有充分的了解而進行優(yōu)化。1. 引言網(wǎng)絡(luò)爬蟲是搜索引擎，數(shù)據(jù)挖掘等互聯(lián)網(wǎng)應(yīng)用的重要組成部分。遞歸下載網(wǎng)頁入本地存儲，如圖1中的操作可以被簡單地描述為以下四個步驟：a. 取一組種子URL作為首要任務(wù)的URL。b. 從URL集合中選取一個URL，并從網(wǎng)上下載頁面。c. 提取網(wǎng)頁中的超鏈接，如果URL符合要求，則將其

3、添加到URL任務(wù)集合中。d. 重復(fù)步驟b和c，直到URL任務(wù)集合成為空或應(yīng)用程序停止。抓取調(diào)度策略就是要確定URL任務(wù)序列的順序。給定時間窗T，不同的調(diào)度策略在T之內(nèi)將抓取到完全不同的頁面集合。圖1. 網(wǎng)絡(luò)爬蟲的運行模式。（控制流由實線表示，數(shù)據(jù)流由虛線表示）。由于萬維網(wǎng)的爆炸式增長，抓取一個有效的哪怕是具有顯著特點的頁面也變得非常有挑戰(zhàn)性：各大搜索引擎抓取十億網(wǎng)頁的典型時間是一個多星期1415；與此同時，大量的新的頁面被創(chuàng)建，而許多已抓取的網(wǎng)頁已經(jīng)變更29。因此，網(wǎng)絡(luò)爬蟲只能訪問那些早期被調(diào)度的頁面。在本文中，我們定義一個網(wǎng)絡(luò)爬蟲的整體效率為有限的時間內(nèi)抓取的頁面總的內(nèi)容?；谏鲜鲈?，這個

4、指標(biāo)是非常重要的并具有普遍性。為了實現(xiàn)整體效率，爬蟲面臨著兩大挑戰(zhàn)：它應(yīng)該以較高的速度下載網(wǎng)頁，并且還選擇性地優(yōu)先抓取最有價值的網(wǎng)頁。我們將它們稱為性能指標(biāo)和質(zhì)量指標(biāo)。這些指標(biāo)大多數(shù)時候是被獨立分開地研究的。雖然這兩個指標(biāo)很重要，但若僅獨立地考慮其中一方面則可能導(dǎo)致極大的偏差。例如，若只考慮性能指標(biāo)，則可能導(dǎo)致爬蟲擁有良好的連接速度卻只能抓取到大量無用網(wǎng)頁，而一味考慮爬行質(zhì)量則可能因為偶然的幾個高質(zhì)量但速度極低網(wǎng)頁而阻塞整個進程。這些情況從全局效率的角度來看都是不可接受的。在本文中，我們將探討網(wǎng)絡(luò)抓取調(diào)度的設(shè)計準(zhǔn)則，優(yōu)化了全局抓取的效率。在下一節(jié)，我們簡要回顧一下網(wǎng)頁檢索相關(guān)的研究工作。在第3

5、節(jié)中，我們提出了一種兩級調(diào)度架構(gòu)。在第4節(jié)中，我們定義了三種調(diào)度算法，分別表示廣度優(yōu)先調(diào)度、性能優(yōu)先調(diào)度和質(zhì)量優(yōu)先調(diào)度。我們還設(shè)計了一個新的全局策略，稱為基于抓取能力調(diào)度，其同時考慮了性能和質(zhì)量兩方面的影響。我們實現(xiàn)了一個兩級調(diào)度策略的網(wǎng)絡(luò)爬蟲，并對其進行了實驗。在第5節(jié)，我們提出了實驗結(jié)果和分析，證明了該算法在相應(yīng)的度量下能有效提高抓取效率。事實上，新策略的提出，比以往任何算法都更有效地提高了總體效率。最后在第6節(jié)我們得出了結(jié)論并提出了未來的研究方向。2. 相關(guān)工作關(guān)于Web抓取的文獻大致可以分為兩類：各大搜索引擎4 15設(shè)計的可以在單位時間內(nèi)下載大量的頁面的高性能爬蟲。雖然形如PageRa

6、nk 4 21等網(wǎng)頁排名網(wǎng)站對于搜索程序是非常重要的，但目前尚不清楚它們是否對搜索引擎的抓取有作用，以及如果有，是怎樣的作用。其他的研究工作主要集中在網(wǎng)頁的調(diào)度方面（下載這些頁面之前，他們通過在抓取任務(wù)列表中的網(wǎng)址表示），通過它們的質(zhì)量排名來進行：網(wǎng)頁對于程序更有價值的排名較高，并且先于那些價值較低的網(wǎng)頁被下載。網(wǎng)頁質(zhì)量的定義通過特定應(yīng)用程序的需求來計算。在文獻6中，聚焦爬蟲尋求出相關(guān)的一組預(yù)定義主題的頁面。在文獻8中，由超鏈接引用的網(wǎng)頁被認(rèn)為是重要的，并給予較高的排名。其他網(wǎng)頁的質(zhì)量測量包括新鮮頁9 10，以及用戶定義的任意謂詞1。文獻11研究了一個URL排序的多個并行的抓取過程。雖然實驗表

7、明這些研究在早期對于下載高質(zhì)量的網(wǎng)頁非常有效，但目前還不清楚他們在時間限制下表現(xiàn)如何，以及是否結(jié)合了頁面的質(zhì)量優(yōu)先等級來進一步提高抓取的全局效率。事實上，許多實驗只是在本地的Web頁面集合進行了“虛擬抓取”的模擬，因此，我們無法知道這些算法在實際的應(yīng)用中會有怎樣的表現(xiàn)。3. 結(jié)構(gòu)設(shè)計在本節(jié)中，我們提出我們的調(diào)度框架設(shè)計。我們首先回顧一下網(wǎng)絡(luò)協(xié)議的功能，以便能夠理解，對于調(diào)度策略來說，清晰地了解服務(wù)器狀態(tài)和網(wǎng)絡(luò)環(huán)境以度量網(wǎng)絡(luò)開銷是非常重要的。基于這種認(rèn)識，我們提出了同時對Web服務(wù)器（TCP連接）級和網(wǎng)頁（具體網(wǎng)址）級進行網(wǎng)頁抓取調(diào)度。3.1. 網(wǎng)絡(luò)協(xié)議的啟示網(wǎng)絡(luò)爬蟲通過建立在TCP連接之上的H

8、TTP協(xié)議下載網(wǎng)頁。傳統(tǒng)的HTTP 1.0協(xié)議有著名的性能問題20：一個單獨的TCP連接打開每個HTTP請求和關(guān)閉接收響應(yīng)后，由于HTTP消息都比較小，網(wǎng)絡(luò)流量的很大一部分是TCP管理報文。另外，TCP連接在其緩慢的起步階段始終運行，導(dǎo)致網(wǎng)絡(luò)容量利用不足。為了解決這些問題，HTTP1.1協(xié)議提供了兩種性能優(yōu)化技術(shù)：一個是持久連接，它允許TCP連接在相同的客戶機和服務(wù)器之間保持開啟狀態(tài)，第二個是流水線傳輸，其允許客戶端接收應(yīng)答之前發(fā)送更多的HTTP請求。很明顯，高性能的爬蟲應(yīng)利用HTTP1.1的優(yōu)點來進行優(yōu)化。為了減少連接管理開銷和慢啟動的影響，抓取工具應(yīng)該鼓勵多個網(wǎng)頁在一個TCP連接的批量下載

9、。下載網(wǎng)頁的時間成本不僅應(yīng)包括發(fā)送URL請求和接收來自服務(wù)器的響應(yīng)所耗時間，也用于打開和關(guān)閉連接時如果需要這樣的操作的時間。因此，一個已經(jīng)連接到Web服務(wù)器的URL，應(yīng)當(dāng)有比沒有連接服務(wù)器的URL更快或“更低成本”的速度?？傊?，對于爬蟲調(diào)度性能的考慮應(yīng)當(dāng)基于TCP連接，而不是基于單個URL。3.2. 兩級調(diào)度圖2. 在兩級調(diào)度中URL任務(wù)分為兩個級別。為了適應(yīng)底層網(wǎng)絡(luò)的性能特點，我們提出兩個層次的新型調(diào)度架構(gòu)：調(diào)度是在兩個URL級別和Web服務(wù)器級別上完成的。在圖2中，我們重新繪制在圖1中的URL的任務(wù)調(diào)度循環(huán)，即對于已發(fā)現(xiàn)但尚未下載的進行排序，并指定在其Web服務(wù)器的相關(guān)URL網(wǎng)址隊列。反過

10、來，Web服務(wù)器在服務(wù)器隊列中對它們進行排名和分類。URL隊列和服務(wù)器隊列都被作為優(yōu)先級隊列，為抓取策略提供排名參考。我們將呈現(xiàn)四個這樣的策略，并在下一節(jié)介紹兩級排名算法。調(diào)度工作流程如下：爬蟲在同一時間從多個Web服務(wù)器進行抓取，以實現(xiàn)網(wǎng)絡(luò)和計算的并行性，同時打開的TCP連接的最大數(shù)目保持在一個系統(tǒng)特定的恒定水平。當(dāng)舊的連接關(guān)閉，爬蟲打開全局排名第一的未連接服務(wù)器的新的連接，并從該服務(wù)器下載最靠前的網(wǎng)址。對下載的網(wǎng)頁進行分析，提取其URL進行排名并插入相應(yīng)的URL隊列。URL隊列更新還可能引發(fā)相應(yīng)的Web服務(wù)器排名的更新。為了避免與服務(wù)器之間進行交換開銷過多的危險，服務(wù)器級調(diào)度在通過非搶占方

11、式實現(xiàn)：一個已經(jīng)建立好的連接不會因為一個未建立的排名更高的連接而被關(guān)閉。Web服務(wù)器通常允許一個連接內(nèi)的不大于固定數(shù)量的多個Web頁面的傳輸。這個數(shù)量是由服務(wù)器配置參數(shù)決定的，這將在第5節(jié)進一步討論。爬蟲在一次連接中抓取網(wǎng)頁的數(shù)量實際上是由一個能平衡性能優(yōu)化的配置參數(shù)決定的。將這個參數(shù)設(shè)定為1意味著嚴(yán)格的URL排序和HTTP 1.1性能優(yōu)勢的喪失。在我們的研究中，我們讓爬蟲盡可能地下載服務(wù)器所允許 的最大數(shù)量的網(wǎng)頁，而這個參數(shù)的設(shè)定將是未來一項有趣的工作。4. 調(diào)度策略在本節(jié)中，我們?yōu)樗姆N優(yōu)化指標(biāo)不同的抓取策略定義了兩級排序算法。具體來說，這四種策略分別是：廣度優(yōu)先抓取策略、性能優(yōu)先策略、網(wǎng)頁

12、質(zhì)量優(yōu)先策略，以及有限時間內(nèi)的網(wǎng)頁質(zhì)量總和優(yōu)先策略。4.1. 廣度優(yōu)先調(diào)度在廣度優(yōu)先調(diào)度中，按照網(wǎng)頁的URL序列進行抓取。因此，我們將URL隊列和服務(wù)器隊列都設(shè)為先進先出（FIFO）的方式。廣度優(yōu)先策略沒有明確的調(diào)度偏好，但能顯示出良好的網(wǎng)頁鏈接質(zhì)量。因此，我們把它作為一個有意義的研究基礎(chǔ)。4.2. 性能優(yōu)先調(diào)度基于性能調(diào)度的目的是在單位時間內(nèi)抓取盡可能多的網(wǎng)頁。抓取過程中優(yōu)先考慮連接速度快的網(wǎng)頁而不考慮網(wǎng)頁質(zhì)量。一臺Web服務(wù)器s通過下列算法來確定它的下一個TCP連接（一般地，我們假設(shè)它是服務(wù)器s的第i個連接）：其中，P(s, i)是從服務(wù)器在第i個TCP連接下載的頁面數(shù)，T(s, i)是下

13、載它們的時間。高排名的服務(wù)器可能會在短時間內(nèi)提供大量的頁面。需要注意的是，為了避免Web服務(wù)器過載，爬蟲程序?qū)σ粋€服務(wù)器在任何時候都不會打開多于一個連接。顯然， P(s, i)和R(s, i)只能在實際完成下載后才能確定。為了達(dá)到目的我們需要預(yù)先估計它的值。如果服務(wù)器的性能和網(wǎng)絡(luò)條件不斷變化，這將是具有挑戰(zhàn)性的。我們定義P(s, i)被設(shè)置為兩個數(shù)中的較小值：ReqestsPerConnection(s, i)是服務(wù)器s在一個TCP連接內(nèi)的URL請求數(shù)，它由之前在此服務(wù)器連接中的情況而估計出來。對于一個新的服務(wù)器，它被設(shè)為一個默認(rèn)值50。TaskURLs(s, i)是服務(wù)器s中URL隊列的長度

14、。T(s, i) 由打開和關(guān)閉連接(2 * ConnectionTime(s, i)以及傳輸P(s, i)個Web頁面的總時間構(gòu)成。p是一個為支持HTTP1.1的服務(wù)器設(shè)置的保留參數(shù)。在我們的實驗中，p被設(shè)置為了1.2。 ConnectionTime 和ResponseTime被預(yù)估為：其中ConnectionTime(s, i-1)和ResponseTime(s, i-1)是上一次的估計值，MeasureConnectionTime和MeasureResponseTime是新的觀測值。我們設(shè)置一個參數(shù)為0.8 以平滑估計。在基于性能的調(diào)度中，服務(wù)器隊列由每個服務(wù)器的R(s, i)進行排序，而

15、URL在每個URL隊列排序為FIFO方式。4.3. 質(zhì)量優(yōu)先調(diào)度基于質(zhì)量優(yōu)先的抓取策略將網(wǎng)頁嚴(yán)格地按照其質(zhì)量的好壞進行排序。為了使實驗具有簡單性和一般性，我們假設(shè)網(wǎng)頁質(zhì)量由一個專有的程序進行評估并且這個過程是透明的。我們還假設(shè)一個網(wǎng)頁質(zhì)量在其URL被發(fā)現(xiàn)并且可用后就在調(diào)度階段保持不變。盡管隨著爬蟲程序獲取到的數(shù)據(jù)增多，網(wǎng)頁的質(zhì)量可能會出現(xiàn)變化，但這種變化與調(diào)度策略呈正交關(guān)系。在本文中，這種變化不做討論。在基于質(zhì)量的抓取策略中，URL序列根據(jù)其質(zhì)量來排序，Web服務(wù)器則根據(jù)其質(zhì)量最好的URL來進行排名：通過這種方式，爬蟲程序總是能將質(zhì)量最好的網(wǎng)頁最先抓取下來。4.4. 基于抓取能力調(diào)度最后，我們

16、設(shè)計了一種算法，在排序調(diào)度中能夠綜合考慮質(zhì)量和性能兩個元素，我們定義一個服務(wù)器的“抓取能力”為：其中，P(s, i) 和 T(s, i) 已經(jīng)在4.2.節(jié)中定義了。C(s, i)反映了爬蟲程序期望在平均時間內(nèi)從服務(wù)器s抓取到的網(wǎng)頁的質(zhì)量和。高“抓取能力”能夠表明服務(wù)器能夠快速地提供高質(zhì)量的網(wǎng)頁。需要注意的是，本文僅使用簡單的代數(shù)和來表示網(wǎng)頁的質(zhì)量總和。關(guān)于這種質(zhì)量總和的其它定義，將是未來一項有趣的工作。在基于抓取能力的調(diào)度策略中，服務(wù)器按照其“抓取能力”進行排名，URL按照其質(zhì)量進行排序。5. 實驗與評估在本節(jié)中，我們給出兩級調(diào)度算法的實現(xiàn)，以及基于第4節(jié)定義的四種調(diào)度策略的爬蟲實驗。5.1.

17、 實驗設(shè)置5.1.1. 程序模式一個高性能爬蟲可以同時從多個Web服務(wù)器抓取數(shù)據(jù)。有兩種備選方案來實現(xiàn)這種并行性：一種是單線程事件驅(qū)動模型（STED），如4中使用的那樣；另一種是15中用到的線程模型。我們選擇STED模式，以避免上下文切換和線程同步帶來的開銷，其缺點是可能導(dǎo)致更復(fù)雜的程序結(jié)構(gòu)。爬蟲程序通過一個單線程的事件循環(huán)來實現(xiàn)。異步的網(wǎng)絡(luò)事件通過UNIX的選擇系統(tǒng)進行注冊并通過回調(diào)函數(shù)來處理。為了避免被充分證明過的DNS查找瓶頸，我們添加了另一個線程來啟用異步DNS查找，以將主機名解析為IP地址。對下載的網(wǎng)頁進行分析并對提取出的URL進行排名，將其插入到URL隊列，然后頁面被丟棄。保存最近

18、使用過的URL的hash值，使得同一網(wǎng)頁不會在短時間內(nèi)再次下載。5.1.2. 硬件環(huán)境我們的爬蟲程序基于C語言編寫，運行于有512M RAM和100Mbps以太網(wǎng)接入的奔騰III700 MHz的PC上。我們實驗的以太網(wǎng)以100Mbps的網(wǎng)關(guān)接入校園網(wǎng)，通過45 Mbps的網(wǎng)關(guān)13連接到互聯(lián)網(wǎng)。我們的一些網(wǎng)絡(luò)協(xié)議管理功能通過由萬維網(wǎng)聯(lián)盟（W3C）提供的LibWWW庫的協(xié)議模塊22修改而來。5.1.3. 數(shù)據(jù)集為了得到基于各種調(diào)度策略可比較的結(jié)果，爬蟲實驗需要具備以下要求：(1) 所有爬蟲都應(yīng)該訪問一組相同的頁面。(2) 每個頁面都應(yīng)該有相同的質(zhì)量。(3) 在每個爬蟲運行期間網(wǎng)絡(luò)流量和Web服務(wù)器

19、的負(fù)載應(yīng)該是可比的。各種測試之后，我們發(fā)現(xiàn)，大學(xué)網(wǎng)站服務(wù)器以較少的動態(tài)生成和頻繁更改的頁面，相對大多數(shù)商業(yè)網(wǎng)站而言對爬蟲程序更穩(wěn)定，更友好。我們選擇了一所大學(xué)來自另一個海岸的大型大學(xué)Web域S，作為我們的測試集。域中有500多個Web服務(wù)器以及超過30,000個網(wǎng)頁。我們知道，與典型商業(yè)Web爬蟲相比，我們的測試集會顯得工作量比較?。坏牵湓试S重復(fù)的實驗以及調(diào)度算法的詳細(xì)特征分析。由于本文提出的調(diào)度方案是比較新的，我們相信，這樣詳細(xì)的分析和深入的了解是非常重要的。使我們的實驗朝著更大規(guī)模發(fā)展是未來一個重要的工作。我們還檢查了可能會影響到調(diào)度效果的各種Web服務(wù)器的性能。

20、例如，我們收集每一個由Web服務(wù)器的HTTP連接支持的URL請求的數(shù)量配置。斯坦福的500個服務(wù)器的數(shù)量配置分布見于圖3(a)：服務(wù)器中的24%在單個連接中僅支持一個請求，這意味著它們正在運行HTTP 1.0；服務(wù)器中的66%在單個連接中支持100個請求，這是HTTP 1.1的典型配置。此分布表明，大量的Web服務(wù)器的使用HTTP 1.1協(xié)議，并預(yù)計該比例在未來繼續(xù)增長。因此，利用HTTP 1.1的性能優(yōu)化技術(shù)將是非常重要的。在圖3(b)中，我們給出了在雅虎網(wǎng)站目錄中列出的3500個 Web服務(wù)器的相同配置。其分布非常類似于圖3(a)。從這個角度來看，我們可以認(rèn)為S域也將

21、是大型爬蟲調(diào)度策略應(yīng)用的一個典型代表。圖3. Web服務(wù)器在單個連接中支持的URL請求的數(shù)量比例5.2. 廣度優(yōu)先調(diào)度性能分析5.2.1. 廣度優(yōu)先調(diào)度在測試集上的應(yīng)用為了更好地理解爬蟲的性能表現(xiàn)以及網(wǎng)絡(luò)條件的影響，我們首先在不同協(xié)議配置下實現(xiàn)廣度優(yōu)先調(diào)度策略。特別地，我們使用了HTTP 1.0，HTTP 1.1單模式（具有持續(xù)連接但沒有流水線技術(shù)），和HTTP 1.1流水線模式（具有兩個永久連接和流水線技術(shù)）。我們也使爬蟲在用一時間打開TCP連接的數(shù)量保持變化。結(jié)果見于圖4。在相同的并行性下，在HTTP 1.1上的抓取速度是HTTP 1.0上的兩倍。流水線技術(shù)能夠進一步提高性能，但沒有預(yù)期中

22、的那樣大。對詳細(xì)的跟蹤數(shù)據(jù)進行分析發(fā)現(xiàn)，其原因是相對服務(wù)器響應(yīng)請求所耗的時間，HTTP的請求連接的往返時延較小。這其中可能包括訪問硬盤的時間，以及提供其它連接的時間。圖4還顯示了爬蟲的吞吐率隨著打開的TCP連接數(shù)的增加而提高。但是，這種提高在連接數(shù)超過96后便沒有了。圖4. 廣度優(yōu)先調(diào)度在各種配置上的性能5.2.2. 快速服務(wù)器上的綜合爬蟲測試為了全面了解爬蟲行為，我們設(shè)計了一個在斯坦福的20個“快速”服務(wù)器上的綜合測試。其響應(yīng)時間皆在100毫秒之內(nèi)，且在一個TCP連接內(nèi)可以響應(yīng)100個URL請求。爬蟲程序僅僅在這些快速服務(wù)器上進行抓取，以避免低速服務(wù)器可能產(chǎn)生的影響會拉低整體的抓取性能。在快

23、速服務(wù)器上的抓取實驗結(jié)果見于圖5。相對于圖4中的96個連接，在圖5(a)中僅使用了14個TCP連接即達(dá)到了爬蟲的最大吞吐量8.4 Mbps。圖5(b)顯示了圖5(a)中每一個條形的時間分解?？偟淖トr間被分為三個部分：系統(tǒng)時間是操作系統(tǒng)內(nèi)核所占用的CPU時間，用戶時間是用戶程序所占用的CPU時間，網(wǎng)絡(luò)時間是CPU在空閑時等待異步的I/O操作所花費的時間。顯然，CPU空閑時間隨著連接數(shù)量的增多而減少。在具有16個TCP連接時，CPU變得飽和。在這之后，更多的TCP連接只會因增加了更多的管理開銷和內(nèi)存空間而降低了性能。此外，我們發(fā)現(xiàn)CPU飽和會降低爬蟲的響應(yīng)能力大量來自服務(wù)器的響應(yīng)被丟棄，甚至一些

24、連接因為超時而被Web服務(wù)器切斷。總之，綜合研究告訴我們，爬蟲性能的瓶頸在于CPU，且增加TCP連接數(shù)不是總能提高性能。相反，與第5.2.1節(jié)比較表明，不同的任務(wù)集可以導(dǎo)致完全不同的抓取性能。圖5. 綜合測試的性能分析5.3. 調(diào)度策略評估接下來，我們給出了在第4節(jié)中提到的四種調(diào)度策略的抓取結(jié)果。為了避免CPU飽和，爬蟲保持在用一時間打開連接數(shù)不超過64個。評估指標(biāo)包括：(1) 抓取速度，即一段時間內(nèi)下載的頁面數(shù)量。(2) 網(wǎng)頁質(zhì)量，即所下載頁面的質(zhì)量總和。(3) 整體效率，即一段時間內(nèi)下載頁面的質(zhì)量總和。如前面提到的那樣，我們相信指標(biāo)(3)是最具實用性的，指標(biāo)(1)和指標(biāo)(2)也可以根據(jù)各種

25、實際應(yīng)用被關(guān)注。關(guān)于網(wǎng)頁質(zhì)量的定義，因?qū)嶋H應(yīng)用不同而有PageRank21和齊普夫分布實驗3 18兩種。正如在4.3節(jié)所述，網(wǎng)頁的質(zhì)量是預(yù)先計算好且在抓取過程中保持不變的。5.3.1. 基于PageRank的網(wǎng)頁質(zhì)量PageRank是一種流行的網(wǎng)頁質(zhì)量評估4 8 1921。谷歌使用PageRank來對用戶查詢的搜索結(jié)果進行排名。文獻8表明，PageRank也可以作為一個很好的抓取指標(biāo)來發(fā)現(xiàn)“重要”的網(wǎng)址。一個網(wǎng)頁的PageRank是由所有包含指向這個網(wǎng)頁URL的網(wǎng)頁的PageRank加權(quán)和來遞歸定義的。具體而言，令u是一個網(wǎng)頁。然后令Fu是u指向的頁面集合，Bu是指向u的頁面集合。令Cu =|

26、Fu| 為u的鏈接數(shù)量，且令0 < d < 1為一個阻尼系數(shù)。假設(shè)Web上一共有T個頁面。則u的PageRank R被定義為：四種調(diào)度策略的抓取結(jié)果如圖6所示：圖6. 基于PageRank質(zhì)量評估的調(diào)度性能如圖6(a)所示，性能優(yōu)先調(diào)度和基于抓取能力的調(diào)度比其他兩種策略具有更高的吞吐率，尤其是在抓取早期階段。具體來說，性能優(yōu)先調(diào)度策略在一半的時間點時已經(jīng)比廣度優(yōu)先調(diào)度策略多下載了50%的頁面。這表明這兩種調(diào)度策略會優(yōu)先選擇速度快的服務(wù)器進行抓取。與性能優(yōu)先調(diào)度策略相比，基于抓取能力的調(diào)度受限于同時要考慮網(wǎng)頁質(zhì)量的排名。前面已經(jīng)提到，一個爬蟲程序不可能抓取到Web上的所有頁面，因此可

27、以一直被認(rèn)為是運行在“早期階段”。因此，提高一個爬蟲在早期階段的性能事實上可以提高其有限生命周期內(nèi)的性能。有趣的是，在圖6(b)顯示的網(wǎng)頁質(zhì)量評估中，質(zhì)量優(yōu)先調(diào)度和基于抓取能力調(diào)度相對于其它兩種策略表現(xiàn)出了大規(guī)模的領(lǐng)先。它們在一開始優(yōu)先選擇高質(zhì)量的網(wǎng)頁，并且在一半的網(wǎng)頁被下載后就已獲得了80%的網(wǎng)頁質(zhì)量總和。對數(shù)據(jù)進行更詳細(xì)的研究，我們發(fā)現(xiàn)其提高的意義可以歸因于PageRank的一個特殊的功能：研究7 16發(fā)現(xiàn)，一個網(wǎng)頁的參照頁面來自同一服務(wù)器的幾率比來自不同服務(wù)器的高。我們稱其為超鏈接的“服務(wù)器局部性”。當(dāng)我們使用像PageRank這樣的基于引用頁質(zhì)量的方法時，在同一服務(wù)器上的網(wǎng)頁往往會獲得

28、類似的質(zhì)量值。因此，質(zhì)量優(yōu)先調(diào)度策略為了積極地尋找高質(zhì)量的網(wǎng)頁，往往會在一個服務(wù)器內(nèi)調(diào)度多個高質(zhì)量網(wǎng)頁，也就是說這些網(wǎng)頁會在同一個連接內(nèi)被下載。與此同時，鑒于網(wǎng)頁質(zhì)量的偏態(tài)分布，對具有更好質(zhì)量的服務(wù)器的調(diào)度就變得非常重要。圖6(c)表示，基于抓取能力調(diào)度在綜合指標(biāo)下整體效率表現(xiàn)最佳，質(zhì)量優(yōu)先調(diào)度緊隨其后。這兩種調(diào)度都能在少于抓取所有頁面總時間的30%內(nèi)獲得高于80%的頁面質(zhì)量總和。性能優(yōu)先調(diào)度也能在一半的時間時有效地領(lǐng)先廣度優(yōu)先調(diào)度大約50%。圖6的結(jié)果表明調(diào)度策略對于改善一個爬蟲程序的優(yōu)化指標(biāo)來說影響非常大。然而，我們還發(fā)現(xiàn)，改善的幅度與PageRank特殊的“服務(wù)器局部性”屬性有關(guān)。為了了

29、解在沒有這種屬性的情況下調(diào)度策略會如何影響網(wǎng)頁的質(zhì)量指標(biāo)，我們進行另一個頁面質(zhì)量評估實驗。5.3.2. 基于齊普夫分布的網(wǎng)頁質(zhì)量齊普夫定律是一個經(jīng)典的觀測一個事件(P)發(fā)生頻率的方法，可用于確定一個由發(fā)生頻率決定的排名(i)，是一個以a為指數(shù)的冪律函數(shù)：最近的一些研究(3,17)發(fā)現(xiàn)齊普夫分布特征的Web訪問模式對互聯(lián)網(wǎng)應(yīng)用有極大的意義。在這個實驗中，我們對所有網(wǎng)頁隨機分配質(zhì)量值，使整體質(zhì)量分布服從齊普夫分布（a被設(shè)置為1）。和PageRank不同，以這種方式分配的頁面質(zhì)量是相互獨立的，也不再具有“服務(wù)器局部性”。圖7顯示了基于這種質(zhì)量度量的抓取結(jié)果。正如預(yù)期的那樣，由于性能的度量與網(wǎng)頁質(zhì)量度

30、量是正交的，圖7(a)的結(jié)果與圖6(a)相類似。而在圖7(b)中，與直覺相反的是，基于抓取能力調(diào)度甚至比質(zhì)量優(yōu)先調(diào)度表現(xiàn)更佳。其原因是當(dāng)質(zhì)量優(yōu)先調(diào)度在抓取質(zhì)量最佳的頁面時，與5.3.1節(jié)描述的不同，同一連接下載的其它頁面不再表現(xiàn)出較高的質(zhì)量。相比之下，基于抓取能力調(diào)度會將根據(jù)一個連接下載的頁面質(zhì)量總和來對服務(wù)器排名，因而能優(yōu)先調(diào)度具有許多高質(zhì)量頁面的服務(wù)器。圖7(c)顯示了基于抓取能力調(diào)度在總體效率方面再一次領(lǐng)先其它的調(diào)度策略。它在三分之一的時間內(nèi)獲得了60%的網(wǎng)頁質(zhì)量和，而這個數(shù)字在一半的時間內(nèi)達(dá)到了80%。性能或質(zhì)量優(yōu)先的調(diào)度策略也略微比廣度優(yōu)先調(diào)度表現(xiàn)更好。由于“服務(wù)器局部性”的消失，質(zhì)

31、量優(yōu)先調(diào)度失去了它相對于性能優(yōu)先調(diào)度的優(yōu)勢。由于基于抓取能力調(diào)度在提高整體效率方面具有穩(wěn)定的成效，我們認(rèn)為它在平衡抓取質(zhì)量和性能方面是一個很好的抓取策略。圖7. 基于齊普夫分布質(zhì)量的抓取效率6. 總結(jié)與展望在本文中，我們研究了如何調(diào)度網(wǎng)頁抓取以獲得更好的性能和質(zhì)量?；趯A(chǔ)網(wǎng)絡(luò)性能特點的認(rèn)識，我們提出了一種新的調(diào)度框架，能夠同時基于Web服務(wù)器級別和單個URL級別進行抓取調(diào)度。該框架是靈活的，可以適應(yīng)各種調(diào)度策略。然后，我們定義了幾種兩級排序算法，分別為廣度優(yōu)先調(diào)度、性能優(yōu)先調(diào)度、質(zhì)量優(yōu)先調(diào)度。我們同時定義了一種新的“基于抓取能力”的調(diào)度策略，其結(jié)合了性能和質(zhì)量兩個方面來進行考慮。我們實現(xiàn)了

32、一個兩級調(diào)度的爬蟲，并對四種調(diào)度策略進行了評估。實驗結(jié)果表明，所有的智能調(diào)度策略，都能使爬蟲有效地基于它們的優(yōu)化目標(biāo)得到提升，尤其是在爬蟲的早期階段。在這些策略中，基于抓取能力調(diào)度能夠領(lǐng)先于其它策略而在有限時間內(nèi)抓取到更多的高質(zhì)量頁面。因此，我們認(rèn)為它在平衡抓取質(zhì)量和性能方面是一個很好的抓取策略。在我們的實驗中，我們發(fā)現(xiàn)抓取行為可能受特定應(yīng)用的因素影響，例如網(wǎng)絡(luò)狀態(tài)或網(wǎng)頁質(zhì)量的定義。因此，抓取調(diào)度策略的設(shè)計總是可以根據(jù)對實際應(yīng)用的充分了解而進行優(yōu)化。在我們的研究中還有一些額外的有趣現(xiàn)象。在第4節(jié)中，我們提出一種估計Web服務(wù)器性能和網(wǎng)絡(luò)條件的方式。對關(guān)于計算開銷與估計精度之間的權(quán)衡進行進一步研

33、究將是一項有趣的工作。在基于抓取能力調(diào)度算法中，我們用代數(shù)求和的方式計算網(wǎng)頁質(zhì)量的總和。而在實際應(yīng)用中頁面的質(zhì)量是彼此相關(guān)的，這可能無法很好地反映一組頁面集合的質(zhì)量總和。這種實際應(yīng)用的特性對于爬取策略具有何種意義以及如何利用好它們值得進一步研究。我們也在推動我們的研究能具有更大的規(guī)模。參考文獻1 C. Aggarwal, F. Al-Garawi, P. Yu. Intelligent crawling on the World Wide Web with arbitrary predicates. In Proceedings of the 9th International World W

34、ide Web Conference (WWW9), 2000 2 A. Arasu, J. Cho, L. Molina, et al. Searching the Web. In ACM Transactions on Internet Technology, 1(1), June 2001 3 L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching, and Zipf-like distributions: Evidence, and Implications, In Proceedings of IEEE

35、 INFOCOM, 1999. 4 S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the 7th World Wide Web Conference (WWW7), 1998. 5 M. Burner. Crawling towards Eternity: Building an archive of the World Wide Web. Web Techniques Magazine, 2(5), May 1997 6 S. Chakra

36、barti and M. Berg, B. Dom. Focused crawling: A new approach to topic-specific web resource discovery. In Proceedings of the 8th International World Wide Web Conference (WWW8), 1999 7 S. Chakrabarti et al. Mining the Web's link structure. In IEEE Computer, 32(8):60-67, August 1999. 8 J. Cho, H. G

37、arcia-Molina, and L. Page. Efficient crawling through URL ordering. In Proceedings of the 7th International World Wide Web Conference (WWW7), 1998 9 J. Cho, H. Molina. The evolution of the Web and implications for an incremental crawler. In Proceedings of 26th International Conference on Very Large

38、Databases (VLDB), 2000 10 J. Cho, H. Garcia-Molina. Synchronizing a database to improve freshness. In Proceedings of the ACM SIGMOD Conference, 2000 11 J. Cho and H. Garcia-Molina. Parallel crawlers. In Proceedings of the Eleventh International World Wide Web Conference, 2002. 12 M. Diligenti, F. M. Coetzee, S. Lawrence, C. L. Giles, M. Gori, Focused crawling using context graphs, Proceedings