廣域網(wǎng)分布式Web 爬蟲滕千紅(湖工，管院，1010831119）摘要：分析了廣域網(wǎng)分布式Web 爬蟲相對于局域網(wǎng)爬蟲的諸多優(yōu)勢，提出了廣域網(wǎng)分布式Web 爬蟲的3個核心問題：Web 劃分、Agent

廣域網(wǎng)分布式Web 爬蟲

滕千紅

(湖工，管院，1010831119）

摘要：分析了廣域網(wǎng)分布式Web 爬蟲相對于局域網(wǎng)爬蟲的諸多優(yōu)勢，提出了廣域網(wǎng)分布式Web 爬蟲的3個核心問題：Web 劃分、Agent 協(xié)同和Agent 部署周繞這3個問題，對目前學術(shù)界和商業(yè)界出現(xiàn)的多種實現(xiàn)方案和策略進行了全面的綜述，深入討論了研究中遇到的問題與挑戰(zhàn)，并論述了廣域網(wǎng)分布式Web 爬蟲的評價模型．最后，對未來的研究方向進行了總結(jié)。

關(guān)鍵詞：搜索引擎；廣域網(wǎng)分布式爬蟲；Web 劃分；Agent 協(xié)同；Agent 部屬。

搜索引擎作為互聯(lián)網(wǎng)上一種有效的信息獲取渠道，與電子郵件、即時通信并稱為互聯(lián)網(wǎng)三大基礎(chǔ)應用。在人們的日常生活中發(fā)揮著重要的作用．然而，互聯(lián)網(wǎng)的飛速發(fā)展使搜索引擎面臨巨大的挑戰(zhàn)．2008年1月發(fā)布的《第21次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告》顯示，中國網(wǎng)站數(shù)量已達150萬個，比去年同期增長了66萬個，增長率達到78．4％：中國總網(wǎng)頁數(shù)為84．7億個，年增長率達到89．4％；網(wǎng)站總字節(jié)數(shù)已經(jīng)達到198 348GB．按照目前的統(tǒng)計數(shù)字，假設(shè)搜索引擎爬蟲系統(tǒng)的網(wǎng)絡(luò)接入總帶寬為lOOMb ／s ，即使這些帶寬被完全利用，僅下載中國的網(wǎng)頁就需要近200天．如此巨大的數(shù)據(jù)量，使得對網(wǎng)頁內(nèi)容和鏈接關(guān)系的處理必須由多機并行完成。分布式Web 爬蟲是

由多個可并發(fā)獲取Web 信息的Agent 構(gòu)成的Web 爬蟲系統(tǒng)，每個Agent 運行于不同的計算資源之上，這些資源或集中部署在同一個局域網(wǎng)(10cal area network，簡稱LAN) 內(nèi)部，或分布在廣域l 網(wǎng)(wide area network。簡稱WAN) 的不同地理位置和網(wǎng)絡(luò)位置，每個Agent 以多進程或多線程方式通過并發(fā)保持多個TCP 鏈接獲取Web 信息．部署于LAN 上的分布式Web 爬蟲受到帶寬等因素的制約，已經(jīng)不能對Web 進行快速而有效的抓?。趶V域網(wǎng)的分布式爬蟲實現(xiàn)方案具有多點接入總帶寬較高、對Internet 負載較小、容易實現(xiàn)就近高效抓取以及可擴展性強等優(yōu)點，已經(jīng)成為學術(shù)界、商業(yè)界和開源社區(qū)爬蟲系統(tǒng)實現(xiàn)的優(yōu)選方案。廣域網(wǎng)分布式爬蟲融合了分布式系統(tǒng)、并行計算及網(wǎng)絡(luò)測量等主題，具有很強的應用價值與理論研究意義。

1、引言

在分布式Web 爬蟲領(lǐng)域，商業(yè)界與學術(shù)界各自為戰(zhàn)，許多優(yōu)秀的實現(xiàn)方法不是源自于學術(shù)界，而是來自于一些公司．出于商業(yè)因素的考慮，公司成果一般不通過論文公開發(fā)表；而學術(shù)界的研究成果雖然公開，但是被大規(guī)模采用的并不多；另外，還有一些組織和個人以GPL(GNU general public license) 的方式開發(fā)和發(fā)布自己的系統(tǒng)．遺憾的是，這類系統(tǒng)也很少以論文形式發(fā)表．部署在LAN 上的分布式Web 爬蟲率先被提出，并得到廣泛的使用．較為著名的有早期的Google[舶，AltaVista 的Intnet Archive Crawlert31，Mercatert4I 等．但是，由于受到帶寬等瓶頸因素的制約，此種系統(tǒng)即使軟硬件的規(guī)模不斷擴大，也只能獲取全體Web 信息中相對較小的一部分．為了

解決上述問題，人們提出了部署于廣域網(wǎng)環(huán)境的分布式Web 爬蟲．

1．1相關(guān)工作

近幾年來，商業(yè)界和開源社區(qū)出現(xiàn)了一些廣域網(wǎng)分布式爬蟲系統(tǒng)(或搜索引擎) ，其思路一般是公司或組織向用戶提供爬蟲程序．一方面，分布在各地的用戶運行自己機器上的爬蟲程序為公司提供數(shù)據(jù)；另一方面，公司為安裝有爬蟲的用戶提供各種檢索服務(wù)，如Yacy(http：／／yaey ．net ／) 的個性化匿名檢索，甚至將利潤反饋給用戶(如 Faroo(http：／／www ．faroo ．corn ／)) ．在實現(xiàn)方面，這些系統(tǒng)有的是類似于SETI@Home那樣的主從式結(jié)構(gòu)(如Majestic(http：／／www ．majesticl2．co ．uk0) ，屬于有調(diào)度中心的Agent 協(xié)同；有的是P2P 方式進行分布式調(diào)度(如Faroo) ，即無調(diào)度中心的Agent 協(xié)同．這些系統(tǒng)的實現(xiàn)五花八門，但是由于發(fā)展時間較短，規(guī)模相對較?。趯W術(shù)方面，Cho 等人首次給出了分布式爬蟲的分類方法、評價指標等一系列基本概念，并提出基于廣域網(wǎng)分布式爬蟲與部署于LAN 的系統(tǒng)相比，具有高可擴展性和減少Internet 負載的優(yōu)點，為廣域網(wǎng)分布式爬蟲的研究奠定了基礎(chǔ)．UbiCrawert 擴展了一些概念，并聲稱可以支持基于廣域網(wǎng)的分布式平臺．Dustin B

等人對多種分布式爬蟲進行了比較，提出廣域網(wǎng)爬蟲是解決爬蟲系統(tǒng)帶寬瓶頸的有效方法．Yahoo 研究院的Baeza ．Yates 等人在其綜述中將分布式爬蟲定義為“原則上某些節(jié)點可以分布于不同的地理或網(wǎng)絡(luò)位置”．2003年后，很多研究開始關(guān)注廣域網(wǎng)分布式爬蟲，代表性的有，IPMicrat 第～個基于位置信息調(diào)度的分布式爬蟲，SE4SEE 實

現(xiàn)了基于網(wǎng)格的分布式爬蟲，Apoideatl 實現(xiàn)了基于P2P 協(xié)議的完全分布式爬蟲．國內(nèi)學術(shù)界對分布式爬蟲研究得較少，代表性的有北京大學的天網(wǎng)搜索引擎[14J的爬蟲系統(tǒng)，這是一個基于LAN 的爬蟲，已經(jīng)開始商業(yè)化運作；上海交通大學的Igloo 爬蟲實現(xiàn)了基于網(wǎng)格服務(wù)的分布式爬蟲(IglooG)，萬方網(wǎng)格的特性使其能夠支持廣域網(wǎng)部署．

1．2分布式爬蟲的基本結(jié)構(gòu)和工作流程

由于爬蟲要下載多個網(wǎng)頁，而各個網(wǎng)頁的下載過程之間依賴性較小，因此可以被并行化．為了高效地下載網(wǎng)頁，爬蟲程序一般被設(shè)計為多線程和多進程協(xié)同的方式，而分布式爬蟲是將多個具有抓取網(wǎng)頁功能的Agent 分別部署于多個計算資源之上的爬蟲程序．以下是分布式爬蟲中每個Agent 的大致工作流程(其中，左側(cè)帶 號的兩行代碼可能需要多機協(xié)同完成) ．為了突出Agent 對URL 的處理，算法描述省略了域名解析、對網(wǎng)頁和URL 的預處理以及解析網(wǎng)站的Robots ．txt 文件的過程．

URL Seen：用于存儲已經(jīng)抓取過的URL ．

URL 隊列：用于存儲待抓取的URL ．

輸入：初始URL 列表．

Agent(初始URL 列表){

將初始URL 列表中的URL 放入URL 隊列；

while(ERE隊列不為空){

從URL 隊列中取出一個URL ；

將URL 存入URLSeen ；

下載URL 指向的網(wǎng)頁：

提取網(wǎng)頁中含有的URL ；

for(每一個新發(fā)現(xiàn)的URL){

if(URL應由本Agent 負責){

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

將URL 放入URL 隊列： )else{

· 通過一定的Web 劃分方法選擇負責當前URL 的Agent ；

· 將URL 發(fā)送至此Agent ； } ) ) }

1．3廣域網(wǎng)分布式Web 爬蟲的優(yōu)勢和挑戰(zhàn)

廣域網(wǎng)分布式Web 爬蟲與基于LAN 的分布式爬蟲或稱局域網(wǎng)爬蟲相比具有諸多優(yōu)勢：

(1)可擴展性

可擴展性是局域網(wǎng)爬蟲的致命缺點，也是提出廣域網(wǎng)分布式爬蟲的主要原因．首先，廣域網(wǎng)系統(tǒng)能夠容納更多的計算資源，擁有更多的網(wǎng)絡(luò)接入點．理論上，整體吞吐量可以無限擴展；局域網(wǎng)爬蟲因其計算資源數(shù)量受到LAN 的限制，很難擴展到較大的規(guī)模，從而限制了系統(tǒng)整體吞吐量．其次，廣域網(wǎng)系統(tǒng)是由若干個相對較小的機群甚至單機節(jié)點組成，這使得資源添加和系統(tǒng)維護都變得相對簡單．如果能

夠進一步利用分布在Intemet 上的個人計算資源，則維護開銷將大為降低；相比之下，在LAN 中維護大規(guī)模機群的代價則非常昂貴，需要解決數(shù)據(jù)存儲、系統(tǒng)互連、機架結(jié)構(gòu)、電源、散熱等諸多問題．

(2)多網(wǎng)絡(luò)接入點

爬蟲在抓取網(wǎng)頁時，HTTP 請求和下載網(wǎng)頁的過程需要占用系統(tǒng)網(wǎng)絡(luò)接入點的大部分帶寬．對基于LAN 的系統(tǒng)，隨著機群規(guī)模的擴大，接入帶寬將變?yōu)橄到y(tǒng)瓶頸．如果爬蟲程序分布在不同的網(wǎng)絡(luò)位置，就可以使用多個網(wǎng)絡(luò)接入點，理論上可以獲得相當于這些接入點加和的總帶寬．并且隨著網(wǎng)絡(luò)接入點數(shù)量的增加，系統(tǒng)的總帶寬也會相應增加，理論上帶寬可以無限擴展．(31減少對Intemet 的網(wǎng)絡(luò)負載 爬蟲程序在發(fā)出HTTP 請求并下載網(wǎng)頁時，大量數(shù)據(jù)報文的傳播增加了Internet 的負載，在一定程度上影響了Intemet 的服務(wù)質(zhì)量．如果能夠?qū)崿F(xiàn)就近抓取，即布置在不同地域的分布式爬蟲僅負責抓取距離自己相對較近的網(wǎng)站，則廣域網(wǎng)分布式爬蟲可以將系統(tǒng)帶給Internet 的網(wǎng)絡(luò)負載控制在局部．而對于基于LAN 的爬蟲，由于其 網(wǎng)絡(luò)接入點單一，大量數(shù)據(jù)包要經(jīng)過較長的路徑才能到達目的地，從而給路徑上的所有網(wǎng)絡(luò)資源(如路由器、交換機、網(wǎng)關(guān)等) 帶來壓力． 廣域網(wǎng)尤其是Intemet 環(huán)境比局域網(wǎng)要復雜得多，系統(tǒng)一旦架設(shè)到廣域網(wǎng)環(huán)境就會受到諸多限制．如何有效利用廣域網(wǎng)資源同時又能消除廣域網(wǎng)環(huán)境的不利影響，是廣域網(wǎng)分布式爬蟲研究所面臨的重大挑戰(zhàn)．本文針對當前廣域網(wǎng)分布式Web 爬蟲的研究和實踐，總結(jié)出這一領(lǐng)域的3個關(guān)鍵問題：

(1)Web劃分：如何將抓取Web 這個巨大的任務(wù)切分成多份，交予系統(tǒng)中的多個Agent 執(zhí)行．

(2)Agent協(xié)同：多個Agent 之間應該如何進行協(xié)同工作，如何進行互聯(lián)與通信．

(3)Agent部署：如何利用現(xiàn)有硬件和網(wǎng)絡(luò)資源構(gòu)建廣域網(wǎng)分布式爬蟲系統(tǒng)．

這3個關(guān)鍵問題在廣域網(wǎng)分布式Web 爬蟲研究中的層次結(jié)構(gòu)如圖l 所示：最上層的Web 劃分強調(diào)的是邏輯問題，相當于決策層；最下層的Agent 部署強調(diào)的是物理問題，它作為系統(tǒng)的基礎(chǔ)是工程性很強的一層；Agent 協(xié)同則既涉及物理又涉及邏輯，包含了程序?qū)崿F(xiàn)和網(wǎng)絡(luò)環(huán)境分析等多方面的問題．

2 、Web 劃分

系統(tǒng)中各個Agent 在抓取過程中會不斷地發(fā)現(xiàn)新的URL ，而這些URL 中存在大量的重復．如果將這些新URL 直接交由發(fā)現(xiàn)它的Agent 抓取，那么將會引起多個Agent 下載相同的網(wǎng)頁，從而引起重復工作，降低整體的網(wǎng)頁抓取效率．因此，需要一種為各個Agent 分配URL 的策略，由此提出Web 劃分的概念．

2．1 Web劃分的定義

定義l(Web劃分集合和Web 劃分集合的分類) ．設(shè)分布式Web 爬蟲由Ⅳ個Agent 組成，Web 上所有網(wǎng)頁的集合

2．2 Web劃分單元

Web劃分單元的選取是實現(xiàn)W 曲劃分時必須考慮的問題．Web

劃分單元是Agent 在工作過程中所負責抓取的最小集合，凡是包含于劃分單元的網(wǎng)頁，全部由一個Agent 負責抓?。糜趙 曲劃分單元的某些屬性的集合稱為劃分屬性，用于指導對Web 劃分單元的分類．這些屬性可以來自URL 字符串本身。也可以來自與URL 相關(guān)的某些事物，如網(wǎng)站IP 地址、網(wǎng)頁內(nèi)容、第三方信息等．根據(jù)廣域網(wǎng)環(huán)境下實驗的經(jīng)驗，廣域網(wǎng)分布式系統(tǒng)在進行任務(wù)劃分時粒度必須適當?shù)卮?，以保證各個節(jié)點具有較高的計算通信比，盡量降低信息交換引發(fā)的時間開銷．Web 劃分單元對應任務(wù)粒度的概念，因此這樣的結(jié)論同樣適用于廣域網(wǎng)分布式爬蟲．下面討論兩個典型的Web 劃分單元(以下簡稱為單元) ，并對其劃分屬性及優(yōu)缺點進行論述．

(1)鏈接(URL)

URL是Web 爬蟲研究中最小的Web 劃分單元，優(yōu)點是簡單、直觀，缺點是粒度太細．由于Web 上存在的鏈

接比網(wǎng)站總數(shù)要多得多，對URL 進行分類的工作量是十分巨大的．與主機名相比，URL 所攜帶的劃分屬性比較

少。僅能顯示文件類型等信息．

(2)主機(host)

以URL 中的主機名(即hostname ，比如URL ：http ：／／www ．sina ．corn ／index ．html 的主機名為www ．sina ．corn) 為 Web 劃分單元，是大部分分布式Web 爬蟲的首選．相對于以URL 為單元而言，本方法產(chǎn)生的跨分區(qū)鏈接較少．因為處于同一個主機的URL 必然會被分配到同一個劃分集合中；而在以URL 為單元的情況下，這

些URL 可能會被分配到很多不同的Web 劃分集合中，這樣，主機內(nèi)部的鏈接也變成了跨分區(qū)鏈接．對主機名的一種延伸是域名，由于一個域名下可能擁有若干主機，因此域名是一種粒度更大的Web 劃分單元．主機所具有的劃分屬性主要有IP 地址、網(wǎng)站類型等。除了以上兩種單元以外，由于RIRs(regional intemet registries)的存在，通過主機的IP 地址等信息還可以得到網(wǎng)站所在國家、地區(qū)及運營商等信息，給Web 劃分單元提供了更多的可選方案。

2．3 Web劃分策略

根據(jù)定義2，在系統(tǒng)中含有Ⅳ個Agent 的情況下，Web 劃分的前提是找出Web 全集的一個大小為Ⅳ的子集(Web劃分集合) 的集合．采用何種方法將所有Web 劃分單元分類成Ⅳ個Web 劃分集合，并實現(xiàn)其與Ⅳ個Agent 的一一映射。構(gòu)成了分布式Web 爬蟲的Web 劃分策略．下面介紹目前已經(jīng)提出的幾種Web 劃分策略，對其原理和優(yōu)、缺點進行詳細論述．

(1)基于隨機哈希

基于隨機哈希的方法是采用得最多的Web 劃分方法．最早的分布式爬蟲系統(tǒng)大多是建立在對在對URL 或主機名哈希的基礎(chǔ)之上的．首先，這種方法非常容易計算，用于調(diào)度的系統(tǒng)開銷較小；其次，由于哈希函數(shù)的隨機性，保證了各個Agent 間負載均衡；另外，這種將字符串映射為隨機數(shù)的方法非常易于與采用DHT 的P2P 系統(tǒng)集成，如UbiCrawler(并沒有聲稱自己是P2P 系統(tǒng)，但是最早使用了類DHT 方法：consistent hashing，Apoidea 等。

基于哈希的方法遇到的最大問題是，結(jié)構(gòu)簡單的哈希值無法體現(xiàn)出主機所具有的類型、地理位置、網(wǎng)絡(luò)距離等信息，也就無法利用這些屬性提高分類質(zhì)量。

(2)基于域名后綴及文件類型

有的爬蟲根據(jù)主機或網(wǎng)站的域名后綴不同，將Web 劃分單元分配到不同的Web 劃分集合．比如，根據(jù)網(wǎng)站域名中諸如．net ，．org ，．corn ，．edu 這些表示組織性質(zhì)的后綴進行分類；還可以根據(jù)URL 字符串中的文件類型如．html ，．rap3等進行分類．以上兩種分類方法更加注重對網(wǎng)頁內(nèi)容的分類．SE4SEE 提出根據(jù)表示語言類型或國家、區(qū)域的域名后綴，如．cn ，jp ，．fr 等進行分類，這樣不僅實現(xiàn)了按照網(wǎng)頁內(nèi)容分類，而且由于每種語言群體的地理分布基本都不相同，也部分地實現(xiàn)了按地理位置劃分，為爬蟲就近抓取創(chuàng)造了一定的條件．這種方法的優(yōu)點是，Web 數(shù)據(jù)在抓取時就已經(jīng)進行了初步的分類，為以后的數(shù)據(jù)分析工作奠定了比較好的基礎(chǔ)．但它仍然存在諸多缺陷：首先，并非每個URL 或域名都遵守傳統(tǒng)的后綴命名規(guī)范，如有的學校的域名就是．corn 而不是大家普遍認同的．edu ；樣，也有很多．cn(中文) 后綴的網(wǎng)站其實含有大量英語內(nèi)容；其次，由于各種類型的網(wǎng)站的數(shù)量或文件的數(shù)量分布不均，將造成系統(tǒng)中各個Agent 的負載不均，比如，按照語言類型分類，小語種網(wǎng)站的數(shù)量非常少，而擁有諸如．en ，．de 這類域名后綴的網(wǎng)站數(shù)量則非常大．跨越較大的地理范圍和網(wǎng)絡(luò)范圍是廣域網(wǎng)分布式系統(tǒng)天生的優(yōu)勢，可以利用這個優(yōu)勢實現(xiàn)Agent 對網(wǎng)站的就近抓取。即對每個網(wǎng)站由距離它