大规模超文本网络搜索引擎剖析

1、大规模超文本网络搜索引擎剖析SergeyBrinandLarrypage概述在这篇文章中，我们介绍Google,一个大规模搜索引擎的原型。Google被设计成未可以进行有效的网络抓取和索引并返回比现行系统更加让人满意的搜索结果。我们的这个原型包括索引了2千4百万页面的全文本和超链接的数据库，你可以通过来进行访问。对于一个计算机工程师来说，建立一个搜索引擎可以说是一项具有挑战性的任务，因为搜索引擎索引成百上千万页面的同时也涉及到了相同数量级别的关键词(Terms)。并且每天要回答超过1千万个查询请求。虽然，在当今网络中，搜索引擎的重要程度正越来

2、越突出的显现出来，但是真正学术上的相关研究却很少。而且，随着科技的飞速发展和网络规模的不断扩大，在今天建立一个搜索已经和三年前大不相同了。这篇论文提供了关于如何创建一个大规模搜索引擎的深层次描述，这也是到目前为止我们所知道的第一篇在这一领域的论文。除了一些传统的数据级别相同的搜索引擎的技术，还有一些新的运用在超文本中旨在创建更为优化的搜索结果的技术。如何建立一个可以深度挖掘利用超文本中信息的大规模搜索引擎？这是本文提出的一个问题。同时，我们关注的另外一个问题是：对于那些不受传统格式限制的超文本，我们如何来进行处理？关键词：万维网(WorldWideWeb),搜索引擎(SearchEngines

3、),信息检索(InformationRetrieval),PageRank,Google1 .介绍网络(Web)给信息检索领域带来了新的挑战。就像飞速增长的对Web搜索毫无经验的新用户一样，互联网上的信息量也在疾速地扩充。人们习惯于利用网页上的链接结构来进行网上冲浪。通常他们的网上旅程都是从高质量的人工维护索引的网站比如说Yahoo或者搜索引擎开始的。人为维护的列表可以有效地包含一些热点流行的话题但是带来的问题是：建立和维护这样一个引用表上的成本过于昂贵和主观化、难以及时的进行改进、不能包括所有深入的主题。依赖于关键词匹配的自动化搜索引擎通常会返回一些低质量的结果给用户。更加恶劣的是，一些广告

4、商为了吸引用户的眼球，不惜误导这些搜索引擎来返回错误的结果给用户。我们建立了一个能够解决这些现存系统中问题的大规模搜索引擎。这套系统能够利用超文本中的信息来返回高质量的搜索结果给用户。我们把系统取名为Google,这个名称来源于Googol,意思是1后面100个0。这个名字能够更好的反映出我们建立这个系统的目标。1.1 .Web搜索引擎：规模的扩大：1994-2000为了适应互联网络的飞速发展，搜索引擎技术这些年来有了质的飞跃。在1994年，万维网虫(WorldWideWebWorm),作为一个最早期的互联网搜索引擎在当时索引了11万个Web页面和可以访问的Web文档。到了1997年的11月，

5、顶级的搜索引擎(WebCrawler)号称已经索引了1亿个Web文档。可以预见的是，至U2000年，可以索引的Web文档数量将会超过10亿个。与此同时，搜索引擎所要应付的查询请求也在以难以置信的速度增长。1994年的3,4月间，WorldWideWebWorm每天大概接受1500个请求。在1997年的11月，Altavista声称其每天处理约2千万个请求。随着互联网用户和自动请求搜索引擎的系统的增加，到2000年底，一些顶尖搜索引擎很有可能达到日处理2千万个请求的数量级。我们系统的目标是在质量和规模上解决所有由上述趋势所带来的问题。1.2 Google抓取网络建立一个搜索引擎抓取目前的互联网带

6、来了很多挑战，为了能够收集网络文档并保持他们的时效性，一种快速的抓取技术是必须的。存储空间必须被合理利用来存储索引和文档本身；索引系统必须能够有效地处理海量数据；请求必须能够以每秒几百甚至几千次的速度被快速地处理。这些问题随着互联网规模的扩大将会变得越来越困难。然而，硬件性能的改进和成本的降低部分地解决了一些困难。但是，这些硬件的发展也带来了一定程度的副作用。比如说磁盘定位时间和操作系统的健壮性。在设计Google的过程中，我们充分考虑到了互联网增长的速率和技术的变化。Google被设计成可以有效地适应海量的数据集。Google能够有效地利用存储空间来存储索引。为了快速有效地对其数据进行访问，

7、我们优化了它的数据结构。除此以外，我们设想，Google索引和存储文档和Html的消耗将最终减少到一个可以接受的数量级。这将为一个像Google一样的中心化系统带来可观的抓取特性。1.3 设计目标1.3.1 改进的搜索质量我们的主要目的是为了改进Web搜索引擎的质量。在1994年，一些人相信一个完全索引的搜索引擎将能够很容易的为我们找到所需要的内容。根据数据显示，1997年的Web已经大不相同了。这些年来，任何一个使用了搜索引擎的用户都可以去测试并感知索引的完整性并不是用来衡量搜索结果质量的唯一因素。“垃圾结果(JunkResults)"常常将一些用户感兴趣的结果给掩盖了。事实上，在

8、1997年11月，只有4家顶级的商业搜索引擎能够在搜索结果中找到自己(根据输入自己的名称在自己的搜索结果的前10条记录中返回自己)。一个主要原因是索引中文档的数量增加了好几个数量级的同时用户阅读文档的能力却没有相应的增加。人们还是希望能在结果的前面几十个结果文档中就能找到他们所需要的信息。正因为此，随着集合大小的增加，我们需要一个工具来对结果进行精准的定位(将最为相关的文档在结果的前十个中返回)。当然，我们希望我们所说的“相关”是在结果中仅仅包括从上万个轻度相关的文档中返回最好的文档。这种高度查准率(Precision)哪怕是在牺牲查全率(Recall)的条件下都是尤为重要的。最近有很多的利用

9、更多超文本信息的优化措施用来帮助改善搜索和其他应用程序的。特别的，链接结构和链接文本为了做出相关性判断和质量过滤提供了大量有用的信息。Google为了达到目标使用了链接结构和锚定文本(anchortext)1.3.2 理论搜索引擎研究随着时间的变迁，互联网除了飞速增长之外，也变得越来越商业化。在1993年，大概1.5%左右的Web服务器使用的是.Com的域名。这个数字在1997年的时候增长到了60%。与此同时，搜索引擎也从纯粹的理论学院派研究转移到了商业应用上。到目前为止，多数搜索引擎的发展都是由一些公司主导并且很少有相关技术细节的论文发表。这导致了搜索引擎技术被大众认为是一种魔法。我们在设计

10、Google的时候就有一个目标，为了给理论中的相关领域带来更多的发展和认识。另外一个很重要的设计目的是为了能够让更多的人可以实际使用我们的系统。用户的使用对于我们来说是非常重要的，因为我们认为很多有趣的研究都将涉及如何平衡大量数据的使用。例如，每天都有成千上万的搜索。但是，得到这些搜索日志的数据却是非常困难的因为这些数据常常被认为是有商业用途而不会公开的。我们的终极设计目的是创建一个这样的架构：这个架构能够支持很多涉及大数据集的新型研究活动。为了达到这个目的，Google将所有抓取到的文档都已压缩的形式存储了下来。我们设计Google的一个主要目的是建立一个环境：研究人员可以迅速的融入进来，处

11、理网络的大块数据并且得出在其他的环境中很难获得的研究成果。在系统建立的初期，我们已经利用Google的数据库发表了几篇论文，还有许多论文正在进行中。另外一个我们的目的是建立一个类似宇宙空间实验室的环境。在这里，研究员，甚至是学生都可以在我们提供的大规模网络数据集上进行各种各样的有趣的研究计划。2 .系统特征Google的两项重要特性帮助Google返回高查准率的搜索结果。第一，Google利用网络的链接结构来计算每一个Web页面的排名。这种排名叫做PageRank,有关这项技术的细节可以参考Page98.第二，Google利用链接来改进搜索结果。2.1 PageRank：为网络排序网络的引用图

12、是一项非常重要的资源但是却常常被当今的一些搜索引擎忽略了。我们创建了一个包括了5亿1千八百万类似于这样的超链接的地图。这些地图使我们可以快速的计算一个Web页面的PageRank值。PageRank是某个Web页面引用重要性的客观量度。这种重要性与人们主观上关于重要性认识是一致的。正是基于此，PageRank是一种把搜索结果根据Web关键词搜索排序的绝佳途径。对于众多热门的主题，在使用了PageRank对结果进行了排序以后，一个简单的对Web页面标题的严格文本匹配搜索就可以获得绝佳的性能。对于Google系统中的全文搜索而言，PageRank更是起到了重要的作用。2.1.1 PageRank计

13、算描述：学术上的引用文献方法被应用到了Web上，很大程度上被用来计算一个给定页面的被引用的次数和向后链接(backlinks)。这种方法可以给出一个页面重要程度和质量的估计值。PageRank对这种方法进行了延伸：并不是对来自于所有页面的链接进行相等的相加，而是对一个页面上的链接数进行规格化。PageRank定义如下：假设页面A有页面T1TN的指向。参数d作为一个阻尼因子，它的值可以设定为0到1之间。我们通常设为0.85。下一节中我们将有关于d的更多细节。C(A)被定义为页面A指向其他页面的链接个数。页面A的PageRank计算如下：PR(A)=(1-d)+d(PR(T1)/C(T1)+.+P

14、R(Tn)/C(Tn)注意到PageRank在Web页面上组成了一个概率分布。所以我们不难得出所有Web页面的PageRank和为1PageRank可以通过一个简单的迭代算法来进行计算，而且这是符合Web链接规格化矩阵的主特征向量的。同样的，一个关于2千6百万Web页面的PageRank计算可以在一台中等规模的工作站上只用几个小时就计算完成。更多关于PageRank计算的细节超出了本文的讨论范围。2.1.2 直觉地判断PageRank可以被认为是用户习惯的模型。我们假设存在一个“随机冲浪者”，我们随机给他一个Web页面，让他持续的点击其中的链接，我们的冲量者从来不会返回，但是他最终会感到疲倦然

15、后从另外一个随机页面开始新一轮的冲浪。随机冲浪者访问一个页面的概率就是这个页面的PageRank值。而且阻尼系数d值是随机冲浪者在每个页面上感到厌倦选择新的随机页面的概率。一个重要的变化因素是仅仅为一个单独的页面或者一组页面增加d值。这种方式允许个性化并且使得故意误导系统使获得高排名的企图几乎不可能实现。我们对于PageRank还有一些其他的扩充，同样可以参考Page98另外的一种直觉判断是这样的，一个页面如果拥有很高的PageRank那么表明肯定有很多页面指向它。直观地，被互联网上多处引用的页面一定是值得访问的。同样的，如果一个页面仅仅被一个页面引用，但是这个引用页面是类似于Yahoo首页这

16、样的页面，我们认为这样的页面同样是值得去访问的。如果一个页面不具有高质量或者是一个坏链接，通常像Yahoo首页这样的页面是不会有这样的链接的。PageRank通过Web的连接结构递归的传递权值来处理上述的两个问题。2.2 锚定文本链接的文本在我们的搜索引擎中被特殊的处理了，大多数的搜索引擎将链接的文本和该页面联系起来。我们除了进行这些处理以外，我们还把这些文本与链接指向的页面联系了起来。这样做有几个好处。第一，这些文本通常提供了比Web页面本身更加精准的对于页面内容的描述性文字。第二，Anchors描述了一些不能被文本搜索引擎索引的文档，比如说图片，程序，数据库等等。这些信息将有可能返回没有被

17、抓取的Web页面的地址。注意到那些没有被抓取的页面可能带来的问题：因为它们的有效性在返回给用户之前永远不可能得到验证。在这种情况下，搜索引擎很有可能返回一个实际上根本不存在的但却有超链接链接到的页面。然而，通过对结果的排序，这个问题在实际中很少会发生。这种通过锚定文本本身对Web页面进行描述的思想最早在WorldWideWebWorm中得以特别地实现因为它帮助搜索非文本信息并扩展了搜索的覆盖度，提供了少数几种可下载文档的信息。我们使用这种思想主要是因为AnchorText可以帮助提供更好的搜索质量。考虑到大量必须被处理的数据量，有效的利用AnchorText在技术上是十分困难的。在我们目前抓取

18、的2千4百万页面中，我们索引了超过2亿5千9百万的Anchor文本。2.3 其他特征：除了使用PageRank和AnchorText以外，Google还有一些其他的特征。首先，Google纪录了页面中每个元素的位置信息，更增加了对于相似度的搜索。此外，Google可以获取一些可视化表示的细节比如说字体大小。大号或者粗体字被赋予更高的权重。第三，我们将所有的原始Html页面存储了下来。3相关工作互联网上的搜索研究历史短暂而简明。WWWW是第一代搜索引擎中的一个。紧跟其后的是一些学院派搜索引擎，很多现在已经公司化了。同Web的发展和搜索引擎的重要性比起来，很少有关于最近搜索引擎技术的文档。然而，还

19、是有相当一部分关于搜索引擎某一特性的工作在进行中。特别值得一提的是目前搜索引擎中对搜索结果进行预后处理得到最终结果，或者得到一个小规模的个性化搜索引擎。最后，还有相当多的关于信息检索系统领域的研究，特别在受约束集合的范围下，在下两个章节的内容中，我们讨论如何扩展这些领域的研究成果使它们能够在Web环境下工作的更好。4.5 信息检索信息检索系统领域中的工作可以回顾到很多年前而且已经是发展得很好的技术了，然而，所有基于信息检索系统的研究都是在基于很小范围内的同类型受约束集合中。比如说科学文献，关于某一个话题的新闻故事等等。确实，信息检索领域的基准一一文本检索会议使用的很小一部分这类型的文档。对比我

20、们抓取的147GB,2千4百万的Web页面，“海量文集”基准只有大概20GB的信息量。很多在TREC上可以获得很好结果的方法并不能在Web上得以适用。比如说，标准向量空间模型对文档和查询根据其中单词的出现来定义其向量。为的是返回与查询条件最为相近的文档。在Web上，这种方法通常返回非常短小的文档，这些文档通常是查询的关键字加上少许单词。比如说，我们曾看到一个主流的搜索引擎在我们输入“BillClinton”查询时返回了一个只包含一句"BillClintonSucks”和一张图片的页面。一些关于网络上的争论认为，用户需要输入更多的关键词来确定他们需要的结果。我们强烈不同意这个问题。如果

21、用户发起一个"BillClinton”的请求，他们应该是得到合理的结果只要有足够多的高质量关于这个话题的信息。通过这个例子，我们相信，为了能够更好的处理网络上的信息，传统的信息检索工作需要进行扩展。4.6 传统受约束集合于Web的区别Web是一个完全不受约束同类文档的大型集合。Web文档在文档结构本身抑或是外部的元数据中就存在有很多变化。比如说，文档本身语言（不论是在自然语言还是程序语言上），词汇（Email地址，链接，压缩码，电话号码，货物编号），格式类型（文本，HTML,PDF,图片，声音）上都有可能不同，此外，很多文档可能都是机器生成的（日志文件，或者动态的根据数据库生成页面）

22、。另一方面，我们定义外部元数据是那些可以推断文档的信息，但是这些信息并不包含在文档当中。一些关于外部元数据的例子：来源的可靠性，更新频率，质量，受欢迎程度或者使用程度，还有引用。不仅仅是这些元数据的来源可能不同，被度量信息本身可能差别也在几个数量级以上。比如说Yahoo目前每天可以有几千万次的页面浏览，但可能Web上其他的某些晦涩难懂的历史文章每10年才会被访问到一次。显然，这两种情况应该被搜索引擎区别来对待。另外一个Web和传统文档的不同来自于，通常对于用户放置于网络上的信息没有一个约束。4系统剖析首先，我们将提供一个总体的架构讨论，然后，我们将会深入讨论一些重要的数据结构。最后，主要的应用

23、程序：抓取，索引和搜索将被深入的进行探讨。Google的架构Google的整体架构在这一节，我们将讨论如上图所示的Google的总体架构。更多关于数据结构和应用程序的讨论将在后续的章节给出。大部分Google的代码为了提高工作效率都是使用C或者C+写成的，这些代码可以在Solaris或者Linux上面运行。在Google中，Web抓取(WebCrawling)(下载Web页面)是通过多个分布式的抓取器完成的。URL服务器(URLServer)发送待抓取页面的URL给抓取器。收集到的Web页面被送到存储服务器(storeserver),存储服务器(storeserver)压缩并把Web页面存放在

24、知识库(Repository)中。每一个页面都有一个与之联系的ID号叫做DocID。这个ID是在一个页面中新的URL被解析出来的时候分配的。索引(indexing)的功能由索引器(indexer)和排序器(sorter)完成。索引器读取知识库中的页面，解压文档然后对文档进行解析。每一个文档都被转换为一组字词的存在集合我们把这个集合叫做Hits。Hits记录字词，文档中的位置，字体的大小和大小写。索引器将这些hits分配到一组称为“桶”的结构中，并由此创建一个部分排序的前向索引(ForwardIndex)。索引器另外一个重要功能是解析每个页面中的链接并把相关重要的信息存放在锚文件(AnchorF

25、ile)中。这个文件包含足够的信息来确定每一个链接来源与指向以及连接的文本。URL解析器(URLResolver)读取这些锚文件然后将这些相对URL路径转换成为绝对路径并依次分配DocID。URL解析器将AnchorText以及由AnchorText指向的DocID放入前向索引中。同时，URL解析器也产生一个链接的数据库，这个数据库中包含有一组组的DocID。连接数据库用来计算所有文档的PageRank值。排序器(Sorter)使用按照DocID排序的桶来根据WordID的顺序产生倒排索引(InvertedIndex)。一些临时的存储空间需要用来进行此项操作。排序器同时也在倒排索引中产生一组W

26、ordID和偏移量。一个叫做DumpLexion的程序将这些链表与由索引器产生的词典关联起来然后产生一个新的词典供搜索器使用。搜索器在Web服务器上运行并且利用由DumpLexicon产生的词典，倒排索引和PageRank来回答查询。主要数据结构优化了的Google数据结构可以以最小的消耗来处理海量文档的抓取，索引和搜索。虽然CPU和大数据块的输入输出这些年来已经有很大改善，磁盘的定位仍然需要大概10MS的时间才能完成。Google被设计为无论何时总是避免不必要的磁盘定位，这种思想对我们数据结构的设计起了极大的作用。大文件(BigFiles)大文件是由64位整数设定地址的虚拟文件，虚拟文件可以

27、生成多文件系统。这种在多文件系统中的分配工作时自动进行的。大文件包(BigFilesPackage)同时也在操作系统没有足够的文件描述符时，负责文件描述符的分配和回收工作。BigFiles同时也支持原始压缩选项。知识库(Repository)Repository:53.5GB=147.8GBuncompressedsynclengtnsynclenqthcomDressqdpqcketcompiessedpacketPacket(storedcompressedinrepository)Idocidecocfelurllenlpaqelerur|paqe知识库包括了所有页面的HTML代码。每一

28、个页面都使用zlib进行压缩。选择的压缩算法是进行了压缩比和速度折中的。我们选择的Zlib在速度上要远远优于Bzip提供的压缩算法。对比与Zlib3比1的压缩比而言，Bzip的压缩比大约是4比1左右。在知识库中，文档顺次排列并且以DocID,长度和URL作为前缀。具体结构可以查看图2。知识库不需要其他更多的数据结构用来访问。这种结构有利于数据的一致性，同时也使得系统的进一步发展更加容易。我们可以从知识库和抓取器的错误日志中方便的重建其他的所有数据结构。文档索引文档索引用来保存每一个文档的信息。这是一个固定宽度按照DocID排序的索引。每一条记录中存储的信息包括当前文档的状态，指向知识库的指针，

29、文档的校验码和一些统计数据。如果文档被抓取，记录中还会包括一个指向叫做Docinfo变长文件的指针。这个变长文件包括文档的URL和标题。如果该页面还没有被抓取，则该指针仅仅指向包含URL地址的URLList。这种设计是希望得到紧凑数据结构使得查询请求可以仅仅在一次磁盘定位时便可以得到相关记录。此外，还有一个文件用来处理从URL到DocID的转换。这是一个URL校验码的列表包括了每一个URL对应的DocID,并且按照校验码来进行排序。为了找到特定URL的DocID。我们通过计算URL的校验码来对文件进行二叉搜索来找到DocID。同时，我们还能够通过合并实现批量化的URL,DocID转换。这被UR

30、L解析器用来实现URL到DocID的转换。批量化更新模式非常重要，因为如果不这样，我们就需要为每一个连接的转换对磁盘进行一次定位。假设要对3亿2千2百万个连接的数据集进行定位，估计要花上1个月的时间。词典（Lexicon）词典通常有多种形式。一个与之前系统中词典最大的不同是我们设计的词典可以在地消耗的前提下放入到内存中。在目前的实现中，我们可以在一台256主存的机器上把词典文件整个的放入到内存中去。目前的词典包含大约1千4万个关键词。它的实现分为两部分。一组关键词（顺序连接但是以NULL作为分割）和一个哈希表。为了应付不同的功能，这组词还包含有一些其他的信息，这些信息超过了本文的讨论范围。Hi

31、t表一个Hit表对应到一个特定文档中某个存在的关键词的信息。这些信息包括关键词位置，大小写信息，字体。Hits表占用了正向索引和倒排索引绝大部分的存储空间。正因为此，所以如何将这些信息有效的表达出来就显得尤为重要了。我们考虑了几种可供选择对位置，字体和大小写进行编码的方案：简单编码（三个连续整数），紧凑编码（手工优化位处理）和哈夫曼编码。最后我们选择一种优化的紧凑编码，因为这种方式可以有效地节约空间同时也省去了哈夫曼编码对位的繁琐处理。Hits的细节在图3中标明。我们的紧凑编码使用两个字节来处理所有的hit。有两种形式的hit,一种我们叫做奇异hits,一种普通hits。奇异hits包括出现在

32、URL,标题，anchorText或者元标签中的hits。普通Hits包括其余的元素。一个普通的hit包括一位指示大小写，指示字体大小，12位指示关键词在文档中的位置（所有大于4095的位置都被当作4096处理），其余的三位用来指定字体的大小。奇异hit包括一位指示大小写，字体大小为被设置为7的可以用于判断是否为奇异hit。4位用来对奇异hit的类别进行编码，其余八位用来辨明位置。对于anchorhits来说，8位的位置分为4位的位置指示和4位的DocID哈希。只要对于一个特定的关键词不存在过多的anchor,一些有限的短语搜索是可能的。我们期望对我们的方法进行更新使之能够对更多的位置和Doc

33、ID进行编码。我们在hit中使用字体大小因为我们不想对仅仅只是字体大小不同而内容一致的文档排序。Hit标的长度存储在hits的最前面。为了节省空间，hit表的在正向索引中与wordID合并在了一起，在倒排索引中则和DocID合并。在两种索引中的长度分别为8位和5位。如果长度超过了本身可以表示的范围，一个叫做Escape的码值将被设定，在接下来的两个字节中将会包含Hit的实际长度。正向索引（ForwardIndex）正向索引实际已经部分的被排序了。正向索引被存储在一系列的桶中（在我们的系统中，桶的个数为64）.。每一个桶保存一个WordID的范围值。如果一个文档包含包括的某个关键词的wordID

34、正好符合某个特定桶wordID和hits表。的范围，这个文档的DocID将会被记录在桶中。后面是该文档中对应到该桶的关键词的这种模式因为重复的DocID要求比实际值更多的存储空间。但是由于桶的数量比较合理这种存储上的差别不会很大，同时也节省了相当多的时间开销和在后期索引阶段排序时编码的复杂度。此外，我们对每个WordID求出对每个桶最小ID的相对值而不是使用WordID的绝对值。这样一来，我们可以只使用24位来记录在桶中的wordID,剩余的8位留名了hits。Hit:2bytesplain:fancy:anchor:cap;1imp:3position;12cap:1imp=7type:4p

35、osition:8cap:1imp=7type:4hash:4pos:4ForwardBarrels:total43GBIdocidwordid:24nhits:8hithithithitwordid:24nhits:8hithithithitnullwordiddocidwordid:24nhits:8wordid:24nhits:8lithithithitlithithithitwordid:24nhits:8hithithithitnullwordidLexicon:293MBInvertedBarrels:41GBwordidndocs"woF9iUTiroes-wordiU

36、ndocsdocid:27do甄27docid:27docid727n晔;5nhits:5n.ts:5nHts:5nithithithitnithithithithithithitnithit倒排索引(InvertedIndex)WordID,倒排索引除了是由排序器来进行处理以外，桶的结构和正向索引是相同的。对于每一个有效的词典包含一个指向包含WordID的桶的指针。这个指针指向一个包括对应hit表白DDocID的链表。这个文档链表表示所有包含该关键词的文档集合。一个重要的问题是，在文档链表中，DocID究竟应以一种什么样的顺序进行存储？一个简单的解决方案是按照DocID的顺序进行排序。这在多

37、关键词进行求交集的时候有利于对文档链表快速地合并。另外一个选择是根据该关键词在每个文档中的排名来进行排序。这种方法对于处理单关键词查询时显得非常有用但是在多关键词的文档链表的合并过程中就显得异常困难。同样，这种排序方式使系统的进一步发展变得更加困难。因为一旦我们对排序的算法进行修改，我们就必须得重新生成整个倒排索引。我们在这两种方法中作了一个折中：对每一个关键词的文档链表保留两个倒排桶：一个集合中的DocID是那些保存有奇异Hits的集合，另外一个是全部的集合。通过这种方式，我们首先在第一个集合中搜索结果，如果第一个集合中的结果不够再对第二个集合进行搜索。抓取网络运行一个网络抓取器是一项颇具挑

38、战性的任务。网络抓取涉及的问题包括网络作弊和可靠性问题，更加重要的是，可能会涉及到一些社会问题。抓取一个十分脆弱的部分因为这一部分要和成千上万的Web服务器和各种不同类型的服务器打交道，这些服务器都远远超过了系统的控制范围。为了能够抓取上千万数量级的Web页面，Google使用了一个快速的分布式抓取系统。一个单独的URL服务器为多个抓取器（在我们的系统中这个值是3）提供待抓取的URL列表。URL服务器和抓取器都是使用Python语言实现的。为了保证Web页面的抓取保持在一个较高的速度上，每一个抓取器每个时刻都保持有近300个连接。在速度最快时，使用4个抓取器的系统可以每秒抓取超过100个页面差

39、不多600K的数据量。一个主要的性能瓶颈在于DNS查找。每一个抓取器都各自维护一个DNS缓存，所以，抓取器不必在每次抓取页面时都进行DNS查找了。这些连接可能存在众多不同的状态：查找DNS,连接服务器，发送请求，接受响应。这些状态使得抓取器成为系统中一个异常复杂的模块。它使用异步的IO来进行事件处理。然后众多的队列用来进行页面不同状态的转移。事实证明，抓取器连接成千上万个服务器产生的数以万计的日志给我带来了海量的Email和电话访问。因为在这些为数众多的上网者中总是有很大一部分人并不知道Crawler为何物。很有可能这是他们第一次见识到Crawler。几乎每天我们都可以收到这样的电子邮件：“喔

40、，你在我的站点上看了不少页面哦，感觉怎样？”。同样也有些人并不了解RobotExclusionProtocol,并且认为她们的页面应该免于被索引，在他们的页面上常常可以看到这样的句子“这个页面是受版权保护的，请勿索引”。这些文字对于抓取器来说无疑是无从知晓的。同样，因为对大量数据的收集，常常会有一些意想不到的结果。比如说，我们的系统曾经试图抓取一个在线游戏的页面。结果导致大量游戏中的垃圾信息被收集起来。由于Web的各种页面或者服务器上的变化。不可避免会有成千上万个问题隐藏在某个页面中最后导致抓取器的崩溃。更糟糕的是，可能导致抓取器的不可预知和错误的活动。像这些访问大部分互联网的系统一定要设计得

41、更加强壮同时也要细心的进行测试。索引网络解析（parsing）-任意一个用来解析互联网络的解析器必须能够应付大量可能存在的错误。这些错误可能是在Html标签中使用打字稿，可能是在标签的中间包含有上千字节的空字符，可能涉及到非AscII码等等，还有更多的错误在挑战人们的想象力去解决。为了提高速度，我们使用Flex来产生词法分析器而摒弃了YACC来产生CFG解析器。开发这样一个能够高速运行并且高度强壮的解析器需要投入巨大的精力。索引文档入桶一文档解析完成以后，被编码进入不同的桶中。每一个词都通过驻留内存的词典的哈希表被转换为一个WordID。新增的词典哈希项被记录到相关文件上。Word转换为Wor

42、dID以后，他们在每个文档中的值被转换成为响应的Hits表，被写入到正向索引中。同步索引状态的主要难题在于词典文件需要共享。我们通过采用为所有的不在词典中的关键词写入日志到日志文件中来代替词典的共享。这样一来，多个索引器可以并行工作，小的日志文件可以在最后阶段被索引器合并成一个大的索引文件。排序-为了产生倒排索引，排序器将所有的正向桶按照WordID进行排序来为标题和AnchorHits和全部文档创建倒排桶。排序器每次对一个桶进行操作，因此对临时存储空间的需求就很少。同时我们使用多个排序器在排序阶段并行的工作。这些排序器可以在同一时间对不同的桶进行操作。由于桶的大小不能够全部载入内存，排序器根

43、据WordID和DocID将其拆分成多个可以载入到内存中的篮（Basket）。然后排序器装载这些篮排序，比逆光把结果写入到短的和完整的倒排桶中。搜索(Searching)搜索的目标是有效的提供高质量的搜索结果。很多目前大型的商业搜索引擎看上去在效率上有了不少改进。因此，我们将注意力主要集中在对研究对搜索结果的改善上。虽然我们相信通过进一步努力，我们的解决方案可以在商业容量上得以扩展。Google的查询评价显示在图4中。.解析查询.将关键词转换成为WordID.找到每个关键词在短倒排桶的起始位置。.搜索所有的文档链表直到找到所有的符合查询条件的文档.计算文档关于该查询的排名.如果我们是在短倒排桶

44、中，定位每个关键词在完全文档链表中的起始位置返回到步骤4.如果还没有到达文档的结尾。则继续步骤4.对于符合要求的文档进行排序，并返回TopK为了有效地缩短响应时间，一旦符合匹配的文档数量达到一个既定的数量(目前是40000)。搜索器自动的跳到图4的第八步。也就是说可能返回的是一个最优化结果的子集。我们现在正在探索其他更好的方案来解决目前的问题。过去，我们对hits用PageRank进行排序。这种方式看上去改善了不少。排序系统Google维持比传统搜索引擎更多的Web文档的信息。每一个Hit表都包括位置，字体和大小写信息。此外，我们将AnchorText和文档的PageRank作为因此放入hit

45、s中。将所有这些信息都考虑到排序中是相当困难的。我们设计的排序函数不会让某一个特定因子起到太大的影响作用。首先，考虑最简单的情形-单关键词的查询。为了对符合单关键词的文档进行排序。Google查询文档的该关键词的hit值。Google把hit分成几种类型：标题，Anchor,URL,纯文本大字体等等。每种类型有其独有的权重。权重组成了一个由类型索引的向量。Google计算在hit表中每种类型的德数量。然后每一个计算结果都转换成一个计算权重(Count-weight)o计算权重一开始随着计数的增加而线性的增加但是很快的就会逐渐停止，所以一旦超过了一定数目就不再会有用了。我们对计数权重的向量与类型

46、权重向量进行点乘为文档得到一个IR分数。最后，IR的分数和PageRank分数混合起来给文档一个最后的排名情况。对于多关键词查询而言，情况就要复杂许多了。多个hit表必须一次性的扫描完毕，和那些再文档中位置比较远的hits比起来，我们应该对对那些在文档中位置靠近的hits给出更高的分数。对于每一个符合插叙的hits集合来说，我们要对其接近度进行计算。接近度的计算是根据hits在文档中的距离进行，从完全匹配到不相关，我们将其分成10个不同的值。计数并不仅仅根据类别，而且也根据相近度来计算。每一个类别相近度对有一个类别相近度权值。我们对计数和权值进行点乘来获得IR分数。所有这些数字和矩阵可以在调试

47、模式下伴随搜索结果显示出来，这些数字和矩阵地显示对我们的排序系统起到了极大的帮助作用。反馈(Feedback)排序函数有许多参数，比如说类型权值和类型相近度权值，精确的计算这些权值的确切值在某种程度上几乎是不可能的。我们通过在搜索引擎中引入用户反馈机制来达到这个目标。一个值得信赖的用户可能会对所有返回的结果进行评价，这种反馈被储存起来，在我们对排序函数进行修改的时候，我们可以通过反馈得到一些有关因子在先前查询中起到的影响。虽然说这些方式远非理想，但确实给了我们如何改进排序算法可以影响搜索结果5.结果和性能Query:billclintonhttp壮wwwwh口1,15B&051100.

48、00%(nodate)(OK)/Office口fthuPrcidunt(Dec231996)(2K)htrp：//WH/EOP/OP/html/OP_Home.htmlWglc口meToThWhiteH口utc(Nov091997)(5K)http:/www:whitehouseTgov/WH/Wekome.htmlG一-dElect。门icMRItoth。P1白sident(Jul141997)(5K)htrp:/www.whitehouseTgov/WH/Mail/html/MaiLPresident.hi

49、mlmNiltcrprTsidEritwhitE99.98%maiko:PosidentwhituhoL*eqov99.2Thu"Unofficial"BillClinton94.06%M(Nov111997)(14K)EillClint0门Meet/Th20hrk)k&(Jun291997)(63K)l-ittp:/zpubJcom/unZun-bc9.htmlP心iden【BillCimmri-TheD日kSide97.27%(Nov101997)(15K)http:/www.佗白kh</clinton.htm$3BillC

50、Jjnnjn9473%(nodate)(4K)http;/Figure4.SampleResultsfromGoogle衡量搜索引擎性能很重要的一个因素是搜索结果的质量。虽然完整的用户评价已经超出了本文的讨论范围，我们自身关于Google经验表明，Google通常可以产生比当前大多数主流商业搜索引擎更好的搜索结果。为了阐释PageRank,AnchorText和相近度的作用，图4给出了Google的对BillClinton这个查询条件的搜索结果。这些结果显示了Google的一些特性。这些搜索结果是由服务器成群的。这为筛选出合适的结果集起到了很大帮助。很多结果是由W这个

51、域名返回的。这通常是我们所期望的搜索站点。当前，很多主流商业搜索引擎通常不会返回站点的任何结果。注意到第一个结果中没有标题。这是因为这个页面没有被抓取。Google通过AnchorText判断出这是一个对应于查询条件好的回答。同样的，第五个结果是一个Email地址，同样没有被抓取，是凭借AnchorText判断得出的结果。所有的这些结果都是高质量的页面，而且经过最终检测，并不存在死链接。这主要因为结果是根据PageRank排序的。PageRank在这些结果中的权重是条形码中红色部分的百分比。最后，结果中并没有出现只有Bill没有Clinton或者只有Clinton没

52、有Bill的结果。这是因为我们为关键词存在的相近度给了非常高的权值。当然，一个对搜索引擎的真正测试需要更广泛用户的使用和对系统进行测试分析，在这里我们邀请读者访问Google的网站：.存储要求除了搜索质量外，Google要求系统能够对Web的增长在性能消耗上做出适应。其中的一方面就是如何有效地使用存储。表1是一些统计数据的细目分类和Google对存储的要求。由于对文档进行了压缩，知识库的大小已经缩减到了53GB。仅仅是全部存储数据的1/3。对目前硬盘的价格而言，对于存储有用的数据而言这已经是相当便宜的资源了。更加重要的是，搜索引擎所需要总体的数据的存储空间量大概是55GB。此外，许多查询可以仅仅在查找短倒排索引就找到满足要求的结果。通过在文档索引中使用好的编码和压缩技术，高质量的Web搜索引擎可以适应一个带有7GB驱动器的新型PC中。对于一个搜索引擎来说，有效的抓取和索引是非常重要的。因为这样一来我们可以保证最新的信息能够及时地收集到而且系统的主要改动可以相应的进行迅速测试。对于Google而言，主要的操作是抓取，索引和排序。很难准确的测量出进行完整一次抓取需要花费多长时间，因为诸如磁盘装满，命名服务器崩溃，或者其它一些问题都可能使得系统停滞下来。总体而言，下载2千6百万页面大概需要花