A Theory of Auto-Scaling for Resource Reservation in Cloud Services

Konstantinos Psychas, Javad GhaderiarXiv 2020 · OpenReview

Introduction

Cloud computing providers manage massive distributed server systems where each node has finite capacities across multiple dimensions, such as CPU, memory, and disk space. As jobs arrive, providers must decide whether to admit them and where to place them to maximize total reward—a value representing service priority or price paid. This challenge is essentially a Multi-dimensional Online Knapsack Problem, complicated by the fact that traffic rates are often unknown and demand is highly volatile.

Traditional approaches often rely on "dedicated hosting," where specific resources are siloed for specific applications. However, this misses the efficiency gains of "consolidation"—packing diverse VM types onto the same hardware to maximize utilization. This paper introduces the Dynamic Reservation Algorithm (DRA), a method that achieves near-optimal performance by intelligently auto-scaling server configurations without requiring prior knowledge of traffic statistics.

The Algorithmic Framework

The researchers propose a two-step framework to handle the complexity of real-time resource allocation. The foundation is the Greedy Placement Algorithm (GPA), designed for static scenarios where demand is known.

The Greedy Placement Algorithm (GPA) pseudocode, which iteratively selects configurations to maximize reward.

As shown in the pseudocode above, GPA iteratively selects VM configurations that yield the highest reward and packs them until resources are exhausted. While simple, this greedy approach proves remarkably robust in large-scale systems.

From Static to Dynamic: The DRA

The Dynamic Reservation Algorithm (DRA) extends this logic to the online setting. It tracks the GPA solution in real-time by classifying servers into different ranks. This classification allows the system to distinguish between "Accept Groups" (servers with desirable configurations) and "Reject Groups" (servers being phased out to be repurposed).

Visualization of server ranking and slot reservation, showing how jobs are packed across different server ranks.

Key to DRA’s success is the Reservation Factor $g(L)$. The algorithm maintains a small buffer of empty slots for high-priority jobs. By scaling this buffer at a specific rate—$\omega(\log L)$—the system can stay ahead of demand spikes without wasting significant capacity. Furthermore, DRA employs "Smart Migration": when a slot opens in a high-rank server, it can move a job from a lower-rank server to fill it, gradually optimizing the data center's packing without mass preemptions.

Performance and Theoretical Guarantees

The authors utilized fluid limits and Lyapunov functions to prove the algorithm's stability and efficiency as the system scales. Their theoretical analysis shows that DRA achieves at least 1/2 of the optimal expected reward. Under a "monotone greedy property" (where rewards align with resource consumption), this guarantee improves to $1 - 1/e$ (~63.2%).

Practical evaluations using the Google Cluster Dataset (Borg) and synthetic Google Cloud-style traffic profiles demonstrated even stronger results:

  • Efficiency: DRA achieved approximately 97% of the optimal reward on average in realistic simulations.
  • Robustness: It significantly outperformed standard load-balancing baselines like "Power-of-d-choices," particularly during extreme demand spikes.
  • Compatibility: The algorithm integrates seamlessly with existing cluster management features, such as job preemption, allowing it to reach nearly the theoretical upper bound of performance during peak loads.

Conclusion

By combining a greedy packing logic with a dynamic reservation buffer, DRA provides a scalable solution for cloud resource management. It eliminates the need for precise traffic forecasting while maintaining high utilization and protecting high-priority services. Future work aims to extend this theory to heterogeneous environments where servers possess different hardware generations and specialized accelerators.

Summary updated

Abstract

We consider a distributed server system consisting of a large number of servers, each with limited capacity on multiple resources (CPU, memory, disk, etc.). Jobs with different rewards arrive over time and require certain amounts of resources for the duration of their service. When a job arrives, the system must decide whether to admit it or reject it, and if admitted, in which server to schedule the job. The objective is to maximize the expected total reward received by the system. This problem is motivated by control of cloud computing clusters, in which, jobs are requests for Virtual Machines or Containers that reserve resources for various services, and rewards represent service priority of requests or price paid per time unit of service by clients. We study this problem in an asymptotic regime where the number of servers and jobs' arrival rates scale by a factor $L$, as $L$ becomes large. We propose a resource reservation policy that asymptotically achieves at least $1/2$, and under certain monotone property on jobs' rewards and resources, at least $1-1/e$ of the optimal expected reward. The policy automatically scales the number of VM slots for each job type as the demand changes, and decides in which servers the slots should be created in advance, without the knowledge of traffic rates. It effectively tracks a low-complexity greedy packing of existing jobs in the system while maintaining only a small number, $g(L)=\omega(\log L)$, of reserved VM slots for high priority jobs that pack well.
BibTeX
@misc{psychas2020theory,
  author = {Konstantinos Psychas and Javad Ghaderi},
  title = {{A Theory of Auto-Scaling for Resource Reservation in Cloud Services}},
  year = {2020},
  eprint = {2005.13744},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.13744},
}
Figure