Sergey Brin和Lawrence Page
Computer Science Department
Stanford Unversity, Stanford, CA 94305, USA
sergey@cs.stanford.edu和page@cs.stanford.edu
摘要：
本文介绍了一个在超文本中广泛应用的大型搜索引擎Google的原型。Google的设计使之能够高效地抓取网络信息并为之建立索引，它的查询结果比现存的其它系统都要更令人满意。这个原型的全文和至少含有2千4百万个页面的超链接数据库可以从http://google.stanford.edu/下载。设计一个搜索引擎是一项富有挑战性的工作。搜索引擎要为上百亿包含等量的不同词汇的网页建立索引。它们每天要接受上亿次的查询。尽管大型的搜索引擎在网络上是非常重要的，但是在学术上却没有多少对它的研究。另外，由于技术的突飞猛进和网页量的剧增，在今天要搭建一个网络搜索引擎比起三年前是大有不同的。本文对我们的大型网络搜索引擎提供了一份深层次的介绍──据我们所知，这是公开发表的论文中第一篇描述得如此详尽的。除了在把传统搜索技术应用到如此数量级的数据中遇到的问题以外，还有一些新的技术上的挑战，比如利用超文本中的附加信息来改善搜索结果。本文将着手解决这个问题，如何搭建一个实用的大型系统来发掘超文本中的附加信息。我们还将要关注如何有效地处理无组织的任何人都能随意发布任何信息的超文本数据集。
关键词
万维网，搜索引擎，信息检索，PageRank算法，Google
1 绪论
（注意：这篇论文有两个版本──一个长一些的全文版本，一个精简一些的打印版本。全文版本可以在网上下载，也可以在研讨会的CD-ROM上找到。）
万维网给信息检索带来了新的挑战。万维网上的信息量在飞速增长，同时网络研究艺术中一些缺乏经验的新用户的数量也在激增。人们一般利用网络上的超链接来网上冲浪，一般都是从高质量人工维护的索引开始，比如Yahoo！或者搜索引擎。人工维护的目录虽然有效地包含了流行的话题，但是它具有主观性、搭建和维护的代价高、升级缓慢，并且无法涵盖所有严肃深奥的主题。基于关键词匹配的自动搜索引擎有经常返回一些低质量结果。更糟的是，有些广告商专门设法误导自动搜索引擎来吸引人们的注意。我们已经建立了一个大型搜索引擎能解决现存系统中的很多问题。它专门利用了超文本中的附加信息来提高搜索结果的质量。我们选择Google作为我们系统的名字，取自一个俗语googol的谐音，意思是10的100次方，这和我们建立一个大型搜索引擎的目标是相当吻合的。
1.1 网络搜索引擎——升级：1994—2000
搜索引擎技术不得不经常调整以跟上网络的增长。1994年，第一批网络搜索引擎中的World Wide Web Worm（WWWW）索引了110’000篇网页和有效的网络文件。到了1997年11月，顶级搜索引擎声称索引了两百万（WebCrawler）至十亿篇网络文件（来自Search Engine Watch）。可以预见到2000年，一个全面的网络索引将会包含一百亿个文件。与此同时，搜索引擎处理的查询量也在爆增。1994年3月和4月，World Wide Web Worm平均每天要接受1500次查询。1997年11月，Altavista声称它每天要处理大约两亿次查询。随着网络用户和查询搜索引擎的自动系统数量的增长，估计到2000年顶级的搜索引擎每天要处理上十亿次的查询。我们的系统的目标就是要着手解决这些问题，无论是质量还是在将搜索引擎技术扩展到如此程度中引入的可扩展性的概念。
1.2 Google：与网络同步
要搭建一个哪怕是能和现今网络规模相适应的搜索引擎都会遇到很多挑战。要想搜集网络文件并保持更新就需要快速的抓取技术。还要有效地利用磁盘空间索引和部分文件本身。索引系统必须能高效地处理上百G的数据。还要迅速地处理每秒钟成百上千次的查询。
随着网络的不断增长，这项工作变得越来越困难了。但是，硬件性能和费用问题的改善也部分地削减了困难度。然而在这个进度中还有几个明显的例外，比如磁盘的寻道时间和操作系统的健壮性。在Google的设计中，我们同时考虑到了网络的增长速度和技术的变更。Google的设计使之能够很好地扩展到能处理极大量的数据。它有效地利用了存储空间来储存索引文件。优化的数据结构使之能够支持快速高效的数据访问（见4.2节）。进一步地，我们希望建立索引和存储文本文件或HTML文档的代价会相对于它们实际的大小而不断减小。对于象Google这样的集中式系统来说，这些措施换来的是可观的可扩展性。
1.3 设计目标
1.3.1 提高搜索质量
我们的首要目标是提高网络搜索引擎的质量。在1994年，有些人认为通过全搜索索引是有可能很容易找到任何东西的。根据Best of The Web 1994–Navigators, “最好的导航服务可以在网络中找到几乎任何东西（只要输入所有的数据）。”然而，1997的网络就大不一样了。任何最近使用过搜索引擎的人都能轻易地证实索引地完整性并不是影响搜索结果质量的唯一因子。用户们真正感兴趣的搜索结果经常被“垃圾结果”所湮没。事实上，到1997年11月为止，在四个顶级的商业搜索引擎中只有一个能搜到自己（在搜索自己名字时前十位结果中返回自己的搜索页面）。引发这个问题的一个主要原因就是索引中文件的数量已经增长了好几个数量级，相应地，用户能查阅的文档数却没有增加。人们仍然只愿意看看前几十个结果。因此，当集合的大小增加时，我们需要具有高精度（比如前几十个结果中的相关文档的数量）的工具。当然，我们希望我们所说的“相关”只是指恰恰最好的文档，因为很可能还有几万个稍有点相关的文档。即使与招回率（系统能够返回的相关文档的总数）的代价相比，高精度仍然是很重要的。近来对利用更多的超文本信息来改进搜索和其它应用软件的方法还是相当乐观的[Marchiori 97][Spertus 97][Weiss 96][Kleinberg 98]。特别是链接结构[Page 98]和链接文本能够为相关性判断和质量过滤提供大量的信息。Google同时利用了链接结构和链接文本（见2.1节和2.2节）。
1.3.2 搜索引擎的学术研究
除了迅猛的发展，网络也随着时间增长变得越来越商业化了。1993年的时候，只有1.5％的网络服务器是在.com域名下的。到了1997年，这个数字增长到超过60 ％。同时，搜索引擎也从学术领域移民到了商业领域中。到目前为止，大多数搜索引擎的开发工作都是在公司中进行的，几乎不公开任何技术细节。这就使得搜索技术很大程度上被关在暗箱中操作，并且面向广告了。我们有强烈的愿望利用Google来推动学术领域中发展和理解。
另一个设计目标是建立一个给相当数量的人们实际使用的系统。用户的使用对于我们来说十分重要，因为我们认为大多数有意义的研究都离不开现代网络中海量数据的支撑。例如，每天都会有几千万的查询量。然而因为这些数据被认为是具有商业价值的，所以我们很难得到这些数据。
我们最后的设计目标就是建立一个能够支持基于海量网络数据的新研究活动的体系结构。为了提供给新研究的使用，Google以压缩形式存储了所有它抓取的实际文档。我们设计Google的一个主要目标在于建立一个环境使得其它的研究人员能够快速进入这个领域、处理网络上海量数据、产生一般很难产生的有意义的成果。系统建立后的不长的时间里，已经有不少论文用到了Google生成的数据库，还有很多正在进行当中。我们的另外一个目标是建立一个空间站实验室似的环境，在这里研究人员甚至学生都能利用我们的海量网络数据进行设计和做一些有意义的实验。
2 系统特性
Google搜索引擎有两个重要的特性，有助于产生高精度结果。第一，它利用网络的链接结构计算每个网页的排名值。这个排名值被称为PageRank，在[Page 98]中有详细的介绍。第二，Google利用链接来改进搜索结果。
2.1 PageRank：给网络带来秩序
网络的引用（链接）图是一件很重要的资源，却在很大程度上被现存的网络搜索引擎忽视了。我们已经建立了一个包含了5亿1千8百万个这样的超链接的图，一个有重要意义的对整体的采样。通过这些图可以迅速地计算一个网页的“PageRank”，一个对引用重要性的客观评价，很好地与人们对重要度的主观概念保持了一致性。由于这种一致性，PageRank是一种对网络关键词搜索结果评级的绝好的方法。对于大多数流行的主题，在对网页标题简单的文本匹配中PageRank对结果评级的表现棒极了（演示可以在google.stanford.edu上得到）。在Google主系统的全文搜索中，PageRank也帮了不少忙。
2.1.1 计算PageRank
在学术文献中的引用理论已经被应用到网络中了，大部分是通过对指向某页的引用或链接计数。这的确对一个网页的重要性或质量给出了一些近似值。PageRank扩展了这种思想，对指向网页的链接并非平等地计数，并且将网页上的链接数标准化。PageRank的定义如下：
我们假设有网页T1…Tn指向（例如：引用）网页A。系数d是值在0 到1之间的抑制因子。我们通常将它设为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)可用简单的迭代算法来计算，对应于规格化后的网络链接矩阵的主特征向量。并且，在一个中等规模的工作站上计算2千6百万网络页面的PageRank只需要几个小时。还有很多细节问题，但是超出了本文的论述范围。
2.1.2 直观理由
PageRank可以被认为是用户行为的模型。我们假设假设有一个“随机冲浪者”，给他一个随机的网页，他不停地点击链接，从不点“后退”，但是最终会厌烦，然后从另外一个随机网页上再开始。这个随机冲浪者访问某一网页的概率就是它的PageRank。而抑制因子d就是随机冲浪者在每一个页面上因厌烦而请求另一随机页面的概率。一个重要的变体是只将抑制因子d加在一个单一的页面上，或者一组页面上。这样就带来了可定制性，并且使得故意误导系统而得到较高的排名的行为变得几乎不可能。我们还有许多其它扩展的PageRank算法，见[Page 98]。
另一个直观理由是如果一个网页有很多网页指向它，或者有一些PageRank值很高的页面指向它，这个网页的PageRank值就会很高。直觉上来讲，一个被网络上到处引用的页面应该是值得一看的。并且，有一些可能只有一个比如从Yahoo!主页上来的引用的网页同样也是只得一看的。如果一个网页质量不高，或者就是个死链，Yahoo!主页是不太可能会链接它的。PageRank通过在网络链接结构中递归地传播权重而同时处理了这两个因素和两者之间的所有情况。
2.2 链接文本
我们的搜索引擎对链接文本进行了特殊处理。大多数搜索引擎将一个链接上的文本和链接所在的页面关联起来。更进一步地，我们把它和这个链接所指向的网页关联起来。这样做有两点好处。首先，链接文本往往能比网页本身提供更精确的描述。其次，对于基于文本的搜索引擎不能索引的文档，比如图像、程序、数据库等，链接文字是有必要存在的。这样就有可能返回一些并没有实际抓取过的页面。注意，没有抓取过的页面会引起问题，因为在返回给用户之前它们并没有被检查过可用性。在这种情况下，搜索引擎甚至会返回一个并不实际存在的页面，但是有一个超链接指向它。但是，我们可以把结果分类，所以这个特殊问题很少发生。
这种将链接文字传递到它所指向的页面的思想在World Wide Web Worm[McBryan 94]中就实现了，就是由于它能有助于搜索非文本数据，而且能够在少量下载文档的情况的下增加搜索覆盖面。我们使用链接传递的主要原因是链接文字能够提供高质量的结果。有效地利用链接文字是有技术困难的，因为要处理的数据量十分巨大。在我们目前抓取的2千4百万个页面中，我们索引了超过2亿5千9百万个链接文本。
2.3 其它特性
除了PageRank和链接文本的使用，Google还有不少其它的特性。首先，对于所有的点击都有位置信息，这样就能在搜索中充分应用邻近性。其次，Google注意到了一些可视的表达细节，比如词语的字号。大号或者黑体字的权重要高于其它的字。再次，在仓库中能够获取原始完整的HTML页面。
3 相关工作
网络中的搜索引擎有一个简短的历史。World Wide Web Worm(WWWW)[McBryan 94]是最早的搜索引擎之一。紧跟着又有许多其它的学术搜索引擎，它们有很多现在已经是上市的公司了。相比网络的增长而言对于搜索引擎的重要性此前只有少量关于现在搜索引擎的文档[Pinkerton 94]。Michael Mauldin（Lycos Inc的首席科学家）[Mauldin]说，“各式各样的服务（包括Lycos）都紧密地关注这些数据库的细节”。不过，在搜索引擎的一些特殊细节上也有一定量的工作。尤其具有代表性的工作有，通过再处理现存的一些商业搜索引擎的结果再得到结果，或者创建小型“个人化的”搜索引擎。最后，在信息检索系统方面的研究也不少，尤其是在精确控制集合方面。在接下来的两节里，我们会讨论在一些需要扩展的的领域，以便更好地在网络上工作。
3.1 信息检索
在信息检索系统领域的工作可以追述到几年前，并且发展迅速[Witten 94]。但是多数在信息检索系统上的研究都是基于小规模同构的精确控制集合的，比如科学论文或者关于某一主题的新闻故事的集合。当然，信息检索的主要测评组织：Text Retrieval Conference[TREC 96]使用了一个相当小的精确控制集合作为它们的基准。相比“极大型公司”才20G的基准，我们爬行了2千4百万总共147G的网页。在TREC上工作良好的东西，拿到网络中来往往就得不到好的结果。比如，标准向量空间模型应该返回与查询词最相近的文档，它假设查询词和文档都是由它们的词频所定义的向量。在网络上，这种策略往往返回在查询词后加几个词的很短的文档。比如，我们在一个主要的搜索引擎上看到，查询“Bill Clinton”，返回了一个只包含“Bill Clinton Sucks”的页面和查询“Bill Clinton”得到的图片。有人争辩说，在网络上用户应该更精确地指定他们想要什么并在查询的时候多用些词。我们强烈地反对这种立场，如果一个用户提出象“Bill Clinton”这样的查询，他应该得到理想的结果，因为在这个主题上存在大量高质量的信息。因为有这样的事例，我们认为标准的信息检索工作需要发展以便高效地处理网络任务。
3.2 网络与精确控制集合的区别
网络是一个完全无控制的异构文档的大型集合。网络中的文档内部极具变化性，外部的元信息也是如此。例如，文档内部的语言（无论是人类还是编程语言）、词汇（电子邮件地址、链接、邮编、电话号码、产品编号等）、格式的类型（文本、HTML、PDF、图像、声音等），甚至有些是机器产生的（日志文件或者数据库的输出）。另一方面，我们将外部元信息定义为能够从一个文档中推出的信息，但是它本身并不包括在文档中。外部元信息的例子如，资料来源的声誉、更新频率、质量、流行度或者访问量，还有引用。不仅外部元信息资料可能的来源各式各样，被评价的东西本身也是极为多样的。比如一个重要的主页比如Yahoo!目前每天要接受上万次的页面浏览，与此相比一篇晦涩的历史文章可能十年才会被浏览一次。很显然，搜索引擎对这两类信息的处理是大不相同的。
网络与精确控制集合间的另一个巨大的区别在于，在网络上实际上没有对什么人可以上传加任何限制。这种发布任何信息的灵活性和搜索引擎对路由传输的巨大影响再加上一些公司为牟取利益而故意操纵搜索引擎一起，已经形成了严重的问题。这些在传统搜索引擎中没有被提出来的问题已经接近信息检索系统了。另外，有意思的是元数据效应对网络搜索引擎几乎是失败的，因为任何没有向用户直接陈述的页面文本都会被指责为是在操纵搜索引擎。还存在有大量的公司专门琢磨操纵搜索引擎以牟取利益。
4 系统剖析
首先，我们对体系结构做一个整体的讨论。然后，会对深层次的重要的数据结构做一些描述。最后，我们会逐个深刻解释主要的应用程序：爬行器，索引器和搜索器。
4.1 Google体系结构概述
在这一节里，我们会对图1中的整个系统是如何工作的做一个整体上的概述。接下来的章节会讨论本节没有涉及的应用程序和数据结构。Google的绝大部分为了保证效率的原因是用C或者C++程序实现的，可以在Solaris或者Linux下运行。
【图1：Google的整体结构】
在Google中，网络爬行（网页的下载）是由很多分布的爬行器来做的。由一个URL服务器来向爬行器发送URL列表。被抓取下来的网页就被送到存储服务器上。存储服务器再把网页压缩并存储在仓库里。每一篇网页都有唯一一个与之相关联的ID号，称作docID，每当有一个新的URL被分析出来的时候都会被赋予一个docID。索引函数由索引器和整理器在执行。索引器会执行若干个函数。它会读取仓库、解压文档并分析它们。每一篇文档都被转化为词汇出现情况的集合，被称为hits。hits记录了词汇、在文档中的位置、对字号的估计和大小写。索引器将这些hits分发到一些“桶”的集合中，创建部分整理好的前向索引。索引器还要执行另一个重要的函数。它要分析出每一篇网页中的链接然后将关于它们的重要信息存储在一个链接文本文件中。这个文件包含了足够的信息，可以判断每个链接分别是从哪里到哪里，还有链接上的文本。
URL分解器读取链接文件，并将其中相URL转化为绝对URL，然后转化成docID。它将链接文本放入前向索引中，将链接所指向的docID与之关联起来。它还要生成一个docID对偶的链接数据库。链接数据库是用来给所有文档计算PageRank的。
整理器获得以docID整理过的（这是一种简化，见4.2.5节）桶，再根据docID进行整理，生成倒排索引。为了使这个操作几乎不需要临时空间，这一步要在一个特定的地方执行。整理器在倒排索引中产生wordID和偏移量的列表。一个叫DumpingLexicon的程序将这个列表和由索引器生成的词典比较构造出搜索器所用的新词典。搜索器由网络服务器运行，利用由DumpingLexicon构造的词典和倒排索引还有PageRank来回应查询。
4.2 主要的数据结构
Google的数据结构是经过优化的，所以能在少量开销的条件下爬行、索引、搜索大规模的文档集。虽然几年来CPU和块输入输出的速率都由显著的提高，但是一次磁盘寻道仍然需要10毫秒来完成。Google的设计尽可能地避免了磁盘寻道开销，这就对数据结构的设计产生了相当大的影响。
4.2.1 BigFiles
BigFiles是跨越多个文件系统的虚拟文件，可由64位整数寻址。在多文件系统之间空间分配是自动处理的。BigFiles包还可以处理文件描述符的空间分配和回收，因为操作系统提供的功能不够我们用的。BigFiles还支持基本的压缩选项。
4.2.2 仓库
仓库包含了所有的网页的HTML全文。每一页都用zlib（见RFC1950）压缩。对压缩技术的选择是在压缩速度和压缩率之间的权衡。我们选择了zlib的速度而没有选择bzip对压缩率的重要改进。和bzip大约4：1的压缩率相比zlib的压缩比为3：1。在仓库中，文档一个接一个地存储，用docID、长度和URL做为前缀，如图2。访问仓库不需要其它的数据结构了。这样有助于保持数据的一致性并且能显著简化开发工作；我们可以通过仅仓库和一个爬行器错误文件来重建所有其它的数据结构。
【图2：仓库数据结构】
4.2.3 文档索引
文档索引保留了每个文档的信息。它是一个定宽ISAM(Index sequential access mode)索引，以docID排序。其中每一项中的存储的信息包括了当前文档状态、指向仓库的指针、文档的校验和还有各种统计数据。如果一篇网页被抓取过，那它同时也会包括一个指针，指向一个变长的含有它的URL和标题的文件，这个文件被成为docinfo。否则这个指针就指向一个只含有URL的URL列表。这样的设计选择是因为我们希望有一个简洁的数据结构，并且能够在一次查询中只访问一次磁盘就得到一条记录。
另外还有一个文件用来将URL转换为docID。文件中是URL的校验和与对应docID的列表，并且以校验和排序。要找到某个特定的URL的docID，先计算出URL的校验和，再在校验和文件中做二分查找就能找到它的docID了。通过于这个文件的合并可以将URL批量转换成docID。这种技术被URL分解器用来将URL转换成docID。而批量转换的改进是至关重要的，因为否则我们就必须对每一个链接进行一次磁盘寻道，这意味着如果只有一个磁盘，要处理我们的3亿2千2百万个链接的数据集会花掉一个月的时间。
4.2.4 词典
词典有几种不同的形式。与以前的系统相比一个重要的变化是词典可以被放在内存中而不会在内存上花费很多。在现在的实现中我们可以将词典放在一台256M内存的机器上。目前的词典含有1千4百万词汇（虽然有一些罕见的词汇没有被放进去）。它的实现分两部分——一个词汇的列表（连接在一起但是用null分隔）和一个指针的散列表。对不同的函数，词汇列表有一些辅助信息，完整的讨论已经超出了本文的范围。
4.2.5 Hit列表
一个hit列表对应于一个特定的词汇在一个特定的文档中出现情况，包括了位置、字号、大小写等信息。Hit列表在前向索引和倒排索引中占了大部分空间。因此，使它们的表现形式尽量有效率很重要。我们考虑了几种可选的方案来对位置、字号和大小写信息进行编码——简单编码（用三个整数），紧凑编码（用手工优化的比特分配），和哈夫曼编码。最后我们选择了手工优化的紧凑编码，因为它占用的空间远小于简单编码，而对比特的操作也远少于哈夫曼编码。Hit的细节见图3。
【图3：前向索引、倒排索引和词典】
我们的紧凑编码每个hit使用两个字节。有两种类型的hit：特别hit与普通hit。特别hit包括了出现在URL、标题、链接文本或者元标签中的hit。普通hit指所有其它的hit。普通hit包括了一个大小写位、字号、和12比特的词汇在文档中的位置（位置超过4095的都被标为4096）。与文档其它部分的相对字号使用3个比特表示（实际上只使用了7个值，因为111表示特别hit）。特别hit由一个大小写位、字号字段被置为7标志特别hit、4比特编码用来表示特别hit的类型、和8比特的位置组成。对于链接hit，8比特的位置字段被分为4比特表示在链接中的位置，另外4比特用作对链接出现文档docID的散列。只要对于一个特定词汇没有那么多的链接，我们就可以进行一些有限的短语查询。为了能对位置字段和docID 的散列字段有更好的解决办法，我们考虑改进链接hit的存储方式。我们使用的相对于本文档其余部分的相对字号，因为在搜索的时候，你不会因为一篇文档的字号比另一篇大就特殊对它进行特殊排序。
hit列表的长度存储hit本身的前面。为了节省空间，hit列表的长度和前向索引中的wordID、倒排索引中的docID结合在一起。这就限制它各自只占8到5个比特（用点技巧可以从wordID中借8个比特）。如果长度超过了这些比特所能表示的范围，就有使用一个溢出码，其后的两个字节是实际的长度。
4.2.6 前向索引
前向索引实际上已经部分地排好序了。它被存储在一定数量的桶里（我们用了64个）。每个桶里维护这一定范围的wordID。如果一篇文档的的词汇落在了某个桶里，这篇文档的docID也被存储在桶里，后跟wordID的列表和与这些词对应的hit 列表。这种方案因为重复存储docID而需要更多的存储空间，但是在由于桶很多所以区别不大，且在整理器进行最后的索引操作的时候能够节省相当多的时间和降低编码复杂度。更进一步地，我们并非存储wordID本身，而是存储该wordID与所在桶最小wordID的相对位置。这样，我们就可以只将24比特用于未排序的桶里的wordID，留下8比特给hit列表的长度字段。
4.2.7 倒排索引
倒排索引包含了和前向索引相同的桶，但是倒排索引已经被整理器处理过了。对于每一个有效的wordID，词典都包含了一个指向该词所在桶里的指针。它同时指向一个docID的doc列表和与之对应的hit列表。这个doc列表表示了一个词汇在所有文档中的出现情况。
一个重要的问题是在doc列表中docID应该以什么顺序存储。一个简单的解决办法是以docID排序。这样可以方便合并不同的doc列表从而支持多词查询。另一个选择是按照词汇在每篇文档中的出现情况排序存储。这样做使得回应单一词汇查询显得轻易而举了，还使对多词查询的结果都接近起始处。但是，这样使合并要麻烦得多。同时，这也让开发工作更困难，因为每当要改动排序函数都要重建索引。我们的选择是两者的折衷，同时维护两组倒排桶——一组用来存储含有标题或者链接文字的hit列表，另一个存储所有的hit列表。这样，我们先在检查第一组桶，如果这些桶里没有足够的匹配我们就查找大桶。
4.3 爬行网络
运行一个网络爬虫程序是一项具有挑战性的任务。这里面有棘手的现象和可靠性问题，甚至还有社会问题。爬虫是最脆弱的程序，因为它涉及到与上百台服务器交互还有各种不在系统控制范围内的域名服务器。
为了覆盖上亿篇网页，Google有一个快速的分布式爬虫系统。一台URL服务器给数台（我们一般运行三台）爬虫提供URL。URL服务器和爬虫都是用Python实现的。每台爬虫一般同时维护300左右个的连接。只有这样才能使网页抓取速度有足够快的速度。在峰值速度下，四个爬虫的系统每秒钟能爬行上百篇网页。这就是说数据率在每秒600K左右。DNS解析是一个主要的性能瓶颈。每个爬虫都自己维护一个DNS缓存，这样就不必在爬取每篇文档前都去解析DNS。上百个连接中的每一个都可能处于几种不同的状态中：DNS解析、连接主机、发送请求和接受回应。这些因素使得爬虫程序成为系统中的一个复杂的组成部分。它使用异步IO来处理事件，还要有许多队列来转换页面抓取的状态。
似乎要运行一个连接超过50万服务器、产生上千万条日志的爬虫也会召来同样数量的Email和电话投诉。因为线上的认识太多，总有人会不知道爬虫是什么东西。几乎每天我们都会收到象这样的Email，“哇，你在我主页上看了这么多东西。你觉得我的网页怎么样？”也有一些人不知道机器人避免协议，还认为在网页上写上“本页版权所有，请勿索引”就可以让自己的网页不被索引到，不用说，爬虫程序很难明白这是什么意思。同时，由于涉及的数据太多，还会发生一些意想不到的事情。比如，我们的系统会去爬取一场网络游戏。结果使得在他们的游戏中产生不少垃圾消息！看起来这是个很容易解决的问题。但是这个问题在我们下载了上千万篇页面的时候才显现出来。由于网页和服务器经常变化，实际上，如果不在因特网上大面积地运行，是很难测试爬虫程序的。有些莫名其妙的问题还会不定地出现在整个网络地某一篇网页上引起爬虫的崩溃，甚至引起一些不可预见的错误行为。大面积访问因特网的系统必须被设计得非常健壮，并且要仔细测试。因为象爬虫这样的大型的复杂系统不定会出什么问题，所以还需要花些重要资源来阅读这些Email，并在问题发生的时候解决它。
4.4 索引网络
分析——任何被设计为运行在整个网络上的分析器都必须能够处理大量可能出现的错误。范围从HTML标签的打字错误到标签之间几K字节的零、非ASCII码字符、上百层的HTML标签嵌套，还有些超出任何人想象的各式各样的和解决办法一样多的错误会出现。为了得到最快速度，我们没有采用YACC生成上下文无关文法分析器，而采用了flex生成的词汇分析器，它只需要配有自己的堆栈。开发这样一个快速并且健壮的的分析器需要极大的工作量。
将文档索引到桶中——在分析完每一篇文档后，它都被编码放进一些桶中。每个词都被一个内存中的散列表——词典转化成wordID。有新词加入词典散列表时，会记录到日志文件中。一旦词汇都被转化为wordID后，它们在当前文档中的出现情况就会被转换成hit列表并被写入到正排桶中。索引阶段并行性的主要困难是词典需要被共享。我们没有共享词典，而是致力于对所有不在基础词典中的额外词汇写到日志中，我们的基础词典中有1千4百万条词汇。这样多个索引器就能并行运行，那个小日志文件可以由最后一个索引器来处理。
整理——为了产生倒排索引，整理器将每个正排桶按照wordID排序并分别为标题、链接、和全问生成倒排桶。一次只有一个桶被处理，所以它需要的临时存储空间很少。另外，我们将排序步骤并行化，我们只要简单的运行多个整理器就能尽可能地用上所有的机器，这样就能同时处理多个桶。因为桶太大没法装到内存里去，所以整理器进一步地将它们细分为一些基于wordID和docID能放进内存里的篮筐。然后整理器将每个篮筐装载到内存里来，将它排序，把其中内容写入到短倒排桶和全文倒排桶里去。
4.5 搜索
搜索的目的是高效地提供高质量的结果。很多商业搜索引擎似乎在效率方面有不小的进步。因此我们在研究中更多的关注质量问题，虽然我们相信我们的解决方案只需再稍微努力就能达到商业标准。Google查询评价的过程如图4。
1. 分析查询词。
2. 将词汇转换为wordID。
3. 在短桶中对每条词汇查找到doc列表的开头。
4. 扫描整个doc列表，直到有一篇文档匹配所有搜索项。
5. 为查询计算该文档的排序值。
6. 如果我们在短桶中，并且在任何doc列表尾部，就在全文桶中对每一条词汇查找到doc列表起始处，然后跳到第4步。
7. 如果我们不在任何doc列表的尾部，跳到第4步。
8. 根据排序值将匹配文档排序，然后返回前k个结果。
【图4：Google查询评价】
在响应时间上加上限制，一旦找到一定数目（目前是4万）的匹配文档，搜索器自动跳到图4中第8步。这意味着有可能会返回次优化的结果。我们现在正在研究新的方法解决这个问题。在以前，我们按照PageRank值将hit排序，似乎能够改善这种情况。
4.5.1 排序系统
Google比一般的搜索引擎对网络文档维护了更多的信息。每一个hit列表包含了位置、字体和大小写信息。另外，我们还考虑了链接文字里的hit和文档的PageRank的影响。在排序中综合考虑这些信息是很困难的。我们对排序函数设计是没有那个因素的影响过大。首先考虑最简单的情况——单一词汇的查询。为了给单一词汇查询中的一篇文档评级，Google先在这篇文档的hit列表找到中那个词。Google假设每一个hit都属于某种类型（标题、链接、URL、大字号普通文本、小字号普通文本……），每种类型都有自己的权重。这些权重构成了一个由类型索引的向量。Google将hit列表中每种类型的hit计数。然后将计数值转换为计数－权重。计数－权重先随着计数值线性增长但是很快就停止增长了，计数超过某个值时就与计数没有关系了。我们将计数－权重与类型－权重向量的内积作为该文档的IR得分。最后，由结合IR和分和PageRank给出该文档最后的评级。
对于多词查询，情况就复杂多了。多个hit列表必须同时扫描，才能使同一文档中相邻的hit的权值比离得远的hit的权值高。分布在不同hit列表中的hit分开匹配，以便相邻的hit一起匹配。对于每个匹配hit集，都要计算一个邻近度。这个邻近度基于hit在文档（或者链接）中的距离计算，但是被分为十个等级，范围从短语匹配到“毫不相干”。我们不仅对每种类型的hit计数，而且还对每种类型和邻近度计数。计数被转换成计数－权重，然后我们取计数－权重和类型—邻近度—权重的内积计算IR得分。所有这些数和矩阵都可以在一种特殊的调试模式下被显示出来。这些显示输出对排序系统的开发工作大有帮助。
4.5.2 反馈
排序函数有许多象类型－权重和类型－近似值－权重这样的参数。从这些参数重得出正确的结果就像在暗箱操作。为了达到目的，我们的搜索引擎重带有用户反馈机制。可信的用户可以对所有返回结果进行有选择的评价。反馈信息被保存下来。然后当我们修改排序函数的时候就能看出这种改变在以前排好序的搜索上的影响。虽然远不是那么完美，但是这能让我们了解排序函数中的改变会如何影响结果。
5 结果和性能
查询: bill clinton
http://www.whitehouse.gov/
100.00% (no date) (0K)
http://www.whitehouse.gov/
Office of the President
99.67% (Dec 23 1996) (2K)
http://www.whitehouse.gov/WH/EOP/OP/html/OP_Home.html
Welcome To The White House
99.98% (Nov 09 1997) (5K)
http://www.whitehouse.gov/WH/Welcome.html
Send Electronic Mail to the President
99.86% (Jul 14 1997) (5K)
http://www.whitehouse.gov/WH/Mail/html/Mail_President.html
mailto:president@whitehouse.gov
99.98%
mailto:President@whitehouse.gov
99.27%
The “Unofficial” Bill Clinton
94.06% (Nov 11 1997) (14K)
http://zpub.com/un/un-bc.html
Bill Clinton Meets The Shrinks
86.27% (Jun 29 1997) (63K)
http://zpub.com/un/un-bc9.html
President Bill Clinton – The Dark Side
97.27% (Nov 10 1997) (15K)
http://www.realchange.org/clinton.htm
$3 Bill Clinton
94.73% (no date) (4K)
http://www.gatewy.net/~tjohnson/clinton1.htm l
【图5：Google查询结果的采样】
一个搜索引擎最重要的评价标准就是查询结果的质量。虽然完整的用户评价已经超出了本问的范围，但以我们的经验看来在多数查询上Google的结果比一些主要的商业搜索引擎要好。举例说明PageRank、链接文本和近似值的应用，图5是在Google中一次搜索“bill clinton”得到的结果。这些结果说明了Google的一些特点。结果是由服务器聚集起来的。这样对在切换结果集的时候很有帮助。相当多数量的结果来自whitehouse.gov域，这正是对这样的搜索希望得到的结果。现在多数主要的商业搜索引擎都不会返回任何来自whitehouse.gov的结果，这不太对。注意第一个结果没有标题。这是因为我们没有抓取过它。Google是从链接文本来判断这对查询是一个好结果的。相似地，第十五个结果也是一个不能抓取的Email地址。它也是由链接文本产生的结果。
所有这些结果的质量都是相当高的，最后检查，没有一个是死链。这很大程度上是因为它们的PageRank值都很高。PageRank值由条中的红色部分的百分比表示。最后，没有一条只有bill没有clinton的结果，也没有一条只有clinton没有bill 的结果。这是因为我们十分重视词汇出现的接近度。当然，一个真正的搜索引擎质量测试需要由广泛的用户学习或者结果分析，这里我们的篇幅有限。相反，请读者们自己取亲身体验Google：http://google.stanford.edu/。
5.1 存储需求
除了搜索质量以外，Google的设计使之能够随着网络的增长而有效地调整成本。这其中就包括了存储效率方面的问题。表1列出了一些统计结果和Google的存储需求。由于应用了压缩计数，仓库的总大小大约是53G，是实际要存网页大小的三分之一多一点。按照当前的磁盘价格来看，仓库成为了成本低廉，有用的数据源。更重要的是，搜索引擎所需全部数据的总大小也是差不多的，大约55G。而且，多数查询只需要用到短倒排索引。有了文件索引优化的编码和压缩方式，一个高质量的搜索引擎就能在一台7G磁盘的新PC上运行了。
5.2 系统性能
有效地抓取和索引对搜索引擎来说是很重要的。这样信息才能保持更新，系统的变更也能被较快测试出来。对于Google，主要的操作是爬虫、索引和整理。要计算爬虫运行一次要多长时间是很困难的，因为有可能会因为磁盘空间不够、域名服务器崩溃或不知道什么原因而导致系统停止。要下载2千6百万的页面（包括错误页面），总共需要大约9天的时间。然而，一旦系统运行流畅了，速度会明显加快，只用63个小时就下载完剩下的1千1百万页面，平均每天4百万篇页面或者每秒48.5篇页面。索引器和爬虫器是自动运行的。索引器比爬虫器运行速度要快一些。这是因为我们在优化索引器上花了大量的时间，保证这不会成为系统的瓶颈。这些优化包括了文档索引的块更新和本地磁盘上重要数据结构的组织存放。索引器每秒中处理大约54篇页面。整理器可以完全并行运行；用4台机器，整个过程整理器需要用掉24小时。
5.3 搜索性能
现在我们研究的主要侧重点不在对搜索性能的改进上。当先版本的Google对大多数查询请求会在1到10秒内给出回应。这些时间主要被花在了磁盘IO和NFS上（因为磁盘是分布在多台机器上的）。并且，Google也没有任何这方面的优化，比如，查询缓存、对常用词的二级索引，也没有其它的什么常见的优化。我们倾向于通过分布式、硬件、软件和算法的改进来提高Google的速度。我们的目标是每秒钟处理几百个查询。表2有一些对当前版本Google响应时间的采样。我们对它们进行了重复搜索，这样就能看到IO缓存对查询的加速。
【表2：搜索时间】
6 结论
Google被设计成可扩展的搜索引擎。它的主要目标是在万维网飞速增长的情况下提供高质量的搜索结果。Google使用了一些技术来提高搜索质量，包括PageRank、链接文本和位置信息等。总之，Google有一个完整的体系结构来搜集网页、对它们建立索引、在它们的基础上提供搜索查询服务。
6.1 未来的工作
一个大型的网络搜索引擎是一个复杂的系统，还有很多工作需要做。我们目前的目标是改进搜索效率，并且扩展到大约1亿网页的规模上。一些简单的可以提高效率的改进包括查询缓存、磁盘空间智能分配和二级索引等。另一个需要研究的领域是增量。我们的智能算法需要判断那些旧网页需要重新抓取，那些新网页需要抓取。在[Cho 98]中已经有对这项工作的解决方案了。利用代理建立搜索数据库是一个很有前途的研究领域，因为有这方面的需求。我们计划增加一些简单的商业搜索引擎都提供的功能比如布尔运算符、取非运算和自动填充等。但是，还有一些点才刚刚开始探索，比如相关反馈和集群（Google现在支持一个简单的基于主机名的集群）。我们还计划提供用户上下文（如用户的位置）和结果摘要。我们还在研究扩展对链接结构和链接文本的利用。做过一些简单的试验后表明，可以通过加大用户主页或书签的权重来个性化PageRank。对于链接文本我们正在做试验将连接文本周围的文字考虑近来而不仅仅是链接文本本身。在网络搜索上引擎上有很丰富研究课题。我们这里列出的单字是在太多，所以我们认为未来的工作这一节在将来也不会变短的。
6.2 高质量搜索
现在网络搜索引擎用的用户面临的最大的问题就是他们所得结果的质量。查询结果往往就是在搞笑或者太离谱了，让用户们浪费宝贵的时间最后心灰意冷。比如在一个很流行商业搜索引擎上搜索“Bill Clinton”的头条搜索结果是“Bill Clinton Joke of the Day: April 14, 1997”。Google的设计是要提供高质量的搜索，即使网络高速增长也能很容易地找到信息。为了达到这一目标，Google大量利用了超文本信息，包括链接结构和链接（锚）文本。Google还用到了相邻度和字体信息。虽然评价一个搜索引擎是很困难的，我们主观地发现Google返回结果的质量比当前的商业搜索引擎的要高。通过PageRank分析链接结构使Google能够评价网页的质量。利用链接文本作为对链接所指向的网页的描述帮助搜索引擎返回相关的（某种程度上使高质量的）结果。最后，利用相邻度信息对提高一些查询的相关度有很大帮助。
6.3 可扩展的体系结构
除了搜索的质量，Google的设计是可扩展的。空间和时间上必须高效，当处理整个网络时有几个固定的因素是非常重要的。在实现Google的过程中，我们见到过CPU、内存访问、内存容量、磁盘寻道、磁盘数据率、磁盘容量和网络IO等各方面的瓶颈。Google已经改进了，在很多操作上能够解决这些瓶颈中的一些。Google的主要数据结构有效利用了可用的存储空间。另外，爬虫、索引和整理这些操作能够在一个星期之内有效地对网络的相当一部分——2千4百万网页建立索引。我们希望能在一个月内对1亿网页建立索引。
6.4 一个研究工具
除了要做一个高质量的搜索引擎，Google还是一个研究工具。Google搜集来的数据已经被用到投稿到学术会议的论文上，还有很多正在进行中。近来的研究比如[Abiteboul 97]显示了在本地不能访问网络的情况下的可能被回答的关于Web的查询的一些限制。这说明Google（或者一个类似的系统）不止是一个有价值的研究工具而且还是大量必要的应用程序之一。我们希望Google能成为搜索者和全球研究人员的资源，并在下一代搜索引擎技术中闪光。
7 致谢
Scott Hassan和Alan Steremberg对Google的开发至关重要。他们的才智是无可替代的，作者非常感谢他们。我们还要感谢Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman和Terry Winograd和全部WebBase开发组的支持和富有见解的讨论。最后我们要感谢IBM，Intel，Sun和投资者慷慨资助仪器。这里所说的研究是Stanford综合数字图书馆计划的一部分，由国家科学自然基金支持，合作协议号IRI-9411306。DARPA ，NASA，Interva研究，Stanford 数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。
引用
l Best of the Web 1994 – Navigators http://botw.org/1994/awards/navigators.html
l Bill Clinton Joke of the Day: April 14, 1997. http://www.io.com/~cjburke/clinton/970414.htm l.
l Bzip2 Homepage http://www.muraroa.demon.co.uk/
l Google Search Engine http://google.stanford.edu/
l Harvest http://harvest.transarc.com/
l Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview
l http://www.computer.org/pubs/expert/1997/trends/x1008/mauldin.htm
l The Effect of Cellular Phone Use Upon Driver Attention http://www.webfirst.com/aaa/text/cell/cell0toc.htm
l Search Engine Watch http://www.searchenginewatch.com/
l RFC 1950 (zlib) ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html
l Robots Exclusion Protocol: http://info.webcrawler.com/mak/projects/robots/exclusion.htm
l Web Growth Summary: http://www.mit.edu/people/mkgray/net/web-growth-summary.html
l Yahoo! http://www.yahoo.com/
l [Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997.
l [Bagdikian 97] Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557
l [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.
l [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.
l [Kleinberg 98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998.
l [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.
l [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
l 1994. http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps
l [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
l [Pinkerton 94] Brian Pinkerton, Finding What People Want: Experie The Second International WWW Conference Chicago, USA, October 17-20, 1994. http://info.webcrawler.com/bp/WWW94.html
l [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.
l [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/
l [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.
l [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.
Post a Comment