本文是谷歌创始人Sergey和Larry在斯坦福大学计算机系读博士时的一篇论文。发表于1997年。在网络中并没有完整的中文译本，现将原文和本人翻译的寥寥几句和网络收集的片段(网友xfygx和雷声大雨点大的无私贡献)整理和综合到一起，翻译时借助了translate.Google.com，因为是技术性的论文，文中有大量的合成的术语和较长的句子，有些进行了意译而非直译。

作为Google辉煌的起始，这篇文章非常有纪念价值，但是文中提到的内容因年代久远，已经和时下最新的技术有了不少差异。但是文中的思想还是有很多借鉴价值。因本人水平有限，对文中内容可能会有理解不当之处，请您查阅英文原版。

大规模的超文本网页搜索引擎的分析

摘要

在本文中我们讨论Google，一个充分利用超文本文件结构进行搜索的大规模搜索引擎的原型。Google可以有效地对网络资源进行爬行搜索和索引，比目前已经存在的系统有更令人满意的搜索结果。该原型的数据库包括2400万页面的全文和之间的链接，可通过http://google.stanford.edu/访问。

设计一个搜索引擎是一种具挑战性的任务。 搜索引擎索索引数以亿计的不同类型的网页并每天给出过千万的查询的答案。尽管大型搜索引擎对于网站非常重要，但是已完成的、

对于大型搜索引擎的学术上的研究却很少。 此外，由于技术上的突飞猛进和网页的急剧增加，在当前，创建一个搜索引擎和三年前已不可同日而语。本文提供了一种深入的描述，

与 Web增殖快速进展今日创建 Web搜索引擎是三年前很大不同。本文提供了到目前为止，对于我们大型的网页所搜引擎的深入的描述，这是第一个这样详细的公共描述。

除了如何把传统的搜索技术扩展到前所未有的海量数据，还有新的技术挑战涉及到了使用超文本中存在的其他附加信息产生更好的搜索结果。本文解决这样一个问题，如何建立一个可以利用超文本中存在的其他附加信息的实用的大型系统，同时我们也研究一下如何有效处理任何人都能发布他们想发布的包含任何信息的大量自由链接的问题。

关键字： 互联网，搜索引擎，文献检索，PageRank，Google

1.简介

(注： 本文由两个版本--较长的完整版本和一个较短的印刷的版本。 完整版本提供在网络上和会议的CD-ROM上)。 Web给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象 Yahoo这样重要的网页或搜索引擎开始。人工维护的网站列表能有效的覆盖受欢迎的流行的站点，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，提供高质量的查询结果，我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎较好的符合。

1.1网络搜索引擎—升级换代：1994-2000

搜索引擎技术不得不快速升级跟上成倍增长的网站数量。1994年，第一个Web搜索引擎，World Wide Web Worm(WWWW)拥有110，000个网页和网站可访问文档的索引。到1994年11月，顶级的搜索引擎声称可以检索到2万 (WebCrawler)100万个网络文件(来自搜索引擎监视)。可以预见到2000年，可检索到的网页将超过10亿。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三 四月份，World Wide Web Worm平均每天收到1500个查询。在1997年11月，Altavista声称它每天要处理大约20’百万个查询。随着网络用户的增长，可以预见到到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术，把它升级到如此大量的数据上。

1.2 Google：升级与网络

建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快并且保持是最新的版本。存储空间必须高效的存储索引和文档。索引系统必须能够高效地处理上百亿GB的数据。处理查询必须快，达到每秒能处理成百上千个查询

。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的性能和成本也在快速增长，可以部分抵消这些困难。然而，还有几个值得例外，如磁盘的寻道时间，操作系统的效率。在设计Google的过程中，我们既考虑了网络的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理超大量数据集。它能够高效地使用存储空间来存储索引。优化的数据结构能够快速有效地存取(请参见4.2节)。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小(请参阅附录B)。对于象Google这样的集中式系统，采取这些措施得到了良好的系统可升级性。

1. 3设计目标

1.3.1 改进搜索质量。

我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引就有可能很容易找到任何东西。根据Best of the Web 1994 -- Navigators，“最佳导航服务应更容易找到几乎任何在网络上(已经输入的所有数据)。”。然而1997年的Web就迥然不同。任何最近使用搜索引擎的用户很容易证实索索引的完整性并不是唯一影响搜索引擎结果的因素。用户感兴趣的搜索结果往往被“垃圾结果”淹没。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己(使用自己的搜索自己的名字时返回的前十个结果中有它自己)。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。人们仍然只希望看前面的几十个搜索结果。因此，当集合增大时，我们就需要高精确度的工具(在返回的前几十个结果中，相关文档的数量)。由于是从成千上万个有点相关的文档中选出几十个，实际上，我们希望相关的概念就是指最好的文档。高精确非常重要，甚至以响应(系统能够返回的有关文档的总数)为代价。令人十分乐观的的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]。尤其是链接结构和链接文本，为相关性的判断和高质量筛选提供了大量的信息。Google既利用了链接结构又用到了链接文本(请参见2.1和2.2节)。

1.3.2 搜索引擎的学术研究

除了发展迅速，Web越来越商业化。到1993年，只有1.5%的网络服务是来自.com域名。到1997年，增长超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少发布技术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告(请参阅附录A)。对于Google来讲我们有一个的主要目标是推动学术领域在此方面的发展和了解。

另一个设计目标是给适合数目的人们一个实用的系统。对我们来说应用十分重要，因为一些研究表明，现代网络系统中存在大量的有用数据。例如，每天有数千万个查询被执行。然而，获得这些数据却非常困难，主要因为它们被认为有商业价值。

我们的最终设计目标是构建一个体系结构，可以支持大型 Web数据上的一种新的研究活动。为了支持新研究，Google以压缩的形式保存了实际所抓到所有的文档。我们设计Google的主要目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量网络数据，得到满意的结果，而通过其它方法却很难得到。系统在短时间内被建立起来，已经有几篇论文用到了Google建立的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究人员甚至学生都可以对我们的海量网络数据设计或做有趣的实验。

2.系统功能

Google搜索引擎有两个重要功能，帮助它产生高精度的搜索结果。首先，应用Web的链接结构计算每个网页的质量等级值，这个等级称为PageRank，将在98页详细描述它。

第二点，Google利用超链接改进搜索结果。

2.1 PageRank：带来网页排序

网络的引用(链接)图形是重要的资源， 却没有被现有的大多搜索引擎使用。我们建立了一个包含518百万个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们主观的对一个网页重要程度的评价，由此对应的是，PageRank值是一个较好的区分通过网络搜索关键字获得的结果的方法。建立的基础是通过引用判断重要性。对于大多数的主题，一个简单的被限制为网页标题的文本匹配搜索当使用PageRank区分时得到了极好的结果(从google.stanford.edu可以得到演示)。对于Google主系统中的全文搜索，PageRank也有很大的帮助。

2.1.1PageRank计算的描述：

文献引用理论应用到Web中，主要由引用或反向链接到给定页来计数。这会反映了该网页的重要性和质量的近似值。PageRank扩展了这种思想，不平等的计算所有页面上的链接并且通过一个页面上的所有链接。PageRank定义如下:

我们假设页面T1…Tn指向网页A(例如，被引用)。参数d是一个设定在0，1之间的制动因子。我们通常设置d为0.85。在下一节有更多关于d的详情，C(A)定义为网页A指向其它网页的链接数，网页A的PageRank值由下式给出：

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

请注意PageRank涵盖所有网页的一个概率分布得来，因此所有网页PageRank和是1。 PageRank或PR(A)可使用一个简单的迭代算法来计算，相应对应月网页链接矩阵的主特征向量。中等规模的网站计算26万网页的 PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。

2.1.2 直觉的解释

PageRank被看作用户行为的模型。我们假想一个“随机上网者”;随机地给他一个网页;他漫无目的地命中网页的链接，而从来不点“返回键”;最终他觉得烦了，又从另一个随机的网页从新开始。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值几乎变成不可能的。我们还有其它的PageRank算法，见98页。另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。 直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。

2.2链接描述文字

我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。第一，通常链接描述文字比网页本身更精确地描述该网页。第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到， 例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意那抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。

链接描述文字是对被引用网页的描述这个思想被用在World Wide Web Worm中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24万个网页，已经检索到259万多个链接描述文字。

2.3其它功能

除了PageRank和应用链接描述文字外，Google还有其他几个功能。一,它有所有命中数的位置信息，所以它可以在搜索中广泛应用邻近性。第二，Google跟踪一些可视化外表细节，例如字的字体大小。更大的字的权重要高于其他的。第三，知识库存储了原始的全文html网页。

3相关的工作

网络检索研究的历史简短。World Wide Web Worm(WWWW)是最早的搜索引擎之一。后来出现了一些用于学术性的搜索引擎，现在它们中的大多数被上市公司拥有。与Web的增长和搜索引擎的重要性相比， 有关当今搜索引擎技术的优秀论文相当少。根据Michael Mauldin(Lycos Inc的首席科学家))，“各种各样的服务(包括Lycos)非常关注这些数据库的信息。”虽然在搜索引擎的某些特点上做了大量工作。具有代表性的工作有，对现有商业搜索引擎的 结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤其在有组织机构集合方面。在下面两节，我们将讨论在信息检索系统中的哪些领域需要改进以便更好的工作在Web上。

3.1信息检索

信息检索系统诞生在几年前，并发展很好。然而,大多数信息检索系统的研究针对的是受控制的同质集合 ，例如,主题相关的科学论文或新闻故事。实际上，信息检索的主要基准，用小规模的、有组织结构的集合作为它们的基准。大型文集基准只有20GB，相比之下，我们抓到的24万个网页占147GB。在TREC上工作良好的系统，在Web上却不一定产生好的结果。例如，标准向量空间模型企图返回和查询请求最相近的文档，把查询请求和文档都看作由出现在它们中的词汇组成的向量。在Web环境下，这种策略常常返回非常短的文档，这些文档往往是查询词再加几个字。例如，查询“Bill Clinton”，返回的网页只包含“Bill Clinton Sucks”，这是我们从一个主要搜索引擎中看到的。网络上有些争议，用户应该更准确地表达他们想查询什么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象“Bill Clinton”这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。像所给的例子，我们认为信息检索标准需要发展，以便有效地处理Web数据。

3.2有组织结构的集合与网络的不同点

Web是完全无组织的异构的大量文档的集合。Web中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言(既有人类语言又有程序)，词汇(

email地址，链接，邮政编 码，电话号码，产品号)，类型(文本，HTML，PDF，图像，声音)，有些甚至是机器创建的文件(log文件，或数据库的输出)。可以从文档中推断出

来，但并不包含在文档中的信息称为隐含信息。隐含信息包括来源的信誉，更新频率，质量，访问量和引用。不但隐含信息的 可能来源各种各样，而且被检测的信息也大不相同，相差可达好几个数量级。例如，一个重要主页的使用量，象Yahoo每天浏览数达到上百万次，于此相比无名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。 Web与有组织结构集合之间的另外一个明显区别是，事实上，向Web上传信息没有任何限制。灵活利用这点可以发布任何 对搜索引擎影响重大的信息，使路由阻塞，加上为牟利故意操纵搜索引擎，这些已经成为一个严重的问题。这些问题还没有被传统的封闭的信息检索系统所提出来。 它关心的是元数据的努力，这在Web搜索引擎中却不适用，因为网页中的任何文本都不会向用户声称企图操纵搜索引擎。甚至有些公司为牟利专门操纵搜索引擎。

4系统分析

首先，我们提供高层次的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将会深度探讨。

图 1.高层次Google体系结构

4.1Google结构概述

这一节，我们将看看整个系统工作方式的高水平综述，见图1。本节不讨论应用和数据结构，在后几节中讨论。为了效率大部分Google是用c或c++实现的，既可以在Solaris也可以在Linux上运行。Google系统中，网络爬虫(下载网页)是由几个分布式crawlers完成的。一个URL服务器负责向crawlers提供URL列表。抓来的网页交给存储服务器 storeserver。然后，由存储服务器压缩网页并把它们存到知识库中。每个网页都有一个ID，称作docID，当新URL从网页中分析出时，就被分配一个docID。由索引器和排序器负责建立索引index function。索引器从知识库中读取文档，对其解压缩和分析。每个文档被转换成一组词的出现情况，称作命中hits。Hits纪录了词，词在文档中的位置，最接近的字号，大小写。索引器把这些hits分配到一组桶barrel中，产生经过部分排序后的索引。索引器的另一个重要功能是分析网页中所有的链接，将有关的重要信息存在链接描述anchors文件中。该文件包含了足够的信息，可以用来判断每个链接链出链入节点的信息，和链接文本。 URL分解器resolver阅读链接描述anchors文件，并把相对URL转换成绝对URL，再转换成docID。为链接描述文本编制索引，并与它所 指向的docID关联起来。同时建立由docID对组成的链接数据库。用于计算所有文档的PageRank值。用docID分类后的barrels，送给 排序器sorter，再根据wordID进行分类，建立反向索引inverted index。这个操作要恰到好处，以便几乎不需要暂存空间。排序器还给出docID和偏移量列表，建立反向索引。一个叫DumpLexicon的程序把这 个列表和由索引器产生的字典结合在一起，建立一个新的字典，供搜索器使用。这个搜索器就是利用一个Web服务器，使用由DumpLexicon所生成的字典，利用上述反向索引以及页面等级PageRank来回答用户的提问。

4.2 主要数据结构

经过优化的Google数据结构，能够用较小的代价抓取大量文档，建立索引和查询。虽然近几年CPU和输入输出速率迅速提高。磁盘寻道仍然需要10ms。任何时候Google系统的设计都尽可能地避免磁盘寻道。这对数据结构的设计影响很大。

4.2.1 大文件

BigFiles是跨越多个文件系统的虚拟文件，用长度是64位的整型数据寻址。多文件系统之间的空间分配是自动完成的。BigFiles包也处理文件描述符的分配。由于操纵系统不能满足我们的需要，BigFiles也支持基本的压缩选项。

4.2.2 知识库

知识库包含每个网页的全部HTML。每个网页用zlib(见RFC1950)压缩。 压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压 缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。

4.2.3 文档索引

文档的索引保持每个文档有关的信息。 它是固定的宽度 ISAM (索引顺序访问模式)索引。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向docinfo文件，该文件的宽度可变，包含了URL和标题。否则指针指向包含这个URL的URL列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表，并按照校验排序。要想知道某个URL的docID，需要计算URL的校验和，然后在校验和文件中执行二进制查找，找到它的docID。通过对这个文件进行合并，可以把一批URL转换成对应的docID。URL分析器用这项技 术把URL转换成docID。这种成批更新的模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322百万个链接的数据集合将 花费一个多月的时间。

4.2.4 辞典

词典有几种不同的形式。和以前系统的重要改进是，词典对内存的要求可以在合理的价格内。当前实现中，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14万词汇(虽然一些很少用的词汇没有加入到词典中)。它执行分两部分—词汇表(串联在一起，但使用空值隔开)和指针的哈希表的列表的实现。不同的函数词列表有一些辅助的信息，超出了本文以详细解释的范围。

4.2.5点击列表

一个命中列表对应着一个单词在一个文档中出现的位置、字体和大小写信息的列表。命中列表占用了正向索引和反向索引的大部分空间，所以怎样尽可能有效的表示是很重要的。我们考虑了对位置，字体和大小写信息的多种编码方式——简单编码(3个整数)，压缩编码(手工优化分配比特)和霍夫曼编码(Huffman coding)。命中(hit)的详情见图3。

图3.正、倒排索引和词典

我们的压缩编码每个命中用到两个字节(byte)。有两种命中：特殊命中(fancy hit)和普通命中(plain hit)。特殊命中包括在URL，标题，锚文本和meta标签上的命中。其他的都是普通命中。一个普通的命中包括一个表示大小写的比特(bit)，字体大小，和12个bit表示的单词在文件中的位置(所有比4095大的位置都被标示为4096)。字体在文档中的相对大小用3个比特表示(实际上只用到7个值，因为111标示一个特殊命中)。一个特殊命中包含一个大小写比特，字体大小设置为7用来表示它是一个特殊命中，4个比特用来表示特殊命中的类型，8个比特表示位置。对于锚命中，表示位置的8个比特被分成两部分，4个比特表示在锚文本中的位置，4个比特为锚文本所在docID的哈希(hash)值。由于一个词并没有那么多的锚文本，所以短语搜索受到一些限制。我们期望能更新锚命中的存储方式能让位置和docID哈希值能有更大的范围。我们使用在一个文档中的相对字体大小是因为在搜索时，你并不希望对于内容相同的不同文档，仅仅因为一个文档字体比较大而有更高的评级(rank)。

命中列表的长度存在命中的前面。为了节省空间，命中列表的长度在正向索引中与wordID结合，在反向索引中与docID结合。这样就将长度分别限制在8个比特和5个比特(有一些技巧可以从wordID中借用8个比特)。如果长度超过了这个范围，会在这些比特中使用转义码，在接下来的两个字节(byte)里才存放真正的长度。

4.2.6 正向索引

正向索引实际上已经部分排序。它被存放在一系列的桶(barrels)里面(我们用了64个)。每个桶保存了一定范围内的wordID。如果一个文档包含了属于某个桶的单词，它的docID将被记录在桶里面，后面接着一个wordID的列表和相应的命中列表。这种结构需要一点多余空间，因为存储了重复的docID，由于桶的数量很小，所以存储空间的差别很小，但是它能在排序器(sorter)建立最终索引的时候大大节省时间并降低了程序复杂度。更进一步，我们并没有存储完整的wordID，而是存储每个wordID相对于其对应的桶里面最小wordID的差距。这样我们只用到了24个比特，从而为命中列表长度(hit list length)留出了8个比特。

4.2.7 反向索引

反向索引与正向索引有着相同的桶，但是它们是先经过排序器处理过的。对每一个合法的wordID，词典包含了一个指向对应的桶的指针。它指向一个docID的列表和相应的命中列表。这个文档列表显示了有这个单词出现的所有文档。

一个重要的事情是如何对这个文档列表排序。一个简单的方法是按照docID排序。在多个单词的查询中，这种方法可以快速地完成两个文档列表的归并。另一种方案是按照这个词在文档中出现的评分(ranking)排序。这种方式使得单个词的查询相当简单，并且多词查询的返回结果也很可能接近开头。但是，归并要困难得多。而且，开发也会困难得多，因为每次评分函数变动就需要重新建立整个索引。我们综合了两种方案，设计了两个倒排桶集合——一个集合只包括标题和锚命中，另一个集合包含所有的命中。这样我们首先检查第一个桶集合，如果没有足够的匹配再检查那个大一点的。

4.3抓取网页

运行网络爬虫是一项很有挑战性的任务。这里不光涉及到巧妙的性能和可靠性问题，更重要的，还有社会问题。抓取是一个很脆弱的应用，因为它需要与成百上千各种各样的web服务器和域名服务器交互，这些都不在系统的控制范围之内。

为了抓取几亿网页，Google有一个快速的分布式爬虫系统。一个单独的URL服务器(URLserver)为多个爬虫(crawler,一般是3个)提供URL列表。URL服务器和爬虫都用Python实现。每个爬虫同时打开大概300个连接。这样才能保证足够快地抓取速度。在高峰时期，系统通过4个爬虫每秒钟爬取100个网页。这大概有600K每秒的数据传输。一个主要的性能压力在DNS查询。每个爬虫都维护一个自己的DNS缓存，这样在它抓取网页之前就不再需要每次都做DNS查询。几百个连接可能处于不同的状态：查询DNS，连接主机，发送请求，接受响应。这些因素使得爬虫成为系统里一个复杂的模块。它用异步IO来管理事件，用一些队列来管理页面抓取的状态。

事实证明，爬虫连接了50多万个服务器，产生了几千万条日志信息，会带来大量的电子邮件和电话。因为很多人在网上，他们并不知道爬虫是什么，因为这是他们第一次见到。几乎每天，我们都会收到这样的电子邮件：“哇，你看了好多我站上的页面，你觉得怎么样?”也有很多人并不知道爬虫禁用协议(robots exclusion protocol)，他们认为可以通过在页面上声明“本页面受版权保护，拒绝索引”就可以保护页面，不用说，网络爬虫很难理解这样的话。而且，由于涉及到大量的数据，一些意想不到的事情总会发生。比如，我们的系统试图去抓取一个在线游戏。这导致了游戏中出现大量的垃圾消息!这个问题被证实是很容易解决的。但是往往我们在下载了几千万个页面之后这个问题才被发现。因为网络页面和服务器总是在变化中，在爬虫正式运行在大部分的互联网站点之前是不可能进行测试的。不变的是，总有一些奇怪的错误只会在一个页面里面出现，并且导致爬虫崩溃，或者更坏，导致不可预测的或者错误的行为。需要访问大量互联网站点的系统需要设计得很健壮并且小心地测试。因为大量像爬虫这样的系统持续导致问题，所以需要大量的人力专门阅读电子邮件，处理新出现遇到的问题。

4.4网站索引

解析——任何被设计来解析整个互联网的解析器都必须处理大量可能的错误。从HTML标签里面的错别字到一个标签里面上千字节的0，非ASCII字符，嵌套了几百层的HTML标签，还有大量超乎人想象的错误和“创意”。为了达到最快的速度，我们没有使用YACC产生CFG(context free gramma，上下文无关文法)解析器，而是用flex配合它自己的栈生成了一个词法分析器。开发这样一个解析器需要大量的工作才能保证它的速度和健壮。

为文档建立桶索引——每一个文档解析过后，编码存入桶里面。每一个单词被内存里的哈希表——词典转化成一个wordID。词典哈希表新加的内容都被记录在一个文件里。单词在被转化成我wordID的时候，他们在当前文档中的出现会被翻译成命中列表，并写入正排桶(forward barrels)中。建立索引阶段的并行操作主要的困难在于词典需要共享。我们并没有共享整个词典，而是在内存里保存一份基本词典，固定的1千4百万个单词，多余的词写入一个日志文件。这样，多个索引器就可以同时运行，最后由一个索引器来处理这个记录着多余单词的小日志文件。

排序——为了产生倒排索引，排序器取出各个正排的桶，然后根据wordID排序来产生一个标题和锚命中的倒排桶，和一个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而且，我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordID和docID将它们进一步分割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短的倒排桶和完整的倒排桶。

4.5搜索

搜索的目标是高效地返回高质量的结果。很多大型的商业搜索引擎在效率方面看起来都有很大的进步。所以我们更专注于搜索结果的质量，但是我们相信我们的解决方案只要花一点精力就可以很好的应用到商业的数据上。Google的查询评估流程如图4。

为了限制响应时间，一旦某个数量(现在是40,000)的匹配文档被找到，搜索器自动跳到图4中的第8步。这意味着有可能返回次优的结果。我们现在在研究新的方法来解决这个问题。在过去，我们根据PageRank值排序，有较好的效果。

1.解析查询(Query)。

2.把单词转化成wordID。

3.从每个单词的短桶文档列表开始查找。

4.扫描文档列表直到有一个文档匹配了所有的搜索词语。

5.计算这个文档对应于查询的评分。

6.如果我们到达短桶的文档列表结尾，从每个单词的全桶(full barrel)文档列表开始查找，跳到第4步。

7.如果我们没有到达任何文档列表的结尾，跳到第4步。

8.根据评分对匹配的文档排序，然后返回评分最高的k个。

图4 Google查询评估

4.5.1评分系统

Google比典型的搜索引擎维护了根多的web文档的信息。每一个命中列表(hitlist)包含了位置，字体和大小写信息。而且，我们综合考虑了超链接文本命中和页面的PageRank值。把所有的信息综合成一个评分是很困难的。我们设计了评分函数保证没有一个因素有太大的影响。首先，考虑简单的情况——一个单词的查询。为了对一个单词的查询计算文档的分值，Google首先为这个单词查看这个文档的命中列表。Google将命中分为不同类型(标题，锚，URL，普通文本大字体，普通文本小字体，……)，每一种类型都有自己的类型权重值(type-weight)。类型权重值构成一个由类型寻址(indexed)的向量。Google数出命中列表中每种类型命中的数量。每个数量转化成一个数量权重(count-weight)。数量权重开始随着数量线性增长，但是很快停止增长，以保证单词命中数多于某个数量之后对权重不再有影响。我们通过数量权重向量和类型权重向量的点乘为一个文档算出一个IR分数。最后这个IR分数与PageRank综合产生这个文档最终的评分。

对于一个多词搜索，情况要更复杂。现在，多个命中列表必须一次扫描完，这样一个文档中较近的命中才能比相距较远的命中有更高的评分。多个命中列表里的命中结合起来才能匹配出相邻的命中。对每一个命中的匹配集(matched set)，会计算出一个接近度。接近度是基于两个命中在文档(或锚文本)中相隔多远计算的，但是被分为10个等级从短语匹配到“一点都不近”。不光要为每一种类型的命中计数，还要为每一种类型和接近度都计数。每一个类型和接近度的组有一个类型-接近度权重(type-prox-weight)。数量被转化成数量权重。我们通过对数量权重和类型-接近度权重做点乘计算出IR分值。所有这些数字和矩阵都会在特殊的调试模式下与搜索结果一起显示出来。这些显示结果在开发评分系统的时候很有帮助

4.5.2 反馈

评分函数有很多参数比如类型权重和类型-接近度权重。找出这些参数的权重值简直就跟妖术一样。为了调整这些参数，我们在搜索引擎里有一个用户反馈机制。一个被信任的用户可以选择性地评价所有的返回结果。这个反馈被记录下来。然后在我们改变评分系统的时候，我们能看到修改对之前评价过的搜索结果的影响。尽管这样并不完美，但是这也给我们一些改变评分函数来影响搜索结果的想法。

5结果与表现

衡量一个搜索引擎最重要的标准是其搜索结果的质量。虽然如何做一个完整的用户评估超越了本文的范围，但是我们在Google身上得到的经验，表明它提供结果，比主要商用搜索引擎对绝大多数搜索提供的结果更好。图表4表示的Google对于搜索“比尔.克林顿”的结果，作为一个例子可以说明，对PageRank, anchor text(关键词),和proximity(相似度)的使用。这样的搜索结果显示了Google的特色。搜索结果被服务器串联在一起。这样的方法当在需要对结果集筛选时非常有用。很大数量的结果会来自域名whitehouse.gov，有理由相信这个来源含有本次该搜索中被期望找到的结果。当前，绝大多数主要的商用搜索引擎不会返回任何来自whitehouse.gov的结果，更不用说正确的结果。注意，第一个搜索到的连接没有标题，是因为它不是抓取得结果，而是Google基于anchor text决定这个结果是查询所期望得到的好结果。同样的，第15号结果是一个电子邮件地址，当然这也是基于超链接的结果，而非可抓取得结果。

所有结果都是合理的高质量页面，而且最后检查，没有坏连接。这主要归功于他们有很高的PageRank。PageRank的百分比使用红色条形图表示。最后，这里的结果中，没有只有Bill没有Clinton或只有Clinton没有Bill的，这是因为我们在关键词出现时使用了非常重要的proximity。当然对一个实际的对搜索引擎的质量测试应该包括广泛的对用户研究或者对搜索结果的分析，但是我们没有时间做以上析。但是我们邀请读者在http://google.stanford.edu/flp自己测试Google。

5.1存储需求

除搜索质量外，Gooogle被设计为能够消化互联网规模不断增长带来的效能问题。一方面，使用高效存储。表一是对Google的统计与存储需求的详细分类，由于压缩后的存储体积为53GB，为源数据的三分之一多一点。就当前的硬盘价格来说可以为有用资源提供廉价的相关存储设备。更重要的是，搜索引擎使用的所有数据的总合需要相应的存储大约为55GB。此外，大多数查询能被要求充分使用短反向索引[short inverted index]，在更好的编码与压缩文档索引后，一个高质量的网络搜索引擎可能只需要一台有7GB存储空间的新电脑。

5.2系统性能

这对搜索引擎的抓取与索引来说很重要。这样信息被转化为数据的速度以及系统主要部分改变后被测试的速度都相对更快。就Google来说，主要操作包括：抓取，索引和排序。一旦硬盘被填满、或命名服务器崩溃，或者其它问题导致系统停止，都很难度量抓取所需要化费的时间。全部花费在下载2千6百万个页面[包括错误页面]的时间大概是9天。但是如果系统运行更为流畅，这个过程还可以更快，最后的1千1百个页面只使用了63个小时，平均4百万每天，每秒48.5页。索引的运行速度快于抓取速度的重要原因是我们花费了足够的时间来优化索引程序，使它不要成为瓶颈。优化包括对本地硬盘上的文档的索引进行大规模的升级和替换关键的数据结构。索引的速度达到大概54页每秒。排序可以完全平行作业，使用四台机器，整个处理时间花费近24个小时。

5.3搜索性能

提高搜索性能并不是本次我们研究的重点。当前版本的Google返回多数查询结果的时间是1到10秒。这个时间主要受到硬盘IO以及NFS[网络文件系统，当硬盘安置到许多机器上时使用]的限制。进一步说，Google没有做任何优化，例如查询缓冲区，常用词汇子索引，和其它常用的优化技术。我们倾向于通过分布式，硬件，软件，和算法的改进来提高Google的速度。我们的目标是每秒能处理几百个请求。表2有几个现在版本Google响应查询时间的例子。它们说明IO缓冲区对再次搜索速度的影响。

6结论

Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信

息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。

6.1未来的工作

大 型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请 求缓冲区，巧妙地分配

磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这 个目标已经由实现了。受需求驱动，

用代理cache创建搜索数据库是一个有前途的研究领域。我们计划加一些简单的已经被商业搜索引擎支持的特征，例如布尔 算术符号，否定，填充。然而另外一些应用刚刚开始探

索，例如相关反馈，聚类(Google现在支持简单的基于主机名的聚类)。我们还计划支持用户上下文 (象用户地址)，结果摘要。我们正在扩大链接结构和链接文本的应用。简单

的实验证明，通过增加用户主页的权重或书签，PageRank可以个性化。对于链 接文本，我们正在试验用链接周围的文本加入到链接文本。Web搜索引擎提供了丰富的研究课题。如

此之多以至于我们不能在此一一列举，因此在不久的将来，我们希望所做的工作不止本节提到的。

6.2高质量搜索

当 今Web搜索引擎用户所面临的最大问题是搜索结果的质量。结果常常是好笑的，并且超出用户的眼界，他们常常灰心丧气浪费了宝贵的时间。例如，一个最流行的商业搜索引擎

搜索“Bill Clillton”的结果是the Bill Clinton Joke of the Day: April 14, 1997。Google的设计目标是随着Web的快速发展提供高质量的搜索结果，容易找到信息。为此，

Google大量应用超文本信息包括链接结构和链接 文本。Google还用到了相邻性和字号信息。评价搜索引擎是困难的，我们主观地发现Google的搜索质量比当今商业搜索引擎高。通过PageRank分析链接结构使Google能够评价网页的质量。用链接文本描述链接所指向的网页有助于搜索引擎返回相关的结果(某种程度上提高了质量)。最后，利用相邻性信息大

大提高了很多搜索的相关性。

6.3可升级的体系结构

除 了搜索质量，Google设计成可升级的。空间和时间必须高效，处理整个Web时固定的几个因素非常重要。实现Google系统，CPU、访存、内存容 量、磁盘寻道时间、磁盘吞吐量

、磁盘容量、网络IO都是瓶颈。在一些操作中，已经改进的Google克服了一些瓶颈。Google的主要数据结构能够有效利用存储空间。进一步，网页爬行，索引，排序已经足够建立大部分web索引，共2千四百万个网页，用时不到一星期。我们希望能在一个月内建立 一亿网页的索引。

6.4研究工具

Google不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如，提出了Web查询的局限性

，不需要网络就可以回答。这说明Google不仅是重要的研究工具，而且必不可少，应用广泛。我们希望Google是全世界研究者的资源，带动搜索引擎技术的更新换代。

7致谢

Scott Hassan and Alan Steremberg评价Google的改进。他们的才智无可替代，作者由衷地感谢他们。感谢Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase开发组的支持和富有深刻见解的讨论。最后感谢IBM，Intel，Sun和投资者的慷慨支持，为我们提供设备。这里 所描述的研究是Stanford综合数字图书馆计划的一部分，由国家科学自然基金支持，合作协议号IRI-9411306。DARPA，NASA，Interva研究，Stanford数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。

引用

Best of the Web 1994 -- Navigators http://botw.org/1994/awards/navigators.html

Bill Clinton Joke of the Day: April 14, 1997. http://www.io.com/~cjburke/clinton/970414.html.

Bzip2 Homepage http://www.muraroa.demon.co.uk/

Google Search Engine http://google.stanford.edu/

Harvest http://harvest.transarc.com/

Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview http://www.computer.org/pubs/expert/1997/trends/x1008/mauldin.htm

The Effect of Cellular Phone Use Upon Driver Attention http://www.webfirst.com/aaa/text/cell/cell0toc.htm

Search Engine Watch http://www.searchenginewatch.com/

RFC 1950 (zlib) ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html

Robots Exclusion Protocol: http://info.we**rawler.com/mak/projects/robots/exclusion.htm

Web Growth Summary: http://www.mit.edu/people/mkgray/net/web-growth-summary.html

Yahoo! http://www.yahoo.com/

[Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997.

[Bagdikian 97] Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557

[Chakrabarti 98] S.Chakrabarti, B.Dom, D.Gibson, J.Kleinberg, P. Raghavan and S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998.

[Cho 98] Junghoo Cho, Hector Garcia-Molina, Lawrence Page. Efficient Crawling Through URL Ordering. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998.

[Gravano 94] Luis Gravano, Hector Garcia-Molina, and A. Tomasic. The Effectiveness of GlOSS for the Text-Database Discovery Problem. Proc. of the 1994 ACM SIGMOD International Conference On Management Of Data, 1994.

[Kleinberg 98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998.

[Marchiori 97] Massimo Marchiori. The Quest for Correct Information on the Web: Hyper Search Engines. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997.

[McBryan 94] Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-26-27 1994. http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps

[Page 98] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress. http://google.stanford.edu/~backrub/pageranksub.ps

[Pinkerton 94] Brian Pinkerton, Finding What People Want: Experiences with the WebCrawler. The Second International WWW Conference Chicago, USA, October 17-20, 1994. http://info.we**rawler.com/bp/WWW94.html

[Spertus 97] Ellen Spertus. ParaSite: Mining Structural Information on the Web. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997.

[TREC 96] Proceedings of the fifth Text REtrieval Conference (TREC-5). Gaithersburg, Maryland, November 20-22, 1996. Publisher: Department of Commerce, National Institute of Standards and Technology. Editors: D. K. Harman and E. M. Voorhees. Full text at: http://trec.nist.gov/

[Witten 94] Ian H Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. New York: Van Nostrand Reinhold, 1994.

[Weiss 96] Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi, Andrzej Duda, and David K. Gifford. HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering. Proceedings of the 7th ACM Conference on Hypertext. New York, 1996.

个人简历

Sergey Brin于1993年获得美国马兰里大学帕克分校数学与计算机专业理学学士学位。他于1995年获得理科硕士成为斯坦福大学计算机科学博士候选人。他是国家科学基础研究生奖学金的获得者。他的的研究领域包括搜索引擎、从非结构化来源提取信息以及对大型文本数据和科学资料进行数据挖掘。

Lawrence Page生于密歇根州东部的兰辛市并于1995年获得了密歇根大学计算机工程的工学学士学位。他目前是斯坦福大学计算机科学博士候选人。他的一些研究方向包括web链接结构、人机交互、搜索引擎、可扩展性的信息访问接口,个人数据挖掘方法。

8附录A广告及形形色色的动机

目前,商业搜索引擎主要的营业模式是广告。广告业务模式的目标并不总是为用户提供高质量的搜索。例如,在我们的搜索引擎的原型中名列前茅的结果关于手机的是”使用手机对驾驶员的注意力的影响”,一个研究作了较为详细的解释了在驾驶时关于使用手机交谈的的干扰和风险。这个查询结果排名如此之高,因为根据PageRank算法它在网络上被引用的近似值判定了它是十分重要。很明显，这对于给手机做广告的广告商赚钱的搜索引擎来说比较困难，因为我们的系统返回的那些支付了广告费的页面。我们认为广告资助的搜索引擎会偏向的广告商和远离消费者的需求，因为即使对于专家来说评估搜索引擎也是很困难的，因为搜索引擎的偏向是特别狡猾的。

一个典型的例子是OpenText搜索引擎,据报道，它向公司出售使特定的查询在搜索结果列表前面的权利。这种类型的偏向比做广告更加阴险，因为这将导致谁都不清楚排名是有价值的还是愿意付费的那些。这种商业模式导致了恐慌和OpenText搜索引擎的终结。但市场可以接纳较低程度的偏向。比如，搜索引擎可以在那些“友好”的公司的查询结果中添加一个因子并从其竞争对手中减少因子。这种类型的偏见是非常难以被发现,但仍能有显著影响市场。广告收益的诱惑经常导致低质量的搜索结果。例如，我们注意到一个大型航空公司的名字用来查询时主要的搜索引擎不会返回它的主页，尽管它已经为它名字的查询此支付了昂贵的而广告费。一个优秀的搜索引擎不会把广告当做必需的虽然这可能导致它从航空公司获得的收益受损。一般来说，从消费者的角度，为了他们可以查找到想要的东西，搜索引擎需要更少的广告。这就是削弱现有当前搜索引擎广告支持业务的原因。然而，依旧总会从那些希望顾客选择商品的广告客户那里取得收益，或者还有其他一些较好的新的方式。但是我们相信这个论点，广告引起太多问题的原因是它对于搜索引擎的竞争是至关重要的。在理论上是无需干涉的。

9附录B伸缩性

9.1Google的可伸缩性

我们把Google设计成具有近期能够处理一亿网页的可伸缩性。我们目前得到了磁盘和机器所需的款额，我们也考虑了大部分数据结构的易扩展性。然而,在100的网页,我们将会非常接近了对各种操作系统的限制，在常见的的操作系统中(现在我们跑在Solaris与Linux)。这些包括诸如可寻址的内存,打开的文件描述符的数目,网络带宽和插座,以及其他许多人。我们相信扩展多到超过一亿万页时将大大增加我们系统的复杂性。

9.2集中索引结构的可伸缩性

计算机性能的提高是它能够以合理的成本对大量文本进行索引，当然，更多的带宽密集型其他媒体，如视频很可能会越来越普遍。

但是，同生产成本较低的文本相比，媒体，如视频文件，文本可能仍然非常普遍。此外，很可能很快就会有语音识别，通过合理的工作的文字转换成语音，扩大现有的文字数量。这一切为集中索引提供了令人惊异的可能性。 下面是一个说明性的示例。 我们假设我们要索引的美国每个人一年中写下的任何事。 我们假设在美国有2.5亿人，他们写每日平均10 k。 这将花费空间850 TB。还假定索引万亿字节现在可以做一个合理的费用。我们还假定索引方法的文字是线性的，或接近线性的复杂性。鉴于所有这些假设，我们可以计算需要多长时间才可以指数的850TB字节的合理费用承担一定的增长因素。摩尔定律在1965年被定义为每18个月翻一番的处理器的功耗。它过去一直明显的符合事实，不仅仅是处理器，还有磁盘等对其他重要的系统参数。如果我们假设，摩尔定律在未来一直得到验证，我们只需要10多倍，或15年才能达到我们索引的美国每个人一年中写下的任何事的的目标且价格是一个小公司可以承担的。当然，硬件专家们有些担心摩尔定律可能无法继续在未来15年一直被遵守，但肯定了许多令人感兴趣的集中应用，即使我们只能达到我们假设的例子的一部分成果。

当然，一个分布式的系统比如 G l oss或Harvest通常会给索引带来高效和较好的技术解决方案，但由于过高的安装设置和管理成本，似乎难说服全世界都使用这些系统。然而，减少管理成本还是很有大有可能的。 如果发生这种情况，并且每个人都开始运行一个分布式的索引系统搜索会当然改善大幅。

因为，计算机不断的发展，人们受限于只能打字和说话，文本索引增加的比例比当前会更多。当然，计算机生成的内容可能无限，但只索引大量的人共生成内容似乎极其有用。 因此，我们乐观的认为，我们集中式的Web搜索引擎结构将改善和有助于搜素文本信息的能力，并随着时间的推移扩展，未来搜索会很光明。

来源：卢松松博客 QQ/微信：13340454 ，转载请注明出处！

本文地址：https://lusongsong.com/info/post/164.html