LAVA: Lifetime-Aware VM Allocation with Learned Distributions and Adaptation to Mispredictions

LAVA: Lifetime-Aware VM Allocation with Learned Distributions and Adaptation to Mispredictions

Speakers: Jianheng Ling, Pratik Worah, Yawen Wang, Martin Maas, Kathryn S. McKinley

Conference: MLSys 2025

YouTube: https://www.youtube.com/watch?v=None

Overview

This talk introduces LAVA (Lifetime-Aware VM Allocation), a novel approach to virtual machine (VM) scheduling within large-scale cloud environments, specifically addressing the challenges faced by Google's Borg Prime scheduler. Presented by a team from Google, including Jianheng Ling and Kathryn S. McKinley, the work focuses on leveraging VM lifetime predictions to optimize resource utilization, reduce operational costs, and enhance system performance. The core problem tackled is the inefficient allocation of VMs on hosts, particularly in scenarios where the vast majority of VMs are short-lived but consume a disproportionately small fraction of total computing resources.

The significance of this research stems from the sheer scale of cloud operations, where schedulers process tens to hundreds of VM requests per second across thousands of hosts, managing tens of thousands of active jobs concurrently. Traditional scheduling approaches often treat all VMs similarly, failing to account for their diverse lifetimes. LAVA proposes a dynamic, adaptive strategy that not only predicts VM lifetimes upon arrival but also continuously re-predicts them based on observed runtime, allowing the scheduler to make more informed decisions. This adaptation to mispredictions and the strategic placement of VMs based on their expected longevity are critical for maximizing host availability, minimizing resource stranding, and reducing customer disruptions.

The motivation for LAVA draws parallels from prior work in memory allocation, where lifetime-based strategies proved effective. The key insight driving LAVA is the stark imbalance: 88% of VMs are short-lived, yet they account for only 2% of total core hours. This observation underscores the potential for significant gains by treating short-lived and long-lived VMs differently, preventing short-lived tasks from inadvertently "polluting" hosts intended for more persistent workloads. By intelligently managing VM placement, LAVA aims to improve power efficiency by enabling more hosts to enter low-power modes, enhance the availability of entire hosts for large VMs, and streamline maintenance operations.

Background

▶ Watch: Introduction to VM scheduling and objectives (0:00)

The efficient management of computing resources in hyper-scale cloud data centers is a fundamental challenge, with significant implications for cost, performance, and reliability. At the heart of this challenge lies the VM scheduling problem, where incoming VM requests must be rapidly and optimally placed onto available physical hosts. Google's internal cluster management system, Borg Prime, operates under immense pressure, handling 10-100 requests per second per pool and managing hundreds to tens of thousands of hosts, with orders of 10,000 active jobs at any given time.

The objectives of such a scheduler are multifaceted:

1. Maximize empty hosts: This is crucial for several reasons. Empty hosts can be put into low-power modes, significantly reducing electricity costs. They also improve the obtainability of large VMs that require an entire host, benefiting specific customer needs. Furthermore, having readily available empty hosts speeds up maintenance operations (e.g., kernel rollouts) and allows for flexible allocation to other demand pools.
2. Minimize stranding: This refers to the inefficient utilization of resources where, for example, a host might have CPU cycles available but be constrained on memory, or vice-versa. The goal is to equally fill all dimensions (CPU, memory, storage, network) on a host to ensure all allocated resources are useful.
3. Minimize VM disruptions: Customers prefer their VMs to remain stable. Frequent migrations or disruptions negatively impact user experience and application performance.

Traditional VM schedulers often employ bin-packing heuristics, attempting to fit as many VMs as possible onto hosts to maximize utilization. While effective in many scenarios, these approaches typically do not explicitly consider the lifetime of a VM as a primary scheduling dimension. This oversight can lead to suboptimal placements, particularly when short-lived VMs (e.g., batch jobs, ephemeral services) are co-located with long-lived VMs (e.g., persistent databases, core services). When a short-lived VM unexpectedly lives longer, or when many short-lived VMs are placed on a host, it can prevent that host from becoming empty, hindering the objectives listed above.

The inspiration for this work, as noted by co-author Kathryn S. McKinley, stems from a 2020 paper on a lifetime-based memory allocator for C. That work observed that C objects exhibit similar lifetime properties to VMs, with a significant proportion being short-lived. The goal there was to minimize huge page fragmentation by leveraging lifetime information. This prior experience motivated the application of similar principles to VM allocation.

In terms of prior work specific to VM prediction, the talk highlights a "lifetime alignment algorithm" that appeared at MLSys two years prior, which serves as a baseline for comparison. This algorithm, referred to as the LA algorithm (Microsoft version), introduced the concept of predicting VM lifetimes once at arrival and then attempting to group VMs with similar predicted lifetimes on the same machine (e.g., a "short-lived host" for short-lived VMs, a "long-lived host" for long-lived VMs). While an advancement, this one-shot prediction mechanism has a critical limitation: it does not adapt to mispredictions. If a VM predicted to be short-lived lives much longer, the host it occupies remains incorrectly classified, preventing optimal scheduling decisions for subsequent VMs. This forms the crucial gap that LAVA aims to address through its adaptive re-prediction and novel allocation strategies.

Key Findings

▶ Watch: LAVA's approach: Initial and re-prediction of VM lifetimes (1:15)

The central revelation underpinning the LAVA project is a critical imbalance in VM lifetime distribution and resource consumption within cloud data centers. The speakers highlighted that 88% of virtual machines are short-lived, yet they consume only 2% of the total core hours. This stark disparity signifies a major inefficiency in traditional, lifetime-agnostic scheduling, as the vast majority of ephemeral VMs can disrupt the optimal placement and management of the few, but resource-intensive, long-lived VMs.

Building upon this insight, the LAVA and NILAS (Non-Invasive Lifetime-Aware Scheduling) algorithms demonstrate significant improvements over the state-of-the-art LA algorithm (the Microsoft baseline):

• Simulation Results:
• NILAS achieved an 11 percentage point improvement in empty hosts compared to the baseline LA algorithm.
• LAVA further improved upon this, demonstrating a 15 percentage point improvement in empty hosts over the baseline.
• In specific scenarios, the maximum margin of improvement for empty hosts could be as high as more than 5% (presumably referring to the delta between LAVA and NILAS, or a peak performance gain in particular configurations). These percentages, while seemingly modest in isolation, represent substantial resource and cost savings when scaled across Google Cloud's global data centers.

• Production Deployment (NILAS):
• An initial version of NILAS has been running in Google Cloud's production environment for almost a year, validating its real-world effectiveness.
• It achieved a 2 to 10 percentage point improvement in empty machines, with variability depending on the specific data center characteristics.
• It also led to a 2 to 3 percentage point decrease in stranding, indicating more balanced and efficient resource utilization across host dimensions.
• Crucially, these improvements were accomplished with a very negligible resource consumption, highlighting the efficiency of the integrated prediction model.

A core technical finding is the efficacy of adaptation to mispredictions through distribution-based, conditional lifetime predictions and dynamic re-prediction. Unlike the one-shot prediction of the baseline, LAVA's continuous re-evaluation of VM lifetimes based on observed uptime allows the scheduler to correct initial errors and make more accurate, real-time decisions, significantly enhancing its robustness and effectiveness.

Furthermore, the introduction of novel algorithmic approaches beyond simple lifetime alignment proved essential. LAVA's key idea of filling gaps between long-lived VMs with much shorter-lived VMs is a significant contribution. This strategy minimizes the impact of potential mispredictions on the overall host exit time, ensuring that hosts can become empty sooner, which directly supports the primary objective of maximizing empty hosts. The successful deployment of the prediction model (a gradient boosted trees model) as part of the scheduler binary, rather than as a separate service, was also a key finding for achieving minimal latency in a critical path component.

Technical Deep Dive

▶ Watch: Limitations of the baseline (LA) algorithm (2:50)

The technical innovation of LAVA lies in its sophisticated approach to VM lifetime prediction and its integration into the scheduling process, moving beyond static, one-shot predictions to a dynamic, adaptive system.

Baseline: The LA (Lifetime Alignment) Algorithm

The talk uses a "lifetime alignment algorithm" (referred to as the LA algorithm or Microsoft's version) as its baseline. This algorithm operates on a simpler principle:

1. One-shot Prediction: When a new VM arrives, the scheduler predicts its lifetime (e.g., short-lived or long-lived) once.
2. Host Classification: Hosts are conceptually "marked" or associated with the type of VMs they predominantly house. For instance, if a long-lived VM is placed on a host, that host might be considered a "long-lived host," and subsequent long-lived VMs would preferentially be placed there. Similarly for short-lived VMs.
3. Static Grouping: The goal is to group VMs with similar predicted lifetimes on the same machine to facilitate quicker emptying of "short-lived hosts" and stable operation of "long-lived hosts."

The fundamental flaw of this approach is its lack of adaptation to mispredictions. As illustrated by the speakers, if a VM initially predicted as short-lived lives significantly longer than expected, the host it occupies remains incorrectly classified. This misprediction prevents the host from being used optimally for new, genuinely long-lived VMs, even though it now contains a de-facto long-lived VM. The host's expected empty time is pushed out, but the scheduler doesn't react, leading to inefficient resource allocation and preventing other hosts from becoming empty.

LAVA's Core Innovations: Distribution-Based Predictions and Re-prediction

LAVA addresses the limitations of the LA algorithm through two primary innovations:

1. Distribution-Based Conditional Lifetime Predictions: Instead of a single point estimate for a VM's lifetime, LAVA considers the distribution of possible lifetimes. Crucially, this prediction is conditional on the VM's observed uptime. The average remaining lifetime of a VM changes significantly as it continues to run. For example, a VM might have an initial average lifetime prediction of 0.2 days. However, if it has already been running for one day, its remaining average lifetime might jump to four days. If it runs for seven days, its remaining average lifetime could be 10 days. This dynamic understanding of lifetime is critical.
2. Dynamic Re-prediction: When a new VM arrives and the scheduler is considering potential hosts, LAVA doesn't just predict the new VM's lifetime. It also re-predicts the lifetimes of all existing VMs on the candidate hosts based on their current uptime. This allows the system to continuously correct previous mispredictions and update its understanding of the remaining lifetime of VMs already running. This "more information is known" principle is central to LAVA's adaptiveness.

Algorithm 1: NILAS (Non-Invasive Lifetime-Aware Scheduling)

NILAS is LAVA's first, more straightforward algorithm, designed to be non-invasive in its initial deployment. It primarily uses lifetime prediction as a tiebreaker or an enhanced scoring mechanism during host selection.

• Mechanism: When evaluating a host for a new VM, NILAS re-predicts the conditional lifetimes of all VMs currently on that host. If a VM previously under-predicted (e.g., predicted short-lived but still running) is found, its updated, longer conditional lifetime is factored into the host's score.
• Effect: This allows the scheduler to realize its initial "mistake" and adjust its view of the host. For example, if host 2 was marked for short-lived VMs but a VM on it lived longer, NILAS would re-predict that VM's remaining lifetime as longer. Consequently, a newly arriving long-lived VM might now be placed on host 2 (which is already "occupied" by a long-lived VM), rather than a potentially empty host 3. This conserves host 3, allowing it to become empty sooner or remain available for other purposes.
• Limitation: While NILAS significantly improves upon the baseline, it can still suffer from a cumulative effect. If the scheduler keeps adding predicted long-lived VMs to a single host, even with accurate re-predictions, the expected exit time of the entire host can be continually pushed further out. This prevents the host from ever becoming empty, which contradicts the goal of maximizing empty hosts.

Algorithm 2: LAVA (Lifetime-Aware VM Allocation)

LAVA is the more advanced algorithm, designed to overcome NILAS's limitation by strategically managing host emptying. It introduces a novel allocation strategy inspired by memory allocation techniques (specifically, the LAMA algorithm mentioned in the C memory allocator work).

• Key Idea: "Fill gaps between long-lived VMs with much shorter-lived VMs."
• Strategy: Instead of continuously packing long-lived VMs onto a host, LAVA aims to cap the expected lifetime of a host. Once a host has a sufficient number of long-lived VMs, or its expected empty time is pushed too far out, LAVA will preferentially place very short-lived VMs into the remaining capacity. The definition of "much shorter-lived" refers to orders of magnitude difference (e.g., hours/minutes versus days/months).
• Benefit: Even if there are mispredictions for these very short-lived VMs, their impact on the overall expected exit time of the host is minimal. It is highly unlikely that a VM predicted to live for minutes will suddenly live for months, thus preserving the host's trajectory towards becoming empty. This ensures that hosts can reliably transition to an empty state, directly contributing to the objective of maximizing empty hosts and enabling power savings or large VM obtainability.

Prediction Model and System Design

The success of LAVA hinges on an accurate and low-latency lifetime prediction model:

• Model Type: A gradient boosted trees model was chosen due to its balance of accuracy and performance, critical for real-time scheduling decisions.
• Deployment: The model is built as part of the scheduler binary, not as a separate server or microservice. This crucial design decision minimizes the latency incurred by prediction and re-prediction, ensuring that the lifetime-aware scheduling remains on the critical path without slowing down the core scheduling loop.
• Maintenance: The model is bundled with the system binary and updated regularly. Google maintains an end-to-end full-stack training, testing, monitoring, and alerting pipeline to ensure the model's continuous accuracy and reliability in a dynamic production environment.

In summary, LAVA represents a significant evolution in VM scheduling by integrating dynamic, distribution-based lifetime predictions and adaptive re-prediction mechanisms. NILAS provides an initial, effective step by correcting mispredictions, while the full LAVA algorithm takes a more proactive approach to host emptying by strategically filling gaps with ephemeral workloads, ensuring that hosts become empty as intended.

Experimental Setup & Results

▶ Watch: Distribution-based conditional lifetime predictions explained (3:30)

The evaluation of LAVA and NILAS involved a rigorous, multi-stage process, starting with high-fidelity simulations and culminating in a significant production deployment.

Validation Methodology

1. High-Fidelity Simulator: The initial validation was performed using a highly accurate simulator. This simulator was built directly upon Google's production code and utilized real production traces. This approach ensured that the experimental environment closely mirrored the complexities and scale of the actual Google Cloud data centers, providing high confidence in the simulation results.
2. Pilot Studies & Production Deployment: Following successful simulation, pilot studies were conducted using causal analysis and AB experiments to verify the correctness and effectiveness of the algorithms in a live environment. This careful validation paved the way for the deployment of NILAS into Google's production infrastructure.

Baselines and Metrics

• Baseline: The primary baseline for comparison was the LA algorithm, a lifetime alignment algorithm previously published (referred to as the Microsoft version in the talk). This algorithm performs a one-shot lifetime prediction and attempts to group VMs with similar predicted lifetimes.
• Key Metrics: The effectiveness of LAVA and NILAS was primarily measured by:
• Empty hosts improvement: A direct measure of how many more hosts can be placed into low-power mode or made available for large VMs/maintenance. This is a critical metric for cost savings and operational flexibility.
• Stranding decrease: Measures the reduction in wasted or underutilized resources on hosts, indicating more efficient bin-packing and balanced resource allocation.

Simulation Results

The simulator demonstrated substantial improvements for both NILAS and LAVA over the baseline LA algorithm:

• NILAS Performance: Achieved an 11 percentage point improvement in empty hosts. This indicates that NILAS's ability to re-predict and adapt to mispredictions significantly increases the number of hosts that can be emptied.
• LAVA Performance: Demonstrated an even greater improvement, achieving a 15 percentage point improvement in empty hosts. This highlights the additional benefits gained from LAVA's strategic "gap filling" approach, which actively manages host emptying.
• Maximum Margin: The speakers noted that the maximum margin of improvement (presumably in specific, favorable scenarios or the difference between LAVA and NILAS) could be as high as more than 5%. These percentage points, when applied to Google Cloud's massive scale, translate into substantial resource optimizations and cost reductions.

Production Deployment Results (NILAS)

The initial version of NILAS was deployed in the Google Cloud production environment and has been running for almost a year. The real-world results confirm the effectiveness observed in simulations:

• Empty Machine Improvement: NILAS achieved a 2 to 10 percentage point improvement in empty machines. The range reflects variability across different data centers, likely due to varying workload characteristics and hardware configurations.
• Stranding Reduction: A 2 to 3 percentage point decrease in stranding was observed. This signifies that NILAS not only frees up entire machines but also optimizes the utilization of resources on the machines that remain active, ensuring a more balanced consumption of CPU, memory, and other dimensions.
• Resource Consumption: Crucially, all these improvements were achieved with very negligible resource consumption. This validates the system design choice of embedding the gradient boosted trees prediction model directly into the scheduler binary, ensuring minimal latency and overhead on the critical scheduling path.

The consistent positive results across both simulation and real-world production environments underscore the robustness and practical value of LAVA's lifetime-aware scheduling techniques. The ongoing work involves rolling out these techniques to more Google virtual machine products, indicating continued confidence in their benefits.

Practical Implications

▶ Watch: LAVA algorithm: Filling gaps with short-lived VMs (4:30)

The introduction of LAVA and NILAS has profound practical implications for various stakeholders within cloud computing environments, from infrastructure teams and model builders to practitioners deploying applications. These advanced scheduling algorithms offer tangible benefits in terms of cost, performance, and operational efficiency, while also presenting certain tradeoffs and limitations.

What this Means for Practitioners, Infra Teams, Model Builders, or Deployers

1. Significant Cost Savings for Infrastructure Teams: The primary objective of maximizing empty hosts directly translates to substantial operational expenditure (OpEx) reductions. Empty hosts can be put into low-power modes, leading to considerable energy savings across vast data center fleets. For a company like Google, a 2-10 percentage point improvement in empty machines represents millions of dollars saved annually.
2. Improved Resource Utilization: The observed 2-3 percentage point decrease in stranding means that fewer resources (CPU, memory, network, storage) are left idle or underutilized on active hosts. This leads to more efficient bin-packing and a higher effective utilization rate of the existing hardware, potentially delaying the need for new hardware purchases (CapEx).
3. Enhanced Large VM Obtainability: With more hosts readily available in an empty state, customers requesting large VMs that require dedicated physical machines can be provisioned much faster and with higher certainty. This directly improves the service quality for specific high-demand workloads.
4. Faster and Smoother Maintenance Operations: Routine maintenance tasks, such as kernel rollouts, security patches, or hardware upgrades, often require evacuating VMs from hosts. Having a larger pool of empty hosts simplifies these operations, making them faster, less disruptive, and easier to plan. This contributes to overall system reliability and security.
5. Robustness to Workload Variability and Mispredictions: The core innovation of LAVA – distribution-based conditional lifetime predictions and dynamic re-prediction – makes the scheduler inherently more resilient. Initial mispredictions about VM lifetimes are inevitable, but LAVA's ability to adapt in real-time ensures that the system doesn't commit to suboptimal placements for extended periods. This leads to a more stable and predictable scheduling environment.
6. Guidance for Model Builders and System Designers: The success of embedding the gradient boosted trees model directly into the scheduler binary (rather than as a separate service) highlights a critical design pattern for performance-sensitive ML-driven systems. For model builders, it emphasizes the need for highly optimized, low-latency models suitable for inline execution. For system designers, it underscores the importance of minimizing inter-service communication overhead for critical path components.
7. Broader Applicability of Lifetime Prediction: As highlighted in the Q&A, the concept of lifetime prediction extends beyond VM scheduling to other resource management problems like cache management, file system design, and memory allocation (e.g., garbage collection). Practitioners in these domains can draw inspiration from LAVA's adaptive, distribution-based approach.

Tradeoffs and Limitations

1. Increased Scheduler Complexity: Integrating lifetime prediction, conditional distributions, and re-prediction mechanisms significantly increases the complexity of the scheduler's logic. This can make development, debugging, and maintenance more challenging compared to simpler bin-packing algorithms.
2. Reliance on Prediction Accuracy: While LAVA adapts to mispredictions, the overall effectiveness still hinges on the underlying prediction model's accuracy. Poor predictions, even if adapted, can still lead to suboptimal decisions. Continuous monitoring and retraining of the model are essential.
3. Computational Overhead: Although minimized by the in-binary model, there is an inherent computational cost associated with predicting and re-predicting lifetimes for potentially thousands of VMs on candidate hosts during each scheduling decision. This must be carefully managed to avoid introducing unacceptable latency.
4. Workload Specificity: While the core principles are general, the specific algorithms (NILAS and LAVA) are tailored to the characteristics of VM workloads in Google Cloud. Adapting them to vastly different environments (e.g., edge computing with highly constrained resources, specialized hardware, or different VM lifecycle patterns) might require significant modifications.
5. Focus on Empty Hosts: While LAVA excels at maximizing empty hosts, other scheduling objectives (e.g., minimizing VM disruptions, specific latency targets for certain workloads) might need careful consideration to ensure they are not inadvertently compromised. The talk emphasizes that VM disruptions are minimized, but the primary metrics presented are empty hosts and stranding.

In conclusion, LAVA represents a substantial advancement in cloud resource management, offering a blueprint for how machine learning can be deeply integrated into core infrastructure components to drive significant operational efficiencies and cost savings. Its practical implications are far-reaching, setting new standards for intelligent, adaptive scheduling in hyperscale environments.

Key Takeaways

• Disproportionate VM Lifetimes: 88% of VMs are short-lived but consume only 2% of core hours, highlighting a critical inefficiency that lifetime-aware scheduling can address.
• Adaptive Re-prediction is Key: Unlike one-shot predictions, LAVA's use of distribution-based conditional lifetime predictions and dynamic re-prediction allows the scheduler to continuously adapt to observed VM behavior and correct initial mispredictions.
• NILAS for Incremental Gains: The Non-Invasive Lifetime-Aware Scheduling (NILAS) algorithm provides substantial improvements (11% empty hosts in simulation, 2-10% in production) by correcting mispredictions and using lifetime as an intelligent tiebreaker.
• LAVA for Optimal Host Emptying: The full LAVA algorithm further optimizes by strategically filling gaps between long-lived VMs with very short-lived ones, ensuring hosts become empty more reliably and quickly (15% empty hosts in simulation).
• Production-Validated Efficiency: Production deployment of NILAS in Google Cloud demonstrated 2-10% empty machine improvement and 2-3% stranding reduction with negligible resource consumption, validating the real-world impact.
• In-Scheduler ML for Performance: Embedding the gradient boosted trees prediction model directly into the scheduler binary is crucial for achieving minimal latency and enabling lifetime-aware decisions on the critical path of VM allocation.

About the Speaker(s)

The talk featured contributions from a team at Google, with Jianheng Ling and Kathryn S. McKinley presenting the work. Kathryn S. McKinley, a distinguished researcher, also noted her prior work in lifetime-based memory allocation for C, which served as a foundational inspiration for the LAVA project, drawing parallels between object lifetimes in programming languages and VM lifetimes in cloud environments. The research and development of LAVA were conducted at Google, underscoring the company's commitment to advancing the state of the art in cloud infrastructure management and optimization.