分布式搜索引擎的模型综述

摘 要 本文综述了分布式搜索引擎的模型、结构和查询方法，并讨论了搜索引擎的评价指标。从搜索引擎的离线处理和在线处理讨论了搜索引擎的基本模块，在线查询过程速度决定了搜索引擎性能的关键因素；从分布式搜索引擎的模型上划分，搜索引擎包含四个主要子系统：网页爬虫系统，索引构建系统、检索系统和日志分析系统；倒排索引结构是以词典（dictionary）和倒排文件（inverted file）组成，分为文档编号递增排序和词频（或影响力）得分递减排序。然后讨论了当前搜索引擎典型的三类查询处理策略，并比较各自适应的条件。最后，综述评价搜索引擎的两个重要指标： 查询效率和查询结果的质量，并列举定量评价公式。

关键词 分布式索引； 搜索引擎；倒排索引；查询处理

中图法分类号 TP393 文献标识码 A

Review on Distributed Search Engine Model

QIAN Libing， JI Zhenzhou

1（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract This paper reviews the model，structure and search method for distributed search engine， and then discusses the evaluation of search engines. From the offline processing and online processing， the basic modules of search engine are discussed. The essential factor of search engine performance is determined by the online search processing. Divided from the distributed search engine model， the search engine consists of four main subsystems： Web crawler system， building index system， retrieval system and log analyzing system. The inverted index is divided into document ids and term frequency（or influence） sequence， which is composed of the dictionary structure and inverted file. Then the paper discusses the typically three types strategies of query processing for the current search eninge， and compares their adaptiation conditions. Finally， the two improtant indicators of evaluation of search engines are reviewed and enumerated the quantitative evaluation formula， which are query efficiently and quality of results， respectively.

Key words Distributed Indexing； Search Engine；，Retrieval Index； Query Processing

0 引 言

随着互联网业务的快速发展，搜索已成为人们学习和生活中的必需工具。面对日益激增的网络数据和复杂的用户需求，强大的搜索能力将成为推动互联网发展的关键要素。

在工业界分布式引擎得到广泛应用，Google、Yahoo！、百度、阿里巴巴等巨大网络引擎公司，都在充分有效地利用分布式搜索架构，以实现分布式引擎的稳定、及拓展运营。

分布式搜索引擎的架构方面，文献[1]指出实现分散化、可扩展和高效的分布式搜索引擎的可行性。文献[2]提出任务并行和数据并行的两种模式架构，能够提高系统吞吐量，实现计算、存储与通信资源的有效利用。文献[3]提出了分布式搜索引擎的成本模型，并指出在足够节点的情况下，存在一个使系统整体最小化的最优节点数量。文献[4]提出面向分布式搜索引擎的并行查询处理方法，可以对查询流量进行有效监测以调整负载平衡。Brroso等人[5] 、Ghemawat等人[6]、Dean等人[7]、Chang等人[8]对Google的分布式搜索引擎进行了概述，并进一步给出了大规模数据处理的介绍。近年来，Map/Reduce[7]已经成功地运用了普通计算机的超大集群，由此实现了大规模的信息处理。作为一种开源的Map/Reduce架构而获得实现的Hadoop具备着一个由Google文件系统复制而来的分布功能，这就为分布式搜索引擎架构的发展提供了良好的现实机遇和广阔经营空间。基于此，下面将展开研究详述。

1 分布式搜索引擎模型

1.1 搜索引擎的结构

如图1所示，搜索引擎主要分两过程：离线处理和在线搜索。具体地，离线处理主要利用爬虫技术抓取互联网上web数据，建立结构化文档数据库（通常采样XML格式存储），再根据索引要求建立索引库，并且能够保证动态更新索引；在线处理则是由用户请求触发，搜索系统查询索引库，系统能够根据搜索日志优化查询结果，同时根据查询缓存来提高搜索效率。

图1 搜索引擎基本模块：离线处理和在线处理

Fig.1 The basic modules of search engine： offline and online processing

经由研究可知，在线查询的过程速度即是决定搜索引擎性能的关键因素，影响查询效率的主要原因包括：用户查询query能够解析出的查询词（term）数；查询词对应的倒排记录表长度；倒排表索引结构和遍历方式；查询词与文档的相关性算法。对于包含缓存策略的系统，缓存效率在很大程度上也将影响查询效率。其中查询词（term）数本身由用户决定，查询词越长代表查询对应的倒排记录表越多，从而需要更多遍历时间开销。倒排记录表的长度与索引的数据规模成线性相关，索引数据越多，平均倒排记录表越长。对于大规模的搜索引擎，多数情况下一个常用倒排记录表需要上百MB存储空间，如果没有一个高效的组织结构和查询处理方法，在短时间内将无法完成对查询过程的常规处理。特别是在大规模高并发的用户请求下，就更加不可能完成指定查询处理过程。

1.2 分布式搜索引擎架构

目前大多数搜索引擎是基于集群的并行分布式架构[10-11]，如图2所示，包括前端应用的查询接口、中间服务器和索引节点三个层次。其中，前端应用接口负载接收各种用户提交的查询，包括点击分析、查询意图分析、查询扩展等，向中间服务器发送最终完整的查询。中间服务器负责向索引服务器发送请求，收集各个索引服务器的相关文档编号，经过排名、获取top-k个得分高的文档id，向文档服务器发送请求，从而获取最终的查询页面转发给用户。

由于索引文档数据较大，倒排索引数据无法存储在单台计算机上，必须分布到集群的多台计算机上，按照分割技术对索引数据进行划分，各个集群中计算机承担查询处理的一部分。同时，借助索引的多份复制容错技术，增强了搜索引擎可靠性。对于文档服务器，类似于索引划分方法，对文档进行水平划分与垂直复制，而对于每次查询请求，则需要在每个小索引上执行查询处理。为了提高搜索引擎的性能，服务器层通常部署查询结果缓存。索引本身就是根据网络爬虫予以定期更新，并完成相应创建的。

基本的搜索引擎包含四个主要子系统：网页爬虫系统，索引构建系统、检索系统和日志分析系统[10-12]。下面即对这四个系统展开如下功能综述。

（1）网络爬虫系统。按照一种策略自动地在互联网中搜索和抓取Web信息，尽可能多、尽可能快地搜索到各种类型的新信息，同时需要定期更新已经搜索旧信息，以免产生无效链接。通常采用两种策略：

按照宽度优先、深度优先或启发式方法搜索URL集合中链接；

按照空间域名、IP地址或国家域名等，进行穷尽式搜索，搜索信息多种多样。

（2）索引构建系统。通过爬虫算法，从网络爬虫中得到网页，对其提取索引词项和链接信息，生成索引词项和URL的关系，建立倒排表。

（3）检索系统。根据用户提交的查询词，经过词项解析、查询词扩展、查询推荐等，查找倒排索引，同时完成页面和查询之间的相关度评分，对输出的结果进行排名，并提供用户的相关性反馈机制。

（4）日志分析系统。查询日志为改进检索速度和效果提供了很好的帮助。一方面记录用户的查询行为，提供查询推荐和个性化搜索；另一方面，用户的查询、翻页和点击行为，从某种程度上对相关性算分、查询结果缓存提供重要改进的服务。

图2分布式搜索引擎的系统架构

Fig.2 The system architecture of distributed search engine

1.3 倒排索引结构

影响搜索引擎的效率、效果问题一直是搜索引擎领域内热门研究内容。对于检索效果，根据用户的查询和文档，可设计建立多种检索模型，如布尔模型、VSM、BM25、自然语言模型等[10-11，13]。对于检索效率问题，有不同的数据结构来支持快速查询，如签名文件[14]、倒排索引等。而作为大规模搜索引擎的必须核心数据结构，倒排索引已证明就是一种非常高效的检索处理结构[14]。

将网络中每个文档或网页（document）看成词组序列，对于整个文档数据集的每个文档都要设定有唯一的文档编号（docId，无特殊情况，以下采用docId指代文档编号）。倒排索引提供文档集中词项与其出现位置的之间的映射，简单组成如图3所示，包含词典（dictionary）和倒排文件（inverted index）两个部分。各个词典的词项对应的倒排列表（posting list）组成了倒排文件。索引词在词典中按照顺序存放，位置信息列表由各个文档的倒排项组成。P（ti，dj）表示词项ti出现文档dj中的信息，包括文档号、词频、相关得分，每个P（ti，dj）构成了词项ti的一个倒排项。

按照倒排项的组织形式，倒排索引结构主要分为两类：

（1）按照文档编号递增排序。在这种索引结构中，每个倒排项包含词项在文档中信息，文档号从小到大排序，这使得在存储文档号di时，按照文档号之间的差值，原来的存储文档号值改变为di - di-1- 1，当值变得很小后可以采用压缩算法。然而由于不知道重要的文档分布在倒排表的哪些位置，索引结构在查询时需要遍历整个倒排链表。

（2）按照词频或者影响力得分递减排序。这类倒排索引结构的优点是重要的文档排在倒排链表的前面，查询时能够很快找到相关、且重要的文档。缺点是：按照词频或得分使得倒排表固定，不能动态进行调整；由于连续的文档很少导致索引压缩率很低；不支持短语或者临近查询。

图3倒数索引结构示意图

Fig.3 The schematic diagrame of inversed index structure

相关研究表明，经过优化的文档编号递增排序要比词频或者影响力排序要更快。以倒排索引结构是采用文档编号递增排序的方式为例，按照文档编号递增排序结构中，词典列出了词汇表中包含的词项，对于词项t都要关联有一个表征其出现位置的信息列表（l（t）），例如词项在倒排文件中的文档docId，保存了这个词的出现次数（词频）。但需要计算更为复杂的分数以及需要精确的位置的查询类型时，还要保存词项t的出现位置信息。

对于一个词t和对应的文档d，较完整的描述如下：

（1）

表示词项t在文档d中出现ft，d次，出现的位置依次为pos1，…，posfd，t。通常每个索引词项t的倒排列表按照docId升序排列，其索引表形式为：

（2）

其中，d1

2 分布式搜索引擎的查询方式

对于索引服务器中的查询处理，研究人员提出了一系列的查询处理策略[10]，大体分为三类。具体表述如下。

2.1 Document-at-a-time（DAAT）

在DAAT的查询处理过程中，首先打开查询请求中所有查询词的倒排索引表，然后同时遍历这些倒排索引表。每次都对当前文档号最小的文档计算相关性得分，并进行统计。而在处理下一篇文档之前，当前的文档的所有相关性得分都必须实现完整计算。因此，DAAT算法是按照文档编号逐篇计算文档的相关性得分，只需要使用较少的存储空间来保存当前文档的最高得分的文档号和分数。通常采用优先队列或者堆来存储当前最高的top-k个文档号及其得分。

2.2 Term-at-a-time（TAAT）

在TAAT处理过程中，每次只打开查询请求中一个查询词的倒排索引，而后进行完整的遍历。因此每次只能得到一个词对文档的部分得分贡献，只有处理了全部倒排索引后，才能得到完整的文档得分。也就是说，TAAT查询处理通常需要对文档分数进行累加，保存文档的临时分数，二者累加器数组的大小与文档集规模相当，所以当搜索引擎的文档规模堪称巨大时，将会使得累加器存储开销也增至庞大。查询词项的倒排索引表太大而不能完全存储在内存时，即是TAAT登场的最佳时机。

2.3 Score-at-a-time（SAAT）

SAAT查询处理适用于影响力排序的索引（Impact-sorted），倒排索引按照文档块的影响力值排序。首先，获取查询词对应的倒排链的各个块的影响值，按照影响值由高到低对块中文档进行处理。每处理一个文档，只能从当前块中获取文档的分数，通常需要处理完成所有块才能得到文档完整分数。因此，SAAT查询方式仍需要为每篇文档分配分数累加器来保存文档临时分数。

2.4 性能综合对比

DAAT算法需要枚举所有匹配的文档，逐个比较其计算得分，然后排序获取top-k个结果，由于不管词项是否出现在文档中都需要为n个查询词（n为用户查询解析的特征词项数目）各自迭代一遍，从而造成算法低效。TAAT或SAAT查询方法中，对每个文档需要一个累加器统计计算过程中得分，而匹配的文档通常都趋于超大，从而使得累加器数组占用过多存储开销。另外，在处理查询词有依赖时，DAAT方法更加容易完成有效处理，这是由于DAAT方法中查询词的依赖信息在处理文档时仅需一次就可以全部得到，而TAAT和SAAT在处理过程中却需要保存分数累加器保存查询词之间的关系，维护代价已是十足客观。

对于不同的倒排索引结构所支持的查询处理方式各不相同，具体就是不同的倒排索引表结构信息的多少使得查询方式各显其能，如表1所示，可以看出TAAT查询可以支持不同的倒排索引结构，而DAAT查询方式只能支持文档号递增排序的倒排索引。

表1 不同倒排索引和支持的查询处理方式

Tab. 1 Different inversed index and its’ appoaches of query processing

倒排索引信息 倒排表文档排序方式 支持查询方式

文档号排序 DAAT、TAAT

文档号排序 DAAT、TAAT

词频排序或影响力排序 TAAT、SAAT

< d， ft，d， [pos1，…，posfd，t]> 文档号排序 DAAT、TAAT

3 分布式搜索引擎的评价指标

查询效率和查询结果的质量是评价搜索引擎的两个重要指标，另外还包括系统可靠性、可扩展性等。用户提交查询后，希望在较短时间内（秒级）返回最希望得到的查询结果。

3.1 查询结果质量的评价指标

对于搜索结果的质量，目前存在很多的评价指标[17-18]，在这里主要介绍查准率（Precision）和召回率（Recall）。

3.1 查准率

查准率指给定一个查询，返回结果列表中相关文档所占的比例，用P@N表示前N个文档包含相关文档的个数。对于搜索引擎，大部分用户只关心前一两页结果，因此P@10和P@20是一种很有效的指标，定义如下：

（3）

3.1.2 召回率

召回率（Recall）指给定一个查询，返回结果中相关文档的个数与全部相关文档的比例，定义如下：

（4）

其中，R代表查询对应相关文档的集合，S代表检索返回的文档集合。通常搜索引擎更关注查准率，对于召回率的计算则稍显困难。

3.1.3 MAP

当存在多个查询时，通常使用MAP（Mean Average Precision）指标，计算MAP之前则需要计算每个查询的平均查准率AP（Average Precision）值，再对各个查询求出平均就是MAP。AP计算公式如下：

（5）

其中，n为实际返回的文档数，P（k）是第k个文档的查准率，choose（k）是布尔函数，当文档相关时为1，不相关时为0。根据AP计算MAP的公式如下：

（6）

其中，|Q|指查询集合Q的个数，AP（qi）表示查询qi对应的平均查准率。

另外，还有DCG（Discounted cumulative gain）、NDCG、MRR（Mean Reciprocal Rank）等搜索引擎的质量指标这里不再一一介绍，参见文献[15-16]。接下部分介绍常用的查询效率的指标，也是对搜索引擎的优化评测的重点。

3.2 查询效率评价指标

查询效率通常指在搜索引擎处理用户查询的资源开销，可以从时间和空间上进行评价。

3.2.1 时间评价

从时间方面，主要针查询响应时间（Response time）和查询吞吐量QPS（queries per second）。查询响应时间是指用户提交查询后到返回结果所用的时间；而查询吞吐量衡量搜索引擎每秒钟能处理完成用户查询的数量。普通用户只关心查询的响应时间，当用户提交查询后感觉到有延时，会觉得搜索引擎的查询速度较慢。在实际评价搜索引擎时，使用平均响应时间或者80%以上的查询响应时间来进行权衡度量。而作为搜索引擎公司则更为关注系统吞吐量，这是因为吞吐量的大小将直接影响到系统能同时服务的用户查询数。追求低响应时间和高吞吐量是检索系统的追求目标，然而二者相互冲突，即无法同时满足最大化。实际应用中多是通过机器规模来扩大系统吞吐量，而利用索引划分来降低各个索引节点的查询延时。

3.2.2 空间评价

从空间上看，主要从查询时内存空间，索引大小以及CPU利用率方面评价搜索引擎性能。查询处理过程中内存空间指在用户查询处理时，所使用的临时空间的多少，与查询算法相关，例如DAAT查询方法使用临时内存空间比TAAT和SAAT的查询方式要小上很多。索引大小是指有文档建立倒排索引后，需要的存储空间大小。CPU利用率则指在查询过程中CPU的开销，用来衡量查询算法复杂性和系统负载。

另外，搜索引擎系统的可扩展是衡量当前系统长久存活的一项重要指标。通常情况下，随着索引数据规模增大，会发生一系列问题，包括系统可靠性、查询结果更新一致、容错等，即通过扩充硬件服务器，不需要对系统的算法、资源调度等加以干涉，直接能实现快速自适应。

4 结束语

本文综述了分布式搜索引擎研究工作相关的内容和当前研究现状，对分布搜索引擎的结构、模型、倒排索引结构进行描述，比较分布式搜索引擎的各自查询处理方式和评价指标。掌握分布式搜索引擎的模型，对于应接当前搜索引擎面临的挑战，进而提升系统扩展性和性能的研究具有重要意义。

参 考 文 献

[1] BENDER M， MICHEL S， TRIANTAFILLOU P， et al. Design alternatives for large-scale web search： Alexander was great， aeneas a pioneer， and anakin has the force[C]// 1st LSDS-IR Workshop， Amsterdam：ACM，2007： 16-22.

[2] ORLANDO S， PEREGO R， SILVESTRI F. Design of a parallel and distributed web search engine[J]. arXiv preprint cs/0407053， 2004.

[3] BAEZA-YATES R， GIONIS A， JUNQUEIRA F， et al. On the feasibility of multi-site web search engines[C]// Proceedings of the 18th ACM conference on Information and knowledge management， [S.l]：ACM， 2009： 425-434.

[4] MOFFAT A， WEBBER W， ZOBEL J. Load balancing for term-distributed parallel retrieval[C]//Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval，[S.l]： ACM， 2006： 348-355.

[5] BARROSO L A， DEAN J， H?LZLE U. Web search for a planet： The Google cluster architecture[J]. Micro， Ieee， 2003， 23（2）： 22-28.

[6] GHEMAWAT S， GOBIOFF H， LEUNG S T. The Google file system[J]. ACM SIGOPS Operating Systems Review， 2003， 37（5）： 29-43.

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

[8] CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： A distributed storage system for structured data[J]. ACM Transactions on Computer Systems （TOCS）， 2008， 26（2）： 4.

[9] 李晓明，闫宏飞，王继民. 搜索引擎――原理、技术与系统[M]（ 第二版）. 北京：科学出版社，2012.5

[10] Lafferty J， Zhai C. Probabilistic relevance models based on document and query generation[M]//Netherlands Springer： Language modeling for information retrieval， 2003： 1-10.

[11] Robertson S， Zaragoza H. The probabilistic relevance framework： BM25 and beyond[M]. Boston： Now Publishers Inc， 2009.

[12] ROELLEKE T， WANG J. A parallel derivation of probabilistic information retrieval models[C]//Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval，[S.l]： ACM， 2006： 107-114.

[13] FALOUTSOS C， CHRISTODOULAKIS S. Signature files： An access method for documents and its analytical performance evaluation[J]. ACM Transactions on Information Systems （TOIS）， 1984， 2（4）： 267-288.

[14] Büttcher S， Clarke C L A， Cormack G V. Information retrieval： Implementing and evaluating search engines[M]. Massachusetts ： Mit Press， 2010：488-505.

[15] 何靖，李晓明.搜索引擎效果评测――基于用户点击日志分析的方法与技术[M].北京：高等教育出版社，2012.

[16] 董守斌，袁华. 网络信息检索[M]. 西安：西安电子科技大学出版社， 2010.