Mapreduce

bigtable + google file system + mapreduce （3）

Mapreduce:分布式计算框架

MapReduce综述

• MapReduce是一种计算模型，该模型可以将大型数据处理任务分解成很多单个的、可以在服务器集群中并行执行的任务，而这些任务的计算结果可以合并在一起来计算最终的结果。简而言之，Hadoop Mapreduce是一个易于编程并且能在大型集群（上千节点）快速地并行得处理大量数据的软件框架，以可靠，容错的方式部署在商用机器上。

MapReduce这个术语来自两个基本的数据转换操作：map过程和reduce过程。

一、map

map操作会将集合中的元素从一种形式转化成另一种形式，在这种情况下，输入的键值对会被转换成零到多个键值对输出。
其中输入和输出的键必须完全不同，而输入和输出的值则可能完全不同。

二、reduce

某个键的所有键值对都会被分发到同一个reduce操作中。确切的说，这个键和这个键所对应的所有值都会被传递给同一个Reducer。
reduce过程的目的是将值的集合转换成一个值（例如求和或者求平均），或者转换成另一个集合。
Reducer最终会产生一个键值对。（需要说明的是，如果job不需要reduce过程的话，那么reduce过程也是可以不用的。）

整个流程：
input—>map—>shuffle—>reduce—>output

分布式：HDFS和Yarn

1. Job：MapReduce作业，是客户端需要执行的一个工作单元：包括输入数据、MapReduce程序和配置信息
2. Task：Hadoop会将作业job分成若干个任务（task）执行，其中包括两类任务：map任务和Reduce任务
3. Input split：输入分片，Hadoop会将MapReduce的输入数据划分成等长的小数据块，称为“分片”,Hadoop为每个分片构建一个map任务，并由该任务运行用户自定义的map函数从而处理分片中的每条记录。

HDFS

**HDFS(Hadoop Distributed File System)**基于Google发布的GFS论文设计开发。HDFS是Hadoop技术框架中的分布式文件系统，对部署在多台独立物理机器上的文件进行管理。

yarn

Yarn 是一个资源调度平台，负责为运算程序提供服务器运算资源，相当于一个分布式的操作系统平台。而MapReduce等运算程序则相当于运行于操作系统之上的应用程序。

分片

1. why

处理单个分片的时间小于处理整个输入数据花费的时间，因此并行处理每个分片且每个分片数据比较小的话，则整个处理过程会获得更好的负载平衡（因为一台较快的计算机能够处理的数据分片比一台较慢的计算机更多，且成一定比例）。

2. 分片的大小

尽管随着分片切分得更细，负载平衡的质量也会更高。但是分片切分得太小的时候，管理分片的总时间和构建map任务的总时间将决定整个作业的执行时间。
对于大多数作业来说，一个合理的分片大小趋于HDFS一个块的大小，默认是128MB。

数据本地化优化（map任务）

Hadoop在存储有输入数据（HDFS中的数据）的节点上运行map任务，可以获得最佳性能（因为无需使用宝贵的集群带宽资源），这就是“数据本地化优化”（data locality optimization）。

1. 本地数据、本地机架与跨机架map任务

有时候存储该分片的HDFS数据块复本的所有节点可能正在运行其他map任务，此时作业调度需要从某一数据块所在的机架中一个节点寻找一个空闲的map槽（slot）来运行该map任务分片。特别偶然的情况下（几乎不会发生）会使用其他机架中的节点运行该map任务，这将导致机架与机架之间的网络传输。下图显示了这三种可能性。

2. 数据本地化原则决定了最佳分片大小

数据本地化的原则解释了为什么最佳分片大小应该与HDFS块大小相同：因为这是确保可以存储在单个节点上最大输入块的大小。

3. reduce任务不具备数据本地化的优势

单个reduce任务的输入通常来自于所有mapper的输出。排过序的map输出需通过网络传输发送到运行reduce任务的节点，数据在reduce端合并并由用户定义的reduce函数处理。

MapReduce任务数据流

reduce任务的数量并非由输入数据的大小决定，而是独立指定的。
真实的应用中，几乎所有作业都会把reducer的个数设置成较大的数字，否则由于所有中间数据都会放到一个reduce任务中，作业的处理效率就会及其低下。
增加reducer的数量能缩短reduce进程；但是reducer数量过多又会导致小文件过多而不够优化。
一条经验法则是：目标reducer保持每个运行在5分钟左右，且产生至少一个HDFS块的输出比较合适。

• 单reduce
  与上文map的操作一致。

• 多个reduce任务的MapReduce数据流
  

map任务到reduce任务的数据流称为shuffle（混洗，类似洗牌的意思），每个reduce任务的输入都来自许多map任务。
shuffle比图示的更加复杂而且调整shuffle参数对作业总执行时间的影响非常大。

• 无reduce任务

当数据完全可以并行处理时可能会出现无reduce任务的情况，唯一的非本地节点数据传输是map任务将结果写入HDFS。

combiner

函数（减少map和reduce之间的数据传输）

由前面的描述我们知道数据传输会占用集群上的可用带宽资源，从而限制了MapReduce作业的数量，因此我们应该尽量避免map和reduce任务之间的数据传输。combiner作为一个中间函数简化map任务的输出从而减少了map任务和reduce任务之间的数据传输。

类似谓词下推来理解。（不能用于avg等，必须满足返回值bool或群的某些性质）