男人们并不是特意惹你生气，我们只是被误解了。以下是对在婚姻中7种经典冲突中男性思维的解释。
根据国家统计局的调查（这总不会是假的吧），在68%的离婚案件中，女性胜诉。她们最流行使用的理由是行为，如果这词儿也流行的话（其实不然）。这暗示着两件可能人尽皆知的事情：第一，男人行为不捡；第二，很多女人在婚后几个月甚至几年后才慢慢明白这一点。这里看起来有不小的知识空白，没关系，简单普及一下，我就让你们明白了。我能够解释我们为什么会行为不检——或者，更确切的说，为什么你们认为我们行为不检，然而事实上，对我们来说，我们的行为是完全可以理解并符合逻辑的。
忘记东西
对于我们无法记住那些你们让我们记得的事情，有科学的原因可以解释。虽然女性大脑比男人的要小10%，其拥有的白质却比灰质多。白质主要用于记忆，而灰质更善于激活大脑进行重复而劳累的Xbox游戏。
这是基因构成，懂了吗？
你要记得：记不得不一定是件坏事儿。我们忘记说"我爱你"，我们忘记生日礼物。我们忘记去超市要买的东西，但是这些不代表我们不爱你们、不喜欢生日礼物或对买那些东西没兴趣，原因很简单，只能怪灰质。
看地图
"就是这条路。"
"为什么不停下来找个人问问呢？
"因为就是这条路。"
"可是我们已经走遍这个村子了。"
"我们没有。"
"有。"
有什么问题吗，姑奶奶们？没有啊，这不是我们在耍犟。是你们。你们和你们匮乏的同情心。我们知道自己错了，我们当然知道。但是我们要面子，我们的思维很简单，这一点，你们知道，我们也知道。承认输了，对我们来说是天大的耻辱，这与承认勃起障碍一样难。最重要的是，我们应该被允许兜圈子，直到我们自己走运或一次次的错了后，找到对的路。记住，永远一定不要说："我告诉过你停下来问问路的。"
你们就当我们是白痴，这样我们会对你们感激不缴，或许还会为你们准备不错的生日礼物——如果我们记得的话。不幸的是，我们通常记不得。
穿上这个我的屁股看起来丰满吗？
这也许是所有婚姻冲突中最不公正的事儿。你们不应该指望一个男人跟你们一整天的逛街，呆在过热的购物中心，周围充满了出着臭汗、无聊的人。有时候甚至等上几小时，站在试衣间外面，对这同样汗流浃背的无聊的男人，无奈的耸耸肩，而你却试穿了同样款式的19条裤子，还每次都问我们："穿这条，我的屁股是不是看起来大一些？"
虽然有着漫长而痛苦的回答这个恶魔问题的经历，我至今还未发现正确的回答。如果我们如实回答（"不是特别明显，我觉得还行"），你们会不说话，因我们不够积极。如果我们如实回答（"我不在乎你的屁股看起来怎么样，我们现在可以回去了吗？"），你会生气。如果我们撒谎（"天啊，真是太美了，你的屁股看起来好丰满啊！"），你会怀疑，然后再问我们问题，比如："你的意思是说我们可以回家了，是吧？"我们眼神的慌乱暴露了我们的意图，然后你们又让我们去另外一家商店。额的神啊！
请不要带我们去购物。你们穿什么我们都爱你们。只要正当的性感就行，但我们不想参与到购买的过程中。
DIY，以及为什么是我们的错？
在宜家之前，男人就能够DIY，现在我们也自认为可以。只是由于可拆装的瑞士货的到来，那些用一把艾伦六角把手无法解决的技术就失传了。但是问到关于奥克斯博湖，毕达哥拉斯定理或者Patsy
Kensit主演的电影中她的野兽使用的致命武器，我们可以立马告诉你。问到我们如何把插头装进非建筑墙内，我们也可以告诉你，只是我们的回答会不对。
在这里重要的是我们的热情。每年，在银行周末假期前，事故预防皇家协会都会公布一些令人震惊的统计数字，说明有多少男人在DIY时，经历了血淋淋的事故。今年，这些事故的第一号杀手工具是：刀子和解剖刀（导致了20000例急诊），锯子（15000例）最后是令人牙齿打颤的碾磨机（6500例）。"过度自信和知识的缺乏，"事故预防皇家协会的报道说，："是DIY事故的主要原因。"可是这不就是让你们对我们一见钟情的可爱特点之一吗？难道你们就不能不看功劳看苦劳吗？
看暴力电影
目前为止，你应该对婚姻关系中男人每天要做的事情所经历的那些害怕、紧张和痛苦有一点认识了吧？所以我们需要时间来放松。你们可以一遍遍念咒语似的说"能给我搓搓背吗？"来放松，我们就是看暴力电影。你们若是不想看，我们没意见。我们甚至不介意在浴室的小电视上看，以便让你看那该死的《飞黄腾达》（美国一档热门商业真人秀节目）。只是不要让我们看你们那些情节悲惨的古装剧，因为我们可能会哭，而男人是从不掉泪的。那样我们必须得面对自己的脆弱情感，那我们男人的面子往哪儿放？还是让我们赶紧往下说吧。
做爱以及其频率
最好是细水长流、毛毛雨常有，受不了要么旱死要么涝死。就像记忆一样，这个也是有科学根据的，而且是我们控制范围之外的。
看其他女人
还是科学的缘故，同样是我们不由自主的。根据《那不是因为你，而是生物原因》的作者Joe
Quirk的看法，男人和女人拥有相互排斥的繁殖系统。女人生成一个卵子需要29.5天，如果这个卵子受孕了，她们又得十月怀胎，然后是数月或数年的母乳喂养。然而，男人几秒钟内就可以产生300万只精子，如果观察野牛、鸟、猿类和你自己的狗，一般情况下，你会发现雄性大多淫荡而雌性比较挑剔。当代的男人，Silvio
Berlusconi（新当选的意大利总统，传出众多绯闻）除外，已经完成了从猿到人的转变，除了两个方面：不盖马桶盖，看其他女人。可是我们也为之付出了沉重的代价：一次次的去购物，和那些被扔在被子外面的漫漫寒夜。
总之，你们赢了，现在我们结案。
2009年8月12日星期三
google搜索原理论文的中文版
这篇文章中，我们介绍了google，它是一个大型的搜索引擎（of a large-scale
search
engine）的原型，搜索引擎在超文本中应用广泛。Google的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24'000'000个网页。我们可以从
http://google.stanford.edu/ 下载。
设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且每天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。
本文详细介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此详细。除了把传统数据搜索技术应用到如此大量级网页中所遇到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。
本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。
关键词 World Wide Web，搜索引擎，信息检索，PageRank, Google 1 绪论 Web
给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象Yahoo这样重要的网页或搜索引擎开始。大家认为List(目录)有效地包含了大家感兴趣的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。
我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。
1.1网络搜索引擎—升级换代（scaling up）：1994-2000
搜索引擎技术不得不快速升级（scale
dramatically）跟上成倍增长的web数量。1994年，第一个Web搜索引擎，World Wide
Web
Worm(WWWW)[McBryan94]可以检索到110，000个网页和Web的文件。到1994年11月，顶级的搜索引擎声称可以检索到2'000'000（WebCrawler）至100'000'000个网络文件（来自
Search Engine
Watch）。可以预见到2000年，可检索到的网页将超过1'000'000'000。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，World
Wide Web Worm 平均每天收到1500个查询。
在1997年11月，Altavista
声称它每天要处理大约20'000'000个查询。随着网络用户的增长，到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术（scaling
search engine technology），把它升级到如此大量的数据上。
1.2 Google：跟上Web的步伐（Scaling with the
Web）建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快，才能跟上网页变化的速度（keep
them up to
date）。存储索引和文档的空间必须足够大。索引系统必须能够有效地处理上千亿的数据。处理查询必须快，达到每秒能处理成百上千个查询（hundreds
to thousands per
second.）。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的执行效率和成本也在快速增长，可以部分抵消这些困难。
还有几个值得注意的因素，如磁盘的寻道时间（disk seek
time），操作系统的效率（operating system
robustness）。在设计Google的过程中，我们既考虑了Web的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理海量数据集。它能够有效地利用存储空间来存储索引。优化的数据结构能够快速有效地存取（参考4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（参考附录B）。对于象Google这样的集中式系统，采取这些措施得到了令人满意的系统可升级性（scaling
properties）。
1. 3设计目标
1.3.1提高搜索质量我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引（a
complete search index）可以使查找任何数据都变得容易。根据Best of the Web
1994 -- Navigators
，"最好的导航服务可以使在Web上搜索任何信息都很容易（当时所有的数据都可以被登录）"。然而1997年的Web就迥然不同。近来搜索引擎的用户已经证实索引的完整性不是评价搜索质量的唯一标准。用户感兴趣的搜索结果往往湮没在"垃圾结果Junk
result"中。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己（搜索自己名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。用户仍然只希望看前面几十个搜索结果。因此，当集合增大时，我们就需要工具使结果精确（在返回的前几十个结果中，有关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人高兴的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori
97] [Spertus 97] [Weiss 96] [Kleinberg
98]。尤其是链接结构[98页]和链接文本，为相关性的判断和高质量的过滤提供了大量的信息。Google既利用了链接结构又用到了anchor文本（见2.1和2.2节）。
1.3.2搜索引擎的学术研究随着时间的流逝，除了发展迅速，Web越来越商业化。1993年，只有1.5%的Web服务是来自.com域名。到1997年，超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少技公开术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（见附录A）。Google的主要目标是推动学术领域在此方面的发展，和对它的了解。另一个设计目标是给大家一个实用的系统。应用对我们来说非常重要，因为现代网络系统中存在大量的有用数据（us
because we think some of the most interesting research will involve
leveraging the vast amount of usage data that is available from modern web
systems）。例如，每天有几千万个研究。然而，得到这些数据却非常困难，主要因为它们没有商业价值。我们最后的设计目标是建立一个体系结构能够支持新的关于海量Web数据的研究。为了支持新研究，Google以压缩的形式保存了实际所抓到的文档。设计google的目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量Web数据，得到满意的结果，而通过其它方法却很难得到结果。系统在短时间内被建立起来，已经有几篇论文用到了Google建的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究者甚至学生都可以对我们的海量Web数据设计或做一些实验。
2. 系统特点 Google搜索引擎有两个重要特点，有助于得到高精度的搜索结果。
第一点，应用Web的链接结构计算每个网页的Rank值，称为PageRank，将在98页详细描述它。
第二点，Google利用超链接改进搜索结果。
2.1 PageRank:给网页排序
Web的引用（链接）图是重要的资源，却被当今的搜索引擎很大程度上忽视了。我们建立了一个包含518'000'000个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们心目中对一个网页重要程度的评价，建立的基础是通过引用判断重要性。因此在web中，PageRank能够优化关键词查询的结果。对于大多数的主题，在网页标题查询中用PageRank优化简单文本匹配，我们得到了令人惊叹的结果（从google.stanford.edu可以得到演示）。对于Google主系统中的全文搜索，PageRank也帮了不少忙。
2.1.1计算PageRank
文献检索中的引用理论用到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）可以用简单的迭代算法计算，相应规格化Web链接矩阵的主特征向量。中等规模的网站计算26'000'000网页的PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。
2.1.2直觉判断
PageRank被看作用户行为的模型。我们假设网上冲浪是随机的，不断点击链接，从不返回，最终烦了，另外随机选一个网页重新开始冲浪。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值。我们还有其它的PageRank算法，见98页。
另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。
2.2链接描述文字（Anchor
Text）我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页（the
page that the link is
on）联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。
第一，通常链接描述文字比网页本身更精确地描述该网页。
第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意哪些抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。链接描述文字是对被链向网页的宣传，这个思想被用在World
Wide Web Worm [McBryan
94]中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24'000'000个网页，已经检索到259'000'000多个链接描述文字。
2.3其它特点除了PageRank和应用链接描述文字外，Google还有一些其它特点。
第一,所有hit都有位置信息，所以它可以在搜索中广泛应用邻近性（proximity）。
第二，Google跟踪一些可视化外表细节，例如字号。黑体大号字比其它文字更重要。
第三，知识库存储了原始的全文html网页。
3有关工作 Web检索研究的历史简短。World Wide Web Worm（[McBryan
94]）是最早的搜索引擎之一。后来出现了一些用于学术研究的搜索引擎，现在它们中的大多数被上市公司拥有。与Web的增长和搜索引擎的重要性相比，有关当今搜索引擎技术的优秀论文相当少[Pinkerton
94]。根据Michael Mauldin（Lycos Inc的首席科学家）)
[Mauldin]，"各种各样的服务（包括Lycos）非常关注这些数据库的细节。"虽然在搜索引擎的某些特点上做了大量工作。具有代表性的工作有，对现有商业搜索引擎的结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤其在有组织机构集合（well
controlled
collections）方面。在下面两节，我们将讨论在信息检索系统中的哪些领域需要改进以便更好的工作在Web上。
3.1信息检索信息检索系统诞生在几年前，并发展迅速。然而大多数信息检索系统研究的对象是小规模的单一的有组织结构的集合，例如科学论文集，或相关主题的新闻故事。实际上，信息检索的主要基准，the
Text Retrieval Conference（[TREC
96]），用小规模的、有组织结构的集合作为它们的基准。
大型文集基准只有20GB，相比之下，我们抓到的24000000个网页占147GB。在TREC上工作良好的系统，在Web上却不一定产生好的结果。例如，标准向量空间模型企图返回和查询请求最相近的文档，把查询请求和文档都看作由出现在它们中的词汇组成的向量。在Web环境下，这种策略常常返回非常短的文档，这些文档往往是查询词再加几个字。例如，查询"Bill
Clinton"，返回的网页只包含"Bill Clinton
Sucks"，这是我们从一个主要搜索引擎中看到的。网络上有些争议，用户应该更准确地表达他们想查询什么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象"Bill
Clinton"这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。象所给的例子，我们认为信息检索标准需要发展，以便有效地处理Web数据。
3.2有组织结构的集合（Well Controlled Collections）与Web的不同点
Web是完全无组织的异构的大量文档的集合。Web中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言（既有人类语言又有程序），词汇（email地址，链接，邮政编码，电话号码，产品号），类型（文本，HTML，PDF，图像，声音），有些甚至是机器创建的文件（log文件，或数据库的输出）。可以从文档中推断出来，但并不包含在文档中的信息称为隐含信息。隐含信息包括来源的信誉，更新频率，质量，访问量和引用。不但隐含信息的可能来源各种各样，而且被检测的信息也大不相同，相差可达好几个数量级。例如，一个重要主页的使用量，象Yahoo
每天浏览数达到上百万次，于此相比无名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。
Web与有组织结构集合之间的另外一个明显区别是，事实上，向Web上传信息没有任何限制。灵活利用这点可以发布任何对搜索引擎影响重大的信息，使路由阻塞，加上为牟利故意操纵搜索引擎，这些已经成为一个严重的问题。这些问题还没有被传统的封闭的信息检索系统所提出来。它关心的是元数据的努力，这在Web搜索引擎中却不适用，因为网页中的任何文本都不会向用户声称企图操纵搜索引擎。甚至有些公司为牟利专门操纵搜索引擎。
4 系统分析（System
Anatomy）首先，我们提供高水平的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将被严格地检查。
Figure 1. High Level Google Architecture
4.1Google体系结构概述这一节，我们将看看整个系统是如何工作的（give a high
level），见图1。本节不讨论应用和数据结构，在后几节中讨论。为了效率大部分Google是用c或c++实现的，既可以在Solaris也可以在Linux上运行。
Google系统中，抓网页（下载网页）是由几个分布式crawlers完成的。一个URL服务器负责向crawlers提供URL列表。抓来的网页交给存储服务器storeserver。然后，由存储服务器压缩网页并把它们存到知识库repository中。每个网页都有一个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知识库 Figure 2. Repository Data Structure
知识库包含每个网页的全部HTML。每个网页用zlib（见RFC1950）压缩。压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。
4.2.3文件索引文件索引保存了有关文档的一些信息。索引以docID的顺序排列，定宽ISAM（Index
sequential access
mode）。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向docinfo文件，该文件的宽度可变，包含了URL和标题。否则指针指向包含这个URL的URL列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表，按校验和排序。要想知道某个URL的docID，需要计算URL的校验和，然后在校验和文件中执行二进制查找，找到它的docID。通过对这个文件进行合并，可以把一批URL转换成对应的docID。URL分析器用这项技术把URL转换成docID。这种成批更新的模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322'000'000个链接的数据集合将花费一个多月的时间。
4.2.4词典词典有几种不同的形式。和以前系统的重要不同是，词典对内存的要求可以在合理的价格内。现在实现的系统，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14000000词汇（虽然一些很少用的词汇没有加入到词典中）。它执行分两部分—词汇表（用null分隔的连续串）和指针的哈希表。不同的函数，词汇表有一些辅助信息，这超出了本文论述的范围。
4.2.5 hit list hit
list是一篇文档中所出现的词的列表，包括位置，字号，大小写。Hit
list占很大空间，用在正向和反向索引中。因此，它的表示形式越有效越好。我们考虑了几种方案来编码位置，字号，大小写—简单编码（3个整型数），紧凑编码（支持优化分配比特位），哈夫曼编码。Hit的详细信息见图3。我们的紧凑编码每个hit用2字节。有两种类型hit，特殊hit和普通hit。特殊hit包含URL，标题，链接描述文字，meta
tag。普通hit包含其它每件事。它包括大小写特征位，字号，12比特用于描述词在文档中的位置（所有超过4095的位置标记为4096）。字号采用相对于文档的其它部分的相对大小表示，占3比特(实际只用7个值，因为111标志是特殊hit)。特殊hit由大小写特征位，字号位为7表示它是特殊hit，用4比特表示特殊hit的类型，8比特表示位置。对于anchor
hit八比特位置位分出4比特用来表示在anchor中的位置，4比特用于表明anchor出现的哈希表hash
of the
docID。短语查询是有限的，对某些词没有足够多的anchor。我们希望更新anchor
hit的存储方式，以便解决地址位和docIDhash域位数不足的问题。
因为搜索时，你不会因为文档的字号比别的文档大而特殊对待它，所以采用相对字号。
hit表的长度存储在hit前。为节省空间hit表长度，在正向索引中和wordID结合在一起，在反向索引中和docID结合存储。这就限制它相应地只占8到5比特（用些技巧，可以从wordID中借8bit）如果大于这些比特所能表示的长度，用溢出码填充，其后两字节是真正的长度。
Figure 3. Forward and Reverse Indexes and the Lexicon
4.2.6正向索引实际上，正向索引已经部分排序。它被存在一定数量的barrel中（我们用64个barrels）。每个barrel装着一定范围的wordID。如果一篇文档中的词落到某个barrel，它的docID将被记录到这个barrel中，紧跟着那些词（文档中所有的词汇，还是落入该barrel中的词汇）对应的hitlist。这种模式需要稍多些的存储空间，因为一个docID被用多次，但是它节省了桶数和时间，最后排序器进行索引时降低编码的复杂度。更进一步的措施是，我们不是存储docID本身，而是存储相对于该桶最小的docID的差。用这种方法，未排序的barrel的docID只需24位，省下8位记录hitlist长。
4.2.7反向索引除了反向索引由sorter加工处理之外，它和正向索引包含相同的桶。对每个有效的docID，字典包含一个指向该词所在桶的指针。它指向由docID和它的相应hitlist组成的doclish，这个doclist代表了所有包含该词的文档。
doclist中docID的顺序是一个重要的问题。最简单的解决办法是用doclish排序。这种方法合并多个词时很快。另一个可选方案是用文档中该词出现的次数排序。这种方法回答单词查询，所用时间微不足道。当多词查询时几乎是从头开始。并且当用其它Rank算法改进索引时，非常困难。我们综合了这两种方法，建立两组反向索引barrel，一组barrels的hitlist只包含标题和anchor
hit，另一组barrel包含全部的hitlist。我们首先查第一组索引桶，看有没有匹配的项，然后查较大的那组桶。
4.3抓网页运行网络爬行机器人是一项具有挑战性的任务。执行的性能和可靠性甚至更重要，还有一些社会焦点。网络爬行是一项非常薄弱的应用，它需要成百上千的web服务器和各种域名服务器的参与，这些服务器不是我们系统所能控制的。为了覆盖几十亿的网页，Google拥有快速的分布式网络爬行系统。一个URL服务器给若干个网络爬行机器人（我们采用3个）提供URL列表。URL服务器和网络爬行机器人都是用Python实现的。每个网络爬行机器人可以同时打开300个链接。抓取网页必须足够快。最快时，用4个网络爬行机器人每秒可以爬行100个网页。速率达每秒600K。执行的重点是找DNS。每个网络爬行机器人有它自己的DNS
cache，所以它不必每个网页都查DNS。每一百个连接都有几种不同的状态：查DNS，连接主机，发送请求，接收回答。这些因素使网络爬行机器人成为系统比较复杂的部分。它用异步IO处理事件，若干请求队列从一个网站到另一个网站不停的抓取网页。运行一个链接到500多万台服务器的网页爬行机器人，产生1千多万登陆口，导致了大量的Email和电话。因为网民众多，总有些人不知道网络爬行机器人是何物，这是他们看到的第一个网络爬行机器人。几乎每天我们都会收到这样的Email"哦，你从我们的网站看了太多的网页，你想干什么？"还有一些人不知道网络搜索机器人避免协议（the
robots exclusion
protocol），以为他们的网页上写着"版权所有，勿被索引"的字样就会被保护不被索引，不必说，这样的话很难被web
crawler理解。因为数据量如此之大，还会遇到一些意想不到的事情。例如，我们的系统曾经企图抓一个在线游戏，结果抓到了游戏中的大量垃圾信息。解决这个问题很简单。但是我们下载了几千万网页后才发现了这个问题。因为网页和服务器的种类繁多，实际上不在大部分Internet上运行它就测试一个网页爬行机器人是不可能。总是有几百个隐含的问题发生在整个web的一个网页上，导致网络爬行机器人崩溃，或者更糟，导致不可预测的不正确的行为。能够访问大部分Internet的系统必须精力充沛并精心测试过。由于象crawler这样大型复杂的系统总是产生这样那样的问题，因此花费一些资源读这些Email，当问题发生时解决它，是有必要的。
4.4Web索引分析—任何运行在整个Web上的分析器必须能够处理可能包含错误的大型集合。范围从HTML标记到标记之间几K字节的0，非ASCII字符，几百层HTML标记的嵌套，各种各样令人难以想象的错误。为了获得最大的速度，我们没有采用YACC产生上下文无关文法CFG分析器，而是采用灵活的方式产生词汇分析器，它自己配有堆栈。分析器的改进大大提高了运行速度，它的精力如此充沛完成了大量工作。把文档装入barrel建立索引—分析完一篇文档，之后把该文档装入barrel中，用内存中的hash表—字典，每个词汇被转换成一个wordID。当hash表字典中加入新的项时，笨拙地存入文件。一旦词汇被转换成wordID，它们在当前文档的出现就转换成hitlist，被写进正向barrel。索引阶段并行的主要困难是字典需要共享。
我们采用的方法是，基本字典中有140万个固定词汇，不在基本字典中的词汇写入日志，而不是共享字典。这种方法多个索引器可以并行工作，最后一个索引器只需处理一个较小的额外词汇日志。排序—为了建立反向索引，排序器读取每个正向barrel，以wordID排序，建立只有标题anchor
hi
t的反向索引barrel和全文反向索引barrel。这个过程一次只处理一个barrel，所以只需要少量暂存空间。排序阶段也是并行的，我们简单地同时运行尽可能多的排序器，不同的排序器处理不同的桶。由于barrel不适合装入主存，排序器进一步依据wordID和docID把它分成若干篮子，以便适合装入主存。然后排序器把每个篮子装入主存进行排序，并把它的内容写回到短反向barrel和全文反向barrel。
4.5搜索搜索的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率方面花费了很大力气。因此我们的研究以搜索质量为重点，相信我们的解决方案也可以用到那些商业系统中。
Google查询评价过程见图4。
1. 分析查询。
2. 把词汇转换成wordID。
3. 在短barrel中查找每个词汇doclist的开头。
4. 扫描doclist直到找到一篇匹配所有关键词的文档
5. 计算该文档的rank
6.
如果我们在短barrel，并且在所有doclist的末尾，开始从全文barrel的doclist的开头查找每个词，goto
第四步
7. 如果不在任何doclist的结尾，返回第四步。
8. 根据rank排序匹配文档，返回前k个。图4
Google查询评价在有限的响应时间内，一旦找到一定数量的匹配文档，搜索引擎自动执行步骤8。这意味着，返回的结果是子优化的。我们现在研究其它方法来解决这个问题。过去根据PageRank排序hit，看来能够改进这种状况。
4.5.1 Ranking系统
Google比典型搜索引擎保存了更多的web信息。每个hitlish包括位置，字号，大小写。另外，我们还考虑了链接描述文字。Rank综合所有这些信息是困难的。ranking函数设计依据是没有某个因素对rank影响重大。首先，考虑最简单的情况—单个词查询。为了单个词查询中一个文档的rank，Goole在文档的hitlist中查找该词。Google认为每个hit是几种不同类型（标题，链接描述文字anchor，URL，普通大字号文本，普通小字号文本，……）之一，每种有它自己的类型权重。类型权重建立了一个类型索引向量。Google计算hitlist中每种hit的数量。然后每个hit数转换成count-weight。Count-weight开始随hit数线性增加，很快逐渐停止，以至于hit数与此不相关。我们计算count-weight向量和type-weight向量的标量积作为文档的IR值。最后IR值结合PageRank作为文档的最后rank
对于多词查询，更复杂些。现在，多词hitlist必须同时扫描，以便关键词出现在同一文档中的权重比分别出现时高。相邻词的hit一起匹配。对每个匹配hit
的集合计算相邻度。相邻度基于hit在文档中的距离，分成10个不同的bin值，范围从短语匹配到根本不相关。不仅计算每类hit数，而且要计算每种类型的相邻度，每个类型相似度对，有一个类型相邻度权type-prox-weight。Count转换成count-weight，计算count-weight
type-proc-weight的标量积作为IR值。应用某种debug
mode所有这些数和矩阵与查询结果一起显示出来。这些显示有助于改进rank系统。
4.5.2反馈
rank函数有很多参数象type-weight和type-prox-weight。指明这些参数的正确值有点黑色艺术black
art。为此，我们的搜索引擎有一个用户反馈机制。值得信任的用户可以随意地评价返回的结果。保存反馈。然后，当修改rank函数时，对比以前搜索的rank，我们可以看到修改带来的的影响。虽然不是十全十美，但是它给出了一些思路，当rank函数改变时对搜索结果的影响。
5执行和结果搜索结果的质量是搜索引擎最重要的度量标准。完全用户评价体系超出了本文的论述范围，对于大多数搜索，我们的经验说明Google的搜索结果比那些主要的商业搜索引擎好。作为一个应用PageRank，链接描述文字，相邻度的例子，图4给出了Google搜索bill
Clinton的结果。它说明了Google的一些特点。服务器对结果进行聚类。这对过滤结果集合相当有帮助。这个查询，相当一部分结果来自whitehouse.gov域，这正是我们所需要的。现在大多数商业搜索引擎不会返回任何来自whitehouse.gov的结果，这是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。Google是根据链接描述文字决定它是一个好的查询结果。同样地，第五个结果是一个Email地址，当然是不可能抓到的。也是链接描述文字的结果。所有这些结果质量都很高，最后检查没有死链接。因为它们中的大部分PageRank值较高。PageRank百分比用红色线条表示。没有结果只含Bill没有Clinton或只含Clinton没有Bill。因为词出现的相近性非常重要。当然搜索引擎质量的真实测试包含广泛的用户学习或结果分析，此处篇幅有限，请读者自己去体验Google，
http://google.stanford.edu/。
5.1存储需求除了搜索质量，Google的设计可以随着Web规模的增大而有效地增大成本。一方面有效地利用存储空间。表1列出了一些统计数字的明细表和Google存储的需求。由于压缩技术的应用知识库只需53GB的存储空间。是所有要存储数据的三分之一。按当今磁盘价格，知识库相对于有用的数据来说比较便宜。搜索引擎需要的所有数据的存储空间大约55GB。大多数查询请求只需要短反向索引。文件索引应用先进的编码和压缩技术，一个高质量的搜索引擎可以运行在7GB的新PC。
5.2系统执行搜索引擎抓网页和建立索引的效率非常重要。Google的主要操作是抓网页，索引，排序。很难测试抓全部网页需要多少时间，因为磁盘满了，域名服务器崩溃，或者其它问题导致系统停止。总的来说，大约需要9天时间下载26000000网页（包括错误）。然而，一旦系统运行顺利，速度非常快，下载最后11000000网页只需要63小时，平均每天4000000网页，每秒48.5个网页。索引器和网络爬行机器人同步运行。索引器比网络爬行机器人快。因为我们花费了大量时间优化索引器，使它不是瓶颈。这些优化包括批量更新文档索引，本地磁盘数据结构的安排。索引器每秒处理54个网页。排序器完全并行，用4台机器，排序的整个过程大概需要24小时。
5.3搜索执行改进搜索执行不是我们研究的重点。当前版本的Google可以在1到10秒间回答查询请求。时间大部分花费在NFS磁盘IO上（由于磁盘普遍比机器慢）。进一步说，Google没有做任何优化，例如查询缓冲区，常用词汇子索引，和其它常用的优化技术。我们倾向于通过分布式，硬件，软件，和算法的改进来提高Google的速度。我们的目标是每秒能处理几百个请求。表2有几个现在版本Google响应查询时间的例子。它们说明IO缓冲区对再次搜索速度的影响。
6结论 Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide
Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。
6.1未来的工作大型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请求缓冲区，巧妙地分配磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这个目标已经由[Cho
98]实现了。受需求驱动，用代理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索引，共24000000个网页，用时不到一星期。我们希望能在一个月内建立100000000网页的索引。
6.4研究工具
Google不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如[Abiteboul
97]，提出了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数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。参考文献
•
Google的设计目标是可升级到10亿网页。我们的磁盘和机器大概能处理这么多网页。系统各个部分耗费的总时间是并行的和线性的。包括网页爬行机器人，索引器和排序器。扩展后我们认为大多数数据结构运行良好。然而10亿网页接近所有常用操作系统的极限（我们目前运行在Solaris和Linux上）。包括主存地址，开放文件描述符的数量，网络socket和带宽，以及其它因素。我们认为当网页数量大大超过10亿网页时，会大大增加系统复杂性。
9.2集中式索引体系的可升级性随着计算机性能的提高，海量文本索引的成本比较公平。当然带宽需求高的其它应用如视频，越来越普遍。但是，与多媒体例如视频相比，文本产品的成本低，因此文本仍然普遍。
search
engine）的原型，搜索引擎在超文本中应用广泛。Google的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24'000'000个网页。我们可以从
http://google.stanford.edu/ 下载。
设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且每天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。
本文详细介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此详细。除了把传统数据搜索技术应用到如此大量级网页中所遇到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。
本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。
关键词 World Wide Web，搜索引擎，信息检索，PageRank, Google 1 绪论 Web
给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象Yahoo这样重要的网页或搜索引擎开始。大家认为List(目录)有效地包含了大家感兴趣的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。
我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。
1.1网络搜索引擎—升级换代（scaling up）：1994-2000
搜索引擎技术不得不快速升级（scale
dramatically）跟上成倍增长的web数量。1994年，第一个Web搜索引擎，World Wide
Web
Worm(WWWW)[McBryan94]可以检索到110，000个网页和Web的文件。到1994年11月，顶级的搜索引擎声称可以检索到2'000'000（WebCrawler）至100'000'000个网络文件（来自
Search Engine
Watch）。可以预见到2000年，可检索到的网页将超过1'000'000'000。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，World
Wide Web Worm 平均每天收到1500个查询。
在1997年11月，Altavista
声称它每天要处理大约20'000'000个查询。随着网络用户的增长，到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术（scaling
search engine technology），把它升级到如此大量的数据上。
1.2 Google：跟上Web的步伐（Scaling with the
Web）建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快，才能跟上网页变化的速度（keep
them up to
date）。存储索引和文档的空间必须足够大。索引系统必须能够有效地处理上千亿的数据。处理查询必须快，达到每秒能处理成百上千个查询（hundreds
to thousands per
second.）。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的执行效率和成本也在快速增长，可以部分抵消这些困难。
还有几个值得注意的因素，如磁盘的寻道时间（disk seek
time），操作系统的效率（operating system
robustness）。在设计Google的过程中，我们既考虑了Web的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理海量数据集。它能够有效地利用存储空间来存储索引。优化的数据结构能够快速有效地存取（参考4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（参考附录B）。对于象Google这样的集中式系统，采取这些措施得到了令人满意的系统可升级性（scaling
properties）。
1. 3设计目标
1.3.1提高搜索质量我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引（a
complete search index）可以使查找任何数据都变得容易。根据Best of the Web
1994 -- Navigators
，"最好的导航服务可以使在Web上搜索任何信息都很容易（当时所有的数据都可以被登录）"。然而1997年的Web就迥然不同。近来搜索引擎的用户已经证实索引的完整性不是评价搜索质量的唯一标准。用户感兴趣的搜索结果往往湮没在"垃圾结果Junk
result"中。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己（搜索自己名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。用户仍然只希望看前面几十个搜索结果。因此，当集合增大时，我们就需要工具使结果精确（在返回的前几十个结果中，有关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人高兴的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori
97] [Spertus 97] [Weiss 96] [Kleinberg
98]。尤其是链接结构[98页]和链接文本，为相关性的判断和高质量的过滤提供了大量的信息。Google既利用了链接结构又用到了anchor文本（见2.1和2.2节）。
1.3.2搜索引擎的学术研究随着时间的流逝，除了发展迅速，Web越来越商业化。1993年，只有1.5%的Web服务是来自.com域名。到1997年，超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少技公开术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（见附录A）。Google的主要目标是推动学术领域在此方面的发展，和对它的了解。另一个设计目标是给大家一个实用的系统。应用对我们来说非常重要，因为现代网络系统中存在大量的有用数据（us
because we think some of the most interesting research will involve
leveraging the vast amount of usage data that is available from modern web
systems）。例如，每天有几千万个研究。然而，得到这些数据却非常困难，主要因为它们没有商业价值。我们最后的设计目标是建立一个体系结构能够支持新的关于海量Web数据的研究。为了支持新研究，Google以压缩的形式保存了实际所抓到的文档。设计google的目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量Web数据，得到满意的结果，而通过其它方法却很难得到结果。系统在短时间内被建立起来，已经有几篇论文用到了Google建的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究者甚至学生都可以对我们的海量Web数据设计或做一些实验。
2. 系统特点 Google搜索引擎有两个重要特点，有助于得到高精度的搜索结果。
第一点，应用Web的链接结构计算每个网页的Rank值，称为PageRank，将在98页详细描述它。
第二点，Google利用超链接改进搜索结果。
2.1 PageRank:给网页排序
Web的引用（链接）图是重要的资源，却被当今的搜索引擎很大程度上忽视了。我们建立了一个包含518'000'000个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们心目中对一个网页重要程度的评价，建立的基础是通过引用判断重要性。因此在web中，PageRank能够优化关键词查询的结果。对于大多数的主题，在网页标题查询中用PageRank优化简单文本匹配，我们得到了令人惊叹的结果（从google.stanford.edu可以得到演示）。对于Google主系统中的全文搜索，PageRank也帮了不少忙。
2.1.1计算PageRank
文献检索中的引用理论用到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）可以用简单的迭代算法计算，相应规格化Web链接矩阵的主特征向量。中等规模的网站计算26'000'000网页的PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。
2.1.2直觉判断
PageRank被看作用户行为的模型。我们假设网上冲浪是随机的，不断点击链接，从不返回，最终烦了，另外随机选一个网页重新开始冲浪。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值。我们还有其它的PageRank算法，见98页。
另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。
2.2链接描述文字（Anchor
Text）我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页（the
page that the link is
on）联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。
第一，通常链接描述文字比网页本身更精确地描述该网页。
第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意哪些抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。链接描述文字是对被链向网页的宣传，这个思想被用在World
Wide Web Worm [McBryan
94]中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24'000'000个网页，已经检索到259'000'000多个链接描述文字。
2.3其它特点除了PageRank和应用链接描述文字外，Google还有一些其它特点。
第一,所有hit都有位置信息，所以它可以在搜索中广泛应用邻近性（proximity）。
第二，Google跟踪一些可视化外表细节，例如字号。黑体大号字比其它文字更重要。
第三，知识库存储了原始的全文html网页。
3有关工作 Web检索研究的历史简短。World Wide Web Worm（[McBryan
94]）是最早的搜索引擎之一。后来出现了一些用于学术研究的搜索引擎，现在它们中的大多数被上市公司拥有。与Web的增长和搜索引擎的重要性相比，有关当今搜索引擎技术的优秀论文相当少[Pinkerton
94]。根据Michael Mauldin（Lycos Inc的首席科学家）)
[Mauldin]，"各种各样的服务（包括Lycos）非常关注这些数据库的细节。"虽然在搜索引擎的某些特点上做了大量工作。具有代表性的工作有，对现有商业搜索引擎的结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤其在有组织机构集合（well
controlled
collections）方面。在下面两节，我们将讨论在信息检索系统中的哪些领域需要改进以便更好的工作在Web上。
3.1信息检索信息检索系统诞生在几年前，并发展迅速。然而大多数信息检索系统研究的对象是小规模的单一的有组织结构的集合，例如科学论文集，或相关主题的新闻故事。实际上，信息检索的主要基准，the
Text Retrieval Conference（[TREC
96]），用小规模的、有组织结构的集合作为它们的基准。
大型文集基准只有20GB，相比之下，我们抓到的24000000个网页占147GB。在TREC上工作良好的系统，在Web上却不一定产生好的结果。例如，标准向量空间模型企图返回和查询请求最相近的文档，把查询请求和文档都看作由出现在它们中的词汇组成的向量。在Web环境下，这种策略常常返回非常短的文档，这些文档往往是查询词再加几个字。例如，查询"Bill
Clinton"，返回的网页只包含"Bill Clinton
Sucks"，这是我们从一个主要搜索引擎中看到的。网络上有些争议，用户应该更准确地表达他们想查询什么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象"Bill
Clinton"这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。象所给的例子，我们认为信息检索标准需要发展，以便有效地处理Web数据。
3.2有组织结构的集合（Well Controlled Collections）与Web的不同点
Web是完全无组织的异构的大量文档的集合。Web中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言（既有人类语言又有程序），词汇（email地址，链接，邮政编码，电话号码，产品号），类型（文本，HTML，PDF，图像，声音），有些甚至是机器创建的文件（log文件，或数据库的输出）。可以从文档中推断出来，但并不包含在文档中的信息称为隐含信息。隐含信息包括来源的信誉，更新频率，质量，访问量和引用。不但隐含信息的可能来源各种各样，而且被检测的信息也大不相同，相差可达好几个数量级。例如，一个重要主页的使用量，象Yahoo
每天浏览数达到上百万次，于此相比无名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。
Web与有组织结构集合之间的另外一个明显区别是，事实上，向Web上传信息没有任何限制。灵活利用这点可以发布任何对搜索引擎影响重大的信息，使路由阻塞，加上为牟利故意操纵搜索引擎，这些已经成为一个严重的问题。这些问题还没有被传统的封闭的信息检索系统所提出来。它关心的是元数据的努力，这在Web搜索引擎中却不适用，因为网页中的任何文本都不会向用户声称企图操纵搜索引擎。甚至有些公司为牟利专门操纵搜索引擎。
4 系统分析（System
Anatomy）首先，我们提供高水平的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将被严格地检查。
Figure 1. High Level Google Architecture
4.1Google体系结构概述这一节，我们将看看整个系统是如何工作的（give a high
level），见图1。本节不讨论应用和数据结构，在后几节中讨论。为了效率大部分Google是用c或c++实现的，既可以在Solaris也可以在Linux上运行。
Google系统中，抓网页（下载网页）是由几个分布式crawlers完成的。一个URL服务器负责向crawlers提供URL列表。抓来的网页交给存储服务器storeserver。然后，由存储服务器压缩网页并把它们存到知识库repository中。每个网页都有一个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知识库 Figure 2. Repository Data Structure
知识库包含每个网页的全部HTML。每个网页用zlib（见RFC1950）压缩。压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。
4.2.3文件索引文件索引保存了有关文档的一些信息。索引以docID的顺序排列，定宽ISAM（Index
sequential access
mode）。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向docinfo文件，该文件的宽度可变，包含了URL和标题。否则指针指向包含这个URL的URL列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表，按校验和排序。要想知道某个URL的docID，需要计算URL的校验和，然后在校验和文件中执行二进制查找，找到它的docID。通过对这个文件进行合并，可以把一批URL转换成对应的docID。URL分析器用这项技术把URL转换成docID。这种成批更新的模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322'000'000个链接的数据集合将花费一个多月的时间。
4.2.4词典词典有几种不同的形式。和以前系统的重要不同是，词典对内存的要求可以在合理的价格内。现在实现的系统，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14000000词汇（虽然一些很少用的词汇没有加入到词典中）。它执行分两部分—词汇表（用null分隔的连续串）和指针的哈希表。不同的函数，词汇表有一些辅助信息，这超出了本文论述的范围。
4.2.5 hit list hit
list是一篇文档中所出现的词的列表，包括位置，字号，大小写。Hit
list占很大空间，用在正向和反向索引中。因此，它的表示形式越有效越好。我们考虑了几种方案来编码位置，字号，大小写—简单编码（3个整型数），紧凑编码（支持优化分配比特位），哈夫曼编码。Hit的详细信息见图3。我们的紧凑编码每个hit用2字节。有两种类型hit，特殊hit和普通hit。特殊hit包含URL，标题，链接描述文字，meta
tag。普通hit包含其它每件事。它包括大小写特征位，字号，12比特用于描述词在文档中的位置（所有超过4095的位置标记为4096）。字号采用相对于文档的其它部分的相对大小表示，占3比特(实际只用7个值，因为111标志是特殊hit)。特殊hit由大小写特征位，字号位为7表示它是特殊hit，用4比特表示特殊hit的类型，8比特表示位置。对于anchor
hit八比特位置位分出4比特用来表示在anchor中的位置，4比特用于表明anchor出现的哈希表hash
of the
docID。短语查询是有限的，对某些词没有足够多的anchor。我们希望更新anchor
hit的存储方式，以便解决地址位和docIDhash域位数不足的问题。
因为搜索时，你不会因为文档的字号比别的文档大而特殊对待它，所以采用相对字号。
hit表的长度存储在hit前。为节省空间hit表长度，在正向索引中和wordID结合在一起，在反向索引中和docID结合存储。这就限制它相应地只占8到5比特（用些技巧，可以从wordID中借8bit）如果大于这些比特所能表示的长度，用溢出码填充，其后两字节是真正的长度。
Figure 3. Forward and Reverse Indexes and the Lexicon
4.2.6正向索引实际上，正向索引已经部分排序。它被存在一定数量的barrel中（我们用64个barrels）。每个barrel装着一定范围的wordID。如果一篇文档中的词落到某个barrel，它的docID将被记录到这个barrel中，紧跟着那些词（文档中所有的词汇，还是落入该barrel中的词汇）对应的hitlist。这种模式需要稍多些的存储空间，因为一个docID被用多次，但是它节省了桶数和时间，最后排序器进行索引时降低编码的复杂度。更进一步的措施是，我们不是存储docID本身，而是存储相对于该桶最小的docID的差。用这种方法，未排序的barrel的docID只需24位，省下8位记录hitlist长。
4.2.7反向索引除了反向索引由sorter加工处理之外，它和正向索引包含相同的桶。对每个有效的docID，字典包含一个指向该词所在桶的指针。它指向由docID和它的相应hitlist组成的doclish，这个doclist代表了所有包含该词的文档。
doclist中docID的顺序是一个重要的问题。最简单的解决办法是用doclish排序。这种方法合并多个词时很快。另一个可选方案是用文档中该词出现的次数排序。这种方法回答单词查询，所用时间微不足道。当多词查询时几乎是从头开始。并且当用其它Rank算法改进索引时，非常困难。我们综合了这两种方法，建立两组反向索引barrel，一组barrels的hitlist只包含标题和anchor
hit，另一组barrel包含全部的hitlist。我们首先查第一组索引桶，看有没有匹配的项，然后查较大的那组桶。
4.3抓网页运行网络爬行机器人是一项具有挑战性的任务。执行的性能和可靠性甚至更重要，还有一些社会焦点。网络爬行是一项非常薄弱的应用，它需要成百上千的web服务器和各种域名服务器的参与，这些服务器不是我们系统所能控制的。为了覆盖几十亿的网页，Google拥有快速的分布式网络爬行系统。一个URL服务器给若干个网络爬行机器人（我们采用3个）提供URL列表。URL服务器和网络爬行机器人都是用Python实现的。每个网络爬行机器人可以同时打开300个链接。抓取网页必须足够快。最快时，用4个网络爬行机器人每秒可以爬行100个网页。速率达每秒600K。执行的重点是找DNS。每个网络爬行机器人有它自己的DNS
cache，所以它不必每个网页都查DNS。每一百个连接都有几种不同的状态：查DNS，连接主机，发送请求，接收回答。这些因素使网络爬行机器人成为系统比较复杂的部分。它用异步IO处理事件，若干请求队列从一个网站到另一个网站不停的抓取网页。运行一个链接到500多万台服务器的网页爬行机器人，产生1千多万登陆口，导致了大量的Email和电话。因为网民众多，总有些人不知道网络爬行机器人是何物，这是他们看到的第一个网络爬行机器人。几乎每天我们都会收到这样的Email"哦，你从我们的网站看了太多的网页，你想干什么？"还有一些人不知道网络搜索机器人避免协议（the
robots exclusion
protocol），以为他们的网页上写着"版权所有，勿被索引"的字样就会被保护不被索引，不必说，这样的话很难被web
crawler理解。因为数据量如此之大，还会遇到一些意想不到的事情。例如，我们的系统曾经企图抓一个在线游戏，结果抓到了游戏中的大量垃圾信息。解决这个问题很简单。但是我们下载了几千万网页后才发现了这个问题。因为网页和服务器的种类繁多，实际上不在大部分Internet上运行它就测试一个网页爬行机器人是不可能。总是有几百个隐含的问题发生在整个web的一个网页上，导致网络爬行机器人崩溃，或者更糟，导致不可预测的不正确的行为。能够访问大部分Internet的系统必须精力充沛并精心测试过。由于象crawler这样大型复杂的系统总是产生这样那样的问题，因此花费一些资源读这些Email，当问题发生时解决它，是有必要的。
4.4Web索引分析—任何运行在整个Web上的分析器必须能够处理可能包含错误的大型集合。范围从HTML标记到标记之间几K字节的0，非ASCII字符，几百层HTML标记的嵌套，各种各样令人难以想象的错误。为了获得最大的速度，我们没有采用YACC产生上下文无关文法CFG分析器，而是采用灵活的方式产生词汇分析器，它自己配有堆栈。分析器的改进大大提高了运行速度，它的精力如此充沛完成了大量工作。把文档装入barrel建立索引—分析完一篇文档，之后把该文档装入barrel中，用内存中的hash表—字典，每个词汇被转换成一个wordID。当hash表字典中加入新的项时，笨拙地存入文件。一旦词汇被转换成wordID，它们在当前文档的出现就转换成hitlist，被写进正向barrel。索引阶段并行的主要困难是字典需要共享。
我们采用的方法是，基本字典中有140万个固定词汇，不在基本字典中的词汇写入日志，而不是共享字典。这种方法多个索引器可以并行工作，最后一个索引器只需处理一个较小的额外词汇日志。排序—为了建立反向索引，排序器读取每个正向barrel，以wordID排序，建立只有标题anchor
hi
t的反向索引barrel和全文反向索引barrel。这个过程一次只处理一个barrel，所以只需要少量暂存空间。排序阶段也是并行的，我们简单地同时运行尽可能多的排序器，不同的排序器处理不同的桶。由于barrel不适合装入主存，排序器进一步依据wordID和docID把它分成若干篮子，以便适合装入主存。然后排序器把每个篮子装入主存进行排序，并把它的内容写回到短反向barrel和全文反向barrel。
4.5搜索搜索的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率方面花费了很大力气。因此我们的研究以搜索质量为重点，相信我们的解决方案也可以用到那些商业系统中。
Google查询评价过程见图4。
1. 分析查询。
2. 把词汇转换成wordID。
3. 在短barrel中查找每个词汇doclist的开头。
4. 扫描doclist直到找到一篇匹配所有关键词的文档
5. 计算该文档的rank
6.
如果我们在短barrel，并且在所有doclist的末尾，开始从全文barrel的doclist的开头查找每个词，goto
第四步
7. 如果不在任何doclist的结尾，返回第四步。
8. 根据rank排序匹配文档，返回前k个。图4
Google查询评价在有限的响应时间内，一旦找到一定数量的匹配文档，搜索引擎自动执行步骤8。这意味着，返回的结果是子优化的。我们现在研究其它方法来解决这个问题。过去根据PageRank排序hit，看来能够改进这种状况。
4.5.1 Ranking系统
Google比典型搜索引擎保存了更多的web信息。每个hitlish包括位置，字号，大小写。另外，我们还考虑了链接描述文字。Rank综合所有这些信息是困难的。ranking函数设计依据是没有某个因素对rank影响重大。首先，考虑最简单的情况—单个词查询。为了单个词查询中一个文档的rank，Goole在文档的hitlist中查找该词。Google认为每个hit是几种不同类型（标题，链接描述文字anchor，URL，普通大字号文本，普通小字号文本，……）之一，每种有它自己的类型权重。类型权重建立了一个类型索引向量。Google计算hitlist中每种hit的数量。然后每个hit数转换成count-weight。Count-weight开始随hit数线性增加，很快逐渐停止，以至于hit数与此不相关。我们计算count-weight向量和type-weight向量的标量积作为文档的IR值。最后IR值结合PageRank作为文档的最后rank
对于多词查询，更复杂些。现在，多词hitlist必须同时扫描，以便关键词出现在同一文档中的权重比分别出现时高。相邻词的hit一起匹配。对每个匹配hit
的集合计算相邻度。相邻度基于hit在文档中的距离，分成10个不同的bin值，范围从短语匹配到根本不相关。不仅计算每类hit数，而且要计算每种类型的相邻度，每个类型相似度对，有一个类型相邻度权type-prox-weight。Count转换成count-weight，计算count-weight
type-proc-weight的标量积作为IR值。应用某种debug
mode所有这些数和矩阵与查询结果一起显示出来。这些显示有助于改进rank系统。
4.5.2反馈
rank函数有很多参数象type-weight和type-prox-weight。指明这些参数的正确值有点黑色艺术black
art。为此，我们的搜索引擎有一个用户反馈机制。值得信任的用户可以随意地评价返回的结果。保存反馈。然后，当修改rank函数时，对比以前搜索的rank，我们可以看到修改带来的的影响。虽然不是十全十美，但是它给出了一些思路，当rank函数改变时对搜索结果的影响。
5执行和结果搜索结果的质量是搜索引擎最重要的度量标准。完全用户评价体系超出了本文的论述范围，对于大多数搜索，我们的经验说明Google的搜索结果比那些主要的商业搜索引擎好。作为一个应用PageRank，链接描述文字，相邻度的例子，图4给出了Google搜索bill
Clinton的结果。它说明了Google的一些特点。服务器对结果进行聚类。这对过滤结果集合相当有帮助。这个查询，相当一部分结果来自whitehouse.gov域，这正是我们所需要的。现在大多数商业搜索引擎不会返回任何来自whitehouse.gov的结果，这是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。Google是根据链接描述文字决定它是一个好的查询结果。同样地，第五个结果是一个Email地址，当然是不可能抓到的。也是链接描述文字的结果。所有这些结果质量都很高，最后检查没有死链接。因为它们中的大部分PageRank值较高。PageRank百分比用红色线条表示。没有结果只含Bill没有Clinton或只含Clinton没有Bill。因为词出现的相近性非常重要。当然搜索引擎质量的真实测试包含广泛的用户学习或结果分析，此处篇幅有限，请读者自己去体验Google，
http://google.stanford.edu/。
5.1存储需求除了搜索质量，Google的设计可以随着Web规模的增大而有效地增大成本。一方面有效地利用存储空间。表1列出了一些统计数字的明细表和Google存储的需求。由于压缩技术的应用知识库只需53GB的存储空间。是所有要存储数据的三分之一。按当今磁盘价格，知识库相对于有用的数据来说比较便宜。搜索引擎需要的所有数据的存储空间大约55GB。大多数查询请求只需要短反向索引。文件索引应用先进的编码和压缩技术，一个高质量的搜索引擎可以运行在7GB的新PC。
5.2系统执行搜索引擎抓网页和建立索引的效率非常重要。Google的主要操作是抓网页，索引，排序。很难测试抓全部网页需要多少时间，因为磁盘满了，域名服务器崩溃，或者其它问题导致系统停止。总的来说，大约需要9天时间下载26000000网页（包括错误）。然而，一旦系统运行顺利，速度非常快，下载最后11000000网页只需要63小时，平均每天4000000网页，每秒48.5个网页。索引器和网络爬行机器人同步运行。索引器比网络爬行机器人快。因为我们花费了大量时间优化索引器，使它不是瓶颈。这些优化包括批量更新文档索引，本地磁盘数据结构的安排。索引器每秒处理54个网页。排序器完全并行，用4台机器，排序的整个过程大概需要24小时。
5.3搜索执行改进搜索执行不是我们研究的重点。当前版本的Google可以在1到10秒间回答查询请求。时间大部分花费在NFS磁盘IO上（由于磁盘普遍比机器慢）。进一步说，Google没有做任何优化，例如查询缓冲区，常用词汇子索引，和其它常用的优化技术。我们倾向于通过分布式，硬件，软件，和算法的改进来提高Google的速度。我们的目标是每秒能处理几百个请求。表2有几个现在版本Google响应查询时间的例子。它们说明IO缓冲区对再次搜索速度的影响。
6结论 Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide
Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。
6.1未来的工作大型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请求缓冲区，巧妙地分配磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这个目标已经由[Cho
98]实现了。受需求驱动，用代理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索引，共24000000个网页，用时不到一星期。我们希望能在一个月内建立100000000网页的索引。
6.4研究工具
Google不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如[Abiteboul
97]，提出了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数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。参考文献
•
Google的设计目标是可升级到10亿网页。我们的磁盘和机器大概能处理这么多网页。系统各个部分耗费的总时间是并行的和线性的。包括网页爬行机器人，索引器和排序器。扩展后我们认为大多数数据结构运行良好。然而10亿网页接近所有常用操作系统的极限（我们目前运行在Solaris和Linux上）。包括主存地址，开放文件描述符的数量，网络socket和带宽，以及其它因素。我们认为当网页数量大大超过10亿网页时，会大大增加系统复杂性。
9.2集中式索引体系的可升级性随着计算机性能的提高，海量文本索引的成本比较公平。当然带宽需求高的其它应用如视频，越来越普遍。但是，与多媒体例如视频相比，文本产品的成本低，因此文本仍然普遍。
图2 Google系统的工作流程图
(注：原图来自Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale
Hypertextual. Web Search Engine, 1998.
http://www-db.stanford.edu/%7Ebackrub/Google.html)
①Google使用高速的分布式爬行器(Crawler)系统中的漫游遍历器(Googlebot)定时地遍历网页，将遍历到的网页送到存储服务器(Store
Server)中。
②存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据库Repository中。Repository获得了每个网页的完全Html代码后，对其压缩后的网页及URL进行分析，记录下网页长度、URL、URL长度和网页内容，并赋予每个网页一个文档号(docID)，以便当系统出现故障的时候，可以及时完整地进行网页的数据恢复。
③索引器(Indexer)从Repository中读取数据，以后做以下四步工作：
④(a)将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后，转化为关键词(wordID)的若干索引项(Hits)，生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。索引项列表被存入到数据桶(Barrels)中，并生成以文档号(docID)部分排序的顺排档索引。
索引项根据其重要程度分为两种：当索引项中的关键词出现在URL、标题、锚文本(Anchor
Text)和标签中时，表示该索引项比较重要，称为特殊索引项(Fancy
Hits)；其余情况则称为普通索引项(Plain
Hits)。在系统中每个Hit用两个字节(byte)存储结构表示：特殊索引项用1位(bit)表示大小写，用二进制代码111(占3位)表示是特殊索引项，其余12位有4位表示特殊索引项的类型(即hit是出现在URL、标题、链接结点还是标签中)，剩下8位表示hit在网页中的具体位置；普通索引项是用1位表示大小写，3位表示字体大小，其余12位表示在网页中的具体位置。
顺排档索引和Hit的存储结构如图3所示。
图3 顺排档索引和Hit的存储结构
值得注意的是，当特殊索引项来自Anchor
Text时，特殊索引项用来表示位置的信息（8位）将分为两部分：4位表示Anchor
Text出现的具体位置，另4位则用来与表示Anchor
Text所链接网页的docID相连接，这个docID是由URL
Resolver经过转化存入顺排档索引的。
(b)索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其Anchor
Text、URL指向等关键信息存入到Anchor文档库中。
(c)索引器生成一个索引词表(Lexicon)，它包括两个部分：关键词的列表和指针列表，用于倒排档文档相连接(如图3所示)。
(d)索引器还将分析过的网页编排成一个与Repository相连接的文档索引(Document
Index)，并记录下网页的URL和标题，以便可以准确查找出在Repository中存储的原网页内容。而且把没有分析的网页传给URL
Server，以便在下一次工作流程中进行索引分析。
⑤URL分析器（URL Resolver）读取Anchor文档中的信息，然后做⑥中的工作。
⑥(a)将其锚文本(Anchor
Text)所指向的URL转换成网页的docID；(b)将该docID与原网页的docID形成"链接对"，存入Link数据库中；(c)将Anchor
Text指向的网页的docID与顺排档特殊索引项Anchor Hits相连接。
⑦数据库Link记录了网页的链接关系，用来计算网页的PageRank值。
⑧文档索引(Document Index)把没有进行索引分析的网页传递给URL Server，URL
Server则向Crawler提供待遍历的URL，这样，这些未被索引的网页在下一次工作流程中将被索引分析。
⑨排序器（Sorter）对数据桶(Barrels)的顺排档索引重新进行排序，生成以关键词(wordID)为索引的倒排档索引。倒排档索引结构如图4所示：
图4 倒排档索引结构
⑩将生成的倒排档索引与先前由索引器产生的索引词表(Lexicon)相连接产生一个新的索引词表供搜索器(Searcher)使用。搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引(Document
Index)和Link数据库计算的网页PageRank值来匹配检索。
在执行检索时，Google通常遵循以下步骤（以下所指的是单个检索词的情况）：
(1)将检索词转化成相应的wordID；
(2)利用Lexicon，检索出包含该wordID的网页的docID；
(3)根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引；
(4)根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序；
(5)调用Document
Index中的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户。
用户检索包含多个检索词的情况与以上单个检索词的情况类似：先做单个检索词的检索，然后根据检索式中检索符号的要求进行必要的布尔操作或其他操作。
google搜索原理论文的中文版
这篇文章中，我们介绍了google，它是一个大型的搜索引擎（of a large-scale
search
engine）的原型，搜索引擎在超文本中应用广泛。Google的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24'000'000个网页。我们可以从
http://google.stanford.edu/ 下载。
设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且每天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。
本文详细介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此详细。除了把传统数据搜索技术应用到如此大量级网页中所遇到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。
本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。
关键词 World Wide Web，搜索引擎，信息检索，PageRank, Google 1 绪论 Web
给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象Yahoo这样重要的网页或搜索引擎开始。大家认为List(目录)有效地包含了大家感兴趣的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。
我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。
1.1网络搜索引擎—升级换代（scaling up）：1994-2000
搜索引擎技术不得不快速升级（scale
dramatically）跟上成倍增长的web数量。1994年，第一个Web搜索引擎，World Wide
Web
Worm(WWWW)[McBryan94]可以检索到110，000个网页和Web的文件。到1994年11月，顶级的搜索引擎声称可以检索到2'000'000（WebCrawler）至100'000'000个网络文件（来自
Search Engine
Watch）。可以预见到2000年，可检索到的网页将超过1'000'000'000。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，World
Wide Web Worm 平均每天收到1500个查询。
在1997年11月，Altavista
声称它每天要处理大约20'000'000个查询。随着网络用户的增长，到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术（scaling
search engine technology），把它升级到如此大量的数据上。
1.2 Google：跟上Web的步伐（Scaling with the
Web）建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快，才能跟上网页变化的速度（keep
them up to
date）。存储索引和文档的空间必须足够大。索引系统必须能够有效地处理上千亿的数据。处理查询必须快，达到每秒能处理成百上千个查询（hundreds
to thousands per
second.）。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的执行效率和成本也在快速增长，可以部分抵消这些困难。
还有几个值得注意的因素，如磁盘的寻道时间（disk seek
time），操作系统的效率（operating system
robustness）。在设计Google的过程中，我们既考虑了Web的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理海量数据集。它能够有效地利用存储空间来存储索引。优化的数据结构能够快速有效地存取（参考4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（参考附录B）。对于象Google这样的集中式系统，采取这些措施得到了令人满意的系统可升级性（scaling
properties）。
1. 3设计目标
1.3.1提高搜索质量我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引（a
complete search index）可以使查找任何数据都变得容易。根据Best of the Web
1994 -- Navigators
，"最好的导航服务可以使在Web上搜索任何信息都很容易（当时所有的数据都可以被登录）"。然而1997年的Web就迥然不同。近来搜索引擎的用户已经证实索引的完整性不是评价搜索质量的唯一标准。用户感兴趣的搜索结果往往湮没在"垃圾结果Junk
result"中。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己（搜索自己名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。用户仍然只希望看前面几十个搜索结果。因此，当集合增大时，我们就需要工具使结果精确（在返回的前几十个结果中，有关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人高兴的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori
97] [Spertus 97] [Weiss 96] [Kleinberg
98]。尤其是链接结构[98页]和链接文本，为相关性的判断和高质量的过滤提供了大量的信息。Google既利用了链接结构又用到了anchor文本（见2.1和2.2节）。
1.3.2搜索引擎的学术研究随着时间的流逝，除了发展迅速，Web越来越商业化。1993年，只有1.5%的Web服务是来自.com域名。到1997年，超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少技公开术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（见附录A）。Google的主要目标是推动学术领域在此方面的发展，和对它的了解。另一个设计目标是给大家一个实用的系统。应用对我们来说非常重要，因为现代网络系统中存在大量的有用数据（us
because we think some of the most interesting research will involve
leveraging the vast amount of usage data that is available from modern web
systems）。例如，每天有几千万个研究。然而，得到这些数据却非常困难，主要因为它们没有商业价值。我们最后的设计目标是建立一个体系结构能够支持新的关于海量Web数据的研究。为了支持新研究，Google以压缩的形式保存了实际所抓到的文档。设计google的目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量Web数据，得到满意的结果，而通过其它方法却很难得到结果。系统在短时间内被建立起来，已经有几篇论文用到了Google建的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究者甚至学生都可以对我们的海量Web数据设计或做一些实验。
2. 系统特点 Google搜索引擎有两个重要特点，有助于得到高精度的搜索结果。
第一点，应用Web的链接结构计算每个网页的Rank值，称为PageRank，将在98页详细描述它。
第二点，Google利用超链接改进搜索结果。
2.1 PageRank:给网页排序
Web的引用（链接）图是重要的资源，却被当今的搜索引擎很大程度上忽视了。我们建立了一个包含518'000'000个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们心目中对一个网页重要程度的评价，建立的基础是通过引用判断重要性。因此在web中，PageRank能够优化关键词查询的结果。对于大多数的主题，在网页标题查询中用PageRank优化简单文本匹配，我们得到了令人惊叹的结果（从google.stanford.edu可以得到演示）。对于Google主系统中的全文搜索，PageRank也帮了不少忙。
2.1.1计算PageRank
文献检索中的引用理论用到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）可以用简单的迭代算法计算，相应规格化Web链接矩阵的主特征向量。中等规模的网站计算26'000'000网页的PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。
2.1.2直觉判断
PageRank被看作用户行为的模型。我们假设网上冲浪是随机的，不断点击链接，从不返回，最终烦了，另外随机选一个网页重新开始冲浪。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值。我们还有其它的PageRank算法，见98页。
另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。
2.2链接描述文字（Anchor
Text）我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页（the
page that the link is
on）联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。
第一，通常链接描述文字比网页本身更精确地描述该网页。
第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意哪些抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。链接描述文字是对被链向网页的宣传，这个思想被用在World
Wide Web Worm [McBryan
94]中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24'000'000个网页，已经检索到259'000'000多个链接描述文字。
2.3其它特点除了PageRank和应用链接描述文字外，Google还有一些其它特点。
第一,所有hit都有位置信息，所以它可以在搜索中广泛应用邻近性（proximity）。
第二，Google跟踪一些可视化外表细节，例如字号。黑体大号字比其它文字更重要。
第三，知识库存储了原始的全文html网页。
3有关工作 Web检索研究的历史简短。World Wide Web Worm（[McBryan
94]）是最早的搜索引擎之一。后来出现了一些用于学术研究的搜索引擎，现在它们中的大多数被上市公司拥有。与Web的增长和搜索引擎的重要性相比，有关当今搜索引擎技术的优秀论文相当少[Pinkerton
94]。根据Michael Mauldin（Lycos Inc的首席科学家）)
[Mauldin]，"各种各样的服务（包括Lycos）非常关注这些数据库的细节。"虽然在搜索引擎的某些特点上做了大量工作。具有代表性的工作有，对现有商业搜索引擎的结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤其在有组织机构集合（well
controlled
collections）方面。在下面两节，我们将讨论在信息检索系统中的哪些领域需要改进以便更好的工作在Web上。
3.1信息检索信息检索系统诞生在几年前，并发展迅速。然而大多数信息检索系统研究的对象是小规模的单一的有组织结构的集合，例如科学论文集，或相关主题的新闻故事。实际上，信息检索的主要基准，the
Text Retrieval Conference（[TREC
96]），用小规模的、有组织结构的集合作为它们的基准。
大型文集基准只有20GB，相比之下，我们抓到的24000000个网页占147GB。在TREC上工作良好的系统，在Web上却不一定产生好的结果。例如，标准向量空间模型企图返回和查询请求最相近的文档，把查询请求和文档都看作由出现在它们中的词汇组成的向量。在Web环境下，这种策略常常返回非常短的文档，这些文档往往是查询词再加几个字。例如，查询"Bill
Clinton"，返回的网页只包含"Bill Clinton
Sucks"，这是我们从一个主要搜索引擎中看到的。网络上有些争议，用户应该更准确地表达他们想查询什么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象"Bill
Clinton"这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。象所给的例子，我们认为信息检索标准需要发展，以便有效地处理Web数据。
3.2有组织结构的集合（Well Controlled Collections）与Web的不同点
Web是完全无组织的异构的大量文档的集合。Web中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言（既有人类语言又有程序），词汇（email地址，链接，邮政编码，电话号码，产品号），类型（文本，HTML，PDF，图像，声音），有些甚至是机器创建的文件（log文件，或数据库的输出）。可以从文档中推断出来，但并不包含在文档中的信息称为隐含信息。隐含信息包括来源的信誉，更新频率，质量，访问量和引用。不但隐含信息的可能来源各种各样，而且被检测的信息也大不相同，相差可达好几个数量级。例如，一个重要主页的使用量，象Yahoo
每天浏览数达到上百万次，于此相比无名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。
Web与有组织结构集合之间的另外一个明显区别是，事实上，向Web上传信息没有任何限制。灵活利用这点可以发布任何对搜索引擎影响重大的信息，使路由阻塞，加上为牟利故意操纵搜索引擎，这些已经成为一个严重的问题。这些问题还没有被传统的封闭的信息检索系统所提出来。它关心的是元数据的努力，这在Web搜索引擎中却不适用，因为网页中的任何文本都不会向用户声称企图操纵搜索引擎。甚至有些公司为牟利专门操纵搜索引擎。
4 系统分析（System
Anatomy）首先，我们提供高水平的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将被严格地检查。
Figure 1. High Level Google Architecture
4.1Google体系结构概述这一节，我们将看看整个系统是如何工作的（give a high
level），见图1。本节不讨论应用和数据结构，在后几节中讨论。为了效率大部分Google是用c或c++实现的，既可以在Solaris也可以在Linux上运行。
Google系统中，抓网页（下载网页）是由几个分布式crawlers完成的。一个URL服务器负责向crawlers提供URL列表。抓来的网页交给存储服务器storeserver。然后，由存储服务器压缩网页并把它们存到知识库repository中。每个网页都有一个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知识库 Figure 2. Repository Data Structure
知识库包含每个网页的全部HTML。每个网页用zlib（见RFC1950）压缩。压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。
4.2.3文件索引文件索引保存了有关文档的一些信息。索引以docID的顺序排列，定宽ISAM（Index
sequential access
mode）。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向docinfo文件，该文件的宽度可变，包含了URL和标题。否则指针指向包含这个URL的URL列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表，按校验和排序。要想知道某个URL的docID，需要计算URL的校验和，然后在校验和文件中执行二进制查找，找到它的docID。通过对这个文件进行合并，可以把一批URL转换成对应的docID。URL分析器用这项技术把URL转换成docID。这种成批更新的模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322'000'000个链接的数据集合将花费一个多月的时间。
4.2.4词典词典有几种不同的形式。和以前系统的重要不同是，词典对内存的要求可以在合理的价格内。现在实现的系统，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14000000词汇（虽然一些很少用的词汇没有加入到词典中）。它执行分两部分—词汇表（用null分隔的连续串）和指针的哈希表。不同的函数，词汇表有一些辅助信息，这超出了本文论述的范围。
4.2.5 hit list hit
list是一篇文档中所出现的词的列表，包括位置，字号，大小写。Hit
list占很大空间，用在正向和反向索引中。因此，它的表示形式越有效越好。我们考虑了几种方案来编码位置，字号，大小写—简单编码（3个整型数），紧凑编码（支持优化分配比特位），哈夫曼编码。Hit的详细信息见图3。我们的紧凑编码每个hit用2字节。有两种类型hit，特殊hit和普通hit。特殊hit包含URL，标题，链接描述文字，meta
tag。普通hit包含其它每件事。它包括大小写特征位，字号，12比特用于描述词在文档中的位置（所有超过4095的位置标记为4096）。字号采用相对于文档的其它部分的相对大小表示，占3比特(实际只用7个值，因为111标志是特殊hit)。特殊hit由大小写特征位，字号位为7表示它是特殊hit，用4比特表示特殊hit的类型，8比特表示位置。对于anchor
hit八比特位置位分出4比特用来表示在anchor中的位置，4比特用于表明anchor出现的哈希表hash
of the
docID。短语查询是有限的，对某些词没有足够多的anchor。我们希望更新anchor
hit的存储方式，以便解决地址位和docIDhash域位数不足的问题。
因为搜索时，你不会因为文档的字号比别的文档大而特殊对待它，所以采用相对字号。
hit表的长度存储在hit前。为节省空间hit表长度，在正向索引中和wordID结合在一起，在反向索引中和docID结合存储。这就限制它相应地只占8到5比特（用些技巧，可以从wordID中借8bit）如果大于这些比特所能表示的长度，用溢出码填充，其后两字节是真正的长度。
Figure 3. Forward and Reverse Indexes and the Lexicon
4.2.6正向索引实际上，正向索引已经部分排序。它被存在一定数量的barrel中（我们用64个barrels）。每个barrel装着一定范围的wordID。如果一篇文档中的词落到某个barrel，它的docID将被记录到这个barrel中，紧跟着那些词（文档中所有的词汇，还是落入该barrel中的词汇）对应的hitlist。这种模式需要稍多些的存储空间，因为一个docID被用多次，但是它节省了桶数和时间，最后排序器进行索引时降低编码的复杂度。更进一步的措施是，我们不是存储docID本身，而是存储相对于该桶最小的docID的差。用这种方法，未排序的barrel的docID只需24位，省下8位记录hitlist长。
4.2.7反向索引除了反向索引由sorter加工处理之外，它和正向索引包含相同的桶。对每个有效的docID，字典包含一个指向该词所在桶的指针。它指向由docID和它的相应hitlist组成的doclish，这个doclist代表了所有包含该词的文档。
doclist中docID的顺序是一个重要的问题。最简单的解决办法是用doclish排序。这种方法合并多个词时很快。另一个可选方案是用文档中该词出现的次数排序。这种方法回答单词查询，所用时间微不足道。当多词查询时几乎是从头开始。并且当用其它Rank算法改进索引时，非常困难。我们综合了这两种方法，建立两组反向索引barrel，一组barrels的hitlist只包含标题和anchor
hit，另一组barrel包含全部的hitlist。我们首先查第一组索引桶，看有没有匹配的项，然后查较大的那组桶。
4.3抓网页运行网络爬行机器人是一项具有挑战性的任务。执行的性能和可靠性甚至更重要，还有一些社会焦点。网络爬行是一项非常薄弱的应用，它需要成百上千的web服务器和各种域名服务器的参与，这些服务器不是我们系统所能控制的。为了覆盖几十亿的网页，Google拥有快速的分布式网络爬行系统。一个URL服务器给若干个网络爬行机器人（我们采用3个）提供URL列表。URL服务器和网络爬行机器人都是用Python实现的。每个网络爬行机器人可以同时打开300个链接。抓取网页必须足够快。最快时，用4个网络爬行机器人每秒可以爬行100个网页。速率达每秒600K。执行的重点是找DNS。每个网络爬行机器人有它自己的DNS
cache，所以它不必每个网页都查DNS。每一百个连接都有几种不同的状态：查DNS，连接主机，发送请求，接收回答。这些因素使网络爬行机器人成为系统比较复杂的部分。它用异步IO处理事件，若干请求队列从一个网站到另一个网站不停的抓取网页。运行一个链接到500多万台服务器的网页爬行机器人，产生1千多万登陆口，导致了大量的Email和电话。因为网民众多，总有些人不知道网络爬行机器人是何物，这是他们看到的第一个网络爬行机器人。几乎每天我们都会收到这样的Email"哦，你从我们的网站看了太多的网页，你想干什么？"还有一些人不知道网络搜索机器人避免协议（the
robots exclusion
protocol），以为他们的网页上写着"版权所有，勿被索引"的字样就会被保护不被索引，不必说，这样的话很难被web
crawler理解。因为数据量如此之大，还会遇到一些意想不到的事情。例如，我们的系统曾经企图抓一个在线游戏，结果抓到了游戏中的大量垃圾信息。解决这个问题很简单。但是我们下载了几千万网页后才发现了这个问题。因为网页和服务器的种类繁多，实际上不在大部分Internet上运行它就测试一个网页爬行机器人是不可能。总是有几百个隐含的问题发生在整个web的一个网页上，导致网络爬行机器人崩溃，或者更糟，导致不可预测的不正确的行为。能够访问大部分Internet的系统必须精力充沛并精心测试过。由于象crawler这样大型复杂的系统总是产生这样那样的问题，因此花费一些资源读这些Email，当问题发生时解决它，是有必要的。
4.4Web索引分析—任何运行在整个Web上的分析器必须能够处理可能包含错误的大型集合。范围从HTML标记到标记之间几K字节的0，非ASCII字符，几百层HTML标记的嵌套，各种各样令人难以想象的错误。为了获得最大的速度，我们没有采用YACC产生上下文无关文法CFG分析器，而是采用灵活的方式产生词汇分析器，它自己配有堆栈。分析器的改进大大提高了运行速度，它的精力如此充沛完成了大量工作。把文档装入barrel建立索引—分析完一篇文档，之后把该文档装入barrel中，用内存中的hash表—字典，每个词汇被转换成一个wordID。当hash表字典中加入新的项时，笨拙地存入文件。一旦词汇被转换成wordID，它们在当前文档的出现就转换成hitlist，被写进正向barrel。索引阶段并行的主要困难是字典需要共享。
我们采用的方法是，基本字典中有140万个固定词汇，不在基本字典中的词汇写入日志，而不是共享字典。这种方法多个索引器可以并行工作，最后一个索引器只需处理一个较小的额外词汇日志。排序—为了建立反向索引，排序器读取每个正向barrel，以wordID排序，建立只有标题anchor
hi
t的反向索引barrel和全文反向索引barrel。这个过程一次只处理一个barrel，所以只需要少量暂存空间。排序阶段也是并行的，我们简单地同时运行尽可能多的排序器，不同的排序器处理不同的桶。由于barrel不适合装入主存，排序器进一步依据wordID和docID把它分成若干篮子，以便适合装入主存。然后排序器把每个篮子装入主存进行排序，并把它的内容写回到短反向barrel和全文反向barrel。
4.5搜索搜索的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率方面花费了很大力气。因此我们的研究以搜索质量为重点，相信我们的解决方案也可以用到那些商业系统中。
Google查询评价过程见图4。
1. 分析查询。
2. 把词汇转换成wordID。
3. 在短barrel中查找每个词汇doclist的开头。
4. 扫描doclist直到找到一篇匹配所有关键词的文档
5. 计算该文档的rank
6.
如果我们在短barrel，并且在所有doclist的末尾，开始从全文barrel的doclist的开头查找每个词，goto
第四步
7. 如果不在任何doclist的结尾，返回第四步。
8. 根据rank排序匹配文档，返回前k个。图4
Google查询评价在有限的响应时间内，一旦找到一定数量的匹配文档，搜索引擎自动执行步骤8。这意味着，返回的结果是子优化的。我们现在研究其它方法来解决这个问题。过去根据PageRank排序hit，看来能够改进这种状况。
4.5.1 Ranking系统
Google比典型搜索引擎保存了更多的web信息。每个hitlish包括位置，字号，大小写。另外，我们还考虑了链接描述文字。Rank综合所有这些信息是困难的。ranking函数设计依据是没有某个因素对rank影响重大。首先，考虑最简单的情况—单个词查询。为了单个词查询中一个文档的rank，Goole在文档的hitlist中查找该词。Google认为每个hit是几种不同类型（标题，链接描述文字anchor，URL，普通大字号文本，普通小字号文本，……）之一，每种有它自己的类型权重。类型权重建立了一个类型索引向量。Google计算hitlist中每种hit的数量。然后每个hit数转换成count-weight。Count-weight开始随hit数线性增加，很快逐渐停止，以至于hit数与此不相关。我们计算count-weight向量和type-weight向量的标量积作为文档的IR值。最后IR值结合PageRank作为文档的最后rank
对于多词查询，更复杂些。现在，多词hitlist必须同时扫描，以便关键词出现在同一文档中的权重比分别出现时高。相邻词的hit一起匹配。对每个匹配hit
的集合计算相邻度。相邻度基于hit在文档中的距离，分成10个不同的bin值，范围从短语匹配到根本不相关。不仅计算每类hit数，而且要计算每种类型的相邻度，每个类型相似度对，有一个类型相邻度权type-prox-weight。Count转换成count-weight，计算count-weight
type-proc-weight的标量积作为IR值。应用某种debug
mode所有这些数和矩阵与查询结果一起显示出来。这些显示有助于改进rank系统。
4.5.2反馈
rank函数有很多参数象type-weight和type-prox-weight。指明这些参数的正确值有点黑色艺术black
art。为此，我们的搜索引擎有一个用户反馈机制。值得信任的用户可以随意地评价返回的结果。保存反馈。然后，当修改rank函数时，对比以前搜索的rank，我们可以看到修改带来的的影响。虽然不是十全十美，但是它给出了一些思路，当rank函数改变时对搜索结果的影响。
5执行和结果搜索结果的质量是搜索引擎最重要的度量标准。完全用户评价体系超出了本文的论述范围，对于大多数搜索，我们的经验说明Google的搜索结果比那些主要的商业搜索引擎好。作为一个应用PageRank，链接描述文字，相邻度的例子，图4给出了Google搜索bill
Clinton的结果。它说明了Google的一些特点。服务器对结果进行聚类。这对过滤结果集合相当有帮助。这个查询，相当一部分结果来自whitehouse.gov域，这正是我们所需要的。现在大多数商业搜索引擎不会返回任何来自whitehouse.gov的结果，这是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。Google是根据链接描述文字决定它是一个好的查询结果。同样地，第五个结果是一个Email地址，当然是不可能抓到的。也是链接描述文字的结果。所有这些结果质量都很高，最后检查没有死链接。因为它们中的大部分PageRank值较高。PageRank百分比用红色线条表示。没有结果只含Bill没有Clinton或只含Clinton没有Bill。因为词出现的相近性非常重要。当然搜索引擎质量的真实测试包含广泛的用户学习或结果分析，此处篇幅有限，请读者自己去体验Google，
http://google.stanford.edu/。
5.1存储需求除了搜索质量，Google的设计可以随着Web规模的增大而有效地增大成本。一方面有效地利用存储空间。表1列出了一些统计数字的明细表和Google存储的需求。由于压缩技术的应用知识库只需53GB的存储空间。是所有要存储数据的三分之一。按当今磁盘价格，知识库相对于有用的数据来说比较便宜。搜索引擎需要的所有数据的存储空间大约55GB。大多数查询请求只需要短反向索引。文件索引应用先进的编码和压缩技术，一个高质量的搜索引擎可以运行在7GB的新PC。
5.2系统执行搜索引擎抓网页和建立索引的效率非常重要。Google的主要操作是抓网页，索引，排序。很难测试抓全部网页需要多少时间，因为磁盘满了，域名服务器崩溃，或者其它问题导致系统停止。总的来说，大约需要9天时间下载26000000网页（包括错误）。然而，一旦系统运行顺利，速度非常快，下载最后11000000网页只需要63小时，平均每天4000000网页，每秒48.5个网页。索引器和网络爬行机器人同步运行。索引器比网络爬行机器人快。因为我们花费了大量时间优化索引器，使它不是瓶颈。这些优化包括批量更新文档索引，本地磁盘数据结构的安排。索引器每秒处理54个网页。排序器完全并行，用4台机器，排序的整个过程大概需要24小时。
5.3搜索执行改进搜索执行不是我们研究的重点。当前版本的Google可以在1到10秒间回答查询请求。时间大部分花费在NFS磁盘IO上（由于磁盘普遍比机器慢）。进一步说，Google没有做任何优化，例如查询缓冲区，常用词汇子索引，和其它常用的优化技术。我们倾向于通过分布式，硬件，软件，和算法的改进来提高Google的速度。我们的目标是每秒能处理几百个请求。表2有几个现在版本Google响应查询时间的例子。它们说明IO缓冲区对再次搜索速度的影响。
6结论 Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide
Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。
6.1未来的工作大型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请求缓冲区，巧妙地分配磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这个目标已经由[Cho
98]实现了。受需求驱动，用代理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索引，共24000000个网页，用时不到一星期。我们希望能在一个月内建立100000000网页的索引。
6.4研究工具
Google不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如[Abiteboul
97]，提出了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数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。参考文献
•
Google的设计目标是可升级到10亿网页。我们的磁盘和机器大概能处理这么多网页。系统各个部分耗费的总时间是并行的和线性的。包括网页爬行机器人，索引器和排序器。扩展后我们认为大多数数据结构运行良好。然而10亿网页接近所有常用操作系统的极限（我们目前运行在Solaris和Linux上）。包括主存地址，开放文件描述符的数量，网络socket和带宽，以及其它因素。我们认为当网页数量大大超过10亿网页时，会大大增加系统复杂性。
9.2集中式索引体系的可升级性随着计算机性能的提高，海量文本索引的成本比较公平。当然带宽需求高的其它应用如视频，越来越普遍。但是，与多媒体例如视频相比，文本产品的成本低，因此文本仍然普遍。
search
engine）的原型，搜索引擎在超文本中应用广泛。Google的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24'000'000个网页。我们可以从
http://google.stanford.edu/ 下载。
设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且每天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。
本文详细介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此详细。除了把传统数据搜索技术应用到如此大量级网页中所遇到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。
本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。
关键词 World Wide Web，搜索引擎，信息检索，PageRank, Google 1 绪论 Web
给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象Yahoo这样重要的网页或搜索引擎开始。大家认为List(目录)有效地包含了大家感兴趣的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。
我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。
1.1网络搜索引擎—升级换代（scaling up）：1994-2000
搜索引擎技术不得不快速升级（scale
dramatically）跟上成倍增长的web数量。1994年，第一个Web搜索引擎，World Wide
Web
Worm(WWWW)[McBryan94]可以检索到110，000个网页和Web的文件。到1994年11月，顶级的搜索引擎声称可以检索到2'000'000（WebCrawler）至100'000'000个网络文件（来自
Search Engine
Watch）。可以预见到2000年，可检索到的网页将超过1'000'000'000。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，World
Wide Web Worm 平均每天收到1500个查询。
在1997年11月，Altavista
声称它每天要处理大约20'000'000个查询。随着网络用户的增长，到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术（scaling
search engine technology），把它升级到如此大量的数据上。
1.2 Google：跟上Web的步伐（Scaling with the
Web）建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快，才能跟上网页变化的速度（keep
them up to
date）。存储索引和文档的空间必须足够大。索引系统必须能够有效地处理上千亿的数据。处理查询必须快，达到每秒能处理成百上千个查询（hundreds
to thousands per
second.）。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的执行效率和成本也在快速增长，可以部分抵消这些困难。
还有几个值得注意的因素，如磁盘的寻道时间（disk seek
time），操作系统的效率（operating system
robustness）。在设计Google的过程中，我们既考虑了Web的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理海量数据集。它能够有效地利用存储空间来存储索引。优化的数据结构能够快速有效地存取（参考4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（参考附录B）。对于象Google这样的集中式系统，采取这些措施得到了令人满意的系统可升级性（scaling
properties）。
1. 3设计目标
1.3.1提高搜索质量我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引（a
complete search index）可以使查找任何数据都变得容易。根据Best of the Web
1994 -- Navigators
，"最好的导航服务可以使在Web上搜索任何信息都很容易（当时所有的数据都可以被登录）"。然而1997年的Web就迥然不同。近来搜索引擎的用户已经证实索引的完整性不是评价搜索质量的唯一标准。用户感兴趣的搜索结果往往湮没在"垃圾结果Junk
result"中。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己（搜索自己名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。用户仍然只希望看前面几十个搜索结果。因此，当集合增大时，我们就需要工具使结果精确（在返回的前几十个结果中，有关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人高兴的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori
97] [Spertus 97] [Weiss 96] [Kleinberg
98]。尤其是链接结构[98页]和链接文本，为相关性的判断和高质量的过滤提供了大量的信息。Google既利用了链接结构又用到了anchor文本（见2.1和2.2节）。
1.3.2搜索引擎的学术研究随着时间的流逝，除了发展迅速，Web越来越商业化。1993年，只有1.5%的Web服务是来自.com域名。到1997年，超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少技公开术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（见附录A）。Google的主要目标是推动学术领域在此方面的发展，和对它的了解。另一个设计目标是给大家一个实用的系统。应用对我们来说非常重要，因为现代网络系统中存在大量的有用数据（us
because we think some of the most interesting research will involve
leveraging the vast amount of usage data that is available from modern web
systems）。例如，每天有几千万个研究。然而，得到这些数据却非常困难，主要因为它们没有商业价值。我们最后的设计目标是建立一个体系结构能够支持新的关于海量Web数据的研究。为了支持新研究，Google以压缩的形式保存了实际所抓到的文档。设计google的目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量Web数据，得到满意的结果，而通过其它方法却很难得到结果。系统在短时间内被建立起来，已经有几篇论文用到了Google建的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究者甚至学生都可以对我们的海量Web数据设计或做一些实验。
2. 系统特点 Google搜索引擎有两个重要特点，有助于得到高精度的搜索结果。
第一点，应用Web的链接结构计算每个网页的Rank值，称为PageRank，将在98页详细描述它。
第二点，Google利用超链接改进搜索结果。
2.1 PageRank:给网页排序
Web的引用（链接）图是重要的资源，却被当今的搜索引擎很大程度上忽视了。我们建立了一个包含518'000'000个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们心目中对一个网页重要程度的评价，建立的基础是通过引用判断重要性。因此在web中，PageRank能够优化关键词查询的结果。对于大多数的主题，在网页标题查询中用PageRank优化简单文本匹配，我们得到了令人惊叹的结果（从google.stanford.edu可以得到演示）。对于Google主系统中的全文搜索，PageRank也帮了不少忙。
2.1.1计算PageRank
文献检索中的引用理论用到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）可以用简单的迭代算法计算，相应规格化Web链接矩阵的主特征向量。中等规模的网站计算26'000'000网页的PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。
2.1.2直觉判断
PageRank被看作用户行为的模型。我们假设网上冲浪是随机的，不断点击链接，从不返回，最终烦了，另外随机选一个网页重新开始冲浪。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值。我们还有其它的PageRank算法，见98页。
另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。
2.2链接描述文字（Anchor
Text）我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页（the
page that the link is
on）联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。
第一，通常链接描述文字比网页本身更精确地描述该网页。
第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意哪些抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。链接描述文字是对被链向网页的宣传，这个思想被用在World
Wide Web Worm [McBryan
94]中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24'000'000个网页，已经检索到259'000'000多个链接描述文字。
2.3其它特点除了PageRank和应用链接描述文字外，Google还有一些其它特点。
第一,所有hit都有位置信息，所以它可以在搜索中广泛应用邻近性（proximity）。
第二，Google跟踪一些可视化外表细节，例如字号。黑体大号字比其它文字更重要。
第三，知识库存储了原始的全文html网页。
3有关工作 Web检索研究的历史简短。World Wide Web Worm（[McBryan
94]）是最早的搜索引擎之一。后来出现了一些用于学术研究的搜索引擎，现在它们中的大多数被上市公司拥有。与Web的增长和搜索引擎的重要性相比，有关当今搜索引擎技术的优秀论文相当少[Pinkerton
94]。根据Michael Mauldin（Lycos Inc的首席科学家）)
[Mauldin]，"各种各样的服务（包括Lycos）非常关注这些数据库的细节。"虽然在搜索引擎的某些特点上做了大量工作。具有代表性的工作有，对现有商业搜索引擎的结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤其在有组织机构集合（well
controlled
collections）方面。在下面两节，我们将讨论在信息检索系统中的哪些领域需要改进以便更好的工作在Web上。
3.1信息检索信息检索系统诞生在几年前，并发展迅速。然而大多数信息检索系统研究的对象是小规模的单一的有组织结构的集合，例如科学论文集，或相关主题的新闻故事。实际上，信息检索的主要基准，the
Text Retrieval Conference（[TREC
96]），用小规模的、有组织结构的集合作为它们的基准。
大型文集基准只有20GB，相比之下，我们抓到的24000000个网页占147GB。在TREC上工作良好的系统，在Web上却不一定产生好的结果。例如，标准向量空间模型企图返回和查询请求最相近的文档，把查询请求和文档都看作由出现在它们中的词汇组成的向量。在Web环境下，这种策略常常返回非常短的文档，这些文档往往是查询词再加几个字。例如，查询"Bill
Clinton"，返回的网页只包含"Bill Clinton
Sucks"，这是我们从一个主要搜索引擎中看到的。网络上有些争议，用户应该更准确地表达他们想查询什么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象"Bill
Clinton"这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。象所给的例子，我们认为信息检索标准需要发展，以便有效地处理Web数据。
3.2有组织结构的集合（Well Controlled Collections）与Web的不同点
Web是完全无组织的异构的大量文档的集合。Web中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言（既有人类语言又有程序），词汇（email地址，链接，邮政编码，电话号码，产品号），类型（文本，HTML，PDF，图像，声音），有些甚至是机器创建的文件（log文件，或数据库的输出）。可以从文档中推断出来，但并不包含在文档中的信息称为隐含信息。隐含信息包括来源的信誉，更新频率，质量，访问量和引用。不但隐含信息的可能来源各种各样，而且被检测的信息也大不相同，相差可达好几个数量级。例如，一个重要主页的使用量，象Yahoo
每天浏览数达到上百万次，于此相比无名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。
Web与有组织结构集合之间的另外一个明显区别是，事实上，向Web上传信息没有任何限制。灵活利用这点可以发布任何对搜索引擎影响重大的信息，使路由阻塞，加上为牟利故意操纵搜索引擎，这些已经成为一个严重的问题。这些问题还没有被传统的封闭的信息检索系统所提出来。它关心的是元数据的努力，这在Web搜索引擎中却不适用，因为网页中的任何文本都不会向用户声称企图操纵搜索引擎。甚至有些公司为牟利专门操纵搜索引擎。
4 系统分析（System
Anatomy）首先，我们提供高水平的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将被严格地检查。
Figure 1. High Level Google Architecture
4.1Google体系结构概述这一节，我们将看看整个系统是如何工作的（give a high
level），见图1。本节不讨论应用和数据结构，在后几节中讨论。为了效率大部分Google是用c或c++实现的，既可以在Solaris也可以在Linux上运行。
Google系统中，抓网页（下载网页）是由几个分布式crawlers完成的。一个URL服务器负责向crawlers提供URL列表。抓来的网页交给存储服务器storeserver。然后，由存储服务器压缩网页并把它们存到知识库repository中。每个网页都有一个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知识库 Figure 2. Repository Data Structure
知识库包含每个网页的全部HTML。每个网页用zlib（见RFC1950）压缩。压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。
4.2.3文件索引文件索引保存了有关文档的一些信息。索引以docID的顺序排列，定宽ISAM（Index
sequential access
mode）。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向docinfo文件，该文件的宽度可变，包含了URL和标题。否则指针指向包含这个URL的URL列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表，按校验和排序。要想知道某个URL的docID，需要计算URL的校验和，然后在校验和文件中执行二进制查找，找到它的docID。通过对这个文件进行合并，可以把一批URL转换成对应的docID。URL分析器用这项技术把URL转换成docID。这种成批更新的模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322'000'000个链接的数据集合将花费一个多月的时间。
4.2.4词典词典有几种不同的形式。和以前系统的重要不同是，词典对内存的要求可以在合理的价格内。现在实现的系统，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14000000词汇（虽然一些很少用的词汇没有加入到词典中）。它执行分两部分—词汇表（用null分隔的连续串）和指针的哈希表。不同的函数，词汇表有一些辅助信息，这超出了本文论述的范围。
4.2.5 hit list hit
list是一篇文档中所出现的词的列表，包括位置，字号，大小写。Hit
list占很大空间，用在正向和反向索引中。因此，它的表示形式越有效越好。我们考虑了几种方案来编码位置，字号，大小写—简单编码（3个整型数），紧凑编码（支持优化分配比特位），哈夫曼编码。Hit的详细信息见图3。我们的紧凑编码每个hit用2字节。有两种类型hit，特殊hit和普通hit。特殊hit包含URL，标题，链接描述文字，meta
tag。普通hit包含其它每件事。它包括大小写特征位，字号，12比特用于描述词在文档中的位置（所有超过4095的位置标记为4096）。字号采用相对于文档的其它部分的相对大小表示，占3比特(实际只用7个值，因为111标志是特殊hit)。特殊hit由大小写特征位，字号位为7表示它是特殊hit，用4比特表示特殊hit的类型，8比特表示位置。对于anchor
hit八比特位置位分出4比特用来表示在anchor中的位置，4比特用于表明anchor出现的哈希表hash
of the
docID。短语查询是有限的，对某些词没有足够多的anchor。我们希望更新anchor
hit的存储方式，以便解决地址位和docIDhash域位数不足的问题。
因为搜索时，你不会因为文档的字号比别的文档大而特殊对待它，所以采用相对字号。
hit表的长度存储在hit前。为节省空间hit表长度，在正向索引中和wordID结合在一起，在反向索引中和docID结合存储。这就限制它相应地只占8到5比特（用些技巧，可以从wordID中借8bit）如果大于这些比特所能表示的长度，用溢出码填充，其后两字节是真正的长度。
Figure 3. Forward and Reverse Indexes and the Lexicon
4.2.6正向索引实际上，正向索引已经部分排序。它被存在一定数量的barrel中（我们用64个barrels）。每个barrel装着一定范围的wordID。如果一篇文档中的词落到某个barrel，它的docID将被记录到这个barrel中，紧跟着那些词（文档中所有的词汇，还是落入该barrel中的词汇）对应的hitlist。这种模式需要稍多些的存储空间，因为一个docID被用多次，但是它节省了桶数和时间，最后排序器进行索引时降低编码的复杂度。更进一步的措施是，我们不是存储docID本身，而是存储相对于该桶最小的docID的差。用这种方法，未排序的barrel的docID只需24位，省下8位记录hitlist长。
4.2.7反向索引除了反向索引由sorter加工处理之外，它和正向索引包含相同的桶。对每个有效的docID，字典包含一个指向该词所在桶的指针。它指向由docID和它的相应hitlist组成的doclish，这个doclist代表了所有包含该词的文档。
doclist中docID的顺序是一个重要的问题。最简单的解决办法是用doclish排序。这种方法合并多个词时很快。另一个可选方案是用文档中该词出现的次数排序。这种方法回答单词查询，所用时间微不足道。当多词查询时几乎是从头开始。并且当用其它Rank算法改进索引时，非常困难。我们综合了这两种方法，建立两组反向索引barrel，一组barrels的hitlist只包含标题和anchor
hit，另一组barrel包含全部的hitlist。我们首先查第一组索引桶，看有没有匹配的项，然后查较大的那组桶。
4.3抓网页运行网络爬行机器人是一项具有挑战性的任务。执行的性能和可靠性甚至更重要，还有一些社会焦点。网络爬行是一项非常薄弱的应用，它需要成百上千的web服务器和各种域名服务器的参与，这些服务器不是我们系统所能控制的。为了覆盖几十亿的网页，Google拥有快速的分布式网络爬行系统。一个URL服务器给若干个网络爬行机器人（我们采用3个）提供URL列表。URL服务器和网络爬行机器人都是用Python实现的。每个网络爬行机器人可以同时打开300个链接。抓取网页必须足够快。最快时，用4个网络爬行机器人每秒可以爬行100个网页。速率达每秒600K。执行的重点是找DNS。每个网络爬行机器人有它自己的DNS
cache，所以它不必每个网页都查DNS。每一百个连接都有几种不同的状态：查DNS，连接主机，发送请求，接收回答。这些因素使网络爬行机器人成为系统比较复杂的部分。它用异步IO处理事件，若干请求队列从一个网站到另一个网站不停的抓取网页。运行一个链接到500多万台服务器的网页爬行机器人，产生1千多万登陆口，导致了大量的Email和电话。因为网民众多，总有些人不知道网络爬行机器人是何物，这是他们看到的第一个网络爬行机器人。几乎每天我们都会收到这样的Email"哦，你从我们的网站看了太多的网页，你想干什么？"还有一些人不知道网络搜索机器人避免协议（the
robots exclusion
protocol），以为他们的网页上写着"版权所有，勿被索引"的字样就会被保护不被索引，不必说，这样的话很难被web
crawler理解。因为数据量如此之大，还会遇到一些意想不到的事情。例如，我们的系统曾经企图抓一个在线游戏，结果抓到了游戏中的大量垃圾信息。解决这个问题很简单。但是我们下载了几千万网页后才发现了这个问题。因为网页和服务器的种类繁多，实际上不在大部分Internet上运行它就测试一个网页爬行机器人是不可能。总是有几百个隐含的问题发生在整个web的一个网页上，导致网络爬行机器人崩溃，或者更糟，导致不可预测的不正确的行为。能够访问大部分Internet的系统必须精力充沛并精心测试过。由于象crawler这样大型复杂的系统总是产生这样那样的问题，因此花费一些资源读这些Email，当问题发生时解决它，是有必要的。
4.4Web索引分析—任何运行在整个Web上的分析器必须能够处理可能包含错误的大型集合。范围从HTML标记到标记之间几K字节的0，非ASCII字符，几百层HTML标记的嵌套，各种各样令人难以想象的错误。为了获得最大的速度，我们没有采用YACC产生上下文无关文法CFG分析器，而是采用灵活的方式产生词汇分析器，它自己配有堆栈。分析器的改进大大提高了运行速度，它的精力如此充沛完成了大量工作。把文档装入barrel建立索引—分析完一篇文档，之后把该文档装入barrel中，用内存中的hash表—字典，每个词汇被转换成一个wordID。当hash表字典中加入新的项时，笨拙地存入文件。一旦词汇被转换成wordID，它们在当前文档的出现就转换成hitlist，被写进正向barrel。索引阶段并行的主要困难是字典需要共享。
我们采用的方法是，基本字典中有140万个固定词汇，不在基本字典中的词汇写入日志，而不是共享字典。这种方法多个索引器可以并行工作，最后一个索引器只需处理一个较小的额外词汇日志。排序—为了建立反向索引，排序器读取每个正向barrel，以wordID排序，建立只有标题anchor
hi
t的反向索引barrel和全文反向索引barrel。这个过程一次只处理一个barrel，所以只需要少量暂存空间。排序阶段也是并行的，我们简单地同时运行尽可能多的排序器，不同的排序器处理不同的桶。由于barrel不适合装入主存，排序器进一步依据wordID和docID把它分成若干篮子，以便适合装入主存。然后排序器把每个篮子装入主存进行排序，并把它的内容写回到短反向barrel和全文反向barrel。
4.5搜索搜索的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率方面花费了很大力气。因此我们的研究以搜索质量为重点，相信我们的解决方案也可以用到那些商业系统中。
Google查询评价过程见图4。
1. 分析查询。
2. 把词汇转换成wordID。
3. 在短barrel中查找每个词汇doclist的开头。
4. 扫描doclist直到找到一篇匹配所有关键词的文档
5. 计算该文档的rank
6.
如果我们在短barrel，并且在所有doclist的末尾，开始从全文barrel的doclist的开头查找每个词，goto
第四步
7. 如果不在任何doclist的结尾，返回第四步。
8. 根据rank排序匹配文档，返回前k个。图4
Google查询评价在有限的响应时间内，一旦找到一定数量的匹配文档，搜索引擎自动执行步骤8。这意味着，返回的结果是子优化的。我们现在研究其它方法来解决这个问题。过去根据PageRank排序hit，看来能够改进这种状况。
4.5.1 Ranking系统
Google比典型搜索引擎保存了更多的web信息。每个hitlish包括位置，字号，大小写。另外，我们还考虑了链接描述文字。Rank综合所有这些信息是困难的。ranking函数设计依据是没有某个因素对rank影响重大。首先，考虑最简单的情况—单个词查询。为了单个词查询中一个文档的rank，Goole在文档的hitlist中查找该词。Google认为每个hit是几种不同类型（标题，链接描述文字anchor，URL，普通大字号文本，普通小字号文本，……）之一，每种有它自己的类型权重。类型权重建立了一个类型索引向量。Google计算hitlist中每种hit的数量。然后每个hit数转换成count-weight。Count-weight开始随hit数线性增加，很快逐渐停止，以至于hit数与此不相关。我们计算count-weight向量和type-weight向量的标量积作为文档的IR值。最后IR值结合PageRank作为文档的最后rank
对于多词查询，更复杂些。现在，多词hitlist必须同时扫描，以便关键词出现在同一文档中的权重比分别出现时高。相邻词的hit一起匹配。对每个匹配hit
的集合计算相邻度。相邻度基于hit在文档中的距离，分成10个不同的bin值，范围从短语匹配到根本不相关。不仅计算每类hit数，而且要计算每种类型的相邻度，每个类型相似度对，有一个类型相邻度权type-prox-weight。Count转换成count-weight，计算count-weight
type-proc-weight的标量积作为IR值。应用某种debug
mode所有这些数和矩阵与查询结果一起显示出来。这些显示有助于改进rank系统。
4.5.2反馈
rank函数有很多参数象type-weight和type-prox-weight。指明这些参数的正确值有点黑色艺术black
art。为此，我们的搜索引擎有一个用户反馈机制。值得信任的用户可以随意地评价返回的结果。保存反馈。然后，当修改rank函数时，对比以前搜索的rank，我们可以看到修改带来的的影响。虽然不是十全十美，但是它给出了一些思路，当rank函数改变时对搜索结果的影响。
5执行和结果搜索结果的质量是搜索引擎最重要的度量标准。完全用户评价体系超出了本文的论述范围，对于大多数搜索，我们的经验说明Google的搜索结果比那些主要的商业搜索引擎好。作为一个应用PageRank，链接描述文字，相邻度的例子，图4给出了Google搜索bill
Clinton的结果。它说明了Google的一些特点。服务器对结果进行聚类。这对过滤结果集合相当有帮助。这个查询，相当一部分结果来自whitehouse.gov域，这正是我们所需要的。现在大多数商业搜索引擎不会返回任何来自whitehouse.gov的结果，这是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。Google是根据链接描述文字决定它是一个好的查询结果。同样地，第五个结果是一个Email地址，当然是不可能抓到的。也是链接描述文字的结果。所有这些结果质量都很高，最后检查没有死链接。因为它们中的大部分PageRank值较高。PageRank百分比用红色线条表示。没有结果只含Bill没有Clinton或只含Clinton没有Bill。因为词出现的相近性非常重要。当然搜索引擎质量的真实测试包含广泛的用户学习或结果分析，此处篇幅有限，请读者自己去体验Google，
http://google.stanford.edu/。
5.1存储需求除了搜索质量，Google的设计可以随着Web规模的增大而有效地增大成本。一方面有效地利用存储空间。表1列出了一些统计数字的明细表和Google存储的需求。由于压缩技术的应用知识库只需53GB的存储空间。是所有要存储数据的三分之一。按当今磁盘价格，知识库相对于有用的数据来说比较便宜。搜索引擎需要的所有数据的存储空间大约55GB。大多数查询请求只需要短反向索引。文件索引应用先进的编码和压缩技术，一个高质量的搜索引擎可以运行在7GB的新PC。
5.2系统执行搜索引擎抓网页和建立索引的效率非常重要。Google的主要操作是抓网页，索引，排序。很难测试抓全部网页需要多少时间，因为磁盘满了，域名服务器崩溃，或者其它问题导致系统停止。总的来说，大约需要9天时间下载26000000网页（包括错误）。然而，一旦系统运行顺利，速度非常快，下载最后11000000网页只需要63小时，平均每天4000000网页，每秒48.5个网页。索引器和网络爬行机器人同步运行。索引器比网络爬行机器人快。因为我们花费了大量时间优化索引器，使它不是瓶颈。这些优化包括批量更新文档索引，本地磁盘数据结构的安排。索引器每秒处理54个网页。排序器完全并行，用4台机器，排序的整个过程大概需要24小时。
5.3搜索执行改进搜索执行不是我们研究的重点。当前版本的Google可以在1到10秒间回答查询请求。时间大部分花费在NFS磁盘IO上（由于磁盘普遍比机器慢）。进一步说，Google没有做任何优化，例如查询缓冲区，常用词汇子索引，和其它常用的优化技术。我们倾向于通过分布式，硬件，软件，和算法的改进来提高Google的速度。我们的目标是每秒能处理几百个请求。表2有几个现在版本Google响应查询时间的例子。它们说明IO缓冲区对再次搜索速度的影响。
6结论 Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide
Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank，链接描述文字，相邻信息。进一步说，Google是一个收集网页，建立索引，执行搜索请求的完整的体系结构。
6.1未来的工作大型Web搜索引擎是个复杂的系统，还有很多事情要做。我们直接的目标是提高搜索效率，覆盖大约100000000个网页。一些简单的改进提高了效率包括请求缓冲区，巧妙地分配磁盘空间，子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取，哪些新网页需要被抓取。这个目标已经由[Cho
98]实现了。受需求驱动，用代理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索引，共24000000个网页，用时不到一星期。我们希望能在一个月内建立100000000网页的索引。
6.4研究工具
Google不仅是高质量的搜索引擎，它还是研究工具。Google搜集的数据已经用在许多其它论文中，提交给学术会议和许多其它方式。最近的研究，例如[Abiteboul
97]，提出了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数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。参考文献
•
Google的设计目标是可升级到10亿网页。我们的磁盘和机器大概能处理这么多网页。系统各个部分耗费的总时间是并行的和线性的。包括网页爬行机器人，索引器和排序器。扩展后我们认为大多数数据结构运行良好。然而10亿网页接近所有常用操作系统的极限（我们目前运行在Solaris和Linux上）。包括主存地址，开放文件描述符的数量，网络socket和带宽，以及其它因素。我们认为当网页数量大大超过10亿网页时，会大大增加系统复杂性。
9.2集中式索引体系的可升级性随着计算机性能的提高，海量文本索引的成本比较公平。当然带宽需求高的其它应用如视频，越来越普遍。但是，与多媒体例如视频相比，文本产品的成本低，因此文本仍然普遍。
图2 Google系统的工作流程图
(注：原图来自Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale
Hypertextual. Web Search Engine, 1998.
http://www-db.stanford.edu/%7Ebackrub/Google.html)
①Google使用高速的分布式爬行器(Crawler)系统中的漫游遍历器(Googlebot)定时地遍历网页，将遍历到的网页送到存储服务器(Store
Server)中。
②存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据库Repository中。Repository获得了每个网页的完全Html代码后，对其压缩后的网页及URL进行分析，记录下网页长度、URL、URL长度和网页内容，并赋予每个网页一个文档号(docID)，以便当系统出现故障的时候，可以及时完整地进行网页的数据恢复。
③索引器(Indexer)从Repository中读取数据，以后做以下四步工作：
④(a)将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后，转化为关键词(wordID)的若干索引项(Hits)，生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。索引项列表被存入到数据桶(Barrels)中，并生成以文档号(docID)部分排序的顺排档索引。
索引项根据其重要程度分为两种：当索引项中的关键词出现在URL、标题、锚文本(Anchor
Text)和标签中时，表示该索引项比较重要，称为特殊索引项(Fancy
Hits)；其余情况则称为普通索引项(Plain
Hits)。在系统中每个Hit用两个字节(byte)存储结构表示：特殊索引项用1位(bit)表示大小写，用二进制代码111(占3位)表示是特殊索引项，其余12位有4位表示特殊索引项的类型(即hit是出现在URL、标题、链接结点还是标签中)，剩下8位表示hit在网页中的具体位置；普通索引项是用1位表示大小写，3位表示字体大小，其余12位表示在网页中的具体位置。
顺排档索引和Hit的存储结构如图3所示。
图3 顺排档索引和Hit的存储结构
值得注意的是，当特殊索引项来自Anchor
Text时，特殊索引项用来表示位置的信息（8位）将分为两部分：4位表示Anchor
Text出现的具体位置，另4位则用来与表示Anchor
Text所链接网页的docID相连接，这个docID是由URL
Resolver经过转化存入顺排档索引的。
(b)索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其Anchor
Text、URL指向等关键信息存入到Anchor文档库中。
(c)索引器生成一个索引词表(Lexicon)，它包括两个部分：关键词的列表和指针列表，用于倒排档文档相连接(如图3所示)。
(d)索引器还将分析过的网页编排成一个与Repository相连接的文档索引(Document
Index)，并记录下网页的URL和标题，以便可以准确查找出在Repository中存储的原网页内容。而且把没有分析的网页传给URL
Server，以便在下一次工作流程中进行索引分析。
⑤URL分析器（URL Resolver）读取Anchor文档中的信息，然后做⑥中的工作。
⑥(a)将其锚文本(Anchor
Text)所指向的URL转换成网页的docID；(b)将该docID与原网页的docID形成"链接对"，存入Link数据库中；(c)将Anchor
Text指向的网页的docID与顺排档特殊索引项Anchor Hits相连接。
⑦数据库Link记录了网页的链接关系，用来计算网页的PageRank值。
⑧文档索引(Document Index)把没有进行索引分析的网页传递给URL Server，URL
Server则向Crawler提供待遍历的URL，这样，这些未被索引的网页在下一次工作流程中将被索引分析。
⑨排序器（Sorter）对数据桶(Barrels)的顺排档索引重新进行排序，生成以关键词(wordID)为索引的倒排档索引。倒排档索引结构如图4所示：
图4 倒排档索引结构
⑩将生成的倒排档索引与先前由索引器产生的索引词表(Lexicon)相连接产生一个新的索引词表供搜索器(Searcher)使用。搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引(Document
Index)和Link数据库计算的网页PageRank值来匹配检索。
在执行检索时，Google通常遵循以下步骤（以下所指的是单个检索词的情况）：
(1)将检索词转化成相应的wordID；
(2)利用Lexicon，检索出包含该wordID的网页的docID；
(3)根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引；
(4)根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序；
(5)调用Document
Index中的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户。
用户检索包含多个检索词的情况与以上单个检索词的情况类似：先做单个检索词的检索，然后根据检索式中检索符号的要求进行必要的布尔操作或其他操作。
对网络连接的理解
一、连接有两类，一类是实连接，例如打固定电话，在线路上固定占用了一个通道，这个通道在通话期间是一直存在的；另一类是虚连接，TCP的连接就是这种，客户端连接到服务器端后，连接虽然建立了，但是实际上物理上并不是真正存在这样的通道。他们之间的连接是靠之间的数据包的往来确立的。所以，对于两台机器之间网络断掉，相互是不可能知道的，并没有什么东西能通知双方，而只能是通过事后发送数据包才能出现了问题，具体什么问题还需要进行判断。一般tcp连接都需要使用一些技术手段来维持，有两种方法：一是利用tcp协议本身，设置SO_KEEPALIVE；二是应用层增加链路检测包。
二、要明白应用进程和内核之间的区别，我们写一般的sokect程序，应用程序只是调用系统提供的函数接口，真正的实现都是内核来完成的，由于网络的特殊性，socket函数有着自己的一些特性，其收发函数都只是本机之间的操作，并不真正涉及到网络。例如send发送函数，返回成功只是表示我们把数据给了内核的发送缓冲区，并不是已经从网卡发送出去了，至于是否发送成功，send函数本身是不可能获得的；接收函数类似，只是表示从内核接收缓冲区拷贝到应用进程成功。
二、要明白应用进程和内核之间的区别，我们写一般的sokect程序，应用程序只是调用系统提供的函数接口，真正的实现都是内核来完成的，由于网络的特殊性，socket函数有着自己的一些特性，其收发函数都只是本机之间的操作，并不真正涉及到网络。例如send发送函数，返回成功只是表示我们把数据给了内核的发送缓冲区，并不是已经从网卡发送出去了，至于是否发送成功，send函数本身是不可能获得的；接收函数类似，只是表示从内核接收缓冲区拷贝到应用进程成功。
男人们并不是特意惹你生气，我们只是被误解了
男人们并不是特意惹你生气，我们只是被误解了。以下是对在婚姻中7种经典冲突中男性思维的解释。
根据国家统计局的调查（这总不会是假的吧），在68%的离婚案件中，女性胜诉。她们最流行使用的理由是行为，如果这词儿也流行的话（其实不然）。这暗示着两件可能人尽皆知的事情：第一，男人行为不捡；第二，很多女人在婚后几个月甚至几年后才慢慢明白这一点。这里看起来有不小的知识空白，没关系，简单普及一下，我就让你们明白了。我能够解释我们为什么会行为不检——或者，更确切的说，为什么你们认为我们行为不检，然而事实上，对我们来说，我们的行为是完全可以理解并符合逻辑的。
忘记东西
对于我们无法记住那些你们让我们记得的事情，有科学的原因可以解释。虽然女性大脑比男人的要小10%，其拥有的白质却比灰质多。白质主要用于记忆，而灰质更善于激活大脑进行重复而劳累的Xbox游戏。
这是基因构成，懂了吗？
你要记得：记不得不一定是件坏事儿。我们忘记说"我爱你"，我们忘记生日礼物。我们忘记去超市要买的东西，但是这些不代表我们不爱你们、不喜欢生日礼物或对买那些东西没兴趣，原因很简单，只能怪灰质。
看地图
"就是这条路。"
"为什么不停下来找个人问问呢？
"因为就是这条路。"
"可是我们已经走遍这个村子了。"
"我们没有。"
"有。"
有什么问题吗，姑奶奶们？没有啊，这不是我们在耍犟。是你们。你们和你们匮乏的同情心。我们知道自己错了，我们当然知道。但是我们要面子，我们的思维很简单，这一点，你们知道，我们也知道。承认输了，对我们来说是天大的耻辱，这与承认勃起障碍一样难。最重要的是，我们应该被允许兜圈子，直到我们自己走运或一次次的错了后，找到对的路。记住，永远一定不要说："我告诉过你停下来问问路的。"
你们就当我们是白痴，这样我们会对你们感激不缴，或许还会为你们准备不错的生日礼物——如果我们记得的话。不幸的是，我们通常记不得。
穿上这个我的屁股看起来丰满吗？
这也许是所有婚姻冲突中最不公正的事儿。你们不应该指望一个男人跟你们一整天的逛街，呆在过热的购物中心，周围充满了出着臭汗、无聊的人。有时候甚至等上几小时，站在试衣间外面，对这同样汗流浃背的无聊的男人，无奈的耸耸肩，而你却试穿了同样款式的19条裤子，还每次都问我们："穿这条，我的屁股是不是看起来大一些？"
虽然有着漫长而痛苦的回答这个恶魔问题的经历，我至今还未发现正确的回答。如果我们如实回答（"不是特别明显，我觉得还行"），你们会不说话，因我们不够积极。如果我们如实回答（"我不在乎你的屁股看起来怎么样，我们现在可以回去了吗？"），你会生气。如果我们撒谎（"天啊，真是太美了，你的屁股看起来好丰满啊！"），你会怀疑，然后再问我们问题，比如："你的意思是说我们可以回家了，是吧？"我们眼神的慌乱暴露了我们的意图，然后你们又让我们去另外一家商店。额的神啊！
请不要带我们去购物。你们穿什么我们都爱你们。只要正当的性感就行，但我们不想参与到购买的过程中。
DIY，以及为什么是我们的错？
在宜家之前，男人就能够DIY，现在我们也自认为可以。只是由于可拆装的瑞士货的到来，那些用一把艾伦六角把手无法解决的技术就失传了。但是问到关于奥克斯博湖，毕达哥拉斯定理或者Patsy
Kensit主演的电影中她的野兽使用的致命武器，我们可以立马告诉你。问到我们如何把插头装进非建筑墙内，我们也可以告诉你，只是我们的回答会不对。
在这里重要的是我们的热情。每年，在银行周末假期前，事故预防皇家协会都会公布一些令人震惊的统计数字，说明有多少男人在DIY时，经历了血淋淋的事故。今年，这些事故的第一号杀手工具是：刀子和解剖刀（导致了20000例急诊），锯子（15000例）最后是令人牙齿打颤的碾磨机（6500例）。"过度自信和知识的缺乏，"事故预防皇家协会的报道说，："是DIY事故的主要原因。"可是这不就是让你们对我们一见钟情的可爱特点之一吗？难道你们就不能不看功劳看苦劳吗？
看暴力电影
目前为止，你应该对婚姻关系中男人每天要做的事情所经历的那些害怕、紧张和痛苦有一点认识了吧？所以我们需要时间来放松。你们可以一遍遍念咒语似的说"能给我搓搓背吗？"来放松，我们就是看暴力电影。你们若是不想看，我们没意见。我们甚至不介意在浴室的小电视上看，以便让你看那该死的《飞黄腾达》（美国一档热门商业真人秀节目）。只是不要让我们看你们那些情节悲惨的古装剧，因为我们可能会哭，而男人是从不掉泪的。那样我们必须得面对自己的脆弱情感，那我们男人的面子往哪儿放？还是让我们赶紧往下说吧。
做爱以及其频率
最好是细水长流、毛毛雨常有，受不了要么旱死要么涝死。就像记忆一样，这个也是有科学根据的，而且是我们控制范围之外的。
看其他女人
还是科学的缘故，同样是我们不由自主的。根据《那不是因为你，而是生物原因》的作者Joe
Quirk的看法，男人和女人拥有相互排斥的繁殖系统。女人生成一个卵子需要29.5天，如果这个卵子受孕了，她们又得十月怀胎，然后是数月或数年的母乳喂养。然而，男人几秒钟内就可以产生300万只精子，如果观察野牛、鸟、猿类和你自己的狗，一般情况下，你会发现雄性大多淫荡而雌性比较挑剔。当代的男人，Silvio
Berlusconi（新当选的意大利总统，传出众多绯闻）除外，已经完成了从猿到人的转变，除了两个方面：不盖马桶盖，看其他女人。可是我们也为之付出了沉重的代价：一次次的去购物，和那些被扔在被子外面的漫漫寒夜。
总之，你们赢了，现在我们结案。
根据国家统计局的调查（这总不会是假的吧），在68%的离婚案件中，女性胜诉。她们最流行使用的理由是行为，如果这词儿也流行的话（其实不然）。这暗示着两件可能人尽皆知的事情：第一，男人行为不捡；第二，很多女人在婚后几个月甚至几年后才慢慢明白这一点。这里看起来有不小的知识空白，没关系，简单普及一下，我就让你们明白了。我能够解释我们为什么会行为不检——或者，更确切的说，为什么你们认为我们行为不检，然而事实上，对我们来说，我们的行为是完全可以理解并符合逻辑的。
忘记东西
对于我们无法记住那些你们让我们记得的事情，有科学的原因可以解释。虽然女性大脑比男人的要小10%，其拥有的白质却比灰质多。白质主要用于记忆，而灰质更善于激活大脑进行重复而劳累的Xbox游戏。
这是基因构成，懂了吗？
你要记得：记不得不一定是件坏事儿。我们忘记说"我爱你"，我们忘记生日礼物。我们忘记去超市要买的东西，但是这些不代表我们不爱你们、不喜欢生日礼物或对买那些东西没兴趣，原因很简单，只能怪灰质。
看地图
"就是这条路。"
"为什么不停下来找个人问问呢？
"因为就是这条路。"
"可是我们已经走遍这个村子了。"
"我们没有。"
"有。"
有什么问题吗，姑奶奶们？没有啊，这不是我们在耍犟。是你们。你们和你们匮乏的同情心。我们知道自己错了，我们当然知道。但是我们要面子，我们的思维很简单，这一点，你们知道，我们也知道。承认输了，对我们来说是天大的耻辱，这与承认勃起障碍一样难。最重要的是，我们应该被允许兜圈子，直到我们自己走运或一次次的错了后，找到对的路。记住，永远一定不要说："我告诉过你停下来问问路的。"
你们就当我们是白痴，这样我们会对你们感激不缴，或许还会为你们准备不错的生日礼物——如果我们记得的话。不幸的是，我们通常记不得。
穿上这个我的屁股看起来丰满吗？
这也许是所有婚姻冲突中最不公正的事儿。你们不应该指望一个男人跟你们一整天的逛街，呆在过热的购物中心，周围充满了出着臭汗、无聊的人。有时候甚至等上几小时，站在试衣间外面，对这同样汗流浃背的无聊的男人，无奈的耸耸肩，而你却试穿了同样款式的19条裤子，还每次都问我们："穿这条，我的屁股是不是看起来大一些？"
虽然有着漫长而痛苦的回答这个恶魔问题的经历，我至今还未发现正确的回答。如果我们如实回答（"不是特别明显，我觉得还行"），你们会不说话，因我们不够积极。如果我们如实回答（"我不在乎你的屁股看起来怎么样，我们现在可以回去了吗？"），你会生气。如果我们撒谎（"天啊，真是太美了，你的屁股看起来好丰满啊！"），你会怀疑，然后再问我们问题，比如："你的意思是说我们可以回家了，是吧？"我们眼神的慌乱暴露了我们的意图，然后你们又让我们去另外一家商店。额的神啊！
请不要带我们去购物。你们穿什么我们都爱你们。只要正当的性感就行，但我们不想参与到购买的过程中。
DIY，以及为什么是我们的错？
在宜家之前，男人就能够DIY，现在我们也自认为可以。只是由于可拆装的瑞士货的到来，那些用一把艾伦六角把手无法解决的技术就失传了。但是问到关于奥克斯博湖，毕达哥拉斯定理或者Patsy
Kensit主演的电影中她的野兽使用的致命武器，我们可以立马告诉你。问到我们如何把插头装进非建筑墙内，我们也可以告诉你，只是我们的回答会不对。
在这里重要的是我们的热情。每年，在银行周末假期前，事故预防皇家协会都会公布一些令人震惊的统计数字，说明有多少男人在DIY时，经历了血淋淋的事故。今年，这些事故的第一号杀手工具是：刀子和解剖刀（导致了20000例急诊），锯子（15000例）最后是令人牙齿打颤的碾磨机（6500例）。"过度自信和知识的缺乏，"事故预防皇家协会的报道说，："是DIY事故的主要原因。"可是这不就是让你们对我们一见钟情的可爱特点之一吗？难道你们就不能不看功劳看苦劳吗？
看暴力电影
目前为止，你应该对婚姻关系中男人每天要做的事情所经历的那些害怕、紧张和痛苦有一点认识了吧？所以我们需要时间来放松。你们可以一遍遍念咒语似的说"能给我搓搓背吗？"来放松，我们就是看暴力电影。你们若是不想看，我们没意见。我们甚至不介意在浴室的小电视上看，以便让你看那该死的《飞黄腾达》（美国一档热门商业真人秀节目）。只是不要让我们看你们那些情节悲惨的古装剧，因为我们可能会哭，而男人是从不掉泪的。那样我们必须得面对自己的脆弱情感，那我们男人的面子往哪儿放？还是让我们赶紧往下说吧。
做爱以及其频率
最好是细水长流、毛毛雨常有，受不了要么旱死要么涝死。就像记忆一样，这个也是有科学根据的，而且是我们控制范围之外的。
看其他女人
还是科学的缘故，同样是我们不由自主的。根据《那不是因为你，而是生物原因》的作者Joe
Quirk的看法，男人和女人拥有相互排斥的繁殖系统。女人生成一个卵子需要29.5天，如果这个卵子受孕了，她们又得十月怀胎，然后是数月或数年的母乳喂养。然而，男人几秒钟内就可以产生300万只精子，如果观察野牛、鸟、猿类和你自己的狗，一般情况下，你会发现雄性大多淫荡而雌性比较挑剔。当代的男人，Silvio
Berlusconi（新当选的意大利总统，传出众多绯闻）除外，已经完成了从猿到人的转变，除了两个方面：不盖马桶盖，看其他女人。可是我们也为之付出了沉重的代价：一次次的去购物，和那些被扔在被子外面的漫漫寒夜。
总之，你们赢了，现在我们结案。
Linux内核编译完整过程
通过网上的资料我自己的实际内核编译，我把对Linux内核编译的过程写在这里，也许对其他的Linux爱好者的编译学习有些帮助，其中很大部分是网上的资料，另外就是我在实际编译过程中的一些实际经验。
内核简介
内核，是一个操作系统的核心。它负责管理系统的进程、内存、设备驱动程序、文件和网络系统，决定着系统的性能和稳定性。
Linux的一个重要的特点就是其源代码的公开性，所有的内核源程序都可以在/usr/src/linux下找到，大部分应用软件也都是遵循GPL而设计的，你都可以获取相应的源程序代码。全世界任何一个软件工程师都可以将自己认为优秀的代码加入到其中，由此引发的一个明显的好处就是Linux修补漏洞的快速以及对最新软件技术的利用。而Linux的内核则是这些特点的最直接的代表。
想象一下，拥有了内核的源程序对你来说意味着什么？首先，我们可以了解系统是如何工作的。通过通读源代码，我们就可以了解系统的工作原理，这在Windows下简直是天方夜谭。其次，我们可以针对自己的情况，量体裁衣，定制适合自己的系统，这样就需要重新编译内核。在Windows下是什么情况呢？相信很多人都被越来越庞大的Windows整得莫名其妙过。再次，我们可以对内核进行修改，以符合自己的需要。这意味着什么？没错，相当于自己开发了一个操作系统，但是大部分的工作已经做好了，你所要做的就是要增加并实现自己需要的功能。在Windows下，除非你是微软的核心技术人员，否则就不用痴心妄想了。
内核编译模式
要增加对某部分功能的支持，比如网络之类，可以把相应部分编译到内核中（build-in），也可以把该部分编译成模块（module），动态调用。如果编译到内核中，在内核启动时就可以自动支持相应部分的功能，这样的优点是方便、速度快，机器一启动，你就可以使用这部分功能了；缺点是会使内核变得庞大起来，不管你是否需要这部分功能，它都会存在，这就是Windows惯用的招数，建议经常使用的部分直接编译到内核中，比如网卡。如果编译成模块，就会生成对应的.o文件，在使用的时候可以动态加载，优点是不会使内核过分庞大，缺点是你得自己来调用这些模块。
实际的内核编译阶段：
一、Linux内核源代码包的获取：http://www.kernel.org，编译内核需要root权限，以下操作都假定你是root用户。请把你需要升级的内核拷贝到/usr/src/下（下文中以2.4.18的内核的linux-2.4.18.tar.gz为例），命令为
#cp linux-2.4.18.tar.gz /usr/src
二、解压源代码包和建立相应的链接：
在当前的/usr/src内容里，注意到有一个linux-
2.4的符号链接，指向一个linux-2.4.7-10（以REDHAT7.2为例）的目录。这就是你所装linux的kernel源代码，删除这个链接。
现在解压我们下载的源程序文件。如果所下载的是.tar.gz（.tgz）文件，请使用下面的命令：#tar
-zxvf linux-2.4.18.tar.gz.tar.gz
如果你所下载的是.bz2文件，例如linux-2.4.18.tar.bz2，请使用下面的命令
#bzip2 -d linux-2.4.18.tar.bz2
#tar -xvf linux.2.4.18.tar
文件将解压到/usr/src/linux目录中,我们把它稍作修改：
#mv linux linux-2.4.18
#ln -s linux-2.4.18 linux（重新建立指向刚刚解压的linux-2.4.18的链接）
三、检查源代码目录下有没有不正确的.o文件以及文件的互相依赖，运行以下命令：
＃cd /usr/src/linux
＃make mrproper
四、创建指向你所编译内核的asm linux scsi链接
为确保/usr/include/目录下的asm、linux和scsi等链接是指向要升级的内核源代码的。它们分别链向源代码目录下的真正的、该计算机体系结构（对于PC机来说，使用的体系结构是i386）所需要的真正的include子目录。如：asm指向/usr/src/linux/include/asm-i386
等。若没有这些链接，就需要手工创建，按照下面的步骤进行：
# cd /usr/include/
# rm -r asm linux scsi
# ln -s /usr/src/linux/include/asm-i386 asm
# ln -s /usr/src/linux/include/linux linux
# ln -s /usr/src/linux/include/scsi scsi
这是配置非常重要的一部分。删除掉/usr/include下的asm、linux和scsi链接后，再创建新的链接指向新内核源代码目录下的同名的目录。这些头文件目录包含着保证内核在系统上正确编译所需要的重要的头文件。
五、内核配置
接下来的内核配置过程比较烦琐，但是配置的适当与否与日后linux的运行直接相关，有必要了解一下一些主要的且经常用到的选项的设置。
配置内核可以根据需要与爱好使用下面命令中的一个：
#make config（基于文本的最为传统的配置界面，不推荐使用）
#make menuconfig（基于文本选单的配置界面，字符终端下推荐使用）
#make xconfig（基于图形窗口模式的配置界面，Xwindow下推荐使用）
#make
oldconfig（如果只想在原来内核配置的基础上修改一些小地方，会省去不少麻烦）
这三个命令中，make
xconfig的界面最为友好，如果你可以使用Xwindow，那么就推荐你使用这个命令，界面如下：
如果你不能使用Xwindow，那么就使用make
menuconfig好了。界面虽然比上面一个差点，总比make
config的要好多了，下图为make menuconfig的界面：
选择相应的配置时，有三种选择，它们分别代表的含义如下：
Y－-将该功能编译进内核
N－-不将该功能编译进内核
M－-将该功能编译成可以在需要时动态插入到内核中的模块
如果使用的是make xconfig，使用鼠标就可以选择对应的选项。如果使用的是
make
menuconfig，则需要使用空格键进行选取。你会发现在每一个选项前都有个括号,
但有的是中括号有的是尖括号，还有一种圆括号。用空格键选择时可以发现，中括号里要么是空，要么是"*"，而尖括号里可以是空，"*"和"M"。这表示前者对应的项要么不要，要么编译到内核里；后者则多一样选择，可以编译成模块。而圆括号的内容是要你在所提供的几个选项中选择一项。
至于内核配置的选项在我的以下文章里有简单的介绍:
Linux内核编译配置选项的简单介绍(一) 和
Linux内核编译配置选项的简单介绍(二)
六、编译，使用以下命令：
#make dep
#make clean
#make bzImage或make zImage
#make modules
#make modules_install
#depmod -a
第一个命令make
dep实际上读取配置过程生成的配置文件，来创建对应于配置的依赖关系树，从而决定哪些需要编译而那些不需要；第二命令make
clean完成删除前面步骤留下的文件，以避免出现一些错误；make zImage和make
bzImage则实现完全编译内核，二者生成的内核都是使用g***压缩的，只要使用一个就够了，它们的区别在于使用make
bzImage可以生成大一点的内核。建议大家使用make bzImage命令。
后面三个命令只有在你进行配置的过程中，在回答Enable loadable module
support (CONFIG_MODULES)时选了"Yes"才是必要的，make modules和make
modules_install分别生成相应的模块和把模块拷贝到需要的目录中。
严格说来，depmod
-a命令和编译过程并没有关系，它是生成模块间的依赖关系，这样你启动新内核之后，使用modprobe命令加载模块时就能正确地定位模块。
七、更新部分内容
经过以上的步骤，我们终于得到了新版本的内核。为了能够使用新版本的内核，我们还需要做一些改动：
#cp /usr/src/linux/System.map /boot/System.map-2.4.18
#cp /usr/src/linux/arch/i386/bzImage /boot/vmlinuz-2.4.18
以上这两个文件是我们刚才编译时新生成的。下面修改/boot下的两个链接System.map和vmlinuz，使其指向新内核的文件：
#cd /boot;rm -f System.map vmlinuz
#ln -s vmlinuz-2.4.18 vmlinuz
#ln -s System.map-2.4.18 System.map
八、修改启动管理器
如果用LILO，修改/etc/lilo.conf，添加以下项：
image=/boot/vmlinuz-2.4.18
label=linux240
read-only
root=/dev/hda2
其中root=/dev/hda2一行要根据需要自行加以修改。
运行：
#/sbin/lilo -v
确认对/etc/lilo.conf的编辑无误，现在重新启动系统：
#shutdown -r now
如果是用Grub启动管理器，则添加如下几项即可。
title Red Hat linux (2.4.18)
root (hd0,0)
kernel /vmlinuz-2.4.18 ro root=/dev/hda2
Grub不需再次调用命令，自动生效。
重启以后就可以用新内核了。
内核简介
内核，是一个操作系统的核心。它负责管理系统的进程、内存、设备驱动程序、文件和网络系统，决定着系统的性能和稳定性。
Linux的一个重要的特点就是其源代码的公开性，所有的内核源程序都可以在/usr/src/linux下找到，大部分应用软件也都是遵循GPL而设计的，你都可以获取相应的源程序代码。全世界任何一个软件工程师都可以将自己认为优秀的代码加入到其中，由此引发的一个明显的好处就是Linux修补漏洞的快速以及对最新软件技术的利用。而Linux的内核则是这些特点的最直接的代表。
想象一下，拥有了内核的源程序对你来说意味着什么？首先，我们可以了解系统是如何工作的。通过通读源代码，我们就可以了解系统的工作原理，这在Windows下简直是天方夜谭。其次，我们可以针对自己的情况，量体裁衣，定制适合自己的系统，这样就需要重新编译内核。在Windows下是什么情况呢？相信很多人都被越来越庞大的Windows整得莫名其妙过。再次，我们可以对内核进行修改，以符合自己的需要。这意味着什么？没错，相当于自己开发了一个操作系统，但是大部分的工作已经做好了，你所要做的就是要增加并实现自己需要的功能。在Windows下，除非你是微软的核心技术人员，否则就不用痴心妄想了。
内核编译模式
要增加对某部分功能的支持，比如网络之类，可以把相应部分编译到内核中（build-in），也可以把该部分编译成模块（module），动态调用。如果编译到内核中，在内核启动时就可以自动支持相应部分的功能，这样的优点是方便、速度快，机器一启动，你就可以使用这部分功能了；缺点是会使内核变得庞大起来，不管你是否需要这部分功能，它都会存在，这就是Windows惯用的招数，建议经常使用的部分直接编译到内核中，比如网卡。如果编译成模块，就会生成对应的.o文件，在使用的时候可以动态加载，优点是不会使内核过分庞大，缺点是你得自己来调用这些模块。
实际的内核编译阶段：
一、Linux内核源代码包的获取：http://www.kernel.org，编译内核需要root权限，以下操作都假定你是root用户。请把你需要升级的内核拷贝到/usr/src/下（下文中以2.4.18的内核的linux-2.4.18.tar.gz为例），命令为
#cp linux-2.4.18.tar.gz /usr/src
二、解压源代码包和建立相应的链接：
在当前的/usr/src内容里，注意到有一个linux-
2.4的符号链接，指向一个linux-2.4.7-10（以REDHAT7.2为例）的目录。这就是你所装linux的kernel源代码，删除这个链接。
现在解压我们下载的源程序文件。如果所下载的是.tar.gz（.tgz）文件，请使用下面的命令：#tar
-zxvf linux-2.4.18.tar.gz.tar.gz
如果你所下载的是.bz2文件，例如linux-2.4.18.tar.bz2，请使用下面的命令
#bzip2 -d linux-2.4.18.tar.bz2
#tar -xvf linux.2.4.18.tar
文件将解压到/usr/src/linux目录中,我们把它稍作修改：
#mv linux linux-2.4.18
#ln -s linux-2.4.18 linux（重新建立指向刚刚解压的linux-2.4.18的链接）
三、检查源代码目录下有没有不正确的.o文件以及文件的互相依赖，运行以下命令：
＃cd /usr/src/linux
＃make mrproper
四、创建指向你所编译内核的asm linux scsi链接
为确保/usr/include/目录下的asm、linux和scsi等链接是指向要升级的内核源代码的。它们分别链向源代码目录下的真正的、该计算机体系结构（对于PC机来说，使用的体系结构是i386）所需要的真正的include子目录。如：asm指向/usr/src/linux/include/asm-i386
等。若没有这些链接，就需要手工创建，按照下面的步骤进行：
# cd /usr/include/
# rm -r asm linux scsi
# ln -s /usr/src/linux/include/asm-i386 asm
# ln -s /usr/src/linux/include/linux linux
# ln -s /usr/src/linux/include/scsi scsi
这是配置非常重要的一部分。删除掉/usr/include下的asm、linux和scsi链接后，再创建新的链接指向新内核源代码目录下的同名的目录。这些头文件目录包含着保证内核在系统上正确编译所需要的重要的头文件。
五、内核配置
接下来的内核配置过程比较烦琐，但是配置的适当与否与日后linux的运行直接相关，有必要了解一下一些主要的且经常用到的选项的设置。
配置内核可以根据需要与爱好使用下面命令中的一个：
#make config（基于文本的最为传统的配置界面，不推荐使用）
#make menuconfig（基于文本选单的配置界面，字符终端下推荐使用）
#make xconfig（基于图形窗口模式的配置界面，Xwindow下推荐使用）
#make
oldconfig（如果只想在原来内核配置的基础上修改一些小地方，会省去不少麻烦）
这三个命令中，make
xconfig的界面最为友好，如果你可以使用Xwindow，那么就推荐你使用这个命令，界面如下：
如果你不能使用Xwindow，那么就使用make
menuconfig好了。界面虽然比上面一个差点，总比make
config的要好多了，下图为make menuconfig的界面：
选择相应的配置时，有三种选择，它们分别代表的含义如下：
Y－-将该功能编译进内核
N－-不将该功能编译进内核
M－-将该功能编译成可以在需要时动态插入到内核中的模块
如果使用的是make xconfig，使用鼠标就可以选择对应的选项。如果使用的是
make
menuconfig，则需要使用空格键进行选取。你会发现在每一个选项前都有个括号,
但有的是中括号有的是尖括号，还有一种圆括号。用空格键选择时可以发现，中括号里要么是空，要么是"*"，而尖括号里可以是空，"*"和"M"。这表示前者对应的项要么不要，要么编译到内核里；后者则多一样选择，可以编译成模块。而圆括号的内容是要你在所提供的几个选项中选择一项。
至于内核配置的选项在我的以下文章里有简单的介绍:
Linux内核编译配置选项的简单介绍(一) 和
Linux内核编译配置选项的简单介绍(二)
六、编译，使用以下命令：
#make dep
#make clean
#make bzImage或make zImage
#make modules
#make modules_install
#depmod -a
第一个命令make
dep实际上读取配置过程生成的配置文件，来创建对应于配置的依赖关系树，从而决定哪些需要编译而那些不需要；第二命令make
clean完成删除前面步骤留下的文件，以避免出现一些错误；make zImage和make
bzImage则实现完全编译内核，二者生成的内核都是使用g***压缩的，只要使用一个就够了，它们的区别在于使用make
bzImage可以生成大一点的内核。建议大家使用make bzImage命令。
后面三个命令只有在你进行配置的过程中，在回答Enable loadable module
support (CONFIG_MODULES)时选了"Yes"才是必要的，make modules和make
modules_install分别生成相应的模块和把模块拷贝到需要的目录中。
严格说来，depmod
-a命令和编译过程并没有关系，它是生成模块间的依赖关系，这样你启动新内核之后，使用modprobe命令加载模块时就能正确地定位模块。
七、更新部分内容
经过以上的步骤，我们终于得到了新版本的内核。为了能够使用新版本的内核，我们还需要做一些改动：
#cp /usr/src/linux/System.map /boot/System.map-2.4.18
#cp /usr/src/linux/arch/i386/bzImage /boot/vmlinuz-2.4.18
以上这两个文件是我们刚才编译时新生成的。下面修改/boot下的两个链接System.map和vmlinuz，使其指向新内核的文件：
#cd /boot;rm -f System.map vmlinuz
#ln -s vmlinuz-2.4.18 vmlinuz
#ln -s System.map-2.4.18 System.map
八、修改启动管理器
如果用LILO，修改/etc/lilo.conf，添加以下项：
image=/boot/vmlinuz-2.4.18
label=linux240
read-only
root=/dev/hda2
其中root=/dev/hda2一行要根据需要自行加以修改。
运行：
#/sbin/lilo -v
确认对/etc/lilo.conf的编辑无误，现在重新启动系统：
#shutdown -r now
如果是用Grub启动管理器，则添加如下几项即可。
title Red Hat linux (2.4.18)
root (hd0,0)
kernel /vmlinuz-2.4.18 ro root=/dev/hda2
Grub不需再次调用命令，自动生效。
重启以后就可以用新内核了。
订阅：
博文 (Atom)
博文
