基于協(xié)程模型的分布式爬蟲框架

楊濟運+劉建勛+姜磊+彭桃+文一憑+盧廳

收稿日期：2013-05-28

基金項目：國家自然科學基金項目（61272063，61100054）；教育部新世紀優(yōu)秀人才支持計劃項目（NCET-10-0140）；教育部人文社科基金項目（12YJCZH084）；湖南省教育廳資助項目（12C0119）；湖南省科技計劃項目（2013FJ3002）；湖南科技大學資助項目（E51368）

作者簡介：楊濟運（1990—），男，浙江溫嶺人，碩士研究生，研究方向：網(wǎng)絡(luò)輿情。

通訊聯(lián)系人，E-mail：iamyoung001@gmail.com

文章編號：1003-6199（2014）03-0126-08

摘 要：網(wǎng)絡(luò)爬蟲主要受到網(wǎng)絡(luò)延遲和本地運行效率的限制，傳統(tǒng)的基于多線程的網(wǎng)絡(luò)爬蟲架構(gòu)主要為了消除網(wǎng)絡(luò)延遲而沒有考慮到本地運行效率。在高并發(fā)的條件下，多線程架構(gòu)爬蟲由于上下文切換開銷增大而導致本地運行效率降低，同時使得網(wǎng)絡(luò)利用率下降，如何能夠在最大化利用網(wǎng)絡(luò)資源的情況下減小系統(tǒng)本地開銷是一個需要研究的問題。針對以上問題，本文提出基于協(xié)程的分布式網(wǎng)絡(luò)爬蟲框架來解決，從開銷、資源利用率、網(wǎng)絡(luò)利用率上對協(xié)程框架和多線程框架進行了分析，并基于協(xié)程實現(xiàn)了一個分布式網(wǎng)絡(luò)爬蟲。實驗表明該框架無論從開銷、資源利用率和網(wǎng)絡(luò)利用率上相對于多線程框架有比較明顯的優(yōu)勢。

關(guān)鍵詞：協(xié)程；分布式；高性能；爬蟲

中圖分類號：TP311 文獻標識碼：A

A Distributed Crawler Framework Based on Coroutine Model

YANG Ji-yun， LIU Jian-xun， JIANG Lei，PENG Tao， WEN Yi-ping，LU Ting

（Key Laboratory of Knowledge Processing and Networked Manufacturing，

Hunan University of Science and Technology， Xiangtan，Hunan 411201， China）

Abstract：Web crawler is mainly limited by the network latency and local resource. The traditional framework of web crawler， which is based on multi-threads， is mainly to eliminate the network latency but failed to take the local resource limitation into account. Under the high concurrent， multi-threads architecture will result in a poor running efficiency because of the increasing of the context switch. So studying on how to make maximum usage of network resources and also considering the local resource limitation becomes a necessary. To solve the above problems， this paper will propose a distributed crawler framework based on coroutine. First we have analyzed the overhead， resource utilization and network utilization between coroutines and threads， and implemented a web crawler based on coroutine. Experiments had shown that our architecture for a distributed web crawler based on coroutine is better than threads-based web crawler.

Key words：coroutine；distribution；high-performance；web crawler

1 引言

隨著互聯(lián)網(wǎng)發(fā)展，尤其是近幾年網(wǎng)絡(luò)上的用戶自己創(chuàng)造內(nèi)容（UGC）和社交網(wǎng)絡(luò)的發(fā)展，數(shù)據(jù)呈爆炸式增長。自2003年開始，中國的網(wǎng)頁規(guī)模基本保持翻番增長，2010年網(wǎng)頁數(shù)量達到600億個，年增長率為78.6%[1]。由于網(wǎng)絡(luò)的增速發(fā)展導致一年產(chǎn)生的信息量比以往所有信息量的總和還要多。這對搜索引擎提出了更高的要求，搜索引擎必須能在不降低搜索質(zhì)量的前提下索引比以往更多的數(shù)據(jù)，而作為搜索引擎的基礎(chǔ)組件的網(wǎng)絡(luò)爬蟲必須能夠在較短的時間內(nèi)完成對目標網(wǎng)絡(luò)的收集。

網(wǎng)絡(luò)爬蟲的工作原理如下： 從一個初始URLs集（稱為種子URLs）出發(fā)， 從中獲取一個URL ，下載網(wǎng)頁， 從網(wǎng)頁中抽取所有的URLs ， 并將新的URLs添加到URLs隊列中。然后爬蟲從隊列中獲取另一個URL。重復剛才的過程， 直到爬蟲達到某種停止標準為止[2]。

尹江等[3]提出目前爬蟲的自身瓶頸主要受到網(wǎng)絡(luò)延時和本地運行效率的限制，而兩者主要表現(xiàn)為程序本地化資源占用、程序切換開銷和網(wǎng)絡(luò)利用率問題。為了突破網(wǎng)絡(luò)延時的限制，目前絕大部分的爬蟲系統(tǒng)采用阻塞同步模型（多線程模型）的設(shè)計，以充分利用網(wǎng)絡(luò)帶寬，大部分的網(wǎng)絡(luò)爬蟲都是基于多線程的架構(gòu)[4]。然而這并不能完全疏通爬蟲的效率瓶頸[5]，周德懋等[6]指出使用多線程模型在隨著連接的增多，線程的切換將是一個很大的開銷。李曉明等[7]提出為最大化利用網(wǎng)絡(luò)資源，同時縮短線程執(zhí)行周期，應該使用非阻塞異步I/O模型而非阻塞同步模型。但是基于事件的非阻塞異步I/O模型編程比較復雜，在絕大部分連接處于活動的狀態(tài)下會有輪詢的開銷，并且在事件響應的時候有驚群現(xiàn)象。因此雖然非阻塞異步I/O模型相對于多線程模型有更好的性能，但是由于難度較大，僅有少數(shù)爬蟲使用[8]。

針對現(xiàn)有爬蟲問題，需要使用非阻塞異步I/O模型來盡可能的提高網(wǎng)絡(luò)利用率，同時兼顧本地資源使用和程序切換開銷，由此本文提出了基于協(xié)程分布式網(wǎng)絡(luò)爬蟲架構(gòu)。協(xié)程是一種程序組件，是由子例程（過程、函數(shù)、例程、方法、子程序）的概念泛化而來的，子例程只有一個入口點且只返回一次，而協(xié)程允許多個入口點，可以在指定位置掛起和恢復執(zhí)行[9]。從定義可見協(xié)程是一個程序組件如同線程和進程，但是屬于非阻塞異步I/O模型，線程和進程并發(fā)是多個子例程通過操作系統(tǒng)時間片輪轉(zhuǎn)來實現(xiàn)，而協(xié)程是單個子例程通過用戶自己控制調(diào)度實現(xiàn)并發(fā)。協(xié)程由于自己控制調(diào)度，無需CPU參與，可以減少大量的無用切換開銷，并且由于本身輕量級，切換開銷也比較小，并且其由于非阻塞異步I/O模型而具有更高的網(wǎng)絡(luò)利用效率。

本文的組織結(jié)構(gòu)為：第2節(jié)將簡要介紹相關(guān)工作；第3節(jié)給出了爬蟲的設(shè)計框架和設(shè)計細節(jié)；第4節(jié)介紹協(xié)程與多線程的對比；第5節(jié)為實驗和分析，以驗證框架的可行性和有效性。最后對全文進行了總結(jié)，并展望了下一步的工作。

2 相關(guān)工作

爬蟲的歷史非常久遠，爬蟲的編程模型也經(jīng)過多種變化，在本節(jié)首先對于爬蟲模型的變化進行介紹再介紹，之后提出目前爬蟲的不足與本文解決方案相關(guān)的研究。

2.1 基于多進程框架的網(wǎng)絡(luò)爬蟲

網(wǎng)絡(luò)爬蟲從早期網(wǎng)絡(luò)剛開始萌芽的時候就誕生了，剛開始使用的是多進程模型，此時僅僅是考慮多并發(fā)來利用網(wǎng)絡(luò)，沒有考慮爬蟲的擴展性問題。具有代表性的為1993年提出來的RBSE spider[10]，1994年提出的MOMspider[11]。這個階段的爬蟲為了克服單線程的I/O等待問題，引入了多進程并發(fā)，MOMspider通過15個進程進行并發(fā)爬取，然而這時候的爬蟲沒有對系統(tǒng)的可擴展性和同步進行設(shè)計。由于受到當時硬件和進程本事占用資源的限制，爬蟲的并發(fā)數(shù)處于很低的狀態(tài)，只能說部分解決了I/O等待問題。

2.2 基于異步非阻塞的網(wǎng)絡(luò)爬蟲

為了提升效率，爬蟲開始使用異步I/O模型，最開始采用的是在1997提出的Internet Archive[12]和1998年Google的早期爬蟲[13]。Internet Archive的每個爬蟲使用64個異步下載端進行并行爬取，并抽取鏈接。早期的Google爬蟲系統(tǒng)使用單線程的異步I/O模型，一次維持300個連接并行爬行。

但是由于早期使用的異步機制是聽過監(jiān)聽事件來實現(xiàn)，與順序編程模型有比較大的不同，導致爬蟲與存儲組件、分發(fā)組件等結(jié)合比較麻煩。

2.3 基于多線程框架的網(wǎng)絡(luò)爬蟲

由于使用異步I/O模型需要程序員自己對線程進行控制，網(wǎng)絡(luò)規(guī)模越來越大，導致使用異步模型更加的復雜，而同步I/O模型將線程的管理交給了操作系統(tǒng)，從編程模式上相對于異步I/O模型使用比較簡單[14]，從可擴展性上考慮，爬蟲開始使用多線程模型，這個模型也被沿用至今。這個期間的代表爬蟲為1999年設(shè)計的Mercator和2004年設(shè)計的Ubicrawler。Mercator采用Java的多線程同步方式實現(xiàn)并行處理，并加入了很多優(yōu)化策略如DNS緩沖、延遲存儲等以提升爬蟲運行效率。Ubicrawler主要是通過對爬蟲進行完全分布性和高容錯性的實現(xiàn)來消除單點故障。

2.4 現(xiàn)有爬蟲架構(gòu)不足

互聯(lián)網(wǎng)飛速發(fā)展，網(wǎng)絡(luò)的規(guī)模翻番增長，傳統(tǒng)使用的多線程爬蟲碰到了越來越多的問題。首當其沖就是多線程上下文切換導致系統(tǒng)性能降低的問題。由于機器性能和網(wǎng)絡(luò)帶寬的發(fā)展，單臺機器的線程并發(fā)數(shù)相對于以前提高不少數(shù)量級，上下文開銷隨著并發(fā)數(shù)的提高變得越來越大。很多學者開始研究多線程之外的選擇，Ding等[15]于2006年使用異步I/O方式實現(xiàn)了分布式爬蟲，取得了滿意的效果。Li等人[16]于2007年發(fā)現(xiàn)線程上下文切換對于系統(tǒng)運行效率影響隨著系統(tǒng)負載的增加而增加，在高并發(fā)的條件下，上下文切換會成為性能殺手。Yin等[20]2008年做了同步模型與異步模型的對比，發(fā)現(xiàn)異步模型相對同步模型獲得了比較大的提升。Zhou等[17]在2009年提出隨著連接的增多，線程的切換將是很大的開銷，非阻塞異步I/O模型具有擴展性強、性能優(yōu)越等特點是高性能網(wǎng)絡(luò)編程的最佳選擇。Shaver等[3]在2012年提出高并發(fā)條件下，協(xié)程計算模型是更優(yōu)的選擇。

由以上工作可知：網(wǎng)絡(luò)爬蟲的編程架構(gòu)從多進程架構(gòu)變化到多線程，而近幾年的研究從多線程轉(zhuǎn)為異步非阻塞模型。相對于多線程模型，單線程異步模型利用消息通知機制從而使網(wǎng)絡(luò)利用率上更高，隨著時間的推移更多的消息組件和存儲組件開始支持異步事件監(jiān)聽機制。但是由于事件監(jiān)聽機制在高并發(fā)條件下需要對本地維持的連接進行輪訓來，也使得效率下降。

2.5 協(xié)程相關(guān)研究

協(xié)程最先由conway等[18]提出，后來由Donald Knuth對協(xié)程進行定義：子例程是協(xié)程的特例[19]。協(xié)程的創(chuàng)建是在用戶態(tài)通過保存棧的狀態(tài)實現(xiàn)的，無需內(nèi)核的參與使得協(xié)程的創(chuàng)建速度非?？?，甚至有些通過拋棄棧用程序代碼執(zhí)行位置來記錄協(xié)程狀態(tài)，稱為Stackless Coroutine，本文即使用這種模型。由于協(xié)程是在用戶態(tài)通過棧實現(xiàn)，協(xié)程占用的資源相對于線程也非常小。

表1是協(xié)程與事件監(jiān)聽模型在實現(xiàn)上的對比，可以看到協(xié)程通過yield關(guān)鍵字來切換，而事件監(jiān)聽模型是通過對于事件的監(jiān)聽來調(diào)用相應的回調(diào)函數(shù)，但是模型跟復雜，也不容易與其他組件結(jié)合。而線程調(diào)度由CPU控制，對于用戶不可見，由此產(chǎn)生低效。通過用戶層來模擬CPU調(diào)度，協(xié)程大大降低了切換的開銷，由此降低了程序的運行開銷。程序由用戶自己控制調(diào)度，由此也使得程序減少了無謂的切換，使得資源利用率更高。I/O bound是指程序運行時間主要在等待I/O完成的時間上，而爬蟲就是I/O bound問題。協(xié)程在碰到I/O等待的時候，自動切換到另外一個協(xié)程而無需用戶介入，這種機制非常適合I/O bound場景，由此想到使用協(xié)程來解決目前爬蟲所碰到的問題。

miller等[11]對于協(xié)程進行了全方面的闡述，并指出協(xié)程是未來發(fā)展的方向，edward[12]指出在并發(fā)編程中，由于線程的很多問題，應該以協(xié)程作為開發(fā)的第一選擇。Xiao等[2]研究了協(xié)程在線程交互之間的使用，相對于使用線程獲得了非常大的提升；Shaver等[3]詳細介紹了協(xié)程的計算模型Nanz等[1]提出在分布式計算中應該使用協(xié)程來解決當前碰到的分布式問題。

表1 協(xié)程與基于事件監(jiān)聽的異步模型對比

3 基于協(xié)程的分布式爬蟲框架

本節(jié)，首先將討論一個爬蟲架構(gòu)所需要的一些目標，然后給出本文框架的詳細設(shè)計。

設(shè)計一個爬蟲需要滿足以下幾個目標：

低消耗和高性能：這是爬蟲內(nèi)在屬性的需求，爬蟲需要盡可能的使用最小的資源達到最高的性能。這里指的消耗不僅僅是爬蟲對于一個頁面的爬取時間消耗，同樣也是爬取一個頁面對系統(tǒng)資源的消耗。

健壯性：健壯的爬蟲需要能夠容忍一些節(jié)點的失敗，對于一些關(guān)鍵數(shù)據(jù)進行多臺冗余備份，防止單點故障，具體采用集群方案來進行冗余備份和提高性能。

速度可控：對于服務器管理者來說，他們會使用一些策略來限制爬蟲的并發(fā)連接和速度。如果爬蟲速度比較快，對于同一臺服務器進行頻率比較高的訪問，會影響服務器的對外服務能力。為了對服務器友好，針對單臺服務器本文設(shè)計了一種頻率控制算法，算法如表2：

表2 頻率控制算法

爬蟲獲得一個服務器的連接地址，第一次根據(jù)配置文件中設(shè)置的爬取間隔爬取，以后根據(jù)頻率控制算法動態(tài)調(diào)整。

可擴展性：現(xiàn)在網(wǎng)絡(luò)的數(shù)據(jù)量非常的大，單臺機器遠遠不能滿足對于爬取的需求，一個爬蟲的可擴展性成為現(xiàn)在爬蟲的基本需求[17]。理想的爬蟲的爬取數(shù)據(jù)隨著機器數(shù)量的增加而線性增長。通過設(shè)計消息隊列來分發(fā)任務，將消息的動態(tài)調(diào)整和管理交給了隊列，由此形成一個server-worker消息分發(fā)模型，基本形成了添加機器對于系統(tǒng)效率的線性提升。

通過以上的目標描述，現(xiàn)介紹基于協(xié)程的爬蟲框架具體實現(xiàn)方案及實現(xiàn)以上爬蟲目標所開展的具體工作。

圖1是爬蟲的框架圖，整體主要由9部分組成。整個數(shù)據(jù)流向為：首先從隊列取出一個URL，并經(jīng)過驗證模塊，如果網(wǎng)頁有訪問限制 （需要用戶名、密碼），從配置文件中讀取用戶名、密碼進行驗證，經(jīng)過驗證之后將URL發(fā)送到非阻塞異步下載模塊。待網(wǎng)頁下載完成之后，對網(wǎng)頁進行解析，將解析出來的內(nèi)容存入MySQL集群，MySQL集群主要存儲今后需要處理的數(shù)據(jù)；解析出來的鏈接發(fā)送到連接檢查器，主要對新解析出來的連接進行去重。調(diào)度模塊根據(jù)下載情況和隊列情況對隊列內(nèi)容進行動態(tài)調(diào)整。日志模塊會對爬蟲的工作情況、爬取工作時間、失敗和錯誤等信息進行記錄。Redis集群作為連接檢查器的后端存儲。消息隊列來負責分發(fā)url數(shù)據(jù)，由此獲得線性擴展。

A.認證模塊

我們的爬蟲盡可能作為一個通用的框架，使用戶可以對于不同的網(wǎng)絡(luò)對象進行爬取，而不僅僅是針對網(wǎng)絡(luò)頁面，認證模塊主要是針對社交網(wǎng)絡(luò)的爬取。由于社交網(wǎng)絡(luò)需要認證才能進行公開流爬取，一般社交網(wǎng)絡(luò)通過OAuth來進行認證，通過將Oauth數(shù)據(jù)存儲于文件中，在Oauth過期之前，對認證信息進行存儲，下次認證直接從文件中讀取。這個模塊中默認內(nèi)置了Twitter和新浪微博的OAuth模塊，為了擴展性，預留了user_login接口，這個接口是對需要認證的網(wǎng)頁提供用戶名、密碼。對于不同的網(wǎng)絡(luò)對象，可以對這個接口進行覆寫達到認證的目的。

B.協(xié)程下載模塊

這是爬蟲最耗時的部分，通過對于不同模型的分析，最終選擇使用協(xié)程機制來作為爬蟲的實現(xiàn)機制。

爬蟲運行過程中，I/O耗費時間記為Ti，而對于進入I/O等待和I/O等待結(jié)束之后的處理時間之和記為Tc，將Tc和Ti之比Tc/Ti記為T。在網(wǎng)絡(luò)帶寬比較小的情況下，Tc相對于Ti是一個很小的開銷，即T是一個很小的值，在這種情況下，需要關(guān)注的是如何最大化利用網(wǎng)絡(luò)而無需關(guān)心本地運行資源。隨著帶寬的增大，程序的并發(fā)數(shù)也越來越大，Ti變得越來越小，T的值變得越來越大，此時本地運行資源消耗變成不得不考慮的問題，協(xié)程就是在高并發(fā)條件下非常好的解決資源和開銷問題的解決方案。

如果有兩個線程A和B，A和B在單獨運行時都需要10 秒來完成自己的任務，而且任務都是運算操作，A、B 之間也沒有競爭和共享數(shù)據(jù)的問題。現(xiàn)在A、B兩個線程并行，操作系統(tǒng)會不停的在A、B兩個線程之間切換，達到一種偽并行的效果，假設(shè)切換的頻率是每秒一次，切換的成本是0.1秒，總共需要 20 + 19 * 0.1 = 21.9 秒，此時每個線程的T值為0.095（1.9/2/10=0.095）。如果使用協(xié)程的方式，由于可以用戶控制調(diào)度，先運行協(xié)程A，A結(jié)束的時候讓位給協(xié)程B，只發(fā)生一次切換，總時間是20 + 1 * 0.1 = 20.1 秒，此時對于每個協(xié)程T值為0.005（0.1/2/10=0.005）。從運行時間和T值上都可以看到協(xié)程相對于線程的優(yōu)勢。

C.HTML解析器

HTML解析器主要使用多策略聯(lián)合頁面抽取算法[18]對網(wǎng)頁進行解析。通過基于libxml對網(wǎng)頁內(nèi)容進行分析，將網(wǎng)頁原始內(nèi)容讀入內(nèi)存構(gòu)建DOM樹，利用頁面抽取算法提取頁面正文存入MySQL集群。對網(wǎng)頁中的鏈接通過正則表達式來匹配，對抽取出的連接送到鏈接檢查模塊進行下一步處理。

D.連接檢查模塊

連接檢查模塊有兩個功能：一是對新抽取的鏈接進行檢查，是不是已經(jīng)爬取過這個連接；二是對這個新的鏈接進行檢查，是不是一個有效的連接。通過對鏈接進行hash計算，將對應的值存入redis集群的set中進行檢查是否已經(jīng)是被爬取過，如果是未爬取過的鏈接，將檢查其有效性，最終生成鏈接、錯誤代碼和錯誤次數(shù)的三元組，將其發(fā)往調(diào)度模塊做下一步處理。

E.調(diào)度模塊

調(diào)度模塊對收到的三元組組做下一步處理。造成從連接檢查模塊返回過來錯誤的原因有很多，可能是由于對方服務器的暫時宕機或者網(wǎng)絡(luò)不通形成的，所以需要對這些連接進行多次查詢。如果是正常的鏈接，將其發(fā)送到redis集群中，消息隊列將從中取出數(shù)據(jù)進行內(nèi)容分發(fā)。對于返回錯誤信息的三元組，將其發(fā)給日志模塊做進一步處理。

F.日志模塊

日志模塊從調(diào)度模塊接收三元組，檢查code的值，如果是404、410等，將這些記錄到日志文件中；如果code是500、503等，通過對三元組擴充，添加等待時間稱為四元組，將這個四元組發(fā)給連接檢查模塊。

G.Redis集群

Redis作為內(nèi)存數(shù)據(jù)庫，訪問速度非常快，同時具有持久化功能，非常適合高速的處理。Redis內(nèi)置數(shù)據(jù)結(jié)構(gòu)比較豐富，內(nèi)置set是一個非常好的查重功能模塊，時間復雜度為O（1）。使用Redis作為系統(tǒng)鏈接檢查模塊的后端存儲和消息隊列的持久化方案，由于Redis目前還沒有原聲支持集群功能，通過實現(xiàn)一致性hash算法，對生成鏈接的hash值進行分發(fā)達到集群功能。

H.MySQL集群

MySQL集群主要用來爬取出來的內(nèi)容進行存儲。單臺MySQL機器容易造成單點故障，用集群解決這個問題，而且集群訪問速度相比單臺更快，本文框架中使用的集群由2個master和3個slaver組成。

I.消息隊列

目前有很多消息隊列產(chǎn)品，如apache的ActiveMQ，vmware的RabbitMQ，但是由于使用性和擴展上比較復雜，沒有可持續(xù)化的功能，本文中實現(xiàn)了一個基于Redis的消息隊列來進行任務的分發(fā)，存取數(shù)據(jù)通過http進行。由于不同機器之間沒有其他消耗，使用消息隊列基本上達到了下載速度跟機器成線性增長。

4 協(xié)程與線程對比

本節(jié)將對協(xié)程與多線程爬蟲框架在本地利用效率、CPU開銷和網(wǎng)絡(luò)利用率上進行對比。

4.1 本地資源效率對比

從進程組成來看，一個進程是一個多元組，P=（p，h，f，c，s）。其中P代表進程；p是可執(zhí)行的程序代碼、程序數(shù)據(jù)與堆棧；h和f分別是執(zhí)行程序代碼需要的硬件和軟件資源；硬件資源包括CPU、特殊功能寄存器、內(nèi)存和磁盤等；軟件資源包括內(nèi)核數(shù)據(jù)結(jié)構(gòu)以及相關(guān)所有信息資源；s代表進程運行的各種狀態(tài)；c是程序運行期間需要的控制信息。

從進程創(chuàng)建過程來看，進程創(chuàng)建所需要的時間和資源比較多；而從CPU執(zhí)行程序需要的上下文考慮，只需要程序計數(shù)器、執(zhí)行堆棧、通過寄存器和狀態(tài)標志，由此對于進程單位進行細分形成線程。而協(xié)程通過外部控制，自己控制堆棧和狀態(tài)，從而更加精簡。如表3所示，線程是一個二元組T=（t，s），其中t是線程代碼、程序數(shù)據(jù)和堆棧；s是線程運行的各種狀態(tài)，而協(xié)程是一元組C=（t），可見協(xié)程所攜帶的數(shù)據(jù)變得越來越少。相對于進程和線程，協(xié)程更加的輕量級，在創(chuàng)建和切換上耗費的資源更小。多線程共享同一地址空間和其他資源，由于線程有進程的某些性質(zhì)，所以被成為“輕量級進程”，而協(xié)程處于同一線程之內(nèi)，共享一個線程數(shù)據(jù)，被稱為“輕量級的線程”。由此可見使用協(xié)程作為爬蟲設(shè)計的方案在本地資源占用上是最優(yōu)選擇。

表3 進程、線程、協(xié)程對比

4.2 CPU開銷對比

在多線程環(huán)境中，CPU進行進程切換時，需要對當前線程的運行環(huán)境進行保存；然后加載需要調(diào)度的下一個線程，最后從程序計數(shù)器指向的位置開始運行。從切換過程可以看到，切換過程涉及到進程環(huán)境保存和恢復，由于進程攜帶的信息比較多，切換開銷比較大。

爬蟲需要進行高并發(fā)連接，如果使用多線程方案，線程之間的切換是個巨大的開銷。創(chuàng)建線程對于資源的需求相對于協(xié)程比較大，服務器創(chuàng)建線程的數(shù)量受到服務器資源的限制。從線程創(chuàng)建所需內(nèi)存、創(chuàng)建的時間和運行效率上看，多線程都不是一個很好的解決方案。線程雖然是對進程進行精簡，降低上下文切換開銷，在高并發(fā)的環(huán)境下依然不能忽視。

協(xié)程由于是自己控制切換與調(diào)度，可以最高效的進行調(diào)度而無需CPU的參與；其次由于協(xié)程本身比較輕量級，在切換開銷上非常的少，是理想的高并發(fā)解決方案。

4.3 網(wǎng)絡(luò)利用率對比

由于協(xié)程通過自主高效的切換管理，可以最大化的利用網(wǎng)絡(luò)，而線程是由CPU調(diào)度導致出現(xiàn)很多網(wǎng)絡(luò)的浪費現(xiàn)象。

圖2是兩種方案在3個并發(fā)數(shù)時的對比，左圖是協(xié)程在一次爬取任務的切換情況，右圖是線程的切換情況。從圖2可以看出，協(xié)程通過自主的高效控制，只在IO等待的時候才進行切換，沒有無效時間的開銷，可以高效的完成一次爬取任務，完成相同的一次任務，協(xié)程方案比線程方案節(jié)省了8t的時間。協(xié)程方案可以在同樣時間內(nèi)獲取更多的數(shù)據(jù)，從而更高的利用了網(wǎng)絡(luò)效率。

綜上所述，在爬蟲應用場景下，協(xié)程是很好的解決方案。

5 實驗分析

基于前面的分析，本節(jié)將對基于協(xié)程的爬蟲架構(gòu)和基于多線程的爬蟲架構(gòu)進行實驗對比，從網(wǎng)絡(luò)利用效率、本地資源占用和CPU開銷進行分析。為了消除外部網(wǎng)絡(luò)不穩(wěn)定對實驗的影響，實驗數(shù)據(jù)采取的是內(nèi)網(wǎng)存儲服務器上的4000000個20k的文件（80G）。本實驗的微機配置如為Intel（R） Core（TM） i3 CPU，3.20GHZ處理器，4G內(nèi)存，操作系統(tǒng)為Ubuntu 12.04，網(wǎng)絡(luò)為10M帶寬共享。由于帶寬限制，過高的并發(fā)數(shù)量將導致網(wǎng)絡(luò)超時，而10M帶寬的理論上限是1250k/s的下載速度，根據(jù)實驗環(huán)境，網(wǎng)絡(luò)利用率對比實驗使用的線程上限是60（1250k/20k=62.5）個。為了測試本地資源效率和CPU開銷，本文做了更高并發(fā)效率的實驗來驗證系統(tǒng)在高并發(fā)條件下的優(yōu)勢。

5.1 本地資源效率對比實驗

在程序本地資源利用方面，主要考察了在不同并發(fā)數(shù)下所占用的內(nèi)存情況，下圖分別顯示了基于協(xié)程與基于線程的爬蟲進程所占用內(nèi)存的情況。從圖3（a）中可以看到常駐內(nèi)存隨著并發(fā)數(shù)的增加呈現(xiàn)近似線性增長，在圖3（b）中看到兩者真實內(nèi)存隨著并發(fā)數(shù)的增加而增加，但是協(xié)程所占用的內(nèi)存相對于線程更少，增加速率也更低，兩者真實內(nèi)存的差值有擴大的趨勢，可見協(xié)程的實現(xiàn)方案想對于線程在內(nèi)存使用上具有占用更低的優(yōu)勢。

5.2 CPU開銷對比實驗

在CPU開銷方面，通過利用不同的并發(fā)數(shù)，來測試CPU上下文切換的開銷情況，通過設(shè)置并發(fā)數(shù)從0到300來進行對比，CPU開銷的計算通過理想運行時間和實際運行時間的比值來衡量。首先介紹程序理想運行時間和實際運行時間，理想運行時間是忽略程序的生成時的初始化和上下文切換時間所計算出來的運行時間，而實際運行時間是程序?qū)嶋H從開始到結(jié)束的運行時間。

由于需要做高并發(fā)的對比實驗，但是由于網(wǎng)絡(luò)限制，過高的并發(fā)數(shù)量會導致網(wǎng)絡(luò)擁塞而出現(xiàn)大量的網(wǎng)絡(luò)超時，并且為了消除網(wǎng)絡(luò)傳輸和文件存儲等開銷對于計算上下文切換的影響，在實驗中將系統(tǒng)中的下載模塊替換為休眠時間5秒鐘。通過30組效果對比，每組做3次試驗來取平均值以盡可能消除系統(tǒng)本身運行對于上下文切換的開銷的影響，試驗結(jié)果如圖4所示，從表中可以看出協(xié)程的開銷一直低于線程的開銷。從并發(fā)數(shù)100開始，線程開銷的增加速度加快，協(xié)程開銷的增加速度相對平穩(wěn)，兩者之間的開銷差距變得越來越大。

由于剛開始并發(fā)數(shù)比較小，CPU對于調(diào)度和切換開銷還在可接受范圍之內(nèi)，隨著并發(fā)數(shù)的增加，CPU對于調(diào)度和上下文的切換開銷變得越來越大，而協(xié)程的調(diào)度不需要CPU參與，所以隨著并發(fā)數(shù)的增加，協(xié)程的開銷并沒有顯著的增加。由此可見，協(xié)程是更適合高并發(fā)的編程模式。

5.3 網(wǎng)絡(luò)利用率對比實驗

對于網(wǎng)絡(luò)資源利用率方面，通過相同時間內(nèi)的數(shù)據(jù)采集量作為對比依據(jù)，由于網(wǎng)絡(luò)是共享的，為了盡可能減少局域網(wǎng)內(nèi)網(wǎng)絡(luò)流量對實驗的影響，將實驗在晚上進行。

圖5（a）是協(xié)程方案和多線程方案在一個周期內(nèi)采集數(shù)據(jù)的對比，分別在不同的時間段進行了10個周期的對比實驗。從圖5中可以看出，在同樣的采集周期之內(nèi)協(xié)程方案能夠比線程方案采集更多的數(shù)據(jù)。在我們實驗的十個周期之內(nèi)，線程方案在一個周期之內(nèi)平均采集了1.71GB的數(shù)據(jù)量，而使用協(xié)程可以采集2.1GB的數(shù)據(jù)量，相比之下協(xié)程可以獲得22. 8%的效果提升。

圖5（b）是網(wǎng)絡(luò)利用效率的累積分布圖。橫軸所表示的是爬蟲的運行周期，以30min為一個爬取周期；縱坐標為爬蟲周期內(nèi)累積所采集的數(shù)據(jù)量，以GB作為單位間隔。經(jīng)過5個小時的爬取，獲取數(shù)據(jù)量的相差為3.793GB。

從上述實驗可以證明，本文中提出的基于協(xié)程的分布式爬蟲框架想對于傳統(tǒng)的線程解決方案具有占用內(nèi)存更低、開銷更小、效率更高等優(yōu)點，尤其是在高并發(fā)條件下，協(xié)程在CPU調(diào)度和上下文切換上的優(yōu)勢更加的明顯。

6 結(jié)論與展望

本文針對傳統(tǒng)爬蟲解決方案在高并發(fā)條件下的的不足提出了一個基于協(xié)程的分布式爬蟲框架，對于爬蟲目前所受到的網(wǎng)絡(luò)和本地運行瓶頸進行分析，提出爬蟲主要需要克服開銷、本地利用率和網(wǎng)絡(luò)利用率的問題。針對以上3個問題提出了我們的解決方案，首先分析了方案的可行性，并通過實驗驗證了方案對于傳統(tǒng)方案的提升。實驗結(jié)果表明我們的方案可以在更小的內(nèi)存利用率、更小的系統(tǒng)開銷的情況下，獲得更高的網(wǎng)絡(luò)利用率。

由于網(wǎng)絡(luò)限制，目前對于工作線程的上限設(shè)置為60，根據(jù)開銷情況，如果并發(fā)數(shù)更高時，傳統(tǒng)的網(wǎng)絡(luò)爬蟲的CPU開銷將會越來越大，在這種情況下，本文提出的基于協(xié)程的爬蟲架構(gòu)將有更好的效果，將來工作將會研究更高網(wǎng)絡(luò)并發(fā)數(shù)下爬蟲的運行情況。

參考文獻

[1] Nanz， Sebastian， Scott West， and Kaue Soares da Silveira. “Examining the Expert Gap in Parallel Programming”. Euro-Par 2013 Parallel Processing[J]. Springer Berlin Heidelberg， 2013. 434-445.

[2] XU X，LI G.Research on Coroutine-Based Process Interaction Simulation Mechanism in C++[J].In AsiaSim 2012， ed： Springer， 2012， pp. 178-187.

[3] SHAVER C，LEE E A.The coroutine model of computation [J].In Model Driven Engineering Languages and Systems， ed： Springer， 2012， pp. 319-334.

[4] FIELDING R T.Maintaining distributed hypertext infostructures： Welcome to MOMspider's web[J].Computer Networks and ISDN Systems， 1994， 27（2）：193-204.

[5] M. BURNER.Crawling towards eternity： Building an archive of the World Wide Web[J]. Web Techniques Mag.， vol. 2， 1997.

[6] BRIN S，PAGE L.The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems， vol. 30， pp. 107-117， 1998.

[7] HEYDON A，NAJORK M.Mercator： A scalable， extensible web crawler[J].World Wide Web， vol. 2， pp. 219-229， 1999.

[8] Y.-X. Ding， X.-L. Wang， L.-B. Lin， Q. Zhang， and Y.-H. Wu.The Design and Implementation of the Crawler-INAR，in Machine Learning and Cybernetics[J].2006 International Conference on， 2006：4527-4530.

[9] C LI， C DING， K SHEN.Quantifying the cost of context switch[J].in Proceedings of the 2007 workshop on Experimental computer science， 2007， p. 2.

[10]D KNUTH.Fundamental Algorithms： Addison-Wesley， 1997.

[11]F P MILLER， A F VANDOME，J MCBREWSTER.“Coroutine： Computer multitasking， Iterator， Fiber （computer science）， Generator （computer science）， Green threads， Lazy evaluation， Pipeline （Unix）， Protothreads， Subroutine， Computer science，” 2009.

[12]E A LEE. The problem with threads[J].Computer， vol. 39， pp. 33-42， 2006.

[13]MELVIN E CONWAY.Design of a separable transition-diagram compiler[J].Communications of the ACM， 1963， 6（7）：396-408.

[14]D EICHMANN， The RBSE spider-balancing effective search against web load[J].Computer Networks and ISDN Systems， 1994， 27（2）： 308-316.

[15]周德懋，李舟軍. 高性能網(wǎng)絡(luò)爬蟲： 研究綜述[J].計算機科學， 2009， 36（8）： 26-29 .

[16]李曉明，閆鴻飛，王繼民. 搜索引擎：原理、技術(shù)與系統(tǒng)（2）[M].北京： 科學出版社， 2012.

[17]高克寧，柴橋子，張斌，等. 支持 Web 信息分類的高性能蜘蛛程序[J].小型微型計算機系統(tǒng)， 2006， 27（7）： 1308-1312.

[18]肖明軍，張巍，鄒翔，等. 一種多策略聯(lián)合信息抽取方法[J].小型微型計算機系統(tǒng)， 2005， 26（4）：614-61

[19]陳杰. 主題搜索引擎中網(wǎng)絡(luò)蜘蛛搜索策略研究[D].杭州：浙江大學， 2006.

[20]尹江，尹治本，黃洪.網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解決方案[J].計算機應用， 2008， 28（5）： 1114-1119.

[21]中國互聯(lián)網(wǎng)絡(luò)信息中心. 第27次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告[R]. 2011.

[7] HEYDON A，NAJORK M.Mercator： A scalable， extensible web crawler[J].World Wide Web， vol. 2， pp. 219-229， 1999.

[8] Y.-X. Ding， X.-L. Wang， L.-B. Lin， Q. Zhang， and Y.-H. Wu.The Design and Implementation of the Crawler-INAR，in Machine Learning and Cybernetics[J].2006 International Conference on， 2006：4527-4530.

[9] C LI， C DING， K SHEN.Quantifying the cost of context switch[J].in Proceedings of the 2007 workshop on Experimental computer science， 2007， p. 2.

[10]D KNUTH.Fundamental Algorithms： Addison-Wesley， 1997.

[11]F P MILLER， A F VANDOME，J MCBREWSTER.“Coroutine： Computer multitasking， Iterator， Fiber （computer science）， Generator （computer science）， Green threads， Lazy evaluation， Pipeline （Unix）， Protothreads， Subroutine， Computer science，” 2009.

[12]E A LEE. The problem with threads[J].Computer， vol. 39， pp. 33-42， 2006.

[13]MELVIN E CONWAY.Design of a separable transition-diagram compiler[J].Communications of the ACM， 1963， 6（7）：396-408.

[14]D EICHMANN， The RBSE spider-balancing effective search against web load[J].Computer Networks and ISDN Systems， 1994， 27（2）： 308-316.

[15]周德懋，李舟軍. 高性能網(wǎng)絡(luò)爬蟲： 研究綜述[J].計算機科學， 2009， 36（8）： 26-29 .

[16]李曉明，閆鴻飛，王繼民. 搜索引擎：原理、技術(shù)與系統(tǒng)（2）[M].北京： 科學出版社， 2012.

[17]高克寧，柴橋子，張斌，等. 支持 Web 信息分類的高性能蜘蛛程序[J].小型微型計算機系統(tǒng)， 2006， 27（7）： 1308-1312.

[18]肖明軍，張巍，鄒翔，等. 一種多策略聯(lián)合信息抽取方法[J].小型微型計算機系統(tǒng)， 2005， 26（4）：614-61

[19]陳杰. 主題搜索引擎中網(wǎng)絡(luò)蜘蛛搜索策略研究[D].杭州：浙江大學， 2006.

[20]尹江，尹治本，黃洪.網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解決方案[J].計算機應用， 2008， 28（5）： 1114-1119.

[21]中國互聯(lián)網(wǎng)絡(luò)信息中心. 第27次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告[R]. 2011.

[7] HEYDON A，NAJORK M.Mercator： A scalable， extensible web crawler[J].World Wide Web， vol. 2， pp. 219-229， 1999.

[8] Y.-X. Ding， X.-L. Wang， L.-B. Lin， Q. Zhang， and Y.-H. Wu.The Design and Implementation of the Crawler-INAR，in Machine Learning and Cybernetics[J].2006 International Conference on， 2006：4527-4530.

[9] C LI， C DING， K SHEN.Quantifying the cost of context switch[J].in Proceedings of the 2007 workshop on Experimental computer science， 2007， p. 2.

[10]D KNUTH.Fundamental Algorithms： Addison-Wesley， 1997.

[11]F P MILLER， A F VANDOME，J MCBREWSTER.“Coroutine： Computer multitasking， Iterator， Fiber （computer science）， Generator （computer science）， Green threads， Lazy evaluation， Pipeline （Unix）， Protothreads， Subroutine， Computer science，” 2009.

[12]E A LEE. The problem with threads[J].Computer， vol. 39， pp. 33-42， 2006.

[13]MELVIN E CONWAY.Design of a separable transition-diagram compiler[J].Communications of the ACM， 1963， 6（7）：396-408.

[14]D EICHMANN， The RBSE spider-balancing effective search against web load[J].Computer Networks and ISDN Systems， 1994， 27（2）： 308-316.

[15]周德懋，李舟軍. 高性能網(wǎng)絡(luò)爬蟲： 研究綜述[J].計算機科學， 2009， 36（8）： 26-29 .

[16]李曉明，閆鴻飛，王繼民. 搜索引擎：原理、技術(shù)與系統(tǒng)（2）[M].北京： 科學出版社， 2012.

[17]高克寧，柴橋子，張斌，等. 支持 Web 信息分類的高性能蜘蛛程序[J].小型微型計算機系統(tǒng)， 2006， 27（7）： 1308-1312.

[18]肖明軍，張巍，鄒翔，等. 一種多策略聯(lián)合信息抽取方法[J].小型微型計算機系統(tǒng)， 2005， 26（4）：614-61

[19]陳杰. 主題搜索引擎中網(wǎng)絡(luò)蜘蛛搜索策略研究[D].杭州：浙江大學， 2006.

[20]尹江，尹治本，黃洪.網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解決方案[J].計算機應用， 2008， 28（5）： 1114-1119.

[21]中國互聯(lián)網(wǎng)絡(luò)信息中心. 第27次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告[R]. 2011.