实现机制
MapReduce操作的执行流程图如图2-3所示。
用户程序调用MapReduce函数后，会引起下面的操作过程（图中的数字标示和下面的数字标示相同)：
(1)MapRedube函数首先把输入文件分成从块，每块大概(可以通过参数决定)，接着在集群的机器上执行分派处理程序。
(2)这些分派的执行程序中有一个程序比较特别，它是主控程序Master。剩下的执行程序都是作为Master分派工作的Worker (工作机)。总共有M个Map任务和及个Reduce任务需要分派，Master选择空闲的Worker来分配这些Map或Reduce任务。
(3)—个被分配了Map任务的Worker读取并处理相关的输入块。它处理输入的数据，并且将分析出的<key,value>对传递给用户定义的Map函数。Map函数产生的中间结果<key，value>对暂时缓冲到内存。
(4)这些缓冲到内存的中间结果将被定时写到本地硬盘，这些数据通过分区函数分成R个区。中间结果在本地硬盘的位置信息将被发送回Master,然后Master负责把这些位置信息传送给Reduce Worker。
(5)当Master通知执行Reduce的Worker关于中间<key,value>对的位置时，它调用远程过程，从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的任务调度，把失效Woricer的任务调度到其他Worker上重新执行。
案例分析
排序通常用于衡量分布式数据处理框架的数据处理能力，下面介绍如何利用MapReduce进行数据排序。假设有一批海量的数据，每个数据都是由26个字母组成的字符串，原始的数据集合是完全无序的，怎样通过MapReduce完成排序工作，使其有序（字典序）呢？可以通过以下三个步骤来完成。
(1)对原始的数据进行分割(Split),得到W个不同的数据分块，如图2-4所示。
(2)对每一个数据块都启动一个Map进行处理，采用桶排序的方法，每个Map中按照首字母将字符串分配到26个不同的桶中，图2-5是Map的过程及其得到的中间结果。
(3)对于Map之后得到的中间结果，启动26个Reduce。按照首字母将Map中不同桶中的字符串集合放置到相应的Reduce中进行处理。具体来说就是首字母为a的字符串全部放在Reducel中处理，首字母为b的字符串全部放在RedUCe2,以此类推。每个Reduce对于其中的字符串进行排序，结果直接输出。由于Map过程中已经做到了首字母 有序，Reduce输出的结果就是最终的排序结果。这一过程如图2-6所示。
从上述过程中可以看出，由于能够实现处理过程的完全并行化，因此利用MapReduce处理海量数据是非常适合的。
