基于優先級隊列的分布式多主題爬蟲

范珊珊，李石君

（武漢大學 計算機學院，湖北 武漢430072）

0 引 言

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

為了改善這一缺陷，本文以多主題任務為切入點，在研究如何使任務集均勻分布到各集群節點的基礎上，提出了一種基于優先級隊列的單節點任務調度算法，基于各主題的特點構建優先級隊列，在單節點中各主題任務基于時間段輪詢調度，使優先級較高的任務能夠進行搶奪式調度，提高分布式環境中各處理節點資源的利用效率，克服傳統分布式爬蟲中各主題任務分配的處理資源差異性較大導致爬取結果不均的缺點。最后實驗分析并比較引入優先級隊列的分布式爬蟲與傳統分布式爬蟲的性能差異。

1 爬蟲調度算法PQ－MCSA

在PQ－MCSA 中采用靜態分配和動態調度相結合的策略，在優先級和權重關系約束下，計算各節點的負載能力，使任務合理分配到各處理機上有序執行。首要的任務是將大量的爬行任務進行合理分割，然后按照一定策略分配到各處理節點上進行爬蟲調度。

1.1 任務分割策略

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

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

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

1.2 任務分配策略

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

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

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

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

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

為了使網址盡可能合理地按照計算節點的承載能力來分配到各個裝載有Crawler的爬行器中，設計一個較好的網址Hash函數，其函數表達式如下

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

記錄單元R 的檢索過程是，首先根據設定的哈希函數Hash（S）計算出R 的偽鍵值Pseudo Key，根據偽鍵值的GL位得到索引的目錄，找到桶的指針，根據該桶的存儲結構尋找該記錄單元R。如果在該桶中查找不到記錄單元R且該桶的標志位BNP＝1，則進入緩存桶中進行查找，在緩存桶中對記錄單元的檢索并不影響記錄的檢索效率，因為緩存桶常駐內存，避免了慢速的I／O 操作。將記錄R 插入桶的過程如圖1所示。

1.2.2 URL邏輯二級節點哈希映射法

圖1 基于緩存的擴展式哈希算法

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

定義1 任務集 （task set）。設URLSet＝ ｛URL1，URL2，URL3，…｝是爬蟲的任務集合，該任務集是動態變化且未知的，因為此任務集會在爬蟲處理網址的過程中發掘新的網址而處于不同的狀態。

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

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

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

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

圖2 二級URL哈希映射

1.3 任務調度策略

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

1.3.1 優先級隊列設計

維護優先級隊列PRIORITY＿QUEUE 這樣一個數據結構來存儲所有主題任務的優先級。隊列中存儲爬取任務和任務對應的優先級。任務可以是某一個爬取主題，也可以細化到粒度為URL的具體爬行目標。如果某一個主題下的所有網址的優先級都相同，則該任務在優先級隊列中以爬取主題存儲，否則細化到單一的URL存儲，這樣能夠提高優先級劃分的靈活性。任務控制塊QUEUE＿MCB，優先級隊列結點QUEUE＿NODE和指針數組QueueArray［］的相互關系見圖X。

定義優先級隊列PRIORITY＿QUEUE 表為一個五元組形式

其中IDtask是任務標識符，采用N 位無符號整型，具體設計由實際任務規模決定。IDtheame表示URLFORM 所屬的主題，稱作主題標識符，當任務的粒度G 為false時才有意義。P 表示隊列中任務的優先度，采用M 位整型存儲。G是任務的粒度，為true表示粒度為主題，為false表示粒度為主題下所包含的URL。TN 隊列上的任務數，是動態可變化的。UMAP 與G 聯合起來使用，采用Map數據結構存儲，該Map中KEY 表示主題的任務標識符IDtask，VALUE 為CHARSEQUECE 類型，存儲主題任務標識符為IDtask且優先級為P 的URL的SURT 格式，當G 為false時UMAP 才有意義。

定義隊列控制塊QUEUE＿MCB的數據結構為一個八元組形式

其中IDtask是任務標識符，它是任務的唯一標志。TN 是任務名稱 （task name），TD 是任務的描述信息 （task description），ST 是分配給此任務的時間片長度 （slice total），SR是在一個時間段內此任務執行的剩余時間段長度 （slice remain），SI 是 任 務 執 行 的 狀 態 信 息 （task state information），CP 是堆棧指針，用于保存任務上下文 （task context P）。TD 是任務延時 （task delay）。優先級隊列的詳細結構設計如圖3所示。

圖3 任務優先級隊列

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

1.3.2 任務調度算法描述

隊列控制塊中唯一表示任務標示符的是TaskID，Slice＿Total用來保存分配到TaskID 所表示的任務的時間區間大小，Slice＿Remain表示任務執行的剩余時間，這兩項用來實現任務的時間片輪轉調度。

算法1：任務初始化

輸入：可調度任務task，預分配的爬取時間段time＿schedule

輸出：任務執行隊列scheduleTaskQueue

算法2：任務調度過程

輸入：任務執行隊列scheduleTaskQueue，優先級隊列priorityQueue

輸出：FOR each crawlSubTask∈scheduleTaskQueue

算法3：搶奪式調度

輸入：待調度的任務task＿pending，正在運行任務task＿crawling，優先級隊列priorityQueue

輸出：啟動后臺線程并進行輪詢監控

啟動后臺線程并進行輪詢監控

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

2 系統實現與結果分析

該多主題的分布式爬蟲系統采用一個功能節點，兩個能力節點進行測試，需要一臺架構服務器，和兩臺能力服務器。其中功能節點用于收集各能力節點的負載情況，來分發任務，維持分布式系統的負載均衡狀況。兩個能力節點采用不同的任務調度方式，進行多主題爬蟲。表1是節點的規格型號和技術參數說明。

表1 系統測試環境參數說明

對于傳統的分布式爬蟲，系統運行時間是24小時，到次日凌晨時會重啟爬蟲，對于優先級隊列的分布式爬蟲，在一輪調度完成之后，會重啟爬蟲，給定測試時間為24小時，此次試驗主要設計爬取稅收領域的3個主題，稅收經驗，每日動態，重點稅源，每一類主題在數據庫中配置了相應的網址，可對網址進行更新修改。

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

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

表2 單個節點爬蟲結果對比

圖4 爬蟲結果總體對比

3 結束語

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

［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）.［梁根，秦勇，郭小雪，等.基于動態多處理節點的分布式系統任務調度 ［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 算法的分布式爬蟲調度策略 ［J］.計算機應用研究，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集群系統的負載均衡算法 ［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）.［耿曉中.基于多核分布式環境下的任務調度關鍵技術研究 ［D］.吉林：吉林大學，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）.［白鶴，湯迪斌，王勁松.分布式多主題網絡爬蟲系統的研究與實現 ［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）.［孟祥乾，葉允明，登斌.基于流水線負載平衡模型的并行爬蟲研究［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）.［柳少峰，董劍，吳智博.一種基于優先級隊列的集群動態反饋調度算法 ［J］.智能計算機與應用，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信息采集關鍵技術研究 ［D］.哈爾濱：哈爾濱工業大學，20011：28－31.］

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