常见算法及数据结构之MapReduce

【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[138]篇文章，欢迎阅读收藏】

1 基本概念

MapReduce 是一个分布式运算程序的编程框架，是用户开发“基于 hadoop 的数据分析 应用”的核心框架。MapReduce 核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的 分布式运算程序，并发运行在一个 hadoop 集群上。在程序由单机版扩成分布式版时，会引入大量的复杂工作。为了提高开发效率，可以将分布式程序中的公共功能封装成框架，让开发人员可以将精力集中于业务逻辑。Hadoop 当中的 MapReduce 就是这样的一个分布式程序运算框架，它把大量分布式程序都会涉及的到的内容都封装进了，让用户只用专注自己的业务逻辑代码的开发。

2 术语解释

映射（ Map ）：

简单说来，一个映射函数就是对一些独立元素组成的概念上的列表的每一个元素进行指定的操作。每个元素都是被独立操作的，而原始列表没有被更改，因为这里创建了一个新的列表来保存新的答案。这就是说， Map 操作是可以高度并行的，这对高性能要求的应用以及并行计算领域的需求非常有用。

化简（ Reduce ）：

对一个列表的元素进行适当的合并，虽然它不如映射函数那么并行，但是因为化简总是有一个简单的答案，大规模的运算相对独立，所以化简函数在高度并行环境下也很有用。

3 详细说明

3.1 MapReduce 原理

Hadoop 中的 MapReduce 是一个使用简单的软件框架，基于它写出来的应用程序能够运行在由上千个机器组成的大型集群上，并以一种可靠容错并行处理 TB 级别的数据集。Hadoop MapReduce 源于 Google 在 2004 年 12 月份发表的 MapReduce 论文。Hadoop MapReduce 其实就是 Google MapReduce 的一个克隆版本。

MapReduce 主要有以下几个特点：

1 、 MapReduce 易于编程：它简单的实现一些接口，就可以完成一个分布式程序，这个分布式程序可以分布到大量廉价的 PC 机器运行。也就是说你写一个分布式程序，跟写一个简单的串行程序是一模一样的。就是因为这个特点使得 MapReduce 编程变得非常流行。

2 、良好的扩展性：当你的计算资源不能得到满足的时候，你可以通过简单的增加机器来扩展它的计算能力。

4 、适合 PB 级以上海量数据的离线处理：它适合离线处理而不适合在线处理。比如像毫秒级别的返回一个结果， MapReduce 很难做到。

MapReduce 框架的核心步骤主要分两部分：Map 和 Reduce ，当你向 MapReduce 提交一个计算作业时，它会首先把计算作业拆分成若干个 Map 任务，然后分配到不同的节点上去执行，每一个 Map 任务处理输入数据中的一部分，当 Map 任务完成后，会生产一些中间文件，这些中间文件将会作为 Reduce 任务的输入数据， Reduce 的任务主要目标就是把前面若干个 Map 的输出汇总到一起并输出。

3.2 MapReduce 工作流程

一个 MapReducer 作业经过了 input ， map ， combine ， reduce ， output 五个阶段，其中 combine 阶段并不一定发生， map 输出的中间结果被分到 reduce 的过程成为 shuffle （数据清洗）。