MapReduce简介

什么是 MapReduce

MapReduce is a programming model and an associated implementation for processing and generating large data sets.

​ MapReduce 是一个并行程序设计模型与方法（Programming Model & Methodology）。它借助于函数式程序设计语言 Lisp 的设计思想，提供了一种简便的并行程序设计方法，用 Map 和 Reduce 两个函数编程实现基本的并行计算任务，提供了抽象的操作和并行编程接口，以简单方便地完成大规模数据的编程和计算处理。

为什么需要 MapReduce

分布式系统的挑战

​ 为了获得更高的计算性能、更强的容错、更安全的系统以及一些业务上天然的需要，人们需要构建可靠的分布式系统，把计算任务分配到各个计算机上完成。但可想而知多台计算机协同工作的方式必然会比单台计算机带来更多的挑战，例如：

• 并发编程和各种复杂交互所带来的挑战
• 计算机集群中发生的局部错误。
• 计算机数量的增长和计算性能的增长不成正比。

MapReduce 的产生

​ MapReduce是由Google设计，开发和使用的一个系统，相关的论文在2004年发表。为了对TB级别的数据进行大量的运算，例如为网页创建索引并排序，谷歌需要几千台计算机来帮助他们完成计算，但这就意味着计算程序必须是分布式的。然而谷歌不可能要求每一位程序员都熟练的开发分布式的程序，自己重复的“造轮子”。因此，一个屏蔽了分布式底层实现，让程序员只关心计算逻辑的框架应运而生——MapReduce。
​ 假设有一个统计一本小说里每个单词出现次数的计算任务，现在有如下解决方法

MapReduce实际上就是方法3的抽象，用户只需要关心具体的计算逻辑，至于如何拆分文件，如何整合结果，都交给框架实现。

MapReduce基本工作方式

Map 函数

• 在MapReduce中，Map函数负责“分”的部分，他的入参由组成，其中，key是输入文件的名字，（这里的输入文件已经是被分成M个数据片段之后的结果），value表示输入文件的内容。在统计单词频率的例子中，value包含了要统计的文本。Map函数会产出零个或者多个中间键值对，在词频统计中，中间键值对以单词为key ，值固定为 1 。

Reduce 函数

• Reduce 函数是在 Map 阶段之后执行的一种操作，用于对映射任务产生的中间键值对进行汇总、合并和处理。Reduce 函数的主要目的是将相同键（key）的所有中间值（values）进行归并和计算，从而生成最终的输出结果。在词频统计中，Reduce函数的入参是某个特定key的所有实例，其中单词为 key，value是一个数组，里面每一个元素是Map函数输出的key的一个实例的value。Reduce 函数将其转化为一个新的键值对，其中键是单词，而值是该单词在文本中的总出现次数。

总体流程

执行 Map 任务

​ 每个输入分片对应一个map任务，该任务使用用户提供的map函数处理分片中的每一条记录。格式化输入将每条记录转换为键值对表示形式。在map任务完成后，结果首先写入内存缓存区，以减少磁盘I/O影响。内存缓存区的默认大小为100MB。当缓冲区的数据占据环形缓冲区的80%时，会触发将数据写入本地磁盘文件，即溢写。在写入过程中，map的处理结果仍然写入缓冲区，这个过程可以看作是一个环形操作。在执行map任务之前，每个键都会被分配到一个分区，这由一个叫做分区器的组件完成。默认的实现是哈希分区器，它根据键的哈希值和reduce任务数对进行取模以确定分区号。然后，在分区内对键进行排序，然后将内存中的数据写入文件。因为数据在内存中已经按分区排序，所以写入文件的数据在分区内是有序的。如果map任务产生的结果很大，就会不断将缓冲区的数据溢写到多个文件中，这些文件是按分区划分的，分区内有序。

​ 当map任务完成后，所有输出的小文件将合并成一个大文件，在合并文件的过程中，还会对分区内的文件进行排序。

​ 注意： 执行map任务时，combine操作是可选的，它是一个本地化的reduce操作，是map运算的后续操作，主要是在map计算中间文件之前对重复的键进行简单合并，以减少网络数据传输，提高带宽利用率。

Shuffle和排序

​ 在MapReduce过程中，需要将各节点上的相同类型的数据聚集到一个节点进行计算，这个将分布在不同节点的数据按照一定规则聚集到一起的过程称为Shuffle（也有人认为Shuffle从map输出结果开始）。当reduce任务开始时，它会通过RPC请求map任务所在的节点来获取属于自己的输出文件。当所有数据都复制过来后，将这些数据合并，由于map的输出数据是有序的，因此在reduce端采用归并排序进行合并，合并后将相同键的数据分组，不同键之间进行排序，最终形成一个键对应一组值的数据。

执行Reduce任务

​ 当分区数据合并成完整的有序列表后，用户的reduce代码开始执行。每个reduce任务都会产生一个单独的输出文件，通常存储在HDFS中。独立的输出文件使得reduce任务之间无需协调共享文件的访问，从而降低了reduce的复杂性并最大化了每个reduce任务的运行效率。输出文件的格式由Output format参数决定，该参数由MapReduce作业配置中的用户指定。

参考资料

• pdos.csail.mit.edu/6.824/paper…

• youtu.be/cQP8WApzIQQ…

• mit-public-courses-cn-translatio.gitbook.io/mit6-824/

• xie.infoq.cn/article/536…