[MapReduce: Simplified Data Processing on Large Clusters](https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/mapreduce-o sdi04.pdf)
摘要
模型
指定一个map function，把kv对处理成新的kv对，然后，reduce函数，把所有的中间态kv归并成结果。
核心问题
1、输入数据分割
2、分布式集群计算调度
3、机器异常处理
4、集群机器间通信
特性
1、海量普通商业机器上运行
2、高可伸缩
一、介绍
为什么要做
海量数据的处理需求，但是实际上计算的代码又不复杂，核心的诉求是数据量太大，难以在单机完成。
怎么做
抽象map - reduce函数接口模型，包括屏蔽并行计算，分布式可伸缩计算、归并等操作，并在普通的商业计算上达到高性能。
二、计算模型
MapReduce提供计算框架，将输入的KV对经过处理，输出新的KV对。
Map和Reduce 函数，都是由用户自定义的。其中，Map函数把一组KV对计算并得到新的KV数据集，而Reduce函数把初步聚合的KV数据集进一步归并到一起。
举例
URL计数
统计日志里面出现的url次数
1、输入一批url
2、map输出的数据结构为<URL,1>
3、reduce函数把所有的URL计数加起来求和，4、输出<URL，total count>
倒排索引
1、输入docID，doc内容
2、map分解，输出<word, docID>
3、reduce把所有word关联的docID放到一起，
4、输出<word，list(docID)>
三、实现
运行的环境
1、2核cpu，2-4G内存机器
2、百兆带宽
3、千百台机器构成的集群，机器故障是常态
4、分布式存储，存储与不可控的硬件设备上
5、用户提交任务模式
执行流程
详细步骤
1、将输入文件安装64MB（用户可自定义）分割成M份，然后在集群中启动多个进程（多少个？）
2、进程模型为master-workers，其中一个master进程，M个map进程，R个reduce进程。master负责分发任务到空闲的map和reduce进程
3、map进程从输入数据中逐个解析kv对，调用用户定义的Map函数，产出新的kv对集合，在内存中缓存起来。
4、map进程周期性的把buffer中的数据，刷到磁盘中。磁盘中写的数据会被分割成R份（每个机器都分割成R份吗），完成后把数据存储路径通知到master。
5、reduce进程会收到来自master的调度通知时，使用RPC把数据拉过来。全部读取后，以key为键值排序。如果数据集过大，内存装不下时，会使用到外部排序。
6、reduce worker对排好序的KV数据集逐个执行用户态reduce函数，把同一个key下的数据聚合起来（注意这个聚合，可能是简单的计数、求和、归并到一起等）。在输出结果中，会把用户态的reduce函数放到文件结尾。
7、当所有的map和reduce 任务完成后，master回吐数据到用户进程。
Master 数据结构
进程信息：map/reduce进程的idle、执行状态、是否已完成
中间结果信息：存储map worker产出的中间KV数据集。
容错
worker 失败处理
核心是把失败worker的任务重新再执行一遍。
- 探活机制：定时ping worker机器，ping不通时，认为任务失败。
- 重做机制：任务失败时，发起任务重做。
- 重做流程：当map worker A失败时，通知所有已经在处理A产出的worker重做，切到新的map worker B的产出中。
- 重试细节：机器故障时，map worker已完成的任务，需要重试，因为此时机器ping不通，已经产出到本地的文件不可达；而reduce worker已完成的任务不用重做，因为已经存储到分布式机器中。
思考
为什么map worker存储到本地而reduce worker存储到分布式存储中？
猜测：分布式存储认为是最终的产出地，map的结果是中间态，放到本地速度快一些。放到分布式存储中，似乎map差距也不大？
master 失败处理
可以用还原点的方式重新拉起一个master进程。实际MR在实现的时候，直接让client侧重试解决。
幂等处理
map 和reduce worker由于重试造成的计算结果如何处理？
1、两类worker执行可能多次，因此产出的结果也会有多份
2、map worker在向master上报计算结果的时候，master如果检测到已经计算过了，则忽略此次上报。
3、reduce worker产生的计算结果在写入最终的存储时，会覆盖写，每次都写一样的内容。
达到了操作的幂等效果。
计算就近原则
跨机器计算涉及到下载中的带宽、时间等消耗。因此，master在分配任务时，把worker分配到含有输入数据的机器上，或者就近的机器上，降低带宽与提高计算时间。
任务大小粒度问题
理想中，任务粒度越小越好，把整个集群的资源充分利用起来。但是master中需要维护任务的进程信息、以及执行状态信息，因此任务数是受限于内存的。reduce任务的个数可以用户来指定，而map任务数M通常由MR来确定（输入数据大小/16MB-64MB）。推荐的指标是，2000台实例时，200000个M任务以及5000个R任务。
任务备份机制
任务备份机制，解决的是MR任务中的长尾问题。长尾问题指的是，部分进程，执行的时间比较久，拖慢了整体的任务时间。因此呢，master在MR任务快完成的时候，把还在进行中的任务做了一次备份执行，无论是原始进程还是备份进程完成，则认为MR任务完成了。这样屏蔽了一些单点故障，比如cpu idle低、磁盘性能差等问题。
