1. MapReduce与云计算

MapReduce是google的一个云计算模型。

云计算主要分为三个层次：IaaS、Paas、SaaS，即Infrastructure as a Service、Platform as a Service、Software as a Service，如图1所示。

图1. 云计算的层次

云计算的概念最早是由Google、Amazon、IBM这样的大公司提出，其概念上与2000年代左右的网格计算非常相似。但是网格计算彻底没落了，因为它缺乏广泛的应用基础。而云计算则不同，它是现有现成的系统、既有的应用案例，这些因素导致云计算从一诞生开始就具有蓬勃的生机。毕竟，这个梦想是现实可触摸的。

云计算由于由不同的厂商提供，所以在早期它的概念相当模糊。后来，各个厂商的技术被分层封装，形成了图1的层次。

IaaS层，主要是以Amazon为代表，它提供底层的硬件实体封装，主要手段是虚拟机。

PaaS层，主要是以Google为代表，提供大规模集群下的操作系统提供的服务，如文件系统、数据库等。

SaaS层，主要是在PaaS层上的应用，如Gmail、facebook等。

其中PaaS层比较关键，因为上层应用需要在此基础上建立。从计算机的发展来看，操作系统的作用巨大，它抽象了底层硬件，向应用程序提供进程、文件、内存等概念。在云计算的环境下，PaaS也要发挥类似的功用。

PaaS层主要提供几个抽象：计算、存储、搜索。计算，对应于进程，是云计算向用户提供的计算资源。存储，是数据的载体，分为结构化与非结构化，如文件系统、分布式数据库等。搜索，由于数据量太大，所以数据的挖掘与发现成了一个基本的问题。

Google对PaaS的解决方案比较完整，包括MapReduce、GFS、BigTable、MegaStore、Spanner等，再加上它看家的搜索。当然，它的技术也是不断在完善与发展的。其中MapReduce就对应于计算的PaaS。

2. 问题的提出

主要的应用场景是大规模分布式计算：数据量巨大、分布在一个IDC机房中、没有严格的实时性要求、机器都是普通的PC机。

想象一下google的主要业务：搜索。它需要从全网络爬取网页，存储在本地，然后做倒排索引。从google主页上发送的搜索请求，会在已经整理好的倒排索引上直接返回。这一业务流程中，最繁重的就是倒排索引的建立。它工作量巨大，同时没有实时需求。

在这样的物理的场景中、这样的业务需求下，如何编写一个倒排索引的业务？当然工作很多，作者的主要思考是：跳出具体的业务，总结出一套基本的计算模型。这套模型能够减轻新手的负担，主要集中在业务上，让模型框架去处理自动分布、容错恢复、负载均衡等问题。

fault tolerant？因为google为了降低成本，采用了普通商业PC服务器来建立IDC机房，只能假设PC机会出问题：硬件的、网络的、软件的。

3. 计算模型

MapReduce的计算模型比较简单，它抽象出Map和Reduce两种操作。前者是将输入数据1：1地处理在本地；Reduce则将输入数据从n个分布式输入n：1处理成一个文件。如图2所示。

MapReduce既是一个计算模型、同时也是一套runtime库、还是一个集群的配置。在图2中，需要有master和多个slave节点——这是一个典型的集群配置。master和slave节点上需要运行mapreduce的进程。

1） 集群的配置

需要指定集群的范围，即那些机器需要作为slave？原文中没有讨论这个话题。不过从前后文看来，似乎是任意指定的，或者与数据的位置无关，因为文章的测试数据展现的数据传输率，这应该是一个比较大的bug。

当前的观点认为，云环境下的存储节点应该构成一个存储对象，即节点既能存储数据，同时也要附加计算的功能。既然文章中指出网络带宽是比存储容量更宝贵的资源，计算就应该放到存储节点上。

文章指出master需要考虑数据的locality，将计算放在存储节点上。由于数据的异构的，master必须理解这种异构性。——这可是一个大麻烦。原文并没有讨论master如何处理这种异构性。这种异构性需求最终有可能会导致应用程序员去了解底层的数据分布情况，从而破坏论文声称的自动并行化的功能。

最终，MapReduce的计算模型就绑定在google的数据组织上。

图2. MapReduce计算模型

2） master的指定

从图2的结构图中，可以发现集群的master地位特殊，它控制这个Job的推进。一旦master挂掉。文章中交代，这主要靠checkpoint来重建master的Job状态。

master的单点故障一直被旁观者诟病，这可能是一种误解。因为，MapReduce的任务很关键吗？非实时的后台倒排索引能有多关键？所以，至少文章[1]中的MapReduce并非应用在关键的实时任务场景下的。

所以，这个master基本上可以随意指定，当它game over，重启一下；或者干脆重做整个Job。

MapReduce需要解决的问题，重点不在master的可靠性上，而在于这个框架的自动分布、slave节点的自动fail over。

3） master数据结构

master的主要数据结构是Job，它描述整个作业，并控制各个Map和Reduce的task。每task的状态为：idle、in-process、completed。master根据task状态机，跟踪task的完成情况。

master维护与slave之间的心跳，如果心跳超时，则判定这个slave挂掉，然后重新指定一个slave去重启这个task。

这里还有一个暗示：MapReduce是在GFS场景下工作。Map产生的结果放在本地，而不是放在GFS上。即，Map的中间文件不会出现在全局GFS的名字空间。

如果一个Map的slave已经完成了工作，然后在Reduce读取的过程中突然又挂掉，它的task必须重做。因为这个Map产生的中间结果是在这台slave的机器上。

而图2中的Reduce则是将结果放在GFS上，所以执行Reduce的slave一旦完成工作，它挂不挂都无所谓了。

但是，在多级的Map/Reduce过程中，Reduce有可能产生的是一个中间结果，也应该放在本地。这样做使得master状态机的设计简单得多。毕竟还是那句话，MapReduce不是为关键实时应用设计的。

4） 最终结果的重名

Job一般会指定最终结果的文件名，这个最终文件通常放在GFS上。但是，有可能在图2中，一个Reduce任务会被执行多次，因为master有可能会因为超时去重启一个Reduce任务。Map任务也会存在同样的问题。

而按照原文的说法，Map或者Reduce如果产生最终结果，这个最终结果必须放在GFS上。Map或者Reduce首先在slave本地生成数据，然后提交给GFS。这里需要由GFS的rename操作保证文件名的原子性。——这一点很重要，这是一个原子性的保证。

5） 异构机器上执行MapReduce

集群场景下，Map或Reduce机器要按照异构做假设条件。在整个MapReduce作业完成的进度中，有可能某个task老是完不成。master可以启动另一个slave在重做这个task。

这称为straggler优化。这种优化，需要修改master的Job数据结构，感知各个task的任务进度。

6） combiner函数

每个Map或Reduce任务执行完毕后，从节省带宽的角度考虑，可能需要压缩中间结果。此时combiner作为一个过滤程序，执行压缩算法。

7） 主动的failure捕捉

除了心跳外，MapReduce库还在Map或Reduce进程上安装段异常处理函数。当发生段异常错误，会向master主动发送错误信息。

8） counter计数器

MapReduce库提供全局计数器，用在如7）的错误捕捉中。也可以在心跳中piggyback这些counter。

图3. counter应用示意图

4. 程序的装载

文章附带了一段代码，值得分析。

1） REGISTER_MAPPER宏，注册mapper，注册到哪里去？

说明google可能有一个组件计算环境。也可能是master本地有一个注册环境，下载到slave上。

2） Job任务的描述为MapReduceSpecification。

从程序上来看，这个描述有很多需要改进的地方。首先，它固定了先是Map然后是Reduce，如果多级嵌套怎么办？其次，这个Job spec最好是用xml格式表述，这样非常友好。

3） MapReduce函数执行的进程，即为master

5. 讨论

MapReduce有它产生的背景和适用场景，至少按照原文[1]的思路是这样的。Andrew Pavlo[2]对比了Hadoop和并行数据库的性能，认为MapReduce是一种退步。接着，Dean[3]做出了回应。针对MapReduce的如下三条指责予以反驳：

1） MR没法用索引，总是对数据进行完全扫描；

2） MR 输入和输出，总是文件系统中的简单文件；

3） MR需要使用不高效的文本数据格式。

应该说，MapReduce从模式上说，并不限于文本、简单文件。虽然，从论文[1]的代码上来看MapInput很可疑。但是，将流文件转换为格式文件并不困难。

全扫描的说法也有问题，从MapReduce的语义上看，与这一点是无关的。

但是，这个性能对比实际上说明了MapReduce并非是为实时的数据处理而准备的，这才是MapReduce的痛点。

从MapReduce的整个过程上来看，中间结果写盘，是一个比较可疑的动作。但是这种设计会简化master的容错处理。另外，MapReduce本身并未对数据库的连接、投影、选择等操作做细化，这并不是MapReduce所关心的。

参考文献

[1] J. Dean and S. Ghemawat, "MapReduce: simplified data processing on large clusters," Communications of the ACM, vol. 51, pp. 107-113, 2008.

[2] A. Pavlo, E. Paulson, A. Rasin, D. J. Abadi, D. J. DeWitt, S. Madden, et al., "A comparison of approaches to large-scale data analysis," in Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, 2009, pp. 165-178.

[3] J. Dean and S. Ghemawat, "MapReduce: a flexible data processing tool," Communications of the ACM, vol. 53, pp. 72-77, 2010.

MapReduce