LIBRA: Lightweight Data Skew Mitigation in MapReduce

被引：77

作者：

Chen, Qi ^{[1
]}

Yao, Jinyu ^{[1
]}

Xiao, Zhen ^{[1
]}

机构：

[1] Peking Univ, Dept Comp Sci, Beijing 100871, Peoples R China

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2015年 / 26卷 / 09期

基金：

中国国家自然科学基金;

关键词：

MapReduce; data skew; sampling; partitioning;

D O I：

10.1109/TPDS.2014.2350972

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

MapReduce is an effective tool for parallel data processing. One significant issue in practical MapReduce applications is data skew: the imbalance in the amount of data assigned to each task. This causes some tasks to take much longer to finish than others and can significantly impact performance. This paper presents LIBRA, a lightweight strategy to address the data skew problemamong the reducers of MapReduce applications. Unlike previous work, LIBRA does not require any pre-run sampling of the input data or prevent the overlap between the map and the reduce stages. It uses an innovative sampling method which can achieve a highly accurate approximation to the distribution of the intermediate data by sampling only a small fraction of the intermediate data during the normal map processing. It allows the reduce tasks to start copying as soon as the chosen sample map tasks (only a small fraction of map tasks which are issued first) complete. It supports the split of large keys when application semantics permit and the total order of the output data. It considers the heterogeneity of the computing resources when balancing the load among the reduce tasks appropriately. LIBRA is applicable to a wide range of applications and is transparent to the users. We implement LIBRA in Hadoop and our experiments show that LIBRA has negligible overhead and can speed up the execution of some popular applications by

引用

页码：2520 / 2533

页数：14

共 29 条

[11]

Isard M., 2007, Operating Systems Review, V41, P59, DOI 10.1145/1272998.1273005

[12]

Kivity A., 2007, P LINUX S, V1, P225

[13]

Kwon Y., 2011, P OP CIRR SUMM

[14]

Kwon YongChul., 2010, SOCC

[15]

Kwon YongChul, 2012, P 2012 ACM SIGMOD IN, P25, DOI [10.1145/2213836.2213840, DOI 10.1145/2213836.2213840]

[16]

Lin J., 2009, P 7 WORKSH LARG SCAL, V1, P57

[17]

Mount R. P., 2004, SLACR782 DEP EN

[18]

Okcan Alper., 2011, PROC SIGMOD C, P949, DOI DOI 10.1145/1989323.1989423

[19]

Olston C., P 2008 ACM SIGMOD IN, P1099

[20]

Poosala V, 1996, PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES, P448

← 1 2 3 →