Optimal Resource Allocation for Elastic and Inelastic Jobs

Benjamin Berg, Mor Harchol-Balter, Benjamin Moseley, Weina Wang, Justin Whitehouse

Introduction

Modern data centers face the challenge of managing heterogeneous workloads consisting of both elastic and inelastic jobs. Elastic jobs can parallelize linearly across any number of available servers (e.g., distributed machine learning training), while inelastic jobs are sequential and restricted to a single server (e.g., simple database queries). The primary objective for cluster schedulers is to allocate $k$ servers to a continuous stream of these jobs to minimize the mean response time.

Problem Formulation

The system is modeled as a continuous-time Markov chain where jobs arrive according to Poisson processes with rates $\lambda_I$ and $\lambda_E$ for inelastic and elastic jobs, respectively. Job sizes are exponentially distributed with means $1/\mu_I$ and $1/\mu_E$, but these sizes are unknown to the scheduler at the time of arrival. The scheduler must decide how to distribute $k$ servers among the waiting jobs. Two primary policies are considered: Elastic-First (EF), which prioritizes parallelizable work, and Inelastic-First (IF), which prioritizes sequential work.

Methodology

The authors analyze the system using a 2D-infinite Markov chain, where the state $(i, j)$ represents the number of inelastic and elastic jobs in the system.

State transition diagram for the 2D-infinite Markov chain representing the system state (i, j).

To overcome the computational difficulty of solving a 2D-infinite chain, a novel technique called Busy Period Transitions was employed. By approximating the time spent processing elastic jobs as an M/M/1 busy period and replacing it with a Coxian distribution, the authors collapsed the complex 2D chain into a solvable 1D-infinite chain, allowing for exact analysis via Matrix-Analytic methods.

The Inelastic-First (IF) policy gives preemptive priority to inelastic jobs. Under IF, if there are $i$ inelastic jobs, they occupy $\min(i, k)$ servers. Any remaining $k - \min(i, k)$ servers are then allocated to the elastic jobs. This behavior is captured in the system's sample path over time.

Sample path of server allocation under the Inelastic-First (IF) policy, highlighting periods where the system is saturated.

Key Insights and Results

The core contribution of this work is the proof of optimality for the IF policy. Using a sample path argument and stochastic dominance, the authors demonstrate that IF minimizes the remaining work in the system compared to any other non-idling, first-come-first-serve policy, provided that elastic jobs are larger on average than inelastic jobs ($\mu_I \ge \mu_E$).

This result is somewhat counterintuitive, as one might expect prioritizing highly parallelizable jobs to be more efficient. However, prioritizing inelastic jobs ensures that all servers remain saturated for longer periods, maximizing overall throughput. This condition ($\mu_I \ge \mu_E$) aligns with real-world data center workloads where distributed training tasks (elastic) are typically much larger than individual inference requests (inelastic).

Conversely, the study shows that if elastic jobs are smaller on average ($\mu_I < \mu_E$), the Elastic-First (EF) policy can outperform IF. The performance gap between these policies widens significantly as the system load increases. The analytical model developed was highly accurate, matching simulation results within a 1% error margin.

Conclusion and Future Work

This research provides a rigorous mathematical foundation for scheduling mixed workloads in data centers. While the IF policy is optimal for the most common scenarios, the model's assumptions—such as perfect linear speedup and exponential job size distributions—present opportunities for future refinement. Future work could explore optimal policies for regimes where elastic jobs are smaller or investigate the impact of bounded elasticity and heavy-tailed job size distributions.

Summary updated

Abstract

Modern data centers are tasked with processing heterogeneous workloads consisting of various classes of jobs. These classes differ in their arrival rates, size distributions, and job parallelizability. With respect to paralellizability, some jobs are elastic, meaning they can parallelize linearly across many servers. Other jobs are inelastic, meaning they can only run on a single server. Although job classes can differ drastically, they are typically forced to share a single cluster. When sharing a cluster among heterogeneous jobs, one must decide how to allocate servers to each job at every moment in time. In this paper, we design and analyze allocation policies which aim to minimize the mean response time across jobs, where a job's response time is the time from when it arrives until it completes. We model this problem in a stochastic setting where each job may be elastic or inelastic. Job sizes are drawn from exponential distributions, but are unknown to the system. We show that, in the common case where elastic jobs are larger on average than inelastic jobs, the optimal allocation policy is Inelastic-First, giving inelastic jobs preemptive priority over elastic jobs. We obtain this result by introducing a novel sample path argument. We also show that there exist cases where Elastic-First (giving priority to elastic jobs) performs better than Inelastic-First. We then provide the first analysis of mean response time under both Elastic-First and Inelastic-First by leveraging recent techniques for solving high-dimensional Markov chains.
BibTeX
@inproceedings{berg2020optimal,
  author = {Benjamin Berg and Mor Harchol-Balter and Benjamin Moseley and Weina Wang and Justin Whitehouse},
  title = {{Optimal Resource Allocation for Elastic and Inelastic Jobs}},
  booktitle = {SPAA},
  year = {2020},
  doi = {10.1145/3350755.3400265},
}
Figure