目录

1. MapReduce

2. 编程模型

3. 实现机制

4. 容错

5. 案例分析

     MapReduce是Google提出的一个软件架构，是一种处理海量数据的并行编程模式，用于大规模数据集（通常大于1TB）的并行计算。

    MapReduce的运行模式如下图所示。图中有M个Map操作和R个Reduce操作。

    MapReduce操作的执行流程如图所示：

     用户程序调用MapReduce函数后，会引起图中的操作过程（图中的数字标示和下面的数字标示相同）：

     （1）分割——MapReduce函数首先把输入文件分成 M 块 ，每块大概16M ~   64MB （可以通过参数决定），接着在集群的机器上执行分派处理程序。

     （2）指派Map——这些分派的执行任务中有一个程序比较特别，它是主控程序 Master 。剩下的执行程序都是作为 Master 分派工作的 Worker（工作机）。总共有 M 个 Map 任务和 R 个 Reduce 任务需要分配，Master 选择空闲的 Worker 来分配这些 Map 或 Reduce任务。

     （3）读取——一个被分配了 Map 任务的 Worker 读取并处理相关的输入块。它处理输入的数据，并且将分析出的  对传递给用户定义的 Map 函数。Map 函数产生的中间结果  对暂时缓冲到内存。

     （4）本地写入——这些缓冲到内存的中间结果将被定时写到本地硬盘，这些数据通过通过分区函数分成 R 个区。中间结果在本地硬盘的位置信息将被发送回 Master ，然后 Master 负责把这些位置信息传送给 Reduce Worker。

    （5）远程读取——当 Master 通知执行 Reduce 的 Worker 关于中间 对的位置时，它调用远程过程，从 Map Worker 的本地硬盘上读取缓冲的中间数据。当 Reduce Worker 读到所有的中间数据，它就使用中间 key 进行排序，这样可使相同 key 的值都在一起。因为有许多不同 key 的 Map 都对应相同的 Reduce 任务，所以排序是必须的。如果中间结果集过于庞大，那么就需要使用外排序。

   （6）写入——Reduce Worker 根据每一个唯一中间 Key 来遍历所有的排序后的中间数据，并且把 Key 和相关的中间结果值集合传递给用户定义的Reduce函数。Reduce函数的结果写到一个最终的输出文件。

   （7）当所有 Map 任务和 Reduce 任务都完成时，Master激活用户程序。此时 MapReduce 返回用户程序的调用点

   由于MapReduce在成百上千台机器上处理海量数据，所以容错机制是不可或缺的。总的来说，MapReduce 通过重新执行失效的地方来实现容错。

     1. Master 失效

         • Master会周期性设置检查点（checkpoint），并导出 Master 的数据。一旦某个任务失效，系统就从最近的一个检查点恢复并重新执行。

         • 由于只有一个 Master 在运行，如果 Master 失效了，则只能终止整个 MapReduce 程序的运行并重新开始。

     2. Worker失效

        • 相对于 Master 失效而言，Worker 失效算是一种常见的状态。

        • Master 会周期性的给 Worker 发送 ping 命令，如果没有 Worker 的应答，则 Master 认为 Worker 失效，终止对这个 Worker 的任务调度，把失效 Worker 的调度任务到其他 Worker 上重新执行。

      以案例介绍 MapReduce 如何进行数据排序。

     假设有一批海量数据，每个数据都是由26个字母组成的字符串，原始的数据集合是完全无序的，MapReduce 通过以下三个步骤来完成排序工作。

        （1）对原始的数据进行分割（Split），得到 N 个不同的数据分块，如图5-1所示。

        （2）对每一个数据分块都启动一个 Map 进行处理。采用桶排序的方法，每个 Map 中按照首字母将字符串分配到26个不同的桶中，图5-2是 Map的过程及其得到的中间结果。

       （3）对于 Map 之后得到的中间结果，启动26个 Reduce。按照首字母将 Map 中不同桶中的字符串集合放置到相应的 Reduce 中进行处理。具体来说就是首字母为 a 的字符串全部放在 Reduce1 中进行处理，首字母为 b 的字符串全部放在 Reduce2 中进行处理，以此类推。每个 Reduce 对于其中的字符串进行排序，结果直接输出。由于 Map 过程中已经做到了首字母有序，Reduce 输出的结果就是最终的排序结果。这一过程如图5-3所示。

                                               图5-1  数据分块

                                       图5-2  Map的过程及其得到的中间结果

                                            图5-3  Reduce过程

       本文学习总结自刘鹏教授主编的教材《云计算（第三版）》