1、本文是谷歌创始人sergey和larry在斯坦福大学计算机系读博士时的一篇论文。发表于 1997年。在网络中并没有完整的中文译本，现将原文和本人翻译的寥寥儿句和网络收集的 片段（网友xfygx和雷声大雨点大的无私贡献）整理和综合到一起，翻译时借助了 ,因为是技术性的论文，文中有人量的合成的术语和较长的句了，有 些进行了意译而非直译。作为google辉煌的起始，这篇文章非常有纪念价值，但是文中提到的内容因年代久远， 已经和时下最新的技术有了不少差异。但是文中的思想还是有很多借鉴价值。因本人水平有 限，对文屮内容可能会佇理解不当之处，请您查阅英文原版。大规模的超文本网页搜索引擎的分析sergey
2、br i n and la wr e n c e pageco mp ut er sc i e n c e de p a r t me n tst a nf or d uni ve r s i t y, st anf or d, ca 94 3 05sergeyds st an ford edu and pages. st an ford edu摘要在本文中我们讨论googl e , 一个充分利用超文本文件结构进行搜索的人规模搜索引擎的原 型o google可以有效地对网络资源进行爬行搜索和索引，比目前已经存在的系统有更令人满意 的搜索结果。该原型的数据库包括2400 jj页面的全文和z间的链
3、接，可通过 h（ t p: / / googl e. stanford, edu/ 访问。设计一个搜索引擎是一种具挑战性的任务。搜索引擎索索引数以亿计的不同类型的网页并 每天给出过千万的杳询的答案。尽管大型搜索引擎对于网站非常重要，但是已完成的、 对于大型搜索引擎的学术上的研究却很少。此外，山于技术上的突飞猛进和网页的急剧增加， 在当前，创建-个搜索引擎和三年前不可同日而语。本文提供了一种深入的描述， 与web增殖快速进展今日创建 视b搜索引擎是三年前很大不同。本文提供了到目前为止，对 于我们大型的网页所搜引擎的深入的描述，这是笫一个这样详细的公共描述。除了如何把传统的搜索技术扩展到前所未有的
4、海量数据，还有新的技术挑战涉及到了使用 超文本中存在的其他附加信息产生更好的搜索结果。本文解决这样一个问题，如何建立一个可以 利用超文木屮存在的其他附加信息的实用的大型系统，同时我们也研究一下如何有效处理任何人 都能发布他们想发布的包含任何信息的人量口由链接的问题。关键字：互联网，搜索引擎，文献检索，pagerank, googl e1 简介（注：本文由两个版本较长的完整版本和一个较短的印刷的版本。完整版本提供在网络上和 会议的cd-rom上）。web给信息检索带来了新的挑战。e b上的信息量快速增长，同时不断 冇毫无经验的新用户来体验web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以 象
5、yahoo这样重要的网页或搜索引擎开始。人工维护的网站列表能有效的覆盖受欢迎的流行的 站点，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键 词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关 注想方设法误导自动搜索引擎。我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应 用超文本结构,提供高质量的查询结果,我们的系统命名为google,取名自googol的通俗拼 法，即io的loo次方，这和我们的h标建立一个大型搜索引擎较好的符合。1.1网络搜索引擎一升级换代:1994- 2000搜索引擎技术不得不快速升级跟上成倍增长的网
6、站数so 1 994年，第一个wb搜索引擎, wor i d w de web wor m （www）拥有110, （）00个网页和网站可访问文档的索引。到1994 年11月，顶级的搜索引挚声称可以检索到2力（webcraw） er ） 100力个网络文件（来自搜 索引擎监视）。可以预见到2000年，可检索到的网页将超过1（）亿。同时，搜索引擎的访问量 也会以惊人的速度增长。在1 997年的三 四刀份，wo r 1 d制de web wor m平均每天收到1500 个查询。在19 9 7年11月，altavista声称它每天要处理大约2 0 '而力个查询。随着网络 用户的增长，可以预见
7、到到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计冃 标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术，把它升级到如此人量的数据 上。i. 2 googl e :升级与网络建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快 并且保持是最新的版本。存储空间必须高效的存储索引和文档。索引系统必须能够高效地处理上 百亿gb的数据。处理查询必须快，达到每秒能处理成百上千个查询随看毗b的不断增长，这些任务变得越来越艰巨。然而硬件的性能和成本也在快速增长, 可以部分抵消这些困难。然而，还有几个值得例外，如磁盘的寻道时间，操作系统的效率。在设 计goog
8、l e的过程中，我们既考虑了网络的增长速度，又考虑了技术的更新。google的设计能 够很好的升级处理超大屋数据集。它能够高效地使用存储空间來存储索引。优化的数据结构能够 快速有效地存取（请参见4. 2节）。进一步，我们希望，相对于所抓取的文本文件和html网 页的数虽而言，存储和建立索引的代价尽可能的小（请参阅附录b）。对于象google这样的集 中式系统，采取这些措施得到了良好的系统可升级性。1. 3设计目标1.3.1改进搜索质量。我们的主要冃标是提高web搜索引擎的质so 1994年，有人认为建立全搜索索引就有可 能很容易找到任何东两。根据best o f t he wfe b 1994
9、 - na vi ga t or s ,"最佳导航服 务应更容易找到儿乎任何在网络上（已经输入的所冇数据）。”。然而19 9 7年的毗b就迥然 不同。任何最近使用搜索引擎的用户很容易证实索索引的完整性并不是唯一影响搜索引擎结果的 因素。用户感兴趣的搜索结果往往被“垃圾结杲”淹没。实际上，到1 997年11刀为止，四大 商业搜索引擎屮只有一个能够找到它自己（使用自己的搜索自己的名字时返冋的前十个结果屮有 它自己）。导致这一问题的主要原因是文档的索引数h增加了好儿个数量级，但是用户能够看的 文档数却没有増加。人们仍然只希望看前而的儿十个搜索结杲。因此，当集合増大时，我们就需 要高精确度的
10、工具（在返冋的前儿十个结果中，相关文档的数s） o由于是从成千上万个有点相 关的文档中选出几十个，实际上，我们希望相关的概念就是指最好的文档。高精确非常重要，英 至以响应（系统能够返回的有关文档的总数）为代价。令人i分乐观的的是利用超文木链接提供 的信息有助于改进搜索和其它应用ma r c hi or i 97 spcr t us 97 w? i s s 96 kleinberg 98。尤其是链接结构和链接文本，为相关性的判断和高质量筛选提供了大量的 信息。googl e既利用了链接结构又用到了链接文本（请参见2. 1和2. 2节）。1.3.2 搜索引擎的学术研究除了发展迅速，we b越来越商
11、业化。到199 3年，只冇1. 5 %，的网络服务是来0. com域名。 到19 9 7年，增长超过了 60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被 公司所有，很少发布技术细节。这就导致搜索引擎技术很人程度上仍然是暗箱操作，并倾向做广 告(请参阅附录a)。对于googl e來讲我们有一个的主要目标是推动学术领域在此方而的发展 和了解。另一个设计日标是给适合数日的人们一个实用的系统。对我们來说应用十分重要，因为一 些研究表明，现代网络系统屮存在大呈的有用数据。例如，每天有数千万个査询被执行。然而, 获得这些数据却非常困难，主要因为它们被认为有商业价值。我们的最终设计冃标是构建
12、一个体系结构，可以支持大型web数据上的-种新的研究活 动。为了支持新研究，google以压缩的形式保存了实际所抓到所有的文档。我们设计googl e 的主要h标z就是要建立一个环境使其彳也研究者能够很快进入这个领域，处理海量网络数据, 得到满意的结果，而通过其它方法却很难得到。系统在短时间内被建立起來，已经有几篇论文用 到了 google建立的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室 似的环境，在这里研究人员茯至学牛都可以対我们的海量网络数据设计或做有趣的实验。2. 系统功能google搜索引擎有两个觅要功能，帮助它产生高楮度的搜索结果。首先，应用0b的链接结 构计算
13、每个网页的质量等级值，这个等级称为pagerank,将在98页详细描述它。第二点，google利用超链接改进搜索结果。2. 1 page rank：带来网页排序网络的引用(链接)图形是重要的资源，却没有被现有的大多搜索引擎使用。我们建立了一个 包含5 18白万个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的 pagerank值，它是一个客观的标准，较好的符合人们主观的对一个网页重要程度的评价，由 此对应的是，pagerank值是一个较好的区分通过网络搜索关键字获得的结果的方法。建立的 基础是通过引用判断重耍性。对于人多数的主题，个简单的被限制为网页标题的文木匹配搜索 当使用
14、page rank区分时得到了极好的结果(从goog 1 e . s t anf or d. edu可以得到演示)。 对j* googl e主系统中的全文搜索,pagerank也有很大的帮助。2. 1. 1 pagerank计算的描述：文献引用理论应用到wb中，主要由引用或反向链接到给定页來计数。这会反映了该网页的重 要性和质虽的近似值。pagerank扩展了这种思想，不平等的计算所有页而上的链接并且通过 一个页而上的所有链接。pagerank定义如下：我们假设页而t1tn指向网页a (例如，被引用)。参数d是一个设定在0, 1 z间的制 动因子。我们通常设置d为0.85。在下一节有更多关于d
15、的详情，c (a)定义为网贞a指向 其它网页的链接数，网页a的pagerank值由下式给岀：pr( a) = ( 1 - d) + d ( pr(t1)/c(t1) + . + pr(tn)/c( tn)请注意pagerank涵盖所有网页的一个概率分布得來，因此所有网页pagerank和是1 o pagerank或pr( a)可使用一个简单的迭代算法来计算，和应对应月网页链接矩阵的主特 征向量。中等规模的网站计算26万网页的pagerank值要花费儿小时。还有一些技术细节超 出了本文论述的范围。2.1.2直觉的解释pagerank被看作用户行为的模型。我们假想一个“随机上网者”；随机地给他一个
16、网页；他 漫无h的地命中网页的链接，而从来不点“返回键”；最终他觉得烦了，乂从另一个随机的网页 从新开始。随机访问一个网页的可能性就是它的pagerank值。制动凶子d是随机访问-个网 页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子 d >|'o这允许个人可以故意地误导系统，以得到较高的pagerank值几卩变成不可能的。我们 还有其它的pagerank算法，见98页。另外的玄觉判断是一个网页有很多网页指向它，或者一 些pagerank值高的网页指向它，则这个网页很重要。直觉地，在wb中，一个网页被很多 网页引用，那么这个网页值得一看。一个网
17、页被彖yahoo这样重要的主页引用即使一次，也值 得一看。如果一个网页的质量不高，或者是死链接，象yahoo这样的主页不会链向它opage ra nk 处理了这两方血因素，并通过网络链接递归地传递。2. 2链接描述文字我们的搜索引擎对链接文本进行了特殊的处理。人多数搜索引擎把链接文字和它所链向的 网页联系起来。另外，把它和链接所指向的网页联系起来。这冇儿点好处。笫一，通常链接描述 文字比网页本身更精确地描述该网页。第二，链接描述文字可能链向的文档不能被文本搜索引擎 检索到，例如图像，程序和数据库。有可能使返冋的网页不能被抓到。注意那抓不到的网页将 会带来一些问题。在返回给用户前检测不了它们的有
18、效性。这种情况搜索引擎可能返回一个根木 不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出來的，所以此类的问题很少发 生。链接描述文字是对被引用网页的描述这个思想被用在world wde wb worm中，主耍 因为它有助于搜索非文本信息，能够用少呈的已f载文档扩大搜索范围。我们大量应用链接描述 文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为 必须处理大量的数据。现在我们能抓到24万个网页，la经检索到2 5 9万多个链接描述文字。2. 3其它功能除了 pagerank和应用链接描述文字外，googl e还有英他儿个功能。一，它有所有命屮数的位 置
19、信息，所以它町以在搜索屮广泛应用邻近性。第二，google跟踪一些可视化外表细节，例如 字的字体大小。更大的字的权重要高于其他的。笫三，知识库存储了原始的全文hl ml网页。3相关的工作网络检索研究的历史简短。wbr 1 d wdc毗b wor m （ww）是最早的搜索引擎后來出 现了一些用于学术性的搜索引擎，现在它们中的人多数被上市公司拥有。与web的增长和搜索 引擎的重要性相比，有关当今搜索引擎技术的优秀论文相当少。根ffimchael mauldin（lycos inc的首席科学家），“各种各样的服务（包括lycos ）非常关注这些数据库的 信息。”虽然在搜索引擎的某些特点上做了大量丁作
20、。具有代表性的工作有，对现有商业搜索引 擎的结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤 其在有组织机构集合方而。在下而两节，我们将讨论在信息检索系统中的哪些领域需要改进以便 更好的工作在web上。信息检索系统诞生在几年前,并发展很好。然而,大多数信息检索系统的研究针对的是受控制的 同质集合，例如，主题相关的科学论文或新闻故事。实际上，信息检索的主要基准，用小规模 的、冇组织结构的集合作为它们的基准。大型文集基准只有2（）gb,相比z下，我们抓到的24 万个网页占147gbo在trec ±工作良好的系统,在we b j：却不一定产生好的结果。例如，标
21、 准向量空间模型企图返冋和查询请求最相近的文档，把查询请求和文档都看作由出现在它们屮的 词汇组成的向暈。在亚b环境下，这种策略常常返回非常短的文档，这些文档往往是杳询词再 加几个字。例如，查询"bi 1 1 cl i nt on w ,返回的网页只包含“bi 1 1 cl i nt on sucks ", 这是我们从一个主要搜索引擎屮看到的。网络上有些争议，用户应该更准确地表达他们想査询什 么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象“bi ii clinton ” 这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。像所给的例
22、子, 我们认为信息检索标准需要发展，以便有效地处理wb数据。3. 2有组织结构的集合与网络的不同点web是完全无组织的异构的大量文档的集合。web中的文档无论内在信息还是隐含信息都存在 大量的杲构性。例如，文档内部就用了不同的语言（既有人类语言乂有程序），词汇（ email地址，链接，邮政编码，电话号码，产品号），类型（文本，html, pdf,图像，声 音），有些其至是机器创建的文件（log文件，或数据库的输出）。可以从文档中推断出 來，但并不包含在文档中的信息称为隐含信息。隐含信息包括來源的信誉，更新频率，质量，访 问量和引用。不但隐含信息的 可能來源各种各样，而且被检测的信息也大不相同，
23、相差可达好 几个数量级。例如，一个重要主页的使象yahoo每天浏览数达到上冇力次，于此相比无 名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。web 与有组织结构集合之间的另外一个明显区别是，事实上，向web ±传信息没有任何限制。灵活 利用这点可以发布任何对搜索引擎影响重大的信息，使路山阻塞，加上为牟利故意操纵搜索引 擎，这些已经成为个严觅的问题。这些问题还没有被传统的封闭的信息检索系统所提出來。它 关心的是元数据的努力，这在wb搜索引擎屮却不适用，因为网页中的任何文本都不会向用户 声称金图操纵搜索引擎。英至有些公司为牟利专门操纵搜索引擎。4系统分析首
24、先，我们提供高层次的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应 用：抓网页，索引，搜索将会深度探讨。图1 .高层次google体系结构4. 1 googi e结构概述这一节，我们将看看整个系统工作方式的高水平综述，见图1。本节不讨论应用和数据结构，在 后几节屮讨论。为了效率大部分googl e是用c或c+实现的，既可以在solaris也町以在 li nux ±运行。google系统屮，网络爬虫（下载网页）是由儿个分布式crawlers完成的。 个url服务器负责向c r a wl e r s提供url列表。抓来的网页交给存储服务器s t or e s e r ve
25、 r o 然后，山存储服务器压缩网页并把它们存到知识库中。每个网页都冇一个id,称作docid,当 新url从网页中分析出时，就被分配一个docldo由索引器和排序器负责建立索引index functiono索引器从知识库中读取文档，对其解压缩和分析。每个文档被转换成一组词的出现 情况，称作命中hitso hits纪录了词，词在文档中的位置，最接近的字号，大小写。索引器 把这些hits分配到一组桶barrel中，产生经过部分排序后的索引。索引器的另一个重要功能 是分析网页中所有的链接，将有关的重要信息存在链接描述anchors文件中。该文件包含了足 够的信息，可以用来判断每个链接链出链入节点的
26、信息，和链接文木。url分解器resol ver 阅读链接描述anchors文件，并把相对url转换成绝对url ,再转换成docid。为链接描述 文本编制索引，并与它所 指向的docl d关联起來。同时建立由docid对组成的链接数据库。 用于计算所有文档的page rank值。用docid分类后的barrels,送给 排序器sort er，再 根据wo r d i d进行分类，建立反向索引i nver【ed i ndex。这个操作要恰到好处，以便儿乎不 需要暂存空间。排序器还给ill docid和偏移量列表，建立反向索引。一个叫dumplexi con的 程序把这 个列表和山索引器产牛的字
27、典结合在一起，建立一个新的字典，供搜索器使用。这个 搜索器就是利用一个wb服务器，使用由dumplexi con所生成的字典，利用上述反向索引以 及页面等级pagerank来回答用户的提问。4. 2主要数据结构经过优化的googl e数据结构，能够用较小的代价抓取大量文档，建立索引和查询。虽然近儿 年cpu和输入输出速率迅速提高。磁盘寻道仍然需要1() ms。任何时候google系统的设计都 尽可能地避免磁盘寻道。这対数据结构的设计影响很大。4. 2. 1 大文件bigfiles是跨越多个文件系统的虚拟文件，用长度是64位的整型数据寻址。多文件系统之间 的牢间分配是自动完成的。bigfiles
28、包也处理文件描述符的分配。由于操纵系统不能满足我 们的需要,bigfiles也支持基本的压缩选项。4. 2. 2 知识库知识库包含每个网页的全部html。每个网页用zl i b (见rfc1 9 50 )压缩。压缩技术的选择 既耍考虑速度又耍考虑床缩率。我们选择zl i b的速度而不是压缩率很高的bzip。知识库用 bzip的压缩率接近4： 1。而用zlib的压 缩率是3： i。文档一个挨着一个的存储在知识库 屮，前缀是docid,长度，url,见图2。访问知识库不需耍其它的数据结构。这有助于数据一 致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。4. 2
29、. 3文档索引文档的索引保持每个文档有关的信息。它是固定的宽度isam(索引顺序访问模式)索引。每 条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档己 经被抓到，指针指向doci nf o文件，该文件的宽度可变，包含了 url和标题。否则指针指向包 含这个url的url列表。这种设计考虑到简洁的数据结构，以及在查询屮只需要一个磁盘寻道 时间就能够访问一条记录。述有一个文件用于把url转换成docldo它是url校验和与相应 docid的列表，并按照校验排序。要想知道某个url的docl d,需要计算url的校验和,然 后在校验和文件中执行二进制查找，找到它的d
30、ocid。通过对这个文件进行合并，可以把一批 url转换成对应的docldo url分析器用这项技 术把url转换成docl do这种成批更新的模 式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，3 22 口万个链接的数据集 合将花费一个多月的时间。4. 2. 4辞典词典有几种不同的形式。和以前系统的重要改进是，词典対内存的耍求可以在合理的价格内。当 前实现中，一台256m内存的机器就可以把词典装入到内存中。现在的词典包含14力词汇（虽 然一些很少用的词汇没有加入到词典中）。它执行分两部分一词汇表（申联在一起，但使用空值 隔开）和指针的哈希表的列表的实现。不同的两数词列表有一些辅助
31、的信息，超出了本文以详细 解释的范围。4.2.5点击列表一个命中列表对应着一个单词在一个文档中出现的位置、字体和人小写信息的列表。命中列表占 用了正向索引和反向索引的大部分空间，所以怎样尽可能有效的表示是很重要的。我们考虑了对 位置，字体和大小写信息的多种编码方式简单编码（3个整数），压缩编码（手工优化分配 比特）和霍夫曼编码（huffman coding）。命中（hit）的详情见图3。图3.正、倒排索引和词典我们的压缩编码每个命中用到两个字节（byte）。有两种命中:特殊命中（fancy hit）和聲通命中（plain hit） o特殊命中包括在url,标题，锚文木和meta标签上的命屮。英
32、他的都是普通命中。一个 普通的命中包括一个表示大小写的比特（bit）,字体大小，和12个bi（表示的单词在文件中的位置（所有比4095大的位置都被标示为4096）。字体在文档中的相对大小用3个比特表示（实际上 只用到7个值，因为111标示一个特殊命中）。一个特殊命中包含一个大小写比特，字体大小设 置为7用來表示它是一个特殊命中，4个比特用來表示特殊命中的类型，8个比特表示位置。对 于锚命中，表示位置的8个比特被分成两部分，4个比特表示在锚文木中的位置，4个比特为锚 文木所在docid的哈希（hash）值。市于一个词并没有那么多的锚文本，所以短语搜索受到一些 限制。我们期望能更新锚命屮的存储方式
33、能让位置和docid哈希值能有更大的范围。我们使用在 个文档屮的相对字体大小是因为在搜索时，你并不希望对于内容相同的不同文档，仅仅因为一 个文档字体比较大而有更高的评级（mnk） o命中列表的心度存在命屮的前面。为了节省空间，命中列表的长度在止向索引中与wordid结 合，在反向索引中与docid结合。这样就将长度分别限制在8个比特和5个比特（有一些技巧可 以从wordid中借用8个比特）。如果长度超过了这个范围，会在这些比特中使用转义码，在接 下來的两个字节（byte）里才存放真正的长度。4.2.6正向索弓|正向索引实际上已经部分排序。它被存放在一系列的桶（barrels）里面（我们用了 6
34、4个）。每 个桶保存了一定范围内的wordid。如果一个文档包含了加于某个桶的单词，它的docid将被记 录在桶里而，片而接若一个wordid的列表和相应的命屮列表。这种结构需要一点多余空间，因 为存储了重复的docid,由于桶的数量很小，所以存储空间的差别很小，但是它能在排序器（sorter） 建立最终索引的时候大大节省时间并降低了程用复杂度。更进一步，我们并没有存储完整的 wordid,而是存储每个wordid和对于其对应的桶里面最小wordid的差距。这样我们只用到了 24个比特,从而为命中列表长度（hit list length）留出了 8个比特。4.2.7反向索引反向索引与止向索引有
35、着相同的桶，但是它们是先经过排序器处理过的。对每一个合法的 wordid,词典包含了一个指向对应的桶的指针。它指向一个docid的列表和和应的命屮列表。 这个文档列表显示了有这个单词出现的所有文档。一个重耍的事情是如何対这个文档列表排序。一个简单的方法是按照doc id排序。在多个单词的 查询中，这种方法可以快速地完成两个文档列表的归并。另一种方案是按照这个词在文档中出现 的评分(ranking)排序。这种方式使得单个词的杳询相当简单，并且多词杳询的返凹结果也很可能 接近开头。但是，归并要困难得多。而1,开发也会困难得多，因为毎次评分函数变动就需要重 新建立整个索引。我们综合了两种方案，设计了
36、两个倒排桶集合一个集合只包括标题和锚命 中，另一个集合包含所有的命中。这样我们首先检查第一个桶集合，如果没有足够的匹配再检杳 那个大一点的。4.3抓取网页运行网络爬虫是一项很仃挑战性的任务。这里不光涉及到巧妙的性能和可靠性问题，更重要的, 还有社会问题。抓取是一个很脆弱的应用，因为它需要与成百上千各种各样的web服务器和域 名服务器交互，这些都不在系统的控制范围之内。为了抓取儿亿网页，google有个快速的分布式爬虫系统。一个单独的url服务器(urlserver) 为多个爬虫(crawler,般是3个)提供url列表。url服务器和爬虫都用python实现。毎个爬虫 同时打开人概3()0个连
37、接。这样才能保证足够快地抓取速度。在高峰时期，系统通过4个爬虫每 秒钟爬取100个网页。这大概有600k每秒的数据传输。一个主要的性能压力在dns杳询。每 个爬虫都维护一个自己的dns缓存，这样在它抓取网页之询就不再需要每次都做dns杳询。几 白个连接可能处于不同的状态：查询dns,连接主机，发送请求，接受响应。这些因素使得爬 虫成为系统里一个复杂的模块。它用异步10来管理事件，用一些队列来管理页面抓取的状态。事实证明，爬虫连接了 50多万个服务器，产生了儿千万条日志信息，会带来大量的电子邮件和 电话。因为很多人在网上，他们并不知道爬虫是什么，因为这是他们第一次见到。儿乎每天，我 们都会收到这
38、样的电子邮件：“哇，你看了好多我站上的页面，你觉得怎么样？ ”也有很多人并 不知道爬虫禁用协议(robots exclusion protocol),他们认为可以通过在页面上声明“本页面受 版权保护，拒绝索引”就町以保护页面，不用说，网络爬虫很难理解这样的话。而且，山于涉及 到大量的数据，一些意想不到的事情总会发生。比如，我们的系统试图去抓取一个在线游戏。这 导致了游戏中出现大虽的垃圾消息！这个问题被证实是很容易解决的。但是往往我们在下载了儿 千万个页而z后这个问题才被发现。因为网络页而和服务器总是在变化中，在爬虫正式运行在大 部分的互联网站点之前是不可能进行测试的。不变的是，总有一些奇怪的错
39、谋只会在一个页面里 而出现，并j1.导致爬虫崩溃，或者更坏，导致不可预测的或者钮误的行为。需要访问大量互联网 站点的系统需要设计得很健壮并且小心地测试。因为大量像爬虫这样的系统持续导致问题，所以 需要大量的人力专门阅读电子邮件，处理新出现遇到的问题。4.4网站索引解析一任何被设计来解析整个互联网的解析器都必须处理大量可能的错误。从html标签里 面的错别字到一个标签里而上千字节的0, hk ascii字符，嵌套了儿百层的html标签，还有 人量超乎人想象的错谋和“创意”。为了达到最快的速度，我们没有使用yacc产生cfg (context free gramma,上下文无关文法)解析器，而是j
40、u flex配合它自己的栈生成了一个词法分析器。 开发这样一个解析器需要大量的工作才能保证它的速度和健壮。为文档建立桶索引每一个文档解析过后，编码存入桶里而。每一个单词被内存里的哈希表 词典转化成一个wordido词典哈希表新加的内容都被记录在一个文件里。单词在被转化成 我word id的时候，他们在当前文档中的出现会被翻译成命中列表，并写入正排桶(forward barrels) 中。建立索引阶段的并行操作丄要的困难在于词典需要共享。我们并没有共享整个词典，而是在 内存里保存一份基本词典，固定的1千4百万个单词，多余的词写入一个日志文件。这样，多个 索引器就可以同时运行，垠后由一个索引器来处
41、理这个记录着多余单词的小11志文件。排序为了产生倒排索引，排序器取岀各个正排的桶，然后根据wordid排序来产生一个标题 和锚命屮的倒排桶，和-个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而丄l, 我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处 理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordid和docld将它们进步分 割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短 的倒排桶和完整的倒排桶。4.5搜索搜索的日标是高效地返冋高质量的结果。很多人型的商业搜索引擎在效率方面看起來都有很人的
42、 进步。所以我们更专注于搜索结杲的质虽，但是我们相信我们的解决方案只要花一点精力就可以 很好的应用到商业的数据上。google的查询评估流程如图40为了限制响应时间，一口某个数量(现在是40,000)的匹配文档被找到，搜索器自动跳到图4屮的 第8步。这意味着有可能返冋次优的结杲。我们现在在研究新的方法来解决这个问题。在过去, 我们根据pagerank值排序，冇较好的效果。1. 解析査询(query)。2. 把单词转化成word id o3. 从每个单词的短桶文档列表开始査找。4. 扌描文档列表肓-到有一个文档匹配了所有的搜索词语。5. 计算这个文档对应于查询的评分。6. 如果我们到达短桶的文档
43、列表结尾,从每个单词的全桶(full barrel)文档列表开始査找,跳到笫 4步。7. 如果我们没有到达任何文档列表的结尾，跳到第4步。8. 根据评分对匹配的文档排序，然后返回评分最高的k个。图4 google杳询评估4.5评分系统google比典型的搜索引擎维护了根多的web文档的信息。每一个命中列表(hitlist)包含了位置, 字体和大小写信息。而且，我们综合考虑了超链接文本命中和页面的pagerank值。把所有的信 息综合成-个评分是很因难的。我们设计了评分函数保证没有一个因素有太人的影响。首先，考 虑简单的悄况一个单词的查询。为了对一个单词的查询计算文档的分值，google tf先
44、为这 个单词杳看这个文档的命中列表。google将命中分为不同类型(标题，锚，url,普通文木大 字体,普通文本小字体,)，每一种类型都有自己的类型权重值(type-weighl)。类型权重 值构成一个由类型寻址(indexed)的向量。google数出命中列表屮每种类型命中的数虽。毎个 数量转化成一个数量权重(coimtweight)。数量权重开始随着数量线性增长，但是很快停止增 长，以保证单词命中数多于某个数量之后对权重不再有影响。我们通过数量权重向量和类型权重 向虽的点乘为-个文档算出一个ir分数。最后这个ir分数与pagerank综合产生这个文档最终 的评分。对于-个多词搜索，情况要更
45、复杂。现在，多个命屮列表必须一次扫描完，这样一个文档中较近 的命中才能比和距较远的命中有更高的评分。多个命中列表里的命中结合起來才能叽配出相邻的 命屮。对每一个命中的匹配集(matched set),会计算出一个接近度。接近度是基于两个命屮在文 档(或锚文木)中相隔多远计算的，但是被分为10个等级从短语匹配到“一点都不近”。不光 要为每一种类型的命中计数，还要为每一种类型和接近度都计数。每一个类型和接近度的组冇一 个类型接近度权重(type-prox-weight) 0数量被转化成数星权重。我们通过对数量权重和类型 接近度权觅做点乘计算出ir分值。所有这些数字和矩阵都会在特殊的调试模式卜与搜索
46、结果一 起显示出来。这些显示结果在开发评分系统的时候很有帮助4.5.2反馈评分函数有很多参数比如类型权重和类型接近度权重。找出这些参数的权重值简氏就跟妖术一 样。为了调整这些参数，我们在搜索引擎里有一个用户反馈机制。一个被信任的用户可以选择性 地评价所有的返回结果。这个反馈被记录下来。然后在我们改变评分系统的时候，我们能看到修 改对z前评价过的搜索结果的影响。尽管这样并不完美，但是这也给我们一些改变评分函数來影 响搜索结果的想法。5结果与表现衡量个搜索引擎放觅耍的标准是其搜索结果的质量。虽然如何做个完整的用户评估超越了本 文的范围，但是我们在google身上得到的经验，表明它提供结果，比主要商
47、用搜索引擎对绝大 多数搜索提供的结果更好。图表4表示的google对于搜索“比尔.克林顿”的结果，作为一个例 子可以说明,对pagerank, anchor text (关键词)proximity (相似度)的使用。这样的搜索结 果显示了 google的特色。搜索结果被服务器串联在一起。这样的方法当在需要对结果集筛选时 非常有用。很大数量的结果会来自域名,有理山相信这个来源含冇木次该搜索中 被期望找到的结果。当前，绝大多数主要的商用搜索引擎不会返冋任何來口 的结 果，更不用说正确的结果。注意，笫一个搜索到的连接没有标题，是因为它不是抓取得
48、结果，而 是google基于anchor text决定这个结果是杳询所期望得到的好结果。同样的，第15号结果是一 个电子邮件地址，当然这也是基于超链接的结果，而非可抓取得结果。所有结果都是合理的高质量页而，而口最后检查，没有坏连接。这主要归功于他们有很高的 pageranko pagerank的百分比使用红色条形图表示。最后，这里的结杲中，没有只有bill没有 clinton或只冇clinton没冇bill的，这是因为我们在关键词出现时使用了非常重要的proximity。 当然对-个实际的对搜索引擎的质量测试应该包括广泛的对用户研究或者对搜索结果的分析，但 是我们没冇时间做以上析。但是我们邀请
49、读者在/flp 口己测试google0 5.1存储需求除搜索质屋外，gooogle被设计为能够消化互联网规模不断增长带來的效能问题。一方而，使用 高效存储。表一是对google的统计与存储需求的详细分类，由于压缩厉的存储体积为53gb, 为源数据的三分z多一点。就当前的硬盘价格来说可以为有用资源提供廉价的相关存储设备。 更重耍的是，搜索引擎使用的所有数据的总合需要相应的存储人约为55gb。此外，人多数查询 能被要求充分使用短反向索01 short inverted index,在更好的编码与压缩文档索引府，一个高质 暈的网络搜索引擎可能只需要一
50、台有7gb存储空间的新电脑。5.2系统性能这对搜索引擎的抓取与索引来说很重耍。这样信息被转化为数据的速度以及系统主要部分改变后 被测试的速度都和对更快。就google来说，主要操作包括：抓取，索引和排序。一硬盘被填 满、或命名服务器助溃，或者英它问题导致系统停止，都很难度量抓取所需耍化费的时间。全部 花费在下载2千6百力个页面包括错误页面的时间大概是9天。但是如果系统运行更为流畅， 这个过程还可以更快，最后的1千i百个页面只使用了 63个小时，平均4百力每天，每秒48.5 页。索引的运行速度快于抓取速度的巫要原因是我们花费了足够的时间来优化索引程序，使它不 要成为瓶颈。优化包括对本地硬盘上的文
51、档的索引进行大规模的升级和替换关键的数据结构。索 引的速度达到人概54页每秒。排序可以完全平行作业，使用四台机器，整个处理时间花费近24 个小时。5.3搜索性能提高搜索性能并不是本次我们研究的重点。当前版本的google返冋多数查询结果的时间是1到 1（）秒。这个时间主要受到硬盘k）以及nfs网络文件系统，当硬盘安置到许多机器上时使用的 限制。进一步说，google没有做任何优化，例如查询缓冲区，常用词汇子索引，和其它常用的 优化技术。我们倾向于通过分布式，硕件，软件，和算法的改进来提高google的速度。我们的 口标是每秒能处理几百个请求。表2有几个现在版* google响应查询时间的例子。
52、它们说明10 缓冲区对再次搜索速度的影响。6结论google设计成可伸缩的搜索引擎。主要目标是在快速发展的world wide web上提供高质量的搜 索结果。google应用了一些技术改进搜索质量包括pagerank,链接描述文字，相邻信 息。进一步说，google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。6.1未来的工作人型web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的fl标是提高搜索效率，覆 盖大约10000（x）00个网页。一些简单的改进提高了效率包括请求缓冲区，巧妙地分配 磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些ih网
53、 页需耍重新抓取，哪些新网页需要被抓取。这个日标已经由实现了。受需求驱动，用代理cache创建搜索数据库是一个仃前途的研究领域。我们计划加一些简单的已经被商业搜索 引擎支持的特征，例如布尔算术符号，否定，填充。然而另外一些应用刚刚开始探 索，例如相关反馈，聚类（google现在支持简单的基于主机名的聚类）。我们还计划支持用户 上下文（彖用户地址），结果摘要。我们正在扩大链接结构和链接文本的应用。简单 的实验证明，通过增加用户主页的权重或书签，pagerank可以个性化。对于链接文札 我们正 在试验用链接周围的文木加入到链接文本。web搜索引擎提供了丰富的研究课题。如 此z多以至于我们不能在此一
54、一列举，因此在不久的将来，我们希望所做的工作不止木节提到的。6.2高质量搜索当今web搜索引擎用户所而临的最大问题是搜索结果的质量。结果常常是好笑的，并且超出用 户的眼界，他们常常灰心丧气浪费了宝贵的时间。例如，一个最流行的商业搜索引擎搜索 u bill clilltonw 的结果是 the bill clinton joke of the day: april 14, 1997。google 的设计目标 是随着web的快速发展提供高质量的搜索结果，容易找到信息。为此，google大量应用超文木信息包括链接结构和链接文本。google还用到了和邻性和字号信息。评 价搜索引擎是困难的，我们主观地
55、发现google的搜索质量比当今商业搜索引擎高pagerank 分析链接结构使google能够评价网页的质量。用链接文木描述链接所指向的网页有助于搜索引 擎返回相关的结果（某种程度上提高了质量）。最后，利用相邻性信息大 大提高了很多搜索的相关性。6.3可升级的体系结构除了搜索质量，google设计成可升级的。空间和时间必须高效，处理整个web时固定的儿个因 素非常垂要。实现google系统，cpu、访存、内存容虽、磁盘寻道时间、磁盘吞吐量、磁盘容量、网络10都是瓶颈。在一些操作屮，已经改进的google克服了一些瓶颈。google 的丄耍数据结构能够有效利用存储空间。进一步，网页爬行，索引，排
56、序已经足够建立大部分 web索引，共2千四百万个网页，用时不到一星期。我们希望能在一个月内建立一亿网页的索 引。6.4研究工具google不仅是高质量的搜索引擎，它还是研究工具。google搜集的数据已经用在许多其它论文 屮，提交给学术会议和许多其它方式。最近的研究，例如，提出了 web查询的局限性 ,不需要网络就可以回答。这说明google不仅是重要的研究丄具，而且必不训少，应用广泛。 我们希望google是全世界研究者的资源，带动搜索引擎技术的更新换代。7致谢scott hassan and alan stereinberg评价google的改进。他们的才智无可替代,作者由衷地感谢他 们。
57、感谢 hector garcia-molina, rajeev motwani, jeff ullman, and terry winograd 和全部 webbase 开发组的支持和富有深刻见解的讨论。最后感谢ibm, intel, sun和投资者的慷慨支持，为我们 提供设备。这里所描述的研究是stanford综合数字图帖馆计划的一部分，山国家科学自然基金 支持,合作协议号iri-9411306o darpa , nasa, interva研究,stanford数字图书馆计划的工 业合作伙伴也为这项合作协议提供了资金。引用best of the web 1994 navigators htt
58、p://1994/avvards/navigatorsehtmlbill clinton joke of the day: april 14,1997. bzip2 homepage http:/www.muraroa>demon<co.uk/google search engine /harvest mauldin, michael l. lycos design choices in an internet search service, ieee expert interview http:/mvwec
