Priority-Aware Scheduler for Serverless Functions Provision and Load Balancing

Introduction

Function-as-a-Service (FaaS) constitutes the core implementation model of serverless computing, facilitating streamlined cloud resource utilization while abstracting infrastructure complexities. Prominent cloud platforms, including AWS Lambda, Google Cloud Functions, and Azure Functions, have implemented FaaS solutions supporting diverse applications: web services [1, 2], machine learning algorithms [3, 4], and other distributed computing frameworks [5, 6]. This paradigm shifts infrastructure management responsibilities from developers to providers [7], enabling focused application logic development. FaaS architectures exhibit three principal advantages: (1) native support for stateless event-driven operations enabling agile deployment cycles, (2) elastic resource allocation synchronized with runtime demand [8], and (3) granular cost optimization to customers through pay-per-execution billing. A representative application architecture is demonstrated in Figure 1.

Image not extracted

Despite its advantages, serverless computing introduces significant cold start challenges that create tension between latency optimization and resource efficiency. Functions are instantiated ephemerally with execution durations typically spanning milliseconds to seconds [9], yet initializing fresh instances (cold starts) requires nontrivial environment preparation latency [10] compared to reusing preloaded warm instances. Empirical studies indicate cold starts contribute over 80% of total response latency [11], directly impacting user experience and service economics [12]. Meanwhile, maintaining warm instances for all functions proves impractical for two fundamental reasons: (1) Most functions experience low invocation frequencies [13], making persistent memory retention economically unjustifiable due to unbilled idle allocation. (2) Providers achieve server consolidation through colocating thousands of short-lived functions, but preloading all instances would require hundreds of GBs of memory [14], exceeding typical server capacities. This dual constraint establishes the core optimization challenge: achieving cold start mitigation while preventing memory bloat [3, 15, 16].

Existing mitigation approaches can be categorized as: (1) system-layer optimizations accelerating environment initialization [17, 18, 19] and (2) occurrence mitigation strategies through instance management [13, 20, 21]. This work focuses on the latter category, specifically investigating non-intrusive cold start reduction within existing infrastructure constraints. Prior instance management techniques [13, 20, 21] employ either fixed-duration instance retention or basic interval-based heuristics, exhibiting three critical limitations: (1) Pattern Oversight: Failure to account for event-driven invocation triggers and their temporal correlations. (2) Sparse Invocation Neglect: Ineffective handling of infrequently called functions due to static retention policies. (3) Resource Agnosticism: Ignorance of memory-constrained multi-worker environments requiring coordinated load distribution.

In this context, we aim to design a predictive, non-intrusive scheduling framework that synergistically addresses these gaps. We identify four challenges in developing such a method:

• Low-Latency: Operational constraints demand subsecond provisioning decisions given FaaS platforms process thousands of concurrent invocations across millions of functions per minute [22], with typical execution windows under one second.

• Burst Tolerance with Multi-Worker Scalability: Scheduling mechanisms must exhibit (1) sublinear complexity growth to accommodate request burst [2], and (2) elastic coordination across dynamically scaled worker pools without architectural modification.

• Skewed Invocation Distribution: Invocation data can be sparse, where 95% of functions experience less than one invocation per day [13], limiting training data availability. Plus, the inherent invocation heterogeneity creates significant memory utilization variance across workers, making load balancing nontrivial.

• Temporal Concept Drift: The lightweight nature of FaaS makes applications evolve faster than traditional software, so scheduling strategies must withstand both short-term concept drift (e.g., hourly user activity fluctuations affecting) and long-term distribution shifts (e.g., quarterly software updates), altering function call patterns and complicating predictive modeling.

Insight: The event-driven paradigm of serverless architectures enables systematic identification of recurrent invocation patterns, permitting optimized function categorization and strategic provisioning. Three empirical observations grounded in both domain expertise and data analysis substantiate this premise: Trigger-Pattern Correlation: 82% of functions exhibit predictable execution sequences tied to specific event triggers (e.g., scheduled data processing workflows), as verified through analysis of production traces (in § 3). Behavioral Convergence: functions within an application often display behavior convergence. For example, functions within a multi-stage processing workload are typically invoked in turn. Transient Temporal Locality: Even irregular functions can exhibit temporal locality, maintaining a short execution window during peak activity periods, permitting cost-effective transient retention. These observations demonstrate that functions can present limited predictable patterns, facilitating a dual-phase scheduling mechanism: 1) anticipate invocations through trigger-pattern mapping and historical sequence analysis to minimize cold starts with minimal memory influence; 2) implement priority-based placement across distributed workers, considering both temporal urgency and memory constraints to reduce loading variances.

We therefore present SPES-Ext, a Extension versions of the Scheduler for Provisioning runtimE Serverless functions. This is a pattern-aware adaptive scheduler that optimizes the latency-resource tradeoff while enforcing load balancing across memory-constrained distributed workers. The design synthesizes three key innovations: (1) We summarize five dominant invocation patterns driven by the empirical analysis of production traces, supplemented by three adaptive retention policies for function patterns that are less predictive. (2) We propose a computationally lightweight yet effective metric–co-occurrence rate–that quantifies inter-function dependencies, enabling predictive chaining of related invocations, i.e., highly correlated functions can be predictive indicators of each other. (3) We design dynamic policy adjustments for continuous pattern recalibration to address concept drift as FaaS evolves. In this way, SPES-Ext operates through two coordinated phases. It anticipates invocations using pattern matching and correlation analysis to pre-load functions with fine-grained strategies. When the invocations come, SPES-Ext orchestrates the load and distribution of functions toward workers. As a result, our rule-based SPES-Ext addresses all the above challenges. Its tailored strategies can handle diverse functions with remarkable scalability and adaptivity, introducing a small computation overhead.

We evaluate SPES-Ext on the most widely used industrial dataset released by Microsoft Azure [13]. Experiments demonstrate the superiority of SPES-Ext, which achieves both-side improvement: reducing the $75^{\mathrm{th}}$-percentile cold start rate by 80%–90% and the wasted memory time by 83.92%–88.82% compared to baselines, and also reducing the proportion of “always-cold” functions significantly. Meanwhile, SPES-Ext lowers the mean variances of workers space by 52.49%–96.14%. Extensive ablation studies further confirm the effectiveness of our designs of inter-function connection and adaptive strategies in our provision policy, as well as the validity of our load-balancing scheduling.

In summary, the main contributions of this paper are:

• We present SPES-Ext, the first rule-based priority-aware scheduler for memory-constrained distributed worker clusters, integrating three modules, i.e., function provision, eviction decision, and load-balancing.

• We summarize typical invocation patterns and categorize functions accordingly as the basis of our novel differentiated provision strategy. We also create an effective “co-occurrence” metric to gauge inter-function correlations. Contributions of designs for adaptivity and unseen functions have also been validated.

• We conduct extensive experiments under both a single-worker scenario without memory constraint and a multi-worker scenario with memory limitation to demonstrate the significant improvement of SPES-Ext in the cold start and wasted memory reduction, as well as the improvement in load balancing effects.

Part of the results in this paper has been reported in SPES [23], published at ICDE. For clarity, we should point out that SPES represents the provision policy we propose in [23], and SPES-Ext refers to the general scheduler we propose in this paper that involves provision, eviction, and load-balancing. For readers who have read the conference version, this extension mainly includes a general scheduler that couples both provisioning and load-balancing (See § 4), and new experiments under the memory-limited, multi-worker scenario (See § 5.2). We also include a more comprehensive background, preliminary analysis, discussion, and related work version.

Background

Serverless Computing

Serverless computing constitutes an evolving cloud execution model where cloud providers assume full responsibility for infrastructure management and dynamic resource allocation, enabling developers to focus exclusively on application logic implementation. As a core subset of serverless architectures, Function-as-a-Service (FaaS) specifically operationalizes this paradigm by abstracting runtime environments into ephemeral, event-triggered computational units. In FaaS, services are structured as stateless computational units (functions) that execute in response to specific event triggers defined through declarative rules [24]. This operational model offers inherent scalability and cost-efficiency through granular pay-per-use billing for actual resource consumption [25]. Practically, cloud-native applications are typically decomposed into discrete, loosely-coupled functions that may adopt explicit orchestration patterns [26]. The technology has gained significant traction across domains, including web services and distributed machine learning training [27]. Despite its advantages, key technical challenges persist, particularly in guaranteeing strict Quality-of-Service (QoS) compliance for metrics such as response latency and tail latency optimization [28].

Cold Start Challenge

Figure 2 displays the lifecycle of a serverless function under FaaS. The FaaS provider initially provisions the function by retrieving user-submitted code and instantiating an isolated runtime sandbox (e.g., container or VM) on cluster nodes—a process termed cold start. This phase sequentially involves code retrieval from persistent storage, sandbox initialization, memory loading, and handler execution. A warm start, conversely, bypasses provisioning phases by reusing pre-initialized environments, thereby minimizing latency. After execution for a request, the environment persists in an idle state until evicted by the orchestration layer after a provider-defined timeout [29]. Naturally, environment reuse inversely correlates with cold start frequency. A critical trade-off emerges: while retaining active environments reduces provisioning overhead and accelerates subsequent invocations, it introduces more idle resource retention quantified via wasted memory time (WMT). Formally, WMT represents the cumulative duration where a function’s runtime image occupies memory without processing requests, serving as a key empirical metric for infrastructure efficiency analysis [13].

Image not extracted

The cold start problem poses a critical challenge in serverless computing, as it introduces substantial runtime latency while providers must strictly adhere to QoS constraints and sustain a perceived “always-ready” service illusion. Empirical studies indicate two compounding factors. First, cold starts dominate the overall execution time [15, 19, 30], accounting for over 70% of total invocation time in mainstream platforms like gVisor, as reported in [17]. On the other hand, transient function lifetimes trigger frequent cold starts across diverse workloads [31, 32, 33]. These render cold-start-induced latency prohibitively detrimental to QoS adherence. Given memory’s cost constraints and finite availability, mitigation strategies necessitate either predictive instance optimization to balance memory utilization and readiness or accelerated provisioning (e.g., parallelized sandbox initialization).

Preliminary Empirical Analysis

Challenges of Serverless Function Provision

Low-Latency

Serverless provisioning systems face dual operational constraints. First, they must execute sub-second scheduling decisions for bursty invocation volumes (e.g., tens of thousands per minute [34]), precluding computationally intensive optimization models. Second, short-lived function lifetimes (typically $< 60\mathrm{s}$) demand dynamic strategy updates within tight scheduling windows [35], as delayed provisioning directly impacts billing efficiency. Consequently, lightweight schedulers outperform complex algorithms in practice, prioritizing decision velocity over theoretical optimality.

Scalability under invocation burst

Serverless provisioning systems must inherently support autonomous elastic scaling as FaaS invocations are extremely bursty and dynamic [33], and resource allocation in a FaaS platform must synchronize with demand spikes within milliseconds to prevent QoS violations. Since invocation rates exhibit order-of-magnitude fluctuations within minute-level intervals (e.g., $10\times$ traffic surges during e-commerce peak events), a highly scalable solution is required.

Skewed Invocation Distribution

Serverless functions demonstrate multidimensional heterogeneity in functionality. They are implemented with varied runtime environments and dependency libraries, creating distinct execution profiles [28]. Moreover, trigger mechanisms span HTTP endpoints (API gateways), database transactions (e.g., Cosmos DB), and message queues, each imposing unique invocation patterns [36]. This heterogeneity induces extreme invocation disparity, evidenced by Azure’s 14-day production traces collected by [13], as shown in Figure 3. We can observe that the invocations are highly nonuniform, with most functions being rarely invoked. Such a power-law distribution creates inherent challenges for learning-based provisioning that require lots of records of each function for training.

Image not extracted

Evolution in invocation behavior

Invocation dynamics evolution introduces critical adaptability challenges for serverless provisioning systems, particularly those employing predictive pre-loading to minimize cold starts. This issue is exacerbated in learning-based approaches due to their need for frequent, resource-intensive retraining. Many factors can cause such shifts, including temporal fluctuations (e.g., holiday-induced traffic spikes in e-commerce platforms), business logic updates (e.g., geographic expansion in business propagating to function dependencies and invocation patterns), trigger reconfigurations (17% of functions annually rebind to new triggers or call chains [13]), etc. The Azure dataset (Figure 4) demonstrates short-term volatility, with representative functions showing abrupt invocation shifts. Such dynamics necessitate provisioning methods with inherent adaptability to concept shifts without requiring constant retraining.

Image not extracted

Observations and Our Insight

Invocation pattern and triggers

Serverless systems employ an event-triggered invocation paradigm where predefined trigger types (HTTP, message queues, scheduled timers) establish deterministic invocation modalities [36]. This architectural constraint enables predictable behavioral patterns for most functions, as evidenced by two empirical findings from the Azure dataset.

First, most functions correspond to only one trigger type. As shown in Figure 5, most of functions bind to a single trigger type, and only 2.6% exhibit multi-trigger bindings (maximum 3 types, categorized as “combination”).

Image not extracted

Second, we find that trigger-specific invocation regularity emerges as a predictive signal, validated through distributional analysis, where we applied the Kolmogorov-Smirnov test on functions with $\ge10$ invocations ($pValue \ge0.05=0.05$ [37]). Results show that 68.12% timer-triggered functions are invoked periodically or quasi-periodically, excluding 6.65% do not have enough counts. Also, 45.02% HTTP-triggered invocations align with Poisson arrivals, conforming to the expectation of human activities, excluding 36.20% without enough samples. Though the Poisson process is memoryless and unsuitable for exact prediction, this statistical alignment demonstrates that meaningful invocation behaviors are associated with triggers.

Application workflow

Serverless applications often orchestrate functions into logical workflows through explicit chaining or callback mechanisms [26], creating inherent temporal and semantic dependencies between invocations. Empirical analysis reveals two key properties of these dependencies. We create a metric co-occurrence rate (COR) to quantify functional cohesion, inspired by linguistic co-occurrence analysis. For any function pair sharing the same application or user context, COR quantifies their invocation simultaneity as:

Analysis of 50 randomly sampled negative pairs (non-associated functions) demonstrates strong workflow cohesion: application/user-linked functions (candidate function) exhibit $4.6 \times$ higher COR (0.231 vs. 0.050) than unrelated pairs. Trigger-mediated convergence further amplifies this cohesion. When functions share trigger types (e.g., HTTP endpoints), their COR increases to 0.271—$2.1 \times$ higher than cross-trigger pairs (0.131). This aligns with our earlier observation in § 3.2.1 that triggers dictate invocation semantics.

These findings confirm that workflow structures imprint measurable invocation patterns, particularly under shared operational triggers. Such regularity provides critical signals for dependency-aware provisioning strategies.

Temporal locality in invocations

Temporal invocation locality—the propensity for serverless functions to exhibit clustered invocation bursts within short timespans—emerges as a critical operational pattern. This phenomenon arises from two complementary factors. First, real-world triggers like flash sales in e-commerce platforms generate rapid request successions, directly propagating to function invocation spikes. Second, common architectural patterns systematically induce bursty behaviors. For example, in a fan-out application, a primary function spawns parallel invocations of multiple downstream functions simultaneously (e.g., processing 100 image thumbnails in one API call). Callback functions that handle asynchronous operations also trigger recursive invocations until task completion (e.g., retry loops in payment systems). Empirical validation via the Azure dataset (Figure 6) reveals even infrequently invoked functions sustain temporal locality. For infrequently invoked functions presenting temporal locality, invocation prediction can be difficult, yet simply keeping a loaded function for some time can considerably reduce cold starts without wasting much memory.

Image not extracted

Insight: The microservice and event-driven architecture of serverless systems results in the concentration of recurring and systematic invocation behaviors. By analyzing the invocation patterns and categorizing functions, we can accurately predict and pre-load function instances to reduce cold starts.

Motivated by these insights, we present SPES-Ext, a lightweight scheduling framework for FaaS systems that synergistically integrates three core mechanisms: rule-based provisioning, adaptive eviction, and distributed load balancing. It leverages the application, user, and trigger information to design tailored and evolution-adaptive strategies to pre-load, evict, and dispatch categorized functions without requiring large amounts of training data. In general, SPES-Ext provides a comprehensive, developer-free, language-agnostic function scheduler that can be seamlessly adopted on systems to optimize cold starts and memory usage.

Methodology

To address the aforementioned challenges, we propose SPES-Ext, a general-purpose, rule-based scheduler with priority awareness. As illustrated in Figure 7, SPES-Ext adopts a three-component architecture: Provision Policy, Eviction Decision, and Workers Load Balancing. The design of SPES-Ext is driven by the following key considerations:

Image not extracted

• To alleviate cold start, how do we predict function invocations and decide function provision?

• When there are functions to load, how to dispatch each function to the workers?

• When the workers are out of memory, which functions should be evicted?

Provision Policy

To address the first challenge, we employ a provision policy that predicts function invocations and dynamically determines which functions to load. Our design rationale is that an optimal scheduler should decide to load a function immediately before its invocation and evict it from memory right away after the execution if no more invocations, so as to minimize idle memory retention. Achieving this requires fine-grained invocation prediction, which forms the core of SPES’s design, whose overview is presented in Figure 8. SPES consists of four key components: deterministic function categorization, indeterminate function assignment, adaptive strategy application, and function provision based on invocation prediction. Specifically, we first summarize typical invocation patterns and formulate their corresponding definitions. These patterns result from pre-defined triggers [38] and the combinatorial methods of function calling (in common application scenarios [39]). If a function satisfies the definitions, it is categorized; Otherwise, SPES assigns uncategorized functions to three supplementary types. We also introduce two dynamic strategies to accommodate evolving FaaS workloads. Finally, SPES provisions functions according to rule-based invocation prediction, where each type follows its own predicting rule.

Image not extracted

It is important to note that distinct triggers may demonstrate identical temporal patterns in function invocations. For instance, both service bus triggers and event grid triggers can process streaming data packets, despite specializing in different message formats. In addressing cold start optimization, maintaining a one-to-one mapping between trigger types and function categories is neither practical nor advantageous.

Let us start with three definitions:

• Waiting time (WT): the length of successive idle time. Take an invocation sequence $(28, 0, 12, 1, 0, 0, 0, 7)$ as an example, where each value denotes the invocation count at each sampling slot, derived to a sequence of WTs $\{WT\} = (1, 3)$, as no invocation exists at the 2nd slot or in slots 5–8. If we foreknow the next WT, for example, at the 4th slot, we know no invocations will arrive in slots 5-8, then we can easily make a perfect decision: evict the function now and re-load it at the end of slot 9. Hence, we can transform invocation prediction to WT prediction. Different from a previously proposed inter-arrival time (IAT) [13], WT depicts the slot-grained interval between two successive invocation sequences, from the last’s end to the next’s start. WT is also different from idle time (IT). IT is the time without invocations or subsequent function executions, so IT exists after any single execution. WT, instead, only appears when a successive series of invocations ends, and the end of a single execution does not necessarily incur a WT.

• Active time (AT): the length of successive time with invocations. The above-mentioned invocation sequence delivers an AT sequence $\{AT\} = (1, 2, 1)$ because the function is invoked in slots 1, 3–4, and 9.

• Active number (AN): a descendable definition, the number of successive invocations during AT. Again, the above sequence delivers $\{AN\} = (28, 13, 7)$.

Deterministic Function Categorization

This section defines five invocation types based on typical invocation patterns and categorizes functions accordingly. Table 1 shows an overview of the five types. The guiding principle for definition is from easy to difficult, also serving as the categorization priority: if a function fits a former type, it will not fit any latter type. Our introduction follows this order.

Type name	Characteristics	Definition	Predictive values
Always warm	Almost invoked all the time	Invoked at every time — Inter-invocation time $\le$ observing time%	–
Regular	Almost invoked periodically	(Processed) $P_{95}(\{WT\}) - P_{5}(\{WT\}) \le1$ CV of $\{WT\} \le0.01$	Median of WTs
Appro-regular	Invoked quasi-periodically	(Processed) the count of $\operatorname{Mode}_{n}(\{WT\}) \ge0.9 \times$ sequence length	$\operatorname{Mode}_{n}(\{WT\})$
Dense	Frequently invoked	$P_{90}(\{WT\}) \le$ a small constant	[min, max] of $\operatorname{Mode}_{k}(\{WT\})$
Successive	Successively invoked	$\min(\{AT\}) \ge\gamma_1$; $\min(\{AN\}) \ge\gamma_2$; $\gamma_1 < \gamma_2$	–

i) Always warm: This type describes consistently active functions, such as long-running operations and hyperfrequent calls, which usually involve durable or timer-triggered functions (whose interval is small enough). For example, functions in continuous integration/deployment (CI/CD) pipelines are consistently invoked to automate code building, testing, and deployment. A function is defined as “always warm” if 1) it is invoked at every sampling time or 2) the sum of inter-invocation time is $\leq$ one-thousandth the observing time. Such functions are undoubtedly always loaded.

ii) Regular: Regular task processing, usually using timer-triggered functions, is a basic functionality (e.g., polling). Yet, their actual invocations may not be strictly periodic (with a constant WT) since there are undesired fluctuations: 1) The exact first/last WTs during an observing period are almost impossible to record. 2) Periodically generated events can be blocked or delayed by contingencies such as concurrency limits, network connectivity issues, etc. 3) Other events can invoke a mostly regularly invoked function occasionally.

Here comes the slacked definition: A “regular” function satisfies either 1) the difference between the 5th and 95th percentile of its WT sequence is $\leq1$ or 2) the coefficient of variation of WTs is close to zero ($\leq0.01$ in practice). Otherwise, we remove the first and last WTs and re-check if the function follows the definition. If the answer is still no, we apply another slacking rule by merging adjacent small WTs. In particular, for each WT closely valued to the WT mode, its adjacent small WTs are gradually merged until reaching ① the sequence’s end or ② another WT close to the mode or ③ an already merged WT. In this way, a WT sequence valued by $(1439, 1438, 1, 1439, 1438, 1)$ is processed to be $(1439, 1439, 1439, 1439)$, and then it seems “regular”. With a processed WT sequence satisfying the above definition, the function belongs to the “regular” type. We partially eliminate accidental factors by processing WTs with slacking rules and modeling essential invocation behaviors. Finally, we record the median of WTs as the predictive value for invocation prediction, leveraged in § 4.1.4.

iii) Approximatively regular: This is the derived type from “regular”. A regular function may experience invocation variance and long-term disturbance. For example, a data-processing function is expected to receive updates from a data station every three minutes (IoT Hub trigger functions). Yet, limited by the data transmission capability, the function is actually invoked every 3–5 minutes. We define such functions as “approximatively (appro-)regular”. Particularly, a function is “appro-regular” if the occurring count of the first $n$ frequently appearing values (modes) of WTs is $\geq$ a large percent (90% practically) of the WT sequence’s length. $n$ is a pre-defined integer. The predictive values for these “appro-regular” functions are the first $n$ modes.

iv) Dense: This characterizes irregular but frequent invocations with intermittent idle durations. “Dense” functions can involve several triggers: queues (or service bus using the queue flavor) for frequent messages in asynchronous processing, influenced by variations in message arrival times; Cosmon DB triggers for frequent real-time data processing; HTTP triggers for processing frequent HTTP requests. Functions with a 90th percentile of the WTs $\leq$ a small constant are defined as “dense”. The range of the first $k$ modes derives predictive values, i.e. $[\min(\operatorname{Mode}_k(\mathrm{WTs})), \max(\operatorname{Mode}_k(\mathrm{WTs}))]$, where $k$ is an empirical integer. Such a function should be unloaded only if its idle time is larger than the constant.

v) Successive: This describes inactive functions experiencing consecutive invocations in a short timeframe (temporal locality) before returning to an inactive state.

It can involve HTTP trigger functions (e.g., bursty social media trends), storage trigger functions (e.g., uploading files to Blob Storage), etc. In practice, feedback loops engaged functions, caching mechanism implementations, and load balancing-involved applications can also exhibit such behavior. We define this as $\min(\{AT\}) \ge\gamma_1$ or $\{AN\} \ge\gamma_2$, where $\gamma_1 < \gamma_2$ and they are pre-defined lower bounds. Predicting the start of such an invocation wave is highly difficult. Nevertheless, we can tolerate the first invocation and keep the function alive until the wave ends. With limited cold starts, we save lots of memory.

Indeterminate Function Assignment

This section handles functions that do not satisfy the above five definitions using two strategies: ① “forgetting” previous records to re-check whether the not-too-long history invocations satisfy the five definitions, and ② assigning the remaining functions with three extra types.

i) Forgetting: As discussed in § 3.1.4, function invocations experience concept shifts. For example, a regular invoked function can be categorized as “always warm” if the interval is adjusted to be smaller than the recording unit. Therefore, the near-the-present records should be given priority. We slice out the sequential invocation observations in days, from the beginning to the half. Then, we gradually remove the older observations from the original $d$-day observations and check whether invocations in 2nd–$d$th days conform to existing definitions. If not, we check the invocations in 3rd–$d$th days, and so on, until the $\lfloor d/2\rfloor$th day.

ii) Assigning: The remaining indeterminate functions are assigned to three types according to the validation results:

D1. Pulsed describes functions showing less obvious temporal locality in invocations than “successive” ones. Similarly, we allow a cold start at the first invocation time and keep the function warm until its idle time reaches a pre-defined threshold.

D2. Correlated invocations are predicted based on other functions. Functions usually work in a logic workflow topology, interacting with other functions. This is present in several common application patterns, including function chaining (where a sequence of functions executes in a specific order), fan-out (where a function calls multiple functions in parallel), and fan-in (where a function waits for multiple functions to finish) [39]. We define such functions using $T$-lagged co-occurrence rate ($T$-COR), derived from COR in § 3.2. $T$-COR is the COR between the target invocation sequence and an $T$-time-lagged invocation sequence of its candidate functions (those sharing an application/user). The lagged COR can better reflect how the invocation of candidate functions indicates near-future invocations of the target function. If the $T$-COR reaches a threshold (practically 0.5, $T \le10$), the candidate invocation is an important predictive indicator, and these two functions are linked. A function can have multiple linkages with different functions, including categorized and uncategorized ones.

• D3. Possible functions are infrequently invoked but have at least one mode of WTs (appears more than once). By taking the modes as predictive values, it is possible to predict invocations, though such prediction is deemed to be insufficiently satisfactory.

If any of the three strategies yields both the least cold starts and the minimum wasted memory during validation, the indeterminate function is directly assigned accordingly. Otherwise, the rate of rise is decided. Denote the cold starts of the above three strategies as $(cs_1, cs_2, cs_3)$ and the corresponding wasted memory are $wm_1, wm_2, wm_3$. Assume definition D1 delivers the minimum cold starts while strategy D2 delivers the minimum wasted memory. We compute the rise rates: $\Delta cs = (cs_2 - cs_1)/cs_1$ and $\Delta wm = (wm_1 - wm_2)/wm_2$. If $\Delta cs \times\alpha\leq\Delta wm$, then the function is assigned to D1, i.e. “plused”; otherwise, D2 prevails, where $\alpha\in(0, 1)$ is a scaling factor, and the smaller $\alpha\in(0, 1)$, the more importance is put on cold starts than wasted memory.

Most functions have been categorized so far, except those that have never been invoked in the validation. We simply leave them as “unknown” since they are likely very infrequently invoked and hardly have meaningful predictive indicators. Some unknown functions may be categorized during the online provision based on our adaptive strategies illustrated in the next section (§ 4.1.3).

Adaptive Strategy Application

This section designs two adaptive strategies to handle concept shifts during the online provision: one adjusts the predictive values; the other is based on inter-function correlation. These strategies can further address some unknown or unseen functions (those that never appear in the training data) with meaningful patterns during the online provision. The application of these strategies is also presented in Figure 8, where the invocation prediction and the prediction values are adaptively updated upon online invocations.

i) Adjusting: This adaptive strategy contains three steps:

1. S1. Record the WTs during the online provision. If there are enough WTs, then initiate the adaptive updating.

2. S2. Update the predictive values if the corresponding values computed from newly collected WTs change significantly with the mean of the old and new ones.

3. S3. If the new WTs for an unknown or unseen function conform to previous definitions with enough samples, categorize the function as the corresponding type.

S2 requires more explanations. We record the predictive values for four types: “regular”, “appro-regular”, “dense”, and “possible”. Their predictive values are the median, the first $n$ modes, the range of the first $k$ modes, and the WT values occurring more than twice, respectively. Take “regular” as an example. Suppose the absolute difference between the median of offline WTs (i.e. the predictive value) and that of online WTs is larger than the standard of offline WTs. The new predictive value is updated by the mean of the old median and the new median. Other types adopt a similar adjusting strategy.

ii) Online correlation: This strategy correlates unseen functions with known functions or appeared unseen functions, as the “correlated” strategy does. To speed up the computation and obtain informative indicators, we only consider candidate functions sharing the same trigger with the target function (aka. unseen function). Initially, if one of the candidates is invoked, we also pre-load the target function. Afterward, we gradually remove less correlated candidates. Again, we adopt COR to measure the degree of correlation. We count the pair-wise target-candidate COR at each slot and record the maximum. If the difference between a COR and the maximum is large enough, the corresponding candidate is kicked out from consideration unless its COR returns close to the maximum.

Next Invocation Prediction and Provision

This section predicts invocations and pre-loads functions based on the predictive values or indicators. “(Appro-)regular” functions have discrete predictive values and “dense” functions use continuous ones. In terms of “possible” functions, if the range of predictive values is larger than a threshold, the values are regarded as discrete; otherwise, we consider continuous integers inside the range of predictive values. The predicted invocation times are naturally the last invoked time added by each of the predictive values.

For the online provision, if one of the predicted invocation times falls in $[t-\theta_{prewarm}, t+\theta_{prewarm}]$ with a pre-defined parameter $\theta_{prewarm}$ at the time of $t$, the function will be pre-loaded. If a loaded function’s current WT is $\ge\theta_{givenup}$, the function will be evicted from the memory, where the parameter $\theta_{givenup}$ differs among function types. Algorithm 1 shows our provision optimization, which is rule-based with good scalability and implements our defined strategies faithfully. Every time the algorithm returns the updated MemSet, based on which we load function instances.

Workers Load Balancing

We apply a greedy algorithm to select the server to load in order to optimize load balancing. Upon a new function to load, our policy selects the server with the most idle memory. If the remaining space is enough to accommodate the function, this function can be easily loaded. However, if the remaining space is not enough (smaller than the required memory size of the target function), we will evict the functions in this server according to the policy introduced in § 4.3. Under an extreme circumstance where all the functions of this server that are predicted not to be invoked in the next moment are evicted, this function still cannot be accommodated, this server will be given up, and we will choose the next server—which has the most remaining space among other servers. The process will be repeated until reaching the last server. Note that it is impossible for a function to be loaded according to our primary assumption built on practical expertise.

Algorithm 1: The provision algorithm of SPES-Ext.

Input: FList: hash ids for all functions;
FState: recording the necessary information about all functions, such as the current WT, history WTs, predictive values, the time of the last invocation, etc;
Invo(t): invocation numbers of each function at the time of t;
InvoSet: set of functions that are invoked at current minute;
ColdSet: set of functions that are invoked but not loaded;
PrewarmSet: set of functions that need to be preloaded but have not yet been loaded;
PendSet: set of functions that are loaded but not invoked currently;
UnloadSet: set of functions that need to be unloaded;
UCorr: the correlations of unseen functions.
WPool: set of functions that are currently loaded in the worker pools.

Output: The updated InvoSet, ColdSet, PrewarmSet, PendSet, UnloadSet, FState and UCorr

1 Function Provision(FList, FState, Invo(t), InvoSet, ColdSet, PrewarmSet, PendSet,
  UnloadSet, UCorr, WPool):
2   for f ∈ FList do
3     if Invo(t)[f] > 0 then
4       InvoSet.add(f);
5       FState[f].last_invoked ← t;
6       FState[f].update_WTs(FState[f].current_WT);
7       FState[f].current_WT ← 0;
       // Adaptively adjusting predictive values.
8       FState[f].update_predictive_values(t);
9       if f is not loaded then
10        FState[f].cold_start_record(t);
11        ColdSet.add(f);
12      else
13        FState[f].current_WT += 1;
14        pre_load_flag ← FState[f].pre_load(FState[f].θ_prewarm);
15        if pre_load_flag is False AND FState[f].current_WT ≥ FState[f].θ_givenup then
16          UnloadSet.add(f);
17        else if pre_load_flag is True then
18          PrewarmSet.add(f);
       // Adaptively processing unseen functions.
19    UCorr.update();
20  Unload all the functions in UnloadSet;
21  PendSet ← WPool.difference(InvoSet);
22  PrewarmSet ← PrewarmSet.difference(InvoSet).difference(PendSet);
23  Sort PrewarmSet by memory in decreasing order;
24  Sort InvoSet by memory in decreasing order;
25  return InvoSet, ColdSet, PrewarmSet, PendSet, UnloadSet, FState, UCorr

Eviction Decision

This section considers the extended memory-limited scenario and answers the second question at the beginning of this chapter – which functions should be evicted when workers are out of memory.

Functions to be Loaded and Evicted

At the start of each minute, two sets of function candidates are considered for loading. The first set, denoted by the Cold Set, includes functions requested by downstream services that have not yet been loaded and must be immediately available for invocation. The second set, referred to as the Prewarming Set, consists of functions predicted by SPES to be beneficial for prewarming, even though they will not be invoked within the current minute. The loading process begins by prioritizing the Cold Set to ensure that there is enough space for all necessary functions. After that, the remaining space is prepared to arrange the functions in the Prewarming Set for potential future invocations. Loaded functions without invocations at this minute are grouped in the Pending Set. Only the functions in this set are considered to be evicted at the beginning.

We assume that the space allows all invoked functions to be loaded within one minute. In practice, when the theoretical capacity for function invocations is exceeded—such as during periods of high user demand—serverless providers typically respond by dynamically scaling their infrastructure. This scalability enables providers to increase supply and, in turn, generate more profit, thereby maintaining a balance between supply (memory and infrastructure) and demand (user requests), resulting in more available resources for concurrent function executions.

Eviction Policy

A fundamental principle is that when there is insufficient memory to load all the functions in the Cold Set or the Prewarming Set, it is required to evict the functions in the Pending Set. Consequently, we assign priorities to the functions in the Pending Set. The priorities are formulated on the basis of the previously calculated prediction values (which are directly related to the timing of the next invocation) and the memory occupied by the functions. Apparently, those functions with larger prediction values (which means they will be invoked later) and larger memory occupation (which means they may waste more resources) are supposed to have a higher priority in being evicted.

Specifically, we first evict functions predicted to have a long idle time. In each minute, the prediction value of each function is updated to predict the next invocation time. According to the previous function categorization, “warm”, “successive”, and “pulsed” functions have a high probability to be invoked at $(t_i + 1)^{\mathrm{th}}$ min after invocations at $t_i^{\mathrm{th}}$ min. Prediction values of functions categorized in other types may fall into an interval, and the lower bound of this interval is taken as the prediction value when calculating the priority. For functions with an equal prediction value, those with larger memory will be evicted first.

Once there is not enough space and we must trade-off functions in the Pending Set and the Prewarming Set, we first keep the functions in the Pending Set that are predicted to be invoked in the next minute. Afterward, we union these two sets and sort them by their confidence scores. The scores are defined by their function types and standard deviations of prediction values.

The confidence scores of the functions are defined as shown in Figure 9, following the order of the function categorization. As previously discussed in § 4, the reliability of predicting the next invocation decreases as we move from the first category to the last, with high-frequency calls being the most predictable, and finally “unknown” calls, which exhibit the least predictable behavior. Thus, functions with a higher degree of predictability should be given a higher confidence score in their likelihood of future invocation, thus making them less likely to be evicted. This approach ensures that more reliably invoked functions remain warm, thereby reducing cold start latency and optimizing system performance in a resource-constrained environment.

Image not extracted

In the eviction process, we first evict the function types with lower confidence. For the functions that fall into the same type, we sort them by standard deviations and evict the ones with larger deviations. This is reasonable since larger deviations mean they fluctuate more dramatically which may lead to inaccurate predictions with higher probabilities.

Figure 10 depicts the workflow of our priority-aware eviction policy. Algorithm 2 shows our eviction and load-balancing algorithm for SPES-Ext.

Image not extracted

Evaluation

Workload. We evaluate SPES and SPES-Ext on the most widely used industrial dataset [40] released by Microsoft Azure Function [13] with real-world invocation traces. The dataset contains the invocation counts per minute for 14 days. The first 12 days are used for pattern modeling (training), and the last two days are used for the simulation, conducted in a container with 32-core Intel Xeon(R) Platinum 8360H CPU and 256 GB memory. The records involve 15,097 users, 24,964 applications, and

Algorithm 2: The eviction and load-balancing algorithm of SPES-Ext.
1 Function Eviction and Load-balancing(FList, FState, InvoSet, ColdSet, PrewarmSet, PendSet, UnloadSet, WorkerList):
2     ColdSet ← sorted (ColdSet, key = lambda f: FState[f].memory, reverse = True);
3     PrewarmSet ← sorted (PrewarmSet, key = lambda f: FState[f].memory, reverse = True);
4     cold_flag ← True;
5     prewarm_flag ← True;
6     for f in ColdSet do
7         WorkerList ← sorted (WorkerList, key = lambda w: w.space, reverse = True);
8         if CanLoad(WorkerList[0], f) then
9             Load f into worker;
10        else
11            cold_flag ← False;
12            RMColdSet ← Remaining ColdSet;
13            break;
14    if cold_flag is True then
15        for f in PrewarmSet do
16            WorkerList ← sorted (WorkerList, key = lambda w: w.space, reverse = True);
17            if CanLoad(WorkerList[0], f) then
18                Load f into worker;
19            else
20                prewarm_flag ← False;
21                Unload previous PreWarmSet functions;
22                break;
23    if cold_flag is False OR prewarm_flag is False then
24        for func ∈ RMColdSet do
25            for each worker by memory decreasing order do
26                if func.memory ≤ remaining space of the worker OR CanEvictForCold(PendSet, func) then
27                    Load func into worker;
28                    break;
29        for func ∈ PrewarmSet do
30            for each worker by memory decreasing order do
31                if func.memory ≤ remaining space of the worker then
32                    Load func into worker;
33                    break;
34                else
35                    if get_min_t(PendSet) > t_i + 1 AND func.memory > remaining space of the worker then
36                        if CanEvictForPrewarm(PendSet, func) then
37                            Load func into worker;
38                            break;
39            if for all workers get_min_t(PendSet) ≤ t_i + 1 AND there’s not enough space for func then
40                Unload previous PreWarmSet functions;
41                Tradeoff (PendSet, PrewarmSet);

83,137 functions. 71,616 functions appear in the training data, 39,388 functions appear in the simulation data, and 743 never appeared during training.

Assumptions. We adopt the simulation principles following [13]. First, assume all executions finish within one minute since 1) most (96%) functions have very short execution time (less than 60 seconds), and 2) we can thereby calculate the worst-case wasted resource time. Second, we assume that cold-start latency for each function is the same, so we only need to care about the number of cold starts and the wasted memory time.

Since the dataset only contains the memory of the app, to evaluate under a memory-constrained scenario, we evenly split the memory allocation among all functions in an application following [15]. For the functions that only appear in the simulation, we assign them the average memory of all applications, split among all functions.

Evaluating SPES Without Memory Limitation Under Single-Worker Scenario

We evaluate SPES by answering four research questions:

• RQ1: How effectively does SPES decrease cold starts?

• RQ2: How much memory waste and computation overhead does SPES incur?

• RQ3: How does SPES trade off memory waste with latency reduction?

• RQ4: How do complementary designs influence SPES?

Baselines

We compare SPES with five state-of-the-art baselines applied to the application layer. Approaches involving system renovations are out of this paper’s scope and will be discussed in § 6. Our baselines include FaaSCache [15], Defuse [20], Hybrid [13], and a fixed keep-alive policy. We reproduce these methods as they do not provide open-source code by strictly following the original papers and referring to a reproduction attempt [41]. Note that the original Hybrid method works at the application unit (Hybrid-Application, HA), so we derive a Hybrid-Function method by employing its design on the function granularity (Hybrid-Function, HF), following [20]. All the parameters are set according to their original papers. The fixed keep-alive policy adopts a length of 10 minutes. FaaSCache requires a pre-defined memory limit, so we adopt the maximum memory size of SPES during the whole simulation.

Metrics and parameters

To quantify the cold-start optimization, we measure the function-wise (application-wise for HA) cold-start rate ($CSR$), i.e. the number of cold starts divided by the number of invocations. We apply wasted memory time ($WMT$, § 2.2) to gauge the idle resource waste. Naturally, the lower the $CSR$ or $WMT$, the fewer cold starts or wasted resources, the better.

We also monitor the effective memory consumption ratio ($EMCR$), which measures the fraction of invoked function instances relative to the total loaded instances on each host machine, serving to assess resource efficiency. A higher EMCR signifies wiser memory allocation, as it indicates a greater proportion of memory is used by active instances rather than remaining idle. As for the parameters, we set $\theta_{\mathrm{prewarm}}$ as two. The $\theta_{\mathrm{givenup}}$ for “dense” and “pulsed” is five, whereas one for the other types. § 5.1.5 further discusses the impact of these pre-defined parameters.

RQ1: Effectiveness in Cold-Start Reduction

Figure 11 displays the cumulative distribution (CDF) of CSR under the provision decisions of SPES and baselines. With a fixed y-axis value, the line representing SPES is positioned to the left of other baseline lines, which indicates that SPES consistently leads to fewer cold starts across a variety of functions, each corresponding to different invocation frequencies. In particular, SPES reduces the 75th percentile cold-start rate (Q3-CSR, for simplicity) from 0.215 to 0.108 compared to Defuse, the best-performing baseline, achieving 49.77% improvement, and reduces 75-CSR by 64.06%–89.20% compared to other baselines. We care more about Q3-CSR because infrequently invoked functions benefit most from optimization [13]. Moreover, 57.99% functions experience no cold starts with SPES, indicating that SPES can allow most functions to be warmly invoked. In contrast, 25.61%–52.59% functions completely experience warm startup using baselines where FaasCache is the best one. On the other hand, regarding infrequently invoked functions, SPES reduces the 90th percentile CSR by 19.87% compared to the best-performing baseline, HA. Such improvements imply that SPES exhibits significant optimization performance for both frequently and infrequently invoked functions, while no baseline can achieve second-best performance with different percentile CSRs.

Image not extracted

Furthermore, SPES significantly reduces “always-cold” functions, which always experience cold starts upon invocations (with CSR equal to 1.0). Figure 12(b) further presents the always-cold percentage, and that of SPES is just less than 8%. Among the baselines, HA has the fewest always-cold functions, which is closest to that of SPES, whereas Defuse and HF, both function-grained methods, increase always-cold functions dramatically. This can be attributed to infrequently invoked functions. About 3.82% functions are invoked less than twice during training, and 6.14% are only once during the simulation, so always-cold functions seem inevitable with limited records. HA mitigates this issue by grouping and loading functions together, yet resulting in more memory consumption and waste. SPES instead connects unseen and unpredictable functions with known functions using trigger, application, and user information and gradually updates the associated functions based on actual invocations. Hence, without much extra memory, SPES performs close to HA.

Image not extracted

In addition to cold start reduction, Figure 12(a) presents the memory usage normalized by the averaged one of SPES. SPES’s memory usage is only 8.08% more than the most resource-efficient method, the fixed keep-alive policy, and saves 36.07%–55.55% memory compared to the other baselines on average. It only consumes about half of the memory of Defuse, the best baseline for cold start reduction.

Figure 13 shows the averaged CSR among different types. As the simulation period is not long enough, we only categorize unknown functions into the type of “possible”, denoted by “newly-possible”. We can see that “unknown” functions contribute the most to cold starts, and “pulsed” functions also incur high CSRs. This is attributed to insufficient historical invocation records. Actually, SPES intentionally connives a cold start when an “unknown” or “pulsed” invocation arrives after a long idle time. Though we can leverage less predictive information, such as the averaged WT, to predict the next invocation or even keep such functions always warm, this can lead to considerable unbillable and wasted memory, undesired for FaaS providers. This outcome is deliberating on the trade-off between performance and resource allocation. Such an issue can be mitigated with more invocation histories revealing predictive indicators for better provision.

Meanwhile, though “correlated” and “possible/newly-possible” functions also lack predictive information with infrequent invocations, their invocations are more likely to be predicted. Thus, we connect some of them with deterministic functions or adaptively extract meaningful behavior indicators from incoming invocations. In this way, their cold starts are suppressed effectively. We will further discuss the usefulness of such strategy designs in § 5.1.6.

RQ2: Wasted Memory Time and Overhead

Waste Memory Time. Figure 14(a) presents that SPES significantly decreases the wasted memory time by 10.89%–63.50% compared to all baselines. Particularly, compared to Defuse, the most effective baseline on cold-start reduction, we reduce 57.06% of the WMT. Figure 14(b) also demonstrates that SPES efficiently uses memory resources, whose EMCR is 46.32%, 5.20%–120.89% higher than compared approaches. The success of SPES can be attributed to careful pattern modeling and differentiated strategies.

Image not extracted

Figure 14: SPES significantly reduces memory waste and achieves more effective memory consumption.

Image not extracted

To further demonstrate how each type contributes to WMT, we derive a metric called the ratio of WMT, which is the WMT divided by the number of invoked times for each serverless function. If a type contains more functions or function invocations, the bespoke scheduling strategy tends to make more proactive provisions, likely resulting in more WMT. Thus, the ratio of WMT can better portray the accuracy of invocation prediction and the usefulness of pre-loading. Figure 15 shows the distribution of the ratio of WMT among different function types, from which we can see the “possible” functions have the highest probability of generating WMT. The predominant reason for this is the infrequent invocation of possible functions, which leads to a scarcity of patterns in the historical database and complicates establishing associations with other functions. Despite these challenges, we persist in our efforts to forecast and pre-warm the invocation of these functions, aiming to reduce cold starts as much as possible. Different from “pulsed” or “unknown” functions that are allowed to generate cold starts, we encourage aggressive prediction attempts for “possible” functions since the latter have at least a duplicated WT, enabling potential predictive value obtaining. However, this strategy unavoidably results in augmented resource wastage.

Image not extracted

SPES Overhead. Herein, we measure the additional latency induced by our implementation. The time complexity within each time window of our approach and the fixed keep-alive policy is $O(n)$, where $n$ represents the number of functions, as it only requires accessing the corresponding function’s category and its predictive value(s). For each invocation, the time complexity of pre-load/unload operations is merely $O(1)$. Within each time window, the time complexity for the fixed keep-alive method is $O(m)$, where $m$ is the number of loaded functions. In contrast, FaaSCache has a time complexity of $O(\log m)$, which involves identifying the container with the lowest priority. Other methods, such as HA, HF, and Defuse, have higher complexities, mainly due to the computational bottleneck in updating histograms. The simulation results align with these expectations. Compared to the fastest fixed keep-alive baseline, which has an average overhead of 0.024 sec per minute, our method adds 0.44 sec’s overhead per minute, mainly due to our more complex strategies for each provision action. Contrasted with the second fastest, FaaSCache, our overhead is reduced by 6.8%. In summary, our overhead is inconsequential compared to the typical latency found in most existing serverless platforms.

RQ3: Trading-off resources and latency

We control the trade-off through two parameters: $\theta_{\mathrm{prewarm}}$ and $\theta_{\mathrm{givenup}}$. As introduced in § 4.1.4, the former decides how long to pre-load a function with a predicted nearby invocation, and the latter decides how long to keep an idle function warm. Intuitively, the larger these two parameters, the more likely a function is to pre-load or keep loaded with more memory usage and potential wasted memory, and the less cold starts. In RQ1 (§ 5.1.3), we set $\theta_{\mathrm{prewarm}}$ as two, and the $\theta_{\mathrm{givenup}}$ for “dense” and “plused” is five, whereas one for the other types. Our original simulation setting is denoted by the red star ($\star$) in the following figures.

Figure 16(a) shows the trade-off under different $\theta_{\mathrm{prewarm}}$, where a point $(x,y)$ represents using $x$-unit memory and obtaining the 75-CSR of $y$, under a certain $\theta_{\mathrm{prewarm}}$.

Image not extracted

The memory is normalized to that under the original setting. Normalized memory usage and 75-CSR are nearly linearly correlated. We can conveniently choose a proper setting by controlling $\theta_{prewarm}$. Since the red star is below and the most distant from the fitting line, $\theta_{prewarm}=2$ is the optimal value.

As $\theta_{givenup}$ should be integers and different from each type, we simply multiply the original $\theta_{givenup}$ setting by 2, 3, 4, and 5, respectively. The results are shown in Figure 16(b), where the linear relationship remains approximately the same, but larger $\theta_{givenup}$s have less impact on the reduction of cold start. This indicates that keeping invoked functions too long is sub-optimal and idle functions should be evicted promptly.

RQ4: Impact of Strategy Designs

Impact of inter-function correlations. This section gauges our design in processing ill-informed functions by developing inter-function correlations. As introduced in § 4.1.2, we propose a simple yet effective $T$-lagged co-occurrence rate metric to connect ill-informed functions with categorized ones. Those with closely related known functions are “correlated”. This strategy is applied during both training and simulation. Figure 17 presents the impact of this strategy. w/o Corr means re-categorizing “correlated” functions into “pulsed”, “possible” or “unknown” during training, but we still deal with unseen functions during the simulation. w/o Online-Corr denotes removing the simulation-applied strategy, i.e. regarding unseen functions as “unknown” but still retaining the “correlated” functions obtained during training. It is shown that the latter strategy slightly reduces the Q3-CSR, whereas the former makes a significant contribution. We attribute the results to the influence of the function number. 4.71% of the functions belong to “correlated” whereas only 1.89% are unseen.

Image not extracted

Impact of designs regarding concept shifts. This section studies the impact of two designs regarding concept shifts: 1) forgetting: forcing unknown functions to a defined type by ignoring older invocations while focusing more on recent data (§ 4.1.2); 2) adjusting: adaptively adjusting the predictive values during the simulation (§ 4.1.3).

Figure 18 depicts the effectiveness after omitting these two adaptive designs, respectively. Removing the second shifting strategy has a slight impact. Similarly, this is attributed to the fact that the forgetting strategy involves more function categorization efforts. We do not pre-load unknown functions, so the forgetting strategy categorizing 340 unknown functions has a larger impact. In contrast, the adjusting strategy only categorizes 174 unknown functions into the “newly-possible” type and updates the predictive values of 499 “(appro-)regular/dense” functions, resulting in less impact. Nevertheless, both designs contribute to the effectiveness of SPES. These designs will play a greater role with more data and a longer simulation period (usually indicating larger shifts).

Image not extracted

Evaluating SPES-Ext With Memory Limitation Under Multi-Worker Scenario

We evaluate SPES-Ext by answering the following research questions:

• RQ5: With memory limitation and multiple workers, how effectively does SPES-Ext decrease cold starts?

• RQ6: With memory limitation and multiple workers, how effectively does SPES-Ext balance the server load?

• RQ7: With memory limitation and multiple workers, how much memory waste and computation overhead does SPES-Ext indeed incur?

• RQ8: How does the balancing policy contribute to SPES-Ext?

• RQ9: How does the number of workers influence the results?

Baselines

Given that SPES-Ext integrates three novel components (provision policy, eviction decision, and load balancing) and no existing solution combines all three aspects, we adopt a component-wise comparison approach.

Provision Policy. To compare with SPES-Ext, we use the five state-of-the-art baselines mentioned in § 5.1.1 as the provision policy of the baseline scheduler.

Eviction Decision. For schedulers lacking explicit multi-worker eviction mechanisms (excluding FaaSCache which employs priority-based eviction), we implement first-in-first-out (FIFO) eviction: functions are evicted based on loading time (oldest first), and currently invoked functions are protected from eviction. On the other hand, SPES-Ext extends traditional FIFO eviction by applying priority-based eviction to PendingSet and PrewarmSet (§ 4.3) and employing FIFO for worker pool eviction to maximize idle memory utilization.

Load Balancing. Following [42], we compare SPES-Ext with four common baselines:

• Hashing scheduler. This is the OpenWhisk default scheduler. In our experiment, we calculate a hash value for each function and map it to the corresponding worker.

• Round-robin scheduling. With this method, workers take turns to load the coming functions.

• Least-loaded scheduling. In this scheduler, we always distribute the incoming invocation to the server with the least load.

• Most-loaded scheduling. This is the scheduling strategy of AWS Lambda. We utilize the same server greedily to load the coming functions. If it reaches its capacity, we turn to the next server.

This selection process yields 20 distinct baseline combinations. To maintain clarity in our presentation and discussion, we adopt the following representative strategy: For each provision policy, we identify the optimal combination of components (provision policy + eviction decision + load balancing) and use this configuration as the canonical representation of that policy class. For instance, if the FaaSCache/Hash combination demonstrates superior cold start mitigation compared to alternative FaaSCache pairings (Round Robin, Least Loaded, Most Loaded), we only exclusively report and analyze the FaaSCache/Hash results as the representative case for all FaaSCache-based configurations.

Metrics and parameters

To comprehensively evaluate system performance, we augment the baseline metrics from § 5.1.1 with an extra Normalized Worker Variance (NWV) metric for load balancing assessment. NWV is computed as $NWV = \frac{\sigma_{mr}^{2}}{\mu_{mr}}$, where $\sigma_{mr}^{2}$ represents the variance of workers’ remaining memory and $\mu_{mr}$ denotes the mean remaining memory at minute-level intervals. This normalization eliminates bias from absolute memory availability, focusing instead on relative distribution efficiency.

We set the server memory configuration following the two critical constraints. The upper bound is that the memory must be constrained to properly evaluate provisioning policy effectiveness under resource competition. The lower bound is that the memory must be adequate to handle peak historical demand without triggering invocation queuing. This is because we decouple the invocation allocation problem from the queuing problem for greater clarity, according to Occam’s Razor principle. Therefore, we set the total memory of servers as $1.1 \times\lceil\max(M_{\mathrm{hist}}) \rceil$ where $M_{\mathrm{hist}}$ represents historical memory demand. The 10% buffer ensures reliable operation while maintaining evaluation stringency.

The number of workers in our experiment is set to six. We will discuss the impact of the server count in § 5.2.7.

RQ5: Effectiveness in Cold-Start Reduction

Figure 19 presents the comparative analysis of cold start rate (CSR) distributions between SPES-Ext and baseline schedulers using cumulative distribution functions (CDFs). The leftward shift of SPES-Ext’s CDF curve demonstrates its consistent superiority in cold start mitigation.

Image not extracted

To be more specific, regarding infrequently invoked functions, on a function-wise level, SPES-Ext reduces the 75th percentile cold-start rate (Q3-CSR, for simplicity) from 50% to 10% compared with FaasCache, the best-performing baseline, achieving 80% improvement. Compared with other baselines, our policy reduces the Q3-CSR by 81.25%-90%. Furthermore, our policy reduces the 90th percentile cold-start rate by 9.76% from 100% of all other baselines. For warm-start functions, 57.94% of the functions don’t experience cold starts under our policy, which indicates that most functions can be invoked with warm startup. Meanwhile, for the baselines, only FaasCache has a 1.54% higher proportion than SPES-Ext, while for others,the proportion of warm start functions varies from 5.78% to 16.80%. These demonstrate that under such a scenario, our policy can utilize the limited memory to significantly improve cold start latency for both frequently and infrequently invoked functions.

Additionally, Figure 19 displays that our policy greatly reduces the percentage of “always cold” functions, i.e. functions with CSR equal to 100%. Under SPES-Ext policy, only 7.65% functions experience a cold start every time they are invoked. Among the baselines, HA has the fewest always-cold functions, which is closest to that of SPES-Ext, whereas HF, the function-grained method, increases always-cold functions dramatically. This can be attributed to infrequently invoked functions. About 3.82% functions are invoked less than twice during training, and 6.14% are only once during the simulation, so always-cold functions seem inevitable with limited records. HA mitigates this issue by grouping and loading functions together, yet results in more memory consumption and waste than HF. However, each application contains fewer than 3 functions on average, so it doesn’t cost much more. SPES-Ext instead connects unseen and unpredictable functions with known functions using trigger, application, and user information, and gradually updates the associated functions based on actual invocations. Hence, SPES-Ext performs even better than HA with less memory.

Although the upper limit of the memory is fixed for these methods, the actual memory usage varies. Figure 20 shows the memory usage normalized by the one of

Image not extracted

SPES-Ext. The memory usage of SPES-Ext is 68.08% less than Defuse, which is the most space-efficient. Compared with other baselines, SPES-Ext saves 75.49%-79.95% memory. FaaSCache, the best baseline in cold start alleviation, consumes 4 times more memory than SPES-Ext.

RQ6: Load Balancing Effect

Since there are many provision and load-balancing policy combinations, we compare and show the best combinations in each type of provision policy, which means the combination with the lowest mean variance. For example, HF-LeastLoaded has a lower mean variance than HF-Hash, HF-RoundRobin, HF-MostLoaded, so we choose HF-LeastLoaded as the representative of all HF combinations when measuring load balancing effect.

As Figure 21(a) and 21(b) present, the normalized variance of SPES-Ext remains under 30 in the 2880 minutes, which lowers the baselines mean variances by 52.49% - 96.14%. Particularly, FaaSCache-MostLoaded has the highest mean variance and HA-LeastLoaded has the lowest. Among the baselines, three of five baselines have the best performance when combined with LeastLoaded, indicating that loading into the worker with the largest space first can help balance the load. The load balancing policy of SPES-Ext also utilizes this, and it sorts the loading set first and prioritizes the loading of the function with the largest memory, which tries to coordinate the balance from the size of the functions. This further improves the load-balancing effect.

Image not extracted

RQ7: Wasted Memory Time and Overhead

Figure 22(a) illustrates the wasted memory time of all methods under a memory-constrained scenario. Our method SPES-Ext significantly decreases the wasted memory time (WMT) by 83.92%-88.82% compared with other baselines. Among the baselines, FaaSCache wastes most memory time while it is most effective on cold-start reduction, indicating that it trades memory resources for efficiency.

Image not extracted

Figure 22(b) presents that SPES-Ext has a high EMCR of 49.61%, which is 24.10%-293.19% higher than the baselines. Particularly, Hybrid-Function(HF) has the highest EMCR but the worst cold start, which means that it doesn’t load either useful functions or useless functions and inefficient loading leads to a high EMCR but also a high cold start rate.

The contribution of balancing policy to SPES-Ext

We perform a component-wise analysis by isolating the load balancing policy while maintaining SPES-Ext’s other components (provisioning and eviction policies). This ablation study replaces only the balancing module with alternative strategies from baseline schedulers.

We analyze the results from three aspects. For cold start alleviation, Figure 23a reveals that SPES-Ext has a marginal but consistent 9.9% reduction in Q3-CSR across all baseline variants. It also achieves an equivalent performance at the 90th percentile and for always-cold rates. In terms of memory efficiency, as quantified in Figure 23b, SPES-Ext consumes no more than 0.11% WMT than baseline balancers. For load distribution analysis, Figure 23c demonstrates that extreme variance is observed in baseline strategies. SPES/Most-Loaded has the largest variance and SPES/Least-Loaded has the least variance among the baselines, which are respectively $1.1\mathrm{e}6\times$ and $4\mathrm{e}3\times$ larger than SPES-Ext on average.

The experimental results confirm that our load balancing policy provides significant load variance reduction (up to 6 orders of magnitude) and consistent cold start improvements without introducing substantial memory waste.

RQ9: The influence of the number of workers

We compare the cold start performance of SPES-Ext with the same total memory but a different number of workers. Figure 24(a) demonstrates that the number of workers has minimal impact on the function cold start latency, which is reasonable because both the total memory and the provision policy remain the same. Figure 24(b) shows that they has similar memory waste, where the setting with 10 servers has most memory waste and setting with 6 servers has the least, while the latter is only 0.07% more.

Image not extracted

Regarding the load balancing effect, as shown in Figure 24(c), the normalized variance of workers is proportional to the number of workers. The mean value of normalized variance varies from 0.20 to 19.17 as the number of workers increases from three to thirty. An intuitive reason is that it’s more difficult to balance the worker load when the number of workers is larger. Meanwhile, since the total space of all workers is fixed, to ensure that the worker can hold functions with a large memory that may not appear in the history, the number of workers should not be too large in our experiment. Hence, considering the analysis above, we choose the worker count as six.

Image not extracted

Image not extracted

Image not extracted

Discussion

Limitations

Idealized Simulation Principles

Our simulation adopts two key assumptions to simplify the process and mitigate dataset limitations. Firstly, we assume each function execution completes within one minute. For functions with longer execution, adjusting the counting unit as necessary to accommodate the vast majority (e.g., 95%) of functions within this timeframe can ensure the assumption’s relevance. For functions exceeding this one timeframe without new invocations—e.g., for a two-minute execution without activity in the second minute—we maintain memory allocation and increment the WMT despite no memory being actually wasted. Such deviation can particularly underestimate resource efficiency, especially for methods with frequent evictions, including ours and HF. Thus, we posit that such marginal deviations do not affect the overall integrity of our experimental findings. Secondly, we assume all functions share the same cold-start latency. Our focus on function-specific metrics means that variations in cold-start latency across functions do not significantly affect our primary research insights, though a more detailed dataset could enhance our analysis of the aggregate cold-start latency and offer a deeper comparison of methodologies.

Over-simplicity of memory consumption

We mainly make three assumptions about the memory consumption. First, we regard all function instances of the same applications as equally consuming the average memory limited by the data without function-wise memory consumption. They actually require different memory allocations, yet the assumption is still reasonable as these functions are usually responsible for simple tasks with confined memory size [20, 43].

In addition, we simply assume that the workers can simultaneously load all the invoked functions in each minute, and thus it does not lead to function queueing problem. Otherwise, we should consider not only the cold start latency but also the queueing delay, which involves tradeoffs among loading different functions.

Furthermore, we make the assumption that when a function has multiple concurrent invocations, they have the same priority and can take turns to execute in the same container within one minute. If multiple containers are required for concurrent invocations, we may underestimate the memory consumption of frequently invoked functions and need to decide the provisioning of nearly identical containers [15].

Ignorance of the worker dynamics

We simply assume that the count and capacity of workers are fixed throughout the experiment, so we don’t involve worker autoscaling. If autoscaling is considered like [44], the number of invokers and invoker memory should autoscale in response to changes in workload demand. We plan to design a more elastic scheduler that covers the autoscaling module and refines our current design to optimize under different scales.

Threats to Validity

Internal

The evolution of serverless functions is very fast. With only 14-day data, we can observe distinct concept shifts in function invocations. We currently do not conduct proactive re-categorization or rule generation. The performance of SPES-Ext may degrade in the very long term. To mitigate this threat, we design adaptive strategies to handle relatively small shifts, which can easily be extended to long-term shifts.

External

The effectiveness of SPES-Ext on other datasets is yet unknown. To alleviate this concern, we choose Azure Function, the most widely used dataset from real-world industry, whose representativeness has been confirmed by many studies [13, 20, 42, 46] [45]. Moreover, it is the only publicly available industrial dataset. We will strengthen cooperation with the industry to evaluate SPES-Ext on more datasets and prompt the implementation of SPES-Ext on a real-world FaaS system. We also release our code to facilitate reproducibility and more experiments in the community.

Related Work

Cold Starts Alleviation. Numerous efforts [13, 15, 17, 20, 35, 42, 47, 48, 49] have focused on minimizing cold starts and memory overhead for FaaS platforms. Related studies [19, 50] classify current methods into two categories: speeding up function warming (involving renovations in the system layer) and reducing occurrences of runtime cold starts (at the application layer). Methods of these two categories are orthogonal, so they can be combined for further cold start optimization.

This first category presents new systems to optimize infrastructure and resource management, employing techniques like load balancing among worker nodes [35, 47], snapshotting [14, 51], sandbox (e.g., container) scheduling and management [17, 21, 48, 52, 53, 54, 55]. One of the most popular research directions is sandbox sharing, i.e., sandboxes of the previous execution are reused for new invocations since reusing the idle sandbox incurs less delay than allocating a new one [52]. A recent study, Pagurus [53], proposed a container management scheme that allows one function’s idle warm container to be forked by another function to alleviate cold starts, showing promising results. However, implementing these methods requires significant engineering efforts, system expertise, and ongoing maintenance due to the underlying platform and sandbox modifications, which pose challenges in diverse infrastructures and platforms.

The second category mitigates cold-start occurrences [13, 15, 20, 21, 42, 49] through a non-intrusive way. A primary step of function scheduling is to decide when and whether to pre-load/evict a function instance to reduce cold starts. [13] utilizes a small histogram to monitor function inter-invocation times, benefiting workloads with clear invocation patterns by optimizing keep-alive and pre-warming. However, it is fully data-driven and ignores the underlying invocation patterns, leaving much room for domain-knowledge-involved invocation prediction. Defuse [20] employs dependency mining from function invocation histories to optimize the keep-alive time and pre-warming. Yet, it relies on the statistical histogram and turns to a fixed keep-alive policy for more than 32% of the functions, delivering inadequate perfection of effectiveness. LCS [49] selected the least recently warm container to reduce cold starts by keeping the containers alive for a longer period. FaaSCache [15] innovatively establishes an equivalence between keeping functions alive and keeping objects in a cache, thereby implementing function provision based on Greedy-Dual-Size Frequency object caching. However, its fundamental idea is to use up the given resources as much as possible until they are insufficient, then evict containers to minimize cold starts. Thus, its way of optimizing resources is rigid without any predictions, failing to smoothly optimize cold starts and resource usage simultaneously. This leads to a more significant waste of memory resources.

There is room for improvement in these function provisioning methods, as most of them either lack fine-grained invocation prediction or rely on costly learning models without fully exploiting diverse invocation patterns. Instead, SPES-Ext adopts lightweight horses-for-courses rule-based strategies to enhance existing approaches via accurate invocation prediction. SPES-Ext also proposes adaptive designs and builds up inter-function correlations, delivering better memory-economic cold-start reduction. Other efforts target a downstream task to determine a suitable node for scheduling an individual function request. FaaSRank [42] and ENSURE [21] attempt to pack load on the adequate number of invokers, allowing the additional unneeded invokers to idle, so as to reduce the completion time and cold starts of functions. Our method can be combined with these methods for finer-grained scheduling.

Load Balancing Related Scheduling. There are works that focus on data-aware or resource-aware load-balancing. Package-aware load balancing [56] considers the data locality of software packages by enhancing consistent hashing to avoid worker overload and ensure overall performance. Meanwhile, [57] [56] concentrate on the locality of the data accessed by function invocations. [58] also refines consistent hashing to develop a locality-aware load-balancing policy. It mainly focuses on the locality of in-memory functions regarding how to choose the “home” server of each function, i.e. assigning the invocations of the same function to a certain subset of servers to guarantee locality. Palette [57] is a load balancer, especially for data-intensive applications, that introduces colors as locality hints and route invocations with the same color to the same set of instances. [44] takes the diversity in resource consumption and lifetime of functions into account, and classifies the serverless applications into two broad categories based on their runtime and resource usage. It also involves the multi-invoker scheduling and autoscales the number of hosts when needed. CH-AL [59] enhances consistent hashing by co-locating functions with shared container image layers and forwarding requests based on real-time node load estimation. Hiku [60] proposes pull-based scheduling where idle workers proactively request tasks, achieving function locality and load balance without consistent hashing. Metronome [61] employs an online prediction model to forecast function execution times for locality-aware delay scheduling, distinguishing data locality from infrastructure locality. SPES-Ext is a priority-aware approach that categorizes functions by their invocation patterns so that we can better characterize the workload and prioritize different functions.

Learning-based approach like [42] utilizes deep reinforcement learning to learn function scheduling decisions and select the invokers. However, RL decisions on the pay-as-you-go FaaS platforms may not be a perfect choice since they may consume much more resources and increase the expenditures of users, which may counteract the resources they save. SPES-Ext is rule-based and costs fewer resources with higher efficiency.

Conclusion

This paper proposes a general rule-based and priority-aware scheduler under the memory-limited and multi-worker scenario. Our insight is that typical invocation patterns resulting from the underlying serverless architecture and triggers with commonness can lead to predictive invocation behaviors. The prediction information implies certain function characteristics, making it feasible to prioritize the functions and thus construct scheduling rules. Hence, we propose SPES-Ext, which provisions functions, makes eviction decisions, and balances workers’ load based on categorization and invocation prediction using tailored strategies. Our rule-based and priority-aware solution effectively mitigates the cold start and load-balancing problem by addressing the challenges of efficiency, scalability, imbalance, and evolution. Experiments demonstrate that SPES-Ext significantly improves three sides of the trade-off: economizing expensive resources, reducing cold starts to mitigate latency, and balancing workers’ load. Lastly, we make our code publicly available to facilitate future research and deployment of serverless computing.

Data Availability

The artifact for SPES-Ext is available at https://github.com/HelloWorldGitHubUser/SPES-Ext.