一.概要
- MapReduce是一种编程模型，它是一种用于处理和生成大型数据集的实现。用户通过指定一个用来处理键值对(Key/Value)的map函数来生成一个中间键值对集合。然后，再指定一个reduce函数， 它用来合并所有的具有相同中间key的中间value 。
二.编程模型
- 由用户所编写的Map函数接收输入，并生成一个中间键值对集合。MapReduce这个库会将所有共用一个键的值组合到一起，传递给Reduce函数
- Reduce函数接收一个中间键以及该键的值得集合作为输入。它会将这些值合并起来，生成一组更小的值得集合。
案例
从大量文档统计计算出每一个单词出现的数量
map(String key, String value):
// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w,"1");
reduce(String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));
map函数会返回一个单词加上它出现的次数的键值对（在这个例子中，返回的出现次数就是1）。
reduce函数会将该单词的出现次数统计在一起。
三.具体实现
- 用户程序中的MapReduce库会先将输入文件切分为M个片段，通常每个片段的大小在16MB到64MB之间。接着，它会在集群中启动许多个进程。
- 有一个进程是比较特殊的，那就是master。剩下的进程都是worker，master会对这些worker进行任务分配。这里有M个Map任务以及R个Reduce任务要进行分配。master会给每个空闲的worker分配一个map任务或者一个reduce任务。
- 被分配了map任务的worker会读取相关的输入数据片段。它会从输入数据中解析出键值对，并将它们传入用户定义的Map函数中。Map函数所生成的中间键值对会被缓存在内存中
- 每隔一段时间，被缓存的键值对会被写入到本地硬盘，并通过分区函数分到R个区域内。这些被缓存的键值对在本地磁盘的位置会被传回master。master负责将这些位置转发给执行reduce操作的worker。
- 当master将这些位置告诉了某个执行reduce的worker，该worker就会使用RPC的方式去从保存了这些缓存数据的map worker的本地磁盘中读取数据。当一个reduce worker读取完了所有的中间数据后，它就会根据中间键进行排序，这样使得具有相同键值的数据可以聚合在一起。之所以需要排序是因为通常许多不同的key会映射到同一个reduce任务中。如果中间数据的数量太过庞大而无法放在内存中，那就需要使用外部排序。
- reduce worker会对排序后的中间数据进行遍历。然后，对于遇到的每个唯一的中间键，reduce worker会将该key和对应的中间value的集合传入用户所提供的Reduce函数中。Reduce函数生成的输出会被追加到这个reduce分区的输出文件中。
- 当所有的map任务和reduce任务完成后，master会唤醒用户程序。此时，用户程序会结束对MapReduce的调用。
完成之后，MapReduce的输出结果会存放在输出文件之中。
3.1 Master的数据结构
- master 中保存了每一个Map和Reduce任务的状态(闲置,正在运行，以及完成), 以及非空闲任务的worker机器的ID
- 它将map任务所生成的中间文件区域的位置传递给reduce任务。
3.2容错
Worker故障
- master会周期性ping 每一个worker .如果在一定时间内没有收到worker的相应，那么master 会将该worker 进行标记为 failed . 所有由该worker完成的Map任务会重置为空闲状态，由其他的worker去进行完成。
Master故障
一个简单的解决好办法就是让master周期性的将上文所描述的数据结构写入磁盘，即checkpoint。如果这个master挂掉了，那么就可以从最新的checkpoint创建出一个新的备份，并启动master进程。然而，因为只有一个master，所以我们并不希望它发生故障。因此如果master故障了，我们目前的实现会中断MapReduce计算。客户端可以检查该master的状态，并且根据需要可以重新执行MapReduce操作。