Hadoop分布式计算框架：实现云计算

Hadoop的核心分为两部分，第一部分是分布式文件系统HDFS，在6.5节已经介绍；第二部分是Hadoop的分布式计算框架MapReduce。

1）MapReduce的含义

MapReduce是Google开发的Java、Python、C＋＋编程模型，它是一种简化的分布式编程模型和高效的任务调度模型，用于大规模数据集（大于1 TB）的并行计算。严格的编程模型使云计算环境下的编程十分简单。MapReduce借鉴了Lisp等函数编程语言的思想，将要执行的问题分解成Map（映射）和Reduce（归约）的方式，先通过Map程序将数据切割成不相关的区块，分配（调度）给大量计算机处理，达到分布式运算的效果，再通过Reduce程序将结果汇总输出。

MapReduce模型简单，并能满足绝大多数网络数据分析工作，因此被Google、Hadoop等云计算平台广泛采用。实际上，MapReduce是一种简化的并行计算编程模型，这对开发人员而言具有重要的意义。随着互联网数据的急剧增长，开发人员面临越来越多的大数据量计算问题，处理这类问题的主要方法是并行计算，然而并行计算是一个相对复杂的技术，不易掌握。MapReduce的出现降低了并行应用开发的入门门槛，隐藏了并行化、容错、数据分布、负载均衡等复杂的分布式处理细节，使得开发人员可以专注于程序逻辑的编写。MapReduce使并行计算得以广泛应用，是云计算的一项重要技术。

2）MapReduce的原理

MapReduce提供了泛函编程的一个简化版本，与传统编程模型中函数参数只能代表明确的一个数或数的集合不同，泛函编程模型中函数参数能够代表一个函数，这使得泛函编程模型的表达能力和抽象能力更高。在MapReduce模型中，输入数据和输出结果都被视作有一系列（key，value）对组成的集合，对数据的处理过程就是Map和Reduce过程。

Map过程：①读取输入文件内容，解析成（key，value）对。对输入文件的每一行，解析成（key，value）对，每一个键值对调用一次Map函数。②根据不同的业务需要由用户提供，处理作为输入的一组（key，value）对，生成另外一组（key，value）对作为中间结果。③对中间结果（key，value）对进行分区。④对不同分区的数据，按照key进行排序、分组，相同key的value放到一个集合中。

每个Map函数都各自针对一部分原始数据进行指定的操作，不同Map之间互相独立，从而使得它们能够很方便地并行执行。

Reduce过程：①对多个Map任务的输出，按照不同的分区，通过网络复制到不同的Reduce节点。②对多个Map任务的输出进行合并、排序。根据不同的业务由用户自定义，对输入的（key，value）进行处理，再转换成新的（key，value）输出。③把Reduce的输出保存到文件中。

每个Reduce函数所处理的Map中间结果是互不交叉的，所有Reduce函数产生的最终结果经过简单连接后形成最终的结果集，因此Reduce任务也可以并行执行。

具体Map和Reduce过程的键值对格式如表10-1所示。

表10-1　Map、Reduce键值对格式

因此，使用MapReduce模型编程时，程序员主要工作是编写以下两个函数：

Map：（k1，v1）－－＞list（k2，v2）(https://www.xing528.com)

Reduce：（k2，list（v2））－－＞list（k3，v3）

Map的输出恰好作为Reduce的输入。

3）MapReduce的执行

MapReduce是一种处理和产生大规模数据集的编程模型，程序员在Map函数中指定对各分块数据的处理过程，在Reduce函数中指定如何对分块数据处理的中间结果进行归约。用户只需要指定Map和Reduce函数来编写分布式的并行程序。当在集群上运行MapReduce程序时，程序员不需要关心如何将输入的数据分块、分配和调度，同时系统还将处理集群内节点失败以及节点间通信的管理等。图10-2给出了一个MapReduce程序的具体执行过程。

图10-2　MapReduce程序的具体执行过程

用户程序调用MapReduce函数后，会引起下面的操作过程：

①用户程序调用MapReduce库函数将输入文件分成M个数据文件块，每个数据文件块大小为16～64 MB（可通过系统可选参数来控制每个数据文件块的大小）。然后使用Fork（可以理解为是一个创建子进程的函数）将用户程序在机群中创建特定数据的程序副本。这些程序副本中包含一个Master程序，若干个Worker程序（Worker的数量可以由用户指定）。

②Master会根据Worker的空闲情况，将Map任务和Reduce任务分配给空闲的Worker。Map任务的数量取决于输入文件被分成的数据文件块M的个数。Reduce任务的数量主要取决于步骤④中的分区数据R。

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

④这些缓冲到内存的中间结果将被定时写到本地硬盘，这些数据通过分区函数分成R个不同分区（分区数据R和分区函数由用户指定）。中间结果在本地硬盘上的存储位置将被发送给Master，Master负责把这些位置信息转发给运行Reduce的Worker。

⑤当运行Reduce的Worker程序接收到Master发来的关于中间结果（key，value）对的存储位置信息后，它调用远程过程，从执行Map的Worker所在本地硬盘上读取缓冲区中的中间结果，其后对key进行排序，使得具有相同key值的数据聚合在一起。由于不同key值会映射到相同Reduce任务上，因此必须进行归并排序，最终形成一个Reduce的输入文件。如果中间数据太大无法在内存中完成排序时，需要使用外排序算法。

⑥Reduce Worker根据每一个唯一中间key来遍历所有排序后的中间数据，并把key值和它相关的中间value值的集合传递给用户自定义的Reduce函数。Reduce函数对输入进行处理后，将得到的最终结果写入所属分区的输出文件。

⑦当所有Map任务和Reduce任务都完成之后，Master唤醒用户程序，此时MapReduce程序返回用户程序的调用点。