article

SAMES: deadline-constraint scheduling in MapReduce

Authors:

Ge YuAuthors Info & Claims

Frontiers of Computer Science: Selected Publications from Chinese Universities, Volume 9, Issue 1

Pages 128 - 141

https://doi.org/10.1007/s11704-014-4138-y

Published: 01 February 2015 Publication History

Abstract

MapReduce is a popular parallel data-processing system, and task scheduling is one of the kernel techniques in MapReduce. In many applications, users have requirements that their MapReduce jobs should be completed before specific deadlines. Hence, in this paper, a novel scheduling algorithm based on the most effective sequence (SAMES) is proposed for deadline-constraint jobs in MapReduce. First, according to the characteristics of MapReduce, we propose a novel sequence-based execution strategy for MapReduce jobs and a new concept, the effective sequence (ES). Then, we design some efficient approaches for finding ESes and choose the most effective sequence (MES) for job execution. We also propose methods for MES-updates and exception handling. Finally, we verify the effectiveness of SAMES through experiments. The experimental results show that SAMES is an efficient scheduling algorithm for deadline-constraint jobs in MapReduce.

References

[1]

Dean J, Ghemawat S. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 2008, 51(1): 107---113

Digital Library

[2]

Jiang D, Ooi B C, Shi L, Wu S. The performance of mapreduce: an in-depth study. Proceedings of the VLDB Endowment, 2010, 3(1---2): 472---483

Digital Library

[3]

Polo J, Carrera D, Becerra Y, Torres J. Performance-driven task coscheduling for mapreduce environments. In: Proceedings of the Network Operations and Managment Symposium (NOMS). 2010, 373---380

[4]

Kc K, Anyanwu K. Scheduling hadoop jobs to meet deadlines. In: Proceedings of 2010 IEEE Second International Conference on Cloud Computing Technology and Science (CloudCom). 2010, 388---392

Digital Library

[5]

Verma A, Cherkasova L, Kumar V S, Campbell R H. Deadline-based workload management for mapreduce environments: pieces of the performance puzzle. In: Proceedings of the Network Operations andManagment Symposium (NOMS). 2012, 900---905

[6]

Sandholm T, Lai K. Dynamic proportional share scheduling in hadoop. In: Proceedings of the Job Scheduling Strategies for Parallel Processing. Berlin: Springer, 2010, 110---131

[7]

Schwarzkopf M, Konwinski A, Abd-El-Malek M, Wilkes J. Omega: flexible, scalable schedulers for large compute clusters. In: Proceedings of the 8th ACM European Conference on Computer Systems, ACM. 2013, 351---364

[8]

Wolf J, Balmin A, Rajan D, Hildrum K, Khandekar R, Parekh S, Wu K L, Vernica R. Circumflex: a scheduling optimizer for mapreduce workloads with shared scans. SIGOPS, 2012, 46(1): 26---32

Digital Library

[9]

Morton K, Balazinska M, Grossman D. Paratimer: a progress indicator for mapreduce dags. In: SIGMOD Conference'10. 2010, 507---518

[10]

Condie T, Conway N, Alvaro P, Hellerstein J M. Mapreduce online. In: Proceedings of NSDI. 2010, 313---328

[11]

Zaharia M, Elmeleegy K, Borthakur D, Shenker S, Sen Sarma J, Stoica I. Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling. In: Proceedings of EuroSys, ACM. 2010, 265---278

Digital Library

[12]

Zaharia M, Konwinski A, Joseph A D, Katz R, Stoica I. Improving mapreduce performance in heterogeneous environments. In: Proceedings of OSDI. 2008, 29---42

[13]

Verma A, Cherkasova L, Campbell R H. Aria: automatic resource inference and allocation for mapreduce environments. In: Proceedings of the 8th ACM International Conference on Autonomic Computing, ACM. 2011, 235---244

[14]

Dou A, Kalogeraki V, Gunopulos D, Mielikainen T, Tuulos V H. Misco: a mapreduce framework for mobile systems. In: Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments, ACM. 2010, 32---39

[15]

Dou A J, Kalogeraki V, Gunopulos D, Mielikainen T, Tuulos V H. Scheduling for real-time mobile mapreduce systems. In: Proceedings of the 5th ACM International Conference on Distributed Event-based System. 2011, 347---358

Cited By

Hedayati SMaleki NOlsson TAhlgren FSeyednezhad MBerahmand K(2023)MapReduce scheduling algorithms in Hadoop: a systematic studyJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00520-912:1Online publication date: 10-Oct-2023
https://dl.acm.org/doi/10.1186/s13677-023-00520-9
Qiu GJiang LZhang Y(2020)MQWAGSProceedings of the 2020 4th High Performance Computing and Cluster Technologies Conference & 2020 3rd International Conference on Big Data and Artificial Intelligence10.1145/3409501.3409515(42-48)Online publication date: 3-Jul-2020
https://dl.acm.org/doi/10.1145/3409501.3409515
Qiu GGao YZhang Y(2020)Research on Job Scheduling Algorithms Based on Cloud ComputingGreen, Pervasive, and Cloud Computing10.1007/978-3-030-64243-3_36(481-495)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64243-3_36
Show More Cited By

Index Terms

SAMES: deadline-constraint scheduling in MapReduce
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Index terms have been assigned to the content through auto-classification.

Recommendations

Preemptive Hadoop Jobs Scheduling under a Deadline
SKG '12: Proceedings of the 2012 Eighth International Conference on Semantics, Knowledge and Grids

MapReduce has become the dominant programming model in a cloud-based data processing environment, such as Hadoop. First In First Out (FIFO) is the default job scheduling policy of Hadoop, but it cannot guarantee that the job will be completed by a ...
Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines

We present a polynomial time algorithm for constructing an optimal schedule, if a feasible schedule exists, for tthe following multimachine scheduling problem. There are n unit-time jobs, with arbitrary release times and deadlines, and m identical ...
An efficient MapReduce scheduling scheme for processing large multimedia data

In this paper, we propose a scheduling scheme to minimize the deadline miss of jobs to which deadlines are assigned when processing large multimedia data such as video and image in MapReduce frameworks. The proposed scheme checks the satisfaction of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Frontiers of Computer Science: Selected Publications from Chinese Universities

Frontiers of Computer Science: Selected Publications from Chinese Universities Volume 9, Issue 1

February 2015

169 pages

ISSN:2095-2228

EISSN:2095-2236

Issue’s Table of Contents

Copyright © Copyright © 2015 Higher Education Press and Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hedayati SMaleki NOlsson TAhlgren FSeyednezhad MBerahmand K(2023)MapReduce scheduling algorithms in Hadoop: a systematic studyJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00520-912:1Online publication date: 10-Oct-2023
https://dl.acm.org/doi/10.1186/s13677-023-00520-9
Qiu GJiang LZhang Y(2020)MQWAGSProceedings of the 2020 4th High Performance Computing and Cluster Technologies Conference & 2020 3rd International Conference on Big Data and Artificial Intelligence10.1145/3409501.3409515(42-48)Online publication date: 3-Jul-2020
https://dl.acm.org/doi/10.1145/3409501.3409515
Qiu GGao YZhang Y(2020)Research on Job Scheduling Algorithms Based on Cloud ComputingGreen, Pervasive, and Cloud Computing10.1007/978-3-030-64243-3_36(481-495)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64243-3_36
Xu MAlamro SLan TSubramaniam S(2017)CRED: Cloud Right-Sizing with Execution Deadlines and Data LocalityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.272607128:12(3389-3400)Online publication date: 9-Nov-2017
https://dl.acm.org/doi/10.1109/TPDS.2017.2726071
Shi YLiu DHu JZhang J(2017)Two-Stage Job Scheduling Model Based on Revenues and ResourcesNetwork and Parallel Computing10.1007/978-3-319-68210-5_4(37-48)Online publication date: 20-Oct-2017
https://dl.acm.org/doi/10.1007/978-3-319-68210-5_4
Jin CLall A(Jim) Xu JZhang ZZhou A(2016)Distributed error estimation of functional dependencyInformation Sciences: an International Journal10.1016/j.ins.2016.01.051345:C(156-176)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.01.051

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents