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

錢(qián)立兵　季振洲

摘 要 本文綜述了分布式搜索引擎的模型、結(jié)構(gòu)和查詢(xún)方法，并討論了搜索引擎的評(píng)價(jià)指標(biāo)。從搜索引擎的離線處理和在線處理討論了搜索引擎的基本模塊，在線查詢(xún)過(guò)程速度決定了搜索引擎性能的關(guān)鍵因素；從分布式搜索引擎的模型上劃分，搜索引擎包含四個(gè)主要子系統(tǒng)：網(wǎng)頁(yè)爬蟲(chóng)系統(tǒng)，索引構(gòu)建系統(tǒng)、檢索系統(tǒng)和日志分析系統(tǒng)；倒排索引結(jié)構(gòu)是以詞典（dictionary）和倒排文件（inverted file）組成，分為文檔編號(hào)遞增排序和詞頻（或影響力）得分遞減排序。然后討論了當(dāng)前搜索引擎典型的三類(lèi)查詢(xún)處理策略，并比較各自適應(yīng)的條件。最后，綜述評(píng)價(jià)搜索引擎的兩個(gè)重要指標(biāo)： 查詢(xún)效率和查詢(xún)結(jié)果的質(zhì)量，并列舉定量評(píng)價(jià)公式。

關(guān)鍵詞 分布式索引； 搜索引擎；倒排索引；查詢(xún)處理

中圖法分類(lèi)號(hào) TP393 文獻(xiàn)標(biāo)識(shí)碼 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 引 言

隨著互聯(lián)網(wǎng)業(yè)務(wù)的快速發(fā)展，搜索已成為人們學(xué)習(xí)和生活中的必需工具。面對(duì)日益激增的網(wǎng)絡(luò)數(shù)據(jù)和復(fù)雜的用戶需求，強(qiáng)大的搜索能力將成為推動(dòng)互聯(lián)網(wǎng)發(fā)展的關(guān)鍵要素。

在工業(yè)界分布式引擎得到廣泛應(yīng)用，Google、Yahoo！、百度、阿里巴巴等巨大網(wǎng)絡(luò)引擎公司，都在充分有效地利用分布式搜索架構(gòu)，以實(shí)現(xiàn)分布式引擎的穩(wěn)定、及拓展運(yùn)營(yíng)。

分布式搜索引擎的架構(gòu)方面，文獻(xiàn)[1]指出實(shí)現(xiàn)分散化、可擴(kuò)展和高效的分布式搜索引擎的可行性。文獻(xiàn)[2]提出任務(wù)并行和數(shù)據(jù)并行的兩種模式架構(gòu)，能夠提高系統(tǒng)吞吐量，實(shí)現(xiàn)計(jì)算、存儲(chǔ)與通信資源的有效利用。文獻(xiàn)[3]提出了分布式搜索引擎的成本模型，并指出在足夠節(jié)點(diǎn)的情況下，存在一個(gè)使系統(tǒng)整體最小化的最優(yōu)節(jié)點(diǎn)數(shù)量。文獻(xiàn)[4]提出面向分布式搜索引擎的并行查詢(xún)處理方法，可以對(duì)查詢(xún)流量進(jìn)行有效監(jiān)測(cè)以調(diào)整負(fù)載平衡。Brroso等人[5] 、Ghemawat等人[6]、Dean等人[7]、Chang等人[8]對(duì)Google的分布式搜索引擎進(jìn)行了概述，并進(jìn)一步給出了大規(guī)模數(shù)據(jù)處理的介紹。近年來(lái)，Map/Reduce[7]已經(jīng)成功地運(yùn)用了普通計(jì)算機(jī)的超大集群，由此實(shí)現(xiàn)了大規(guī)模的信息處理。作為一種開(kāi)源的Map/Reduce架構(gòu)而獲得實(shí)現(xiàn)的Hadoop具備著一個(gè)由Google文件系統(tǒng)復(fù)制而來(lái)的分布功能，這就為分布式搜索引擎架構(gòu)的發(fā)展提供了良好的現(xiàn)實(shí)機(jī)遇和廣闊經(jīng)營(yíng)空間?；诖?，下面將展開(kāi)研究詳述。

1 分布式搜索引擎模型

1.1 搜索引擎的結(jié)構(gòu)

如圖1所示，搜索引擎主要分兩過(guò)程：離線處理和在線搜索。具體地，離線處理主要利用爬蟲(chóng)技術(shù)抓取互聯(lián)網(wǎng)上web數(shù)據(jù)，建立結(jié)構(gòu)化文檔數(shù)據(jù)庫(kù)（通常采樣X(jué)ML格式存儲(chǔ)），再根據(jù)索引要求建立索引庫(kù)，并且能夠保證動(dòng)態(tài)更新索引；在線處理則是由用戶請(qǐng)求觸發(fā)，搜索系統(tǒng)查詢(xún)索引庫(kù)，系統(tǒng)能夠根據(jù)搜索日志優(yōu)化查詢(xún)結(jié)果，同時(shí)根據(jù)查詢(xún)緩存來(lái)提高搜索效率。

圖1 搜索引擎基本模塊：離線處理和在線處理

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

經(jīng)由研究可知，在線查詢(xún)的過(guò)程速度即是決定搜索引擎性能的關(guān)鍵因素，影響查詢(xún)效率的主要原因包括：用戶查詢(xún)query能夠解析出的查詢(xún)?cè)~（term）數(shù)；查詢(xún)?cè)~對(duì)應(yīng)的倒排記錄表長(zhǎng)度；倒排表索引結(jié)構(gòu)和遍歷方式；查詢(xún)?cè)~與文檔的相關(guān)性算法。對(duì)于包含緩存策略的系統(tǒng)，緩存效率在很大程度上也將影響查詢(xún)效率。其中查詢(xún)?cè)~（term）數(shù)本身由用戶決定，查詢(xún)?cè)~越長(zhǎng)代表查詢(xún)對(duì)應(yīng)的倒排記錄表越多，從而需要更多遍歷時(shí)間開(kāi)銷(xiāo)。倒排記錄表的長(zhǎng)度與索引的數(shù)據(jù)規(guī)模成線性相關(guān)，索引數(shù)據(jù)越多，平均倒排記錄表越長(zhǎng)。對(duì)于大規(guī)模的搜索引擎，多數(shù)情況下一個(gè)常用倒排記錄表需要上百M(fèi)B存儲(chǔ)空間，如果沒(méi)有一個(gè)高效的組織結(jié)構(gòu)和查詢(xún)處理方法，在短時(shí)間內(nèi)將無(wú)法完成對(duì)查詢(xún)過(guò)程的常規(guī)處理。特別是在大規(guī)模高并發(fā)的用戶請(qǐng)求下，就更加不可能完成指定查詢(xún)處理過(guò)程。

1.2 分布式搜索引擎架構(gòu)

目前大多數(shù)搜索引擎是基于集群的并行分布式架構(gòu)[10-11]，如圖2所示，包括前端應(yīng)用的查詢(xún)接口、中間代理服務(wù)器和索引節(jié)點(diǎn)三個(gè)層次。其中，前端應(yīng)用接口負(fù)載接收各種用戶提交的查詢(xún)，包括點(diǎn)擊分析、查詢(xún)意圖分析、查詢(xún)擴(kuò)展等，向中間代理服務(wù)器發(fā)送最終完整的查詢(xún)。中間代理服務(wù)器負(fù)責(zé)向索引服務(wù)器發(fā)送請(qǐng)求，收集各個(gè)索引服務(wù)器的相關(guān)文檔編號(hào)，經(jīng)過(guò)排名、獲取top-k個(gè)得分高的文檔id，向文檔服務(wù)器發(fā)送請(qǐng)求，從而獲取最終的查詢(xún)頁(yè)面轉(zhuǎn)發(fā)給用戶。

由于索引文檔數(shù)據(jù)較大，倒排索引數(shù)據(jù)無(wú)法存儲(chǔ)在單臺(tái)計(jì)算機(jī)上，必須分布到集群的多臺(tái)計(jì)算機(jī)上，按照分割技術(shù)對(duì)索引數(shù)據(jù)進(jìn)行劃分，各個(gè)集群中計(jì)算機(jī)承擔(dān)查詢(xún)處理的一部分。同時(shí)，借助索引的多份復(fù)制容錯(cuò)技術(shù)，增強(qiáng)了搜索引擎可靠性。對(duì)于文檔服務(wù)器，類(lèi)似于索引劃分方法，對(duì)文檔進(jìn)行水平劃分與垂直復(fù)制，而對(duì)于每次查詢(xún)請(qǐng)求，則需要在每個(gè)小索引上執(zhí)行查詢(xún)處理。為了提高搜索引擎的性能，代理服務(wù)器層通常部署查詢(xún)結(jié)果緩存。索引本身就是根據(jù)網(wǎng)絡(luò)爬蟲(chóng)予以定期更新，并完成相應(yīng)創(chuàng)建的。

基本的搜索引擎包含四個(gè)主要子系統(tǒng)：網(wǎng)頁(yè)爬蟲(chóng)系統(tǒng)，索引構(gòu)建系統(tǒng)、檢索系統(tǒng)和日志分析系統(tǒng)[10-12]。下面即對(duì)這四個(gè)系統(tǒng)展開(kāi)如下功能綜述。

（1）網(wǎng)絡(luò)爬蟲(chóng)系統(tǒng)。按照一種策略自動(dòng)地在互聯(lián)網(wǎng)中搜索和抓取Web信息，盡可能多、盡可能快地搜索到各種類(lèi)型的新信息，同時(shí)需要定期更新已經(jīng)搜索舊信息，以免產(chǎn)生無(wú)效鏈接。通常采用兩種策略：

按照寬度優(yōu)先、深度優(yōu)先或啟發(fā)式方法搜索URL集合中鏈接；

按照空間域名、IP地址或國(guó)家域名等，進(jìn)行窮盡式搜索，搜索信息多種多樣。

（2）索引構(gòu)建系統(tǒng)。通過(guò)爬蟲(chóng)算法，從網(wǎng)絡(luò)爬蟲(chóng)中得到網(wǎng)頁(yè)，對(duì)其提取索引詞項(xiàng)和鏈接信息，生成索引詞項(xiàng)和URL的關(guān)系，建立倒排表。

（3）檢索系統(tǒng)。根據(jù)用戶提交的查詢(xún)?cè)~，經(jīng)過(guò)詞項(xiàng)解析、查詢(xún)?cè)~擴(kuò)展、查詢(xún)推薦等，查找倒排索引，同時(shí)完成頁(yè)面和查詢(xún)之間的相關(guān)度評(píng)分，對(duì)輸出的結(jié)果進(jìn)行排名，并提供用戶的相關(guān)性反饋機(jī)制。

（4）日志分析系統(tǒng)。查詢(xún)?nèi)罩緸楦倪M(jìn)檢索速度和效果提供了很好的幫助。一方面記錄用戶的查詢(xún)行為，提供查詢(xún)推薦和個(gè)性化搜索；另一方面，用戶的查詢(xún)、翻頁(yè)和點(diǎn)擊行為，從某種程度上對(duì)相關(guān)性算分、查詢(xún)結(jié)果緩存提供重要改進(jìn)的服務(wù)。

圖2分布式搜索引擎的系統(tǒng)架構(gòu)

Fig.2 The system architecture of distributed search engine

1.3 倒排索引結(jié)構(gòu)

影響搜索引擎的效率、效果問(wèn)題一直是搜索引擎領(lǐng)域內(nèi)熱門(mén)研究?jī)?nèi)容。對(duì)于檢索效果，根據(jù)用戶的查詢(xún)和文檔，可設(shè)計(jì)建立多種檢索模型，如布爾模型、VSM、BM25、自然語(yǔ)言模型等[10-11，13]。對(duì)于檢索效率問(wèn)題，有不同的數(shù)據(jù)結(jié)構(gòu)來(lái)支持快速查詢(xún)，如簽名文件[14]、倒排索引等。而作為大規(guī)模搜索引擎的必須核心數(shù)據(jù)結(jié)構(gòu)，倒排索引已證明就是一種非常高效的檢索處理結(jié)構(gòu)[14]。

將網(wǎng)絡(luò)中每個(gè)文檔或網(wǎng)頁(yè)（document）看成詞組序列，對(duì)于整個(gè)文檔數(shù)據(jù)集的每個(gè)文檔都要設(shè)定有唯一的文檔編號(hào)（docId，無(wú)特殊情況，以下采用docId指代文檔編號(hào)）。倒排索引提供文檔集中詞項(xiàng)與其出現(xiàn)位置的之間的映射，簡(jiǎn)單組成如圖3所示，包含詞典（dictionary）和倒排文件（inverted index）兩個(gè)部分。各個(gè)詞典的詞項(xiàng)對(duì)應(yīng)的倒排列表（posting list）組成了倒排文件。索引詞在詞典中按照順序存放，位置信息列表由各個(gè)文檔的倒排項(xiàng)組成。P（ti，dj）表示詞項(xiàng)ti出現(xiàn)文檔dj中的信息，包括文檔號(hào)、詞頻、相關(guān)得分，每個(gè)P（ti，dj）構(gòu)成了詞項(xiàng)ti的一個(gè)倒排項(xiàng)。

按照倒排項(xiàng)的組織形式，倒排索引結(jié)構(gòu)主要分為兩類(lèi)：

（1）按照文檔編號(hào)遞增排序。在這種索引結(jié)構(gòu)中，每個(gè)倒排項(xiàng)包含詞項(xiàng)在文檔中信息，文檔號(hào)從小到大排序，這使得在存儲(chǔ)文檔號(hào)di時(shí)，按照文檔號(hào)之間的差值，原來(lái)的存儲(chǔ)文檔號(hào)值改變?yōu)閐i - di-1- 1，當(dāng)值變得很小后可以采用壓縮算法。然而由于不知道重要的文檔分布在倒排表的哪些位置，索引結(jié)構(gòu)在查詢(xún)時(shí)需要遍歷整個(gè)倒排鏈表。

（2）按照詞頻或者影響力得分遞減排序。這類(lèi)倒排索引結(jié)構(gòu)的優(yōu)點(diǎn)是重要的文檔排在倒排鏈表的前面，查詢(xún)時(shí)能夠很快找到相關(guān)、且重要的文檔。缺點(diǎn)是：按照詞頻或得分使得倒排表固定，不能動(dòng)態(tài)進(jìn)行調(diào)整；由于連續(xù)的文檔很少導(dǎo)致索引壓縮率很低；不支持短語(yǔ)或者臨近查詢(xún)。

圖3倒數(shù)索引結(jié)構(gòu)示意圖

Fig.3 The schematic diagrame of inversed index structure

相關(guān)研究表明，經(jīng)過(guò)優(yōu)化的文檔編號(hào)遞增排序要比詞頻或者影響力排序要更快。以倒排索引結(jié)構(gòu)是采用文檔編號(hào)遞增排序的方式為例，按照文檔編號(hào)遞增排序結(jié)構(gòu)中，詞典列出了詞匯表中包含的詞項(xiàng)，對(duì)于詞項(xiàng)t都要關(guān)聯(lián)有一個(gè)表征其出現(xiàn)位置的信息列表（l（t）），例如詞項(xiàng)在倒排文件中的文檔docId，保存了這個(gè)詞的出現(xiàn)次數(shù)（詞頻）。但需要計(jì)算更為復(fù)雜的分?jǐn)?shù)以及需要精確的位置的查詢(xún)類(lèi)型時(shí)，還要保存詞項(xiàng)t的出現(xiàn)位置信息。

對(duì)于一個(gè)詞t和對(duì)應(yīng)的文檔d，較完整的描述如下：

（1）

表示詞項(xiàng)t在文檔d中出現(xiàn)ft，d次，出現(xiàn)的位置依次為pos1，…，posfd，t。通常每個(gè)索引詞項(xiàng)t的倒排列表按照docId升序排列，其索引表形式為：

（2）

其中，d1

2 分布式搜索引擎的查詢(xún)方式

對(duì)于索引服務(wù)器中的查詢(xún)處理，研究人員提出了一系列的查詢(xún)處理策略[10]，大體分為三類(lèi)。具體表述如下。

2.1 Document-at-a-time（DAAT）

在DAAT的查詢(xún)處理過(guò)程中，首先打開(kāi)查詢(xún)請(qǐng)求中所有查詢(xún)?cè)~的倒排索引表，然后同時(shí)遍歷這些倒排索引表。每次都對(duì)當(dāng)前文檔號(hào)最小的文檔計(jì)算相關(guān)性得分，并進(jìn)行統(tǒng)計(jì)。而在處理下一篇文檔之前，當(dāng)前的文檔的所有相關(guān)性得分都必須實(shí)現(xiàn)完整計(jì)算。因此，DAAT算法是按照文檔編號(hào)逐篇計(jì)算文檔的相關(guān)性得分，只需要使用較少的存儲(chǔ)空間來(lái)保存當(dāng)前文檔的最高得分的文檔號(hào)和分?jǐn)?shù)。通常采用優(yōu)先隊(duì)列或者堆來(lái)存儲(chǔ)當(dāng)前最高的top-k個(gè)文檔號(hào)及其得分。

2.2 Term-at-a-time（TAAT）

在TAAT處理過(guò)程中，每次只打開(kāi)查詢(xún)請(qǐng)求中一個(gè)查詢(xún)?cè)~的倒排索引，而后進(jìn)行完整的遍歷。因此每次只能得到一個(gè)詞對(duì)文檔的部分得分貢獻(xiàn)，只有處理了全部倒排索引后，才能得到完整的文檔得分。也就是說(shuō)，TAAT查詢(xún)處理通常需要對(duì)文檔分?jǐn)?shù)進(jìn)行累加，保存文檔的臨時(shí)分?jǐn)?shù)，二者累加器數(shù)組的大小與文檔集規(guī)模相當(dāng)，所以當(dāng)搜索引擎的文檔規(guī)?？胺Q(chēng)巨大時(shí)，將會(huì)使得累加器存儲(chǔ)開(kāi)銷(xiāo)也增至龐大。查詢(xún)?cè)~項(xiàng)的倒排索引表太大而不能完全存儲(chǔ)在內(nèi)存時(shí)，即是TAAT登場(chǎng)的最佳時(shí)機(jī)。

2.3 Score-at-a-time（SAAT）

SAAT查詢(xún)處理適用于影響力排序的索引（Impact-sorted），倒排索引按照文檔塊的影響力值排序。首先，獲取查詢(xún)?cè)~對(duì)應(yīng)的倒排鏈的各個(gè)塊的影響值，按照影響值由高到低對(duì)塊中文檔進(jìn)行處理。每處理一個(gè)文檔，只能從當(dāng)前塊中獲取文檔的分?jǐn)?shù)，通常需要處理完成所有塊才能得到文檔完整分?jǐn)?shù)。因此，SAAT查詢(xún)方式仍需要為每篇文檔分配分?jǐn)?shù)累加器來(lái)保存文檔臨時(shí)分?jǐn)?shù)。

2.4 性能綜合對(duì)比

DAAT算法需要枚舉所有匹配的文檔，逐個(gè)比較其計(jì)算得分，然后排序獲取top-k個(gè)結(jié)果，由于不管詞項(xiàng)是否出現(xiàn)在文檔中都需要為n個(gè)查詢(xún)?cè)~（n為用戶查詢(xún)解析的特征詞項(xiàng)數(shù)目）各自迭代一遍，從而造成算法低效。TAAT或SAAT查詢(xún)方法中，對(duì)每個(gè)文檔需要一個(gè)累加器統(tǒng)計(jì)計(jì)算過(guò)程中得分，而匹配的文檔通常都趨于超大，從而使得累加器數(shù)組占用過(guò)多存儲(chǔ)開(kāi)銷(xiāo)。另外，在處理查詢(xún)?cè)~有依賴(lài)時(shí)，DAAT方法更加容易完成有效處理，這是由于DAAT方法中查詢(xún)?cè)~的依賴(lài)信息在處理文檔時(shí)僅需一次就可以全部得到，而TAAT和SAAT在處理過(guò)程中卻需要保存分?jǐn)?shù)累加器保存查詢(xún)?cè)~之間的關(guān)系，維護(hù)代價(jià)已是十足客觀。

對(duì)于不同的倒排索引結(jié)構(gòu)所支持的查詢(xún)處理方式各不相同，具體就是不同的倒排索引表結(jié)構(gòu)信息的多少使得查詢(xún)方式各顯其能，如表1所示，可以看出TAAT查詢(xún)可以支持不同的倒排索引結(jié)構(gòu)，而DAAT查詢(xún)方式只能支持文檔號(hào)遞增排序的倒排索引。

表1 不同倒排索引和支持的查詢(xún)處理方式

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

倒排索引信息 倒排表文檔排序方式 支持查詢(xún)方式

文檔號(hào)排序 DAAT、TAAT

文檔號(hào)排序 DAAT、TAAT

詞頻排序或影響力排序 TAAT、SAAT

< d， ft，d， [pos1，…，posfd，t]> 文檔號(hào)排序 DAAT、TAAT

3 分布式搜索引擎的評(píng)價(jià)指標(biāo)

查詢(xún)效率和查詢(xún)結(jié)果的質(zhì)量是評(píng)價(jià)搜索引擎的兩個(gè)重要指標(biāo)，另外還包括系統(tǒng)可靠性、可擴(kuò)展性等。用戶提交查詢(xún)后，希望在較短時(shí)間內(nèi)（秒級(jí)）返回最希望得到的查詢(xún)結(jié)果。

3.1 查詢(xún)結(jié)果質(zhì)量的評(píng)價(jià)指標(biāo)

對(duì)于搜索結(jié)果的質(zhì)量，目前存在很多的評(píng)價(jià)指標(biāo)[17-18]，在這里主要介紹查準(zhǔn)率（Precision）和召回率（Recall）。

3.1 查準(zhǔn)率

查準(zhǔn)率指給定一個(gè)查詢(xún)，返回結(jié)果列表中相關(guān)文檔所占的比例，用P@N表示前N個(gè)文檔包含相關(guān)文檔的個(gè)數(shù)。對(duì)于搜索引擎，大部分用戶只關(guān)心前一兩頁(yè)結(jié)果，因此P@10和P@20是一種很有效的指標(biāo)，定義如下：

（3）

3.1.2 召回率

召回率（Recall）指給定一個(gè)查詢(xún)，返回結(jié)果中相關(guān)文檔的個(gè)數(shù)與全部相關(guān)文檔的比例，定義如下：

（4）

其中，R代表查詢(xún)對(duì)應(yīng)相關(guān)文檔的集合，S代表檢索返回的文檔集合。通常搜索引擎更關(guān)注查準(zhǔn)率，對(duì)于召回率的計(jì)算則稍顯困難。

3.1.3 MAP

當(dāng)存在多個(gè)查詢(xún)時(shí)，通常使用MAP（Mean Average Precision）指標(biāo)，計(jì)算MAP之前則需要計(jì)算每個(gè)查詢(xún)的平均查準(zhǔn)率AP（Average Precision）值，再對(duì)各個(gè)查詢(xún)求出平均就是MAP。AP計(jì)算公式如下：

（5）

其中，n為實(shí)際返回的文檔數(shù)，P（k）是第k個(gè)文檔的查準(zhǔn)率，choose（k）是布爾函數(shù)，當(dāng)文檔相關(guān)時(shí)為1，不相關(guān)時(shí)為0。根據(jù)AP計(jì)算MAP的公式如下：

（6）

其中，|Q|指查詢(xún)集合Q的個(gè)數(shù)，AP（qi）表示查詢(xún)qi對(duì)應(yīng)的平均查準(zhǔn)率。

另外，還有DCG（Discounted cumulative gain）、NDCG、MRR（Mean Reciprocal Rank）等搜索引擎的質(zhì)量指標(biāo)這里不再一一介紹，參見(jiàn)文獻(xiàn)[15-16]。接下部分介紹常用的查詢(xún)效率的指標(biāo)，也是對(duì)搜索引擎的優(yōu)化評(píng)測(cè)的重點(diǎn)。

3.2 查詢(xún)效率評(píng)價(jià)指標(biāo)

查詢(xún)效率通常指在搜索引擎處理用戶查詢(xún)的資源開(kāi)銷(xiāo)，可以從時(shí)間和空間上進(jìn)行評(píng)價(jià)。

3.2.1 時(shí)間評(píng)價(jià)

從時(shí)間方面，主要針查詢(xún)響應(yīng)時(shí)間（Response time）和查詢(xún)吞吐量QPS（queries per second）。查詢(xún)響應(yīng)時(shí)間是指用戶提交查詢(xún)后到返回結(jié)果所用的時(shí)間；而查詢(xún)吞吐量衡量搜索引擎每秒鐘能處理完成用戶查詢(xún)的數(shù)量。普通用戶只關(guān)心查詢(xún)的響應(yīng)時(shí)間，當(dāng)用戶提交查詢(xún)后感覺(jué)到有延時(shí)，會(huì)覺(jué)得搜索引擎的查詢(xún)速度較慢。在實(shí)際評(píng)價(jià)搜索引擎時(shí)，使用平均響應(yīng)時(shí)間或者80%以上的查詢(xún)響應(yīng)時(shí)間來(lái)進(jìn)行權(quán)衡度量。而作為搜索引擎公司則更為關(guān)注系統(tǒng)吞吐量，這是因?yàn)橥掏铝康拇笮⒅苯佑绊懙较到y(tǒng)能同時(shí)服務(wù)的用戶查詢(xún)數(shù)。追求低響應(yīng)時(shí)間和高吞吐量是檢索系統(tǒng)的追求目標(biāo)，然而二者相互沖突，即無(wú)法同時(shí)滿足最大化。實(shí)際應(yīng)用中多是通過(guò)機(jī)器規(guī)模來(lái)擴(kuò)大系統(tǒng)吞吐量，而利用索引劃分來(lái)降低各個(gè)索引節(jié)點(diǎn)的查詢(xún)延時(shí)。

3.2.2 空間評(píng)價(jià)

從空間上看，主要從查詢(xún)時(shí)內(nèi)存空間，索引大小以及CPU利用率方面評(píng)價(jià)搜索引擎性能。查詢(xún)處理過(guò)程中內(nèi)存空間指在用戶查詢(xún)處理時(shí)，所使用的臨時(shí)空間的多少，與查詢(xún)算法相關(guān)，例如DAAT查詢(xún)方法使用臨時(shí)內(nèi)存空間比TAAT和SAAT的查詢(xún)方式要小上很多。索引大小是指有文檔建立倒排索引后，需要的存儲(chǔ)空間大小。CPU利用率則指在查詢(xún)過(guò)程中CPU的開(kāi)銷(xiāo)，用來(lái)衡量查詢(xún)算法復(fù)雜性和系統(tǒng)負(fù)載。

另外，搜索引擎系統(tǒng)的可擴(kuò)展是衡量當(dāng)前系統(tǒng)長(zhǎng)久存活的一項(xiàng)重要指標(biāo)。通常情況下，隨著索引數(shù)據(jù)規(guī)模增大，會(huì)發(fā)生一系列問(wèn)題，包括系統(tǒng)可靠性、查詢(xún)結(jié)果更新一致、容錯(cuò)等，即通過(guò)擴(kuò)充硬件服務(wù)器，不需要對(duì)系統(tǒng)的算法、資源調(diào)度等加以干涉，直接能實(shí)現(xiàn)快速自適應(yīng)。

4 結(jié)束語(yǔ)

本文綜述了分布式搜索引擎研究工作相關(guān)的內(nèi)容和當(dāng)前研究現(xiàn)狀，對(duì)分布搜索引擎的結(jié)構(gòu)、模型、倒排索引結(jié)構(gòu)進(jìn)行描述，比較分布式搜索引擎的各自查詢(xún)處理方式和評(píng)價(jià)指標(biāo)。掌握分布式搜索引擎的模型，對(duì)于應(yīng)接當(dāng)前搜索引擎面臨的挑戰(zhàn)，進(jìn)而提升系統(tǒng)擴(kuò)展性和性能的研究具有重要意義。

參 考 文 獻(xiàn)

[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] 李曉明，閆宏飛，王繼民. 搜索引擎——原理、技術(shù)與系統(tǒng)[M]（ 第二版）. 北京：科學(xué)出版社，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] 何靖，李曉明.搜索引擎效果評(píng)測(cè)——基于用戶點(diǎn)擊日志分析的方法與技術(shù)[M].北京：高等教育出版社，2012.

[16] 董守斌，袁華. 網(wǎng)絡(luò)信息檢索[M]. 西安：西安電子科技大學(xué)出版社， 2010.