20世纪90年代中期，随着Web用户数量的爆炸式增长，Web搜索成为第一批广受欢迎的大型Internet服务之一，而组织这些海量数据则超出了当时手工管理目录服务的极限。随着家用和商用网络连接的普及，在Internet上提供新的服务变得越来越具有吸引力，有时甚至能够代替传统客户端的计算能力。基子Web的地图和电子邮件服务是这些趋势的几个早期范例。各种新服务的不断出现使应用级要求大大提高。例如，一个搜索负载并不需要具有高效率原子更新能力的架构，所以它自然就会对硬件故障具有更好的容错性。但对于一个用来跟踪"用户在赞助商广告上的单击"的应用来说却正好相反，在广告上的单击相当于小型的财务交易，所以需要很多来自交易信息管理系统的保障。

　　考虑到各种服务多样化的需求，数据中心应该是一种通用的计算系统。虽然专业化的硬件解决方案可能会非常适合服务中的个别部分，但需求的多样性使得专业化硬件对全局运行无法产生较大的影响。另一个对专业化硬件不利的因素，是工作负载的变动速度。产品的需求快速进化，高明的程序员会不断地从经验中学习并重写基本的算法和数据结构，而这些都远远超出了硬件本身的进化速度。因此，即使为某个专业领域设计了专业化的硬件，很有可能等到这些解决方案实现时它们就已经不再适用了。

　　这一节对两种有典型代表意义的工作负载做一些概述性的描述，即在线服务系统和批处理 (离线)系统。这里用一个网页搜索应用的基本构架来作为在线服务系统的例子，再用一个基干引用的相似度计算系统 (使用MapReduce技术)来作为批处理负载的例子。

　　1·Web搜索

　　Web搜索是个典型的大海捞针问题。虽然无论什么时候想要准确确定互联网的大小都是极其困难的，但是不管怎么说它都包含了数以千亿计的文档，并且还在不断地增长。假设Web包含了1000亿个文档，每个文档的平均大小是4KB(压缩后)，邢么这个"海"就有40OTB。Web搜索使用的数据库是一个由这个存储库生成的索引，生成的方法是把这些文档倒过来按照图2.9所示的逻辑形式做成一个新的存储库。一个词典结构给每一个词务都分配一个ID。这个词条lD标志出相应词条出现过的文档的列表，以及一些相关的上下文信思，包括位置和其他的一些属性 (如这个词条是否在文档的题目里)。

　　这样生成的倒排索引的大小视具体的实现情况而定，但是通常都会与原来的存储库的数量级相同。通常的搜索查询包括一系列的词条，而系统的任务就是找到含有所有这些词条的文档 (一个AND查询)，再确定哪些文档最有可能符合用户的需求。查询操作也可以包括可选的特殊操作符来表示或(OR操作)，或者限制搜索的出现只在特定位置的词条(短语操作)。为了简便，在此只关注更常见的AND查询。

　　搜索算法需要对每个词条遍历张贴列表，直到找到所有包括在所有两个张贴列表里的文档。然后再对找到的文档使用各种参数进行排序，列入文档的总体重要程度(对于Google来说就是PageRank[209]分数)，以及很多其他与词条在文档中的出现相关的属性 (如出现次数、位置等)，然后向用户返回排名最高的文档。

　　考虑到索引的巨大尺寸，这次搜索可能要涉及数以千计的机器。要做到这一点，需要把索引切分成经过负载均衡的子文件，并分发到所有的机器上，可依照文档或词条来切分。

　　用户请求被一个前端Web服务器接受，并将其分发到索引集群中的所有机器上。为保证必要的带宽或者容灾，索引子文件的多个复件可以被放在不同的机器上，这样在某个特定的查询中就只需要调用一小部分的机器。索引服务获取相关数据，对其进行预排序，再将最好的结果送往前端系统 (或者中间服务器)，这些系统再从整个集群的结果中选出最好的。这时只有对应于结果Web页面中的doc_IDs是已知的，需要经过第二阶段的计算才能得出实际的题目、URL，以及一段跟查询相关的文章内容预览，以便为用户提供一些搜索务目周围的上下文信息。这一岁的实现方法是将doc_ID发送到保存了实际文档的一系列机器上。

　　同样，存储库也需要被切分并放在大量的服务器上。

　　在上述操作中，用户所感知的延迟需要控制在毫秒级别:因此这种体系结构非常重视消除延迟。然而，高带宽仍然是度量性能的一个重要指标，因为一个受欢迎的服务可能需要支持每秒数以千计的请求。索引会经常更新，但是对于处理单个查询的时间粒度来说，索引可以被视为一个只读结构。而且因为索引查询阶段不需要机器之间的通信 (除了最后的合并阶段)，计算过程实际上是高效并行化的。最后，利用不同的查询之间没有逻辑联系这一点，可以进一步进行并行优化。

　　如果索引是按照doc_ID划分的，那么这个工作负载对网络的带宽要求就比较低，因为在机器之间交换的信息量一般不会超过请求信息本身太多(100字节左右)，但是却具备一定的暴发性特点。基本上前端的服务器是作为流量增幅器，它们把单个的请求分发到大量的服务器上。这不但会在请求路径上，也可能会在相应路径上产生一组暴发性的流量。即使总体网络占用率比较低，也需要小心地管理网络流量以便把丢包率降到最低。

　　最后，因为Web搜索是一项在线服务，它也会被一般的流量变化所影响，因为用户在网络上的活跃度在一天当中的不同时段是不同的。如图2·10所示，图中高峰时间段的流最是一般时间段流量的两倍还多。

　　2·学术文章相似度

　　用户请求提供了许多关于Internet服务需要大规模计算的例子。这些计算一般都是数据并行的工作负载，用来预备或包装数据以便用于在线服务，如计算PageRank，或者Web内容库中建立反向索引都属于这一类计算。这里采用一个不同的例子——从一个学术论文和期刊的内容库里找出相似的文章，来进行说明。

　　这对提供科学类出版物的在线服务系统是一项非常有用的功能，如 Google学术(htttp://Scholar.google.com)。文章相似性关系能够辅助基于关键词的搜索，并可作为查找相关信息的另一种方式:当找到一篇需要的文章后，用户可以要求服务显示与原始文章相关的其他文章。

　　计算相似度有多种方法，一般都使用多种方法相结合的方法。在学术文章中，多种形式的引用分析已经能够提供有效的相似度。这里考虑其中一种分析方法 —— 协同引用。基本思路是计算同时引用文章A和文章B的文章的篇数，来作为A和B的相似度的衡量标准。当这个操作对所有的文章都遍历完成并且合理平均化之后，每篇文章会得到一个相似度得分，然后创建一个相似文章的列表。这个列表会周期性更新，而且每次更新都成为在线服务状态的一部分。

　　计算过程自一个引用表开始，这张表在每一个文章标志符和一系列被这篇文章引用的文章之间创建一个映射。输入数据被分割成数以百计的大小相近的文件 (这可以通过对文章标志符取一个指纹，再用输入文件的数量去除它，使用得出的余数作为文件的ID这样的方法来实现)以利于有效地并行执行。

　　下面使用一套MapReduce过程来制作所有文章的引用表并且生成协同引用相似度向量。

　　在第一个Map环节，我们从每一个引用列表(A1，A2，，A3，...，An")生成引用列表中所有的文档对，将它们输送进Reduce环节，去对每个对的出现次数进行统计。结果是产生一个将所有协同引用的文档与协同引用计数关联起来的结构。注意，这个过程远没有达到二次函数的数量级，因为多数文档的协同引用数都是0，所以会被忽略。

　　接下来使用第二遍MapReduce过程将所有的词条按照文档分组，平均化它们的分数，并且生成一个按照与原文档相似度降序排列的文档列表。

　　这种两遍数据并行程序在数以百计的服务器上运行，每个阶段的计算任务都较为轻量，　但之后则会在Map和Reduce服务器之间有大量的全对全通信。然而与Web搜索不同的是，这里的网络流量是流式的，使已有的拥塞控制算法处理起来就要容易一些。它与Web搜索相反的另一个特性是，单个任务的延迟对总负载的并行效率并没有多大影响。

　　责任编辑：GOCN