Joint scheduling of MapReduce jobs with servers: Performance bounds and experiments

Xiao Ling, Yi Yuan, Dan Wang, Jiangchuan Liu, Jiahai Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

Published by Elsevier Inc. MapReduce-like frameworks have achieved tremendous success for large-scale data processing in data centers. A key feature distinguishing MapReduce from previous parallel models is that it interleaves parallel and sequential computation. Past schemes, and especially their theoretical bounds, on general parallel models are therefore, unlikely to be applied to MapReduce directly. There are many recent studies on MapReduce job and task scheduling. These studies assume that the servers are assigned in advance. In current data centers, multiple MapReduce jobs of different importance levels run together. In this paper, we investigate a schedule problem for MapReduce taking server assignment into consideration as well. We formulate a MapReduce server-job organizer problem (MSJO) and show that it is NP-complete. We develop a 3-approximation algorithm and a fast heuristic design. Moreover, we further propose a novel fine-grained practical algorithm for general MapReduce-like task scheduling problem. Finally, we evaluate our algorithms through both simulations and experiments on Amazon EC2 with an implementation with Hadoop. The results confirm the superiority of our algorithms.
Original languageEnglish
Pages (from-to)52-66
Number of pages15
JournalJournal of Parallel and Distributed Computing
Volume90-91
DOIs
Publication statusPublished - 1 Apr 2016

Keywords

  • Fast heuristic
  • MapReduce
  • NP-complete
  • Scheduling
  • Server assignment

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this