1、主要研究工作在于对传统搜索引擎的功能模块加以改进，对爬行、索引、搜索过程中的步骤进行详细分析，将非顺序执行的步骤进一步分解为两部分：数据计算和数据合并。同时，应用 Map/Reduce 编程模型思想，把数据计算任务封装到 Map 函数中，把数据合并任务封装到 Reduce 函数中。经过以上改进的搜索引擎系统可以部署在廉价PC构成的Hadoop分布式环境中，并具有较高的响应速度、可靠性和扩展性。这与分布式搜索引擎中的技术需求极为符合，因此本文使用 Hadoop 作为系统分布式计算平台。此外，系太原理工大学硕士学位论文 II 统使用了基于倒排文档的全文检索技术，构建了以关键词为单位的倒排索引模块，
2、同时结合 TF-IDF 和 PageRank 算法，改进了网页评分策略，优化了搜索结果。最后，详细分析了在应用 Map/Reduce 编程模型实现系统模块过程中遇到的问题，及其解决方案。构建了一个 4 节点的小型分布式搜索引擎系统，通过对网络资源的爬行、索引和检索，以及对系统进行可靠性和扩展性测试，获得实验数据。在分析实验数据的基础上，验证了所提出的基于 Hadoop的分布式搜索引擎的合理性。关键词：M a p/R e d u c e，H a d o o p，分布式计算，搜索引擎 太原理工大学硕士学位论文 III THE RESEARCH AND IMPLEMENTATION OF DISTR
3、IBUTED SEARCH ENGINE BASED ON HADOOP ABSTRACT Distributed Search Engine is a brand new information retrieval system which is consisted of distributed computing technology and full-text retrieval technology.It has changed the way of achieving informations for people and has made it more effectively.N
4、ow it has been deep into every aspects of the Internet,and it is known as the first Step of navigation.At present,most of the search engine system are structured similarly-centralized structure,which means all of system s modules are deployed on one server,and it also result in the server must be of
5、 high performance，meanwhile,the system still have poor stability and bad scalability.In order to deal with these disadvantanges,people have to purchase very large and expensive servers to satisfy the system requirements,however,not everyone have the ability to afford such high cost.In addition,a pri
6、mitive string matching mode was adopted to gain the results in many traditional information retrieval systems.Although this method is simple,the search efficiency became very low when data volume is huge,and customers could not retrieve useful informations in time.The two disadvantages mentioned abo
7、ve was a big challenge to the promotion of search engine.In order to deal with this challenge,the technology of distributed computing and inverted document full-text retrieval were introduced into the search engine system.In this paper,it summaried the advantages and disadvantages based on an analys
8、is of several distributed search engine systems.In order to deal with the 太原理工大学硕士学位论文 IV existing drawbacks,it proposed a distributed search engine based on Hadoop.The main tasks of this paper are to improve the traditional search engine function modules,analyze the steps on the crawling,indexing,s
9、earching,in the process,and further decomposed these process that can be excuted disorderly into two parts:data computing and data combining.Then,packaged the algrithm of data computing into Map function,and the algrithm of data combining into Reduce function by using Map/Reduce programming thinking
10、s.After the implementation of these technologies,it improved search engine system could be deployed on a Hadoop distributed environment which was structured by some low-cost PCs,so this system had high response speed,reliability and scalability.Because of the technology closed to the distributed sea
11、rch engine s needs.In this paper,it used Hadoop distributed computing platform as a system.Besides,this paper constructed with keywords for inverted indexing module,by using the inverted document based full-text retrieval technology.And it combined with TF-IDF and PageRank algorithm to improve the p
12、age score strategy and optimize the search results.Finally,a detailed analysis of how to use Map/Reduce programming model to achieve system module has proposed as well as the difficulties in the implementation process,a nd it built a small distributed search engine system with four nodes,the experim
13、ental data was achieved by means of the crawling,indexing and retrieving through Internet,and tested system reliability and scalability.In the analysis of this experimental data,the rationality of the distributed search engine based on Hadoop has been validated.KEY WORDS:Map/Reduce,Hadoop,Distribute
14、d compute,Search Engine 太原理工大学硕士学位论文 1 第一章 绪论 1.1 课题研究背景 随着互联网的飞速发展，大量网站如同雨后春笋般大批涌现，截止 2009 年，全球互联网新增网站达 4600 万，总计达 2.315 亿。全球数字化信息总量也呈现出快速增长势头。随着社交网站不断涌现、上网手机层出不穷，目前全世界的数字内容约为 4870 亿吉比特（GB），从如此海量的数据中检索出需要的信息就必须使用搜索引擎了，根据权威调查机构正望咨询 09 年搜索引擎用户调查报告显示，搜索引擎的渗透率持续提高，有 91%的网民每个月至少使用一次搜索引擎，此数字比上一年增加了 4 个百分
15、点，搜索引擎是许多网民上网的第一站1。毫无疑问，搜索引擎已经成为互联网上人们获取信息的最重要手段。目前，搜索引擎研究一直都处于持续升温状态，几大通用搜索引擎，如 Google、Baidu、Yahoo等已经牢牢的控制了搜索市场，而软件巨头微软也于 2009 年 6 月推出了全新的搜索引擎 Bing，加入了搜索行列。同时，搜索引擎作为基础软件在网站内部取得了广泛应用，不仅大型门户网站如美国在线、雅虎、亚马逊等等每一个著名网站的首页都在显著位置放置了搜索框，就连迪斯尼、麦当劳、美孚石油这些传统企业也都无一例外地在它们的首页上放置了搜索框或搜索功能的链接，美国 500 强中使用搜索引擎的网站几乎达到
16、100%。总的来看，国外主流的搜索引擎技术已比较成熟，无论从结果、性能还是稳定性来看，都能提供令人满意的结果，并且已经在人们的日常信息获取中发挥作用。反观国内，目前对搜索引擎潜在价值的开发明显不够，除了网易、新浪、搜狐等少数门户网站使用了搜索引擎外，大多数网站使用的还是基于数据库关键字匹配的简单信息检索系统。这种检索方式，效率低，检索结果准确性也不尽如人意。那些拥有搜索引擎的门户网站，其搜索引擎系统都采用了同样的体系结构集中式结构，即运行各子系统的服务器在物理上集中分布。这也导致了系统对单台服务器性能要求高，易出现故障，可扩展性差等缺点。于是，为了使系统得到最佳的性能、最好的容错性和最容易的扩
17、展性，分布式搜索引擎应运而生了。分布式搜索引擎是由若干台计算机组成的系统，每台计算机都具有独太原理工大学硕士学位论文 2 立的物理资源，系统内的每个子系统都可以利用这些资源高度自治而相互合作地工作，共同完成爬行、索引和搜索任务。同时，系统资源还具有冗余性，保证在一台或几台计算机出现故障后，系统不会出错和瘫痪。分布式搜索引擎系统解决了现有系统对单台服务器性能要求高，易出现故障，可扩展性差等缺点。因此，研究这一课题是很有意义的。1.2 搜索引擎的发展 最早现代意义上的搜索引擎出现于1994年7月。当时Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中，创建了 Ly
18、cos，除了相关性排序外，Lycos 还提供了前缀匹配和字符相近限制。1994 年 7 月 20 日，数据量为 54,000 的 Lycos 正式发布。同年4 月，斯坦福大学的两名博士生，David Filo 和美籍华人杨致远（Gerry Yang）共同创办了超级目录索引 Yahoo，随着访问量和收录链接数的增长，Yahoo 目录开始支持简单的数据库搜索。1998年10月，由 Larry Page 和Sergey Brin两人搭档创办的搜索引擎Google正式推出，以其独特的网页排序、动态摘要、网页快照、每日更新等特点，改写了现代搜索引擎的历史，并成功地使搜索引擎的概念深入人心。从此搜索引擎进
19、入了高速发展时期。经过多年的发展，搜索引擎的子系统划分已经很明确，一般包括 3 个部分2：1.网络爬行器（Crawler）：爬行器从一个或数个种子超链接出发，发现新的网页并保存这些网页的快照，然后分析它们，从中提取网页链接，扩充链接列表库以供爬行器下一轮爬行使用。爬行器循环执行这一流程从网络上抓取所需网页数据。2.索引器（Indexer）：索引器的功能是对网页内容进行分词，建立倒排索引文档。其中分词功能是非常重要的一环，众所周知，英文是以词为单位的，词和词之间是靠空格或标点隔开，而中文是以字为单位，句子中部分字只有连起来才能描述一个意思。中文分词的好坏直接关系到搜索的准确性，而索引文档的存储结
20、构又关系到搜索的响应速度。3.查询器（Searcher）：查询器的功能是向用户提供查询界面，在收到用户的查询请求时，解析查询条件，检索倒排索引文档，并根据一定的评分策略，对匹配的结果集进行排序，并返回检索结果。目前，除了那些大名鼎鼎的商业搜索引擎以外，大部分的搜索引擎都将这三种子系统集中部署，即集中式结构。随着索引信息量的快速增长和用户搜索量上升，系统的处太原理工大学硕士学位论文 3 理性能、容错性、扩展性，以及灾难恢复性差的缺点日趋明显，严重影响了搜索引擎的应用。因此，在系统结构方面，下一步的发展方向是分布式结构。1.3 分布式搜索引擎研究现状 为了解决集中式结构存在的诸多缺点，人们很早就开
21、始了搜索引擎分布式结构的研究。近几年已经开发出几种应用分布式信息检索的系统3，主要有：（1）ROADS 主题信息检索系统，它由 Loughborough 技术大学的计算机科学系、Britol大学的 ILRT 和 Bath大学的 UKOLN 联合开发，应用了 WHOIS+协议。WHOIS+是一种简单的分布式信息查找协议，被用于连接许多基本级服务器和索引服务器，以形成统一的目录服务器，提供灵活的方式实现跨平台查询。然而，WHOIS+并没有提供许多查询功能，虽然它易于操作，但是为了实现查询中的自动推荐，必须在客户程序上进行修改。每一个希望参加到同一目录服务之中的基本级服务器和索引服务器必须生成一个“
22、前期知识”，以说明它所包括的款目，因此，其扩展能力也受到一定的限制。目前，其应用范围一般局限于数字图书馆领域。（2）Issac 项目由美国国家自然科学基金赞助，由 University of Wisconsin-Madison的计算机科学系承担，主要目的是帮助高等教育团体实现 Internet 上的资源发现。其目标是链接地理上各自分布的 metadata 数据集，使之成为一个整体上统一的数据资源库，通过利用 LDAP（Lightweight Directory Access Protocol）以及 CIP（Common Indexing Protocol）协议，来实现分布式查询提交，数据返回，
23、交换索引信息的结构4。Issac 搜索引擎在分布式搜索方面具有很大进步，但是，它仍有两个致命缺陷：在查询的相关性方面，有巨大的障碍，系统常常给出许多不相关的检索内容，在使用的时候，用户将很多的精力放在内容的判断上。（3）基于 P2P 的分布式搜索引擎。P2P 采用全分布式网络体系结构，它也称为分布式对等网络5。不再使用中央服务器，消除了中央服务器带来的稳定性问题。没有中央控制点，不会因为一点故障导致全部瘫痪，是真正的分布式网络。用户 PC 性能及其与网络连接方式决定网络弹性和性能。这种模式具有自组织行为，降低了拥有者的成本，提供可扩展性。特别适合在自组织网上的应用，如即时通信等。但是这种结构使
24、得每一个节点都必须同时拥有统一的节点分布图，系统的扩展性不好，同时协调节点之间通信也成为一个挑战。太原理工大学硕士学位论文 4 以上三个系统代表了人们在分布式搜索引擎研究领域里的不懈努力，但也都有一定些弊端。未来的搜索引擎系统大都需要更强的计算力，更高的稳定性，更好的扩展性，同时也需要一定的策略将优化搜索结果，满足用户快速获取准确信息的需求6,7,8。本文所讨论的基于 Hadoop 的分布式搜索引擎系统顺应了这种发展趋势，利用 Map/Reduce编程模式9设计了系统模块，部署在一个分布式平台上，充分利用已有的资源，组织更为庞大的计算网络，满足搜索引擎对计算能力、稳定性和扩展性的需求，并综合利
25、用TF-IDF 和 PageRank 评分策略优化搜索结果。1.4 本文的研究内容及论文章节安排 本文的目标是分析分布式计算技术的优势，以及搜索引擎主要使用的技术，结合分布式计算和倒排文档全文检索技术，设计与实现一个分布式搜索引擎。其内容和结构安排如下：第一章简要地阐述了课题研究背景，搜索引擎的发展历史，分布式搜索引擎研究现状方面的内容，分析现有系统的不足。第二章从理论角度出发，分析了 Map/Reduce 编程模型，倒排文档全文检索机制，中文分词三方面的原理，以及它们的使用范围。并介绍了分布式搜索引擎系统使用的相关技术，包括 Hadoop 分布式计算平台，Lucene 全文检索框架，以及相关
26、辅助工具。为后面的研究工作奠定了基础。第三章阐述了分布式搜索引擎系统的设计思想。并依据业务功能，将系统划分为三大业务子系统：爬行子系统、索引子系统和查询子系统。对每个子系统的工作流程进行了详细分析，利用 Map/Reduce 模型改进这三个子系统，使它们具有分布式处理的能力。第四章深入子系统内部，从功能方面分析了子系统设计过程中包含的主要模块，以及模块内部各个类之间的关系。运用成熟的开源工具实现了系统，并讨论了实现过程中的难点，及其解决方法。第五章是实验平台搭建和实验数据分析。本章利用 4 台计算机建立了一个小型的分布式处理环境，在此基础上部署了分布式搜索引擎系统。经过多次实验，得出了实验结果
27、，并对不同环境情况下取得数据进行分析，最终对系统做出总体评价。第六章是总结与展望。对论文工作进行总结，并提出今后要做的工作和研究方向。太原理工大学硕士学位论文 5 第二章 分布式搜索引擎相关技术分析 分布式搜索引擎是以分布式计算技术和倒排文档全文索引技术相结合构建的庞大而复杂的系统，因此有必要对这两种技术进行详细分析。此外，在设计与实现过程中，还使用了许多新兴的技术，在这一章里也做了简单的介绍。2.1 分布式计算技术 2.1.1 Map/Reduce 编程模型 在程序设计中，一项工作往往可以被拆分成为多个任务，任务之间的关系可以分为两种：一种是任务之间有相互的依赖，先后顺序不能够颠倒，这类任务
28、是无法并行处理的；另一种是不相关的任务，可以并行执行。绝大部分大型计算工作都是属于后者。只不过，输入的数据通常是非常巨大的，并且为了能在合理时间内执行完毕，其计算任务必须分布到上百个或者上千个计算机上去执行。如何并发计算，如何分布数据，如何处理失败等等相关问题合并在一起就会导致原本简单的计算掩埋在为了解决这些问题而引入的很复杂的代码中9。Map/Reduce 编程模型正是为了解决这些问题而发明的。Map/Reduce10是 Google 实验室于 2004 年提出的一种新的分布式程序设计模型，用于在集群上对海量数据进行并行处理。在 Google 内部，Map/Reduced 的应用非常广泛包括
29、：分布 grep，分布排序，web 连接图反转，每台机器的词矢量，web 访问日志分析，反向索引构建，文档聚类，机器学习，基于统计的机器翻译等。值得注意的是，Map/Reduce实现以后，它被用来重新生成 Google 的整个索引，以取代老的 ad hoc 程序去更新索引，足以证明其具有非常高的性能。Map/Reduce 的名字源于这个模型中的两项核心操作：Map 和 Reduce，实际处理的都是大量像对这样的简单数据类型。在模型中首先对输入的数据进行分割，将分割后的数据分配给 Map 函数，而 Map 把分配到的数据（一般为一组对）映射为另外的一组型中间数据，其映射的规则由一个函数指定；Re
30、duce是对 Map 输出的型中间数据进行归约并输出最终结果，这个归约的规则也是由一个函数指定。这两项操作的规则是可以由程序设计人员的指定，正是这一点带给了 Map/Reduce 模型巨大的灵活性11。执行流程如图 2-1 所示。太原理工大学硕士学位论文 6 图 2-1 M a p/R e d u c e 模型执行流程图 Figure 2-1 Map/Reduce Module Flow Chart 使用这样的函数形式实现的程序可以自动分布到一个由普通机器组成的大型集群上并发执行。系统会解决输入数据的分布细节，跨越机器集群的程序执行调度，处理机器的失效，并且管理机器之间的通讯请求。这样的模式允
31、许程序员可以不需要有什么并发处理或者分布式系统的经验，就可以充分利用分布式系统的资源12,13。2.1.2 Hadoop 平台简介 Hadoop 是一个基于 Map/Reduce的相当成功的分布式计算平台，Hadoop 由 Apache Software Foundation 组织于 2005 年秋天正式引入，目前的最新版本是 0.19.1。Map/Reduce 是 Google 的一项重要技术，是一种简化并行计算的编程模型，它让那些没有多少并行计算经验的开发人员也可以开发并行应用。Map/Recuce 可以将被划分成多个小的 Block 的海量检索数据以分布式的方法局部计算，并应用 Map 将他们映射到一个提供 Reduce 的中心上，从而达到快速处理海量数据检索的目的。分布式文件系统 HDFS（Hadoop Distributed File System）是 Hadoop 的另一重要功能。HDFS 是受 Google 文件系统的启发，建立在大型集群上可靠存储大数据集的
