Meeting deadlines for approximation processing in MapReduce environments

Ming-hao HU; Chang-jian WANG; Yu-xing PENG

doi:10.1631/FITEE.1601056

Your Location：

Home >

Browse articles >

Meeting deadlines for approximation processing in MapReduce environments

Regular Papers | Updated：2022-05-19

- Meeting deadlines for approximation processing in MapReduce environments
- 满足MapReduce环境下近似处理的时限要求
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 11, Pages: 1754-1772(2017)
- Affiliations：
  
  National Laboratory for Parallel and Distributed Processing, School of Computer, National University of Defense Technology, Changsha 410073, China
- Author bio：
  
  Ming-hao HU, E-mail: minghao_hu@yeah.net
- Funds：
- DOI：10.1631/FITEE.1601056
  CLC： TP311
- Received：13 March 2016，
  
  Revised：2017-11-22，
  
  Published：2017-11
- Accepted：
Scan QR Code
Ming-hao HU, Chang-jian WANG, Yu-xing PENG. Meeting deadlines for approximation processing in MapReduce environments[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1754-1772.
DOI：

Ming-hao HU, Chang-jian WANG, Yu-xing PENG. Meeting deadlines for approximation processing in MapReduce environments[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1754-1772. DOI： 10.1631/FITEE.1601056.

摘要

为了向大数据分析提供实时结果，在现今的生产环境中满足MapReduce作业的时限要求是非常关键的。许多研究致力于解决时限要求的问题，目前存在两种代表性的方法。第一种是分配适量资源以在时限前完成整个作业，在时限紧迫或资源受限时，该方法会错过时限；另一种是在时限约束下运行预数据量的样本，该方法能满足时限但无法使数据量最大化。在本文中，我们提出一个时限-导向的任务调度方法来解决上述问题，称为"Dart"。给定具体的时限和可用资源量时，Dart使用基于历史数据和作业运行状态的迭代估计法准确预测作业完成时间。基于时间预测，Dart法采用接近-修改算法做出动态调度决策，在满足时限的情况下将可处理数据量最大化并消除掉队任务。同时Dart法可有效地避免任务失败和数据倾斜，防止其性能受影响。在包含64个虚拟机的集群上使用OpenCloud和Facebook的工作负载对Dart法进行评估。结果表明Dart法在时限紧迫和资源受限情况下能有效满足时限并将处理数据量最大化。

Abstract

To provide timely results for big data analytics

it is crucial to satisfy deadline requirements for MapReduce jobs in today's production environments. Much effort has been devoted to the problem of meeting deadlines

and typically there exist two kinds of solutions. The first is to allocate appropriate resources to complete the entire job before the specified time limit

where missed deadlines result because of tight deadline constraints or lack of resources; the second is to run a pre-constructed sample based on deadline constraints

which can satisfy the time requirement but fail to maximize the volumes of processed data. In this paper

we propose a deadline-oriented task scheduling approach

named 'Dart'

to address the above problem. Given a specified deadline and restricted resources

Dart uses an iterative estimation method

which is based on both historical data and job running status to precisely estimate the real-time job completion time. Based on the estimated time

Dart uses an approach--revise algorithm to make dynamic scheduling decisions for meeting deadlines while maximizing the amount of processed data and mitigating stragglers. Dart also efficiently handles task failures and data skew

protecting its performance from being harmed. We have validated our approach using workloads from OpenCloud and Facebook on a cluster of 64 virtual machines. The results show that Dart can not only effectively meet the deadline but also process near-maximum volumes of data even with tight deadlines and limited resources.

关键词

Keywords

references

S. Acharya , , , P. Gibbons , , , V. Poosala . . Aqua: a fast decision support system using approximate query answers . . Proc. 25th Int. Conf. on Very Large Data Bases , , 1999 . . p.754 - - 757 . . . .

S. Agarwal , , , B. Mozafari , , , A. Panda , , , 等 . . Blinkdb: queries with bounded errors and bounded response times on very large data . . Proc. 8th ACM European Conf. on Computer Systems , , 2013 . . p.29 - - 42 . . DOI: 10.1145/2465351.2465355 http://doi.org/10.1145/2465351.2465355 . .

G. Ananthanarayanan , , , S. Kandula , , , A.G. Greenberg , , , 等 . . Reining in the outliers in Map-Reduce clusters using Mantri . . Proc. 10th USENIX Symp. on Operating Systems Design and Implementation , , 2010 . . p.24 - - 38 . . . .

G. Ananthanarayanan , , , A. Ghodsi , , , S. Shenker , , , 等 . . Effective straggler mitigation: attack of the clones . . Proc. 10th USENIX Symp. on Networked Systems Design and Implementation , , 2013 . . p.185 - - 198 . . . .

G. Ananthanarayanan , , , M.C.C. Hung , , , X. Ren , , , 等 . . Grass: trimming stragglers in approximation analytics . . Proc. 11th USENIX Symp. on Networked Systems Design and Implementation , , 2014 . . p.289 - - 302 . . . .

Apache . . The Apache Hadoop Project . . http://hadoop.apache.org/ http://hadoop.apache.org/ , , 2016 . . .

D.M. Bates , , , D.G. Watts . . Nonlinear regression inference using the linear approximation . . In: Jantsch E., Waddington, C. (Eds.), Nonlinear Regression: Iterative Estimation and Linear Approximations. Wiley Online Library , , 1988 . . p.142 - - 167 . . DOI: 10.1002/9780470316757.ch2 http://doi.org/10.1002/9780470316757.ch2 . .

Laboratories Bell . . Approximate Query Processing: Taming the Terabytes . . http://www.vldb.org/conf/2001/tut4.pdf http://www.vldb.org/conf/2001/tut4.pdf , , 2001 . . .

Y. Chen , , , A. Ganapathi , , , R. Griggith , , , 等 . . The case for evaluating MapReduce performance using workload suites . . Proc. IEEE 19th Int. Symp. on Modeling, Analysis & Simulation of Computer and Telecommunication Systems , , 2011 . . DOI: 10.1109/MASCOTS.2011.12 http://doi.org/10.1109/MASCOTS.2011.12 . .

Y. Chen , , , S. Alspaugh , , , R. Katz . . Interactive analytical processing in big data systems: a cross-industry study of MapReduce workloads . . Proc. VLDB Endow. , , 2012 . . 5 ( ( 12 ): ): 1802 - - 1813 . . DOI: 10.14778/2367502.2367519 http://doi.org/10.14778/2367502.2367519 . .

M. Chowdhury , , , M. Zaharia , , , J. Ma , , , 等 . . Managing data transfers in computer clusters with orchestra . . SIGCOMM Comput. Commun. Rev. , , 2011 . . 41 ( ( 4 ): ): 98 - - 109 . . DOI: 10.1145/2043164.2018448 http://doi.org/10.1145/2043164.2018448 . .

M. Chowdhury , , , Y. Zhong , , , I. Stoica . . Efficient coflow scheduling with varys . . SIGCOMM Comput. Commun. Rev. , , 2014 . . 44 ( ( 4 ): ): 443 - - 454 . . DOI: 10.1145/2740070.2626315 http://doi.org/10.1145/2740070.2626315 . .

Cloudera . . Statistical Workload Injector for MapReduce . . https://github.com/SWIMProjectUCB/SWIM https://github.com/SWIMProjectUCB/SWIM , , 2013 . . .

J. Dean , , , S. Ghemawat . . MapReduce: simplified data processing on large clusters . . Commun. ACM , , 2008 . . 51 ( ( 1 ): ): 107 - - 113 . . DOI: 10.1145/1327452.1327492 http://doi.org/10.1145/1327452.1327492 . .

A.D. Ferguson , , , P. Bodik , , , S. Kandula . . Jockey: guaranteed job latency in data parallel clusters . . Proc. 7th ACM European Conf. on Computer Systems , , 2012 . . p.99 - - 112 . . DOI: 10.1145/2168836.2168847 http://doi.org/10.1145/2168836.2168847 . .

H. Herodotou , , , H. Lim , , , G. Luo . . Starfish: a self-tuning system for big data analytics . . Proc. 7th Biennial Conf. on Innovative Data Systems Research , , 2011 . . p.261 - - 272 . . . .

M. Hu , , , C. Wang , , , P. You , , , 等 . . Deadline-oriented task scheduling for mapreduce environments . . LNCS , , 2015 . . 9529 359 - - 372 . . DOI: 10.1007/978-3-319-27122-4\_25 http://doi.org/10.1007/978-3-319-27122-4\_25 . .

K. Kc , , , K. Anyanwu . . Scheduling Hadoop jobs to meet deadlines . . IEEE 2nd Int. Conf. on Cloud Computing Technology and Science , , 2010 . . p.388 - - 392 . . DOI: 10.1109/CloudCom.2010.97 http://doi.org/10.1109/CloudCom.2010.97 . .

S. Li , , , S. Hu , , , S. Wang , , , 等 . . Woha: deadline-aware Map-Reduce workflow scheduling framework over Hadoop clusters . . IEEE 34th Int. Conf. on Distributed Computing Systems , , 2014 . . p.93 - - 103 . . DOI: 10.1109/ICDCS.2014.18 http://doi.org/10.1109/ICDCS.2014.18 . .

J. Liu , , , K. Shih , , , W. Lin , , , 等 . . Imprecise computations . . Proc. IEEE , , 1994 . . 82 83 - - 94 . . DOI: 10.1109/5.259428 http://doi.org/10.1109/5.259428 . .

S. Lohr . . Simple probability samples . . In: Sampling: Design and Analysis. Addison-Wesley, London , , 2009 . . p.35 - - 67 . . . .

D.W. Marquardt . . An algorithm for least-squares estimation of nonlinear parameters . . J. Soc. Ind. Appl. Math. , , 1963 . . 11 ( ( 2 ): ): 431 - - 441 . . . .

K. Morton , , , M. Balazinska , , , D. Grossman . . ParaTimer: a progress indicator for MapReduce dags . . Proc. ACM SIGMOD Int. Conf. on Management of Data , , 2010a . . p.507 - - 518 . . DOI: 10.1145/1807167.1807223 http://doi.org/10.1145/1807167.1807223 . .

K. Morton , , , A. Friesen , , , M. Balazinska , , , 等 . . Estimating the progress of MapReduce pipelines . . Proc. IEEE 26th Int. Conf. on Data Engineering , , 2010b . . p.681 - - 684 . . DOI: 10.1109/ICDE.2010.5447919 http://doi.org/10.1109/ICDE.2010.5447919 . .

H.J. Motulsky , , , L.A. Ransnas . . Fitting curves to data using nonlinear regression: a practical and nonmathematical review . . FASEB J. , , 1987 . . 1 ( ( 5 ): ): 365 - - 374 . . . .

OREILLY . . Interactive Big Data Analysis Using Approximate Answers . . https://tinyurl.com/k5favda/ https://tinyurl.com/k5favda/ , , 2013 . . .

J. Polo , , , D. Carrera , , , Y. Becerra , , , 等 . . Performance-driven task co-scheduling for MapReduce environments . . Proc. IEEE Int. Congress on Network Operations and Management Symp. , , 2010 . . p.373 - - 380 . . DOI: 10.1109/NOMS.2010.5488494 http://doi.org/10.1109/NOMS.2010.5488494 . .

K. Ren , , , Y. Kwon , , , M. Balazinska , , , 等 . . Hadoop's adolescence: an analysis of Hadoop usage in scientific workloads . . Proc. VLDB Endow. , , 2013 . . 6 ( ( 10 ): ): 853 - - 864 . . DOI: 10.14778/2536206.2536213 http://doi.org/10.14778/2536206.2536213 . .

V.K. Vavilapalli , , , A.C. Murthy , , , C. Douglas , , , 等 . . Apache Hadoop Yarn: yet another resource negotiator . . Proc. 4th Annual Symp. on Cloud Computing , , 2013 . . p.5:1 - - 5:16 . . DOI: 10.1145/2523616.2523633 http://doi.org/10.1145/2523616.2523633 . .

S. Venkataraman , , , A. Panda , , , G. Ananthanarayanan , , , 等 . . The power of choice in data-aware cluster scheduling . . Proc. 11th USENIX Symp. on Operating Systems Design and Implementation , , 2007 . . p.301 - - 316 . . . .

A. Verma , , , L. Cherkasova , , , R.H. Campbell . . Aria: automatic resource inference and allocation for MapReduce environments . . Proc. 8th ACM Int. Conf. on Autonomic Computing , , 2011 . . p.235 - - 244 . . DOI: 10.1145/1998582.1998637 http://doi.org/10.1145/1998582.1998637 . .

A. Verma , , , L. Cherkasova , , , V.S. Kumar , , , 等 . . Deadline-based workload management for MapReduce environments: pieces of the performance puzzle . . Proc. IEEE Int. Congress on Network Operations and Management Symp. , , 2012 . . p.900 - - 905 . . DOI: 10.1109/NOMS.2012.6212006 http://doi.org/10.1109/NOMS.2012.6212006 . .

C. Wang , , , Y. Peng , , , M. Tang , , , 等 . . MapCheckReduce: an improved MapReduce computing model for imprecise applications . . Proc. IEEE Int. Congress on Big Data , , 2014 . . p.366 - - 373 . . DOI: 10.1109/BigData.Congress.2014.61 http://doi.org/10.1109/BigData.Congress.2014.61 . .

X. Wang , , , D. Shen , , , M. Bai , , , 等 . . SAMES: deadline-constraint scheduling in MapReduce . . Front. Comput. Sci. , , 2015 . . 9 ( ( 1 ): ): 128 - - 141 . . DOI: 10.1007/s11704-014-4138-y http://doi.org/10.1007/s11704-014-4138-y . .

N. Zacheilas , , , V. Kalogeraki . . Real-time scheduling of skewed MapReduce jobs in heterogeneous environments . . Proc. 11th Int. Conf. on Autonomic Computing , , 2014 . . p.189 - - 200 . . . .

M. Zaharia , , , A. Konwinski , , , A.D. Joseph , , , 等 . . Improving MapReduce performance in heterogeneous environments . . Proc. 8th USENIX Symp. on Operating Systems Design and Implementation , , 2008 . . p.7 - - 21 . . . .

M. Zaharia , , , D. Borthakur , , , S. Sen , , , 等 . . Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling . . Proc. 5th European Conf. on Computer Systems , , 2010 . . p.265 - - 278 . . DOI: 10.1145/1755913.1755940 http://doi.org/10.1145/1755913.1755940 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

XIRAC: an optimized product-oriented near-real-time operating system with unlimited tasks and an innovative programming paradigm based on the maximum entropy method

A multi-agent collaboration scheme for energy-efficient task scheduling in a 3D UAV-MEC space

A non-group parallel frequent pattern mining algorithm based on conditional patterns

Energy-aware scheduling with reconstruction and frequency equalization on heterogeneous systems*

Related Author

Alireza ZIRAK

Yang LI

Ziling WEI

Jinshu SU

Baokang ZHAO

Zhe-jun KUANG

Hang ZHOU

Dong-dai ZHOU

Related Institution

Photonics and Quantum Technologies Research School, Nuclear Science and Technology Research Institute

College of Computer, National University of Defense Technology

Academy of Military Sciences

College of Computer Science and Technology, Changchun University

School of Economics, Changchun University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰