Reducing partition skew on MapReduce: an incremental allocation approach
Reducing partition skew on MapReduce: an incremental allocation approach
复制标题
减少 MapReduce 上的分区倾斜：一种增量分配方法
DOI：
10.1007/s11704-018-6586-2
复制
发表时间：
2019-06
影响因子：
4.2
通讯作者：
Li ZhanHuai
中科院分区：
文献类型：
--
作者：
Wang Zhuo;Qun Chen;Bo Suo;Pan Wei;Li ZhanHuai
MapReduce是一种并行计算模型，在分布式集群大数据处理中得到了广泛的应用。MapReduce由交替的map和reduce阶段组成，必须将映射器生成的中间数据shuffle到reducer中。确保MapReduce上工作负载平衡的关键挑战是在没有映射数据的详细分布信息的情况下减少reducer之间的分区倾斜。在本文中，我们提出了一种增量数据分配方法来减少MapReduce上reducer之间的分区倾斜。该方法将映射数据划分为多个微分区，并在映射过程中逐步收集其大小的统计数据。然后在多轮中将微分区增量地分配给reducer。我们建议分两个步骤执行增量分配：微分区调度和微分区分配。提出了一个马尔可夫决策过程模型来优化分配承诺的多轮微分区调度问题。我们给出了一个时间复杂度为o （K·N2）的最优解，其中K表示分配轮数，n表示微分区数。另外，我们还提出了一种贪婪但更有效的算法，其时间复杂度为o （K·NlnN）。然后，我们提出了一个最小最大规划模型来处理微分区和reducer之间的分配映射，并由于其np完备性而给出了一个有效的启发式解决方案。最后，我们在开源的MapReduce平台Hadoop上实现了所提出的方法，并对其性能进行了实证评估。我们的大量实验表明，与最先进的方法相比，所提出的方法在reducer之间实现了更好的数据负载平衡，并且总体上具有更好的并行性能。
MapReduce, a parallel computational model, has been widely used in processing big data in a distributed cluster. Consisting of alternate map and reduce phases, MapReduce has to shuffle the intermediate data generated by mappers to reducers. The key challenge of ensuring balanced workload on MapReduce is to reduce partition skew among reducers without detailed distribution information on mapped data.In this paper, we propose an incremental data allocation approach to reduce partition skew among reducers on MapReduce. The proposed approach divides mapped data into many micro-partitions and gradually gathers the statistics on their sizes in the process of mapping. The micropartitions are then incrementally allocated to reducers in multiple rounds. We propose to execute incremental allocation in two steps, micro-partition scheduling and micro-partition allocation. We propose a Markov decision process (MDP) model to optimize the problem of multiple-round micropartition scheduling for allocation commitment. We present an optimal solution with the time complexity ofO(K·N2), in which K represents the number of allocation rounds andNrepresents the number of micro-partitions. Alternatively, we also present a greedy but more efficient algorithm with the time complexity ofO(K·NlnN). Then, we propose a minmax programming model to handle the allocation mapping between micro-partitions and reducers, and present an effective heuristic solution due to its NP-completeness. Finally, we have implemented the proposed approach on Hadoop, an open-source MapReduce platform, and empirically evaluated its performance. Our extensive experiments show that compared with the state-of-the-art approaches, the proposed approach achieves considerably better data load balance among reducers as well as overall better parallel performance.
登录
查看更多内容
DOI：
10.14778/2212351.2212353
发表时间：
2012-04
期刊：
ArXiv
影响因子：
--
作者：
Ahmed A. Metwally;C. Faloutsos
通讯作者：
Ahmed A. Metwally;C. Faloutsos
DOI：
10.1145/2608020.2608021
发表时间：
2014-06
期刊：
--
影响因子：
--
作者：
Prateek Dhawalia;S. Kailasam;D. Janakiram
通讯作者：
Prateek Dhawalia;S. Kailasam;D. Janakiram
DOI：
10.1145/2391229.2391242
发表时间：
2012-10
期刊：
--
影响因子：
--
作者：
A. Rasmussen;V. Lam;Michael Conley;G. Porter;Rishi Kapoor;Amin Vahdat
通讯作者：
A. Rasmussen;V. Lam;Michael Conley;G. Porter;Rishi Kapoor;Amin Vahdat
DOI：
10.1109/cloudcom.2010.25
发表时间：
2010-11
期刊：
2010 IEEE Second International Conference on Cloud Computing Technology and Science
影响因子：
--
作者：
Shadi Ibrahim;Hai Jin;Lu Lu-Lu;Song Wu;Bingsheng He;Li Qi
通讯作者：
Shadi Ibrahim;Hai Jin;Lu Lu-Lu;Song Wu;Bingsheng He;Li Qi
DOI：
10.1145/2063576.2063976
发表时间：
2011-10
期刊：
--
影响因子：
--
作者：
Lars Kolb;Andreas Thor;E. Rahm
通讯作者：
Lars Kolb;Andreas Thor;E. Rahm