張小琴，王曉輝

(中南民族大學(xué) 圖書(shū)館，武漢430074)

在信息檢索過(guò)程中，移動(dòng)代理中的URL隊(duì)列是最關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，一般采用內(nèi)存數(shù)據(jù)結(jié)構(gòu)，如:采用鏈表來(lái)實(shí)現(xiàn)URL隊(duì)列.而對(duì)于大規(guī)模的搜索引擎，將會(huì)有數(shù)十億的URL待抓取，這種數(shù)據(jù)結(jié)構(gòu)不能滿(mǎn)足要求［1］.于是，人們提出了使用內(nèi)存數(shù)據(jù)庫(kù)的方法存儲(chǔ)URL，Berkeley DB［2］是應(yīng)用較廣的一種嵌入式數(shù)據(jù)庫(kù).在Berkeley DB嵌入式數(shù)據(jù)庫(kù)中，將URL對(duì)應(yīng)到同一個(gè)Key值的隊(duì)列當(dāng)中，這樣會(huì)導(dǎo)致處理URL時(shí)，被放入到同一個(gè)線程中處理.那么，對(duì)于大大小小不同的站點(diǎn)會(huì)有很多不同的隊(duì)列，大門(mén)戶(hù)網(wǎng)站形成的隊(duì)列會(huì)非常臃腫，而且多線程處理器不能充分發(fā)揮作用，使得線程池中大多數(shù)線程處于等待狀態(tài)，而影響移動(dòng)代理抓取速度［3］.

針對(duì)上述問(wèn)題，本文以 Heritrix［4，5］為架構(gòu)，結(jié)合Berkeley DB嵌入式數(shù)據(jù)庫(kù)，引入散列算法改進(jìn)隊(duì)列存儲(chǔ)URL方式，將URL盡可能多地散列到不同的隊(duì)列當(dāng)中，即對(duì)應(yīng)不同的Key值，使多線程處理器充分發(fā)揮其功能.

1 Heritrix與Berkeley DB連接實(shí)現(xiàn)

為了實(shí)現(xiàn)所需的抓取邏輯，在現(xiàn)有的Heritrix框架基礎(chǔ)上對(duì)各個(gè)組件進(jìn)行擴(kuò)展.Heritrix的主要組織結(jié)構(gòu)為:(1)抓取任務(wù)CrawlOrder類(lèi):該類(lèi)是整個(gè)抓取工作的起點(diǎn).一次抓取任務(wù)包括許多屬性，建立一個(gè)任務(wù)的方式有很多種.(2)中央控制器 Crawl-Controller:該類(lèi)決定抓取任務(wù)的開(kāi)始和結(jié)束.Crawl-Controller的類(lèi)結(jié)構(gòu)如圖 1 所示［6］.(3)Frontier:一次抓取任務(wù)需要設(shè)定一個(gè)Frontier，以此來(lái)不斷為其每個(gè)線程提供URL.Frontier類(lèi)，是移動(dòng)代理的核心類(lèi)，為多線程處理提供鏈接.Heritrix采用多線程機(jī)制，提供了一個(gè)標(biāo)準(zhǔn)的線程池ToePool，用于管理所有的抓取線程.

圖1 Crawl-Controller的類(lèi)結(jié)構(gòu)Fig.1 Structure of Crawl-Controller

從Heritrix架構(gòu)可以看到，一個(gè)鏈接在被處理之后，會(huì)得到新生成的鏈接，這些新鏈接被Frontier類(lèi)中的schedule方法調(diào)用，將其加入到URL隊(duì)列進(jìn)行后續(xù)處理.但在進(jìn)入隊(duì)列之前，要在已經(jīng)生成的一張HashMap中進(jìn)行檢查，查看該條鏈接是否已經(jīng)被處理器鏈處理過(guò).

Berkeley DB可以有效解決URL隊(duì)列中的存放問(wèn)題，Berkeley DB的事務(wù)子系統(tǒng)能夠完成事務(wù)支持.對(duì)Berkeley DB的所有操作都是通過(guò)API接口函數(shù)完成.為了使用該數(shù)據(jù)庫(kù)，在Heritrix中構(gòu)造如下關(guān)鍵類(lèi):

1)BdbMutipleWorkQueues;

2)BdbWorkQueue;

3)BdbUriUniqFilter;

4)BdbFrontier.

這4個(gè)類(lèi)中，前兩個(gè)配合完成URL隊(duì)列排隊(duì)工作，后兩者完成對(duì)等待進(jìn)隊(duì)的URL查重工作.移動(dòng)代理利用上述4個(gè)類(lèi)完成鏈接的處理工作，再經(jīng)過(guò)URL處理鏈，實(shí)現(xiàn)一個(gè)移動(dòng)代理完成捕獲URL的全過(guò)程.

Heritrix使用Berkeley DB進(jìn)行鏈接隊(duì)列的構(gòu)建，鏈接隊(duì)列在進(jìn)入BdbMultipleWorkQueue之前，賦予一個(gè)Key值，對(duì)應(yīng)的鏈接和Key值捆綁之后成為一個(gè)隊(duì)列.那么Key值作為鏈接隊(duì)列的標(biāo)識(shí)，它和URL之間存在一種必然內(nèi)在聯(lián)系.

為了克服Heritrix中的Key值策略存在的效率低缺陷，本文提出了一種基于散列算法的Key賦值策略，即通過(guò)把所有URL進(jìn)入不同的隊(duì)列，用字符串長(zhǎng)短去轉(zhuǎn)化Key值，這樣不同長(zhǎng)度URL的Key值不同.

2 散列算法在移動(dòng)代理中實(shí)現(xiàn)

2.1 字符串散列函數(shù)

散列算法主要采用的是面對(duì)字符串的散列，通過(guò)散列算法將某一長(zhǎng)度的字符串轉(zhuǎn)換成散列值輸出，這樣的轉(zhuǎn)換是一種壓縮映射，可以大大減少URL在隊(duì)列中等待的時(shí)間.對(duì)字符串的散列是根據(jù)其長(zhǎng)度進(jìn)行轉(zhuǎn)換，不同的URL鏈接可能會(huì)由于長(zhǎng)度相同得到同一Key值.按照散列函數(shù)Key=F(X)，其中F()是單向的散列函數(shù)，X是任意長(zhǎng)度的字符串鏈接，以二進(jìn)制的形式存儲(chǔ)在計(jì)算機(jī)中，Key是經(jīng)過(guò)散列函數(shù)計(jì)算后得到的散列值［7］.散列過(guò)程如圖2所示.

圖2 散列過(guò)程示意圖Fig.2 Process of hashing

圖2直觀反映了對(duì)URL的散列過(guò)程，對(duì)于字符字節(jié)長(zhǎng)度相同的URL，經(jīng)過(guò)散列函數(shù)的計(jì)算之后得到相同的Key值，會(huì)出現(xiàn)在一個(gè)隊(duì)列中，不同長(zhǎng)度的Key值不一樣，形成一一對(duì)應(yīng)關(guān)系.這樣形成的數(shù)據(jù)訪問(wèn)結(jié)構(gòu)，通過(guò)散列之后，數(shù)據(jù)會(huì)被快速定位.考慮到既要滿(mǎn)足數(shù)據(jù)存儲(chǔ)的速度，又要減少散列函數(shù)本身會(huì)造成的數(shù)據(jù)沖突，需要一種具有負(fù)載均衡效果好的散列函數(shù).經(jīng)典的散列函數(shù)有:ELFHash函數(shù)、BKDRHash函數(shù)和 SDBMHash函數(shù).其中，BKDRHash帶有種子因子的散列函數(shù)，其執(zhí)行效率更高.因此，本文在改進(jìn)移動(dòng)代理隊(duì)列時(shí)，采用BKDRHash 函數(shù)對(duì)字符串進(jìn)行散列［8，9］.

2.2 散列過(guò)程

通過(guò)改寫(xiě)QueueAssignmentPolicy類(lèi)，并將其中的getClassKey()方法覆蓋，這個(gè)方法的需求參數(shù)是一個(gè)鏈接字符串對(duì)象，而字符串散列函數(shù)正好就是根據(jù)鏈接對(duì)象返回一個(gè)值.實(shí)現(xiàn)流程如圖3所示.

具體實(shí)現(xiàn)過(guò)程為:在移動(dòng)代理的鏈接制造工廠類(lèi)中，新建一個(gè)BKDRHashQueueAssignPolicy類(lèi)，這個(gè)類(lèi)繼承自QueueAssignmentPolicy類(lèi)，將改寫(xiě)的散列函數(shù)的參數(shù)返回值指向getClassKey的目的地址，之后在AbstractFrontier類(lèi)中將該策略的方法加入一條 BKDRHashQueueAssignPolicy.class.getName()方法;最后在Heritrix的屬性配置中設(shè)置，添加該條策略，使其生效.

圖3 散列函數(shù)實(shí)現(xiàn)流程Fig.3 Hash function processing flow

3 系統(tǒng)測(cè)試及評(píng)估

3.1 測(cè)試環(huán)境

本文是在JAVA平臺(tái)Eclipse 3.3上進(jìn)行設(shè)計(jì)開(kāi)發(fā)，軟件環(huán)境包括 Windows XP SP3，開(kāi)發(fā)工具Eclipse和Tomcat，性能比較開(kāi)發(fā)工具Jfree.

移動(dòng)代理啟動(dòng)之前，進(jìn)行移動(dòng)代理抓取參數(shù)的設(shè)置，在Heritrix抓取網(wǎng)頁(yè)時(shí)，通過(guò)這些屬性域控制移動(dòng)代理.在Jobs選項(xiàng)卡中，設(shè)置移動(dòng)代理抓取的種子集合，選取了國(guó)內(nèi)5個(gè)知名度和訪問(wèn)流量比較高的網(wǎng)站作為測(cè)試對(duì)象.在Seeds表中輸入http://www.sina.com.cn/、http://www.sohu.com/、http://www.163.com/、http://www.qq.com/ 、http://www.xinhuanet.com/五大門(mén)戶(hù)網(wǎng)站的地址.

對(duì)Max-Byte-Download設(shè)置為0，即對(duì)抓取速度不作限制，Max-Toe-Thread設(shè)置為1000，在 Version項(xiàng)中需要替換為Heritrix當(dāng)前的版本信息，其它的選項(xiàng)都保持默認(rèn).

3.2 實(shí)驗(yàn)結(jié)果與分析

在移動(dòng)代理完成任務(wù)之后，本文對(duì)Logs選項(xiàng)中數(shù)據(jù)進(jìn)行分析，Logs表中記錄了非常豐富的數(shù)據(jù)信息，crawler.log 記錄了時(shí)間、狀態(tài)碼等.prigress.log報(bào)表記錄每一條抓取的時(shí)間、存在的隊(duì)列、下載的速度、每秒鐘抓取的鏈接數(shù)，以及抓取的最大深度等等信息.在Totals欄中記錄了移動(dòng)代理當(dāng)前運(yùn)行的負(fù)載情況，并統(tǒng)計(jì)了隊(duì)列的長(zhǎng)度和線程數(shù)量等信息.

本文通過(guò)大量實(shí)驗(yàn)取平均值的方法，對(duì)改進(jìn)前后的移動(dòng)代理的性能進(jìn)行統(tǒng)計(jì)分析.在每次任務(wù)完成后，統(tǒng)計(jì)Logs表中的數(shù)據(jù)，然后清洗本次的抓取記錄，重新設(shè)置抓取參數(shù)，啟動(dòng)任務(wù)，反復(fù)進(jìn)行移動(dòng)代理速度的數(shù)據(jù)統(tǒng)計(jì)，去掉差異化較大的數(shù)據(jù)，將剩余數(shù)據(jù)計(jì)算得出平均值，在得到大量平均的數(shù)據(jù)之后對(duì)結(jié)果進(jìn)行對(duì)比分析.圖4表示的是改進(jìn)前后的移動(dòng)代理隊(duì)列在單位時(shí)間內(nèi)對(duì)URL的抓取速度.

圖4 抓取URL的速度比較Fig.4 Comparison of snatching URL rate

從圖4可以看出，在移動(dòng)代理對(duì)處理的初級(jí)階段，性能并沒(méi)有得到明顯的提升，在經(jīng)過(guò)一段URL進(jìn)隊(duì)之后，隊(duì)列中的URL越來(lái)越多，這個(gè)時(shí)間點(diǎn)之后，添加散列算法的移動(dòng)代理的性能開(kāi)始明顯提升.直到對(duì)隊(duì)列所有的數(shù)據(jù)處理完成之后，速度再次回到零，完成一次完整的抓取任務(wù).

本文又從移動(dòng)代理的活躍線程數(shù)方面進(jìn)行數(shù)據(jù)的對(duì)比分析，移動(dòng)代理Heritrix在默認(rèn)情況下，采取了HostPolicy策略，這樣的結(jié)果導(dǎo)致移動(dòng)代理在處理一個(gè)主站點(diǎn)下的URL時(shí)，只有單個(gè)線程工作，更多的線程都處于等待狀態(tài)，并不能充分發(fā)揮多線程處理器的優(yōu)勢(shì)，移動(dòng)代理抓取性能低下.圖5是對(duì)添加散列算法前后，移動(dòng)代理在實(shí)際運(yùn)行中活躍線程數(shù)的統(tǒng)計(jì).

圖5 活躍線程數(shù)比較Fig.5 Comparison of activity thread number

最后，在相同時(shí)間點(diǎn)對(duì)改進(jìn)前后下載速度進(jìn)行統(tǒng)計(jì)、分析，數(shù)據(jù)對(duì)比如圖6所示.

圖6 下載速度比較Fig.6 Comparison of download speed

從圖6可以看出，移動(dòng)代理在抓取任務(wù)的初始階段，處理速度并不明顯，這一階段是移動(dòng)代理在對(duì)種子集合的分析定位，找到相應(yīng)的資源站點(diǎn)，而在獲取相應(yīng)的資源之后，速度開(kāi)始上升，由于加入散列算法之后的移動(dòng)代理在處理URL方面更有優(yōu)勢(shì)，所以在整體的下載速度上更優(yōu).

4 結(jié)語(yǔ)

本文運(yùn)用散列算法對(duì)Heritrix的隊(duì)列處理機(jī)制進(jìn)行了改進(jìn)，通過(guò)大量實(shí)驗(yàn)分析可以看出，改進(jìn)后的移動(dòng)代理在抓取URL的平均速度、活躍線程數(shù)和整體的下載速度等方面都表現(xiàn)出了更好的性能，并適應(yīng)于同一域名的主站點(diǎn)和不同域名的主站點(diǎn).

［1］Sivasubramanian S，Pierre G，van Steen M，et al.Analysis of caching and replication strategies for Web applications［J］.IEEE Internet Computing，2007，11(1):60-66.

［2］Ye Dan，Wang Yiming.Distributed processing of mass cognitive information based on cognitive engine framework［C］//BMEI.International Conference on BioMedical Engineering and Informatics.Guangzhou:IEEE，2012:1446-1450.

［3］Belkin N J.Grand challenges for information retrieval［J］.SIGIR Forum，2008，42(1):47-54.

［4］張俊林.搜索引擎核心技術(shù)詳解［M］.北京:電子工業(yè)出版社，2012.

［5］Chen Jianxia，Wu Wei，Wang Chunzhi.A mobile phone information search engine based on Heritrix and Lucene［C］//ICCSE.The 7th International Conference on Computer Science ＆ Education.Melbourne:IEEE，2012:1602-1604.

［6］李 剛，宋 偉.征服Ajax+Lucene構(gòu)建搜索引擎［M］.北京:人民郵電出版社，2006.

［7］Shen Haiying，Li Ze.A scalable and mobility-resilient data search system forlarge-scale mobile wireless networks［J］.IEEE Transactionson Paralleland Distributed Systems，2013，24(6):1-11.

［8］邱 哲，符滔滔.開(kāi)發(fā)自己的搜索引擎——Lucene 2.0+Heritrix［M］.北京:人民郵電出版社，2010.

［9］Wu Guanlong，Kuo Yinshi.Scalable mobile video retrieval with sparse projection learning and Pseudo label mining［J］.IEEE Multimedia，2013，20(7):1-12.