改进型MapReduce(第二版)-大数据文档资料.pptx

改进型MapReduce(第二版)

1.前言

本文通过对MapReduce的分析，列出MapReduce存在的问题，然后提出一种解决这些问题的改进型MapReduce，这种改进型的MapReduce暂且取名为MapBalanceReduce。由于经验和水平有限，所述观点和方法未必正确，诚心欢迎交流探讨。

2.调度实体

在MapReduce和改进型MapReduce都存在Job和Task，它们之间的关系如下UML图所示：

Job是由一到多个Tasks组成的Tasks池，同一个Job内的各Task间是平等独立，不存在依赖也不存在优先级高低。JobTree是在MapReduce之上的一层调度体，如存在于HadoopHive。

计算框架的作用就是通过将Job分解成Tasks，然后调配Tasks到集群中各节点去执行。因此Tasks是整个系统均衡和调度的核心对象。可以说，控制好了Tasks，就能够调度好均衡好，否则就可能发生数据倾斜，一些节点累死而另一些节点饿死。

3.MapReduce问题

MapReduce最重要的基础是DFS（分布式文件系统），它的工作原理可简单的使用下图表示，包含了map和reduce两个最核心的过程，以及A、B和C三个数据输入输出：

除了上表所述的特征外，B部分的数据块个数通常为预先指定的reduce个数，因此其值通常不大，而且将reduce个数增倍意义也不大。

3.1.map

由于map的输入源自于DFS，是相对静态的数据，所以各MapTask是均衡的，而且其大小是已知和确定的。

3.2.reduce

reduce不同于map，它处理的是map后的数据，是动态产生的数据，只有在map完成之后才能确定的数据（包括数据的分布和大小等）。数据在经过map之后，就映射到了某个ReducdeTask，不能再更改，而且ReduceTask的个数也是不能修改的。

这会带来如下严重的问题：

1)reduce端数据倾斜：比如有些ReduceTask需要处理100GB数据，而另有一些只需

一见eyjian@第二版2

A

B

C

存储位置

DFS

本地存储

DFS

块大小是否均衡？

是

否

是

块大小是否可确定？

是

否

是

map和reduce的块大小是否接近？

不确定，非受控

map个数是否已知，非动态确定？

是

reduce个数是否已知，非动态确定？

是

通过分析A、B和C不难得出如下表所示的特征：

改进型MapReduce

改进型MapReduce

要处理10GB数据，甚至还有些ReduceTask可能空转，没有任何数据需要处理。最严重时，可能发生某个ReduceTask被分配了超出本地可用存储空间的数据量，或是超大数据量，需要特长处理时间；

2)reduce端数据倾斜直接导致了ReduceTask不均衡；

3)并行Job困难。类似于操作系统进程调度，如果要并行，必然存在Job间的调度切换，但由于ReduceTask需要处理的数据量可能很大，需要运行很长的时间，如果强制停止ReduceTask，对于大的ReduceTask会浪费大量的已运行时间，甚至可能导致一个大的Job运行失败。因此，无法实现类似于进程的并行调度器。

3.3.数据不均衡的两种情况

数据不均衡可分为两类：

1)KEY过于聚集，即不同KEY的个数虽多，但经过映射（如HASH）后，过于聚集在一起

采用两种办法相结合：一是将KEY分散得足够大（如HASH桶数够多），二是在balance的时候，进行重HASH，将大的打成小的。

2)KEY值单一，即不同KEY的个数少

对于这种情况，采用HASH再分散的方法无效，事先也无法分散得足够大，但处理的方法也非常简单。对这种情况，按照大小进行横切即可，但这个时候一次reduce无法得到最终结果，至少需要连接两次reduce，另外还需要增加balance接口，以方便区别是最后一次reduce，还是中间的reduce。

3.4.总结：两大主要问题

总的来说，MapReduce存在如下两大问题：

1)reduce并非不均衡，可能导致严重的倾斜；

2)并行调度能力弱，这是因为每个Task（主要是Red