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

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

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