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

1、 基于Redis的分布式搜索引擎研究 李彦辰艾庆忠王少非Summary：针对互联网网内信息搜索效率低下问题，设计了以Redis数据库以及Mapreduce思想为核心的分布式搜索引擎框架。为了应对互联网信息时效性强、更新快、难以被准确检索的特点，基于该框架设计了分布式爬虫、分布式索引建立、分布式链接分析算法。该框架明显提高了信息处理的效率，为分布式搜索引擎的搭建提供有效模板。经过测试，与以基于其它主流框架搭建分布式搜索引擎相比，基于Redis的分布式搜索引擎在爬虫爬取、索引生成、链接分析性能方面均有提升。Key：分布式搜索引擎；Redis数据库；Mapreduce思想DOIDOI：10.1190

2、7/rjdk.172561：TP393：A：16727800（2018）003020104英文SummaryAbstract：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 c

3、haracterized 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 i

4、nformation 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 dist

5、ributed search engine based on the Redis Data Base all have a obvious elevation.英文KeyKey Words：distributed search engine；redis data base；Mapreduce pattern0引言2015年2月发布的第35次中国互联网络发展状况统计报告显示，截至2014年12月，中国网站总数已达335万个，年增长4.6%；域名总数增至2 060万个，年増长11.7%；网页数量为1899亿个，年増长26.6%1；网页长（总字节数）达到8.468PB。如此巨大的互联网数据，使网络爬

6、虫对页面采集性能与效率的要求也越来越高，因此，对网页采集与链接关系的处理必须由多机并行完成。目前，国内外大型互联网公司与相关研究机构（如Google、百度）在此问题上已有一些较为成熟的解决方案，但是出于商业机密等因素考虑，这些方案一般只能为用户提供一种不可定制的搜索服务，且并未公开。本文通过研究搜索引擎基本体系机构及分布式的思路与技术，介绍了基于Redis的分布式搜索引擎框架，主要贡献有：总结了基于Mapreduce原理的分布式搜索引擎工作原理；设计了基于Redis的高效分布式搜索引擎框架；设计了基于该框架的分布式爬虫算法、索引算法、排序算法；实验证明了该框架的可行性。1搜索引擎相关性技术1.

7、1Mapreduce相关性研究Mapreduce（映射/规约）理念在于将计算分为Map、reduce两个过程，通过键位值对说明数据信息2。Mapreduce是采用并行方式计算大规模数据集的编程模型，也是一种分布式计算模型，其核心组成是Map函数与reduce函数3。Map过程先对客户端信息进行分割，将其分割为一种类型数据块，分别调用Map函数将初始数据转化为新的中间数据。Reduce过程调用Reduce函数对于中间数据按照规约整合，得到返回值。1.2分布式网络爬虫分布式网络爬虫整体设计重点在于爬虫如何进行通信。目前按通信方式不同，分布式网络爬虫可以分为主从模式、自治模式与混合模式3种45，其中

8、主从模式是搜索引擎常用模式。主从模式是指由一台主机作为控制节点负责对所有运行网络爬虫的主机进行管理，爬虫只需要从控制节点那里接收任务，并把新生成任务提交给控制节点。在整个过程中不必与其它爬虫通信，这种方式实现简单，利于管理。而控制节点则需要与所有爬虫进行通信，并用一个地址列表保存系统中所有爬虫信息。当系统中爬虫数量发生变化时，协调者需要更新地址列表里的数据，这一过程对于系统中的爬虫是透明的。1.3倒排索引倒排索引（Inverted index）常被稱为反向索引、置入档案或反向档案，是一种索引方法，被用来存储全文搜索中某个单词在一个文档或者一组文档中存储位置的映射6。它是文档检索系统中最常用的数

9、据结构，通过倒排索引，可以根据Key快速获取包含这个单词的文档列表。倒排索引主要由“单词词典”与“倒排文件”两个部分组成。其主要思想是处理器得到一个网页后，对该网页进行分析，对网页中所有去停用词后的词语进行分析，将其出现次数以及该网页的url一同存储入数据库，最终在数据库中得到一个关键字key。其出现在网页的url以及次数为value的数据库文件，从而实现对所抓取网页关键字的倒排索引构建。 2分布式搜索引擎设计框架本搜索引擎主要基于Redis，采用python编写的主从模式分布式搜索引擎，利用Redis内存高速存储读取信息的特点78，通过Redis进行各个主机进程之间的信息通信，达到mater

10、对slaves的命令传输控制。本搜索引擎采用主从模式的分布式结构。其中master命令主要以数据包的形式存储在Redis数据库中，slave通过对数据包的读取分析，完成大量的数据运算，降低mater的工作负担，然后将运算结果传递给master。master只需要对slaves传递的信息进行筛选与汇总，进行任务的再分配，充分利用各个机器的性能，达到分布式运算分析的目的，避免资源浪费，且构成一个准确高效的分布式整体5。数据在redis服务器中以队列的形式存储，master向队列尾部添加数据，slave从队列头部读取数据。通过这样的形式，一方面可以避免因资源竞争而导致分布式系统死锁，保证了程序的可行

11、性；另一方面确保了资源能在有限的时间内被读取到，避免资源浪费的情况发生。在redis数据库中时常存在这样3个队列：nrq= RedisQueue（）；srq= RedisQueue（）；trq=RedisQueue（）；其中，nrq是需要被处理的数据队列，sqr是已经被处理的数据队列，trq是存储共享的tag队列。Slave通过读取trq队列获得当前唯一的工作序号tag，nrq队列中的数据出队让salve获取，这样的工作流程避免了资源抢占的冲突；然后slave运算的结果会入队存储在srq中，再出队到master，让master进行数据汇总，完成分布式系统的工作。通过以上系统机制，Mapredu

12、ce的实现也成为可能。master对数据进行Map操作，将类型数据块存放到nrq队列中，并由slave读取；slave完成对的运算后，将结果存入srq队列中由master获取来实现。3分布式搜索引擎设计与实现3.1分布式爬虫设计本研究中，分布式爬虫采用materslave模式，通过mater对slaves的主机进行信息传递与资源分配。首先Slave需要爬取网页的源代码，并从中取出需要爬取的url加入爬取队列中；其次对爬取到的url进行去重，保证没有重复的爬取。通过对master和slaves的分工设定，可以很好地解决这个资源抢占的矛盾。分布式爬虫的工作流程如图1所示。首先，事先设定需要爬取的起

13、始网页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队列对数据进行

14、并行运算，但与爬虫的储存控制有所不同。由于数据库已经事先储存了网页信息，所以需要分析时爬虫直接从数据库读取数据到一个队列中，不再需要master对队列进行控制。在slave中，slave利用分词模块对网页进行分析，将网页中某词出现的网页url编号，该词在网页中出现的频度，打包成预定好的数据格式，存储到分析结果队列中，然后由master读取。再由master统一对数据进行存储操作以避免多主机对数据库操作时造成的数据冲突。slave的核心结构如图2所示。其中，salve首先通过队列srq获取需要进行分词操作的文本；再通过队列trq获取唯一tag保证不予其它slave发生冲突；然后利用jieba分词

15、模块对文本进行分词；最后将分词统计结果储存在数据块中，并将该数据块加入nrq队列中，由master自行获取。Master的核心结构如图3所示。其中，master直接从nrq队列获取由slave运算得到的数据块，将其汇总到了数据库。在本文研究中将Mapreduce思想应用到排序索引中，实现了分布式构建索引。3.3分布式排序算法运算设计链接分析算法在运算时需要占用大量内存与时间，通过分布式系统的设计可以加快运算速度，以提高计算分析效率。本文研究利用了Mapreduce的思想以及基于Redis的队列数据传输设计分布式排序算法。排序算法采用的是Pagerank，是通过计算网站间的相关度进行排序。如果一

16、个网站被外链接的次数越多，说明这个网站越重要。Pagerank算法首先需要生成网站出度网址的矩陣，然后生成设定每个网址的初始rank，最后通过迭代运算得到最终排名9。将Pagerank算法用到Mapreduce的思想中也能提高计算分析效率，分为两个步骤：（1）Map：将每次需要运算的数据打包成约定格式的数据。需要打包的数据有：PAGERANK每轮对应站点的运算结果；对应站点的url编号；对应站点的出度网页编号。然后将这些数据包发送给slave运算。（2）reduce：slave对收到的数据包进行解析，将Pagerank值与其对应的url编号返回，由master对运算结果进行汇总，完成该轮的Pa

17、gerank运算。 4分布式搜索引擎性能检验4.1分布式爬虫性能检验为了测试分布式爬虫的性能，在本研究中通过给定爬取起始网页以及爬取深度，测试不同数量的slave对于爬虫性能提升的额度。在开启1个slave的情况下，起始种子url为http：/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.1

18、18个/s；在开启4个slave的情况下，速度达到了17.079 个/s。由此可以看出网页的爬取速度与slave的数量成正比，但是，随着slave数量的增加，爬取速度增加的速率也会降低。当slave的数量增加到一定大小时，继续增加slave的数量将不会加快爬取速度。由于本研究使用2台主机导致爬去速度相对较慢，在实际应用中，slave分布在多个主机上，爬取速度会比实验中的更快。slave的上限数是由master主机性能决定的，master主机的性能越强大，slave数的上限也会越大。4.2分布式索引生成性能检验通过观察固定数量网页文本量，不同slave数量对于检验索引生成速度存在差异。如4.2中

19、所述，数据量为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分布式算法性能检验本研究以域名下的网站为分析源，分析Pagerank算法的性能。共有35 602个站点，同样使用不同数量的slave分析其分布式排序性能。在1个slave的

20、情况下使用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密集

21、型操作及Pagerank计算的运算密集型操作进行实验，实验主机数量均为3台。由此可以观察到两者的速度不相上下，证明了基于Redis的分布式系统在爬虫上的速度与基于Hadoop的分布式系统在爬虫上的速度是可以相提并论的。爬虫速度如图4所示。在Pageranke算法的计算上，运算结果如图5所示。可见在Pagerank算法上计算Redis分布式优于基于Hadoop集群分布式，Redis分布式在构建分布式搜索引擎上比Hadoop集群更有优势。5结语本文主要研究了基于Redis的分布式搜索引擎，讨论了在实际互联网环境中的实践效果以及可行性，包括基于Redis數据库的分布式搜索引擎的框架设计、主从模式分布

22、式爬虫的设计框架、排序索引的分布式生成、基于Mapreduce思想的分布式的Pagerank计算的实现框架，并实验证明了运用分布式搜索引擎后在抓取网页，建立搜索引擎索引，Pagerank链接分析算法运算在这几个方面的性能提升，证明了本系统在分布式搜索引擎系统上的应用优于Hadoop集群系统。未来基于该框架应当能够发展出更加完善的分布式搜索引擎。ReferenceReference：1BRIN S， PAGE L. Reprint of the anatomy of a largescale hypertextual web search engineJ. Computer networks， 2012，56（18）：38253833.2李明，唐轶.基于移动Agent的分布式Web搜索模型的设计与实现J.计算机应用与软件，2016，33（4）：1821.3DEAN J， GHEMAWAT S. MapReduce simplified data processing on large clustersJ. Communications of the ACM， 2008，51（1）：107113.4苏旋.分布式网络爬虫技术的