TL;DR
Cloud providers struggle to efficiently admit new workloads to clusters, often leading to underutilization due to conservative admission policies. This paper proposes sophisticated admission policies that leverage probabilistic information about workload behavior, significantly improving cluster utilization and potentially saving billions of dollars annually.
What Problem Does This Paper Address?
Cloud computing relies on efficiently matching incoming workloads (deployments) to available cluster resources. A major challenge arises from the dynamic nature of these workloads: they can unpredictably scale their resource demands up or down. Cloud providers must decide whether to admit a new deployment, knowing that doing so might prevent existing deployments from scaling later, thus violating service level agreements (SLAs). Current practices often involve overly conservative "threshold policies" that reserve large portions of clusters, leading to low average utilization. This paper tackles the "cluster admission problem" by developing smarter ways to decide which deployments to admit, aiming to maximize resource utilization while respecting SLAs.
Methods
The authors formalize the cluster admission problem as a constrained Partially Observable Markov Decision Process (POMDP). Since optimally solving this is infeasible, they develop heuristic policies based on simplifying assumptions. The core idea is to move beyond simple utilization thresholds and instead use probabilistic estimates of future workload behavior.
- Zeroth Moment Policy (Baseline): This is the standard, myopic policy that only considers the current number of active cores against a fixed threshold.
- First Moment Policy: This policy uses the expected future resource usage (the first moment) of deployments to make admission decisions. It leverages Markov's Inequality to bound the probability of exceeding capacity.
- Second Moment Policy: This policy further improves upon the first by incorporating the variance of future resource usage (the second moment), using Cantelli's inequality for a tighter bound on failure probability.
- Marginal Heuristic: A modification to the moment policies that allows accepting "marginal" deployments (those with very low expected future impact) even if they slightly push the system towards an unsafe state, especially when prior information is limited.
- Information Elicitation Mechanism: A variance-based payment rule designed to incentivize users to provide more accurate information about their deployment types, thereby improving the provider's prior knowledge.
Datasets
The authors use a real-world data trace from Microsoft Azure (Cortez et al., 2017) containing one month of internal job data. This dataset, comprising 35,576 deployments, is used to fit the parameters of their probabilistic models for deployment behavior. They then use these fitted models to simulate longer time periods (3 years) to evaluate their proposed policies.
Key Insights and Ideas
- Beyond Simple Thresholds: Simple utilization thresholds are suboptimal because they ignore the type of workload and its potential for future scaling. A few large, dynamic workloads can have a disproportionately large impact on cluster capacity.
- Probabilistic Forecasting is Key: Using expected future resource usage (first moment) and even variance (second moment) of deployments significantly improves admission decisions compared to static thresholds.
- Prior Information is Crucial: The performance of admission policies dramatically improves with better prior information about arriving deployments. Even a few observations can lead to substantial gains.
- Incentivizing Information Sharing: A variance-based pricing mechanism can effectively incentivize users to reveal information about their deployment types, leading to better cluster utilization.
Key Results
- The proposed First Moment Policy achieved a 15.74 percentage point increase in average cluster utilization (from 50.45% to 66.19%) compared to the baseline "Zeroth Moment Policy."
- The Second Moment Policy further improved utilization to 67.32%, a 33.44% relative improvement over the baseline.
- With prior information equivalent to just 1 observation, utilization jumped to 75% (First Moment) and 79.5% (Second Moment).
- With 50 observations, the Second Moment Policy reached 83.8% utilization, achieving over 90% of a theoretical upper bound.
- The variance-based payment rule, combined with user-declared types, showed a sizable increase in utilization (e.g., 77% vs. 83% in one simulation).
Limitations and Future Work
- Infeasibility of Optimal POMDP Solution: The authors acknowledge that finding the truly optimal policy for the full POMDP is computationally infeasible due to the large state space and complex dynamics.
- Simplifying Assumptions: The tractability of their policies relies on assumptions like "no future arrivals" and "at most one event per timestep," which are approximations.
- Data Limitations: The Azure dataset, while valuable, is limited to one month and specific to Microsoft's internal workloads, potentially limiting the generalizability of the fitted models.
- Future Work:
- Investigating cluster selection policies (i.e., which cluster to assign a deployment to, not just whether to admit it).
- Modeling more complex deployment life cycles beyond simple stochastic processes.
- Exploring alternative economic designs, such as offering deployments with guaranteed vs. best-effort scaling.
- Further research into mechanism design for eliciting information, considering competitive effects and different pricing strategies.
Summary updated