Speed Scaling on Parallel Servers With MapReduce Type Precedence Constraints

Rahul Vaze, Jayakrishnan NairIEEE/ACM Trans. Networking 2021 · OpenReview

1. Introduction

In modern distributed computing environments, frameworks like Hadoop and Spark have popularized the MapReduce paradigm to handle massive datasets. These systems partition jobs into two distinct phases: "map" tasks and "reduce" tasks. While these frameworks offer scalability, they introduce significant scheduling challenges, particularly regarding the trade-off between performance (flow time) and energy consumption. This paper investigates the problem of speed scaling on parallel servers under strict MapReduce precedence constraints, where servers can dynamically adjust their speeds to balance delay and power costs.

2. The Problem: Precedence and the "Caged Task" Dilemma

The primary constraint in a MapReduce job is that a reduce task cannot begin until all map tasks for that specific job have been completed. This creates a unique bottleneck in multi-server systems. At any given time, a system might have a massive backlog of reduce tasks that are technically in the queue but cannot be executed because they are "caged" by a single pending map task.

From an energy perspective, this is problematic. Modern servers typically follow a power consumption model of $P(s) = s^\alpha$ (where $\alpha > 1$). If an algorithm sees a large queue, it might scale up server speeds to reduce flow time. However, if most of those tasks are caged, the increased speed may be wasted on a small number of executable tasks, leading to inefficient energy use. The authors aim to design online algorithms that minimize the sum of flow time and energy costs despite these constraints.

3. Algorithmic Approaches

The authors utilize Shortest Remaining Processing Time (SRPT) as a foundational principle and evaluate their algorithms using competitive analysis. This involves comparing the performance of their online algorithms against an offline optimal scheduler (OPT) using potential functions to bound the competitive ratio.

3.1 Job-based Flow Time

To minimize the delay of entire jobs, the authors propose job-SRPT. This algorithm groups tasks by job and prioritizes the shortest cumulative jobs. By focusing on the job as a whole rather than individual tasks, the algorithm effectively bypasses the complexities of intra-job precedence. This allows the adaptation of existing multi-server SRPT proofs to the MapReduce context.

3.2 Task-based Flow Time

When the goal is to minimize the sum of delays for individual tasks, the authors propose prioritizing "free" (executable) tasks. To address mathematical dependencies on the ratio between the largest and smallest task sizes (denoted as $\beta$), they introduce a Simultaneous Processing variant. In this model, a server is permitted to process up to three specific task types simultaneously (e.g., the shortest map task and the shortest free reduce task). This theoretical "hack" ensures consistent progress in the potential function, regardless of task size disparities.

4. Key Results and Insights

The research demonstrates that simple, SRPT-based speed scaling can achieve competitive ratios that do not depend on the number of jobs or the number of servers:

  • Job-based Performance: In a batch setting (where all jobs arrive at time 0), job-SRPT achieves a competitive ratio of approximately $4(2 - 1/K)^\alpha$, where $K$ is the number of servers. This is remarkably close to bounds found in systems without any precedence constraints.
  • Task-based Performance: The basic task-based algorithm achieves a ratio scaling with $\beta$. However, the simultaneous processing refinement successfully removes this dependency, yielding a constant competitive ratio of $8 + \frac{4}{2-\alpha} + 3^\alpha$.
  • Empirical Validation: Simulations using Poisson job arrivals and exponential task sizes show that enforcing MapReduce constraints only increases the total cost by a factor of at most 5 compared to a theoretical system with no constraints.

5. Limitations and Future Work

While the theoretical bounds are strong, some limitations remain. The job-based flow time guarantee currently assumes a batch arrival setting; proving similar bounds for a fully dynamic online setting remains an open challenge. Additionally, the simultaneous processing model used to achieve size-independent bounds assumes $\alpha < 2$ and may introduce practical context-switching overheads not fully captured in the mathematical model.

6. Conclusion

This paper provides a robust theoretical framework for managing energy-efficient parallel servers under MapReduce constraints. By identifying how to handle "caged" tasks and leveraging SRPT-based scheduling, the authors show that precedence constraints do not necessarily prevent the achievement of strong competitive ratios in speed scaling environments.

Summary updated

Abstract

A multiple server setting is considered, where each server has tunable speed, and increasing the speed incurs an energy cost. Jobs arrive to a single queue, and each job has two types of sub-tasks, map and reduce, and a <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">precedence</b> constraint among them: any reduce task of a job can only be processed once all the map tasks of the job have been completed. In addition to the scheduling problem, i.e., which task to execute on which server, with tunable speed, an additional decision variable is the choice of speed for each server, so as to minimize a linear combination of the sum of the flow times of jobs/tasks and the total energy cost. The precedence constraints present new challenges for the speed scaling problem with multiple servers, namely that the number of tasks that can be executed at any time may be small but the total number of outstanding tasks might be quite large. We present simple speed scaling algorithms that are shown to have competitive ratios, that depend on the power cost function, and/or the ratio of the size of the largest task and the shortest reduce task, but not on the number of jobs, or the number of servers.
BibTeX
@article{vaze2021speed,
  author = {Rahul Vaze and Jayakrishnan Nair},
  title = {{Speed Scaling on Parallel Servers With MapReduce Type Precedence Constraints}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2021},
  url = {https://openreview.net/forum?id=9h_L1J8MoD},
}
Figure