基于改進Kademlia協議的分布式爬蟲①

陶耀東,向中希,(中國科學院 沈陽計算技術研究所,沈陽 068)(中國科學院大學,北京 00049)

?

基于改進Kademlia協議的分布式爬蟲①

陶耀東1,向中希1,2
1(中國科學院 沈陽計算技術研究所,沈陽 110168)
2(中國科學院大學,北京 100049)

摘 要:隨著互聯網信息的爆炸式增長,搜索引擎和大數據等學科迫切需要一種高效、穩定、可擴展性強的爬蟲架構來完成數據的采集和分析.本文借助于對等網絡的思路,使用分布式哈希表作為節點間的數據交互的載體,同時針對網絡爬蟲自身的特點,對分布式哈希表的一種實現——Kademlia協議進行改進以滿足分布式爬蟲的需求.在此基礎上設計并完善了具有可擴展性和容錯性的分布式爬蟲集群.在實際試驗中,進行了單機多線程實驗和分布式集群的實驗,從系統性能角度和系統負載角度進行分析,實驗結果表明了這種分布式集群方法的有效性.

關鍵詞:分布式哈希表; P2P; 網絡爬蟲; Kademlia協議; 去中心化

隨著互聯網時代的來臨,網絡信息呈指數級增長.傳統的網絡爬蟲已漸漸不能滿足互聯網搜索引擎和大數據分析的需要[1],而基于中心調度的主從式的爬蟲也因為網絡負載高、擴展相對困難、廣域網部署困難[2,3]等原因發展緩慢,因此全分布式、易擴展的網絡爬蟲架構[4-6]成為了學術界和工業界的優選方案.

對等網絡(Peer-to-Peer Networks,P2P)是一種采用對等策略計算模式的網絡,是近年來較為流行的一種網絡架構[7].網絡的參與者共享他們所擁有的部分硬件資源(CPU、內存、硬盤、帶寬等),這些共享資源能被其他對等結點直接訪問而無需經過中間實體.在此網絡中的參與者既是資源(服務和內容)提供者,又是資源(服務和內容)獲取者.這種網絡體系可以滿足全分布式架構的需要.

快速高效資源檢索是 P2P網絡體系的核心問題.其主要檢索方式經歷了中心索引服務器、非結構化覆蓋網絡、結構化覆蓋網絡這幾個階段.結構化覆蓋網絡基于分布式哈希表(Distributed Hash Table,DHT)的技術,具有無需中心索引服務器、查找速度快、網絡開銷小等優點,在實際的大規模的 P2P網絡環境中被廣泛使用.DHT的代表實現有 Chord[8],Kademlia[9]等.而在實際使用中較廣泛的是Kademlia 協議,其主要應用有eMule、Bitcomet.

1　Kademlia 協議

1.1距離度量

在Kademlia 中,每個節點都在初始化時被分配了一個160位的節點ID ,同時DHT網絡中的所有資源(鍵值對)也是用160位的標識鍵(Key)來表示.一個節點通常存儲那些與它距離相近的資源.每一個資源的鍵一般通過哈希函數計算生成,而節點ID是節點自身隨機生成的.在DHT網絡中,所有距離(節點與節點、節點與資源)都是通過異或運算產生的.可以表示為:

x,y可以是一個節點ID 或者是資源的標識鍵.因為距離是基于節點ID的,而節點ID是隨機生成的,所以距離相近并不意味物理距離上的相近.

1.2K桶

Kademlia的路由表是通過一些稱之為 K 桶的表格構造起來的.對每一個0≤ i ≤160,每個節點都保存有一些和自己距離范圍在區間[2i,2i+1)內的一些節點信息,這些信息由一些(IP地址,UDP端口,Node ID)的數據列表構成(DHT 網絡是靠UDP 協議交換信息的).每一個這樣的列表都稱之為一個 K 桶,并且每個 K桶內部信息存放位置是根據上次看到的時間順序排列,最近看到的放在頭部,最后看到的放在尾部.每個桶都有不超過 k 個的數據項.

一個節點的全部 K 桶列表如表 1 所示.

表1　K桶的結構表

i 　[2i,2i+1)(IP,UDP,Node ID)i-1…(IP,UDP,Node ID)i-k… 　… 　…

當i值很小時,K 桶通常是空的(也就是說沒有足夠多的節點,比如當 i＝0 時,就最多可能只有 1 項); 而當 i 值很大時,其對應 K 桶的項數又很可能會超過 k個(覆蓋距離范圍越廣,存在較多節點的可能性也就越大),這里 k 是為平衡系統性能和網絡負載而設置的一個常數,但必須是偶數.

1.3RPC操作

Kademlia定義了4種RPC(Remote Procedure Call)操作,它們分別是PING、STORE、FIND_NODE、FIND_VALUE.

① PING操作允許一個節點來檢測另一個節點是否在線.同時每個PING的回復包含了回復者的節點ID.

② STORE操作是用來存儲資源到DHT網絡中,通知一個節點存儲一個對,以便以后查詢需要.

③ FIND_NODE操作是用來查找另一個節點.當一個節點需要查找另一個節點的時候,它會發起一個FIND_NODE的請求給與路由表中與目標節點最接近的k個鄰居節點.然后每一個鄰居節點重復以上操作,直至沒有更好的結果或者目標節點被發現.

④ FIND_VALUE操作與FIND_NODE操作相似,然而當一個節點包含所需的key時,會返回所需資源而不是離它最接近的k個鄰居節點,當請求該key的節點獲得了資源以后,執行STORE操作把結果存入到最近的k個節點中,以加快下一次執行FIND_VALUE的速度.

1.4路由表查詢

DHT網絡的核心問題是快速節點查找.Kademlia的節點查詢通過以下步驟實現:

① 計算節點之間的距離 d(x,y)=x⊕ y

② 從x的第?log2d?個K桶中取出α個節點,分別對其進行FIND_NODE操作,如果這個 K 桶中的信息少于α個,則從附近多個K桶中選擇距離最接近 d的總共α個節點.

③ 對于收到FIND_NODE請求的每個節點,如果發現自己就是 y,則回答自己是最接近y的; 否則測量自己和 y 的距離,并從自己對應的 K 桶中選擇α個節點的信息給 x.

④x對新接受到的每個節點都再次執行FIND_NODE 操作,此過程不斷重復執行,直到每一個分支都有節點響應自己是最接近 y 的.

⑤ 通過上述查找操作,x 得到了 k 個最接近 y的節點信息.

這里的α參數是用來控制路由查詢的速度的,當α比較大時,會加快查找速度但同時會增加節點間的通信量.這個過程可以用圖1描述.

圖1　節點發現流程圖

2　分布式爬蟲策略

2.1系統結構

本文設計的基于改進的Kademlia協議的分布式爬蟲的結構(單節點)如圖2所示.

其中,爬蟲模塊負責以廣度優先的方式爬取互聯網信息,將獲取的網頁解析并將得到的目標鏈接交給協議模塊處理,協議模塊根據定義好的處理方式分發鏈接(執行RPC操作),然后爬蟲模塊繼續從任務隊列中獲取下一個任務,以同樣的方式處理.節點間的協作完全通過協議模塊來控制,以此實現完全分布式.

圖2　爬蟲節點的系統結構

2.2協議改進

結合分布式爬蟲自身的特點和特定的需求,本文在Kademlia算法原有的基礎上提出了以下改進措施:

2.2.1增加新的存儲模塊

爬蟲模塊是以URL為單位執行的,對整個系統而言,URL就是資源,此時不能將其存儲到原有的對.這里將原有協議中的存儲分為4個部分:

① 原有存儲: 用來保存對信息.② 任務隊列: 用來存儲需要執行的URL的隊列.③ 備份隊列: 用來存儲需要備份的鄰居節點的URL的隊列.

④ 處理記錄: 用來存儲已完成的URL的哈希表.

2.2.2增加新的RPC操作

定義了四種新的RPC操作: STORE_TASK、STORE_BACKUP、DELETE_BACKUP、REFRESH_TASK.通過新的RPC操作來保證分布式中各個節點的協作.

① STORE_TASK操作允許一個節點將它發現的資源(URL)進行分發,根據任務劃分策略執行RPC操作,將資源存儲到劃分的節點讓其處理.

② STORE_BACKUP操作允許一個節點間它發現的資源進行備份,根據容災策略執行RPC操作,將資源存儲到距離它最為接近的多個鄰居節點中.

③DELETE_BACKUP操作允許一個節點在執行完任務后,執行RPC操作,將它的鄰居節點備份的信息刪除掉.

④ REFRESH_TASK操作允許一個節點通知它的鄰居節點重新分發其任務隊列中的所有任務.

2.2.3增加網絡結構變化的處理

對于DHT網絡節點的增加、退出、異常等情況增加了新的處理方式,保證DHT網絡的可擴展性和容錯性.

2.3任務劃分與處理策略

對于整個DHT網絡而言,需要將任務進行劃分到每一個具體的節點,同時保證該任務的唯一性(相同的任務每次都會被分配到同一個節點)和整個系統的均衡性(每個節點分配的任務量大致相當)[10].這里采用的策略是: 采用與節點資源存儲相同的哈希函數,將URL哈希成為與節點ID位數一致的key,根據之前提到的距離定義獲得與節點最接近的節點,將該URL存放到所選節點的任務隊列中(使用RPC操作STORE_TASK).

因為使用策略的唯一性可以保證相同任務每次都能被發送到同一節點,所以可以根據已保存的處理URL記錄進行去重,如果不對URL進行檢查,會導致大量冗余任務產生,從而降低系統效率.

整個任務的處理流程如下所示:

(1)本地節點選擇需要的分發的URL,計算它的哈希值作為key .

(2)本地節點執行RPC操作FIND_NODE尋找與URL的key距離最接近的節點作為目標節點.

(3)對目標節點執行RPC操作STORE_TASK .

(4)對目標節點的鄰居節點執行RPC操作STORE_BACKUP,將URL存到鄰居節點的備份隊列.

(5)目標節點先在處理記錄中進行URL去重檢查,如果不重復則將URL存到任務隊列.

(6)目標節點的爬蟲模塊從任務隊列中獲取任務并執行.

(7)目標節點執行完成后,計算key與節點ID的距離的哈希值,將任務存放到處理記錄對應的哈希表項中.

(8)目標節點對鄰居節點執行RPC操作DELETE _BACKUP,刪除鄰居節點備份隊列中的任務.

2.4擴展與容災策略

2.4.1節點加入

當一個新的節點需要加入到現有的DHT網絡中時,需要知道至少一個節點的信息,其主要過程為:

(1)新節點將已有節點插入到合適的K桶中,建立路由表.

(2)新節點執行RPC操作FIND_NODE,請求的節點為自身ID,從而更新DHT網絡其他節點的路由表信息.

(3)新節點根據其他節點的返回信息,更新自身的路由表信息.

(4)新節點執行RPC操作REFRESH_TASK,向鄰居節點請求任務.

(5)鄰居節點對其任務列表中的所有URL執行RPC操作STORE_TASK,將距離新節點較近的任務分發給新節點.

2.4.2節點正常退出

在Kademlia協議中,節點退出時是不需要發布任何信息的,只需要每個節點周期性地發布所有的對信息,然而改進的Kademlia協議中需要對退出節點的備份隊列和任務隊列進行處理,主要流程:

(1)退出節點對其任務隊列中所有的任務,進行重新發布,找出每個任務最接近的節點,并執行RPC操作STORE_TASK

(2)退出節點對其備份隊列中所有的任務,進行重新發布,找出每個任務最接近的幾個節點,對最接近的節點執行RPC操作STORE_TASK,而對其他節點執行RPC操作STORE_BACKUP

(3)節點退出

2.4.3節點異常退出

每個節點周期性地發布其備份隊列中的所有的信息并執行RPC操作STORE_TASK,這樣當節點發生異常退出時,可以保證該任務不會丟失掉.

3　實驗與仿真

為了比較爬蟲的擴展性,本文設計了兩組試驗:單機試驗和集群實驗.其中單機實驗使用多線程的方法進行擴展,而集群實驗通過增加節點來進行擴展.爬蟲模塊兩者相同,都是根據廣度優先的方法進行爬取,起點設為 http:.www.baidu.com .主要流程如圖3所示.

3.1單機實驗

單機實驗所使用的環境為Ubuntu 14.04 LTS 操作系統,使用Intel Core i5 處理器.實驗中通過改變系統所用線程數來對爬蟲模塊的單機性能從以下兩個方面進行評估:

圖3　爬蟲模塊的流程

3.1.1系統性能

其中處理速度代表每秒中能夠爬取并解析的URL 數,生成速度代表每秒鐘解析生成的URL數.通過設置爬蟲模塊的線程數統計系統的處理速度和生成速度,如圖4所示,隨著線程數的增加,系統的處理速度和生成速度有顯著的提升,然而提升的速度會受到實驗機器性能的限制而降低最終飽和.

圖4　多線程的系統性能

3.1.2系統負載

網絡帶寬占用和CPU占用是爬蟲運行過程中的平均負載.由圖5可知,隨著線程數的增加,系統的網絡負載和CPU負載會逐漸增加,很容易達到飽和.

圖5　多線程的系統負載

3.2集群實驗

集群實驗是通過云主機來進行測試的,集群中每一個節點所使用的環境均為Ubuntu 14.04 LTS 操作系統,使用單核處理器.實驗中通過增加集群中的節點來對整個分布式集群實驗.節點IP分布如表2如示.

表2　分布式集群節點分布

設置爬蟲模塊每5 s 調用一次,每隔1 min增加一個節點,將采樣的周期定為20 s,采樣時間8 min,記錄下URL處理速度和生成速度如圖6所示.

圖6　分布式集群采樣圖

3.2.1系統性能

將采樣的結果按照不同的集群規模進行分類并計算在不同規模下集群的平均處理速度.通過最小二乘法進行一元線性擬合,所得結果如圖7所示.

圖7　分布式集群的系統性能

隨著集群規模的增大,整個集群的處理能力增強,且相對穩定,處理速度大致呈線性增長.當需要提升集群的處理能力時,僅需要增加額外的節點即可,具有較好的拓展性.

3.2.2系統負載

由于云主機的帶寬較大,系統使用的帶寬非常少,因此未做測量.統計每個節點在不同規模下的CPU負載如圖8所示.

圖8　分布式集群的系統負載

由圖8可知,隨著集群規模的增大,每個節點的平均CPU占用基本不發生改變.只有在節點間通信和爬蟲模塊會消耗一些CPU資源,這意味著系統的拓展性良好,節點負載基本不會受集群規模擴大的影響.

4　結語

本文提出了一種基于改進的Kademlia協議的完全分布式的網絡爬蟲,同時闡述了針對Kademlia協議的改進和整個系統的設計與結構.通過實際實驗,有效地驗證了這種架構的可行性.對比單機多線程方式,能夠避免單個節點資源耗盡的問題,具有良好的擴展性和容錯性.同時本文的分布式爬蟲能夠部署到廣域網范圍,不受局域網的制約.

參考文獻

1許笑.分布式 Web 信息采集關鍵技術研究[博士學位論文].哈爾濱:哈爾濱工業大學,2011.

2許笑,張偉哲,張宏利,方濱興.廣域網分布式 Web 爬蟲.軟件學報,2010,21(5): 1067–1082.

3黃志敏,曾學文,陳君.一種基于 Kademlia 的全分布式爬蟲集群方法.計算機科學,2014,41(3):124–128.

4Boldi,Paolo,et al.Ubicrawler: A scalable fully distributed web crawler.Software: Practice and Experience,2004,34(8): 711–726.

5金凡,顧進廣.一種改進的T-Spider分布式爬蟲.電子學與計算機,2011,28(8):102–104.

6周模,張建宇,代亞非.可擴展的DHT網絡爬蟲設計和優化.中國科學(信息科學),2010,40(9):1211–1222.

7Singh A,et al.Apoidea: A decentralized peer-to-peer architecture for crawling the world wide web.Distributed Multimedia Information Retrieval.Springer Berlin Heidelberg.2004.126–142.

8Stoica I,et al.Chord: A scalable peer-to-peer lookup service for internet applications.ACM SIGCOMM Computer Communication Review,2001,31(4): 149–160.

9Maymounkov P,Mazieres D.Kademlia: A peer-to-peer information system based on the xor metric.Peer-to-Peer Systems.Springer Berlin Heidelberg.2002.53–65.

10Li GL,Zhang HB.Design of a distributed spiders system based on Web service.Second Pacific-Asia Conference on Web Mining and Web-based Application,2009.WMWA’09.IEEE,2009.

Distributed Crawler Based on the Improved Kademlia Protocol

TAO Yao-Dong1,XIANG Zhong-Xi1,2
1(Shenyang Institute of Computing Technology,Chinese Academy of Sciences,Shenyang 110168,China)2(University of Chinese Academy of Sciences,Beijing 100049,China)

Abstract:With the explosive growth of Internet information,researches on search engine and big data call for an efficient,stable and scalable crawler architecture to collect and analyze Internet data.Inspired by peer to peer network,we use distributed hash table as a carrier of communication between nodes,while a distributed hash table implementation—Kademlia protocol is modified and improved to meet the needs of the distributed crawler cluster’s scalability and fault tolerance.In the experiments,we carried out multi-threaded experiment on single computer and node expansion experiment on distributed cluster.From system performance and system load point of view,the experimental results show the effectiveness of this kind of distributed cluster.

Key words:distributed hash table; peer to peer; network crawler; Kademlia protocol; decentration

基金項目:①沈陽市科技計劃(F14-056-7-00)

收稿時間:2015-07-21;收到修改稿時間:2015-09-14