雙結(jié)構(gòu)網(wǎng)絡中URL去重機制研究

袁志偉，楊　鵬，劉　旋

(東南大學 計算機科學與工程學院，計算機網(wǎng)絡和信息集成教育部重點實驗室, 南京 211100)

?

雙結(jié)構(gòu)網(wǎng)絡中URL去重機制研究

袁志偉，楊鵬，劉旋

(東南大學 計算機科學與工程學院，計算機網(wǎng)絡和信息集成教育部重點實驗室, 南京 211100)

摘要:針對雙結(jié)構(gòu)網(wǎng)絡的特點及其URL去重面臨的挑戰(zhàn),根據(jù)Bloom Filter的工作原理,提出一種基于可擴展的動態(tài)可分裂Bloom Filter的URL去重機制,并在原型系統(tǒng)中進行實現(xiàn)和部署。實驗結(jié)果表明，該機制能夠有效適用于大規(guī)模、高性能和分布式的雙結(jié)構(gòu)網(wǎng)絡爬蟲應用。

關鍵詞:統(tǒng)一內(nèi)容標簽去重;動態(tài)可分裂;布隆過濾器;雙結(jié)構(gòu)網(wǎng)絡;網(wǎng)絡爬蟲

當今互聯(lián)網(wǎng)已經(jīng)由服從泊松分布的隨機網(wǎng)絡演變?yōu)榉膬缏煞植嫉臒o標度網(wǎng)絡[1],主要表現(xiàn)為極少數(shù)網(wǎng)站(如Google,YouTube等)擁有遠遠高于普通網(wǎng)站成千上萬倍的連接數(shù),成為互聯(lián)網(wǎng)80%流量的主要源頭[2]。并且傳統(tǒng)網(wǎng)絡中點對點傳輸?shù)捏w系結(jié)構(gòu),導致熱門信息在互聯(lián)網(wǎng)中冗余傳輸,進一步引發(fā)互聯(lián)網(wǎng)流量的無標度增長。為了分擔互聯(lián)網(wǎng)骨干網(wǎng)流量,文獻[2-5]主張為當今互聯(lián)網(wǎng)主結(jié)構(gòu)增加具有廣播推送能力的播存次結(jié)構(gòu),形成雙結(jié)構(gòu)二元互補網(wǎng)絡,簡稱為雙結(jié)構(gòu)網(wǎng)絡。

播存次結(jié)構(gòu)由廣播發(fā)送端、邊緣服務器和用戶終端三部分組成,如圖1所示。廣播發(fā)送端借助于網(wǎng)絡爬蟲將互聯(lián)網(wǎng)中熱門內(nèi)容進行統(tǒng)一標引并形成統(tǒng)一內(nèi)容標簽UCL(Uniform Content Label),UCL的數(shù)量巨大但只有1 KB,保存于用戶終端,而網(wǎng)頁全文數(shù)據(jù)容量很大,保存于離用戶若干跳的邊緣服務器。衛(wèi)星廣播只將UCL推送到用戶終端(PC機、手機、pad等),而將UCL和網(wǎng)頁全文都推送到邊緣服務器。用戶通過瀏覽UCL摘要信息,決定是否向邊緣服務器獲取網(wǎng)頁全文。只有當邊緣服務器不存在網(wǎng)頁全文時,才需要向互聯(lián)網(wǎng)遠端服務器獲取。

圖1　雙結(jié)構(gòu)網(wǎng)絡架構(gòu)Fig.1　Dual-structural network

UCL的數(shù)量巨大,需要通過網(wǎng)絡爬蟲對熱門內(nèi)容進行自動化標引,然而互聯(lián)網(wǎng)URL數(shù)量數(shù)以億計且URL間可能相互鏈接,網(wǎng)絡爬蟲在爬取過程中會將已經(jīng)爬取的URL再次加入到等待爬取的URL隊列之中,這樣導致網(wǎng)絡爬蟲多次下載同一個頁面,消耗了網(wǎng)絡帶寬資源并降低了爬取效率。所以網(wǎng)絡爬蟲在爬取過程中需要判斷每一條URL是否已經(jīng)被爬取過,以避免重復爬取,這個過程稱為URL去重[6],是任何一個網(wǎng)絡爬蟲亟需解決的關鍵問題。

筆者首先介紹了Bloom Filter的工作原理,并在綜合分析了雙結(jié)構(gòu)網(wǎng)絡中網(wǎng)絡爬蟲URL去重的基本需求后,提出一種針對雙結(jié)構(gòu)網(wǎng)絡中去除重復URL的動態(tài)可分裂Bloom Filter。最后在原型系統(tǒng)中驗證了該方案的有效性和可行性。

1Bloom Filter

經(jīng)典Bloom Filter[7-14]由1個二進制數(shù)組和k個哈希映射函數(shù)(Map Hash)組成,用來表示一個集合,其基本工作原理是Bloom Filter通過k個哈希映射函數(shù)將元素映射為二進制數(shù)組的k個位置。當向集合插入某元素時,使用k個哈希映射函數(shù)對該元素進行k次哈希計算,并且將二進制數(shù)組中與k個哈希計算結(jié)果相對應的k個二進制位置為1。在查詢某元素是否在集合中時,使用k個哈希映射函數(shù)對該元素進行k次哈希計算,只有當二進制數(shù)組中與k個哈希計算結(jié)果對應的二進制位都為1時,才判定該元素在集合中。二進制數(shù)組中的每一位初始化為0。圖2為k=3時,經(jīng)典Bloom Filter的示例圖。

圖2　k=3時經(jīng)典Bloom Filter的示例圖Fig.2　Example of classical Bloom Filter when k is 3

由于Bloom Filter使用哈希映射的方式存儲元素,查詢時有可能會發(fā)生誤判(false positive)。誤判是指某個不存在于集合中的元素被誤判為屬于該集合[7-8]。假設二進制數(shù)組的長度為m,集合中元素個數(shù)為n,則誤判率f的計算公式[7-8]為:

(1)

式中,p0表示二進制數(shù)組中某一位為0的概率。理論計算表明最小誤判率fmin的計算公式[7-8]為:

(2)

此時,哈希映射函數(shù)的個數(shù)k的計算公式[7-8]為:

(3)

由式(2)可知,Bloom Filter的誤判率主要取決于m和n的比值,并且誤判率只能減小,無法消除。所以Bloom Filter不適合“零錯誤率”的應用場景,但是對于容忍低誤判率的應用場景下,Bloom Filter可以通過極低的誤判率換取到存儲空間的極大節(jié)省和讀寫性能的極大提高。

Bloom Filter是一個時間和空間效率很高的數(shù)據(jù)結(jié)構(gòu),它在不同領域獲得了廣泛的應用。文獻[9]使用Bloom Filter設計了分布式的Web 緩存共享機制,文獻[10]使用Bloom Filter表示De Bruijn graph,文獻[11]使用Bloom Filter計算DNA的子串的數(shù)量,文獻[12]則使用Bloom Filter進行深度包檢測,文獻[13]使用Bloom Filter存儲CCN中的PIT表,文獻[14]使用Bloom Filter壓縮多播轉(zhuǎn)發(fā)表,并對經(jīng)典Bloom Filter進行了改進。

2雙結(jié)構(gòu)網(wǎng)絡中的URL去重

網(wǎng)絡爬蟲的去重可以看作一個URL篩選過程。將所有URL看作一個隊列Q=[x1,x2,x3, …,xN],其中N表示隊列中元素的數(shù)量。如圖3所示,對于每一個從隊列中彈出的元素,網(wǎng)絡爬蟲都需要運行去重算法判斷是否需要進一步爬取。

圖3　URL去重流程圖Fig.3　Graph of detecting duplicated URLs

雙結(jié)構(gòu)網(wǎng)絡使用分布式爬蟲并行爬取熱門內(nèi)容,為了盡快地將當天新增熱門內(nèi)容進行廣播,每一個網(wǎng)絡爬蟲每天都需要爬取大量的網(wǎng)頁,從而對URL去重的效率提出很高的要求。文獻[15]指出對于一個每秒鐘爬取300個網(wǎng)頁的爬蟲系統(tǒng),每秒需要進行至少2 000次的URL去重查詢工作。

為了加快處理效率,雙結(jié)構(gòu)網(wǎng)絡使用Bloom Filter進行URL去重。除此之外,雙結(jié)構(gòu)網(wǎng)絡中的URL去重策略還面臨以下幾個挑戰(zhàn):

1) 雙結(jié)構(gòu)網(wǎng)絡使用內(nèi)存數(shù)據(jù)庫存儲Bloom Filter。由于內(nèi)存數(shù)據(jù)庫的容量受到內(nèi)存的限制[16-17],所以雙結(jié)構(gòu)網(wǎng)絡中的Bloom Filter不能太長。

2) 互聯(lián)網(wǎng)中的URL數(shù)量眾多,而且會隨時間增長,一段時間之后,Bloom Filter會超過預先設定的誤判率的要求,需要對Bloom Filter進行擴展。所以雙結(jié)構(gòu)網(wǎng)絡中的Bloom Filter應該是可以擴展的。

3) 為了避免帶寬成為瓶頸,雙結(jié)構(gòu)網(wǎng)絡的網(wǎng)絡爬蟲應該是分布式部署的。同時為了加快處理效率,每一個網(wǎng)絡爬蟲應該不需要和其他網(wǎng)絡爬蟲進行交互,就可以確定某一條URL是否已經(jīng)被爬取過。

當前基于Bloom Filter的URL去重方案在可擴展性、性能等方面存在缺陷,并不能適應于雙結(jié)構(gòu)網(wǎng)絡。Internet Archive 爬蟲使用32 kB大小的Bloom Filter存儲每一個域名下URL,在之后的批處理階段會使用2 GB空間的Bloom Filter來存儲多個網(wǎng)站的URL[6]。Apoide爬蟲采用了和Internet Archive爬蟲相似的思路,每一個域名都使用了一個8 kB的Bloom Filter來存儲該域名下的URL[18]。但是雙結(jié)構(gòu)網(wǎng)絡的網(wǎng)絡爬蟲主要爬取互聯(lián)網(wǎng)中的熱門網(wǎng)站,而使用一個固定大小的Bloom Filter存儲熱門網(wǎng)站的URL是不夠的。

為了提高在雙結(jié)構(gòu)網(wǎng)絡中Bloom Filter的并發(fā)讀寫效率,一種合理且高效的方案是將Bloom Filter分布式存儲,增強并行化,提高效率。筆者結(jié)合雙結(jié)構(gòu)網(wǎng)絡環(huán)境的特點提出了一種動態(tài)可分裂Bloom Filter(Dynamic Splittable Bloom Filter, DSBF)。

圖4　初始時動態(tài)可分裂Bloom Filter的結(jié)構(gòu)Fig.4　The initial structure of splitting DSBF

圖5　分裂中的動態(tài)可分裂Bloom FilterFig.5　The structure of splitting DSBF

3一種動態(tài)可分裂的Bloom Filter

如圖6所示,動態(tài)可分裂Bloom Filter采用樹狀的分層存儲結(jié)構(gòu),它用到兩種哈希函數(shù),一種是經(jīng)典Bloom Filter中的哈希映射函數(shù),一種是新引入的哈希定位函數(shù)(LocHash)。根結(jié)點(第0層)中存放一個哈希定位函數(shù)。在除樹根外的各層中,每一個葉結(jié)點中存放一個經(jīng)典的Bloom Filter(稱為葉片Bloom Filter),它用于存儲元素;每一個非葉結(jié)點中存放一個哈希定位函數(shù),它把沒有存儲在本結(jié)點的元素導向到它的子結(jié)點。動態(tài)可分裂Bloom Filter主要包含4種操作:初始化,插入操作,分裂操作和查詢操作。

圖6　分裂后的動態(tài)可分裂Bloom FilterFig.6　The structure of splitted DSBF

如圖4所示,動態(tài)可分裂Bloom Filter初始時只包含根結(jié)點和第一層的c個葉結(jié)點。c表示初始時預先設定的葉片Bloom Filter的個數(shù),c的大小由誤判率上限fmax、元素個數(shù)n和每個葉片Bloom Filter的長度m共同決定。

向動態(tài)可分裂Bloom Filter插入元素時,需要對元素進行H次(H代表樹的高度,H≥1)哈希定位計算,以確定該數(shù)據(jù)元素具體存儲到哪一個葉片Bloom Filter中。具體過程如下:首先,使用根結(jié)點的哈希定位函數(shù)對該數(shù)據(jù)元素進行哈希計算,判斷該數(shù)據(jù)元素存儲到根結(jié)點的哪一個子結(jié)點中。接著,判斷該子結(jié)點是否是葉結(jié)點。如果是,則將該數(shù)據(jù)元素直接存儲到該葉片Bloom Filter中;如果不是,則使用該非葉結(jié)點的哈希定位函數(shù)繼續(xù)上述計算過程,直至將該數(shù)據(jù)元素最終定位并存儲到一個葉片Bloom Filter為止。

當某一個葉片Bloom Filter(記做結(jié)點d)存儲的元素過多,導致它的誤判率超過fmax時,需要對其進行分裂。具體過程如下:首先,在待分裂結(jié)點d的下一層新增c個葉片Bloom Filter,并使它們成為結(jié)點d的子結(jié)點。接著,為待分裂結(jié)點d增加一個哈希定位函數(shù),并通過該哈希定位函數(shù)將結(jié)點d存儲的數(shù)據(jù)元素通過再哈希的方式,存儲到d的對應子結(jié)點(某個葉片Bloom Filter)中。最后刪除待分裂結(jié)點d存儲的Bloom Filter,只保留結(jié)點d的哈希定位函數(shù)。圖5和圖6是分裂操作的示意圖。分裂過程中,動態(tài)可分裂Bloom Filter仍舊可以對外提供服務:插入數(shù)據(jù)元素時,將元素插入到待分裂結(jié)點d的子結(jié)點中,查詢時,則需要查詢待分裂結(jié)點d和它的子結(jié)點。

查詢操作類似于插入操作。需要對元素進行H次哈希定位計算,以確定該數(shù)據(jù)存儲在哪一個葉片Bloom Filter中,之后再對該葉片Bloom Filter執(zhí)行具體的查詢操作。

動態(tài)可分裂Bloom Filter的結(jié)構(gòu)是一棵樹,樹中的葉結(jié)點提供讀寫服務,內(nèi)部結(jié)點只提供元素的導向服務,所有的元素都會存儲到葉結(jié)點之中。在接下來的討論中,我們假定每一個葉片Bloom Filter二進制數(shù)組長度為m,集合中元素個數(shù)為n,誤判率上限為fmax。

動態(tài)可分裂Bloom Filter的每一次分裂都是有代價的,為了減少分裂次數(shù),它初始化之后的c個葉片Bloom Filter應該足夠存儲預先估計的元素個數(shù)。此時每一個葉結(jié)點可以存儲的元素個數(shù)u的計算公式為，

(4)

那么c的計算公式為,

(5)

由于c必須是一個整數(shù),而且c越大誤判率會越低,所以公式5對于所求的c取上界。此時哈希映射函數(shù)的個數(shù)k的計算公式為,

(6)

任何Bloom Filter都存在誤判率,動態(tài)可分裂Bloom Filter也不例外。由于動態(tài)可分裂Bloom Filter使用哈希定位的方式將元素存儲到不同的葉結(jié)點中,所以它相對于單個Bloom Filter具有更好的誤判率。動態(tài)可分裂Bloom Filter的查詢最終都是對單個葉結(jié)點的查詢,所以它的誤判率主要取決于誤判率最大的葉結(jié)點。那么,誤判率fmax的計算公式為,

(7)

式中：s表示葉結(jié)點的個數(shù)；fi表示第i個葉結(jié)點的誤判率。如果哈希定位函數(shù)的輸出是完全均勻的,即元素的導向過程是完全隨機的,那么所有葉結(jié)點的誤判率都相等,此時誤判率fmax就是任意一個葉結(jié)點的誤判率,此時fmax的計算公式如下,

(8)

和式(2)進行對比可知,動態(tài)可分裂Bloom Filter可以取得比經(jīng)典Bloom Filter更低的誤判率。盡管這種降低是以更大的存儲空間為代價,但是動態(tài)可分裂的Bloom Filter可以將葉片Bloom Filter分布式存儲,存儲空間不會成為動態(tài)可分裂Bloom Filter的負擔。

動態(tài)可分裂Bloom Filter中包含了兩種哈希函數(shù):哈希映射函數(shù)和哈希定位函數(shù)。哈希映射函數(shù)存在于葉結(jié)點中,它的值域是{1,2,3,…,m},它的計算結(jié)果映射了葉片Bloom Filter的某一個二進制位。哈希定位函數(shù)的值域是{1,2,3,…,c},它存在于內(nèi)部結(jié)點中,它的計算結(jié)果決定了內(nèi)部結(jié)點將元素導向到哪一個子結(jié)點。

由于哈希定位函數(shù)和哈希映射函數(shù)的作用并不相同,所以哈希定位函數(shù)和哈希映射函數(shù)可以使用相同的常用哈希函數(shù)取模(分別對m和c取模)實現(xiàn)。哈希定位函數(shù)的結(jié)果決定了內(nèi)部結(jié)點將元素導向到哪一個子結(jié)點,為了保證所有子結(jié)點能夠均勻負擔讀寫任務,要求不同層之間的哈希定位函數(shù)相互不同。如果不同層的哈希定位函數(shù)相同,那么會使元素的導向不再隨機,造成部分葉結(jié)點無法提供讀寫功能。如圖6所示,如果LocHash(root)和LocHash(root,3)是同一個哈希定位函數(shù),那么所有導向到結(jié)點DSBF(root,3)的元素都會存儲到DSBF((root,3),3)中,結(jié)點DSBF(root,3)的另外4個子結(jié)點將無法提供服務。但是,同一層的哈希定位函數(shù)可以相同的,這是因為同一層結(jié)點的元素導向過程不會產(chǎn)生相互影響,能夠保證元素導向的隨機性。

(9)

由式(9)可知,動態(tài)可分裂Bloom Filter的存儲能力是隨著H的增加以幾何級數(shù)增加的。

上文為了討論方便,設定了每次分裂都分裂為c個子結(jié)點,實際上分裂的子結(jié)點數(shù)量并不一定必須是c。

由于動態(tài)可分裂Bloom Filter的讀寫增加了元素從根結(jié)點到葉結(jié)點的導向過程,元素需要經(jīng)過最多H次的哈希定位計算,會略微增加讀寫時間。但是由于其存儲能力以幾何級數(shù)增加,即便元素數(shù)量很多,它的層數(shù)也不會太大。經(jīng)典Bloom Filter的時間復雜度為O(k),動態(tài)可分裂Bloom Filter的時間復雜度為O(k+L),而O(k)=O(k+L)=O(1)。因此,動態(tài)可分裂Bloom Filter能夠取得了經(jīng)典Bloom Filter同樣的時間效率。

4實驗與結(jié)果分析

筆者使用播存次結(jié)構(gòu)原型系統(tǒng)中爬取的150多萬URL進行動態(tài)可分裂Bloom Filter測試工作,每一個Bloom Filter都使用Redis數(shù)據(jù)庫進行存儲。

圖7　動態(tài)可分裂Bloom Filter和經(jīng)典Bloom Filter的誤判率對比Fig.7　The false rate comparison of the DSBF and CBF

實際上經(jīng)典Bloom Filter可以看作H=1,c=1的動態(tài)可分裂Bloom Filter。圖7展示了兩種Bloom Filter的誤判率對比結(jié)果,每一條曲線都代表了H=1的動態(tài)可分裂Bloom Filter的誤判率,其中c=1的曲線表示經(jīng)典Bloom Filter的誤判率,m表示葉片Bloom Filter中二進制數(shù)組的長度,n表示動態(tài)可分裂Bloom Filter存儲的URL數(shù)量。實驗首先選取n條URL存入動態(tài)可分裂Bloom Filter中,然后選取另外的n/10條URL進行誤判率的計算。由圖可知,在存儲空間相同的情況下,動態(tài)可分裂Bloom Filter的誤判率和經(jīng)典Bloom Filter的誤判率相同,如果使用更多的存儲空間,動態(tài)可分裂Bloom Filter可以取得更低的誤判率。雖然這種降低是以更多的存儲空間為代價,但是由于動態(tài)可分裂Bloom Filter可以將葉片Bloom Filter分布式存儲,所以存儲空間的增加并不會成為它的劣勢。

由于動態(tài)可分裂Bloom Filter的葉片Bloom Filter可以分布式存儲,每一次的URL去重可能需要網(wǎng)絡數(shù)據(jù)傳輸,所以網(wǎng)絡延遲可能會成為動態(tài)可分裂Bloom Filter的瓶頸,一種合理且有效的方式是采用批處理的方式解決網(wǎng)絡時延問題,即一次向動態(tài)可分裂Bloom Filter發(fā)送多條URL。

圖8　去重效率實驗結(jié)構(gòu)圖Fig.8　Experiment frame work of detecting duplicated URLs

圖9　去重效率實驗結(jié)果Fig.9　Experiment results of detecting duplicated URLs

URL去重效率是動態(tài)可分裂Bloom Filter的重要性能指標,本文通過實驗測試動態(tài)可分裂Bloom Filter的去重效率。圖8展示了去重效率實驗的結(jié)構(gòu)圖。實驗構(gòu)建了一個H=1,c=3的動態(tài)可分裂Bloom Filter,如圖8所示,A,B,C分別存儲了一個葉片Bloom Filter, C部署了一個爬蟲進程,該進程通過多線程的方式進行URL的去重,每一個線程每次處理300條URL數(shù)據(jù)。實驗中,通過ping命令進行測試發(fā)現(xiàn),傳輸64 bytes數(shù)據(jù),C點到A點時延約為0.35～0.42 ms,而C點到B點的時延約為0.38～0.45 ms。

圖9為動態(tài)可分裂Bloom Filter的URL去重效率實驗結(jié)果圖。每一次實驗都會進行100萬條URL的去重,由圖中可知,H=1,c=3的動態(tài)可分裂Bloom Filter每秒鐘約可以處理1.5×104條URL,基本可以滿足雙結(jié)構(gòu)網(wǎng)絡中多個網(wǎng)絡爬蟲并行進行URL去重的需要,并且隨著c的增加動態(tài)可分裂Bloom Filter的處理速率能夠進一步增加。

圖10　Internet Archive中每個Bloom Filter存儲的URL數(shù)量Fig.10　The unmber of URLs for eachbloom filter in internet archive

Internet Archive 使用32 kB大小的Bloom Filter存儲一個域名下的URL,如果k=10，根據(jù)式(3),該Bloom Filter約可以存儲1.8×104URL。固定大小的Bloom Filter存儲大型網(wǎng)站空間不足,存儲小型網(wǎng)站又會造成空間的浪費。本文使用網(wǎng)絡爬蟲對騰訊網(wǎng)、新浪網(wǎng)、新華網(wǎng)等網(wǎng)站進行爬取,圖10展示了爬蟲在一天時間里所提取到的各個網(wǎng)站的URL數(shù)量,即為Internet Archive 爬蟲中每個Bloom Filter中存儲的URL數(shù)量。由圖10可知,Internet Archive 爬蟲32 kB大小的Bloom Filter并不足以存儲熱門網(wǎng)站的URL數(shù)量,并且由于每一個Bloom Filter存儲的URL數(shù)量也不夠均衡,會造成空間的浪費。如果將上述所有URL存儲到H=1,c=10的DSBF中,則每一個Bloom Filter的存

儲的URL數(shù)量基本均衡,圖11為實驗結(jié)果圖。

圖11　DSBF每個Bloom Filter存儲的URL數(shù)量Fig.11　The number of URLs for each bloom filter in DSBF

5結(jié)論

Bloom Filter能夠適用于大規(guī)模數(shù)據(jù)集合的存儲和查詢工作。只需要以極低的誤判率為代價,它就能夠大大節(jié)約存儲空間并且查詢和插入時間不會隨著集合中元素的增加而增加。筆者介紹了Bloom Filter的原理,并圍繞雙結(jié)構(gòu)網(wǎng)絡中URL去重的實際需求后,提出了更加適用于分布式部署的動態(tài)可分裂Bloom Filter的URL去重機制,就其相關參數(shù)進行了理論分析,在原型系統(tǒng)中實驗證明了其有效性和可行性。

參考文獻：

[1]LI X,CHEN G.A local-world evolving network model[J].Physica A:Statistical Mechanics and its Applications,2003,328(1):274-286.

[2]楊鵬, 李幼平.二元互補未來互聯(lián)網(wǎng)體系結(jié)構(gòu)[J].復雜系統(tǒng)和復雜性科學,2014,11(1):53-59.

[3]楊鵬,李幼平.播存網(wǎng)絡體系結(jié)構(gòu)普適模型及實現(xiàn)模式[J].電子學報,2015,5(5):974-979.

[4]李幼平, 楊鵬.共享文化大數(shù)據(jù)的新機制 [J].中國計算機學會通訊,2013,5(9):36-40.

[5]顧梁,楊鵬,羅軍舟.一種播存網(wǎng)絡環(huán)境下的 UCL 協(xié)同過濾推薦方法[J].計算機研究與發(fā)展,2015,52(2):475-486.

[6]HEYDON A,NAJORK M.Mercator:A scalable,extensible web crawler[J].World Wide Web,1999,2(4):219-229.

[7]BLOOM B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970,13(7):422-426.

[8]BRODER A,MITZENMACHER M.Network applications of bloom filters: A survey[J].Internet Mathematics,2004,1(4):485-509.

[9]FAN L,CAO P,ALMEIDA J,et al.Summary cache:a scalable wide-area web cache sharing protocol[J].IEEE/ACM Transactions on Networking (TON),2000,8(3):281-293.

[10]CHIKHI R,RIZK G.Space-efficient and exact de Bruijn graph representation based on a Bloom filter[J].Algorithms for Molecular Biology,2013,8(22):1.

[11]MELSTED P,PRITCHARD J K.Efficient counting ofk-mers in DNA sequences using a bloom filter[J].BMC bioinformatics,2011,12(1):333.

[12]KOCAK T,KAYA I.Low-power bloom filter architecture for deep packet inspection[J].Communications Letters,IEEE,2006,10(3):210-212.

[13]HEYDON A,NAJORK M，MERC Y W,et al.DiPIT:a distributed bloom-filter based PIT table for CCN nodes[C]∥IEEE.21st International Conference on Computer Communications and Networks,USA:NY，2012:1-7.

[14]LI D,CUI H,HU Y,et al.Scalable data center multicast using multi-class bloom filter[C]∥IEEE.19th IEEE International Conference on Network Protocols(ICNP),[S.l.]，2011:266-275.

[15]SHKAPENYUK V,SUEL T.Design and implementation of a high-performance distributed web crawler[C]∥IEEE..Proceedings of 18th international conference on data engineering.USA:California,2002:357-368.

[16]HAN J,E HH,LE G,et al.Survey on NoSQL database[C]∥IEEE.6th international conference on Pervasive computing and applications.Port Eliabeth:IEEE,2011:363-366.

[17]STRAUCH C,SITES U L S,KRIHA W.NoSQL databases[EB/OL].[2012-07-11].http:∥www.christof-strauch.de/nosqldbs.pdf.

[18]SINGH A,SRIVATSA M,LIU L,et al.Apoidea:A decentralized peer-to-peer architecture for crawling the world wide web[C]∥Distributed Multimedia Information Retrieval.Berlin Heidelberg：Springer,2004:126-142.

(編輯：朱倩)

Research on Detecting Duplicated URL in Dual-Structural Network

YUAN Zhiwei，YANG Peng，LIU Xuan

(SchoolofComputerScienceandEngineering,KeyLaboratoryofComputerNetworkandInformationIntegrationoftheMinistryofEducation,SoutheastUniversity,Nanjing211100，China)

Abstract:In this paper,the concept of Dual-Structural Network is firstly introduced and the principles of Bloom Filter are surveyed.Then,the basic requirements for detecting duplicated URLs in Dual-Structural Network are analyzed. Moreover,a dynamic splittable Bloom Filter for web crawlers is proposed, which can increase its capacity according to application requirements and fit large-scale, high-performance and distributed web crawlers. Finally, the feasibility and efficiency of the proposed Bloom Filter is demonstrated by a series of experiments.

Key words:duplicated URL detection;dynamic splittable;bloom filter;dual-structural network;web crawler

中圖分類號:TP301

文獻標識碼:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.01.014

作者簡介：袁志偉(1990-)，男，山東日照人，碩士生，主要從事網(wǎng)絡安全、雙結(jié)構(gòu)網(wǎng)絡的研究，(E-mail) yuluoyzw@163.com通訊作者：楊鵬，男，博士，副教授，主要從事未來網(wǎng)絡體系結(jié)構(gòu)、分布式計算的研究，(E-mail) pengyang@seu.edu.cn

基金項目：國家863計劃課題基金資助項目：基于內(nèi)容聚類與興趣適配的高效內(nèi)容分發(fā)技術(shù)(2013AA013503)；國家自然科學基金資助項目：具有互補雙結(jié)構(gòu)的新型網(wǎng)絡及關鍵技術(shù)研究(61472080)；中國工程院咨詢研究基金資助項目：國家第二網(wǎng)絡戰(zhàn)略研究(2015-XY-04)

收稿日期：2015-05-25

文章編號:1007-9432(2016)01-0068-07