《Google 三大论文》_MapReduce

MapReduce是Google三大论文中与应用方面最接近的一层，应该说，也是我们在学习和应用分布式系统基础架构（如hadoop）时唯一关心的。

简单点说，MapReduce是一种编程模型，在处理和生成TB级数据时非常有用：通过简单的接口来实现自动的并行化合大规模的分布式运算，并且不用考虑容错、负载均衡等等繁琐而麻烦的细节。

MapReduce借用了函数式编程的概念，它的实现的思路是：将庞大但是相似（这在分布式处理中很常见）的小的Task，通过Map函数分给不同的主机运算，最后，通过Reduce函数收集并合并计算结果，得到所需。

其基本模型是：利用一个输入Key/Value pair集合来产生一个输出的Key/Value pair集合。如下所示：

(input) <k1, v1> -> map -> <k2, v2> -> combine -> <k2, v2> -> reduce -> <k3, v3> (output)

举一个简单的例子。在Google，好吧，为了体现我的爱国，说百度。百度的日常工作中每天会处理大量的原始数据，比如：文档抓取、网站排序、Web请求统计和日志管理。这些操作本身很简单，甚至许多像我一样的菜鸟都能实现。然而，《算法的分析和设计》这门课程告诉我们，当n本身趋于大数时，即使是O（n）的复杂度也不是一台普通的主机所能完成的。

假设我们要统计Web请求。

现在，将这项工作交给一个实现了GFS（分布式文件系统）的主机集群。百度在各地的服务器执行Map函数，处理其周边范围的“小任务”，输入为每次Web站点请求，输出为（“URL”，1），即每有一次访问便将之记录下来。Reduce函数将各地的结果收集起来并进行统计。

注意，在整个MapReduce过程中我们并没有指定执行Map函数的主机和执行Reduce函数的主机，他的实现完全是在GFS的帮助下自动完成的，应用程序员并不需要关心。我们同样并不需要关心多台主机间的通信问题。这有点像网络下的Socket编程，我们并不需关心数据传输的底层实现。

 

其具体流程图如下：

 

下面是一些简单的扩展问题

 

一、容错问题

由于MapReduce本身是设计应用于大规模的分布式计算的（至少得有多台计算机吧），因此一个基本观点是故障是常态。虽然用户本身不用关心容错问题，但简单了解一下MapReduce库在容错方面的措施还是有好处的。

 

1）worker错误

worker是实际进行计算工作的主机，也是计算集群中最多的一部分，因此，worker出现故障的概率是最高的。

 

master通常会和所有的worker结点保持心跳信号，如果在规定的时间内未收到worker返回的信号，那该worker会被标记为无效。所有应该由这些worker完成的task（包括已经完成的task）都会被重置为初始化状态，并动态分配给其余的worker处理。

 

 

2）master错误

master故障是比较麻烦的事情，因为在原则上MapReduce的信息缓存和管理工作都是由master完成的。一旦master出现错误，那么现行的MapReduce任务就崩溃了。

 

比较直观的解决办法有2个。一是定期将master数据结构写入磁盘，形成一个checkpoint。一旦发生错误，可以从最后一个checkpoint开始启动新的master进程。二是一旦master出错，整个任务就被终止。客户可以根据日志来检查错误原因，并重新启动。在实际当中，第二种方式是更常用的。

 

 

 

 

二、任务粒度

如前所述，我们把Map分为M个小Task，把Reduce分为R个小Task。一般来说，M+R >> 主机数量。

 

M和R值都是需要限制的，因为，master结点的调度动作的时间复杂度是O（M+R），而空间复杂度是O（M*R）。由于对每个状态用一个byte就可以表示，所以空间复杂度倒是其次，关键是对于有限的带宽来说，时间复杂度一般接受不了。对Google的业务来说，M=200000，R=5000，主机数=2000比较合适。

 

 

三、备用任务

在实际测试当中，MapReduce的整体完成时间通常取决于“落后者”。即可能有某些Map任务和Reduce任务需要额外花费几倍的时间来处理。可能是原因有多种，比如带宽竞争，或者某台主机过热导致CPU失常等等。

 

一个有效的机制是：当一个MapReduce任务接近完成时，master会为剩余的“落伍”任务调度备用的进程来完成。不管是正式的主机完成了任务还是备用的主机完成了任务，该任务都会被标记为已经完成。测试表明，这种调优策略通常只占总时间的很少一部分，但在关闭备用任务之后，要多花44%的时间来完成一个排序任务。