基于改進Kademlia協(xié)議的分布式爬蟲①

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

?

基于改進Kademlia協(xié)議的分布式爬蟲①

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

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

關(guān)鍵詞:分布式哈希表; P2P; 網(wǎng)絡(luò)爬蟲; Kademlia協(xié)議; 去中心化

隨著互聯(lián)網(wǎng)時代的來臨,網(wǎng)絡(luò)信息呈指數(shù)級增長.傳統(tǒng)的網(wǎng)絡(luò)爬蟲已漸漸不能滿足互聯(lián)網(wǎng)搜索引擎和大數(shù)據(jù)分析的需要[1],而基于中心調(diào)度的主從式的爬蟲也因為網(wǎng)絡(luò)負載高、擴展相對困難、廣域網(wǎng)部署困難[2,3]等原因發(fā)展緩慢,因此全分布式、易擴展的網(wǎng)絡(luò)爬蟲架構(gòu)[4-6]成為了學(xué)術(shù)界和工業(yè)界的優(yōu)選方案.

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

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

1　Kademlia 協(xié)議

1.1距離度量

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

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

1.2K桶

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

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

表1　K桶的結(jié)構(gòu)表

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

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

1.3RPC操作

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

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

② STORE操作是用來存儲資源到DHT網(wǎng)絡(luò)中,通知一個節(jié)點存儲一個對,以便以后查詢需要.

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

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

1.4路由表查詢

DHT網(wǎng)絡(luò)的核心問題是快速節(jié)點查找.Kademlia的節(jié)點查詢通過以下步驟實現(xiàn):

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

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

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

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

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

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

圖1　節(jié)點發(fā)現(xiàn)流程圖

2　分布式爬蟲策略

2.1系統(tǒng)結(jié)構(gòu)

本文設(shè)計的基于改進的Kademlia協(xié)議的分布式爬蟲的結(jié)構(gòu)(單節(jié)點)如圖2所示.

其中,爬蟲模塊負責(zé)以廣度優(yōu)先的方式爬取互聯(lián)網(wǎng)信息,將獲取的網(wǎng)頁解析并將得到的目標(biāo)鏈接交給協(xié)議模塊處理,協(xié)議模塊根據(jù)定義好的處理方式分發(fā)鏈接(執(zhí)行RPC操作),然后爬蟲模塊繼續(xù)從任務(wù)隊列中獲取下一個任務(wù),以同樣的方式處理.節(jié)點間的協(xié)作完全通過協(xié)議模塊來控制,以此實現(xiàn)完全分布式.

圖2　爬蟲節(jié)點的系統(tǒng)結(jié)構(gòu)

2.2協(xié)議改進

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

2.2.1增加新的存儲模塊

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

① 原有存儲: 用來保存對信息.② 任務(wù)隊列: 用來存儲需要執(zhí)行的URL的隊列.③ 備份隊列: 用來存儲需要備份的鄰居節(jié)點的URL的隊列.

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

2.2.2增加新的RPC操作

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

① STORE_TASK操作允許一個節(jié)點將它發(fā)現(xiàn)的資源(URL)進行分發(fā),根據(jù)任務(wù)劃分策略執(zhí)行RPC操作,將資源存儲到劃分的節(jié)點讓其處理.

② STORE_BACKUP操作允許一個節(jié)點間它發(fā)現(xiàn)的資源進行備份,根據(jù)容災(zāi)策略執(zhí)行RPC操作,將資源存儲到距離它最為接近的多個鄰居節(jié)點中.

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

④ REFRESH_TASK操作允許一個節(jié)點通知它的鄰居節(jié)點重新分發(fā)其任務(wù)隊列中的所有任務(wù).

2.2.3增加網(wǎng)絡(luò)結(jié)構(gòu)變化的處理

對于DHT網(wǎng)絡(luò)節(jié)點的增加、退出、異常等情況增加了新的處理方式,保證DHT網(wǎng)絡(luò)的可擴展性和容錯性.

2.3任務(wù)劃分與處理策略

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

因為使用策略的唯一性可以保證相同任務(wù)每次都能被發(fā)送到同一節(jié)點,所以可以根據(jù)已保存的處理URL記錄進行去重,如果不對URL進行檢查,會導(dǎo)致大量冗余任務(wù)產(chǎn)生,從而降低系統(tǒng)效率.

整個任務(wù)的處理流程如下所示:

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

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

(3)對目標(biāo)節(jié)點執(zhí)行RPC操作STORE_TASK .

(4)對目標(biāo)節(jié)點的鄰居節(jié)點執(zhí)行RPC操作STORE_BACKUP,將URL存到鄰居節(jié)點的備份隊列.

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

(6)目標(biāo)節(jié)點的爬蟲模塊從任務(wù)隊列中獲取任務(wù)并執(zhí)行.

(7)目標(biāo)節(jié)點執(zhí)行完成后,計算key與節(jié)點ID的距離的哈希值,將任務(wù)存放到處理記錄對應(yīng)的哈希表項中.

(8)目標(biāo)節(jié)點對鄰居節(jié)點執(zhí)行RPC操作DELETE _BACKUP,刪除鄰居節(jié)點備份隊列中的任務(wù).

2.4擴展與容災(zāi)策略

2.4.1節(jié)點加入

當(dāng)一個新的節(jié)點需要加入到現(xiàn)有的DHT網(wǎng)絡(luò)中時,需要知道至少一個節(jié)點的信息,其主要過程為:

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

(2)新節(jié)點執(zhí)行RPC操作FIND_NODE,請求的節(jié)點為自身ID,從而更新DHT網(wǎng)絡(luò)其他節(jié)點的路由表信息.

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

(4)新節(jié)點執(zhí)行RPC操作REFRESH_TASK,向鄰居節(jié)點請求任務(wù).

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

2.4.2節(jié)點正常退出

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

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

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

(3)節(jié)點退出

2.4.3節(jié)點異常退出

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

3　實驗與仿真

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

3.1單機實驗

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

圖3　爬蟲模塊的流程

3.1.1系統(tǒng)性能

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

圖4　多線程的系統(tǒng)性能

3.1.2系統(tǒng)負載

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

圖5　多線程的系統(tǒng)負載

3.2集群實驗

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

表2　分布式集群節(jié)點分布

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

圖6　分布式集群采樣圖

3.2.1系統(tǒng)性能

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

圖7　分布式集群的系統(tǒng)性能

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

3.2.2系統(tǒng)負載

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

圖8　分布式集群的系統(tǒng)負載

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

4　結(jié)語

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

參考文獻

1許笑.分布式 Web 信息采集關(guān)鍵技術(shù)研究[博士學(xué)位論文].哈爾濱:哈爾濱工業(yè)大學(xué),2011.

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

3黃志敏,曾學(xué)文,陳君.一種基于 Kademlia 的全分布式爬蟲集群方法.計算機科學(xué),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分布式爬蟲.電子學(xué)與計算機,2011,28(8):102–104.

6周模,張建宇,代亞非.可擴展的DHT網(wǎng)絡(luò)爬蟲設(shè)計和優(yōu)化.中國科學(xué)(信息科學(xué)),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