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

?

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

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

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

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

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

對等網(wǎng)絡(luò)(Peer-to-Peer Networks,P2P)是一種采用對等策略計(jì)算模式的網(wǎng)絡(luò),是近年來較為流行的一種網(wǎng)絡(luò)架構(gòu)[7].網(wǎng)絡(luò)的參與者共享他們所擁有的部分硬件資源(CPU、內(nèi)存、硬盤、帶寬等),這些共享資源能被其他對等結(jié)點(diǎn)直接訪問而無需經(jīng)過中間實(shí)體.在此網(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ò)這幾個(gè)階段.結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)基于分布式哈希表(Distributed Hash Table,DHT)的技術(shù),具有無需中心索引服務(wù)器、查找速度快、網(wǎng)絡(luò)開銷小等優(yōu)點(diǎn),在實(shí)際的大規(guī)模的 P2P網(wǎng)絡(luò)環(huán)境中被廣泛使用.DHT的代表實(shí)現(xiàn)有 Chord[8],Kademlia[9]等.而在實(shí)際使用中較廣泛的是Kademlia 協(xié)議,其主要應(yīng)用有eMule、Bitcomet.

1　Kademlia 協(xié)議

1.1距離度量

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

x,y可以是一個(gè)節(jié)點(diǎn)ID 或者是資源的標(biāo)識(shí)鍵.因?yàn)榫嚯x是基于節(jié)點(diǎn)ID的,而節(jié)點(diǎn)ID是隨機(jī)生成的,所以距離相近并不意味物理距離上的相近.

1.2K桶

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

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

1.3RPC操作

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

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

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

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

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

1.4路由表查詢

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

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

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

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

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

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

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

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

2　分布式爬蟲策略

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

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

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

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

2.2協(xié)議改進(jìn)

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

2.2.1增加新的存儲(chǔ)模塊

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

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

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

2.2.2增加新的RPC操作

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

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

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

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

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

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

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

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

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

因?yàn)槭褂貌呗缘奈ㄒ恍钥梢员ＷC相同任務(wù)每次都能被發(fā)送到同一節(jié)點(diǎn),所以可以根據(jù)已保存的處理URL記錄進(jìn)行去重,如果不對URL進(jìn)行檢查,會(huì)導(dǎo)致大量冗余任務(wù)產(chǎn)生,從而降低系統(tǒng)效率.

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

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

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

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

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

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

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

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

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

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

2.4.1節(jié)點(diǎn)加入

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

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

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

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

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

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

2.4.2節(jié)點(diǎn)正常退出

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

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

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

(3)節(jié)點(diǎn)退出

2.4.3節(jié)點(diǎn)異常退出

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

3　實(shí)驗(yàn)與仿真

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

3.1單機(jī)實(shí)驗(yàn)

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

圖3　爬蟲模塊的流程

3.1.1系統(tǒng)性能

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

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

3.1.2系統(tǒng)負(fù)載

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

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

3.2集群實(shí)驗(yàn)

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

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

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

圖6　分布式集群采樣圖

3.2.1系統(tǒng)性能

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

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

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

3.2.2系統(tǒng)負(fù)載

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

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

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

4　結(jié)語

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

參考文獻(xiàn)

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

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

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

6周模,張建宇,代亞非.可擴(kuò)展的DHT網(wǎng)絡(luò)爬蟲設(shè)計(jì)和優(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

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

收稿時(shí)間:2015-07-21;收到修改稿時(shí)間:2015-09-14