💻 computer science

BudgetFunnel: Coarse-to-Fine Global Budget Allocation for Trace-Driven Serverless Cold-Start Mitigation

BudgetFunnel is a trace-driven, coarse-to-fine framework that allocates a shared warm-retention budget across heterogeneous serverless functions using lightweight screening and a precedence-aware greedy allocator, achieving near-optimal cold-start mitigation with significantly reduced evaluation overhead compared to full-evaluation and existing baseline strategies.

Original authors: xuming wu, Zhipeng Ye, Gaoyuan Zhao, Zihao Lu, Jiayi Hong, Wen-Yu Peng, Zhibin Shao, Yan Cao

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: xuming wu, Zhipeng Ye, Gaoyuan Zhao, Zihao Lu, Jiayi Hong, Wen-Yu Peng, Zhibin Shao, Yan Cao

Original paper licensed under CC BY 4.0 (https://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

In the modern cloud, a vast number of applications run on a model called serverless computing. Instead of keeping a computer server running constantly to handle requests, the system wakes up a fresh, empty environment only when a user needs it, performs the task, and then lets it go to sleep. This approach saves money and reduces waste, but it has a frustrating flaw: the first time a user asks for a service, the system must build that environment from scratch. This process, known as a "cold start," causes a noticeable delay. To fix this, system administrators can keep some of these environments awake and ready, a strategy called "prewarming." However, keeping too many environments awake wastes the very resources the system was designed to save. The challenge lies in deciding exactly which functions to keep warm and for how long, especially when there are thousands of different functions competing for a limited pool of resources.

Researchers have developed a new method called BudgetFunnel to solve this balancing act. The core idea is to treat the total time available for keeping environments awake as a shared budget that must be spent wisely across a massive workload. In a typical cloud system, there might be thousands of different functions, each with its own unique pattern of use. Some are used constantly, while others are used rarely or in sudden, unpredictable bursts. If an administrator tries to calculate the perfect "keep-alive" time for every single function to minimize delays, the calculation itself takes so long that it becomes impractical. BudgetFunnel addresses this by using a two-step process that first filters the problem down to its most critical parts.

The researchers tested their method using real-world data logs from two major cloud providers, one from Microsoft Azure and another from Alibaba. These logs contained millions of records showing when different functions were called. The team first used a simple, fast check to identify which functions were likely to cause the most delays if they were allowed to go cold. They looked at basic patterns, such as how often a function was used, how irregular its usage was, and whether it followed a daily rhythm. Based on these simple clues, they selected only the top ten percent of functions as "candidates" for detailed analysis. The remaining ninety percent were left with a default setting of zero, meaning the system would not try to keep them warm.

Once the candidates were identified, the researchers ran a detailed simulation on just this small group. They tested various durations for keeping these specific functions awake, calculating exactly how much delay would be saved versus how much resource cost would be incurred for each option. Finally, they used a greedy algorithm to distribute the total available "warm time" budget among these candidates. This algorithm worked like a careful shopper with a fixed amount of money, choosing the upgrades that offered the biggest reduction in delays for the smallest cost. The result was a tailored plan that assigned specific keep-alive times to the most important functions while ignoring the rest.

The findings showed that this focused approach was remarkably effective. By evaluating only ten percent of the functions, the system achieved a nine-fold increase in speed compared to trying to calculate the best settings for every single function. Despite this massive reduction in calculation time, the quality of the result remained very high. The number of delayed requests, measured as a percentage of total traffic, stayed within just 1.54 percent of the result produced by a full-evaluation greedy approach (which analyzes all functions) on the Azure data, and within 1.93 percent on the Alibaba data. In other words, the system saved almost all the potential performance benefits while avoiding the heavy computational cost of analyzing everything.

The study also compared this method against other common strategies, such as keeping all functions warm for the same fixed amount of time or using average wait times to guess how long to keep them. BudgetFunnel significantly outperformed these standard approaches, reducing the rate of cold starts by up to 39 percent on the Alibaba workload. The researchers confirmed that their method was robust, meaning it worked well even when they changed the way they counted delays or adjusted the specific time intervals they tested. They also verified that the greedy algorithm they used was very close to the mathematically optimal solution for smaller test cases, differing by less than 2.6 percent from the certified optimum.

This work demonstrates that in complex systems, it is often possible to find a near-optimal solution without examining every single detail. By using a coarse filter to identify the most critical elements and then applying detailed analysis only where it matters, administrators can manage resources efficiently without getting bogged down in impossible calculations. The BudgetFunnel framework offers a practical way to keep serverless applications fast and responsive without breaking the bank, proving that a little bit of smart filtering can go a long way in managing the invisible machinery of the cloud.

Technical Summary: BudgetFunnel

1. Problem Statement

Serverless computing (Function-as-a-Service) faces a persistent performance challenge: cold starts. When a function is invoked without a pre-existing warm execution environment, the platform must provision resources, leading to significant latency spikes. While prewarming (keeping instances alive via Time-To-Live or TTL policies) mitigates cold starts, it incurs a cost in "warm-retention resources" (idle compute time).

The core problem addressed is the allocation of a shared warm-retention budget across a heterogeneous set of serverless functions. Existing approaches often apply uniform policies or focus on single-function optimization, failing to account for the trade-off between varying function characteristics (sparsity, burstiness, periodicity) and a global resource constraint. The goal is to minimize the Cold-Start Rate (CSR)—specifically the request-weighted percentage of invocations that experience a cold start—subject to a fixed global budget of warm instance-seconds.

2. Methodology: BudgetFunnel

The paper proposes BudgetFunnel, a coarse-to-fine trace-driven framework designed to allocate a shared warm budget efficiently without evaluating every function exhaustively. The framework operates in three distinct stages:

Stage 0: Lightweight Proxy Screening (Coarse)

Instead of simulating every function, the framework first identifies a small subset of "candidate" functions that are most likely to benefit from warm-retention policies.

Features: It computes lightweight statistics from invocation traces:
- Sparsity: The fraction of time slots with zero invocations.
- Burstiness: Normalized variance of request rates.
- Periodicity: A lightweight daily autocorrelation proxy.
Scoring: These features are robustly normalized (using Median Absolute Deviation) and combined into an equal-weight proxy score.
Selection: The top- $\gamma$ fraction of functions (e.g., $\gamma = 0.10$ ) are selected as candidates. Non-candidates are assigned a default TTL of 0.

Stage 1: Fine-Grained Candidate Evaluation (Simulation)

Only the selected candidates undergo detailed trace-driven simulation.

Simulation: For each candidate, the framework simulates the system over a discrete TTL grid (ranging from 0 to 60 minutes).
Metrics: It estimates the marginal reduction in cold requests ( $\Delta CR$ ) and the marginal increase in warm cost ( $\Delta Cost$ ) for each TTL upgrade relative to the baseline (TTL=0).
Semantics: The simulation uses a slot-based abstraction (1-minute slots) where a function remains warm for $k$ slots after its last activity. Cold starts are counted as request-weighted events (requests arriving when the function is cold).

Stage 2: Precedence-Aware Global Budget Allocation

A greedy allocator distributes the global budget $B$ across the candidates.

Mechanism: It calculates a gain ratio (marginal benefit per marginal cost) for upgrading a function from its current TTL level to the next level in the grid.
Constraint: The algorithm respects precedence constraints; a function can only be upgraded to a higher TTL if it has already been assigned the lower TTL.
Execution: Using a max-heap, the algorithm iteratively selects the upgrade with the highest gain ratio that fits within the remaining budget until the budget is exhausted.

3. Key Contributions

Shared-Budget Formulation: The paper formulates cold-start mitigation as a workload-wide optimization problem under a common resource budget, rather than isolated per-function decisions.
Coarse-to-Fine Evaluation: It introduces a screening mechanism that reduces the computational cost of fine-grained simulation by focusing only on high-potential candidates, achieving significant speedups.
Separated Approximation Analysis: The evaluation rigorously separates two sources of approximation:
- Screening Loss: Measured by comparing the coarse-to-fine approach against a "full-evaluation" greedy approach (where $\gamma=1$ ).
- Allocation Loss: Measured by comparing the greedy allocator against an exact Mixed-Integer Linear Programming (MILP) solution on the same reduced workload.
Robust Trace-Driven Evaluation: The framework is validated on two distinct workloads (Azure serverless traces and Alibaba microservice traces) with extensive sensitivity analyses regarding proxy features, TTL grids, cold-counting semantics, and budget definitions.

4. Experimental Results

The evaluation uses the Azure serverless trace (3-day window, top-1000 functions) and the Alibaba Cluster Trace–Microservices v2021 (12-hour window, top-1000 microservices).

Efficiency vs. Accuracy: At a candidate ratio of $\gamma = 0.10$ (evaluating only 10% of functions), BudgetFunnel achieves approximately a 9× end-to-end speedup compared to full evaluation.
Performance Gap:
- On the Azure trace, the request-weighted CSR is within 1.54% of the full-evaluation greedy baseline at $1 \times B_{ref}$ .
- On the Alibaba trace, the gap is within 1.93%.
- Across the full budget sweep, the maximum relative CSR gap to full-evaluation greedy is 2.48% (Azure) and 2.16% (Alibaba).
Comparison to Baselines:
- On Alibaba, BudgetFunnel reduces CSR by up to 39.4% compared to a Global TTL policy and 21.8% compared to an IAT-Mean TTL policy under matched budgets.
Optimality Gap: Same-scope exact MILP experiments on reduced Azure workloads (50–200 functions) show the greedy allocator is within 1.42–2.60% of the certified optimum.
Robustness: The method's ranking and performance remain stable across different cold-counting semantics (request-weighted vs. slot-level), proxy feature ablations, and provider-specific trace windows.

5. Significance and Claims

The paper modestly claims that BudgetFunnel provides a practical mechanism for reducing the computational cost of evaluating shared warm-budget allocation problems in serverless environments.

Clarification on "Global": The authors explicitly state that "global" refers to workload-wide coordination under a shared budget, not mathematical global optimality. The greedy allocator is a heuristic, not a guaranteed global optimizer.
Scope of Application: The framework is designed for offline, trace-driven analysis. The authors note that because public traces are aggregated (lacking per-request timing), latency results are treated as model-based sensitivity analyses rather than direct production measurements.
Complementarity: The work does not claim to replace system-level optimizations (like snapshotting or JIT) or predictive pre-warming. Instead, it offers a specific mechanism for resource allocation that can be integrated with or run alongside such systems to optimize the trade-off between cost and cold-start performance.

In summary, BudgetFunnel demonstrates that it is possible to achieve near-optimal cold-start mitigation with a shared budget by focusing computational effort on a small, screened subset of functions, thereby making large-scale, trace-driven budget optimization feasible.