2.5 应用层软件
Web搜索曾是最早的受欢迎的大规模互联网服务之一，从20世纪90年代中期开始的互联网内容的井喷，使处理如此大量的信息超出了当时人工管理目录的能力。然而，随着针对家庭和公司的网络连接业务的持续增长，通过互联网提供新的服务变得越来越有吸引力，有时甚至取代了传统客户端的功能。基于网页的地图和邮件服务就是这一发展趋势的端倪。服务范围的扩大也造成了应用需求极大的多样性。例如，一个搜索任务可能不需要一个具备细粒度更新能力的基础架构，也就自然可以容忍硬件故障（因为Web搜索不需要每次都绝对的精准）。而对于追踪用户点击特定链接（广告）的应用就是另外一回事了，每次点击广告都是一个小型的财务交易，需要一个交易数据库管理系统来保证。
一旦考虑多种服务的各种需求，数据中心也就必须成为通用计算系统。虽然专门的硬件解决方案对个别的服务来说非常适合，但随着需求范围的拓宽，采用特别的硬件在操作层面越来越不现实。另外，工作负载的快速演变也使得专用硬件不可行。产品需求演变很快，聪明的程序员会汲取经验，及时改写底层算法和数据结构，而硬件无法做到如此快速的进化。因此，潜在风险在于当某个特别的硬件解决方案实施的时候，很可能就已经不适合原来要解决的问题了。
2.5.1 工作负载示例
这里不会介绍互联网服务工作负载的过多细节，主要是因为这一市场的动态特性使得这些细节在本书出版的时候已经过时。不过在较高的层面描述两大类应用——在线服务和批（离线）处理系统——两种工作负载还是有用的。接下来我们概述一下Web搜索应用的基本结构，以此作为一个在线服务的例子。再用一个使用MapReduce的基于引文相似度计算的例子来说明批处理工作负载。
2.5.2 在线应用：Web搜索
这是典型的“干草垛捞针”问题。虽然很难确定任意时间点网页的大小，但是毫无疑问网页包含数千亿的独立文档并且数目仍在不断增长。假设网页包含一千亿个文档，每个文档压缩后平均大小4KB，那么“干草垛”的规模则有约400TB之大。Web搜索数据库就是一个建立在这个巨大存储库上的索引，通过倒排一系列文档创建出如图2.1所示的逻辑格式的存储库。
词典结构把存储库里的每个条目都关联上一个ID。这个条目的ID标示出该条目出现过的文档列表，以及一些前后关系信息，比如位置和各种其他属性等（例如该条目是否在标题档）。
转化后的索引大小取决于具体的实施情况，但仍然具备原有存储库的数量级。典型的搜索查询条件包含一组关键词序列，系统的任务是找出包含该关键词的所有文档，并决定哪些文档可能是用户最满意的结果。搜索条件可以使用特殊的运算符（比如OR运算符），或者限制在关键词出现的特定序列（如短语符号）中搜索。为简单起见，这里我们着重讨论比较普遍的AND查询。
举例来说，比如要搜索“纽约的饭馆”。搜索算法必须过滤所有分别包含“纽约”和“饭馆”关键词的发布列表，直到找出同时包含这两个关键词的所有文档。然后再将找到的文档用不同的参数排序，比如文档整体重要性（例如Google采用PageRank 【116】），或者用与文档中关键词关联的其他属性排序（比如出现的频率和位置等），最后将排名最靠前的结果呈现给用户。
介于索引的庞大规模，搜索算法的运行可能需要跨越几千台机器。搜索算法运行时，索引被分割成许多负载平衡的子文件，再分布到所有机器上。索引的分区可以通过文档或关键词完成。网页前端服务器收到用户搜索请求后，将搜索任务分配给索引群里的所有机器。考虑到搜索处理能力和容错的必要性，索引子文件的多个副本可以放置在不同的机器中，也就是说只有部分机器参与了搜索任务。索引服务的机器计算出本地结果，将预先排序得出的最优结果发送给前端系统（或中转服务器），前端系统再从所有集群中选出最好的结果。这时只有相应搜索结果的网页文档ID列表可知。第二阶段需要计算出实际的标题、链接以及能为用户提供搜索关键词语境的特定文档片段。这一阶段通过把文档ID列表发送给包含文档副本的一组机器实现。如前所述，由于存储库内容很大，需要分区放置在大量服务器上来完成。
上述运算的总用户感知延迟要求在几分之一秒内，因此这种架构的重点在于减少延迟。不过，高吞吐量也是一项很重要的性能指标，因为有些受欢迎的服务需要支持每秒几千条的查询。索引是不断频繁更新的，但在处理单一查询的时间粒度里，索引可以看做只读结构。另外，因为索引只有在最后合并步骤时才需要进行跨机器间查询的互相通信，因此整个计算是非常有效率地并行运行。最终，由于不同的Web搜索任务间并无相互逻辑关联，则更高层次的并行计算得以实现。
如果索引由文档ID进行分区，工作负载就平均带宽而言有着相对较小的网络需求，因为在机器间互相交换的数据量一般并不比搜索查询本身更大（一般在几百字节左右），不过也确实存在某些突发行为。一般来说，前端服务器把单个查询请求分配到大量服务器上时就像一个流量放大器，这不仅在请求路径上生成了一系列突发流量，在响应路径上可能也是如此。因此，即使整体网络利用率很低，也不能对网络流量管理掉以轻心，这对于减少丢包至关重要。
最后，Web搜索作为在线服务将会受到正常的流量变化的影响，因为用户每天不同时段在网页上的活跃程度是不一样的。图2.2说明了这一点，高峰时段的流量是非高峰时段的两倍以上。这种流量变化给系统运营者带来了很大的挑战，因为服务必须要能适应明显高于一般行为的流量强度。
2.5.3 离线应用：学术文章相似度
要求互联网服务提供大型计算的用户请求例子有很多。这些计算通常是典型的数据并行处理任务，需要将数据准备好，或者打包提供给随后的在线服务使用。例如，计算PageRank或从Web库里创建倒排索引文件就属于这一类。再举一个不同的例子：在学术论文期刊的库里搜索相似的文章。这是互联网服务一个非常有用的功能，获取科学出版物，例如 “Google Scholar。文献相似度关系对基于关键字的搜索系统进行了补充，成为另一种发现关联信息的方法。找到一篇有兴趣的文章后，用户可以要求将所有与该文非常相关的文章都列出来。
计算相似度指标的方法有好几种，用多种方法并将结果合并通常比较准确。对于学术文献，众所周知综合使用不同的引文分析能计算出高质量的相似度指标。现在我们来看其中一种叫做“共引”的分析方法，其基本思路就是计算出同时引用文献A和文献B的文献数量，以此做为文献A与B之间的相似度指标。在完成所有计算并适当标准化后，我们可以得到一个文献间相似度（共引）的数值，并创建出一个数据结构用来给每个文献返回一个根据共引值排序的相似文献列表。这种数据结构周期性进行更新，每次更新后就成为在线服务的一部分。
计算开始时首先创建一个引用图，反映出一个文献与一组被引用文献的映射关系。输入数据被分成数百个相似大小的文件（例如，可以通过提取文献识别指纹，与输入的文件数量相除，再把余数作为文件ID），从而实现高效的并行执行。我们运行一个MapReduce任务来获得引用图，并产生所有文献的共引相似性指标向量。在第一个Map阶段，利用每个引文列表（A1、A2、A3. . .An）生成对文件，再输送到Reduce阶段计算所有对文件出现的次数。第一步生成的结果是与所有共引对文件相关联的共引计数的数据结构。注意这会比平方级的计算量少很多，因为多数文档都是零共引计数，因而被忽略不计。第二个MapReduce过程将给定的文档输入进行分组，将分数规范化，并以相似度分数递减的顺序生成一个文档列表。
这种分两步走的数据并行程序，以每个步骤相对轻量的计算任务运行在数百台服务器上，然后每个阶段的Map与Reduce之间出现大量的全局通信。然而与Web搜索不同，该网络流量流动自然，对于现有的拥塞控制算法更加友好。而且与Web搜索相反，这种并行程序对并行计算延迟的敏感程度也不如搜索任务。