Scheduling MapReduce Jobs on Unrelated Processors

Dimitris Fotakis, Ioannis Milis, Emmanouil Zampetakis, Georgios Zois

Abstract

This paper addresses the complex challenge of scheduling MapReduce jobs in heterogeneous computing environments. By modeling the problem as a generalized Flexible Flow Shop (FFS) on unrelated processors and explicitly accounting for the data shuffle phase, the authors derive the first constant-approximation algorithms for minimizing total weighted completion time. The proposed algorithms provide theoretical guarantees within factors of 54 to 81 of the optimal schedule, representing a significant advancement in the theoretical understanding of big data orchestration.

1. Introduction

In modern data centers, MapReduce serves as a fundamental framework for parallel processing. However, the efficiency of these systems is heavily dependent on task scheduling. Most existing theoretical models simplify the problem by assuming identical processors or by ignoring the "Data Shuffle" phase—the period where intermediate data is transferred across the network from Map tasks to Reduce tasks.

This research introduces a more realistic model using "unrelated processors," where the processing time of a task depends specifically on the machine it is assigned to. This model effectively captures data locality: a task runs faster on a machine where its input data already resides. The authors focus on minimizing the total weighted completion time, a metric that prioritizes finishing high-importance jobs quickly.

2. Problem Formulation

The authors generalize the Flexible Flow Shop (FFS) problem to fit the MapReduce paradigm. A job $j$ consists of a set of Map tasks and a set of Reduce tasks. All Map tasks must complete before any Reduce tasks can begin. The environment consists of unrelated processors, meaning the time $p_{i,k,j}$ to process task $k$ of job $j$ on processor $i$ is arbitrary.

Crucially, the model incorporates the Data Shuffle phase. The authors analyze two variants:

  1. Co-located Shuffle: Shuffle and Reduce tasks occur on the same processor.
  2. General Shuffle: Shuffle tasks can occur on different processors than their corresponding Reduce tasks.

3. Methodology

The proposed solution utilizes a multi-stage algorithmic framework based on Linear Programming (LP) relaxations.

3.1 Interval-Indexed LP Relaxation

To handle the complexity of continuous time, the authors discretize the schedule into logarithmic time intervals. They formulate an LP that allows for "fractional" task completion, providing a mathematical lower bound for the optimal completion time.

3.2 TaskScheduling(b) and MRS Algorithms

The TaskScheduling(b) algorithm rounds the fractional LP results into a feasible schedule for a single stage (either Map or Reduce). To synchronize these stages, the authors introduce the Map-Reduce Scheduling (MRS) algorithm. MRS uses a calculated "width" ($\omega_j$) for each job, acting as a buffer to ensure that the precedence constraints (Maps finishing before Reduces) are respected without causing excessive idle time on the processors.

3.3 Modeling the Shuffle

The shuffle phase is treated as an additional set of tasks. By integrating these into the flow shop model, the authors ensure the algorithm accounts for the network and I/O bottlenecks that often dominate real-world MapReduce performance.

4. Theoretical Results

The primary contribution of this work is the derivation of the first constant approximation ratios for MapReduce scheduling on unrelated processors. While these ratios are theoretical upper bounds, they guarantee that the algorithm's performance will never deviate from the optimum by more than a fixed factor, regardless of the input size or job complexity.

  • 54-Approximation: Achieved for the standard Map-Reduce model with multiple tasks per job and for the co-located Map-Shuffle-Reduce model.
  • 81-Approximation: Achieved for the most general case where Shuffle tasks are independent of Reduce task placement.

5. Discussion and Future Work

This work bridges the gap between simplistic theoretical models and the messy reality of data center scheduling. By using the unrelated processors model, the authors provide a mathematical language for data locality.

While the approximation constants (54 and 81) may appear high for practical implementation, they represent a major breakthrough in computational complexity, moving the problem from "unknown" to "constant-factor" solvable. Future research directions include extending these offline algorithms to "online" settings where jobs arrive dynamically, and exploring "preemption-restart" models to better reflect how modern clusters handle task interruptions.

Summary updated

BibTeX
@inproceedings{fotakis2015scheduling,
  author = {Dimitris Fotakis and Ioannis Milis and Emmanouil Zampetakis and Georgios Zois},
  title = {{Scheduling MapReduce Jobs on Unrelated Processors}},
  booktitle = {SEA},
  year = {2015},
  doi = {10.1007/978-3-319-20086-6\_11},
}
Figure