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

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