基于Redis的分布式搜索引擎研究

李彥辰　艾慶忠　王少非

摘要：

針對互聯網網內信息搜索效率低下問題，設計了以Redis數據庫以及Mapreduce思想為核心的分布式搜索引擎框架。為了應對互聯網信息時效性強、更新快、難以被準確檢索的特點，基于該框架設計了分布式爬蟲、分布式索引建立、分布式鏈接分析算法。該框架明顯提高了信息處理的效率，為分布式搜索引擎的搭建提供有效模板。經過測試，與以基于其它主流框架搭建分布式搜索引擎相比，基于Redis的分布式搜索引擎在爬蟲爬取、索引生成、鏈接分析性能方面均有提升。

關鍵詞：

分布式搜索引擎；Redis數據庫；Mapreduce思想

DOIDOI：10.11907/rjdk.172561

中圖分類號：TP393

文獻標識碼：A文章編號文章編號：16727800（2018）003020104

英文摘要Abstract：To tackle the inefficiency of searching information through the Internet， a distributed search engine based on the Redis Data Base and mapreduce pattern was devised. To better adapt to the situation of the Internet at present， which is characterized by timesensitive，fastupdate and searching timeconsuming features， three techniques including distributed crawler， distributed index construction and distributed link analysis algorithm is applied within our distributed search engine. The framework greatly elevate the efficiency of the information processing and provide an effective template for the construction of the distributed search engine. After testing， compared with the search engines based on the other prevalent frameworks， the performances of three aspects including crawling， index generation and link analysis of the distributed search engine based on the Redis Data Base all have a obvious elevation.

英文關鍵詞Key Words：distributed search engine；redis data base；Mapreduce pattern

0引言

2015年2月發布的《第35次中國互聯網絡發展狀況統計報告》顯示，截至2014年12月，中國網站總數已達335萬個，年增長4.6%；域名總數增至2 060萬個，年増長11.7%；網頁數量為1899億個，年増長26.6%[1]；網頁長（總字節數）達到8.468PB。如此巨大的互聯網數據，使網絡爬蟲對頁面采集性能與效率的要求也越來越高，因此，對網頁采集與鏈接關系的處理必須由多機并行完成。目前，國內外大型互聯網公司與相關研究機構（如Google、百度）在此問題上已有一些較為成熟的解決方案，但是出于商業機密等因素考慮，這些方案一般只能為用戶提供一種不可定制的搜索服務，且并未公開。

本文通過研究搜索引擎基本體系機構及分布式的思路與技術，介紹了基于Redis的分布式搜索引擎框架，主要貢獻有：①總結了基于Mapreduce原理的分布式搜索引擎工作原理；②設計了基于Redis的高效分布式搜索引擎框架；③設計了基于該框架的分布式爬蟲算法、索引算法、排序算法；④實驗證明了該框架的可行性。

1搜索引擎相關性技術

1.1Mapreduce相關性研究

Mapreduce（映射/規約）理念在于將計算分為Map、reduce兩個過程，通過鍵位值對說明數據信息[2]。Mapreduce是采用并行方式計算大規模數據集的編程模型，也是一種分布式計算模型，其核心組成是Map函數與reduce函數[3]。Map過程先對客戶端信息進行分割，將其分割為一種類型數據塊，分別調用Map函數將初始數據轉化為新的中間數據。Reduce過程調用Reduce函數對于中間數據按照規約整合，得到返回值。

1.2分布式網絡爬蟲

分布式網絡爬蟲整體設計重點在于爬蟲如何進行通信。目前按通信方式不同，分布式網絡爬蟲可以分為主從模式、自治模式與混合模式3種[45]，其中主從模式是搜索引擎常用模式。主從模式是指由一臺主機作為控制節點負責對所有運行網絡爬蟲的主機進行管理，爬蟲只需要從控制節點那里接收任務，并把新生成任務提交給控制節點。在整個過程中不必與其它爬蟲通信，這種方式實現簡單，利于管理。而控制節點則需要與所有爬蟲進行通信，并用一個地址列表保存系統中所有爬蟲信息。當系統中爬蟲數量發生變化時，協調者需要更新地址列表里的數據，這一過程對于系統中的爬蟲是透明的。

1.3倒排索引

倒排索引（Inverted index）常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲全文搜索中某個單詞在一個文檔或者一組文檔中存儲位置的映射[6]。它是文檔檢索系統中最常用的數據結構，通過倒排索引，可以根據關鍵詞快速獲取包含這個單詞的文檔列表。倒排索引主要由“單詞詞典”與“倒排文件”兩個部分組成。其主要思想是處理器得到一個網頁后，對該網頁進行分析，對網頁中所有去停用詞后的詞語進行分析，將其出現次數以及該網頁的url一同存儲入數據庫，最終在數據庫中得到一個關鍵字key。其出現在網頁的url以及次數為value的數據庫文件，從而實現對所抓取網頁關鍵字的倒排索引構建。

2分布式搜索引擎設計框架

本搜索引擎主要基于Redis，采用python編寫的主從模式分布式搜索引擎，利用Redis內存高速存儲讀取信息的特點[78]，通過Redis進行各個主機進程之間的信息通信，達到mater對slaves的命令傳輸控制。

本搜索引擎采用主從模式的分布式結構。其中master命令主要以數據包的形式存儲在Redis數據庫中，slave通過對數據包的讀取分析，完成大量的數據運算，降低mater的工作負擔，然后將運算結果傳遞給master。master只需要對slaves傳遞的信息進行篩選與匯總，進行任務的再分配，充分利用各個機器的性能，達到分布式運算分析的目的，避免資源浪費，且構成一個準確高效的分布式整體[5]。

數據在redis服務器中以隊列的形式存儲，master向隊列尾部添加數據，slave從隊列頭部讀取數據。通過這樣的形式，一方面可以避免因資源競爭而導致分布式系統死鎖，保證了程序的可行性；另一方面確保了資源能在有限的時間內被讀取到，避免資源浪費的情況發生。在redis數據庫中時常存在這樣3個隊列：

nrq= RedisQueue（）；

srq= RedisQueue（）；

trq=RedisQueue（）；

其中，nrq是需要被處理的數據隊列，sqr是已經被處理的數據隊列，trq是存儲共享的tag隊列。Slave通過讀取trq隊列獲得當前唯一的工作序號tag，nrq隊列中的數據出隊讓salve獲取，這樣的工作流程避免了資源搶占的沖突；然后slave運算的結果會入隊存儲在srq中，再出隊到master，讓master進行數據匯總，完成分布式系統的工作。通過以上系統機制，Mapreduce的實現也成為可能。master對數據進行Map操作，將類型數據塊存放到nrq隊列中，并由slave讀取；slave完成對的運算后，將結果存入srq隊列中由master獲取來實現。

3分布式搜索引擎設計與實現

3.1分布式爬蟲設計

本研究中，分布式爬蟲采用materslave模式，通過mater對slaves的主機進行信息傳遞與資源分配。首先Slave需要爬取網頁的源代碼，并從中取出需要爬取的url加入爬取隊列中；其次對爬取到的url進行去重，保證沒有重復的爬取。通過對master和slaves的分工設定，可以很好地解決這個資源搶占的矛盾。

分布式爬蟲的工作流程如圖1所示。首先，事先設定需要爬取的起始網頁url；然后將起始url寫入隊列srq中，供slave讀取分析。slave的工作流程如下：

（1）從srq隊列中爬取到url。

（2）對url進行訪問，如果url的服務器能夠訪問，下載網頁文本，并將網頁文本存儲到數據庫中。

（3）對網頁文本內容進行分析，抓取其中格式正確并且符合預先設定的抓取要求的url，將這些url寫入nrq隊列中。

master工作流程的步驟有：①nrq隊列中取出一個url；②對url進行去重（使用Bloom filter）；③對url格式進行判斷；④如果②、③的判斷都通過，則將該url寫入srq隊列中。

3.2分布式索引構建

本研究以分布式方式構建索引，其思路是利用Redis隊列對數據進行并行運算，但與爬蟲的儲存控制有所不同。

由于數據庫已經事先儲存了網頁信息，所以需要分析時爬蟲直接從數據庫讀取數據到一個隊列中，不再需要master對隊列進行控制。在slave中，slave利用分詞模塊對網頁進行分析，將網頁中某詞出現的網頁url編號，該詞在網頁中出現的頻度，打包成預定好的數據格式，存儲到分析結果隊列中，然后由master讀取。再由master統一對數據進行存儲操作以避免多主機對數據庫操作時造成的數據沖突。slave的核心結構如圖2所示。

其中，salve首先通過隊列srq獲取需要進行分詞操作的文本；再通過隊列trq獲取唯一tag保證不予其它slave發生沖突；然后利用jieba分詞模塊對文本進行分詞；最后將分詞統計結果儲存在數據塊中，并將該數據塊加入nrq隊列中，由master自行獲取。

Master的核心結構如圖3所示。

其中，master直接從nrq隊列獲取由slave運算得到的數據塊，將其匯總到了數據庫。在本文研究中將Mapreduce思想應用到排序索引中，實現了分布式構建索引。

3.3分布式排序算法運算設計

鏈接分析算法在運算時需要占用大量內存與時間，通過分布式系統的設計可以加快運算速度，以提高計算分析效率。本文研究利用了Mapreduce的思想以及基于Redis的隊列數據傳輸設計分布式排序算法。

排序算法采用的是Pagerank，是通過計算網站間的相關度進行排序。如果一個網站被外鏈接的次數越多，說明這個網站越重要。Pagerank算法首先需要生成網站出度網址的矩陣，然后生成設定每個網址的初始rank，最后通過迭代運算得到最終排名[9]。將Pagerank算法用到Mapreduce的思想中也能提高計算分析效率，分為兩個步驟：

（1）Map：將每次需要運算的數據打包成約定格式的數據。需要打包的數據有：PAGERANK每輪對應站點的運算結果；對應站點的url編號；對應站點的出度網頁編號。然后將這些數據包發送給slave運算。

（2）reduce：slave對收到的數據包進行解析，將Pagerank值與其對應的url編號返回，由master對運算結果進行匯總，完成該輪的Pagerank運算。

4分布式搜索引擎性能檢驗

4.1分布式爬蟲性能檢驗

為了測試分布式爬蟲的性能，在本研究中通過給定爬取起始網頁以及爬取深度，測試不同數量的slave對于爬蟲性能提升的額度。

在開啟1個slave的情況下，起始種子url為http：//zsb.jlu.edu.cn/list/45.html，數據在MYSQL數據庫中存儲。其中，網頁id為INT型，占4字節；網頁url為VARCHAR類型；網頁內容為LONGTEXT類型。

對于深度為2的爬取設定，爬取708個網頁，占25 600KB，平均速度為5.385個/s；在開啟2個slave的情況下，速度達到了10.992 個/s；在開啟3個slave的情況下，速度達到了14.118個/s；在開啟4個slave的情況下，速度達到了17.079 個/s。由此可以看出網頁的爬取速度與slave的數量成正比，但是，隨著slave數量的增加，爬取速度增加的速率也會降低。當slave的數量增加到一定大小時，繼續增加slave的數量將不會加快爬取速度。由于本研究使用2臺主機導致爬去速度相對較慢，在實際應用中，slave分布在多個主機上，爬取速度會比實驗中的更快。slave的上限數是由master主機性能決定的，master主機的性能越強大，slave數的上限也會越大。

4.2分布式索引生成性能檢驗

通過觀察固定數量網頁文本量，不同slave數量對于檢驗索引生成速度存在差異。如4.2中所述，數據量為25 600KB，對于不同數量的slave分析文本速度進行統計。在1個slave的情況下，速度為4.262個/s；2個slave的情況下速度為6.661個/s；3個slave的情況下速度為7.775個/s；4個slave的情況下速度為8.514個/s。由此可以看出對于索引生成的速度圖線平均斜率比爬蟲的要小，主要原理是此算法對master的運算負擔比較大，使用性能較強大的主機可以改善該問題。

4.3PAGERANK分布式算法性能檢驗

本研究以jlu.edu域名下的網站為分析源，分析Pagerank算法的性能。共有35 602個站點，同樣使用不同數量的slave分析其分布式排序性能。在1個slave的情況下使用963.955s計算；在2個slave的情況下使用754.473s；在3個slave的情況下使用648.617s；在4個slave的情況下使用584.876s。由此可以看出隨著slave數量的增加，在網頁總數一定的情況下，Pagerank的計算速度有較為明顯的提高，說明本研究的分布式系統能夠有效加快排序算法的運算速度。

4.4兩種引擎效果對比

Apache Nutch是以Hadoop為基礎實現的分布式系統，具有以Hadoop為基礎編寫的分布式搜索引擎的代表性[11]。因此通過與基于Apache Nutch的分布式搜索引擎進行對比，分析本研究的框架優勢。

在該實驗中，分別對網頁爬蟲爬取的IO密集型操作及Pagerank計算的運算密集型操作進行實驗，實驗主機數量均為3臺。

由此可以觀察到兩者的速度不相上下，證明了基于Redis的分布式系統在爬蟲上的速度與基于Hadoop的分布式系統在爬蟲上的速度是可以相提并論的。爬蟲速度如圖4所示。

在Pageranke算法的計算上，運算結果如圖5所示。

可見在Pagerank算法上計算Redis分布式優于基于Hadoop集群分布式，Redis分布式在構建分布式搜索引擎上比Hadoop集群更有優勢。

5結語

本文主要研究了基于Redis的分布式搜索引擎，討論了在實際互聯網環境中的實踐效果以及可行性，包括基于Redis數據庫的分布式搜索引擎的框架設計、主從模式分布式爬蟲的設計框架、排序索引的分布式生成、基于Mapreduce思想的分布式的Pagerank計算的實現框架，并實驗證明了運用分布式搜索引擎后在抓取網頁，建立搜索引擎索引，Pagerank鏈接分析算法運算在這幾個方面的性能提升，證明了本系統在分布式搜索引擎系統上的應用優于Hadoop集群系統。未來基于該框架應當能夠發展出更加完善的分布式搜索引擎。

參考文獻參考文獻：

[1]BRIN S， PAGE L. Reprint of the anatomy of a largescale hypertextual web search engine[J]. Computer networks， 2012，56（18）：38253833.

[2]李明，唐軼.基于移動Agent的分布式Web搜索模型的設計與實現[J].計算機應用與軟件，2016，33（4）：1821.

[3]DEAN J， GHEMAWAT S. MapReduce simplified data processing on large clusters[J]. Communications of the ACM， 2008，51（1）：107113.

[4]蘇旋.分布式網絡爬蟲技術的研究與實現[D].哈爾濱：哈爾濱工業大學，2006.

[5]詹恒飛，楊岳湘，方宏.Nutch分布式網絡爬蟲研究與優化[J].計算機科學與探索，2011，5（1）：6874.

[6]周海松，劉建明，李龍.基于Lucene的垂直搜索引擎研究與實現[J].桂林電子科技大學學報，2014，34（3）：226229.

[5]史寶明，賀元香，吳崇正.主題搜索引擎中爬蟲搜索策略的研究[J].計算機工程與應用，2014，50（2）：116119.

[6]林子皓.主題爬蟲的設計與實現[J].計算機技術與發展，2014（8）：99102.

[7]成功，李小正，趙全軍.一種網絡爬蟲系統中URL去重方法的研究[J].中國新技術新產品，2014（12）：2323.

[8]吳寶貴，丁振國.基于Map/Reduce的分布式搜索引擎研究[J].數據分析與知識發現，2007，2（8）：5255.

[9]PAGE L， BRIN S， MOTWANI R， et al. The pagerank citation ranking： bringing order to the web[J]. Stanford Digital Libraries Working Paper， 1998，9（1）：114.

[10]HAVELIWALA T H. Topicsensitive pagerank[C]Proceedings of the 11th International Conference on World Wide Web. ACM， 2002.

[11]BORTHAKUR D. The hadoop distributed file system： architecture and design[J]. Hadoop Project Website， 2007，11： 21.

責任編輯（責任編輯：劉亭亭）