高性能海量数据检索系统的设计与实现

1、北京大学硕士研究生学位论文题目：海量文档高速检索系统的设计与实现姓名：谢翰学号：10280040系别：信息科学技术学院专业：计算机软件与理论研究方向：网络与分布式系统导师：李晓明教授二零零五年六月版权声明任何收存和保管论文各种版本的单位和个人，未经本论文作者授权，不得将本论文转借他人，亦不得随意复印、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权益之问题，将可能承担法律责任。摘要搜索引擎的检索效率是评价搜索引擎质量的一个重要指标，面对互联网上信息量的不断增加以及搜索引擎网页库的不断增大，对检索系统性能要求也越来越高。本文详细介绍了一个搜索引擎检索系统的设计与实现，针对搜索引擎检索系统的性

2、能问题进行了研究，讨论了影响检索性能的几个因素，并分别提出改进的方法和途径。这些方法包括设计出结构更加良好的倒排文件结构，改进整数压缩编码，引入倒排文件cache,预先计算关键词与文档相关度，减少关键词相对位置计算开销，改进站点聚类算法等。另外，论文还阐述了系统中使用的新的相关度计算方法，这个算法使得在最终的结果排序上比原有系统有了一些改进。论文的组织形式以实际系统中各模块为主线，这些模块包括倒排文件结构，底层数据接口，查询，计分和站点聚类等。在论文最后给出了系统的综合测试结果，指出系统中还存在的不足，并对后续工作提出了一些建议。关键词：搜索引擎，检索系统，倒排文件，检索效率，相关度计算The

3、DesignandImplementationofaHighPerformanceRetrievalSystemXIEHan(ComputerSoftwareandTheory)DirectedbyLIXiaomingAbstractTheperformanceofretrievingiscrucialformodernsearchengine.Thisarticleintroducesthedesignandimplementationofaretrievalsystemforwebsearchengine.Especially,wewilldiscussthefactorsthataffe

4、ctretrievalperformance,andgivethesolutionsforeachofthem,suchasdesigninganewformatforinvertedfileandanewencodingalgorithmforintegers,introducingcachefortheindex,pre-computingthesimilarityoftermsanddocuments,anddesigningabettersitegroupingalgorithm.Anewrankingalgorithmusedinthesystemwillbediscussedtoo

5、.Thearticleisorganizedbymodules,includinginvertedfile,datainterface,queryscoringandsitegrouping.Inthelastchapterwewillmakeanoverallevolution,andsomeadvicesforitsfurtherimprovementwillbegiven.Keywords:searchengine,retrievalsystem,invertedfile,performance,ranking.目录第1章绪论1.1.1 搜索引擎原理1.1.2 倒排文件2.1.3 检索系

6、统分布式结构.4.1.4 现有系统的不足与本文的主要贡献5第2章倒排文件设计 基本原则 整数压缩编码方法 系统使用的倒排文件结构定义81 描述文件8.1 索引文件101 记录文件10第3章底层数据组织131.1.< 影响检索效率的主要因素1.31.2.< 创建索引1.51.3.< 获得文档列表18< 接口与数据组织1.8< 性能测试201.4.< 获得位置列表231.5.< 模块的一些不足26第4章查询过程274.2 文档列表求交274.3 相关度计算284.3.1 关键词与文档相关度284.3.2 相对位置得

7、分304.4 站点聚类314.5 查询模块接口33第5章综合评测与总结35系统整体结构35实验设计36实验结果37总结39第1章绪论搜索引擎原理众所周知，搜索引擎是从互联网上搜寻信息的重要工具。随着互联网规模的不断增大，网上信息量的不断增长，搜索引擎的作用越来越明显。互联网上搜索引擎虽然大小不同，功能各异，但它们都包含以下一些基本的功能模块。.网页收集网页收集是搜索引擎的第一步工作，要进行网页搜索显然必须先有一个网页库。除了少量手工加入的网页，大多数网页都是通过被称为spider的自动网页收集程序收集下来的。spider的基本工作原理很简单：以一些重要的网页为种子，先收集这些网页，提取这些网页

8、上的链接，再收集被链向的网页。如此不断地循环下去，就可收集到互联网上大量的网页。另外也可通过端口扫描的方法发现隐藏的web服务器。评价spider的质量有几个重要的指标，包括网页收集的速度，网页质量与重复率，发现新增网页和变化网页的速度，动态网页的收集策略，对对方web服务器的礼貌性等。目前大多数的研究都集中在网页质量和增量式的网页收集上。.页面预处理从互联网上收集到了网页，到真正的提供搜索服务还有很多的事情要做。首先是对网页进行一些预处理。对网页进行预处理的原因是，网页上的很多信息实际上与网页的主题毫无关系，比如广告，我们称这些为噪音信息。如果不把这些噪音信息去除则会影响到最后的查询质量。止

9、匕外，很多网页之间在排版，字体等方面虽不一样，但正文的内容却是相同的，如是让它们都出现在查询结果中显然是多余的，必须去掉一个。还有一些无内容的垃圾网页，作弊网页，也必须在这个阶段消除掉。.建立索引从页面预处理模块得到了净化过的页面，要高效进行查询，还必须对页面建立从关键词到其出现位置的索引。这个索引称为倒排索引，对应的索引文件称为倒排文件。对于索引的建立应该说技术已经很成熟，关键是要定义出良好的索引结构，以支持检索模块对页网进行快速而准确的检索。其次要保证建立索引的速度，才能让新收集到的网页尽快地被查询到，提高搜索引擎的时新性。.网页检索网页检索模块是最终与搜索引擎用户交互的模块。系统根据用户

10、提供的查询，从建立好索引的网页库中找到与查询最相关的页面，根据相关度及网页的重要性计算出一个综合的得分，把得分最高的网页按顺序返回给用户。可以说，网页检索方面还有很多问题需要研究，包括：查询与网页相关度的计算，这直接影响查询结果的排序；查询的响应时间和系统吐吞率，一个大型的搜索引擎瞬间之内就会有大量用户发出请求，面对这么多用户，如何以最快的速度响应，如果提高一段时间内可处理的最大查询个数，是现代搜索引擎面临的一个重要问题；检索系统的可扩展性和容错性也尤为重要，检索是搜索引擎中对硬件需求最大的部分，往往是几百台甚至上万台计算机协同工作，这么多的计算机如何协调，在部分机器出现故障的时候如何让系统继

11、续工作，也是一个研究领域。除了这上述的几个基本模块，现代的搜索引擎还包含其它的一些功能。例如网页重要性的计算，网页的自动分类等。总之，搜索引擎的研究还远远没有到尽头，搜索引擎离它最终的目标还很远。本文将着重研究搜索引擎检索模块中的检索效率问题，同时也会涉及索引与相关度计算等方面。倒排文件倒排文件由搜索引擎的索引模块生成，并被检索模块所使用。前面提到，倒排文件是从关键词到其出现位置(occurrence)的一种索引。对于搜索引擎来说，关键词的出现位置信息必须包括出现关键词的文档列表，以及关键词在各文档内的位置列表。一般而言倒排文件由索引文件和记录文件组成，索引文件每个记录包含一个关键词和一个指针

12、，该指针指向记录文件中存放关键词信息的位置。大致结构如下图所示：索引文件记录文件图1.1倒排文件利用倒排文件，检索系统可以快速的找到查询词对应的文档列表。对由多个关键词所组成的查询，还可以根据各个词在各个文档中出现的位置，来计算查询与文档的相关度。倒排索引是迄今为止发现的用于搜索引擎最好的索引结构，既方便建立，又很好的支持各种查询操作。在实际应用中的倒排文件远比上图的复杂：为了更好的计算相关度，倒排文件中还要加入其它的一些信息，例如关键词在文档中的属性信息；为了提高检索效率，可能要调整倒排文件的结构，例如先存放出现关键词的所有文档列表，再存放所有的位置信息，把上图中位置信息的形式：<do

13、c1><pos1pos2Pos3><doc2><pos1'pos2'pos3'><doc3><pos1'pbs2'pos3'，>变换为：<doc1doc2doc3><pos1pos2Pos3pos1'pos2'pos3'pos1'p'os2'pos3''>通过这种变换，当我们不关心词在文档中位置列表的时候，就可以一次地读入词对应的文档列表，减少对外存的访问次数。在后面我们还将详细讨论倒排文件的设

14、计，我们会发现倒排文件结构的好坏直接影响检索速度。检索系统分布式结构现代搜索引擎搜索的网页都数量巨大，目前的北大天网e.pku搜索引擎搜索的网页量就有1.2亿，而一般的商业搜索引擎搜索的网页量至少都有数亿，甚至是达到数十亿。在这种情况下，一个单机的检索系统显然无法处理每秒成百上千的用户查询请求。此时，设计出一个结构良好的分布式检索系统显得尤为重要。一般成言，分布式检索系统至少包括两个部分：一台或多台用于接收入用户查询请求的前台服务器，和多个用于实际数据检索的后台服务器。具结构如下图所示:后台检索机群图1.2检索系统分布式结构当用户在搜索框中填入一个查询，点击搜索按钮，其查询就被随机的发送到任意

15、一台前台服务器上。而前台服务器实际上并不保存网页的索引信息，它将用户的查询通过广播的方式发送到后台的检索机群上。后台检索机群中，每台机器中都存放有部分网页的倒排索引，当它收入到广播过来的查询，便在其索引中查找出与查询其关的网页，并根据一定的相关度算法计算出得分，把相关度最高的若干个网页的文档号与得分一起发送回前台的服务器。前台服务器收集几个检索机器上的结果，按得分归并后把最相关的网页返回给用户。由于时间的关系本文必没有详细的研究检索系统的分布式结构，而是更多的关注各个检索节点上的效率。可以说，这两方面共同决定了一个检索系统的性能。现有系统的不足与本文的主要贡献现有的天网检索系统，是从天网1.0

16、开始，经过不断的完善和发展起来的。在几年里为老师和同学们的科研工作提供了一个重要的平台。但它还存在了一些问题需要我们去改善。例如以下几个方面：.检索效率不高。每个检索节点检索的网页量大约在二百多万，每秒只能处理十几个的查询请求。主要原因是没有为倒排文件建立cache每次查询都要多次访问外存，磁盘成了系统的瓶颈。止匕外，其分布式结构也不太好，前台服务器与检索节之间基于同步的多进程的交互方式，也影响和整个系统的效率。.倒排文件信息量不够。现在的倒排文件中，关键词在文档中的属性信息很少，只用两个bit分别表示词是否在网页title和摘要中，并且不能为关键词在文档中各个位置设立属性信息。由于信息量的缺

17、乏，在计算词与文档相关性的时候，往往不够准确。.系统的可扩展性和容错性不足。系统现在运行在由一台前台服务器，19个检索节点构成的分布式环境中。对于增加检索节点可能带来的广播风爆，以及增加前台服务器查询策略的变化，都没有考虑到。此外，数据没有冗余，当系统中部分机器出现故障，则会影响查询结果。本文针对检索效率的问题进行了研究。设计出来更加良好的倒排文件结构，改进整数压缩算法，并增加倒排文件的信息量。通过有效的cache策略，让索引尽量的在内存中可以找到，减少访问磁盘的开销。通过一些有效的预处理，减少了浮点运算的次数，也进一步的提高了检索效率。对于相关度计算，本文也做了一些改进，使得在最后的结果排序

18、上更符合用户需求。止匕外，一个具有良好程序结构的可用系统，也很好的支持了文中提出的观点。在以下章节中，我们将详细的分析整个系统的设计与实现，以及设计背后的理论基础。第2章倒排文件设计基本原则前面提到过倒排文件的作用和基本结构，在新的系统中，为了让应用程序进行高效检索，并改进结果的排序，我们设计了新的倒排文件结构。在系统的开发过程中，这个结构被修改了很多次，每个设计都各有利弊，最终确定的结构也不是在各方面都最优。但倒排文件的设计都必须遵循几个基本的原则：文件必须是没有二义性，可以正确的还原出数据。例如当我们保存记录<doc1><pos1pos2><doc2>&

19、lt;pos1pos2'>,在读取的时候就无法确定<doc2>处保存的是出现该关键词的新的一个文档号，还是该关键词在docl中的下一个出现位置。因此必须多保存一个词频信息，例如<doc1><tf1><pos1pos2><doc2><tf2><pos1'pos2'>°tf1和tf2分别表示词在docl和doc2中的出现次数。这样才可正确的还原出信息。文件的规模应当尽量小，记录文件中每条记录应该占用尽可能小的空间，以减少读取记录时传输的数据量。方法是进行索引压缩Scholer

20、,etal.,2002：使用变长的整数编码，用较少的空间保存较小的整数；整数使用差值存放，例如把文档号按升序排列，第一个文档号保存实际值，之后的都保存与前一个文档号的差值。关键词在文档中的位置也用类似的保存方法。差值表示法的另一个好处就是可以更方便的求多个文档列表的交集，并且更方便的计算多个关键词在同一文档中的相对位置，在后面我们还会介绍。虽然对索引进行压缩会带来额外的数据解压开销，但相对于它带来的好处，这种开销完全是值得的。索引压缩减少了读取数据时从磁盘传输的数据量，但在检索时平均每个查询对磁盘的访问次数，更大的影响了检索效率。因此，设计倒排文件时，应当支持程序在最少次数内读取到需要的信息。

21、例如在上一章中提到的，把文档列表连续的保存。倒排文件的设计还必须考虑方便索引模块的建立，以及方便检索模块的操作，因此结构不应该太复杂。例如，在设计过程中参考了文献彭波,2003中的倒排文件分块组织技术，把文档根据属性的不同分块保存。表面上看查询时可以先读重要的文档列表，但在实现过程中却发现对于多个关键词组成的查询，操作起来异常的复杂，最终不得不放弃整数压缩编码方法变长的整数编码可分为两类，字节对齐整数编码和非字节对齐整数编码。前者优势有较高的压缩比率，后者则有更高的压缩与解压效率。文献彭波,2003认为，在搜索引擎的应用中，检索效率比索引数据占用的空间更为重要。文中对比了字节对齐编码ByteC

22、ode和非字节对齐编码GolombWitten,etal.,1994,其压缩比率分别为0.3359和0.2635,解码时间比为1:6。目前天网系统中使用的ByteCode编码在文献赵江华,2002中有描述，它可对数值从0至230-1的正整数进行压缩编码。用第一个字节的最高两位表示整数所占的字节数，则1字节的压缩整数包含6个有效位，可表示整数0至63;2字节的压缩整数包含14个有效位，表示整数范围从64至214-1。3字节可表示从214至222-1,4字节可表示从222至230-1。在新的系统设计依然使用字节对齐的整数编码方式，用ByteCodeEx表示，但与ByteCode不同，ByteCod

23、eEx使用了可变长的位数来表示压缩整数的所占字节数，并且根据计算机的字节序(ByteOrder)使用不相同的编码方式，加快解码速度。以BigEndian的字节序为例，第一字节的最高位开始，如果连续n个位为1,则表示压缩整数长度为n+1个字节，有效位从第一个为0的位开始。例如第一个字节110001101,从最高位开始连续出现2个1,则说明整数占3个字节；又例如第一个字节01100101,最高一位就是0,说明整数占1个字节，该整数为的值为99。由此我们可以得出，m个字节的压缩整数可表示的整数最大值为28xm"(m-2)-1o这种方法比ByteCode的优势是只需一个字节就可表示从0至12

24、7,对于小整数占多数的倒排文件来说，压缩率比较高，可以为每个从64至127的整数节省去一个字节的空间。但当整数的范围从221到222-1时，则会多占用一个字节。ByteCodeEx可扩展到无限大的正整数。以下是为2576933个文档建立倒排索引，对整数的使用情况统计：表2.1整数统Ih整数范围06364127128216-1216221-1221222-1>222出现次数2,822,189,488245,763,9511,191,448,54421,135,917206,38929ByteCode字节数122334ByteCodeEx字节数112344可以算出，用ByteCodeEx方法

25、节省了倒排文件的空间45763951-206389245MB，整数的压缩率为0.3221,比起ByteCode有不小的提高。对于LittleEndian的计算机系统，编码方式略有不同，表示压缩整数长度的位从第一个字节的最低位开始，并且也先存放低字节。这样做是为了提高编码和解码的效率。系统使用的倒排文件结构定义新系统的倒排文件由描述文件，索引文件和记录文件组成，下面分别对它们进行定义。描述文件描述文件记录了倒排文件自身的属性信息。可用BNF表示如下:des-file=(attributeCRLF)*CRLFattribute=namevaluename=1*<anyCHARexceptCT

26、LsorseparatorsCTLs=<octets031and127>separators(r'|<”|>"|"|：”|""|v”>i门rr门?”|=t'广't飞value=*<anyoctetexceptCTLs>CRLF=Rn”也就是说，描述文件包括零个或多个<属性名：属性值>的行，最后以一个空行为结尾。这与HTTP协议RFC2616中消息头的定义类似。现在已定义的属性有：Byte-Order属性：表示倒排文件中使用整数的字节序，包含压缩整数和非压缩整数。如果我们使用统一

27、的节字序，如BigEndian,那么在UttleEndian的机器上使用倒排文件则需要进行字节的交换，影响效率。所以我们允许自定义倒排文件的字节序。Byte-Order的属性值可以是Big-Endian或Little-Endian。默认值为Big-Endian。Align-Bits属性：前面说过，索引文件中保存的是关键词和其位置信息在记录文件中的偏移量。为了节省空间(主要是节省应用程序内存开销)，我们在这个文件格式中，使用了32位的偏移量。但是32位的偏移量最多可以表示4GB的空间，而当文档的数量比较多，记录文件的大小肯定是要超过4GB的。因此，这个格式中允许让记录文件中每个记录在某个边界上对

28、齐，也就是说，让每个记录偏移量的低若干位总是0,在索引文件中只保存高32位，再通过移位来获得记录的实际偏移量。Align-bits属性就是表示移动的位数，默认为0位。由于要让记录在边界上对齐，势必引起一些空间的浪费。我们假设，Align-bits为n,倒排文件总关键词数为m。则记录文件的大小应该在4GX2n-1到4Gx2n之间(如果小于前者，则Align-bits等于n-1就足够了)，平均每条记录的空间浪费是2n-1-1字节，于是，整个倒排文件中，浪费的空间总数为mx(2n-1-1)字节。浪费的空间最大可能比例为mX(2n-1-1)/4GX2n-1<m/4G。在实际应用中，m一般不超过5

29、00万，由此可算出，这个比例不会超过0.125%。Attr-Size属性：在这个格式中，允许关键词在每个出现它的文档中，有0个或多个字节的属性信息，例如term-><doc1><attr1><doc2><attr2><doc3><attr3>。这个属性信息的意义在本格式中无定义，完全由应用程序决定。但规定属性信息必须是整字节的，并且所有的属性信息必须等长。这个长度就是倒排文件的Attr-size属性。如果未标明，默认为0。Uint-Encoding属性：压缩整数的编码方式。格式中有规定哪些整数是必须压缩(如文档号)，

30、哪些是整数必须是非压缩(如记录信息偏移量)，但没有规定使用的压缩编码算法，应用程序可自行定义。Uint-Encoding属性默认为上节描述的ByteCodeEx。索引文件索引文件的结构比较简单，文件头用4个字节的非压缩整数表示索引文件中总的关键词量，之后连续存放记录。用BNF8示如下：idx-file=term_cntterm_info*term_info=term_lentermoffsetdoclist_lenterm_len=<1字节无符号整数>term=*<anyoctet>offset=<4字节无符号整数>doclist_len=<压缩整数&

31、gt;可以看出，每个t己录由<term_len><term><offset><doclist_len>组成，分别表示关键词长度，关键词(长度为term_len),关键词的出现位置信息在记录文件中的偏移量，以及关键词对应文档列表的字节长度。当我们要获得某个关键词的文档列表，首先获得关键词上述索引信息，把记录文件的文件指针移动到对应位置，再调用读操作，例如：lseeko(fd,(u_int64_t)offset<<align_bits,SEEK_SET);n=read(fd,buf,doclist_len);记录文件的文档列表信息中，包含

32、了各文档号以及关键词在各文档中的属性信息，但不包含关键词在各文档中的位置列表信息。对于单个关键词的查询来说，位置列表信息没有必要读取，上面的信息已经足够计算相关度了。也就是说，对于单个关键词的查询，一次读操作就足够了。记录文件记录文件是整个倒排文件中最重要，也是最复杂的部分。用BNF表示如下:recd-file=(occurpadding)*occur=doclistposinfodoclist=dfdoc*doc=docidattrposlistlenposinfo=poslist*poslist=tfpos*df,docid,poslistlen,tf,pos=<压缩正整数>p

33、adding=<占位的字节，使记录大小总是2ali9kbits的整倍数>attr=<长度为attr-size字节的用>由BNFW见，每个记录由文档列表信息（doclist）和在文档中的位置信息（posinfo）组成，doclist的开始位置用一个压缩整数保存了doclist中文档的个数，也就是词的文档频率（df）,之后连续保存每个文档（doc）的信息，包括文档号（docid）,关键词在文档中的属性（attr）和关键词在本文档中位置列表的字节长度（poslistlen）,docid使用差值存放。posinfo由df个位置列表（poslist）所组成，依次对应每一个文档。每

34、个poslist开始位置存放了关键词在该文档中的出现次数，即词频（tf）,接下来用差值的形式连续存放各个位置（pos）。记录文件和索引文件的示意图如图2.1所示（align-bits=3）。可以看出，记录文件中每个记录里又包含了一级的索引，这个索引是从文档号到位置列表。但是从BNF中发现，我们只保存了每个文档的位置列表的长度，并没有保存位置列表在记录文件中的实现位置，那么我们得到一个docid之后，如何读取到位置列表呢？这就与我们对文档列表的访问方式有关。我们看到，<docid><attr><len>这个记录中，只有attr是定长的，其它两个都是变长整数，因

35、此我们是不可能对文档列表进行随机访问的，只能顺序地读取。在搜索引擎的检索系统中，这种访问模式已经足够了。从图中我们又可以看出，所有的文档列表和位置列表都是连续存放的，所以，当我们读取文档列表的时候，只需把位置列表的长度累加起来，就可以得到下一个位置列表的相对于文档列表末尾的偏移。例如，第n个文档的位置列表，在文件中的实际位置为：n-1alignbitsoffsetx2一+doclist_len+工poslist_lenii=1其中，offset和doclist_len都是从索引文件中获得。这样的设计使程序在读取倒排文件的过程中，必须多保留一些信息，并增加了一些计算上的开销，但offset1=X

36、XXXoffset2=YYYY由此带来的好处是减少了对空间的占用，这也就减少了读取磁盘的开销，同时可能减少应用程序cache的空间开销。这个交换完全是值得的。<term_len1><termn1><doclist_len1><offset1><term_len2><termn2><doclist_len2><offset2>索引文件XXXX000<df><docid1><attr1><len1><docid2><attr2>&l

37、t;len2><tf1><pos1><pos2><pos3>tf2><pos1'><pos2'><pos3'>tf3><pos1'><pos2'><pos3'><padding>YYYY000<df'><docid1'><attr1'><len1'><docid2'><attr2'>

38、;<len2'>tf1'><pos1><pos2><pos3>tf2'><pos1'><pos2'><pos3'>tf3'><pos1'><pos2'><pos3'><padding>ZZZZ000记录文件图2.1记录文件和索引文件的示意第3章底层数据组织影响检索效率的主要因素首先，我们有必要先了解一下一个查询被执行的过程。如图1.2所示，当前台服务器通过广播的方式把

39、查询发送到检索节点上，检索节点首先对查询进行预处理，例如切词，如果支持布尔查询还必须对查询表达式进行分析生成一棵查询语法树。得到一系列的关键词之后，检索系统分别从倒排索引中找出各个关键词所对应的文档列表。一般而言，搜索引擎返回的各文档里都包含每个查询关键词，于是我们必须对获得到的文档列表求交集，查询的结果必然就落在这个交集里。接着对交集里的每一个文档，我们首先计算每个关键词与文档的相关度得分，再累加起来。这时候我们还没有利用到词在文档中的位置信息。例如我们的查询是“北京大学”，并且被切为“北京”和“大学”两个关键词，那么，交集中这两个词连续出现的文档显然相关度更高一些。此时我们就要利用到关键词

40、在文档中的位置信息，对于那些连续出现这两个词的文档，再增加一些相对位置的得分。在算得每个文档与查询的相关度得分之后，我们还不能直接把排好序的结果返回给用户，因为结果中很多的文档都是在同一个站点之下的，对用户来说可能每个站点只需一个结果就够了，如果有需要可以再点击站内查询。于是，我们还需要根据站点对结果集进行聚类，每个站点内只保留一个或两个结果，把最重要的一些结果连同相关度得分返回给前台服务器。前台服务器收集到各检索节点发来的结果，进行归并再把得分最高的返回给搜索引擎用户。本文现在只关心检索节点做的事情，其中切词与检索效率关系不大，我们也不讨论。其它的包含以下五个部分：.获取文档列表从倒排文件的

41、结构中我们可以看出，要获得给定关键词的文档列表，首先要从索引文件中找到对应的入口，得到offset和doclist_len之后再到记录文件中读取文档列表信息。显然，从索引文件头开始顺序查找关键词是不现实的，与原有天网系统相同，我们把term-><offset,doclist_len>这个索引信息常驻内存。而对于记录文件中的文档列表信息，要让它们都常驻内存似乎就有一些困难了。但根据文献王建勇等,2001,Saraiva,etal.,2001,用户查询词的分布具有很强的局部性，大多数经常被检索的词都是集中在一个很小的范围之内的。另外，该文献还提到，用户查询有一定的稳定性，用户在一

42、段时间内发出的查询往往有一些相似。这两方面说明了对倒排文件使用cache的有效性，通过良好的cache结构，让尽可能多的查询词在内存中找到对应的文档列表，减少访问磁盘的开销，正是本系统中提高检索效率的一个重要方法。.文档列表求交集前面提到，从倒排索引中获得的文档列表一定是按文档号升序排列的，这就为我们求文档列表的交集带来了很多方便。新系统中，求文档交集的算法也有一些改进，由原来的每次两列进行求交，改为多列同时求交。但实验说明这一步操作并非影响检索效率的关键。.计算关键词与文档相关度对各个关键词和文档求相关度得分是检索过程中使用CPU最多的一个步骤，主要是浮点运算的操作。例如使用传统的tf*id

43、f的计算方法，每个关键词相对于每篇文档，都至少要进行3次的取对数运算。虽然在检索系统中，对外存的访问时间是决定系统性能的关键，但如果可以节省相关度计算的时间，也可以在一定的程度上提高检索效率。.计算相对位置对于由多个关键词组成的查询，计算它们相对位置应该说是整个检索过程最耗时的部分。特别是当关键词都是高频词的时候，文档列表的交集中的文档个数可能达到上百万个。此时读取每个词在每个文档中的位置信息，如果不进行特别处理，则要进行上百万次的读盘操作。如果对关键词在文档中的位置信息进行cache其消耗的内存要比文档列表大得多。因此，提高计算相对位置的效率也是改善系统整体性能的关键。.站点聚类站点聚类不涉

44、及对磁盘的操作，其效率并不会构成系统的瓶颈。但新的系统还是改进了原有的算法，通过先聚类后排序的方式，减少了最终进行排序的文档量，从时间复杂度上对性能进行了优化。在这一章里，我们主要讨论的是系统最底层的数据组织。这个模块为上层的模块提供了一个快速的访问索引文件的接口，同时它负责对文档列表和位置列表的cache进行组织。我们将以模块的接口为主线来分析其数据组织。创建索引要访问索引文件首先必须创建一个索引对象(index),其接口如下：index_t*createindex(constchar*desfile,constchar*idxfile,constchar*datafile,size_tca

45、che_max);前三个参数分别是描述文件，索引文件和记录文件的文件名，最后一个参数cache_max为index对象可用的文档列表cache最大值，必须根据硬件条件来确定。在index.c文件中我们可以看到如下的定义：typedefstruct_indexindex_t;struct_indexintdatafd;unsignedintalign_bits;size_tattr_size;size_tterm_cnt;struct_term_entry*term_list;mbuf_t*mbuf;structlist_headdoc_list;size_tcache_max;size_tca

46、che_size;当createindex被调用时，描述文件和索引文件中的内容被一次地读入内存，索引文件中的索引信息被保存在term_list域中，按照关键词开存排列，在查找时使用二分查找的方式。与原有系统使用散列查找的方法有所不同。原因是，使用散列将引起太多的内存浪费。可以大致的计算一下，假设总的关键词数为m,散列的空间至少需要3m,则至少浪费2m个指针的空间。而且每个关键词入口还至少需要一个指针来解决散列函数的冲突，于是总的多余指针开销达到3m个。假设m等于500万，则浪费的总字节数为3X500万X系统地址长度，在32位系统下大约为60MB。而由于关键词都已经一次性读入内存，对关键词的查找

47、所占用的时间几乎可以乎略不计，在认真考虑之后系统使用了二分的查找方式。关键词列表在内存中的组织如下图：index图3.1关键词列表关键词列表是一个指针的数组，各指针指向的内存块中保存的关键词信息。但从图中我们可以看出，这些内存块的长度并不一样，这是为了尽量节省内存的开销而使用了变长结构，这个结构的定义如下：struct_term_entry(union(struct_doc_list_head*doc_list;unsignedintoffset;unsignedintpos_info_size:8;unsignedintterm_len:8;charterm1;)；最后一个域term为关键词

48、的原文，term_len表示关键词长度。在关键词之后还有一个变长整数记录了关键词所对应的文档列表信息的长度，从结构的定义上看不到。在为每个term_entry分配内存之前都必须精确计算出它所需的字节数。如果最后一个域定义为char*term,则平均每个结构会增加3个指针的额外开销。offset域保存了关键词文档列表信息在记录文件中的偏移，这个域与doc_list域共用一个内存单元，如果该关键词的文档列表在cache中，则doc_list域指向cache中的文档列表。但我们并没有看到结构中用来标识文档列表是否在cache中的域，这是因为这个标志被存放在term_list指针数组每个指针的最低位。

49、在使用内存分配函数(如malloc)获得内存时，得到的内存至少是与计算机系统的字长对齐的，最低两个位必然是0,这两个位可以被用来保存一些信息。除了最低位用来标识文档列表是否被cache,次低位也被利用，它被用来标识pos_info_size域的计数单位(粒度)。pos_info_size域保存的是关键词所有位置列表信息的总长度，指针次低位用于标识这个长度是以16字节为单位还是以4K字节为单位。由于指针中一些位被程序所利用，因此需要一次转换来获得实际地址，例如：#defineDOC_LIST_MASK#definePOS_INFO_MASK#defineMASK_ALL#defineTERM_E

50、NTRY(ptr)1UL2UL(DOC_LIST_MASK|POS_INFO_MASK)(struct_term_entry*)(*(unsignedlong*)(ptr)&MASK_ALL)此外为了避免动态内存管理而引起的平均两个指针额外内存开销，在为term_entry分配内存时并不是直接调用malloc函数，而是通过一个专门设计的类(mbuf)来负责内存分配。该对象可把额外开销降至几乎为零，但必须保证后申请的内存先被释放。使用完index对象，必须调用destroyindex函数将对象释放。函数原型为:voiddestroyindex(index_t*index);3.3获得文档

51、列表接口与数据组织创建了index对象，要得到关键词对应的文档列表，首先要获得文档列表对象，其调用是：doclist_t*getdoclist(constchar*term,size_tlen,index_t*index);第一参数term为关键词，根据索引文件的格式定义可以包含任意字符；len表示关键词的长度；index参数为createindex函数生成的索引对象。getdoclist函数首先从index->term_list找到对应的term_entry,如果该关键词的文档列表不在cache中，则把它从记录文件读到cache,如果cache已经达到最大值还要淘汰掉那些最久没有被访问

52、到的文档列表。下图是文档列表在cache中的组织：indexdoclistcache图3.2文档列表的cache组织我们看看每个文档列表cache的结构:struct_doc_list_cache(structlist_headIru;size_tstruct_size;struct_term_entry*entry;unsignedintoffset;chardoc_list1;);所有文本3列表cache通过lru域以链表的形式组织，由于这也是一个变长结构，因此我们用struct_size来记录下结构实际占用的空间，用于统计当前总的cache使用量。entry指回termlist中对应的位

53、置，以便当cache被淘汰时把最低位清0。offset域取自对应的termentry,因为当文档列表被读入cache时,termentry中的offset域被doc_list指针所覆盖，当cache被换出时要把它恢复。这么做的目也是为了节省内存的占用。doclist对象内有一个指针，当对象被创建时，它指向了cache中的对应文档列表开始位置。文档列表的cache使用LRU的淘汰策略，当cache被一个doclist对象引用时，还要把它移到链表的最前端。cache中的文档列表数据以压缩的形式存放。止匕外，在上一节中我们提到，每个termentry中有一个域用于保存关键词位置信息总长度，并且有16

54、字节或4K字节现两种粒度。当把文档列表从外存读到cache中的时候，如果发现其粒度为16字节，也就是说位置列表信息的总长度不超16X255字节，则会把关键词在各文档中的位置列表信息一起读入内存(根据倒排文件的格式，位置信息紧跟着文档列表信息存放)。这样当程序需要读取关键词的在各文档中的位置列表时，无需再进行磁盘的读取操作。在获得文档列表对象之后，可调用readdoclist函数读取到文档列表中的信息：size_treaddoclist(structdoc_entry*docs,size_tn,doclist_t*doclist);该函数从doclist对象中读出n个文档，并把doclist的内

55、部指针向前移动，这类似于文件系统的read操作。但与文件系统不同，doclist不存在类似lseek的操作，这是因为cache中数据都是压缩的，只能顺序访问。在index.h中有doc_entry结构的定义：structdoc_entry(unsignedintdocid;constchar*attr;unsignedint_offset;unsignedint_len;)；前两个域分别为文档号与关键词在文档中的属性,调用者可直接使用。_len域记录了关键词在文档中位置信息的长度，_offset域是该文档之前所有文档_len域的总和。在2.3.3节中我们提到过，可用于计算位置列表信息在记录文件

56、中的位置。函数的调用者并不需要直接访问这两个域，但它们在获取位置列表的时候有作用。使用完doclist对象之后，需调用函数freedoclist将对象释放：voidfreedoclist(doclist_t*doclist);3.3.2性能测试卜面我们对cache的性能进行测试。我们选用了天网查询日志中的20000个查询记录，测试的文档集合约250万文档，倒排文件中，attr_size=2我们先看看cache命中率随着cache大小的变化:T一字节命中率T一文档列表命中率可以看出，当cache最大值为500MB时，就有超过85%的字节命中率，这个数字似乎很激动人心。但是另一组实验数据却很出乎意

57、料，下图是cache大小和查询响应时间的变化关系(测试中没有计算关键词在文档中的相对位置，且所有请求串行发送)：查询响应时间(ms)图3.4cache大小对查询响应时间的影响可以说这个结果很让人失望，我们发现虽然cache命中率越来越高，但对查询的响应是时间却没有什么影响，甚至有变慢的趋势。分析其原因：操作系统自身有cache机制，操作系统会把当前所有可用的内存用作文件系统cache,以减少对磁盘的真正访问次数，提高IO速度。由于文件系统cache的存在，我们对文档列表cache#用也就很不明显了。但这似乎还不能说明问题，因为我们根据自己的需要组织cache,性能应该会比文件系统cache更好

58、一点。于是我们又把cache最大值调到1500MB,发现系统性能急剧下降。经过分析，认为是索引系统的某些页面被换出引起。由于文件系统cache的需要，把用户程序的一些物理内存页面交换到虚拟内存，当这些页面再次需要使用时又被换入，使得磁盘IO开销很大。现在，我们换一个实验环境来试试，我们选用一台有16GB内存的计算机，以确保无需用到虚拟内存，其结果如下：r查询响应时间（ms）图3.5cache大小对查询响应时间的影响（系统内存16GB）可以看出在这种情况下cache确实起了一定的作用，但由于文件系统同样有cache的原因，因此效果并不明显。我们回到那台2GB内存的机器，并把文件系统cache禁用

59、AndreaArcangeli,2001（在打开文件时使用O_DIRECT标志）,在这种方式下，数据通过DMA方式直接从磁盘传送到用户空间的内存，无需经过内核空间的交换，减少了内存的重制次数。再做一次实验，结果如下：10图3.6cache大小对查询响应时间的影响（关闭文件系cache)此时cache的作用就比较明显了，并且，当cache大小为1GB的时候，响应时间比图3.4中任何一个都要快。虽然说使用1GB的内存用于文档列表cache可能不太值得，但至少说明，我们可以通过自己组织cache的方式，绕开文件系统cache来提高检索的性能。由于在读取以O_DIRECT方式打开的文件时，缓冲区内存，传输的数据长度和文件偏移量都必须是页面对齐（Linux内核2.6之后只要求512字节对齐），导致实际读取的数据要多一点。因此如果要设计一个这种方式的检索系统，可以考虑记录文件和cache都以固定大小的块形式组织