🤖 machine learning

Cost-aware Duration Prediction for Software Upgrades in Datacenters

This paper introduces Acela, a cost-aware duration prediction framework that optimizes software upgrade scheduling in datacenters by addressing asymmetric misprediction costs and straggler effects, resulting in significantly improved efficiency, throughput, and reduced cancellation rates in Meta's production systems.

Original authors: Yi Ding, Aijia Gao, Thibaud Ryden, Michal Sedlak, Essam Ewaisha, Igor Marnat, Henry Hoffmann

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yi Ding, Aijia Gao, Thibaud Ryden, Michal Sedlak, Essam Ewaisha, Igor Marnat, Henry Hoffmann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive data center as a giant, bustling city of millions of servers. These servers are the workhorses that power your favorite apps, videos, and searches. But just like any machine, they need regular maintenance and software updates to stay secure and fast.

The problem is that updating these servers is tricky. If you try to update them all at once, the city grinds to a halt. If you update them too slowly, it takes forever. The data center operators at Meta (the company behind Facebook, Instagram, etc.) have been playing it very safe: they assume every single update will take the absolute longest possible time.

The Problem: The "Worst-Case" Traffic Jam
Think of it like a bus driver who assumes every single passenger will take 10 minutes to get on the bus, even though most only take 30 seconds. Because the driver is so cautious, the bus sits idle for hours, wasting time and fuel.

In the data center, this "worst-case" thinking meant their "upgrade windows" (the specific time slots set aside for updates) were only being used 20–40% of the time. They were leaving a lot of potential work on the table, and it took many more cycles to get all the servers updated.

The Solution: Acela, the Smart Traffic Controller
The paper introduces a new system called Acela. Think of Acela as a super-smart traffic controller that doesn't just guess; it predicts exactly how long each specific update will take for each specific server.

But here's the catch: Acela isn't just trying to be "accurate" in a math class sense. It's trying to be cost-aware.

Under-predicting (guessing an update will take 10 minutes when it actually takes 20) is dangerous. The server misses its deadline, the update fails, and the whole schedule gets messed up.
Over-predicting (guessing 20 minutes when it takes 10) is safe. The server finishes early, but the window sits idle for a bit.

Acela knows that being slightly "safe" (over-predicting) is better than being "risky" (under-predicting). It uses a special math trick called Quantile Regression to intentionally guess a little longer than average, ensuring the job gets done on time without causing a crash.

How Acela Works (The Secret Sauce)

It learns from the past: Acela looks at millions of past updates to see patterns.
It ignores the "weirdos": Sometimes, a server has a hardware glitch and takes forever to update (a "straggler"). If Acela learned from these glitches, it would start guessing that every update takes forever. So, Acela smartly filters out these extreme outliers before learning, so it doesn't get scared into being too conservative.
It picks the best guess: It tries out different prediction strategies and picks the one that finishes the most updates while still keeping the failure rate low.

The Results: A Faster, Smoother City
When the researchers tested Acela in Meta's real data centers, the results were impressive:

Better Time Use: They got 1.25 times more work done in the same amount of time. The upgrade windows were finally being used efficiently.
More Updates: They were able to schedule 33% more updates and successfully finish 41% more updates.
Fewer Failures: Even though they were doing more work, the number of failed or cancelled updates dropped by 2.4 times. They met their safety goals (95% of updates finishing on time) much more reliably.

In a Nutshell
Before Acela, the data center was like a cautious driver stuck in traffic, moving slowly because they were afraid of delays. Acela is like a GPS that knows exactly how long every road trip takes, allowing the driver to take more trips in a day without ever running out of time. It balances the need for speed with the need for safety, making the whole system run much smoother.

Technical Summary: Cost-Aware Duration Prediction for Software Upgrades in Datacenters

Problem Statement

Software upgrades are essential for maintaining server reliability in hyperscale datacenters, yet they present unique scheduling challenges distinct from standard service jobs (e.g., search, streaming). Unlike service jobs, which are flexibly distributed across servers to optimize latency and throughput, software upgrades are tied to specific servers with fixed requirements. The primary objective is to meet a strict Service Level Objective (SLO): at least 95% of scheduled upgrades must complete within a fixed "upgrade window."

Current production schedulers (e.g., at Meta) adopt a conservative approach, assuming fixed, worst-case durations for all upgrades to ensure SLO compliance. This strategy results in significant inefficiency, with upgrade window utilization averaging only 20–40% across datacenters. The core challenge lies in the mismatch between standard machine learning goals (maximizing prediction accuracy) and system goals (meeting SLOs while maximizing throughput). Standard predictors often minimize symmetric loss, failing to account for the asymmetric costs of prediction errors: underprediction risks missing the SLO (causing cancellations and repair workflows), while mild overprediction is acceptable and often preferable for safety.

Methodology: The Acela Framework

The authors propose Acela, a cost-aware duration prediction framework designed to integrate seamlessly with existing upgrade schedulers. Acela addresses the problem through three key technical innovations:

1. Asymmetric Cost Modeling via Quantile Regression

Recognizing that underprediction is more costly than overprediction, Acela moves beyond predicting the conditional mean (which minimizes symmetric L2 loss). Instead, it employs Quantile Gradient Boosting Trees (QGBT) to estimate conditional quantiles.

Mechanism: By selecting a quantile parameter $\tau > 0.5$ (e.g., 0.9), the model is trained to slightly overpredict durations.
Loss Function: The system minimizes the quantile loss function, which penalizes underpredictions ( $y \ge \hat{y}$ ) more heavily than overpredictions ( $y < \hat{y}$ ) when $\tau > 0.5$ . This aligns the training objective directly with the SLO requirement.

2. Custom Scoring for Model Selection

Acela introduces a custom scoring function to select the optimal model and quantile parameter, balancing prediction accuracy with SLO compliance. The score is defined as:
$\text{score} = \begin{cases} \text{MAE} & \text{if } \text{OPR} \ge \text{SLO} \\ (\alpha \cdot (1 - \text{OPR}) + 1) \cdot \text{MAE} & \text{if } \text{OPR} < \text{SLO} \end{cases}$
Where:

MAE: Mean Absolute Error (measuring accuracy).
OPR: Overprediction Rate (fraction of upgrades where predicted duration > actual duration).
SLO: The target threshold (95%).
$\alpha$ : A penalty parameter for underprediction.

This function prioritizes models that meet the SLO (OPR $\ge$ 95%). If the SLO is met, the system minimizes MAE to avoid excessive overprediction (which reduces throughput). If the SLO is at risk, the penalty increases sharply.

3. Training Set Diversification (Straggler Mitigation)

Training data often contains "stragglers"—outliers with extreme durations caused by hardware failures or repair workflows. Including these can bias models toward extreme overprediction, reducing efficiency.

Strategy: Acela diversifies the training dataset by creating truncated versions that exclude upgrades in the 99th and 99.9th percentiles.
Selection: Models are trained on these truncated datasets across various quantiles. The best-performing model (lowest score) is selected, ensuring predictions are accurate for the majority of cases while maintaining a safety margin without being skewed by rare failures.

Integration

Acela is implemented as an enhancement layer atop Meta's existing scheduler. It includes a Data Collection Pipeline (DCP), a Model Training and Selection (MTS) module, and a Prediction Query Service (PQS). The scheduler uses Acela's duration predictions to make priority-aware decisions: when priorities are equal, shorter predicted durations are favored to increase throughput; when priorities conflict, the higher-priority upgrade is executed first.

Key Contributions

The paper claims the following contributions:

Large-scale Characterization: The first in-depth analysis of software upgrades at Meta's production datacenter scale, identifying distinct challenges compared to service jobs.
Problem Formalization: Framing software upgrade scheduling as a constrained optimization problem where prediction accuracy is secondary to SLO compliance and throughput.
Asymmetric Cost Identification: Highlighting the unique cost structure of upgrade scenarios where underprediction is significantly more detrimental than overprediction.
Novel Framework (Acela): A new prediction framework utilizing quantile regression, custom scoring, and straggler removal to optimize scheduling outcomes.
Real-world Deployment: The first deployed solution to enhance upgrade efficiency in a production datacenter, validated on millions of upgrades.

Evaluation Results

The authors evaluated Acela using over 4 million software upgrades collected over three months for training and a subsequent month of real-world operations (nearly 1 million upgrades) for testing.

Production Results (vs. Heuristic Baseline):

Utilization: Acela improved upgrade window utilization by 1.25 $\times$ compared to the conservative heuristic baseline.
Throughput: The number of scheduled software upgrades increased by 33%, and the number of completed upgrades increased by 41%.
SLO Compliance: Despite handling significantly more upgrades, Acela reduced the cancellation rate by 2.4 $\times$ , successfully meeting the 95% completion SLO. In contrast, the heuristic baseline failed to meet the SLO in the evaluated period.

Simulation & Ablation Studies:

Loss Functions: Models using symmetric loss functions (L2, L1, Huber) achieved lower Mean Absolute Error (MAE) but failed to meet the SLO (OPR $\approx$ 50%). Acela's quantile loss achieved the target OPR (95%) with a slightly higher MAE, demonstrating that accuracy alone is insufficient for this domain.
Straggler Removal: Removing stragglers from the training set improved prediction accuracy (MAE) by 1.2 $\times$ without negatively impacting the OPR, confirming the efficacy of the data diversification strategy.
Quantile Sensitivity: Sensitivity analysis showed that setting the quantile parameter $\tau$ between 0.9 and 0.99 optimally balances the trade-off between scheduling volume and cancellation rates.

Significance and Claims

The paper positions this work as the first datacenter-scale study of software upgrades and the first deployed solution to enhance upgrade efficiency through duration prediction. The authors emphasize that their approach shifts the paradigm from "maximizing prediction accuracy" to "optimizing for system objectives" (SLO compliance and throughput). By acknowledging the asymmetric costs of errors and the specific operational constraints of datacenter upgrades (e.g., fixed windows, buffer limits), Acela demonstrates that cost-aware prediction can significantly improve operational efficiency in large-scale infrastructure without compromising reliability.