Google的开始－－剖析大规模超文本网络搜索引擎

66 阅读 0 评论 44 点赞

我是靠谱客的博主舒心鱼，最近开发中收集的这篇文章主要介绍Google的开始－－剖析大规模超文本网络搜索引擎，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

转载自：[url]http://www.yeeyan.com/articles/view/thunder/364[/url]
原作者: Sergey Brin and Lawrence Page译者: 雷声大雨点大 (Blog)

译者：本文是谷歌创始人Sergey和Larry在斯坦福大学计算机系读博士时的一篇论文。发表于1997年。Google的一切应该都起源与此。深入了解Google，深入了解互联网的未来，当读此文。我把全文分成6个部分，推荐到这里。有兴趣的朋友可以一起来翻译。

我没有发现本文的完整中译，只找到了这个片段，由xfygx朋友翻译了本文的第一部分，其他似乎没有全部完成。

所以，这部分译文是xfygx原作，而非我的翻译！我只是就自己的理解做了些改动。如果有幸xfygx朋友能看到我在他/她博客的留言，来我们译言，我非常希望能把本文转到他/她名下。

另外，如果您发现已有其他出色的完整中译版了，请告诉我们。免得译者们重复劳动。
摘要
在本文中，我们将介绍Google，一个充分利用超文本文件（译者：即HTML文件）结构进行搜索的大规模搜索引擎的原型。Google可以有效地对互联网（Web）资源进行爬行搜索（crawl）〔注 1〕和索引，比目前已经存在的系统有更令人满意的搜索结果。该原型的数据库包括2400万页面的全文和之间的链接，可通过[url]http://google.stanford.edu/[/url]访问。
设计搜索引擎是一项富有挑战的任务。搜索引擎为数以亿计的网页建立索引，而这些网页包含了同样数量级的不同词语。每天响应数千万计的查询请求。尽管大规模网络搜索引擎是很重要的，但在这个领域很少有理论研究。更由于技术的飞速发展和互联网的普及，今天这样的搜索引擎和三年前的搜索引擎会是非常不同的。本文对我们的大规模搜索引擎进行了深入的讨论，这也是目前为止我们所知道的公开发表的第一篇如此详细的讨论。
除了如何把传统的搜索技术扩展到前所未有的海量数据，我们还面临这样一个新的技术挑战：如何使用超文本文件所蕴含的扩展信息以产生更好的搜索结果。本文讨论了如何建立一个实用的大规模系统，以利用超文本文件中的额外信息。另外，我们也关注了如何有效处理超文本文件不可控的问题，因为人们可以随意发表超文本文件（译者：如个人网页）。
关键词
World Wide Web, Search Engines, Information retrieval, PageRank, Google
1.简介
互联网对信息检索（Information Retrieval）领域产生了新的挑战。网上的信息数量是在不断的快速增长，同时有越来越多对网络搜索毫无经验的新用户上网。在网上冲浪时，人们一般会利用网络的“链接图”（译者：想像每个网页是一个点，网页之间的链接是从一个点指向另一个点的边，这就构成了一张有向图。）。而这经常从一个人工维护的网址列表（如Yahoo!）或是一个搜索引擎开始。人工维护的列表有效覆盖了流行的主题，但这些是主观的，花费高昂，更新缓慢，并且不能覆盖全部的主题，特别是冷僻的主题。依赖关键词匹配的自动搜索引擎通常返回太多的低质量的匹配结果。更糟的是，一些广告商通过某些方式误导搜索引擎以试图吸引人们的注意力。我们建立了一个大规模搜索引擎来解决已存在系统的许多问题。它充分利用超文本文件所表达额外信息来提供更高质量的搜索结果。我们选择这个名字，Google，是因为它是googol（表示10的100次方)这个词的常用拼写法。而这个词的意义与我们建立这个大规模搜索引擎的目标是非常一致的。
1.1 互联网搜索引擎 -- 扩展：1994 - 2000
搜索引擎技术必须极大规模地扩展才能赶上互联网的发展步伐。在1994年,最早的 web搜索引擎之一，World Wide Web Worm(WWWW) [McBryan 94]已经索引了11万web页面和文档。到了1997年的11月，顶级的搜索引擎声称的索引的页面数量从2百万(WebCrawler) 到10亿(根据 Search Engine Watch)。可以想像到2000年，索引全部的Web将需要包含超过十亿的文档。同时，搜索引擎需要处理的查询请求也会有不可想像的增长。在1994年 3月到4月间，World Wide Web Worm平均每天收到1500个查询。而到了1997年的11月，Altavista声称　它平均每天要处理大约2千万的查询。随着web的用户和使用搜索引擎的自动系统数量的增加，到2000年，顶级的搜索引擎每天将会需要处理数以亿计的查询。我们的系统的目标是解决这些由搜索引擎大规模扩展所带来的问题，包括质量和可扩展性。
1.2 Google:与Web同步发展
即便建立一个适应今天互联网信息量的搜索引擎已经面临着许多的挑战。我们需要使用快速爬行搜索技术收集web文档并保持它们的及时更新；我们需要可以有效存储文档索引和文档自身（这不是必须的）的海量存储空间；我们需要可以有效处理数百GB数据的索引系统；我们还需要可以在一秒内处理成百上千的查询的计算能力。
这些任务都随着Web的增长而愈发变的困难。然而，硬件性能的提高和费用的降低可以部分的抵消这些困难。但某些方面是个例外，如硬盘数据读取的速度和操作系统的鲁棒性（译者：可以通俗地理解为稳定性）都没有显著提高。在设计Google的过程中，我们已经考虑到了Web 和技术这两方面的发展。Google被设计为可以适应极大数据量。它有效使用存储空间来保存索引。它的数据结构被优化以便可以快速和有效的存取数据（见 4.2节)。另外，我们认为，相对于文本以及HTML文档数量的增长，索引和存储花费它们的费用最终会下降(见附录B)。因此，Google这样的集中式（译者：而非分布到许多远程计算机，如P2P系统）搜索系统随着互联网的发展而扩容就成为可能。
1.3 设计目标
1.3.1 提高搜索质量
我们的主要目标是提高web搜索引擎的质量。在1994年，一些人认为用一个完整的搜索索引就可以很容易地找到任何信息。在1994年互联网最佳－－导航员上，有这样的话"最好的导航服务应该是使用户可以很容易的在Web上找到任何信息"。然而，到1997，这个任务仍是非常困难的。在最近使用搜索引擎的用户都可以很容易的证实索引的完整性并不是决定搜索结果质量的唯一因素。"垃圾结果" 经常会使用户找不到真正感兴趣的结果。实际上，到1997年的十一月，四个顶级搜索引擎中，仅仅只有一个可以在搜索时发现它自身(对查询自己名字的请求，返回结果中将自己排在结果中的前十名)。产生这个问题的主要原因之一是在这些搜索引擎的索引库中文档的数量成数量级地增长，而用户看这么多文档的能力却不可能这样增长。用户往往只看结果中的前数十个。因此，随着文档规模的增加，我们需要工具来提高查准率（在前十个结果中返回相关内容）。实际上，我们说的"相关"是指最好的那一份，因为可能会有几万份“稍微“相关的文档。查准率在我们的眼中是如此的重要，以至于我们甚至愿意为此损失一些查全率。最近的研究显示，超文本文件中的信息可以有助于提高搜索和其他应用[Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]。特别是网页链接的结构，以及链接本身的文字，为相关性判定和进行质量的筛选提供了许多信息。Google使用了网页链接结构和锚（译者：HTML中的语法，表示一个指向网页的链接）链接中的文字。（详见2.1和2.2节）
1.3.2 搜索引擎的理论研究
随着WEB的巨大发展，互联网也越来越商业化。在1993年，只有1.5%的web服务器是.com的域名。而到了1997年，这个数字已经变成了60%。同时，搜索引擎的从学术研究变成了商业性质。到目前为止，大多数的搜索引擎的开发都是由公司来进行的，很少有详细的技术资料被公开。这导致了这项技术带有了许多神秘的色彩，并且是以广告为主（见附录A）。对于Google，我们有一个非常重要的目标就是推动搜索引擎在学术界的发展和理解。
另外的重要的设计目标是建立一个可以让一定数量的用户实际使用的系统。用户使用对我们来说非常重要，因为我们认为真正利用了现代互联网系统的海量数据的研究才是最有价值的。比如现在每天有数千万用户查询，但由于这些数据被认为具有商业价值，很难拿来作学术研究。
我们最终的设计目标是建立一个可以支持在大规模互联网数据上进行研究活动的系统构架。为了支持研究活动，Google存储了全部的在爬行搜索中发现的实际数据，并压缩起来。主要的目标之一是建立一个环境，在这个环境中，研究者可以很快的利用这个难得的系统，处理web数据，产生令人感兴趣的结果。在短时间内系统就被建立起来，已经有一些论文使用了通过Google生成的数据库。还有许多其它的项目在进行之中。另外的目标是我们希望建立一个类似空间站的环境，使得研究者，甚至是学生可以在我们的大规模web数据上进行实验。

〔注 1〕爬行搜索，Crawl，是指搜索引擎会跟随网页间的链接从一个网页“爬行”到下一个网页。而对每一个网页的分析和记录，或者这个过程的结果，则称为“索引”。

2.系统功能

Google搜索引擎通过两个重要功能来产生高精确度的结果。第一，它利用互联网的链接结构为每个网页计算出一个高质量的排名。这个排名被称为PageRank[注一]，具体在Larry Page98年的论文[Page 98]中有详述。第二，Google利用链接本身来提高搜索结果的质量。

2.1 PageRank: 给互联网带来秩序

现有的搜索引擎在很大程度上忽略了一个重要资源－－把互联网看做是一个引用关系（链接关系）图（见第一部分的注解）。我们已经产生了包含5亿1千8百万这样的超文本链接（就是网页指向网页的链接）的地图－－这是对整个互联网的一个相当显著的采样。这样的地图让我们能快速计算网页的“PageRank”－－一个对于网页被引用程度的客观衡量，而被引用程度与人们对于网页重要性的主观认识也很好地吻合。由于这样的吻合，PageRank成为对用关键字搜索网页返回的结果进行排序的极好方式。对于最热门的分类，局限于网页标题进行简单的文字查找，PageRank排序后的搜索结果效果极好。而在整个Google系统中进行全文查找，PageRank的作用也是非常显著的。

2.1.1 PageRank 计算简述

学术文献的引用机制被应用到互联网上－－主要就是计算一个网页被引用，或被反向链接的次数。这给出了对一个网页重要性或质量的估计。PageRank进一步发展了这个想法：来自不同页面的链接被给以不同的权重，并依据一个网页上链接的个数正态化。PageRank的定义如下：
我们假定网页　A　有若干其他网页（T1...Tn）指向它（即引用关系）。参数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)可以通过一个简单的循环算法来计算。这对应于正态化后的互联网链接矩阵的主要艾根向量的计算。另外，2千6百万网页的PageRank可以在一台中型服务器上，通过几小时的计算完成。这里有很多细节超出了本论文的讨论范围。

2.1.2 直观解释

PageRank 可以被想像成一个对用户行为建立的模型。我们假想一个“随机上网者”；随机地给他一个网页；他漫无目的地点击网页的链接，而从来不点“返回键”；最终他觉得烦了，又从另一个随机的网页从新开始。在上述模型中，“随机上网者”访问一个页面的概率就是这个页面的PageRank。而阻尼系数d，则是我们的“随机上网者”在访问了一个页面后，觉得烦了，开始访问一个新的页面的概率。上述模型的一个重要变形是把阻尼系数d加到一个网页上，还是加到一组网页上。这个变形使得故意欺骗系统获得高排名的企图几乎变成不可能的。我们对PageRank有若干延伸，详见这里[Page 98]。

另一个直观的解释是如果有很多其他网页指向一个页面，或者其他有很高PageRank的网页指向这个页面，该页面应该有较高的PageRank。直觉告诉我们，如果一个网页被互联网上的很多其他网页引用，它应该是值得关注的。而那些只有一个引用的页面，如果它来自象Yahoo!首页，那大约这个网页也值得看看。如果一个网页质量不高或根本就是一个死链接，Yahoo首页多半不会链接它。PageRank　考虑了上述两种以及之间的各种情况，它用递归方式把网页的权重通过互联网的链接结构传播出去。

2.2 锚链接（Anchor，是HTML的语法，即网页链接）的文本

链接的文字在我们的搜索引擎中受到特殊处理。大多数搜索引擎把链接中的文本部分（比如keso这个链接中的keso）归属于这个链接所在的网页。而我们除此之外，还把它归属于这个链接指向的页面。这有几个好处。第一，锚链接对被指向网页的描述，通常比网页本身的描述更准确。第二，锚链接可能指向那些不能被建立文本索引的文档，如图片、程序、数据库。这使得现在不能爬行搜索的页面可以被搜索到了。注意，以前从未被爬行搜索过的页面可能会产生问题，因为它们的有效性从未被验证过。比如搜索引擎甚至会返回一个有链接指向，但其实根本不存在的页面。然而，由于我们可以对结果排序，这个问题很少会出现。

把锚链接中的文本传播到被指向的页面这个想法，在World Wide Web Worm [McBryan 94] 已经被实施了。主要用于对非文本文件的搜索，和把搜索结果扩展到更多下载文档。而我们使用锚链接，主要是因为它可以提供高质量的结果。有效使用锚链接在技术上是很难实现的，因为大量数据需要处理。在我们现在爬行搜索过的2千4百万网页中，我们为2亿5千9百万锚链接建立了索引。

2.3 其他功能
除了使用PageRank和利用锚链接中的文本外，Google还有其他一些功能。第一，它有所有网页的位置信息，因此在搜索过程中充分应用了接近程度。第二，Google　记录网页的一些视觉表现，如单词的字体大小。大字体的权重比小字体要高。第三，完整的原始HTML页面被保存下来（即Google的网页快照功能）。

[注一]　PageRank　可以译为网页排名，建议后面就用原文了。另外，Page　恰恰是Google创始人之一Larry Page的姓。

3相关工作
基于web的搜索研究有一段简短的的历史。万维网蠕虫( wwww )[ mcbryan 94 ]是第一个网上搜索引擎。但随后,产生了几个学院派的搜索引擎,其中有不少现在已经是公开的上市公司了。相比Web的增长和搜索引擎的重要性,现在几乎没有关于当前搜索引擎有价值的研究材料 [Pinkerton 94].。据迈克尔.茂丁( lycos公司首席科学家)[Mauldin] "各种服务(包括lycos )紧密的守卫着这些数据库" 。
不过,在搜索引擎的具体的特点上已进行了相当的工作。对现有商业搜索引擎产生的搜索结果的后处理已经取得了卓有成效的成果,或是产生小规模的“个性化的“搜索引擎。最终,有过不少针对信息检索系统的研究,尤其是对受控制的结果集的研究。在随后两节中,我们将讨论一些必须扩大研究的领域,以便更好地在Web上工作。

3.1信息检索
信息检索系统的研究,已经有很多年了,并且成果显著[Witten 94] 。然而,大多数信息检索系统的研究针对的是受控制的同质集合，例如,主题相关的科学论文或新闻故事。的确,信息检索的主要的基准,文本检索会议[TREC 96] ,用了一个相当小的，并且受控制的集合作为其基准。“非常大的语料库“; 基准只有20gb 大小，相较于我们搜索过的 2千4百万网页，有147gb 的数据量。在TREC 上工作很好的搜索引擎，拿到Web上来往往效果不佳。举例来说,标准向量空间模型试图返回和搜索条件最为近似的文件,假定搜索和文件都是各自文字定义的向量。对Web 而言,这种策略只会返回非常简短的文件，包含查询本身和几句话。举例来说,我们已经看到了一个主要的搜索引擎返回的一个页面仅仅含有“比尔.克林顿真糟“;和从“比尔.克林顿“搜索来的图片。有人争论到 ,在Web上用户应该更具体,更准确地指出他们要什么,并且在搜索查询中增添更多词。我们坚决反对这种立场。如果用户发出对“比尔克林顿“的搜索查询 ,他们应得到合理的结果,因为就这个话题存在着大量的高品质的资料。鉴于这一类的例子,我们认为标准的信息检索工作需要扩大范围，从而有效处理 Web。

3.2 Web和受控集合的不同

互联网 Web是一个广阔的充满完全不受控制的异构文件的集合。Web 上的文件,不但内部格式极其不同,而且外部元信息也未必可用。例如,文件内部的不同,有各自的语言(包括自然语言和编程语言),各自的词汇(电子邮件地址,链接,邮编,电话号码,产品号码)，文件格式的不同(文本格式, html格式, pdf格式,图像格式,声音格式),并且甚至可能是机器产生的(日志文件或者数据库的输出文件) 。在另一方面,我们定义文件的外部元信息，从这些信息就可以推断出一个文件的大概,但是元信息并不包含在文件中。文件外部元信息的例子,包括这样一些信息：来源的声誉,更新频率,质量,受欢迎程度和用法 , 和引用。不仅是外部元信息的可能来源千差万别,而且衡量的方式也存在很多不同数量级的差异。举例来说,比较从一个大型网站的主页得到的使用信息,如，雅虎，目前每天获得几百万的页面浏览量，而一个晦涩的历史文章,可能每10年才能被浏览一次。显而易见,搜索引擎必须严重区别对待这两个条目。

另一个Web 和受控集合的较大差异是,几乎没有限制控制人们在网上可以放什么。把这种灵活性的内容发布和产生巨大影响的搜索引擎结合起来，去吸引访问浏览量。并且很多公司通过故意操纵搜索引擎来赢利，日益成为一个严重问题。这个问题在传统的封闭的信息检索系统中一直没有发现。另外,有趣的是我们注意到web搜索引擎使得想通过元数据操纵搜索引擎的努力基本上失败了,因为网页上的任何文字如果不是用来呈现给用户的，就是被滥用来操纵搜索引擎。甚至有许多公司专门操纵搜索引擎以达到赢利的目的。

（断断续续地把它翻完了。第4部分是Google搜索引擎最核心的一块，有一些设计细节还不是很懂，希望能和大家一起探讨。翻译不当之处还请各位指出，谢谢。）
4 系统剖析（System Anatomy）
首先，我们对架构做一个高层的讨论。接着，对重要的数据结构有一个深入的描述。最后，我们将深入分析主要的应用程序：爬虫，索引和搜索。
4.1 Google架构概述
[img]http://infolab.stanford.edu/~backrub/over.gif[/img]

图1. Google高层架构
在这一部分，我们将对图1中整个系统是怎么运行的有一个高层的概述。这一部分没有提到应用程序和数据结构，这些会在接下来的几部分里讨论。考虑到效率，Google的大部分是用C或C++实现，可以在Solaris或者Linux下运行。
在Google中，网页抓取（下载web页面）的工作由分布式的爬虫（crawlers）完成。有一个URL服务器（图1中的URL Server）把需要抓取的URL列表发送给爬虫。网页抓取好之后被发送到存储服务器（图1中的Store Server）。接着存储服务器将抓取来的网页压缩并存放在仓库(repository)里。每一个网页都有一个与之相关的ID，叫docID。在一个网页里每发现一个新的URL，就会赋予它一个ID。索引功能由索引器（图1中的indexer）和排序器（图1中的sorter）完成。索引器有很多功能。它从仓库中读取，解压并分析文档。每个文档都被转化成一个词的集合，词出现一次叫做一个命中（hits）。每条命中记录了一个词，这个词在文档中的位置，字体大小的近似值以及大小写信息。索引器将这些命中分布到一系列“桶”（barrels）里面，建立一个半排序(partially sorted)的正排索引(forward index)。索引器还有一个重要的功能。它解析出每张网页里面的所有链接，并把这些链接的相关重要信息存放在一个锚(anchors)文件里。这个文件包含了足够的信息，以显示每个链接从哪里连接过来，链到哪里和链接的描述。
URL分解器（URLresolver）读取锚文件，将相对URL转化为绝对URL，再转化成docID。它为锚文本建立一个正排索引，并与锚指向的docID关联起来。它还产生一个有docID对组成的链接数据库。这个链接数据库哟功能来计算所有文件的PageRank值。
排序器(sorter)对按照docID排序的(这里做了简化，详情见4.2.5小节)“桶”(barrels)重新按照wordID排序，用于产生倒排索引(inverted index)。这个操作在恰当的时候进行，所以需要很少的暂存空间。排序器还在倒排索引中建立一个wordID和偏移量的列表。一个叫DumpLexicon的程序把这个列表与由索引器产生的词典结合起来，生成一个新的词典，供搜索器（searcher）使用。搜索器由一个Web服务器运行，根据DumpLexicon产生的词典，倒排索引和PageRank值来回答查询。
4.2 主要的数据结构
Google的数据结构经过了优化，这样大量的文档能够在较低的成本下被抓取，索引和搜索。尽管CPU和I/O速率这些年以惊人的速度增长，但是每一个磁盘查找操作仍需要大概10微秒才能完成。Google在设计时尽量避免磁盘查找，这一设计也大大影响了数据结构的设计。
4.2.1 BigFiles
BigFiles是分布在不同文件系统下面的虚拟文件，通过64位整数寻址。虚拟文件被自动分配到不同文件系统。BigFiles的包还负责分配和释放文件描述符（译者注：牵涉到操作系统底层），因为操作系统提供的功能并不能满足我们的要求。BigFiles还支持基本的压缩选项。
4.2.2 数据仓库（Repository）
[img]http://infolab.stanford.edu/~backrub/repos.gif[/img]

图2. 数据仓库的结构
数据仓库包括了每个web页面的整个HTML代码。每个页面用zlib（参见RFC1950）压缩。压缩技术的选择是速度和压缩比的一个权衡。我们选择zlib是因为它的压缩速度要比bzip快很多。在数据仓库上，bzip的压缩比是4：1，而zlib的是3：1。在数据仓库中，文档一个一个连接存放，每个文档有一个前缀，包括docID，长度和URL（如图2）。要访问这些文档，数据仓库不再需要其他的数据结构。这使得保持数据一致性和开发都更简单；我们可以仅仅通过数据仓库和一个记录爬虫错误信息的文件来重建其他所有的数据结构。
4.2.3 文档索引（Document Index）
文档索引保存了每个文档的信息。它是一个根据docID排序的定长(fixed width)ISAM（索引顺序访问模式Index sequential access mode）索引。这些信息被存放在每个条目(entry)里面，包括当前文档状态，指向数据仓库的指针，文档校验和(checksum)和各种统计数据。如果文档已经被抓取了，它还会包括一个指针，这个指针指向一个叫docinfo的变长(variable width)文件，里面记录了文档的URL和标题。否则，这个指针将指向一个URL列表，里面只有URL。这样设计的目的是为了有一个相对紧凑的数据结构，在一次搜索操作中只需要一次磁盘查找就能取出一条记录。
另外，还有一个文件用来将URL转化成docID。这个文件是一个列表，包括URL校验和(checksum)和对应的docID，根据校验和排序。为了找到某一个URL的docID，首先计算URL的校验和，然后在校验和文件里做一次二分查找，找到它的docID。URL转化成docID是通过文件合并批量操作的。这个技术是在URL分解器（URL resolver）把URL转化成docID时使用的。这种批量更新的模式很关键，因为如果我们为每个链接做一次磁盘查找，一个磁盘需要1个月的时间才能为我们的3.22亿条链接的数据集完成更新。
4.2.4 词典（Lexicon）
词典多种不同格式。与早前的系统相比，一个重要的变化是现在的词典可以以合理的成本全部放在内存里面。目前的实现中，我们把词典放在一个256M的主存里面。现在的词典有1.4千万单词（尽管一些非常用词没有被包含进来）。它由两部分实现——一个单词列表（连接在一起，但是通过空白nulls分开）和一个指针的哈希表(hash table)。单词列表还有一些附加信息，但是这些不在本篇文章的讨论范围。
4.2.5 命中列表（Hit Lists）
一个命中列表对应着一个单词在一个文档中出现的位置、字体和大小写信息的列表。命中列表占用了正排索引和倒排索引的大部分空间，所以怎样尽可能有效的表示是很重要的。我们考虑了对位置，字体和大小写信息的多种编码方式——简单编码（3个整数），压缩编码（手工优化分配比特）和霍夫曼编码（Huffman coding）。命中（hit）的详情见图3。
[img]http://infolab.stanford.edu/~backrub/barrels.gif[/img]

图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 正排索引（Forward Index）
正排索引实际上已经部分排序（partially sorted）。它被存放在一系列的桶（barrels）里面（我们用了64个）。每个桶保存了一定范围内的wordID。如果一个文档包含了属于某个桶的单词，它的docID将被记录在桶里面，后面接着一个wordID的列表和相应的命中列表。这种结构需要一点多余空间，因为存储了重复的docID，由于桶的数量很小，所以存储空间的差别很小，但是它能在排序器（sorter）建立最终索引的时候大大节省时间并降低了程序复杂度。更进一步，我们并没有存储完整的wordID，而是存储每个wordID相对于其对应的桶里面最小wordID的差距。这样我们只用到了24个比特，从而为命中列表长度（hit list length）留出了8个比特。
4.2.7 倒排索引（Inverted Index）
倒排索引与正排索引有着相同的桶，但是它们是先经过排序器处理过的。对每一个合法的wordID，词典包含了一个指向对应的桶的指针。它指向一个docID的列表和相应的命中列表。这个文档列表显示了有这个单词出现的所有文档。
一个重要的事情是如何对这个文档列表排序。一个简单的方法是按照docID排序。在多个单词的查询中，这种方法可以快速地完成两个文档列表的归并。另一种方案是按照这个词在文档中出现的评分(ranking)排序。这种方式使得单个词的查询相当简单，并且多词查询的返回结果也很可能接近开头（译者注：这句不是很理解）。但是，归并要困难得多。而且，开发也会困难得多，因为每次评分函数变动就需要重新建立整个索引。我们综合了两种方案，设计了两个倒排桶集合——一个集合只包括标题和锚命中（译者注：后面简称短桶），另一个集合包含所有的命中（译者注：后面简称全桶）。这样我们首先检查第一个桶集合，如果没有足够的匹配再检查那个大一点的。
4.3 网页抓取（Crawling the Web）
运行网络爬虫是一项很有挑战性的任务。这里不光涉及到巧妙的性能和可靠性问题，更重要的，还有社会问题。抓取是一个很脆弱的应用，因为它需要与成百上千各种各样的web服务器和域名服务器交互，这些都不在系统的控制范围之内。
为了抓取几亿网页，Google有一个快速的分布式爬虫系统。一个单独的URL服务器（URLserver）为多个爬虫(crawler,一般是3个)提供URL列表。URL服务器和爬虫都用Python实现。每个爬虫同时打开大概300个连接(connecton)。这样才能保证足够快地抓取速度。在高峰时期，系统通过4个爬虫每秒钟爬取100个网页。这大概有600K每秒的数据传输。一个主要的性能压力在DNS查询(lookup)。每个爬虫都维护一个自己的DNS缓存，这样在它抓取网页之前就不再需要每次都做DNS查询。几百个连接可能处于不同的状态：查询DNS，连接主机，发送请求，接受响应。这些因素使得爬虫成为系统里一个复杂的模块。它用异步IO来管理事件，用一些队列来管理页面抓取的状态。
事实证明，爬虫连接了50多万个服务器，产生了几千万条日志信息，会带来大量的电子邮件和电话。因为很多人在网上，他们并不知道爬虫是什么，因为这是他们第一次见到。几乎每天，我们都会收到这样的电子邮件：“哇，你看了好多我站上的页面，你觉得怎么样？”也有很多人并不知道爬虫禁用协议（robots exclusion protocol），他们认为可以通过在页面上声明“本页面受版权保护，拒绝索引”就可以保护页面，不用说，网络爬虫很难理解这样的话。而且，由于涉及到大量的数据，一些意想不到的事情总会发生。比如，我们的系统试图去抓取一个在线游戏。这导致了游戏中出现大量的垃圾消息！这个问题被证实是很容易解决的。但是往往我们在下载了几千万个页面之后这个问题才被发现。因为网络页面和服务器总是在变化中，在爬虫正式运行在大部分的互联网站点之前是不可能进行测试的。不变的是，总有一些奇怪的错误只会在一个页面里面出现，并且导致爬虫崩溃，或者更坏，导致不可预测的或者错误的行为。需要访问大量互联网站点的系统需要设计得很健壮并且小心地测试。因为大量像爬虫这样的系统持续导致问题，所以需要大量的人力专门阅读电子邮件，处理新出现遇到的问题。
4.4 网站索引（Indexing the Web）
解析——任何被设计来解析整个互联网的解析器都必须处理大量可能的错误。从HTML标签里面的错别字到一个标签里面上千字节的0，非ASCII字符，嵌套了几百层的HTML标签，还有大量超乎人想象的错误和“创意”。为了达到最快的速度，我们没有使用YACC产生CFG（context free gramma，上下文无关文法）解析器，而是用flex配合它自己的栈生成了一个词法分析器。开发这样一个解析器需要大量的工作才能保证它的速度和健壮。
为文档建立桶索引——每一个文档解析过后，编码存入桶里面。每一个单词被内存里的哈希表——词典转化成一个wordID。词典哈希表新加的内容都被记录在一个文件里。单词在被转化成我wordID的时候，他们在当前文档中的出现会被翻译成命中列表，并写入正排桶(forward barrels)中。建立索引阶段的并行操作主要的困难在于词典需要共享。我们并没有共享整个词典，而是在内存里保存一份基本词典，固定的1千4百万个单词，多余的词写入一个日志文件。这样，多个索引器就可以同时运行，最后由一个索引器来处理这个记录着多余单词的小日志文件。
排序——为了产生倒排索引，排序器取出各个正排的桶，然后根据wordID排序来产生一个标题和锚命中的倒排桶，和一个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而且，我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordID和docID将它们进一步分割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短的倒排桶和完整的倒排桶。
4.5 搜索（Searching）
搜索的目标是高效地返回高质量的结果。很多大型的商业搜索引擎在效率方面看起来都有很大的进步。所以我们更专注于搜索结果的质量，但是我们相信我们的解决方案只要花一点精力就可以很好的应用到商业的数据上。Google的查询评估流程如图4。
为了限制响应时间，一旦某个数量(现在是40,000)的匹配文档被找到，搜索器自动跳到图4中的第8步。这意味着有可能返回次优的结果。我们现在在研究新的方法来解决这个问题。在过去，我们根据PageRank值排序，有较好的效果。
解析查询（Query）。
把单词转化成wordID。
从每个单词的短桶文档列表开始查找。
扫描文档列表直到有一个文档匹配了所有的搜索词语。
计算这个文档对应于查询的评分。
如果我们到达短桶的文档列表结尾，从每个单词的全桶(full barrel)文档列表开始查找，跳到第4步。
如果我们没有到达任何文档列表的结尾，跳到第4步。
根据评分对匹配的文档排序，然后返回评分最高的k个。
图4 Google查询评估
4.5.1 评分系统（The Ranking System）
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 反馈（Feedback）
评分函数有很多参数比如类型权重和类型-接近度权重。找出这些参数的权重值简直就跟妖术一样。为了调整这些参数，我们在搜索引擎里有一个用户反馈机制。一个被信任的用户可以选择性地评价所有的返回结果。这个反馈被记录下来。然后在我们改变评分系统的时候，我们能看到修改对之前评价过的搜索结果的影响。尽管这样并不完美，但是这也给我们一些改变评分函数来影响搜索结果的想法。

5 结果与表现
衡量一个搜索引擎最重要的标准是其搜索结果的质量。虽然如何做一个完整的用户评估超越了本文的范围，但是我们在Google身上得到的经验，表明它提供结果，比主要商用搜索引擎对绝大多数搜索提供的结果更好。图表4 表示的 Google对于搜索“比尔.克林顿”的结果，作为一个例子可以说明，对PageRank, anchor text （关键词）,和proximity（相似度）的使用。这样的搜索结果显示了Google的特色。搜索结果被服务器串联在一起。这样的方法当在需要对结果集筛选时非常有用。很大数量的结果会来自域名whitehouse.gov，有理由相信这个来源含有本次该搜索中被期望找到的结果。当前，绝大多数主要的商用搜索引擎不会返回任何来自whitehouse.gov的结果，更不用说正确的结果。注意，第一个搜索到的连接没有标题，是因为它不是抓取得结果，而是Google 基于anchor text 决定这个结果是查询所期望得到的好结果。同样的，第15号结果是一个电子邮件地址，当然这也是基于anchor text的结果，而非可抓取得结果。
所有结果都是合理的高质量页面，而且最后检查，没有坏连接。这主要归功于他们有很高的PageRank。PageRank的百分比使用红色条形图表示。最后，这里的结果中，没有只有Bill没有Clinton 或只有 Clinton 没有Bill 的，这是因为我们在关键词出现时使用了非常重要的proximity。当然对一个实际的对搜索引擎的质量测试应该包括广泛的对用户研究或者对搜索结果的分析，但是我们没有时间做以上析。但是我们邀请读者在 [url]http://google.stanford.edu/flp[/url] 自己测试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缓冲区对再次搜索速度的影响。

另外一篇参考译文：[url]http://blog.csdn.net/fxy_2002/archive/2004/12/23/226604.aspx[/url]