《Google 三大论文》_MapReduce
MapReduce是Google三大论文中与应用方面最接近的一层，应该说，也是我们在学习和应用分布式系统基础架构（如hadoop）时唯一关心的。
简单点说，MapReduce是一种编程模型，在处理和生成TB级数据时非常有用：通过简单的接口来实现自动的并行化合大规模的分布式运算，并且不用考虑容错、负载均衡等等繁琐而麻烦的细节。
MapReduce借用了函数式编程的概念，它的实现的思路是：将庞大但是相似（这在分布式处理中很常见）的小的Task，通过Map函数分给不同的主机运算，最后，通过Reduce函数收集并合并计算结果，得到所需。
其基本模型是：利用一个输入Key/Value pair集合来产生一个输出的Key/Value pair集合。如下所示：
(input)?
?
下面是一些简单的扩展问题
?
一、容错问题
由于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%的时间来完成一个排序任务。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
