概述

MapReduce是一个分布式计算模型。根据输入文件、Map/Reduce函数来产生计算结果。

  • Map函数：输入为key/value值，输出中间的key/value值的集合
  • Reduce函数：输入为一个key和一个value值集合，输出为最后的结果。

MapReduce中存在一台Master，用于管理和分配工作给Worker执行。

运行

  1. key/value 输入数据会被划分为 M 个数据集合（16MB~64MB不等，以文件形式存在）
  2. Master收到文件集合，将其分配给Worker执行Map任务。
  3. Map生成中间key/value集合，其会被分区函数分成 R 个区域，对应R个Reuce任务，将其写入到硬盘中。最后通知Master存储中间信息。
  4. 等到Map任务完全执行完成，得到 M * R 个中间文件。
  5. Master分配执行Reduce任务。
  6. Worker会拿到分区下的中间文件位置信息，进行读取，然后进行聚合排序，把相同key的中间key/value信息给Reduce执行。最后将结果追加到所属分区的输出文件中。
  7. 等待Reduce任务全部执行完成，产生R个结果文件（因为存在R个区域），其是保存在共享存储中的。
  8. Master唤醒用户程序，告知完成。

其中 R 通常是由用户指定的。

如果 Master 收到了两份相同任务的文件信息，只保留一份即可，因为是幂等的。

为了避免多个执行相同Reduce任务的Worker产生相同的文件，需要使用原子性操作确保结果仅包含一个Reduce任务产生的数据。

优化

1，落伍者

影响一个MapReduce的总执行时间最通常的因素是“落伍者”，例如机器磁盘出现问题时，将会等待非常久的时间。

解决方法是调用备用的Worker来执行这个任务。

2，顺序排序

将中间key/value数据按key排序，可以增加之后Reduce任务的读取效率（从随机读取变为顺序读取）。

3，Combiner函数

在某些情况下，Map函数产生的中间key值的重复数据会占很大的比重，并且用户自定义的Reduce函数满足结合律和交换律。

可以运行指定一个可选的combiner函数，在本地将相同key值进行合并，然后写入到中间文件中。

一般情况下，Combiner和Reduce函数是一样的。Combiner函数和Reduce函数之间唯一的区别是MapReduce库怎样控制函数的输出。

容错

1，worker故障

Master会周期性的发送心跳请求（Ping）Worker。若Worker在超时时间内未响应，则可以认为该Worker故障，重新分配其执行的任务。

因为Map任务的中间结果存储在Worker中，因此其已经完成的Map任务也需要重新执行。Reduce的结果是存储在全局文件系统中的，不需要重新执行。

2，Master故障

Master周期性的将元数据持久化。

3，损害的记录

因为程序中的Bug或输入文件中的Bug，导致Map/Reduce任务在处理时Crash掉。Master可以通过记录这些任务，来跳过这些记录（出现多次时可以判定是Bug）。