隨著Internet信息量的爆炸式增長，搜索引擎越來越受關(guān)注，然而信息量的增加使得搜索引擎中的信息搜集工作變得更加繁重。單機(jī)集中式信息搜集技術(shù)已成為搜索引擎發(fā)展的瓶頸。分布式和并行處理技術(shù)以其強(qiáng)大的處理能力成為信息搜集技術(shù)的首選，但也產(chǎn)生了一些新問題，如保證節(jié)點(diǎn)間不重復(fù)搜集網(wǎng)頁信息、節(jié)點(diǎn)間的任務(wù)分配均衡以及節(jié)點(diǎn)的損壞對(duì)系統(tǒng)的影響等。當(dāng)前，圍繞著分布式信息搜集技術(shù)研究較多的內(nèi)容有：URL匹配算法和劃分策略、節(jié)點(diǎn)間任務(wù)的負(fù)載平衡和系統(tǒng)的可擴(kuò)展性" title="可擴(kuò)展性">可擴(kuò)展性。
　　URL匹配和系統(tǒng)負(fù)載平衡是分布式和并行技術(shù)在信息搜集系統(tǒng)中的關(guān)鍵。通過深入分析現(xiàn)有的幾種分布式信息搜集系統(tǒng)的一些不足，提出了基于URL分級(jí)散列的分布式信息搜集系統(tǒng)。該系統(tǒng)主要針對(duì)中文網(wǎng)絡(luò)信息進(jìn)行信息搜集，使用了兩種適用于中文信息搜集的URL散列函數(shù)對(duì)URL進(jìn)行節(jié)點(diǎn)定位和匹配，該方法使得URL匹配對(duì)資源的開銷減少、負(fù)載平衡性提高。
1 URL匹配和系統(tǒng)負(fù)載平衡
1.1 URL匹配
　　Internet中的信息是異構(gòu)的、復(fù)雜的、多變的，網(wǎng)絡(luò)中存在著大量的重復(fù)鏈接，若不作處理，會(huì)使搜索引擎的Spider在網(wǎng)絡(luò)中爬行時(shí)重復(fù)處理信息，造成系統(tǒng)不必要的資源開銷和存儲(chǔ)空間的浪費(fèi)。搜索引擎通過URL匹配算法解決上述問題，由于URL為字符串，URL匹配的問題實(shí)際為字符串匹配的問題。
　　散列(Hashing)是信息存儲(chǔ)和查詢所采用的一項(xiàng)基本技術(shù)，它能以O(shè)(1)時(shí)間復(fù)雜度對(duì)數(shù)據(jù)進(jìn)行處理，可以很好地用于URL的匹配。天網(wǎng)的開發(fā)者通過實(shí)驗(yàn)評(píng)測表明：對(duì)字符串散列效果很好的ELFhash函數(shù)對(duì)URL散列效果并不是很理想，并給出了兩種效果較好的散列函數(shù)。有些研究中也使用MD5算法對(duì)URL進(jìn)行計(jì)算、處理并匹配，但MD5算法會(huì)消耗大量的系統(tǒng)資源，造成系統(tǒng)整體性能下降。
1.2 系統(tǒng)負(fù)載平衡
　　系統(tǒng)負(fù)載平衡是指分布式系統(tǒng)" title="分布式系統(tǒng)">分布式系統(tǒng)中各節(jié)點(diǎn)間任務(wù)分配的平衡。例如：一個(gè)分布式系統(tǒng)有n個(gè)節(jié)點(diǎn)，對(duì)N份任務(wù)，每個(gè)節(jié)點(diǎn)的任務(wù)量為N/n，這是一種理想狀態(tài)；另一種極端的狀態(tài)是所有的N任務(wù)集中到一個(gè)節(jié)點(diǎn)上，其他n-1個(gè)節(jié)點(diǎn)任務(wù)量為0。
　　系統(tǒng)負(fù)載平衡主要通過URL劃分策略來實(shí)現(xiàn)。URL劃分有動(dòng)態(tài)和靜態(tài)兩種方式。URL動(dòng)態(tài)劃分策略會(huì)使系統(tǒng)負(fù)載平衡性更好一些，但系統(tǒng)資源開銷更大，且不易實(shí)現(xiàn)。靜態(tài)劃分策略實(shí)現(xiàn)簡單，占用系統(tǒng)資源開銷少，若劃分策略合理，也能使系統(tǒng)具有很好的系統(tǒng)負(fù)載平衡。例如：站點(diǎn)散列策略(一個(gè)站點(diǎn)一旦散列到某個(gè)節(jié)點(diǎn)，則該節(jié)點(diǎn)負(fù)責(zé)該站點(diǎn)的所有任務(wù))能很好地將站點(diǎn)均勻地散列到系統(tǒng)的節(jié)點(diǎn)上。
1.3 URL匹配和負(fù)載平衡的問題
　　在分布式信息搜集系統(tǒng)運(yùn)行過程中，URL匹配需要考慮到整個(gè)系統(tǒng)搜集到的URL，通過增加一個(gè)控制系統(tǒng)和節(jié)點(diǎn)的URL共享來解決這種問題。例如：在每個(gè)搜集節(jié)點(diǎn)上部署相同的visited_urls數(shù)據(jù)表(已經(jīng)訪問過的URL數(shù)據(jù)表)，URL與其進(jìn)行匹配。這種方法既浪費(fèi)了節(jié)點(diǎn)的存儲(chǔ)空間又降低了URL匹配的成功率，而且隨著節(jié)點(diǎn)的增加不會(huì)改善反而會(huì)加大通信的開銷，也限制了分布式信息系統(tǒng)性能的提升空間。
　　站點(diǎn)散列策略可以使站點(diǎn)比較均勻地分布到每個(gè)節(jié)點(diǎn)上，但網(wǎng)絡(luò)中每個(gè)站點(diǎn)包含的信息量相差很大。假定幾個(gè)信息量非常大的站點(diǎn)散列到某個(gè)節(jié)點(diǎn)上，而另一個(gè)節(jié)點(diǎn)上的大站點(diǎn)少一些，則這兩個(gè)節(jié)點(diǎn)負(fù)載會(huì)出現(xiàn)不均衡。考慮到站點(diǎn)個(gè)數(shù)S>>節(jié)點(diǎn)個(gè)數(shù)n，上述情況出現(xiàn)的幾率非常低，一般可以忽略。但基于這種方法設(shè)計(jì)的系統(tǒng)搜集到后期會(huì)發(fā)生某些節(jié)點(diǎn)的搜集任務(wù)集中在幾個(gè)包含信息量大的站點(diǎn)上的問題，造成系統(tǒng)搜集的效率急劇下降。當(dāng)系統(tǒng)中的節(jié)點(diǎn)n變大，而針對(duì)搜集的站點(diǎn)S變小的情況下，站點(diǎn)包含信息量不均的問題不能忽略，造成分布式信息搜集系統(tǒng)可擴(kuò)展性和可移植性不好。
2 基于URL分級(jí)散列的分布式信息搜集系統(tǒng)
　　搜集系統(tǒng)通常由三部分組成：控制模塊" title="控制模塊">控制模塊、搜集器和原始數(shù)據(jù)庫?？刂颇K控制搜集器的工作，是整個(gè)系統(tǒng)的核心。搜集器的功能是爬行和解析信息。原始數(shù)據(jù)庫的功能是存儲(chǔ)信息。分布式信息搜集系統(tǒng)按控制模塊的設(shè)計(jì)分為三種" title="三種">三種方案：獨(dú)立方案、動(dòng)態(tài)分配方案以及靜態(tài)分配方案。
2.1 三種設(shè)計(jì)方案的分析
　　獨(dú)立方案：分布式系統(tǒng)中各節(jié)點(diǎn)單獨(dú)運(yùn)行，互不通信。由于網(wǎng)絡(luò)信息的復(fù)雜性，很難找到一種方法將網(wǎng)絡(luò)信息分成單獨(dú)的幾塊，所以這種方案在分布式信息搜集系統(tǒng)中一般很少采用。如果只針對(duì)信息量的搜集而言，獨(dú)立方案的性能最好。例如：一個(gè)分布式系統(tǒng)中有n個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的搜集性能均為p，則整個(gè)系統(tǒng)的信息量的搜集性能為n×p。
　　動(dòng)態(tài)分配方案：分布式系統(tǒng)存在一個(gè)控制模塊，在系統(tǒng)運(yùn)行過程中，動(dòng)態(tài)地分配URL到各個(gè)節(jié)點(diǎn)。利用節(jié)點(diǎn)與控制模塊之間的通信，動(dòng)態(tài)分配方案可以實(shí)現(xiàn)網(wǎng)絡(luò)信息的搜集工作。但是分布式系統(tǒng)內(nèi)部信息的通信占用帶寬，使得系統(tǒng)中每個(gè)節(jié)點(diǎn)的原有搜集性能p下降，系統(tǒng)的信息量搜集性能小于n×p，造成整體性能降低。
　　靜態(tài)分配方案：將URL按事先分配好的策略分配到各個(gè)節(jié)點(diǎn)。靜態(tài)分配方案的關(guān)鍵在于URL劃分策略，一個(gè)好的URL劃分策略占用很少的系統(tǒng)開銷，卻可以很好地解決URL匹配和系統(tǒng)負(fù)載平衡問題。但靜態(tài)分配方案也存在缺陷，即跨節(jié)點(diǎn)的URL問題：一個(gè)URL可以被某些節(jié)點(diǎn)發(fā)現(xiàn)，卻不能被處理。這使得搜集過程中缺失大量的信息。
2.2 基于URL分級(jí)散列方案
　　對(duì)以上三種方案分析表明：獨(dú)立方案信息搜集性能最好；動(dòng)態(tài)分配方案處理網(wǎng)絡(luò)信息搜集最理想化；靜態(tài)分配方案實(shí)現(xiàn)效果最好，但存在技術(shù)上的缺陷。吸取它們的優(yōu)點(diǎn)，筆者給出了基于URL分級(jí)散列方案：分布式系統(tǒng)由一個(gè)控制節(jié)點(diǎn)" title="控制節(jié)點(diǎn)">控制節(jié)點(diǎn)和若干個(gè)搜集節(jié)點(diǎn)組成，搜集節(jié)點(diǎn)只處理定位到本節(jié)點(diǎn)的URL，其余提交控制節(jié)點(diǎn)，由控制節(jié)點(diǎn)負(fù)責(zé)URL的調(diào)度；URL的定位和URL匹配實(shí)行分級(jí)散列處理，根據(jù)URL的地址格式：scheme：//host：port/path，URL定位使用針對(duì)路徑(path)的散列函數(shù)，URL匹配過程中使用針對(duì)站點(diǎn)(host)的散列函數(shù)，并根據(jù)路徑散列函數(shù)進(jìn)行站點(diǎn)內(nèi)匹配。
　　該方案URL的處理流程：首先根據(jù)Spider解析出的URL表對(duì)URL實(shí)行節(jié)點(diǎn)定位，每個(gè)節(jié)點(diǎn)單獨(dú)處理定位到本節(jié)點(diǎn)URL，對(duì)于定位后發(fā)現(xiàn)不屬于本節(jié)點(diǎn)的URL，發(fā)送到控制節(jié)點(diǎn)；然后控制節(jié)點(diǎn)對(duì)這些URL定位，在合適的時(shí)間發(fā)送URL到其定位節(jié)點(diǎn)；同時(shí)每個(gè)節(jié)點(diǎn)對(duì)本節(jié)點(diǎn)搜集到的URL在控制節(jié)點(diǎn)做實(shí)時(shí)更新及控制節(jié)點(diǎn)上待定位的URL做相應(yīng)處理，以免造成URL重復(fù)處理，搜集節(jié)點(diǎn)與控制節(jié)點(diǎn)采取定時(shí)、有限的通信。URL處理流程如圖1所示。

2.3 兩種URL散列函數(shù)的設(shè)計(jì)
　　系統(tǒng)在定位過濾器、匹配過濾器和定位分配器的運(yùn)行中以及在URL定位表和URL數(shù)據(jù)結(jié)構(gòu)表的生成過程中都需要對(duì)URL做大量的散列處理，對(duì)URL散列函數(shù)的要求較高。本文設(shè)計(jì)的系統(tǒng)是面向中文信息的搜集系統(tǒng)，常用的散列函數(shù)在此處的應(yīng)用效果不理想。針對(duì)中文信息的特點(diǎn)，給出了兩種適用于中文信息搜集的URL散列函數(shù)。
　　據(jù)2004年中國互聯(lián)網(wǎng)絡(luò)信息資源數(shù)量調(diào)查報(bào)告，截止到2004年底，CN注冊下的域名總數(shù)為432 077個(gè)，全國域名總數(shù)為1 852 300個(gè)。全國網(wǎng)站總數(shù)約為668 900個(gè)。全國網(wǎng)頁總數(shù)約為650 682 300個(gè)。當(dāng)前中文網(wǎng)址在百萬數(shù)量級(jí)，中文網(wǎng)頁在10億數(shù)量級(jí)，站點(diǎn)的平均頁面數(shù)量在1 000以上。
　　雖然運(yùn)用散列技術(shù)進(jìn)行匹配的成功率無法準(zhǔn)確預(yù)見，但大量的實(shí)驗(yàn)表明：設(shè)裝填因子為a，給定散列表空間為N，對(duì)S個(gè)站點(diǎn)進(jìn)行散列，則a=S/N，當(dāng)a<0.75時(shí)，散列的效果很好?；诖颂匦?，設(shè)計(jì)了URL匹配散列函數(shù)和URL定位散列函數(shù)。
2.3.1 URL匹配散列函數(shù)
　　URL匹配散列函數(shù)是針對(duì)中文站點(diǎn)散列匹配的函數(shù)。設(shè)定站點(diǎn)散列函數(shù)的表空間為221(2 097 152)。由于字符的ASCII碼值的首位為擴(kuò)展位，函數(shù)中取字符的ASCII值的后七位進(jìn)行運(yùn)算。
　　Java語言實(shí)現(xiàn)如下：
　　int result(String url){　　　　// 指定一個(gè)URL字符串
　　int r=0；int s=0；　　　　　　//給定兩個(gè)32位的整型變量r，s=0
　　for(int i=0；i　　r=(r<<7)+(int)url.chatAt(i)；//字符的ASCII碼值與變量r相加后值左移七位
　　s=r；　　　　　　　　　　　　　　//將結(jié)果值賦值給變量s
　　while(!(r==s)){　　　　　　　　　　//相加后結(jié)果值與上次值的1~21位相等時(shí)停止
　　r=s&0x001FFFFF；　　　　　　　　//獲取值的1~21位
　　s=(s&0xFFE00000)>>21；　　　　//獲取值的32~22位，并將獲取值右移21位
　　s=s+r；}　　　　　　　　　　　　//獲取原來值的32~22位與1~21位相加的結(jié)果值
　　return s；　　　　　　　　　　//返回結(jié)果值s
　　}
2.3.2 URL定位散列函數(shù)
　　考慮到每個(gè)站點(diǎn)的平均網(wǎng)頁數(shù)量為1 000多，設(shè)定path散列的表空間N為215(32 768)，該值可以滿足大多數(shù)的站點(diǎn)，對(duì)少數(shù)的大站點(diǎn)超過0.75N，再次進(jìn)行動(dòng)態(tài)散列。定位散列函數(shù)的實(shí)現(xiàn)比站點(diǎn)散列函數(shù)簡單，基于path的長度較長而對(duì)散列的表空間要求不高。函數(shù)中取字符的ASCII碼值的后五位進(jìn)行計(jì)算。
　　Java語言實(shí)現(xiàn)如下：
　　int result(String path){//指定path字符串
　　int r=0；int s=0；//給定兩個(gè)整型變量r，s=0
　　for(int i=0；i　　s=(s<<5)+(int)url.chatAt(i)；　　　　//字符的ASCII碼值與s相加后值左移5位。
　　if(i%3==2){　　　　　　　　　　　　//每三位字符的ASCII碼值為一組
　　r^=s；s=0；}　　　　　　　　　　　　//將r異或s的值賦值給r，s清零
　　}
　　return r^s；　　　　　　　　　　//返回結(jié)果值r^s
　　}
2.4 系統(tǒng)小結(jié)
　　URL分級(jí)散列方案通過URL定位方式實(shí)現(xiàn)URL的劃分，使系統(tǒng)的負(fù)載平衡性和健壯性加強(qiáng)：因?yàn)榫W(wǎng)絡(luò)中的URL數(shù)量遠(yuǎn)遠(yuǎn)大于站點(diǎn)的數(shù)量，所以URL定位方式在URL分配的負(fù)載平衡上優(yōu)于站點(diǎn)散列方式；因?yàn)橐粋€(gè)站點(diǎn)的URL會(huì)散列到不同的節(jié)點(diǎn)，所以單個(gè)節(jié)點(diǎn)的損壞對(duì)站點(diǎn)的影響減小，從而系統(tǒng)的健壯性很好。該方案使用了簡單易行、針對(duì)性強(qiáng)的兩種URL散列函數(shù)，減少了系統(tǒng)運(yùn)行中大量的散列運(yùn)算對(duì)系統(tǒng)資源的消耗，提高了URL匹配的成功率；同時(shí)將URL匹配集中在控制節(jié)點(diǎn)上，URL的劃分使搜集節(jié)點(diǎn)上需要匹配的URL量減少，進(jìn)一步節(jié)省了搜集節(jié)點(diǎn)的資源開銷和URL的匹配成功率。采用二級(jí)散列的方法還使系統(tǒng)具有啟發(fā)式信息搜集的功能：在控制節(jié)點(diǎn)上，URL進(jìn)行站點(diǎn)匹配失敗，即該站點(diǎn)未搜集過，則定義為新站點(diǎn)，控制節(jié)點(diǎn)啟動(dòng)對(duì)此站點(diǎn)的搜集任務(wù)。這種基于站點(diǎn)的啟發(fā)式搜集對(duì)系統(tǒng)首次搜集效果明顯。
　　該方案集中了以往三種方案的優(yōu)點(diǎn)：搜集節(jié)點(diǎn)只處理本節(jié)點(diǎn)的URL使其具有獨(dú)立搜集的功能；定位過濾器實(shí)現(xiàn)靜態(tài)劃分策略；控制節(jié)點(diǎn)使其具備動(dòng)態(tài)分配的功能。
3 實(shí)驗(yàn)分析
　　采用Java語言模擬分布式信息搜集系統(tǒng)的工作，主要測試三個(gè)方面：分布式信息搜集系統(tǒng)的性能提高、負(fù)載平衡和URL匹配。
　　系統(tǒng)的搜集節(jié)點(diǎn)分別設(shè)置為1、3、5、7、11、13，得到URL搜集性能統(tǒng)計(jì)表如表1所示。

　　由表1得出：隨著分布式系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)的增加，系統(tǒng)搜集的信息量也增加，系統(tǒng)的整體性能也得到了提高，但是節(jié)點(diǎn)數(shù)的增加卻使單個(gè)搜集節(jié)點(diǎn)的性能有所下降?？紤]在利用Java多線程技術(shù)進(jìn)行的仿真試驗(yàn)中，線程的增多和網(wǎng)絡(luò)信息量的增加，會(huì)使系統(tǒng)資源和網(wǎng)絡(luò)通信開銷過大，單個(gè)搜集節(jié)點(diǎn)的性能應(yīng)該有所提高，分布式系統(tǒng)的性能基本上隨著搜集節(jié)點(diǎn)的增加呈線性增長。
　　URL匹配性能統(tǒng)計(jì)表如表2所示。由表2得出，系統(tǒng)中URL很好地散列到各個(gè)節(jié)點(diǎn)且節(jié)點(diǎn)上的URL匹配成功率非常高。主要匹配集中在URL控制節(jié)點(diǎn)上，此節(jié)點(diǎn)不負(fù)責(zé)對(duì)信息的搜集，只是用來調(diào)度跨節(jié)點(diǎn)的URL和構(gòu)造URL數(shù)據(jù)結(jié)構(gòu)表，控制節(jié)點(diǎn)采用定時(shí)有限的調(diào)度方式，因此，控制節(jié)點(diǎn)任務(wù)的繁重不會(huì)使系統(tǒng)的搜集性能下降。