悟懂MapReduce，不纠结！

• 2019 年 10 月 31 日
• 筆記

在《谷歌 MapReduce 初探》中，我们通过统计词频的 WordCount 经典案例，对 Google 推出的 MapReduce 编程模型有了一个认识，但是那种认识，还只是停留在知道有那么个模型存在，并没有认识到骨子里。而且上次初探，也遗留了很多猜想和疑问，这次不妨让我们深入去认识一下 MapReduce，希望能达到一个质的认识。

重点回顾

MapReduce 主要思想是分治法。采取分而治之的思想，将一个大规模的问题，分成多个小规模的问题，把多个小规模问题解决，然后再合并小规模问题的结果，就能够解决大规模的问题。

这么聊下去，我感觉会让你们很懵圈！那不妨举点栗子，举栗解千愁。

举个不太恰当的栗子，不知道大家有没有在农村掰过玉米，我小时候还没有自动收割机，每当玉米熟了的时候，都是靠人工去掰。要是家庭里只有一个劳动力，那只能一垅一垅的去掰；如果家庭劳动力比较多，就可以分配任务，同时去掰多垅玉米，人手一垅玉米，掰的过程放到篮子里或者地上就行，因为有专门的人手负责打包装车，这样很快一亩地就掰完了，而且能很快统计出掰了几车玉米。

人多力量大，不知道大家能否感受到一丝“分而治之”的理念；多个劳动力人手一行玉米，不知道大家有没有感觉到一丝 “MapReduce 之 Map”的概念；专门的人力负责打包装车，不知道大家有没有感觉到一丝“Map Reduce 之 Reduce”的概念。

再为你假设一个场景，面试的时候给你一个数组：{10,6,7,1,3,9,4,2} 要实现排序。

实现方式会有千万种，而我们只提“归并排序”，因为它是建立在归并操作上的一种有效的排序算法，并且是采用分治法（Divide and Conquer）的一个非常典型的应用。

如上图示意，归并排序的过程已经把分治的思想表达的很清楚了，有对算法感兴趣的可以自行深入。

一图解千愁

为了我们更清晰的了解 MapReduce 的流程，懒癌犯了，就不画图了，肆意找了一张图贴上。图上字字珠玑，一定要好好揣摩要传达的意思，切记一定要记住整个流程（重点是分区，归并）。

重拾案例

通过上面不太恰当的例子和图，稍微对 MapRedcue 的思想抽象了一下，不知道大家有没有什么感触呢？接下来让我们重拾上次分享提到的“WordCount”的经典案例，窥探一下具体的执行过程。

剖析背后。如图示意，主要参与者角色分为 User Program、Master 以及系列 Worker。

User Program 顾名思义就是我们实现好的业务逻辑处理的 MapReduce 程序代码；

Master 从图中也能够看出来承担了任务分配，能够把任务指派给 map worker 和 reduce worker（应该会存储一些元数据，记录哪些数据要给哪些 map worker，哪些数据要给哪些 reduce worker），猜想应该也会跟踪维护任务的状态；其实也就是皇上，掌控全局。

Worker 从图中能够看出主要分为 Map Worker、Reduce Worker。

Map Worker 从图中也能看出来负责接收用户的输入，然后执行用户实现的 map 操作，结果写入本地中间文件。

Reduce Worker 从图中能够看出来能够读取 Map Worker 产生的中间文件，并执行用户实现的 reduce 操作，并把结果输出（例如写到 GFS 存储）。

如何运转？这里要提一本书《大数据技术原理与应用》，因为下面这段剖析来自于这本书。

（1）执行 WordCount 的用户程序（采用 MapReduce 编写），会被系统分发部署到集群中的多台机器上，其中一台机器作为 Master，负责协调调度作业的执行，其余机器作为 Worker，可以执行 Map 或 Reduce 任务。

（2）系统分配一部分 Worker 执行 Map 任务，一部分 Worker 执行 Reduce 任务；MapReduce 将输入文件切分成 M 个分片，Master 将 M 个分片分给处于空闲状态的 N 个 Worker 来处理。

（3）执行 Map 任务的 Worker 读取输入文件，执行 Map 操作，生成一系列 <key,value> 形式的中间结果，并将中间结果保存在内存的缓冲区中。

（4）缓冲区中的中间结果会被定期刷写到本地磁盘上，并被划分为 R 个分区，这 R 个分区会被分发给 R 个执行 Reduce 任务的 Worker 进行处理；Master 会记录这 R 个分区在磁盘上的存储位置，并通知 R 个执行 Reduce 任务的 Worker 来“领取”属于自己处理的那些分区的数据。

（5）执行 Reduce 任务的 Worker 收到 Master 的通知后，就到相应的 Map 机器上“领回”属于自己处理的分区。不过可能会从多个 Map 机器上领取数据，因此当所有 Map 机器上的属于自己处理的数据都已经领取回来以后，这个 Reduce 任务的 Worker 会对领取的键值对进行排序（如果内存中放不下需要用到外部排序），使得具有相同 Key 的键值对聚集在一起，然后就可以开始执行具体的 Reduce 操作了。

（6）执行 Reduce 任务的 Worker 遍历中间数据，对每一个唯一 key 进行 Reduce 函数，结果写入到输出文件中；执行完毕后，唤醒用户程序，返回结果。

可靠性保证？

Master 的可用性？认为 Master 挂掉几率很小，如果挂掉任务就执行失败。

Worker 的可用性？Master 每隔一段时间会 ping 每个 Worker，如果 Worker 长时间没回复，Master 就将它标记为失效。如果失效的的 Worker 执行的是 Map 任务，则需要通知对应的 reduce 的 Worker 节点去新的 Map Worker 节点拿输入数据。

答疑解惑

针对上期遗留的问题逐个进行剖析解答。

猜想：map、reduce 函数中间感觉又触发了“针对同一个单词的 value 的组合（也就是把相同单词出现的次数，串在一起）”，不然 reduce 函数怎么能接收到 values（每个单词对应的出现次数的一串“1”）。

这不就是归并的事情么！在“一图解千愁”以及“如何运转？”环节中均有答案！

疑问 1：map 产生的中间键值对，是放到内存、本地磁盘还是放到了 GFS 上存储？

在“一图解千愁”以及“如何运转？”环节中均有答案！

疑问 2：我们写好了 Map 函数和 Reduce 函数，怎么就跑到了多台机器上呢？

在“如何运转？”环节中已经有答案！