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

廣域網分布式Web 爬蟲

滕千紅

(湖工，管院，1010831119）

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

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

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

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

1、引言

在分布式Web 爬蟲領域，商業(yè)界與學術界各自為戰(zhàn)，許多優(yōu)秀的實現(xiàn)方法不是源自于學術界，而是來自于一些公司．出于商業(yè)因素的考慮，公司成果一般不通過論文公開發(fā)表；而學術界的研究成果雖然公開，但是被大規(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 信息中相對較小的一部分．為了

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

1．1相關工作

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

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

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

1．2分布式爬蟲的基本結構和工作流程

由于爬蟲要下載多個網頁，而各個網頁的下載過程之間依賴性較小，因此可以被并行化．為了高效地下載網頁，爬蟲程序一般被設計為多線程和多進程協(xié)同的方式，而分布式爬蟲是將多個具有抓取網頁功能的Agent 分別部署于多個計算資源之上的爬蟲程序．以下是分布式爬蟲中每個Agent 的大致工作流程(其中，左側帶 號的兩行代碼可能需要多機協(xié)同完成) ．為了突出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(每一個新發(fā)現(xiàn)的URL){

if(URL應由本Agent 負責){

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

將URL 放入URL 隊列： )else{

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

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

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

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

(1)可擴展性

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

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

(2)多網絡接入點

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

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

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

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

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

2 、Web 劃分

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

2．1 Web劃分的定義

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

2．2 Web劃分單元

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

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

(1)鏈接(URL)

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

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

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

(2)主機(host)

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

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

2．3 Web劃分策略

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

(1)基于隨機哈希

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

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

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

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