基于雙緩沖的分布式爬蟲調度策略的設計與研究*

盧照 師 軍 張耀午 王 琦

（1.運城學院數學與信息技術學院 運城 044000）（2.陜西師范大學計算機科學學院 西安 710100）

1 引言

網絡信息以指數級的速度增長，面對如此海量的數據信息，如何保證數據采集的完整性與實時性將是一個很大挑戰。目前主流開源爬蟲框架在網絡通信開銷上優化甚少，缺乏一個有效的方案減少網絡開銷問題。大量的通信開銷不但給服務器帶來巨大的壓力，也在很大程度上限制了并行系統，使之性能無法得到充分的發揮。

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

2 分布式框架介紹

2.1 開源爬蟲框架介紹

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

2.2 分布式爬蟲架構

分布式爬蟲系統通常分為主從式與對等式這兩種架構形式。主從式架構通常由一臺性能強勁的Master 主服務器與多臺Slave 從服務器構成，主服務器負責分配待抓取的URL 任務到每臺從服務器上，并協調各個Slave節點的任務負載，由于主節點通常對硬件要求苛刻，往往會成為分布式系統的瓶頸。對等式架構所有爬蟲節點在分工與運作邏輯是一致的，去中心化的設計使得分布式系統具有更強的處理能力和可靠性，服務器對硬件的要求比主從架構要求低。

2.3 負載均衡策略

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

3 雙緩沖的分布式調度設計

3.1 設計思想

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

3.2 設計架構

基于Scrapy-Redis 框架進行二次開發，采用Python 語言作為編碼語言。系統采用對等式架構設計，每一個爬行器都是一個邏輯獨立的個體，沒有主從角色之分［9］。每一個節點都能夠獨立實現任務的爬取、網頁的解析、內容的存儲以及任務與狀態信息的共享。利用Zookeeper作為爬行器之間狀態信息交換的媒介，采用Redis 作為分布式爬蟲的判重信息與任務信息交換的媒介［10］。

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

圖1 Scheduler功能結構圖

“集群通信模塊”通過固定訪問頻率來進行節點之間狀態信息交換，這能使得遠程頻率較為均勻，不會使服務端出現訪問壓力大幅度波動，有利于提高分布式系統的穩定性［11］。

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

圖2 節點狀態轉換圖

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

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

智能隊列模塊采用“策略設計模式”，它會通過固定訪問頻次來分析其他節點的狀態進行負載量計算，通過連通器水平衡原理計算出運載量［13］。當運載量為正值時，從本地隊列尾部獲取任務后壓縮為一次請求上傳到遠端隊列上，當運載量為負值時，從遠端隊列獲取任務并放入本地隊列尾端，負載轉移流程如圖3所示。

圖3 負載量轉移流程圖

爬蟲負載任務量的多少決定了節點的負載壓力。當爬取速度達到吞吐量頂峰時，負載的壓力幾乎不影響任務處理的吞吐量。負載均衡主要工作是分攤各節點的多余負載量，所以對算法收斂速度要求不會太苛刻，重點在減少通信交互次數。本文通過一個雙向隊列實現塊狀運輸，負載均衡模塊會伴隨心跳對任務量進行計算，將多余的任務量從隊列的尾端取出后壓縮為一次請求放入遠程隊列中。去重查詢屬于I/O問題，在操作系統中，通常通過緩存的方式來解決快速設備與慢速設備速度不匹配的問題。可以用爬蟲系統面臨的網絡延遲問題來類比此問題，通過將遠端服務器的查詢結果存儲在本地緩存中，當本地需要再一次查詢去重結果的時候，會在本地緩存中找到上一次訪問記錄，從而避免再一次通過遠程訪問獲得結果，加快了查詢速度。

當進行判重查詢時，會先對BuerFilter（本地去重）進行詢問，當本地無法判斷的情況下將內容繼續發送給BloomFilter（遠端去重）進行去重［14］。在內存中構建本地去重庫，能提升判重的速度，但是內存的資源也是很有限的，通過借鑒操作系統中的LRU（最近最少使用算法）來限定條目數量，讓內存控制在一個合理的范圍，雖然降低了判重命中率，但節省了大量的存儲空間［15］。

LRU算法通過采用有序字典來實現，通過維護一個列表，在列表中存放URL，URL 經過HASH 后對應的地址存放True/False，當查詢一個URL 的時候，會進行反向遍歷查找并刪除，并在列表的尾部重新放入，如此列表的尾部始終為最新查詢信息，列表首部始終為最舊的查詢信息［16］。當列表內存放長度到達限定值時，每次都從列表首部刪去最舊的信息，騰出空間來存放最新的查詢信息。

4 雙緩沖分布式爬蟲的實驗

4.1 實驗平臺介紹

實驗采取模擬網絡延遲，對模擬站點進行爬取來確保結果盡量客觀，減少無關項的干擾。在MacOS 系統下通過“NetworkLinkConditioner”軟件來對網絡延遲進行模擬，它能調用MacOS 底層，能讓整個網絡環境十分貼近真實的網絡延遲。

4.2 數據分析

在帶寬限制為10Mpbs，網絡延遲滿足線性增長的環境下進行訪問測試。每次的測試任務量固定為100 個，延遲增長函數為10ms+N*20ms，其中N 范圍（0～4），共計5 次測量，將測量結果繪制如圖4所示。

圖4 不同延遲對吞吐量的影響圖

通過這組測試，可以觀察到當訪問延遲隨著時間呈線性增長時，吞吐量呈明顯的非線性快速下降，網絡訪問延遲極大的限制了吞吐量，如此低的吞吐量會使得URL 去重效率低下、任務調度緩慢，無法充分發揮分布式系統的優勢。若能越多的抵消訪問延遲的影響，爬取速度收益就越會顯著的提升。

在帶寬限制為10Mpbs，網絡延遲約為50ms 的環境下進行訪問測試，每次的測試任務量固定為1000 個，運載粒度增長函數為10+N*10，其中N 范圍（0～19），共計20 次測量，將測量結果繪制如圖5所示。

圖5 運載粒度對吞吐量的影響圖

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

4.3 實驗結果分析

在帶寬限制為10Mpbs，網絡延遲約為10ms 的環境下，采用三個節點構成的集群進行訪問測試。采用集群監視器實現每秒鐘對爬蟲結果進行一次統計，共計120 次測量。通過調用Python 的matplotlib庫對120次測量數據分析，繪制成圖。該圖x軸為爬取時間（單位：s），y 軸為標簽上的所對應的信息值，實驗結果圖如圖6所示。

圖6 實驗結果圖

LoadBalacing_10ms.json 為僅啟動了負載均衡優化，BuerFilter_10ms.json 為僅啟動了緩存去重優化，None_10ms.json 為沒有優化的結果，Both_10ms.json 為同時采用了負載均衡與緩沖去重優化的結果。結果表明，URL 去重通信開銷的最大，其次是任務調度的開銷。在采用緩沖去重的狀態下，再采用動態平衡大粒度傳輸任務，能使集群獲得近4 倍的吞吐量提升。

5 結語

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