Chisel++: handling partitioning skew in MapReduce framework using efficient range partitioning technique
Chisel++: handling partitioning skew in MapReduce framework using efficient range partitioning technique
复制标题
DOI：
10.1145/2608020.2608021
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Prateek Dhawalia;S. Kailasam;D. Janakiram
中科院分区：
文献类型：
--
作者：
Prateek Dhawalia;S. Kailasam;D. Janakiram
MapReduce框架中的作业完成取决于运行最慢的reduce任务。在减少任务的完成点之间存在过大的时间差距会显著延迟工作。reduce task completion中的同步不仅可以更快地完成作业，还可以提高资源利用率。reduce任务的完成时间主要取决于每个任务的数据负载。键的划分在将输入数据负载平衡到reduce任务中起着重要作用。文献中提出了使用采样技术的范围分区，而不是基于哈希的分区，以提供更好的密钥分布。但是数据采样也容易受到数据/分区偏斜的影响，因为只有一小部分实际数据被扫描。在没有关于整个数据的先验信息的情况下，很难设计出完美的负载平衡分区程序。Chisel允许在分区期间发生数据倾斜，但通过为倾斜分区创建多个部分归约器和一个全局归约器来动态处理它。但当约简器的输出量很大时，全局约简器就成为了一个瓶颈。我们提出了一个有效的范围划分技术，消除了使用的全球减少，并产生更好的性能。我们还讨论了实现范围划分的各种方法。在我们的实验中，Chisel++在作业完成时间方面比Chisel提高了2倍。
Job completion in MapReduce framework depends upon the slowest running reduce task. Inordinate time gap among the completion points of reduce tasks delays a job significantly. Synchronization in reduce task completion not only completes a job faster but also increases resource utilization. Completion time of reduce tasks depends mainly upon the data load given to each of them. Partitioning of keys plays a major role in load balancing input data to the reduce tasks. Range partitioning using sampling technique has been proposed in the literature over hash based partitioning to provide better key distribution. But data sampling is also susceptible to data/partitioning skew since only a small portion of the actual data is scanned. It is very difficult to design a perfect load balancing partitioner without having prior information about the entire data. Chisel, allows data skew to occur during partitioning but handles it dynamically by creating multiple partial reducers and one global reducer for the skewed partition. But this technique suffers from the global reducer becoming a bottleneck when the amount of reducer output is huge. We propose an efficient range partitioning technique which eliminates the use of global reducer and yields better performance. We also discuss various heuristics to implement range partitioning. Chisel++ achieved 2 times improvement in terms of job completion time over Chisel in our experiments.