Online Social Welfare Maximization with Spatio-Temporal Resource Mesh for Serverless

Hailiang Zhao, Shuiguang Deng, Zhengzhe Xiang, Jianwei YinarXiv 2021 · arXiv · OpenReview

Abstract

Multi-server jobs are imperative in modern computing clusters. A multi-server job has multiple task components and each of the task components is responsible for processing a specific size of workloads. Efficient online workload dispatching is crucial but challenging to co-located heterogeneous multi-server jobs. The dispatching policy should decide $(i)$ where to launch each task component instance of the arrived jobs and $(ii)$ the size of workloads that each task component processes. Existing policies are explicit and effective when facing service locality and resource contention in both offline and online settings. However, when adding the deadline-aware constraint, the theoretical superiority of these policies could not be guaranteed. To fill the theoretical gap, in this paper, we design an $\alpha$-competitive online workload dispatching policy for deadline-aware multi-server jobs based on the spatio-temporal resource mesh model. We formulate the problem as a social welfare maximization program and solve it online with several well designed pseudo functions. The social welfare is formulated as the sum of the utilities of jobs and the utility of the computing cluster. The proposed policy is rigorously proved to be $\alpha$-competitive for some $\alpha \geq 2$. We also validate the theoretical superiority of it with simulations and the results show that it distinctly outperforms two handcrafted baseline policies on the social welfare.

Introduction

In modern data centers, jobs are rarely "one-size-fits-all." A single job, such as training a large neural network, often requires multiple "task components" (workers) running across different servers simultaneously. Managing these is a complex challenge due to service locality (tasks requiring specific hardware like GPUs), resource contention among co-located jobs, and strict deadlines. Unlike standard batch jobs, these often have a "drop-dead" time; if the training isn't finished by then, the utility of the job plummets.

While many algorithms handle contention or locality, adding strict deadlines in an online setting—where future job arrivals are unknown—usually breaks theoretical performance guarantees. This paper introduces ONSOCMAX, a novel online algorithm that fills this gap, moving beyond "best-effort" heuristics to a mathematically grounded framework with a proven $\alpha$-competitive ratio.

Methodology: The Spatio-Temporal Resource Mesh

The core innovation of ONSOCMAX is the Spatio-Temporal Resource Mesh. Instead of viewing the cluster as a static list of servers, the authors divide the environment into a grid of "resource units" defined by both a physical node and a specific time slot. This allows the algorithm to "reserve" future capacity across both space and time.

Spatio-temporal resource mesh illustrating job allocation across nodes and time slots.

Social Welfare and Marginal Cost Pricing

The objective is to maximize social welfare, defined as the sum of "Job Utility" (how satisfied the user is with the processed workload) and "Cluster Utility" (how efficiently the system uses its resources). To make decisions online, the algorithm uses a "pseudo-social welfare function" that treats resource allocation as an economic problem. It assigns a "cost" to using a resource unit based on how full that unit already is. As a node nears capacity, the cost rises exponentially, effectively "saving" space for high-value jobs that might arrive later.

The ONSOCMAX Algorithm

When a new multi-server job arrives, the algorithm receives a quadruple representing its requirements and utility function. It then calculates a near-optimal solution for workload dispatching and updates the resource mesh utilization in parallel.

Algorithm 1: ONSOCMAX for online workload dispatching.

To solve the complex optimization problem for each arriving job quickly, the authors employ an iterative solver based on the Augmented Lagrangian Method, which handles constraints like deadlines and capacity efficiently in polynomial time.

Evaluation and Key Results

The paper evaluates the algorithm using a simulated heterogeneous cluster environment consisting of 10 nodes over a 24-hour horizon. Job arrivals were modeled using a Poisson distribution, and service durations followed an exponential distribution to simulate real-world variance.

Performance Highlights

  • Superior Social Welfare: In simulations, ONSOCMAX consistently outperformed two common baselines: MAX-FIRST (a myopic "greedy" approach) and EQUAL-SHARE (a naive fairness approach).
  • Theoretical Robustness: The authors prove that ONSOCMAX is $\alpha$-competitive (where $\alpha \ge 2$). In the world of online algorithms, this is a "gold standard" result, meaning that regardless of the job arrival pattern, the algorithm will never perform worse than $1/\alpha$ of the best possible offline schedule.
  • Versatility: The algorithm maintained its lead across varying levels of cluster congestion and different job utility models (linear, logarithmic, and polynomial).

Discussion and Future Work

While ONSOCMAX provides a strong theoretical foundation, some practical limitations remain. The current model assumes that adding more workers always speeds up a job, ignoring the "communication bottleneck" where network synchronization overhead can eventually slow down distributed training. Additionally, the algorithm relies on accurate profiling of node capacities and job requirements. Future work could extend this to complex "Directed Acyclic Graph" (DAG) workflows where tasks have strict sequential dependencies rather than being largely independent components.

Summary updated

Abstract

Multi-server jobs are imperative in modern computing clusters. A multi-server job has multiple task components and each of the task components is responsible for processing a specific size of workloads. Efficient online workload dispatching is crucial but challenging to co-located heterogeneous multi-server jobs. The dispatching policy should decide $(i)$ where to launch each task component instance of the arrived jobs and $(ii)$ the size of workloads that each task component processes. Existing policies are explicit and effective when facing service locality and resource contention in both offline and online settings. However, when adding the deadline-aware constraint, the theoretical superiority of these policies could not be guaranteed. To fill the theoretical gap, in this paper, we design an $\alpha$-competitive online workload dispatching policy for deadline-aware multi-server jobs based on the spatio-temporal resource mesh model. We formulate the problem as a social welfare maximization program and solve it online with several well designed pseudo functions. The social welfare is formulated as the sum of the utilities of jobs and the utility of the computing cluster. The proposed policy is rigorously proved to be $\alpha$-competitive for some $\alpha \geq 2$. We also validate the theoretical superiority of it with simulations and the results show that it distinctly outperforms two handcrafted baseline policies on the social welfare.
BibTeX
@misc{zhao2021online,
  author = {Hailiang Zhao and Shuiguang Deng and Zhengzhe Xiang and Jianwei Yin},
  title = {{Online Social Welfare Maximization with Spatio-Temporal Resource Mesh for Serverless}},
  year = {2021},
  eprint = {2112.02456},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.02456},
}
Figure