分布式爬蟲系統(tǒng)中URL去重的設計與實現(xiàn)

陳宇倫 周奎

摘? 要：目前全球URL總數(shù)在350億以上，在滿足時效性的前提下，越來越多地選擇采用分布式爬蟲技術，它可以快速高效地從Web中獲取有價值的數(shù)據(jù)。基于Redis數(shù)據(jù)庫設計一種相關去重協(xié)議，實現(xiàn)URL去重，有利于提高分布式系統(tǒng)的穩(wěn)定性和高效性，以及保持整個系統(tǒng)對URL去重的一致性。

關鍵詞：分布式爬蟲系統(tǒng);URL去重;URL去重協(xié)議

（School of Electrical and Information Engineering，Hubei University of Automotive Technology，Shiyan? 442002，China）

Abstract：There are more than 35 billion URLs in the world nowadays. Under the premise of satisfying the timeliness，more and more people choose to adopt distributed crawler technology，which can quickly and efficiently obtain valuable data from Web. Based on Redis database，this paper designs a kind of related de-reduplication protocol to realize URL de-reduplication，which is helpful to improve the stability and efficiency of distributed system，and to maintain the consistency of the whole system to URL.

Keywords：distributed crawler system;URL de-duplication;URL de-duplication protocol

0? 引? 言

隨著移動互聯(lián)技術的日益成熟和Web的飛速發(fā)展，Web這張網(wǎng)也愈來愈壯大。每天在這張網(wǎng)中產生大量的數(shù)據(jù)，蘊藏在這張網(wǎng)中的數(shù)據(jù)的價值不言而喻。從Web中快速而高效地挖掘數(shù)據(jù)成為各大公司的核心競爭力，要想高效地從Web中挖掘數(shù)據(jù)，分布式系統(tǒng)必不可少[1]。在分布式爬蟲系統(tǒng)中也面臨著各種復雜的挑戰(zhàn)，比如分布式任務的調度、分布式系統(tǒng)中負載均衡、分布式系統(tǒng)中URL去重等。分布式系統(tǒng)中URL去重算法影響著系統(tǒng)的效率，面對上百億的URL設計一個優(yōu)秀的去重算法能提高整個系統(tǒng)的性能[2]。

1? 分布式系統(tǒng)URL去重關鍵技術

1.1? Redis

Redis是開源的且遵循BSD協(xié)議，基于Key-Value的數(shù)據(jù)庫，同時有著極高的性能以及提供多種數(shù)據(jù)結構的存儲。分布式調度協(xié)議基于Redis數(shù)據(jù)庫作為數(shù)據(jù)存儲技術，實現(xiàn)分布式系統(tǒng)中URL去重。

基于Redis數(shù)據(jù)庫URL去重協(xié)議的設計，將分布式系統(tǒng)劃分為兩層，分布式系統(tǒng)架構如圖1所示。本地主機和中心主機，將中心主機作為單個網(wǎng)絡節(jié)點，通過單個節(jié)點實現(xiàn)與本地網(wǎng)絡和其他網(wǎng)絡通信對URL去重[3]。

本地主機Redis服務（local_Redis）擁有三大數(shù)據(jù)庫：（1）已完成的URL池（finish_URL），用于保存已經(jīng)爬取的URL以及去重查詢;（2）爬蟲的任務池（task_pool），用于保存爬蟲將要爬取的任務;（3）新獲取的URL數(shù)據(jù)池（URL_pool），用于保存最新獲取的URL。

中心主機Redis服務（center_Redis）擁有三大數(shù)據(jù)庫：（1）去重后的URL數(shù)據(jù)池（task_URL），用于分配給本地網(wǎng)絡其他主機的task_pool;（2）本地網(wǎng)絡去重池（local_reduce_pool），用于本地網(wǎng)絡其他主機間的去重;（3）其他網(wǎng)絡去重池（dist_reduce_pool），用于發(fā)送至其他網(wǎng)絡，由其他網(wǎng)絡完成去重查詢，如果沒有其他網(wǎng)絡此處可選用[4]。

1.2? 分布式系統(tǒng)中URL去重協(xié)議

實現(xiàn)分布式爬蟲系統(tǒng)需要解決分布在不同主機上URL的去重問題，由于URL分散在不同主機和不同網(wǎng)絡，對URL去重存在一些困難。設計一種協(xié)議為解決URL去重時URL一致性，將一定量URL作為一個集合去重時的基本單位。在去重時每臺主機上的爬蟲獲取的新URL首先在本地去重，然后將第一輪去重后的URL集合提交至中心節(jié)點，再由中心節(jié)點去重，中心節(jié)點將本地網(wǎng)絡主機發(fā)來的URL分發(fā)至其他網(wǎng)絡，再由其他網(wǎng)絡去重，再將去重的結果上報。主機與中心節(jié)點和中心節(jié)點與其他網(wǎng)絡的去重，按照設計的數(shù)據(jù)格式通信[5]。

2? URL去重協(xié)議的設計與實現(xiàn)

2.1? URL去重協(xié)議格式

URL去重協(xié)議格式如圖2所示，URL set為不同主機間要去重的URL集合，每次以一定量的URL作為一次通信的數(shù)據(jù)，IP為當前主機IP地址，用于主機間的通信和身份標識，number為整個分布式系統(tǒng)中唯一的標識，用以區(qū)分哪個網(wǎng)絡哪個主機的哪次請求，flag為每次通信時發(fā)送的何種請求[6]。

2.2? 本地去重

運行在不同主機上的爬蟲在抓取頁面時，會從頁面中獲取新的URL，將新獲取的URL存入本地URL_pool。在本地去重時，遍歷URL_pool中的URL，并計算每個URL的哈希值，同時與finish_url中的哈希值比較，若URL_pool中存在相同的哈希值，將該URL從URL_pool中刪除。在遍歷時將不重復的URL以一定數(shù)量構成URL_set，URL_set數(shù)據(jù)格式為JSON格式，其中以URL字符串為鍵，以阿拉伯數(shù)字0為默認值進行表示，并生成分布式系統(tǒng)中唯一的number作為去重協(xié)議數(shù)據(jù)幀的標識，置flag=1，置IP為本機IP，構成基本去重協(xié)議數(shù)據(jù)幀，并將此數(shù)據(jù)幀發(fā)給中心節(jié)點[7]。

2.3? 本地局域網(wǎng)去重

中心節(jié)點收到數(shù)據(jù)時，讀取flag的值，并根據(jù)flag的值將URL_set存入對應的數(shù)據(jù)庫中。若flag=1，表明接收到的數(shù)據(jù)為待去重URL的集合，并將整個數(shù)據(jù)幀存入local_reduce_pool。中心節(jié)點處理local_reduce_pool中的數(shù)據(jù)幀時，從local_reduce_pool中每獲取一個數(shù)據(jù)幀，置其flag=2，并向本地局域網(wǎng)主機發(fā)起廣播，等待局域網(wǎng)內主機的應答。

主機收到數(shù)據(jù)時，判斷flag的值，若flag=2，表明接收的數(shù)據(jù)為去重請求，同時判斷數(shù)據(jù)幀中的IP是否為本機IP，若是，則丟棄該數(shù)據(jù)幀;否則，該數(shù)據(jù)幀進入去重隊列。去重隊列處理數(shù)據(jù)幀時遍歷URL_set中的URL，在遍歷時計算該URL的哈希值，并在finish_URL中查找是否有相同的哈希值，若finish_URL中存在相同的哈希值，則令鍵為該URL字符串的值為1，否則保持原值不變。遍歷完URL_set時，令flag=3，并將該數(shù)據(jù)幀中發(fā)給中心節(jié)點。

中心節(jié)點收到數(shù)據(jù)時，判斷flag的值，若flag=3，表明接收的數(shù)據(jù)為去重應答，此時判斷數(shù)據(jù)幀中的IP是否為本局域網(wǎng)中其他主機IP，若是本局域網(wǎng)中其他主機IP數(shù)據(jù)幀進入去重隊列。去重隊列處理數(shù)據(jù)幀時讀取number，并從local_reduce_pool取出相同number的數(shù)據(jù)幀，獲取的數(shù)據(jù)幀其flag=2。去重隊列遍歷flag=3的URL_set，根據(jù)flag=3中值不為0的項，刪除flag=2中對應的鍵的項，直到URL_set中的URL遍歷完。在限定的延時時間內，直到接收了相同number所有主機去重應答為止，該number下的URL_set去重結束，此時刪除local_reduce_pool中該number對應的數(shù)據(jù)幀，并將此數(shù)據(jù)幀轉入dis_reduce_pool中。

2.4? 分布式系統(tǒng)去重

中心主機接收到數(shù)據(jù)幀時，判斷flag的值，若flag=2，表明此數(shù)據(jù)幀為去重請求，同時判斷IP是否為其他網(wǎng)絡IP，若是，則此數(shù)據(jù)幀進入dis_reduce_pool，并由分布式去重查詢隊列處理，否則返回。分布式去重查詢隊列將dis_reduce_pool的數(shù)據(jù)幀廣播到本局域網(wǎng)所有主機，等待本地主機的去重應答。

中心主機接收到數(shù)據(jù)幀時，判斷flag的值，若flag=3，表明此數(shù)據(jù)幀為去重應答，同時判斷IP是否為本機IP或其他網(wǎng)絡IP。若IP為其他網(wǎng)絡IP，此數(shù)據(jù)幀進入分布式去重隊列。分布式去重隊列處理數(shù)據(jù)幀時讀取number，并從本機dis_reduce_pool獲取相同number的數(shù)據(jù)幀，獲取到的數(shù)據(jù)幀flag=2，分布式去重隊列遍歷flag=3的URL_set，判斷flag=3中鍵的值是否為0，若是，則令flag=2中對應的鍵的值為1，否則保持原值不變。在限定的延時時間內，直到接收了相同number所有主機的去重應答為止，并將該數(shù)據(jù)幀發(fā)送給數(shù)據(jù)幀中IP對應的網(wǎng)絡。若IP為本機IP，此數(shù)據(jù)幀進入分布式去重隊列，分布式隊列處理數(shù)據(jù)幀時讀取number，并從本機dis_reduce_pool獲取相同number的數(shù)據(jù)幀，獲取到的數(shù)據(jù)幀flag=2，分布式去重隊列遍歷flag=3的URL_set，判斷flag=3中鍵的值是否為0，若不是，則刪除flag=2中對應的項，否則保持原值不變。在限定的延時時間內，直到接收了相同number所有主機的去重應答為止，分布式系統(tǒng)URL去重完成，并將該URL_set中的URL存入task_pool[8]。

3? 結? 論

本文設計了一個簡單且易于實現(xiàn)的分布式去重協(xié)議，對去重協(xié)議算法進行了詳細的介紹和說明。使用Redis數(shù)據(jù)庫存儲URL哈希信息，可以快速查詢URL是否被爬取，分布在不同網(wǎng)絡的主機將去重結果發(fā)送至中心主機，中心主機負責整個分布式系統(tǒng)中URL去重。

參考文獻：

[1] 李婷.分布式爬蟲任務調度與AJAX頁面抓取研究 [D].成都：電子科技大學，2015.

[2] 呂陽.分布式網(wǎng)絡爬蟲系統(tǒng)的設計與實現(xiàn) [D].成都：電子科技大學，2013.

[3] 吳昊.主題爬蟲URL分析模型與高度技術研究 [D].哈爾濱：哈爾濱工程大學，2011.

[4] 邱祝文.基于redis的分布式緩存系統(tǒng)架構研究 [J].網(wǎng)絡安全技術與應用，2014（10）：52+54.

[5] 陳亮，廖文和.分布式結構在企業(yè)信息管理系統(tǒng)中的應用 [J].機械制造與自動化，2002（5）：48-50.

[6] 程斌，金海，石柯.一種自適應的分布式調度策略 [J].小型微型計算機系統(tǒng)，2005，26（10）：1793-1798.

[7] 梁正友，張林才.基于Rabin指紋方法的URL去重算法 [J].計算機應用，2008，28（S2）：185-186+203.

[8] 袁志偉，楊鵬，劉旋.雙結構網(wǎng)絡中URL去重機制研究 [J].太原理工大學學報，2016，47（1）：68-74.

作者簡介：陳宇倫（1995-），男，漢族，湖北孝感人，本科在讀，研究方向：分布式爬蟲系統(tǒng)、網(wǎng)絡程序開發(fā)與設計;周奎（1980-），漢族，男，湖北荊州人，講師，碩士研究生，研究方向：智能汽車、圖像處理、嵌入式系統(tǒng)。