Open Genluo opened 4 years ago
MapReduce 是一种并行编程模型，用于大规模数据集(大于 1 TB)的并行运算，它将复杂的、运行于大规模集群上的并行计算过程高度抽象到两个函数:Map 和 Reduce。MapReduce 极大地方便了分布式编程工作，编程人员在不会分布式并行编程的情况下，也可以很容易将自己的程序运行在分布式系统上，完成海量数据集的计算。
分布式并行编程与传统的程序开发方式有很大的区别。传统的程序都是以单指令、单数据流的方式顺序执行，虽然这种方式比较符合人类的思维习惯，但是这种程序的性能受到单台机器性能的限制，可扩展性较差。分布式并行程序可以运行在由大量计算机构成的集群上，从而可以充分利用集群的并行处理能力，同时通过向集群中增加新的计算节点，就可以很容易地实现集群计算能力的扩充。
MapReduce 是谷歌公司的核心计算模型。MapReduce 将复杂的、运行于大规模集群上的并行计算过程高度地抽象到两个函数:Map 和 Reduce，这两个函数及其核心思想都源自函数式编程语言。
在 MapReduce 中，一个存储在分布式文件系统中的大规模数据集会被切分成许多独立的小数据块，这些小数据块可以被多个 Map 任务并行处理。MapReduce 框架会为每个 Map 任务输入一个数据子集，Map 任务生成的结果会继续作为 Reduce 任务的输入，最终由 Reduce 任务输出最后结果，并写入分布式文件系统。特别需要注意的是，适合用 MapReduce 来处理的数据集需要满足一个前提条件:待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。
MapReduce 设计的一个理念就是“计算向数据靠拢”，而不是“数据向计算靠拢”，因为移动数据需要大量的网络传输开销，尤其是在大规模数据环境下，这种开销尤为惊人，所以，移动计算要比移动数据更加经济。本着这个理念，在一个集群中，只要有可能，MapReduce 框架就会将Map 程序就近地在 HDFS 数据所在的节点运行，即将计算节点和存储节点放在一起运行，从而减少了节点间的数据移动开销。
MapReduce 编程之所以比较容易，是因为程序员只要关注如何实现 Map 和 Reduce 函数，而不需要处理并行编程中的其他各种复杂问题，如分布式存储、工作调度、负载均衡、容错处理、网络通信等，这些问题都会由 MapReduce 框架负责处理。
下面给出一个简单实例。比如，我们想编写一个 MapReduce 程序来统计一个文本文件中每个单词出现的次数，对于表 7-1 中的 Map 函数的输入<k1,v1>而言，其具体数据就是<某一行文本在文件中的偏移位置，该行文本的内容>。用户可以自己编写 Map 函数处理过程，把文件中的一行读取后解析出每个单词，生成一批中间结果<单词,出现次数>，然后把这些中间结果作为 Reduce函数的输入，Reduce 函数的具体处理过程也是由用户自己编写的，用户可以将相同单词的出现次数进行累加，得到每个单词出现的总次数。
MapReduce 的核心思想可以用“分而治之”来描述，如图 7-1 所示，也就是把一个大的数据集拆分成多个小数据块在多台机器上并行处理，也就是说，一个大的 MapReduce 作业，首先会被拆分成许多个 Map 任务在多台机器上并行执行，每个 Map 任务通常运行在数据存储的节点上，这样，计算和数据就可以放在一起运行，不需要额外的数据传输开销。当 Map 任务结束后，会生成以<key,value>形式表示的许多中间结果。然后，这些中间结果会被分发到多个 Reduce 任务在多台机器上并行执行，具有相同 key 的<key,value>会被发送到同一个 Reduce 任务那里，Reduce 任务会对中间结果进行汇总计算得到最后结果，并输出到分布式文件系统中。
需要指出的是，不同的 Map 任务之间不会进行通信，不同的 Reduce 任务之间也不会发生任何信息交换;用户不能显式地从一台机器向另一台机器发送消息，所有的数据交换都是通过MapReduce 框架自身去实现的。
在 MapReduce 的整个执行过程中，Map 任务的输入文件、Reduce 任务的处理结果都是保存在分布式文件系统中的，而 Map 任务处理得到的中间结果则保存在本地存储中(如磁盘)。另外，只有当 Map 处理全部结束后，Reduce 过程才能开始;只有 Map 需要考虑数据局部性，实现“计算向数据靠拢”，而 Reduce 则无需考虑数据局部性。
MapReduce 框架使用 InputFormat 模块做 Map 前的预处理，比如验证输入的格式是否符 合输入定义;然后，将输入文件切分为逻辑上的多个 InputSplit，InputSplit 是 MapReduce 对文件 进行处理和运算的输入单位，只是一个逻辑概念，每个 InputSplit 并没有对文件进行实际切割，只 是记录了要处理的数据的位置和长度。
因为 InputSplit 是逻辑切分而非物理切分，所以还需要通过 RecordReader(RR)根据 InputSplit 中的信息来处理 InputSplit 中的具体记录，加载数据并转换为适合 Map 任务读取的键值 对，输入给 Map 任务。
Map 任务会根据用户自定义的映射规则，输出一系列的<key,value>作为中间结果。
为了让 Reduce 可以并行处理 Map 的结果，需要对 Map 的输出进行一定的分区(Portition)、 排序(Sort)、合并(Combine)、归并(Merge)等操作，得到<key,value-list>形式的中间结果，再 交给对应的 Reduce 进行处理，这个过程称为 Shuffle。从无序的<key,value>到有序的 <key,value-list>，这个过程用 Shuffle(洗牌)来称呼是非常形象的。
Reduce 以一系列<key,value-list>中间结果作为输入，执行用户定义的逻辑，输出结果给 OutputFormat 模块
OutputFormat 模块会验证输出目录是否已经存在以及输出结果类型是否符合配置文件中 的配置类型，如果都满足，就输出 Reduce 的结果到分布式文件系统。
所谓 Shuffle（洗牌），是指对 Map 输出结果进行分区、排序、合并等处理并交给 Reduce 的过程。因此，Shuffle 过程分为 Map 端的操作和 Reduce 端的操作，如图 7-3 所示，主要执行以下操作
(1) 在Map端进行shuffle过程
Map 的输出结果首先被写入缓存，当缓存满时，就启动溢写操作，把缓存中的数据写入磁盘文件，并清空缓存。当启动溢写操作时，首先需要把缓存中的数据进行分区，然后对每个分区的 数据进行排序(Sort)和合(Combine)，之后再写入磁盘文件。每次溢写操作会生成一个新的 磁盘文件，随着 Map 任务的执行，磁盘中就会生成多个溢写文件。在 Map 任务全部结束之前， 这些溢写文件会被归并(Merge)成一个大的磁盘文件，然后通知相应的Reduce 任务来领取属于 自己处理的数据
(2)在Reduce端进行shuffle过程
Reduce 任务从 Map 端的不同 Map 机器领回属于自己处理的那部分数据，然后对数据进行归并(Merge)后交 给 Reduce 处理。
MapReduce 是一种并行编程模型，用于大规模数据集(大于 1 TB)的并行运算，它将复杂的、运行于大规模集群上的并行计算过程高度抽象到两个函数:Map 和 Reduce。MapReduce 极大地方便了分布式编程工作，编程人员在不会分布式并行编程的情况下，也可以很容易将自己的程序运行在分布式系统上，完成海量数据集的计算。
概述
1、分布式并行编程
分布式并行编程与传统的程序开发方式有很大的区别。传统的程序都是以单指令、单数据流的方式顺序执行，虽然这种方式比较符合人类的思维习惯，但是这种程序的性能受到单台机器性能的限制，可扩展性较差。分布式并行程序可以运行在由大量计算机构成的集群上，从而可以充分利用集群的并行处理能力，同时通过向集群中增加新的计算节点，就可以很容易地实现集群计算能力的扩充。
2、MapReduce并行编程模型
MapReduce 是谷歌公司的核心计算模型。MapReduce 将复杂的、运行于大规模集群上的并行计算过程高度地抽象到两个函数:Map 和 Reduce，这两个函数及其核心思想都源自函数式编程语言。
在 MapReduce 中，一个存储在分布式文件系统中的大规模数据集会被切分成许多独立的小数据块，这些小数据块可以被多个 Map 任务并行处理。MapReduce 框架会为每个 Map 任务输入一个数据子集，Map 任务生成的结果会继续作为 Reduce 任务的输入，最终由 Reduce 任务输出最后结果，并写入分布式文件系统。特别需要注意的是，适合用 MapReduce 来处理的数据集需要满足一个前提条件:待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。
MapReduce 设计的一个理念就是“计算向数据靠拢”，而不是“数据向计算靠拢”，因为移动数据需要大量的网络传输开销，尤其是在大规模数据环境下，这种开销尤为惊人，所以，移动计算要比移动数据更加经济。本着这个理念，在一个集群中，只要有可能，MapReduce 框架就会将Map 程序就近地在 HDFS 数据所在的节点运行，即将计算节点和存储节点放在一起运行，从而减少了节点间的数据移动开销。
3、Map和Reduce函数
MapReduce 编程之所以比较容易，是因为程序员只要关注如何实现 Map 和 Reduce 函数，而不需要处理并行编程中的其他各种复杂问题，如分布式存储、工作调度、负载均衡、容错处理、网络通信等，这些问题都会由 MapReduce 框架负责处理。
下面给出一个简单实例。比如，我们想编写一个 MapReduce 程序来统计一个文本文件中每个单词出现的次数，对于表 7-1 中的 Map 函数的输入<k1,v1>而言，其具体数据就是<某一行文本在文件中的偏移位置，该行文本的内容>。用户可以自己编写 Map 函数处理过程，把文件中的一行读取后解析出每个单词，生成一批中间结果<单词,出现次数>，然后把这些中间结果作为 Reduce函数的输入，Reduce 函数的具体处理过程也是由用户自己编写的，用户可以将相同单词的出现次数进行累加，得到每个单词出现的总次数。
工作流程
1、概述
MapReduce 的核心思想可以用“分而治之”来描述，如图 7-1 所示，也就是把一个大的数据集拆分成多个小数据块在多台机器上并行处理，也就是说，一个大的 MapReduce 作业，首先会被拆分成许多个 Map 任务在多台机器上并行执行，每个 Map 任务通常运行在数据存储的节点上，这样，计算和数据就可以放在一起运行，不需要额外的数据传输开销。当 Map 任务结束后，会生成以<key,value>形式表示的许多中间结果。然后，这些中间结果会被分发到多个 Reduce 任务在多台机器上并行执行，具有相同 key 的<key,value>会被发送到同一个 Reduce 任务那里，Reduce 任务会对中间结果进行汇总计算得到最后结果，并输出到分布式文件系统中。
需要指出的是，不同的 Map 任务之间不会进行通信，不同的 Reduce 任务之间也不会发生任何信息交换;用户不能显式地从一台机器向另一台机器发送消息，所有的数据交换都是通过MapReduce 框架自身去实现的。
在 MapReduce 的整个执行过程中，Map 任务的输入文件、Reduce 任务的处理结果都是保存在分布式文件系统中的，而 Map 任务处理得到的中间结果则保存在本地存储中(如磁盘)。另外，只有当 Map 处理全部结束后，Reduce 过程才能开始;只有 Map 需要考虑数据局部性，实现“计算向数据靠拢”，而 Reduce 则无需考虑数据局部性。
2、执行阶段
MapReduce 框架使用 InputFormat 模块做 Map 前的预处理，比如验证输入的格式是否符 合输入定义;然后，将输入文件切分为逻辑上的多个 InputSplit，InputSplit 是 MapReduce 对文件 进行处理和运算的输入单位，只是一个逻辑概念，每个 InputSplit 并没有对文件进行实际切割，只 是记录了要处理的数据的位置和长度。
因为 InputSplit 是逻辑切分而非物理切分，所以还需要通过 RecordReader(RR)根据 InputSplit 中的信息来处理 InputSplit 中的具体记录，加载数据并转换为适合 Map 任务读取的键值 对，输入给 Map 任务。
Map 任务会根据用户自定义的映射规则，输出一系列的<key,value>作为中间结果。
为了让 Reduce 可以并行处理 Map 的结果，需要对 Map 的输出进行一定的分区(Portition)、 排序(Sort)、合并(Combine)、归并(Merge)等操作，得到<key,value-list>形式的中间结果，再 交给对应的 Reduce 进行处理，这个过程称为 Shuffle。从无序的<key,value>到有序的 <key,value-list>，这个过程用 Shuffle(洗牌)来称呼是非常形象的。
Reduce 以一系列<key,value-list>中间结果作为输入，执行用户定义的逻辑，输出结果给 OutputFormat 模块
OutputFormat 模块会验证输出目录是否已经存在以及输出结果类型是否符合配置文件中 的配置类型，如果都满足，就输出 Reduce 的结果到分布式文件系统。
3、shuffle过程详解
所谓 Shuffle（洗牌），是指对 Map 输出结果进行分区、排序、合并等处理并交给 Reduce 的过程。因此，Shuffle 过程分为 Map 端的操作和 Reduce 端的操作，如图 7-3 所示，主要执行以下操作
(1) 在Map端进行shuffle过程
Map 的输出结果首先被写入缓存，当缓存满时，就启动溢写操作，把缓存中的数据写入磁盘文件，并清空缓存。当启动溢写操作时，首先需要把缓存中的数据进行分区，然后对每个分区的 数据进行排序(Sort)和合(Combine)，之后再写入磁盘文件。每次溢写操作会生成一个新的 磁盘文件，随着 Map 任务的执行，磁盘中就会生成多个溢写文件。在 Map 任务全部结束之前， 这些溢写文件会被归并(Merge)成一个大的磁盘文件，然后通知相应的Reduce 任务来领取属于 自己处理的数据
(2)在Reduce端进行shuffle过程
Reduce 任务从 Map 端的不同 Map 机器领回属于自己处理的那部分数据，然后对数据进行归并(Merge)后交 给 Reduce 处理。