基于雙緩沖的分布式爬蟲調(diào)度策略的設(shè)計(jì)與研究*

盧照 師 軍 張耀午 王 琦

（1.運(yùn)城學(xué)院數(shù)學(xué)與信息技術(shù)學(xué)院 運(yùn)城 044000）（2.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 西安 710100）

1 引言

網(wǎng)絡(luò)信息以指數(shù)級(jí)的速度增長(zhǎng)，面對(duì)如此海量的數(shù)據(jù)信息，如何保證數(shù)據(jù)采集的完整性與實(shí)時(shí)性將是一個(gè)很大挑戰(zhàn)。目前主流開源爬蟲框架在網(wǎng)絡(luò)通信開銷上優(yōu)化甚少，缺乏一個(gè)有效的方案減少網(wǎng)絡(luò)開銷問題。大量的通信開銷不但給服務(wù)器帶來巨大的壓力，也在很大程度上限制了并行系統(tǒng)，使之性能無法得到充分的發(fā)揮。

劉爽等［1］針對(duì)分布式搜索引擎的任務(wù)調(diào)度及負(fù)載均衡問題，提出了基于GNP 算法的分布式爬蟲調(diào)度策略和負(fù)載均衡的方法，利用網(wǎng)絡(luò)延遲建立GNP 坐標(biāo)，通過測(cè)量選擇合適的通信節(jié)點(diǎn)進(jìn)行通訊。這不但提高了集群靈敏度，還減輕了對(duì)服務(wù)端的請(qǐng)求壓力。黃志敏等［2］提出了一種基于Kademlia的全分布式爬蟲集群方法。該方法基于Kademlia 構(gòu)建出了爬蟲集群底層的通信機(jī)制，不僅繼承了Kademlia的多種優(yōu)良性質(zhì)，還設(shè)計(jì)出了具備高擴(kuò)展性、強(qiáng)魯棒性的全分布式爬蟲集群模型。董禹龍等［3］提出了一種主動(dòng)獲取任務(wù)式的分布式網(wǎng)絡(luò)爬蟲方法，通過評(píng)估節(jié)點(diǎn)負(fù)載及運(yùn)行狀況，主動(dòng)向中控節(jié)點(diǎn)申請(qǐng)任務(wù)隊(duì)列。馬蕾等［4］采用Nutch 爬蟲框架和Zookeeper 分布式協(xié)調(diào)服務(wù)，運(yùn)用提取頁面信息算法優(yōu)化提取頁面信息流程，關(guān)鍵詞匹配優(yōu)化算法抓取相關(guān)數(shù)據(jù)。本文以減少通信開銷為突破點(diǎn)，結(jié)合對(duì)等式架構(gòu)任務(wù)被消費(fèi)的特點(diǎn)，提出了任務(wù)在盡量在本地執(zhí)行的優(yōu)化方向。讓原本需要遠(yuǎn)程處理的任務(wù)盡量在本地執(zhí)行，從而減少任務(wù)調(diào)度上的通信開銷。

2 分布式框架介紹

2.1 開源爬蟲框架介紹

Scrapy 是一個(gè)快速、高層次的屏幕抓取和Web抓取框架，該框架耦合度低，任何人均可依據(jù)自己的需求進(jìn)行擴(kuò)展，屬于目前最為火爆的開源爬蟲框架之一。Redis 是一個(gè)完全開源免費(fèi)，遵守BSD 協(xié)議的高性能Key-Value 數(shù)據(jù)庫［5］。Scrapy-Redis 是就是通過利用Redis 實(shí)現(xiàn)共享任務(wù)隊(duì)列與URL 去重集合，使得Scrapy單機(jī)爬蟲項(xiàng)目能夠輕松擴(kuò)展到多臺(tái)機(jī)器上，從而實(shí)現(xiàn)較大規(guī)模的爬蟲集群。但是由于Scrapy-Redis 框架內(nèi)部訪問的設(shè)計(jì)問題通信訪問十分頻繁，從而導(dǎo)致爬取效率低下，網(wǎng)絡(luò)延遲成為了該框架的性能瓶頸。

2.2 分布式爬蟲架構(gòu)

分布式爬蟲系統(tǒng)通常分為主從式與對(duì)等式這兩種架構(gòu)形式。主從式架構(gòu)通常由一臺(tái)性能強(qiáng)勁的Master 主服務(wù)器與多臺(tái)Slave 從服務(wù)器構(gòu)成，主服務(wù)器負(fù)責(zé)分配待抓取的URL 任務(wù)到每臺(tái)從服務(wù)器上，并協(xié)調(diào)各個(gè)Slave節(jié)點(diǎn)的任務(wù)負(fù)載，由于主節(jié)點(diǎn)通常對(duì)硬件要求苛刻，往往會(huì)成為分布式系統(tǒng)的瓶頸。對(duì)等式架構(gòu)所有爬蟲節(jié)點(diǎn)在分工與運(yùn)作邏輯是一致的，去中心化的設(shè)計(jì)使得分布式系統(tǒng)具有更強(qiáng)的處理能力和可靠性，服務(wù)器對(duì)硬件的要求比主從架構(gòu)要求低。

2.3 負(fù)載均衡策略

依據(jù)負(fù)載能否在運(yùn)行前被事先劃分，負(fù)載均衡可分為靜態(tài)與動(dòng)態(tài)兩類［6］。若負(fù)載劃分比例能夠事先被確定，則屬于靜態(tài)負(fù)載均衡，常見的靜態(tài)負(fù)載均衡有簡(jiǎn)單輪詢法、加權(quán)輪詢法、一致性哈希法。若負(fù)載劃分比例僅在運(yùn)行時(shí)才能被確定，則屬于動(dòng)態(tài)負(fù)載均衡，為了避免去中心化方法帶來的通信負(fù)載高、難以擴(kuò)展等問題，“緊鄰法”被廣泛應(yīng)用于解決同構(gòu)網(wǎng)絡(luò)下的動(dòng)態(tài)負(fù)載均衡問題［7］。由于分布式系統(tǒng)可能由性能差異很大的主機(jī)構(gòu)成，且網(wǎng)絡(luò)通信延遲不可預(yù)測(cè)，都使得負(fù)載難以被事先估計(jì)，靜態(tài)負(fù)載均衡算法難以再起作用［8］。本文采用梯度法作為本分布式爬蟲系統(tǒng)的動(dòng)態(tài)負(fù)載均衡算法，它能夠動(dòng)態(tài)均攤各個(gè)節(jié)點(diǎn)多余的負(fù)載，擁有較強(qiáng)的擴(kuò)展性。

3 雙緩沖的分布式調(diào)度設(shè)計(jì)

3.1 設(shè)計(jì)思想

考慮到廣域網(wǎng)上延遲對(duì)爬蟲效率帶來的嚴(yán)重影響，又由于無法改變網(wǎng)絡(luò)延遲這一硬性條件，所以如何減少遠(yuǎn)程服務(wù)器的訪問次數(shù)是提高效率的關(guān)鍵。分布式爬蟲主要的網(wǎng)絡(luò)通信開銷在“URL判重”、“任務(wù)調(diào)度分配”上。所以想要以減輕通信開銷的方式提高集群的運(yùn)作效率，應(yīng)最主要從“URL判重”與“任務(wù)調(diào)度分配”這兩個(gè)通信開銷下手。針對(duì)“對(duì)等式分布式爬蟲”，每個(gè)爬蟲節(jié)點(diǎn)同時(shí)扮演著既是任務(wù)的生產(chǎn)者又是任務(wù)的消費(fèi)者這一特點(diǎn)，可以通過“自產(chǎn)自銷”的方式來減少任務(wù)調(diào)度的通信開銷，節(jié)點(diǎn)依據(jù)自己的消費(fèi)能力，通過動(dòng)態(tài)負(fù)載均衡算法，將多余負(fù)載壓縮為大粒度任務(wù)進(jìn)行傳輸，來能有效的降低通信頻次。結(jié)合互聯(lián)網(wǎng)結(jié)構(gòu)特點(diǎn)與同站點(diǎn)網(wǎng)頁結(jié)構(gòu)相似性，URL在短時(shí)間內(nèi)很可能會(huì)被反復(fù)判重，可以通過本地緩存，記錄URL 判重查詢的結(jié)果，當(dāng)同以URL 被再次查詢時(shí)，就可以不通過遠(yuǎn)程訪問完成URL 判重任務(wù)，從而減低遠(yuǎn)程服務(wù)器訪問壓力，進(jìn)而提升去重的效率。

3.2 設(shè)計(jì)架構(gòu)

基于Scrapy-Redis 框架進(jìn)行二次開發(fā)，采用Python 語言作為編碼語言。系統(tǒng)采用對(duì)等式架構(gòu)設(shè)計(jì)，每一個(gè)爬行器都是一個(gè)邏輯獨(dú)立的個(gè)體，沒有主從角色之分［9］。每一個(gè)節(jié)點(diǎn)都能夠獨(dú)立實(shí)現(xiàn)任務(wù)的爬取、網(wǎng)頁的解析、內(nèi)容的存儲(chǔ)以及任務(wù)與狀態(tài)信息的共享。利用Zookeeper作為爬行器之間狀態(tài)信息交換的媒介，采用Redis 作為分布式爬蟲的判重信息與任務(wù)信息交換的媒介［10］。

這樣的設(shè)計(jì)的好處是節(jié)約成本、擴(kuò)大應(yīng)用范圍，當(dāng)爬行器數(shù)量增多時(shí)，中心交換可能淪為性能的瓶頸。為了解除瓶頸，只需將Redis 與Zookeeper改用集群模式而不用改變爬蟲的配置，如此松耦合的設(shè)計(jì)為部署帶來極大的便利。通過對(duì)Scheduler進(jìn)行擴(kuò)展來實(shí)現(xiàn)分布式，Scheduler主要由智能隊(duì)列模塊、去重模塊、集群通信模塊構(gòu)成，其中“集群通信模塊”負(fù)責(zé)收集與傳遞節(jié)點(diǎn)的狀態(tài)信息，為動(dòng)態(tài)負(fù)載均衡提供前提條件。“智能隊(duì)列模塊”由一個(gè)本地緩沖隊(duì)列與遠(yuǎn)程隊(duì)列訪問接口組成，爬取的任務(wù)在本地緩沖隊(duì)列中“自產(chǎn)自銷”，通過負(fù)載均衡算法將多余負(fù)載壓縮傳遞到其他節(jié)點(diǎn)中。Scheduler 功能結(jié)構(gòu)圖如圖1所示。

圖1 Scheduler功能結(jié)構(gòu)圖

“集群通信模塊”通過固定訪問頻率來進(jìn)行節(jié)點(diǎn)之間狀態(tài)信息交換，這能使得遠(yuǎn)程頻率較為均勻，不會(huì)使服務(wù)端出現(xiàn)訪問壓力大幅度波動(dòng)，有利于提高分布式系統(tǒng)的穩(wěn)定性［11］。

由于訪問延遲不可預(yù)測(cè)，所以“任務(wù)吞吐量”參數(shù)應(yīng)該被動(dòng)態(tài)測(cè)量。但由于動(dòng)態(tài)測(cè)量值抖動(dòng)現(xiàn)象比較嚴(yán)重，不利于集群的穩(wěn)定性，因此通過一個(gè)固定長(zhǎng)度的隊(duì)列來對(duì)采集到的吞吐量信息進(jìn)行收集，之后再對(duì)收集到的信息求平均值，從而獲得較為穩(wěn)定的值。通過這樣的方法，既能夠動(dòng)態(tài)的采集狀態(tài)信息，又能夠輸出穩(wěn)定可靠的值，還能通過控制隊(duì)列的長(zhǎng)度的方式調(diào)整采集的靈敏度。同時(shí)集群通信模塊采用“觀察者設(shè)計(jì)模式”實(shí)現(xiàn)節(jié)點(diǎn)數(shù)量發(fā)現(xiàn)功能，利用Zookeeper的臨時(shí)節(jié)點(diǎn)概念，當(dāng)客戶端連接上Zookeeper 的時(shí)候就會(huì)持續(xù)發(fā)送心跳，從而保持這個(gè)節(jié)點(diǎn)存在［12］。通過對(duì)Zookeeper 進(jìn)行分析，就能得知有多少個(gè)爬蟲正處于上線狀態(tài)，節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖如圖2所示。

圖2 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖

3.3 大粒度傳輸與緩存輔助去重

并行系統(tǒng)看起來就像管道系統(tǒng)，當(dāng)你將不同橫截面積的管道（吞吐量）連接起來，直觀上總系統(tǒng)的吞吐量會(huì)受限于最窄的管道（最小的吞吐量T）并且與其擺放位置有著重要關(guān)系。所以應(yīng)該著重在最窄的管道上進(jìn)行性能優(yōu)化，否則吞吐量提升效果幾乎是微乎其微的。

智能隊(duì)列模塊采用“策略設(shè)計(jì)模式”，它會(huì)通過固定訪問頻次來分析其他節(jié)點(diǎn)的狀態(tài)進(jìn)行負(fù)載量計(jì)算，通過連通器水平衡原理計(jì)算出運(yùn)載量［13］。當(dāng)運(yùn)載量為正值時(shí)，從本地隊(duì)列尾部獲取任務(wù)后壓縮為一次請(qǐng)求上傳到遠(yuǎn)端隊(duì)列上，當(dāng)運(yùn)載量為負(fù)值時(shí)，從遠(yuǎn)端隊(duì)列獲取任務(wù)并放入本地隊(duì)列尾端，負(fù)載轉(zhuǎn)移流程如圖3所示。

圖3 負(fù)載量轉(zhuǎn)移流程圖

爬蟲負(fù)載任務(wù)量的多少?zèng)Q定了節(jié)點(diǎn)的負(fù)載壓力。當(dāng)爬取速度達(dá)到吞吐量頂峰時(shí)，負(fù)載的壓力幾乎不影響任務(wù)處理的吞吐量。負(fù)載均衡主要工作是分?jǐn)偢鞴?jié)點(diǎn)的多余負(fù)載量，所以對(duì)算法收斂速度要求不會(huì)太苛刻，重點(diǎn)在減少通信交互次數(shù)。本文通過一個(gè)雙向隊(duì)列實(shí)現(xiàn)塊狀運(yùn)輸，負(fù)載均衡模塊會(huì)伴隨心跳對(duì)任務(wù)量進(jìn)行計(jì)算，將多余的任務(wù)量從隊(duì)列的尾端取出后壓縮為一次請(qǐng)求放入遠(yuǎn)程隊(duì)列中。去重查詢屬于I/O問題，在操作系統(tǒng)中，通常通過緩存的方式來解決快速設(shè)備與慢速設(shè)備速度不匹配的問題。可以用爬蟲系統(tǒng)面臨的網(wǎng)絡(luò)延遲問題來類比此問題，通過將遠(yuǎn)端服務(wù)器的查詢結(jié)果存儲(chǔ)在本地緩存中，當(dāng)本地需要再一次查詢?nèi)ブ亟Y(jié)果的時(shí)候，會(huì)在本地緩存中找到上一次訪問記錄，從而避免再一次通過遠(yuǎn)程訪問獲得結(jié)果，加快了查詢速度。

當(dāng)進(jìn)行判重查詢時(shí)，會(huì)先對(duì)BuerFilter（本地去重）進(jìn)行詢問，當(dāng)本地?zé)o法判斷的情況下將內(nèi)容繼續(xù)發(fā)送給BloomFilter（遠(yuǎn)端去重）進(jìn)行去重［14］。在內(nèi)存中構(gòu)建本地去重庫，能提升判重的速度，但是內(nèi)存的資源也是很有限的，通過借鑒操作系統(tǒng)中的LRU（最近最少使用算法）來限定條目數(shù)量，讓內(nèi)存控制在一個(gè)合理的范圍，雖然降低了判重命中率，但節(jié)省了大量的存儲(chǔ)空間［15］。

LRU算法通過采用有序字典來實(shí)現(xiàn)，通過維護(hù)一個(gè)列表，在列表中存放URL，URL 經(jīng)過HASH 后對(duì)應(yīng)的地址存放True/False，當(dāng)查詢一個(gè)URL 的時(shí)候，會(huì)進(jìn)行反向遍歷查找并刪除，并在列表的尾部重新放入，如此列表的尾部始終為最新查詢信息，列表首部始終為最舊的查詢信息［16］。當(dāng)列表內(nèi)存放長(zhǎng)度到達(dá)限定值時(shí)，每次都從列表首部刪去最舊的信息，騰出空間來存放最新的查詢信息。

4 雙緩沖分布式爬蟲的實(shí)驗(yàn)

4.1 實(shí)驗(yàn)平臺(tái)介紹

實(shí)驗(yàn)采取模擬網(wǎng)絡(luò)延遲，對(duì)模擬站點(diǎn)進(jìn)行爬取來確保結(jié)果盡量客觀，減少無關(guān)項(xiàng)的干擾。在MacOS 系統(tǒng)下通過“NetworkLinkConditioner”軟件來對(duì)網(wǎng)絡(luò)延遲進(jìn)行模擬，它能調(diào)用MacOS 底層，能讓整個(gè)網(wǎng)絡(luò)環(huán)境十分貼近真實(shí)的網(wǎng)絡(luò)延遲。

4.2 數(shù)據(jù)分析

在帶寬限制為10Mpbs，網(wǎng)絡(luò)延遲滿足線性增長(zhǎng)的環(huán)境下進(jìn)行訪問測(cè)試。每次的測(cè)試任務(wù)量固定為100 個(gè)，延遲增長(zhǎng)函數(shù)為10ms+N*20ms，其中N 范圍（0～4），共計(jì)5 次測(cè)量，將測(cè)量結(jié)果繪制如圖4所示。

圖4 不同延遲對(duì)吞吐量的影響圖

通過這組測(cè)試，可以觀察到當(dāng)訪問延遲隨著時(shí)間呈線性增長(zhǎng)時(shí)，吞吐量呈明顯的非線性快速下降，網(wǎng)絡(luò)訪問延遲極大的限制了吞吐量，如此低的吞吐量會(huì)使得URL 去重效率低下、任務(wù)調(diào)度緩慢，無法充分發(fā)揮分布式系統(tǒng)的優(yōu)勢(shì)。若能越多的抵消訪問延遲的影響，爬取速度收益就越會(huì)顯著的提升。

在帶寬限制為10Mpbs，網(wǎng)絡(luò)延遲約為50ms 的環(huán)境下進(jìn)行訪問測(cè)試，每次的測(cè)試任務(wù)量固定為1000 個(gè)，運(yùn)載粒度增長(zhǎng)函數(shù)為10+N*10，其中N 范圍（0～19），共計(jì)20 次測(cè)量，將測(cè)量結(jié)果繪制如圖5所示。

圖5 運(yùn)載粒度對(duì)吞吐量的影響圖

通過這組測(cè)試，可以了解到隨著運(yùn)載粒度增大，完成1000 個(gè)URL 爬取所消耗的時(shí)間呈現(xiàn)反比例下降，這使得吞吐量提升呈現(xiàn)類拋物線提升，所以運(yùn)載粒度并不是越大越好，應(yīng)根據(jù)情況選擇適合的運(yùn)載粒度。

4.3 實(shí)驗(yàn)結(jié)果分析

在帶寬限制為10Mpbs，網(wǎng)絡(luò)延遲約為10ms 的環(huán)境下，采用三個(gè)節(jié)點(diǎn)構(gòu)成的集群進(jìn)行訪問測(cè)試。采用集群監(jiān)視器實(shí)現(xiàn)每秒鐘對(duì)爬蟲結(jié)果進(jìn)行一次統(tǒng)計(jì)，共計(jì)120 次測(cè)量。通過調(diào)用Python 的matplotlib庫對(duì)120次測(cè)量數(shù)據(jù)分析，繪制成圖。該圖x軸為爬取時(shí)間（單位：s），y 軸為標(biāo)簽上的所對(duì)應(yīng)的信息值，實(shí)驗(yàn)結(jié)果圖如圖6所示。

圖6 實(shí)驗(yàn)結(jié)果圖

LoadBalacing_10ms.json 為僅啟動(dòng)了負(fù)載均衡優(yōu)化，BuerFilter_10ms.json 為僅啟動(dòng)了緩存去重優(yōu)化，None_10ms.json 為沒有優(yōu)化的結(jié)果，Both_10ms.json 為同時(shí)采用了負(fù)載均衡與緩沖去重優(yōu)化的結(jié)果。結(jié)果表明，URL 去重通信開銷的最大，其次是任務(wù)調(diào)度的開銷。在采用緩沖去重的狀態(tài)下，再采用動(dòng)態(tài)平衡大粒度傳輸任務(wù)，能使集群獲得近4 倍的吞吐量提升。

5 結(jié)語

傳統(tǒng)上幾乎是通過類似多線程或是異步并發(fā)等方式［9］，設(shè)法避開網(wǎng)絡(luò)延遲帶來的阻塞影響，這是一種提高吞吐量的可行方法，但是無法做到低成本。本文以降低通信開銷為優(yōu)化方向，通過“基于雙緩沖的大粒度任務(wù)傳輸策略”與“基于高速緩存原理的本地緩存輔助去重方案”對(duì)分布式爬蟲進(jìn)行優(yōu)化。采用這種方式的最大價(jià)值是它與傳統(tǒng)方法并不沖突，甚至是可以與傳統(tǒng)方法協(xié)同工作的。我們依然能利用多線程或是異步并發(fā)方式，使得吞吐量得到更進(jìn)一步的提升。