范珊珊，李石君

（武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢430072）

0 引 言

目前已有各種算法研究在分布式爬蟲中分配資源和調(diào)度網(wǎng)頁抓取的策略。其中，文獻(xiàn) ［3］提出基于動態(tài)反饋的負(fù)載均衡算法，使任務(wù)集在集群系統(tǒng)中各單節(jié)點(diǎn)中得到均勻分布；文獻(xiàn) ［10］提出一種改進(jìn)的T－Spider分布式爬蟲，其對頁面切割一遍各節(jié)點(diǎn)能夠并行地解析網(wǎng)頁。然而，這些方法更為集中地研究分布式爬蟲整體框架與單節(jié)點(diǎn)之間的資源分配和調(diào)度策略，未能將調(diào)度粒度細(xì)化到單節(jié)點(diǎn)中的各子任務(wù)，從而忽略了單節(jié)點(diǎn)中多樣性任務(wù)之間的調(diào)度競爭和協(xié)同關(guān)系。

為了改善這一缺陷，本文以多主題任務(wù)為切入點(diǎn)，在研究如何使任務(wù)集均勻分布到各集群節(jié)點(diǎn)的基礎(chǔ)上，提出了一種基于優(yōu)先級隊(duì)列的單節(jié)點(diǎn)任務(wù)調(diào)度算法，基于各主題的特點(diǎn)構(gòu)建優(yōu)先級隊(duì)列，在單節(jié)點(diǎn)中各主題任務(wù)基于時間段輪詢調(diào)度，使優(yōu)先級較高的任務(wù)能夠進(jìn)行搶奪式調(diào)度，提高分布式環(huán)境中各處理節(jié)點(diǎn)資源的利用效率，克服傳統(tǒng)分布式爬蟲中各主題任務(wù)分配的處理資源差異性較大導(dǎo)致爬取結(jié)果不均的缺點(diǎn)。最后實(shí)驗(yàn)分析并比較引入優(yōu)先級隊(duì)列的分布式爬蟲與傳統(tǒng)分布式爬蟲的性能差異。

1 爬蟲調(diào)度算法PQ－MCSA

在PQ－MCSA 中采用靜態(tài)分配和動態(tài)調(diào)度相結(jié)合的策略，在優(yōu)先級和權(quán)重關(guān)系約束下，計(jì)算各節(jié)點(diǎn)的負(fù)載能力，使任務(wù)合理分配到各處理機(jī)上有序執(zhí)行。首要的任務(wù)是將大量的爬行任務(wù)進(jìn)行合理分割，然后按照一定策略分配到各處理節(jié)點(diǎn)上進(jìn)行爬蟲調(diào)度。

1.1 任務(wù)分割策略

任務(wù)分割是指將用戶指定的Web Page集合合理劃分，然后分布到多個爬行器中，分割過程中需要避免一個URL被分配到多個處理節(jié)點(diǎn)下，出現(xiàn)重復(fù)下載，以及漏掉某些網(wǎng)址，出現(xiàn)某些Web頁面不能下載的情況。

傳統(tǒng)的任務(wù)分割方法是通過協(xié)調(diào)器來實(shí)現(xiàn)的，將爬蟲分成一個協(xié)調(diào)器 （coordinator）和多個爬行器 （crawler）。在分布式系統(tǒng)中，指定一臺主機(jī)作為協(xié)調(diào)器，將用戶指定的URL 通過Hash函數(shù)計(jì)算，按照計(jì)算結(jié)果將URL 分配到指定的計(jì)算節(jié)點(diǎn)中。協(xié)調(diào)器負(fù)責(zé)系統(tǒng)全局的URL 分布，而超過爬行范圍的鏈接則通過計(jì)算節(jié)點(diǎn)反饋給協(xié)調(diào)器處理模塊，由協(xié)調(diào)器通過一定策略轉(zhuǎn)發(fā)給其余對應(yīng)的Crawler。由于爬蟲任務(wù)量隨著爬蟲的進(jìn)行逐漸增多，在并行處理系統(tǒng)中協(xié)調(diào)器需要處理大量的URL，很容易出現(xiàn)超負(fù)荷運(yùn)行的情況，從而影響系統(tǒng)性能，這成為垂直搜索引擎爬蟲能力提升的瓶頸。

在改進(jìn)的任務(wù)分割算法中，設(shè)定URLs＝ ｛URL1，URL2，URL3，…｝是爬蟲系統(tǒng)運(yùn)行過程中積累的網(wǎng)頁地址集合，爬行器數(shù)目為M，待下載網(wǎng)頁的集合為W，任務(wù)分割子集合為｛W1，W2，…，Wn｝，滿足∪ni＝1Wi＝W 且Wi∩Wj＝，其中i≠j，1≤i＜j≤n，且滿足：｜Wi｜≈｜Wj｜，即每個任務(wù)節(jié)點(diǎn)上的任務(wù)量是大致相等，達(dá)到各爬行器分配的任務(wù)均衡。

1.2 任務(wù)分配策略

哈希方法是信息查詢和存儲所用的一項(xiàng)基本技術(shù)，一些基于Hash函數(shù)的文件結(jié)構(gòu)在大型的分布式文件系統(tǒng)中得到了廣泛的應(yīng)用。在靜態(tài)負(fù)載分配的各種方案之中，我們選擇是利用緩存與哈希算法相結(jié)合靜態(tài)分配策略，這種算法能有效緩解一般哈希算法中由于輸入的記錄鍵值分布異常而出現(xiàn)大量內(nèi)存浪費(fèi)的情況，使負(fù)載能均勻分配到各計(jì)算節(jié)點(diǎn)之上。

1.2.1 基于緩存的擴(kuò)展式哈希算法 （cache－based extendible hashing system）

哈希算法能實(shí)現(xiàn)對記錄的隨機(jī)快速訪問，傳統(tǒng)哈希算法中，設(shè)定被訪問的記錄鍵值為KEY，哈希函數(shù)為Hash（），N 為存儲單元的總數(shù)，通過key＝Hash（KEY）計(jì)算出記錄鍵值所對應(yīng)的偽鍵值，其中記錄鍵值KEY 所對應(yīng)的存儲單元編號ID 為key%N。這種直接映射哈希算法的不足之處是，對于存儲單元總數(shù)N 隨時間變化敏感的情形并不合適，因?yàn)镹 如果易于隨時間變化，記錄鍵值KEY 數(shù)量較多，偽鍵值key 計(jì)算較頻繁的情況下會消耗大量的內(nèi)存資源，效率不高。與緩存相結(jié)合的哈希算法是通過引入一定大小的緩存，該緩存大小可以隨系統(tǒng)的需求來制定，這部分緩存用于記錄各文件的使用情況，提高內(nèi)存利用率，使哈希函數(shù)將記錄的鍵值 （KEY）均勻的映射到偽鍵域上。在提高偽鍵值查詢效率的同時，避免每次因存儲單元總數(shù)的變化而需要全部重新計(jì)算偽鍵值 （pseudo key）的缺陷。

算法過程為在文件結(jié)構(gòu)中構(gòu)造桶文件 （bucket file）、目錄文件 （directory file）、緩 存 桶 （cache bucket）3 種 抽象的數(shù)據(jù)結(jié)構(gòu)。桶文件由桶組成，它們是一些桶文件塊，在桶中設(shè)置記錄單元RU （record unit），局部長度LL （local length）兩個因素，其中RU 用于記載桶中存放的記錄數(shù)。全局長度為GL （global length），其中GL 的值為所有局部深度LL中的最大值，GL 和LL 隨著RU 的數(shù)量及記錄的分布的變化而變化。目錄文件中維護(hù)一個有2GL個元素的數(shù)組NArray，NArray［x］為該數(shù)組的第x個索引項(xiàng)對應(yīng)的目錄，NArray［x］都存儲有指向某個桶的指針，成為桶指針 （bucket pointer），對于一個桶，如果其局部深度LL為M，那么目錄文件中總工有2GL－M個桶指針指向它。初始時只有一個桶，而且LD＝0，RU＝0，數(shù)組NArray有一個元素，NArray［0］都存儲有指向該桶的指針。

緩存桶的目錄文件的結(jié)構(gòu)和普通桶文件結(jié)構(gòu)基本是相同的，在桶文件的結(jié)構(gòu)上，緩存桶增加了兩個標(biāo)志位，一個標(biāo)志位為LG，用來表示桶的局部深度和全局長度之間的關(guān)系，具體是，LG＝0 表示該記錄單元對應(yīng)桶LL＜GL，而LG＝1表示該記錄單元對應(yīng)桶LL＝GL；另外一個標(biāo)志位為BNP，為布爾型值，表示桶在其對應(yīng)的緩存桶中是否存在相應(yīng)記錄，BNP＝0 為假，表示桶在緩存桶中沒有記錄，相反BNP＝1為真，表示桶在緩存桶中有記錄。

為了使網(wǎng)址盡可能合理地按照計(jì)算節(jié)點(diǎn)的承載能力來分配到各個裝載有Crawler的爬行器中，設(shè)計(jì)一個較好的網(wǎng)址Hash函數(shù)，其函數(shù)表達(dá)式如下

該函數(shù)中，ASCII用來取字符串中每個字符的ASCII碼，第一次取值W ＝GL，第二次取值W ＝LL，其中GL 為全局長度，LL為桶的局部深度，實(shí)驗(yàn)表明，該哈希函數(shù)呈現(xiàn)的分布均勻，能夠使爬行器獲取的任務(wù)數(shù)量均勻增長。

記錄單元R 的檢索過程是，首先根據(jù)設(shè)定的哈希函數(shù)Hash（S）計(jì)算出R 的偽鍵值Pseudo Key，根據(jù)偽鍵值的GL位得到索引的目錄，找到桶的指針，根據(jù)該桶的存儲結(jié)構(gòu)尋找該記錄單元R。如果在該桶中查找不到記錄單元R且該桶的標(biāo)志位BNP＝1，則進(jìn)入緩存桶中進(jìn)行查找，在緩存桶中對記錄單元的檢索并不影響記錄的檢索效率，因?yàn)榫彺嫱俺ｑv內(nèi)存，避免了慢速的I／O 操作。將記錄R 插入桶的過程如圖1所示。

1.2.2 URL邏輯二級節(jié)點(diǎn)哈希映射法

圖1 基于緩存的擴(kuò)展式哈希算法

采用URL 邏輯二級節(jié)點(diǎn)哈希映射發(fā)來實(shí)現(xiàn)網(wǎng)頁爬取URL的分布式分配，使URL 的分配不再交由傳統(tǒng)方法中的協(xié)調(diào)器完成，這樣可使系統(tǒng)規(guī)模靈活可擴(kuò)展。這種新方法的顯著特點(diǎn)是在爬蟲任務(wù)和最終的分配的物理實(shí)況之間加入一層邏輯空間的概念，即首先將URL映射到一張一維的邏輯表上，這是第一級映射，對爬取任務(wù)集進(jìn)行第一步劃分，然后進(jìn)行第二級映射，將邏輯表上的節(jié)點(diǎn)映射到各個物理節(jié)點(diǎn)中。作如下的定義：

定義1 任務(wù)集 （task set）。設(shè)URLSet＝ ｛URL1，URL2，URL3，…｝是爬蟲的任務(wù)集合，該任務(wù)集是動態(tài)變化且未知的，因?yàn)榇巳蝿?wù)集會在爬蟲處理網(wǎng)址的過程中發(fā)掘新的網(wǎng)址而處于不同的狀態(tài)。

定義2 劃分粒度 （partition granularity）。設(shè)定M 為爬蟲系統(tǒng)的并行節(jié)點(diǎn)數(shù)量，［M］＝ ｛1，2，3，…，M｝表示集群系統(tǒng)中的所有節(jié)點(diǎn)的集合。N 為單個爬行節(jié)點(diǎn)上網(wǎng)頁抓取線程的總數(shù)。在單機(jī)爬蟲系統(tǒng)中為了有效地管理CPU，網(wǎng)絡(luò)帶框，IO 等資源，會將爬行的任務(wù)集合按照一定策略分配給各個線程。定義即所有的任務(wù)集URLSet 到M×N 個線程之間的映射為劃分粒度。

定義3 host（URL）。定義host（URL）為一個URL 的主機(jī)部分，通常情況下可以根據(jù)某一網(wǎng)址得出其值。例如

URL1＝ “http：／／www.lib.gxu.edu.cn／content／detail.asp”，則host（URL）＝ “www.lib.gxu.edu.cn”。一個host（URL）一般對應(yīng)物理領(lǐng)域的某一臺Web Server。

URL邏輯二級節(jié)點(diǎn)哈希映射的步驟為，約定可利用的并行節(jié)點(diǎn)數(shù)目為T，當(dāng)前正在運(yùn)行的爬蟲數(shù)目為N（N＜＝T），而系統(tǒng)初始節(jié)點(diǎn)數(shù)為n，在爬蟲運(yùn)行過程中n 不斷變化，變現(xiàn)為集群節(jié)點(diǎn)不斷發(fā)生變化。在第一級映射中，采用Hash（URL）mod M 的方法將URL 映射到節(jié)點(diǎn)數(shù)為M的邏輯表上，其中M＞＞N，在第二級映射中，同樣采取Hash（URL）的方法，將M 個邏輯節(jié)點(diǎn)映射到n 個集群節(jié)點(diǎn)上，通過兩級映射，將劃分粒度成功細(xì)化到n，結(jié)合一個隨機(jī)性較強(qiáng)的哈希函數(shù)，將可以達(dá)到各個爬行節(jié)點(diǎn)上的子任務(wù)集相對均勻的目的，如圖2所示。

圖2 二級URL哈希映射

1.3 任務(wù)調(diào)度策略

集群式系統(tǒng)中，通過分布式任務(wù)調(diào)度算法將整個任務(wù)集分配到了各個計(jì)算節(jié)點(diǎn)上。任務(wù)是多主題的，按照主題的時效性特點(diǎn)和其重要程度以合理的方式分成不同的優(yōu)先度。例如時效性較強(qiáng)的Web頁面類是需要優(yōu)先爬取的，且爬取的頻率要求較大，這樣才能周期性的及時將內(nèi)容爬取下來供搜索引擎處理，這種主題的URL優(yōu)先度較高。而時效性要求較低而且更新周期較長的網(wǎng)頁類別優(yōu)先度較低。優(yōu)先級分類原則是不同重要性的網(wǎng)頁類別分成不同的優(yōu)先級，對優(yōu)先級不同的任務(wù)集采用搶占式調(diào)度的方式來進(jìn)行爬取，優(yōu)先級高的類別優(yōu)先獲得系統(tǒng)調(diào)度，從而提高重要性較高的主題任務(wù)被爬取的機(jī)會。而重要性類似或相同的網(wǎng)頁類別則賦予同等的優(yōu)先級，采用多線程和類似于分時操作系統(tǒng)中采用的時間片輪轉(zhuǎn)的方式來分配調(diào)度空間，在調(diào)度時具有同等優(yōu)先級的類別具有相同的幾率。以此方式來減少有些URL類別始終都得不到爬取的現(xiàn)象，提高節(jié)點(diǎn)的利用率。

1.3.1 優(yōu)先級隊(duì)列設(shè)計(jì)

維護(hù)優(yōu)先級隊(duì)列PRIORITY＿QUEUE 這樣一個數(shù)據(jù)結(jié)構(gòu)來存儲所有主題任務(wù)的優(yōu)先級。隊(duì)列中存儲爬取任務(wù)和任務(wù)對應(yīng)的優(yōu)先級。任務(wù)可以是某一個爬取主題，也可以細(xì)化到粒度為URL的具體爬行目標(biāo)。如果某一個主題下的所有網(wǎng)址的優(yōu)先級都相同，則該任務(wù)在優(yōu)先級隊(duì)列中以爬取主題存儲，否則細(xì)化到單一的URL存儲，這樣能夠提高優(yōu)先級劃分的靈活性。任務(wù)控制塊QUEUE＿M(jìn)CB，優(yōu)先級隊(duì)列結(jié)點(diǎn)QUEUE＿NODE和指針數(shù)組QueueArray［］的相互關(guān)系見圖X。

定義優(yōu)先級隊(duì)列PRIORITY＿QUEUE 表為一個五元組形式

其中IDtask是任務(wù)標(biāo)識符，采用N 位無符號整型，具體設(shè)計(jì)由實(shí)際任務(wù)規(guī)模決定。IDtheame表示URLFORM 所屬的主題，稱作主題標(biāo)識符，當(dāng)任務(wù)的粒度G 為false時才有意義。P 表示隊(duì)列中任務(wù)的優(yōu)先度，采用M 位整型存儲。G是任務(wù)的粒度，為true表示粒度為主題，為false表示粒度為主題下所包含的URL。TN 隊(duì)列上的任務(wù)數(shù)，是動態(tài)可變化的。UMAP 與G 聯(lián)合起來使用，采用Map數(shù)據(jù)結(jié)構(gòu)存儲，該Map中KEY 表示主題的任務(wù)標(biāo)識符IDtask，VALUE 為CHARSEQUECE 類型，存儲主題任務(wù)標(biāo)識符為IDtask且優(yōu)先級為P 的URL的SURT 格式，當(dāng)G 為false時UMAP 才有意義。

定義隊(duì)列控制塊QUEUE＿M(jìn)CB的數(shù)據(jù)結(jié)構(gòu)為一個八元組形式

其中IDtask是任務(wù)標(biāo)識符，它是任務(wù)的唯一標(biāo)志。TN 是任務(wù)名稱 （task name），TD 是任務(wù)的描述信息 （task description），ST 是分配給此任務(wù)的時間片長度 （slice total），SR是在一個時間段內(nèi)此任務(wù)執(zhí)行的剩余時間段長度 （slice remain），SI 是 任 務(wù) 執(zhí) 行 的 狀 態(tài) 信 息 （task state information），CP 是堆棧指針，用于保存任務(wù)上下文 （task context P）。TD 是任務(wù)延時 （task delay）。優(yōu)先級隊(duì)列的詳細(xì)結(jié)構(gòu)設(shè)計(jì)如圖3所示。

圖3 任務(wù)優(yōu)先級隊(duì)列

定義網(wǎng)址的格式為SURT 格式 （sort－friendly URI reordering transform），一般網(wǎng)址的格式采用URL 格式 （uniform resource locator，統(tǒng)一資源定位符），SURT 格式是對URL格式的一種改進(jìn)，有利于URL 的排序和集合聚攏。SURT 格 式 將 “scheme：／／userinfo＠domain.tld：port／path？query＃fragment”形式的URL 轉(zhuǎn)換成 “scheme：／／（tld，domai n，：port＠userinfo）／path？query＃fragment”的形式，例如 “http：／／www.baidu.com”對應(yīng)的SURT格 式 是 “http：／／ （com，baidu，www，）”。同 時 引 入TaskID 作為每一個任務(wù)的標(biāo)識符，TaskID 可以采用N 位的符號整數(shù)來表示，可存儲的任務(wù)數(shù)目為2N。

1.3.2 任務(wù)調(diào)度算法描述

隊(duì)列控制塊中唯一表示任務(wù)標(biāo)示符的是TaskID，Slice＿Total用來保存分配到TaskID 所表示的任務(wù)的時間區(qū)間大小，Slice＿Remain表示任務(wù)執(zhí)行的剩余時間，這兩項(xiàng)用來實(shí)現(xiàn)任務(wù)的時間片輪轉(zhuǎn)調(diào)度。

算法1：任務(wù)初始化

輸入：可調(diào)度任務(wù)task，預(yù)分配的爬取時間段time＿schedule

輸出：任務(wù)執(zhí)行隊(duì)列scheduleTaskQueue

算法2：任務(wù)調(diào)度過程

輸入：任務(wù)執(zhí)行隊(duì)列scheduleTaskQueue，優(yōu)先級隊(duì)列priorityQueue

輸出：FOR each crawlSubTask∈scheduleTaskQueue

算法3：搶奪式調(diào)度

輸入：待調(diào)度的任務(wù)task＿pending，正在運(yùn)行任務(wù)task＿crawling，優(yōu)先級隊(duì)列priorityQueue

輸出：啟動后臺線程并進(jìn)行輪詢監(jiān)控

啟動后臺線程并進(jìn)行輪詢監(jiān)控

任務(wù)調(diào)度過程中，首先將所有可調(diào)度的任務(wù)細(xì)分成各個爬行子任務(wù)，按照其優(yōu)先級分配到不同的預(yù)備隊(duì)列中，在預(yù)備隊(duì)列中完一系列例如DNS解析等網(wǎng)頁爬取的初始化工作。調(diào)度器不間斷地調(diào)度任務(wù)，優(yōu)先級高的有較高的幾率獲得系統(tǒng)運(yùn)行資源并被調(diào)度進(jìn)入爬取隊(duì)列中，而優(yōu)先級相同的任務(wù)分時地占用調(diào)度資源。預(yù)先給不同優(yōu)先級的任務(wù)分配不同的爬行時間閾值，即一次爬取的最大時間，同一優(yōu)先級的任務(wù)之間的爬行時間閾值相同。而不同優(yōu)先級的任務(wù)根據(jù)調(diào)度策略的不同分配不同的爬行時間閾值，在任務(wù)開始時，維護(hù)一個計(jì)時器對每個開始運(yùn)行的爬行任務(wù)進(jìn)行計(jì)時，相同優(yōu)先級的任務(wù)之間進(jìn)行時間片輪轉(zhuǎn)，如果有優(yōu)先級更高的任務(wù)被調(diào)度進(jìn)來，則當(dāng)前運(yùn)行的任務(wù)會被強(qiáng)制進(jìn)入就緒隊(duì)列，而將執(zhí)行資源讓給優(yōu)先級高的任務(wù)。在任務(wù)調(diào)度的同時，維護(hù)一個Demon線程，統(tǒng)計(jì)各個主題下任務(wù)的爬取規(guī)律和爬取的網(wǎng)頁數(shù)量。如果符合相應(yīng)主題的爬取規(guī)律且在規(guī)定時間內(nèi)爬取到了最低數(shù)量的相關(guān)性網(wǎng)頁，則相應(yīng)的爬行時間閾值減少一個額度，同時將在較短的時間內(nèi)調(diào)換執(zhí)行同類任務(wù)或者更高優(yōu)先級的任務(wù)。這樣在有限的調(diào)度周期內(nèi)，該主題爬取的機(jī)會減少，留給其它主題的爬取機(jī)會將會增多，從而保證各個爬取的主題分配到的運(yùn)行資源是相對均勻的。

2 系統(tǒng)實(shí)現(xiàn)與結(jié)果分析

該多主題的分布式爬蟲系統(tǒng)采用一個功能節(jié)點(diǎn)，兩個能力節(jié)點(diǎn)進(jìn)行測試，需要一臺架構(gòu)服務(wù)器，和兩臺能力服務(wù)器。其中功能節(jié)點(diǎn)用于收集各能力節(jié)點(diǎn)的負(fù)載情況，來分發(fā)任務(wù)，維持分布式系統(tǒng)的負(fù)載均衡狀況。兩個能力節(jié)點(diǎn)采用不同的任務(wù)調(diào)度方式，進(jìn)行多主題爬蟲。表1是節(jié)點(diǎn)的規(guī)格型號和技術(shù)參數(shù)說明。

表1 系統(tǒng)測試環(huán)境參數(shù)說明

對于傳統(tǒng)的分布式爬蟲，系統(tǒng)運(yùn)行時間是24小時，到次日凌晨時會重啟爬蟲，對于優(yōu)先級隊(duì)列的分布式爬蟲，在一輪調(diào)度完成之后，會重啟爬蟲，給定測試時間為24小時，此次試驗(yàn)主要設(shè)計(jì)爬取稅收領(lǐng)域的3個主題，稅收經(jīng)驗(yàn)，每日動態(tài)，重點(diǎn)稅源，每一類主題在數(shù)據(jù)庫中配置了相應(yīng)的網(wǎng)址，可對網(wǎng)址進(jìn)行更新修改。

表2中每個主題中有3個參數(shù)，下載URL 數(shù)量、發(fā)現(xiàn)URL數(shù)量、網(wǎng)頁下載總數(shù)，分成A 組和B組，A 組表示傳統(tǒng)的分布式多主題爬蟲系統(tǒng)，B 組表示基于優(yōu)先級隊(duì)列的分布式多主題爬蟲系統(tǒng)，運(yùn)用相同的能力節(jié)點(diǎn)在規(guī)定的時間內(nèi)測試，A 組即A1主題，A2主題，A3主題；相應(yīng)地右邊是B1主題、B2主題、B3主題。Ai和Bi均分出重點(diǎn)稅源、稅收經(jīng)驗(yàn)、每日情報3個主題，然后對比左右兩邊的數(shù)據(jù)均勻情況。從測試結(jié)果中可以看出，該分布式爬蟲系統(tǒng)各節(jié)點(diǎn)中任務(wù)爬取較均勻，具有較高的性能。

圖4橫坐標(biāo)是時間，縱坐標(biāo)是爬取的網(wǎng)頁數(shù)目，每隔兩個小時采集一次樣本數(shù)據(jù)，展現(xiàn)的是A 組和B組的總體爬蟲結(jié)果對比。能力節(jié)點(diǎn)1進(jìn)行B 組的爬蟲實(shí)驗(yàn)，能力節(jié)點(diǎn)2進(jìn)行A 組的爬蟲實(shí)驗(yàn)。能力節(jié)點(diǎn)2引入優(yōu)先級隊(duì)列的分布后調(diào)度的情況，表示優(yōu)先級不同的主題之間是如何體現(xiàn)調(diào)度關(guān)系的。畫中4條曲線表示的是A 組和B組并行節(jié)點(diǎn)的均值和總和，體現(xiàn)出了調(diào)度算法的實(shí)際運(yùn)作過程，同時進(jìn)行了新舊對比。是對分布式爬取節(jié)點(diǎn)的一個切片展示。從圖中可以看出采用新算法的爬蟲的所有主題比不采用新算法的爬蟲結(jié)果分布的要均勻，且避免了舊的算法出現(xiàn)的沒有數(shù)據(jù)的特殊情況。

表2 單個節(jié)點(diǎn)爬蟲結(jié)果對比

圖4 爬蟲結(jié)果總體對比

3 結(jié)束語

在集群環(huán)境中，傳統(tǒng)的分布式主題爬蟲較為集中地關(guān)注分布式系統(tǒng)的架構(gòu)和功能模塊的劃分和協(xié)同，忽略了各計(jì)算節(jié)點(diǎn)的子任務(wù)集的相關(guān)度計(jì)算因素，及爬取資源分配情況。本文提出了一種基于優(yōu)先級隊(duì)列的分布式主題爬蟲調(diào)度算法PQ－MCSA。在對任務(wù)集進(jìn)行分配模塊中，引入基于緩存的可擴(kuò)展哈斯算法檢索記錄，減少了I／O 操作數(shù)，避免了傳統(tǒng)的可擴(kuò)展哈希方法在偽鍵值分布不均勻上造成浪費(fèi)內(nèi)存的缺陷。在單處理節(jié)點(diǎn)中，針對多主題的子任務(wù)集，根據(jù)各主題的優(yōu)先度和時效性不同的特點(diǎn)基于優(yōu)先級隊(duì)列進(jìn)行優(yōu)先級隊(duì)列調(diào)度。實(shí)驗(yàn)結(jié)果表明，使用該算法能夠在更短的時間內(nèi)爬取相對較多的網(wǎng)頁，使各主題爬取的結(jié)果相對均勻。確定各主題任務(wù)的優(yōu)先級過程中，是根據(jù)以往經(jīng)驗(yàn)和主題相關(guān)度因素進(jìn)行設(shè)定的，還缺乏精確的方法生成與主題特點(diǎn)相對應(yīng)的優(yōu)先級。將在下一步工作中進(jìn)行上述研究，以進(jìn)一步提高調(diào)度的實(shí)用性和準(zhǔn)確度。

［1］LIANG Gen，QIN Yong，GUO Xiaoxue，et al.Task scheduling in distributed system based on dynamic multi processing nodes［J］.Computer Engineering，2009，35 （9）：31－33 （in Chinese）.［梁根，秦勇，郭小雪，等.基于動態(tài)多處理節(jié)點(diǎn)的分布式系統(tǒng)任務(wù)調(diào)度 ［J］.計(jì)算機(jī)工程，2009，35 （9）：31－33.］

［2］LIU Shuang，JIANG Chunxiang，ZHANG Weizhe，et al.GNP－based scheduling strategy for distributed crawling ［J］.Application Research of Computers，2010，27 （2）：446－449（in Chinese）.［劉爽，姜春祥，張偉哲，等.基于GNP 算法的分布式爬蟲調(diào)度策略 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（2）：446－449.］

［3］WANG Chunjuan，DONG Lili，JIA Li.Load balance algorithm for Web cluster system ［J］.Computer Engineering，2010，36 （2）：102－104 （in Chinese）. ［王春娟，董麗麗，賈麗.Web集群系統(tǒng)的負(fù)載均衡算法 ［J］.計(jì)算機(jī)工程，2010，36 （2）：102－104.］

［4］GENG Xiaozhong.Research on key techniques of task scheduling based on multi－core distributed environment ［D］.Jilin：Jilin University，2013：30－32 （in Chinese）.［耿曉中.基于多核分布式環(huán)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究 ［D］.吉林：吉林大學(xué)，2013：30－32.］

［5］BAI He，TANG Dibin，WANG Jinsong.Research and implementation of distributed and multi－topic Web crawler system［J］.Computer Engineering，2009，35 （19）：13－16 （in Chinese）.［白鶴，湯迪斌，王勁松.分布式多主題網(wǎng)絡(luò)爬蟲系統(tǒng)的研究與實(shí)現(xiàn) ［J］.計(jì)算機(jī)工程，2009，35 （19）：13－16.］

［6］MENG Xiangqian，YE Yunming，DENG Bin.Study on paral－lel crawler based on pipeline load balancing model［J］.Computer Engineering，2009，35 （2）：34－36 （in Chinese）.［孟祥乾，葉允明，登斌.基于流水線負(fù)載平衡模型的并行爬蟲研究［J］.計(jì)算機(jī)工程，2009，35 （2）：34－36.］

［7］Cafarella M J，Madhavan J，Halevy A.Web－scale extraction of structured data ［J］.SIGMOD Record，2008，37 （4）：55－61.

［8］LIU Shaofeng，DONG Jian，WU Zhibo.A dynamic－feedback scheduling algorithm for cluster load balancing based on priority queue［J］.Intelligent Computer and Applications，2012，28（4）：78－80 （in Chinese）.［柳少峰，董劍，吳智博.一種基于優(yōu)先級隊(duì)列的集群動態(tài)反饋調(diào)度算法 ［J］.智能計(jì)算機(jī)與應(yīng)用，2012，28 （4）：78－80.］

［9］XU Xiao.Research on key technology of distributed Web crawling ［D］.Harbin：Harbin Institute of Technology，20011：28－31 （in Chinese）.［許笑.分布式Web信息采集關(guān)鍵技術(shù)研究 ［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，20011：28－31.］

［10］JIN Fan，GU Jinguang.An improved t－spider distributed crawler［J］.Microelectronics ＆Computer，2011，28 （8）：102－104 （in Chinese）.［金凡，顧進(jìn)廣.一種改進(jìn)的T－Spider分布式爬蟲 ［J］.微電子學(xué)與計(jì)算機(jī)，2011，28 （8）：102－104.］