The growth in popularity of serverless platforms is being accompanied by a rapid increase in the variety of applications (apps) being deployed on them [22,36,37,50]. The vast majority (∼96%) of these apps are short-running, with execution times lesser than 30s [65]. This includes apps such as Sentiment Analysis and Audio Translation, which are being deployed in user-facing settings like automated chat moderation for real-time events [8,10,20] and advanced multimedia messaging [13,21,23], respectively. Being user-facing, such apps have been envisioned being administered under strict SLOs in terms of response time requirements [2,27,39,43,55,58,59]. Achieving a low tail latency is also critical for these apps as it is an integral part of the Quality of Service (QoS) delivered to the end-user [26,27,33,34,52,55,56,62].
A significant portion of these apps are composed of one or more functions that process user-provided inputs to produce the desired output [11,12,16,18,35]. Existing work in the area of input-sensitive profiling has shown that many such apps, which we will call Input size-Sensitive apps (IS apps), have execution times that depend heavily on the provided input size [25,31,35,38,41]. This introduces challenges with respect to container provisioning and maintaining a high degree of SLO compliance, that are not currently addressed by state-of-the-art serverless Resource Management frameworks (RM frameworks) in both industry and academia [9,12,16,27,40,43,55]. The two main concerns that arise from this are: • Existing RM frameworks, being agnostic to the input sizesensitive characteristics of the above apps, resort to using the average execution times of their composite functions to determine the number of containers needed during autoscaling decisions. As we will discuss later, this leads to spawning an inappropriate number of containers.
• Incoming requests to the IS app will inevitably have starkly different execution times depending on their corresponding input sizes. Due to having an agreed-upon SLO for the app [27,43], requests with a higher execution time will have a lower 'buffer time' before violating the SLO. Existing RM frameworks do not account for this.
To address these concerns, we propose Cypress 1 , an input size-sensitive serverless RM framework that minimizes resource consumption, while maintaining a high degree of SLO compliance by virtue of its policies that adapt to the distribution of the input sizes associated with the request trace (we will, henceforth, refer to this simply as input size distribution). Two of Cypress's chief policies are Input size-Sensitive Request Batching (IS Batching) and Input size-Sensitive Request Reordering (IS Reordering). IS Batching refers to batching multiple requests onto fewer containers by taking their input size-dependent execution times and respective SLOs into account. IS Reordering reorders requests in the incoming request queue such that requests with higher potential execution times (and typically, higher input sizes) are executed first so as to meet the SLOs of as many requests as possible. These policies are utilized by the scaling services of Cypress, which are: (i) the Proactive Scaler, that deploys containers for functions in advance through prediction of future request loads and input size distributions, (ii) the Reactive Scaler, that scales containers appropriately to recover from potential resource mismanagement resulting from possible load/input size mis-predictions of the other scaling services, and (iii) the Look-Ahead Scaler, that allocates containers for downstream functions in advance as requests arrive at the initial functions in multi-function apps. Apart from IS Batching and IS Reordering, Cypress leverages Chained Prediction, wherein the input size distribution of downstream functions are also predicted using a variation of input-sensitive profiling, so as to cater specifically to the idiosyncrasies of multi-function apps. Note that we focus on input-sensitive profiling specific to input sizes, which we will henceforth refer to as Input size-Sensitive Profiling (IS Profiling). This is leveraged in all relevant aspects of Cypress's architecture to facilitate the above policies/services.
We implement Cypress using OpenFaaS, an open source serverless framework [17], and extensively evaluate it using real-world datacenter traces subject to various input size distributions on a 288 core Kubernetes cluster. Our results show that Cypress spawns up to 66% fewer containers, thereby, 1 Our scheme adapts to practically all input size distributions of the request trace, mimicking the climate resilience of the Cypress evergreen tree.
Atoll [55] Serverless Cost Prediction [35] Power-chief [63] Fifer [40] Xanadu [32] GrandSLAm [43] Sequoia [57] Hybrid Histogram [51] Cirrus [30] Q-Zilla [46] Kraken [27] Cypress improving container utilization and cluster-wide energy savings by up to 2.95× and 23%, respectively, versus state-of-the art serverless RM frameworks. Furthermore, Cypress guarantees the SLO requirements for up to 99.99% of requests.
This section provides a brief background of serverless computing and input size-sensitive functions, followed by the motivation for incorporating input size-sensitive policies into RM frameworks.
In serverless computing, the user writes code for a function, uploads it to the serverless platform and registers an event (such as an HTTP request or a file upload) to invoke the function (henceforth, we will use 'event' and 'request' interchangeably). Depending on the app, these functions may process input provided as part of an incoming request and/or input files from a storage service to produce the desired output (which may also be a file that gets stored). Such functions are supported in commercial serverless platforms including AWS Lambda [9], Microsoft Azure Functions [16] and Google Cloud Functions [12]. The registered event triggers function execution, possibly accompanied by a "cold start" latency, which is associated with launching a new container, setting up the runtime environment and deploying the function by downloading its code.
Cold starts can take up a significant proportion of a function's response time (up to tens of seconds [5,6]) and can, thus, lead to SLO violations. That being the case, a wealth of existing research [24,28,29,47,48,54,64] focuses on mitigating cold start overheads. Another approach involves hiding the effects of cold starts via proactive container provisioning [19,32,55,57]. Additionally, some of these provisioning policies minimize containers by batching multiple requests onto fewer containers, as opposed to spawning one for each request (as is the norm) [27,40,43]. Kraken [27] and Fifer [40] are two such serverless RM frameworks that accomplish batching using the average execution time and function's SLO. For a comparison of Cypress against related work, we refer the reader to Table 1.
Interestingly, works such as [25,31,35,38,41] have demonstrated that the execution time of some functions can vary depending on various input parameters. Input-Sensitive profiling encompasses a set of techniques which can be used to empirically determine the execution time of individual routines as a function of such parameters. In particular, this can be done using the input size as the input parameter. We refer to this technique as Input size-Sensitive Profiling (IS Profiling). One key aspect in which this differs from theoretical computational complexity (that uses notations such as Big-O bounds to describe the scalability of algorithms) is that it can actually estimate the value of running time of the function in practice, as opposed to identifying the bounding factors of the growth rates of algorithms. IS Profiling typically achieves this by (i) performing multiple profiling runs of the function/routine with workloads spanning several magnitudes of input size, (ii) observing the performance and (iii) fitting these observations to a statistical model that predicts metrics (such as execution time) as a mathematical function of workload size. Note that this is a generalized approach that produces a model applicable to any input size. As we will demonstrate, the above techniques also apply to certain serverless functions, which we refer to as Input size-Sensitive functions (IS functions). Table 2 presents some IS apps from the AWS Serverless Application Repository [11] and/or the OpenFaaS Function Store [18]. Below, we investigate the implications of IS functions on state-of-the-art serverless resource provisioning policies.
As mentioned earlier, the container provisioning policies of some state-of-the-art works (such as Kraken [27] and Fifer [40]) batch requests using the average execution times and SLOs of functions (relative to the app's SLO) to determine the function's batch size (defined as the number of requests that can be served by a container without violating the SLO). This, in turn, is used to calculate the required number of containers. However, as we will demonstrate shortly, when the execution time is input size-dependent, request batching using average execution times proves to be inaccurate, as there is considerable variation in request execution times. This can lead to inappropriate container provisioning. Additionally, the input size distribution itself has to be predicted to facilitate proactive container provisioning. Opportunity 1: In order to accurately provision the required number of containers, it is essential to incorporate an Input size-Sensitive container provisioning policy in the RM framework that can both predict the input size distribution and load of future requests as well as batch requests according to their input size-dependent execution times.
To this end, we propose Input size-Sensitive Batching (IS Batching), which is a request batching policy that takes into account the input size-dependent execution time of each request and each function's SLO while performing request batching akin to the First Fit Bin Packing algorithm [45]. Here, the requests are 'packed' into containers depending on their potential execution times (estimated using IS profiling), and a new container is spawned when none of the existing containers can take an additional request without violating the function's SLO. Note that IS Batching needs to be performed together with input size distribution prediction to proactively spawn the requisite containers.
To explore the benefits of the above policies, we conduct an experiment on our multi-node cluster that pits a scheme, IS Batch, that has both input size distribution prediction and IS Batching against two others that use state-of-the-art policies, namely, No Batch (which spawns a container per incoming request, as in Atoll [55]) and Static Batch (which uses a static batch size, based on average execution time, to batch requests, as in Kraken/Fifer [27,40]) (Figures 1a,1b). Here, 'heavy' and 'light' are with regards to the relative input size of the majority of requests of the distribution. For the heavy distribution (Figure 1a), IS Batch spawns 30% fewer containers compared to No Batch and Static Batch. This is because IS Batch spawns the requisite containers, whereas the other schemes over-provision containers, as No Batch does not perform batching and Static Batch inaccurately calculates the batch size using the function's average execution time (which skews towards the higher side here). However, partly due to spawning fewer containers, and, thereby, increasing the queuing at containers, IS Batch has lower SLO compliance compared to other schemes (99.57% vs. 99.99%).
In case of the light distribution (Figure 1b), IS Batch spawns 41% fewer containers than No Batch, which spawns the same number of containers as it does for the heavy distribution (being agnostic to input size distributions). Similarly, the SLO compliance of IS Batch is lower than that of No Batch (99.35% vs. 99.99%). However, since, here, the average function execution time skews towards the lower side, Static Batch under-provisions containers (13% fewer containers than IS Batch). Consequently, IS Batch has higher SLO compliance compared to it (99.35% vs. 97.78%). Challenge 2: Input size-Sensitive Request Scheduling Although IS Batch seems to provision the requisite containers, its SLO compliance needs to be improved. Apart from allocating fewer containers, the other reason for this is that IS Batch is intended to spawn containers so as to meet each individual request's SLO by only considering its potential execution time and the First-Fit Bin Packing algorithm. It does not account for the queuing delays each request would face due to its relative position in the request queue. As a result, heavier requests queued behind lighter ones may potentially cause SLO violations, as they have a shorter 'buffer' time to execute (Section 1). To address this, we incorporate Input size-Sensitive Request Reordering (IS Reordering) on top of the IS Batch scheme to reorder the request queue to prioritize heavier requests over lighter ones (similar to the First-Fit Descending Bin Packing Algorithm [42]). Opportunity 2: Although the IS Batch scheme is useful for spawning the requisite containers to meet the SLOs of a large portion of requests, it is vital to perform Input size-Sensitive Request Reordering to maximize SLO compliance, while maintaining the same, minimal number of containers.
Adding the IS Reordering policy to the previous IS Batch scheme substantially improves the SLO compliance of the resultant scheme (which we call IS (Batch+RR)), while spawning the same number of containers. For instance, for the previous experiment, under the light distribution, IS (Batch+RR) has improved SLO compliance compared to IS Batch (99.98% vs. 99.35%) (with equal containers) and nearly matches No Batch's SLO compliance (99.99%) (using 41% fewer containers). While Static Batch provisions 13% fewer containers than IS (Batch+RR), IS (Batch+RR) greatly surpasses it in terms of SLO compliance (99.98% vs. 97.78%).foot_0 Challenge 3: Multi-Function Applications While the above policies can help single-function apps remain highly SLO-compliant with the requisite containers, they may not suffice when the serverless app is composed of multiple IS functions (forming a 'function chain'). One reason is that the input size distribution for each IS function will be different since each function processes its input and produces an output, which then becomes the input for the subsequent function(s). Therefore, predicting only a particular IS function's input size distribution in a multi-function IS app is insufficient to perform effective IS Batching for all its functions.
A possible solution to this is, what we refer to as, Chained Prediction. This predicts the input size distribution of both the first IS function as well as those of subsequent IS functions. This is done by inferring the intermediate input sizes between each IS function in the function chain by using a variation of IS Profiling. Although Chained Prediction can help estimate the number of containers required for all functions, errors in prediction may arise, especially given that multiple predictions are done at once (for future request load as well as initial and intermediate input size distributions).
Normally, reactive scaling is used to appropriately scale containers to compensate for prediction errors in proactive scaling. However, this can potentially lead to cold starts if containers have to be scaled up. One way to mitigate this (and potentially improve SLO compliance) is to perform, what we call, Look-Ahead Scaling (LA Scaling), wherein containers are appropriately scaled in advance for all IS functions that appear later in the function chain (descendent functions) when requests arrive at the initial IS function(s). Note that LA Scaling, like Proactive Scaling, also uses Chained Prediction with IS batching. To demonstrate the benefits of Chained Prediction and LA Scaling, we compare three schemes, namely, No CP, CP and
) predicts the input size distribution for only the first IS function in the app and defaults to using static batch sizes to proactively spawn containers for subsequent IS functions. CP uses Chained Prediction to proactively spawn containers for all IS functions in the app according to their predicted input size distributions, whereas CP+LAS adds LA Scaling on top of this to provision containers for descendent functions early while requests arrive. Note that all three schemes leverage IS Batching. CP improves upon both the response time (5%) and SLO compliance (99.95% vs. 99.93%) compared to No CP (Figure 2). This is because CP accurately provisions the requisite containers for all IS functions, including Text_Translate (which appears later in the function chain), as evidenced by Figure 3, which depicts the breakdown of containers spawned by each scheme. From Figure 2, it can also be seen that CP+LAS betters CP in terms of response time (∼3%) and SLO compliance (99.98% vs. 99.95%) as it can alleviate potential cold start effects for descendent functions by accurately spawning containers for them in advance. Note that the above improvements in SLO compliance translate to a 4% and 6% improvement in tail latency for CP versus No CP and CP+LAS versus CP, respectively 3 . These improvements, as we will later see, are magnified under larger-scale request traces.
As we will see in Section 6, all these policies synergize to help the resultant scheme outperform state-of-the-art RM frameworks in terms of resource consumption and/or SLO compliance. 3 Not shown in any figure
As elucidated in the previous section, it is essential to incorporate IS Profiling into the RM framework as this grants it visibility into the input size-dependent function execution times, thereby, enabling intelligent container scaling and request scheduling decisions to be made. In this section, we describe the variations of IS Profiling that are employed by the framework on real-world serverless apps. These will be instrumental in the policies that will be discussed later.
One of the primary goals of integrating IS Profiling into the system is to determine a function's execution time as a mathematical function of its input size. To achieve this, online model-fitting is performed using function execution times that are sampled across time for various runs for a multitude of input sizes [1,3,7,49,53]. This yields a statistical model that estimates the function's execution time, given an input size. Figures 4,5 depict various plots showing the relationship between input size and execution time for the IS functions for different ranges of input sizes that are typically seen for the corresponding app [1,3,7,49,53]. Note that Send Message is treated as a non-IS function here since its execution time is practically the same for the input sizes it receives as part of Audio Translation's function chain.
Once profiling causes the model to attain sufficient accuracy, the framework automatically infers input size classes for each function to aid in input size distribution prediction. An input size class is a range of input sizes that results in a distinct batch size for the function, given its SLO (the class boundaries are determined using the latest IS Profiling model). Input size classes are introduced to simplify prediction and facilitate the use of a light-weight, history-based prediction model (EWMA) (overhead of ∼ 10 -3 ms). Input size distribution prediction is carried out by predicting the fraction of future requests that will fall under each of the constructed input size classes.
For our purposes, model-fitting for IS profiling is performed with least-squares linear regression and powerlaw regression (as in [31,38]). Regression selects model parameters (𝑎 and 𝑏 below) so as to minimize some measure of error. Linear Models: For a set of points (𝑥 𝑖 , 𝑦 𝑖 ), least-squares linear regression constructs a model that can predict 𝑦 as ŷ (𝑥)
Powerlaw Models: A powerlaw model, on the other hand, predicts 𝑦 as ŷ (𝑥) def = 𝑎𝑥 𝑏 . Since the plot of a powerlaw model is a straight line on log-log axes, linear regression can be used on (𝑙𝑜𝑔𝑥 𝑖 , 𝑙𝑜𝑔𝑦 𝑖 ) to fit observations to the model. Thus, we find 𝑎 and 𝑏 that minimizes the following quantity:
Since regression, by itself, does not evaluate the suitability of the model, Cypress utilizes the 𝑅 2 statistic to select the bestfitting model from the two. 𝑅 2 is a measure of the model's goodness-of-fit that quantifies the fraction of the variance in 𝑦 accounted for by a least-squares linear regression on 𝑥 [38]:
𝑘 𝑖=1 (𝑦 𝑖ȳ) 2 Note that ȳ and x denote the sample means of k-vectors 𝑦 and 𝑥, respectively. This formula also applies to powerlaw fits, but with 𝑥 and 𝑦 replaced by 𝑙𝑜𝑔𝑥 and 𝑙𝑜𝑔𝑦, respectively. 𝑅 2 can take values ranging from 0 (bad) to 1 (excellent). Cypress chooses the fit with the highest 𝑅 2 value as the best-fitting model for a function.
So far, we have discussed IS profiling in the context of predicting execution times of functions as a mathematical function of their input sizes. However, achieving this for multi-function apps is challenging as descendant IS functions will receive requests with different input sizes from those that the initial one(s) received (Challenge 3, Section 2.3). Chained Prediction is used to address this. It uses a variation of IS profiling wherein the input size of a function is used to predict its resultant output size. This can be used to predict the intermediate input sizes of each function in the function chain, given an initial input size. This is achieved using techniques similar to those seen earlier: the input-to-output size profiles collected for IS functions that appear earlier in the function chain (Figures 6a,6b) are used to construct models online from which the one with the highest 𝑅 2 value is chosen to be the best fitting. In addition to Proactive Scaling, LA Scaling also leverages the above techniques to estimate the requisite containers for descendent functions. Note that for both variants of IS Profiling seen thus far, the best-fitting model's predicted values are within ∼7% of the actual values, on average (which is sufficient for our purposes). As we will now see, incorporating IS profiling into all scaling services enables them to make intelligent scaling/scheduling decisions.
Figure 7 outlines the overall design of Cypress. Users trigger the invocation of apps 1 hosted on a Serverless platform 2 by submitting requests to them (either in the form of HTTP requests or through actions like uploading input files to a storage service). The function execution times and corresponding input sizes are sampled to perform IS profiling and thereby, construct a statistical model online (and corresponding input size classes) to use in the various policies that will be described shortly. In Cypress, containers are provisioned in advance for the app's functions by the Proactive Scaler (PS) 3 to serve the incoming requests by avoiding cold starts. The PS accomplishes this by making use of relevant metrics obtained from the serverless platform's monitoring tools/logs 4 and Cypress's other scaling service(s) 5 / 6 . These metrics, in addition to a developer-provided app descriptor, are then used by the PS along with the input size classes inferred from IS profiling to perform Input Size Distribution Prediction 7 . This is, in turn, coupled with Request Load Prediction 8 to estimate the number of future requests of each input size class. With this information, the PS uses IS Batching 9 to calculate the required number of containers and notifies the underlying resource orchestrator 10 to proactively spawn them.
Cypress also employs a Reactive Scaler (RS) 5 that makes use of two key features to further reduce the app's SLO violations. Firstly, the RS performs IS Reordering 11 to prioritize heavier requests over lighter ones to improve SLO compliance. Secondly, it also uses Overload Detection 12 to keep track of request overloading at functions by monitoring queuing delays at containers. In case of an overload, it triggers container scaling after calculating the additional containers needed to mitigate the delay. The RS also utilizes Idling Detection 13 to scale down the number of containers when an excess is detected. Both Overload and Idling Detection aid in coping with the PS's potential mis-prediction of load and/or input size distribution(s).
For multi-function apps, Cypress employs an additional scaling service called the Look-Ahead Scaler (LAS) 6 that uses Chained Prediction 14 to scale containers appropriately for the app's descendent functions as incoming requests arrive at the initial function(s). This performs a more accurate allocation of containers compared to proactive scaling, while also reducing cold start effects that could arise from reactive scaling. Chained Prediction is also leveraged by the PS to effectively spawn containers for all functions in the function chain in advance. Note that IS Batching permeates the container scaling process employed in the PS, RS and LAS. Below, we discuss these aspects of Cypress's design in more detail.
The PS is an integral component of Cypress designed to accurately provision the requisite containers in advance. As shown in Algorithm 1, this is done for each function such that enough containers will be provisioned for them at the end of fixed time windows ( a in Algorithm 1). This requires not only the prediction of future request load (as in [27,40,55]), but also that of future input size distributions (a feature unique to Cypress). For this, the PS makes use of input size classes (derived from the latest IS profiling model) and a pluggable statistical model (EWMA, in our case) to predict the fraction of future requests that will belong to different input size classes based on the corresponding fractions seen in previous prediction windows. Thus, PS, in effect, performs input size distribution prediction ( c in Algorithm 1). This is used in conjunction with the prediction for the total number of future requests (also using a statistical model) ( b in Algorithm 1) to estimate how many of them will fall under each input Algorithm 1 Proactive Scaling
Scale_Containers( 𝑓 𝑢𝑛𝑐, 𝑟𝑒𝑞𝑑_𝑐𝑜𝑛) size class. Note that a bit of history information is allowed to accumulate (typically for a few prediction windows) before the aforementioned statistical models are used to make predictions for subsequent windows. All the above information serves as an approximation for the future request queue ( e in Algorithm 1), which is used together with IS Batching to calculate the required number of containers to proactively spawn ( f in Algorithm 1).
For multi-function apps, the PS is augmented with Chained Prediction ( d in Algorithm 1) to help predict the input size distribution for all IS functions so as to spawn the requisite containers for them. This is achieved by additionally inferring all the intermediate input sizes between each function in the app's function chain by performing Input-to-Output size mapping (Section 3).
Once the required number of containers is estimated, the PS instructs the underlying orchestrator to provision them. Note that, for non-IS functions, the PS defaults to simply predicting the future number of requests alone and considers the average execution time of each of them for calculating the required containers (as in [27,40,55]).
Many serverless frameworks [9,12,16,32,55,57, 61] spawn one container to serve each incoming request to a function. While this can help minimize SLO violations, comparable performance can be achieved with fewer containers by exploiting the notion of slack. Slack refers to the difference in expected response time (based on the function's SLO, calculated relative to the app's SLO) and actual execution time of functions within an app. This allows requests to meet their SLO deadlines, even if they incur a queuing delay. Note that this is equally applicable to single and multi-function apps. Slack is leveraged by works such as Kraken [27] and Fifer [40] to batch multiple requests to fewer containers by queuing the requests at them, thus, reducing the number of containers spawned. For this, the batch size of a function, 𝑓 , is calculated as Batch Size (𝑓 ) = Function SLO ( 𝑓 ) Average Execution Time (𝑓 ) . However, as execution time is input size-dependent for IS functions, request batching using average execution times proves to be inaccurate (Section 2), as it is unaware of the considerable variation in execution times that, in turn, leads to variable slack. To account for these facts, we introduce IS Batching, which is a request batching policy that is cognizant of the input size-dependent execution times of IS functions. To this end, it first uses IS Profiling to map each request's associated input size to the corresponding execution time (Section 3). With this knowledge, request batching is performed as in the First-Fit Bin Packing algorithm, as alluded to in Section 2. Note that for non-IS functions, the average execution time is used to perform batching as it is independent of the input size in such cases. As mentioned earlier, IS Batching is used throughout all of Cypress's scaling services (Figure 7) to calculate the number of required containers to serve a given request queue to an IS app.
Although proactive scaling and IS Batching can ensure that the requisite containers are spawned, further optimization is required to maximize SLO compliance (Challenge 2, Section 2.3). This is because these policies aid in spawning containers to meet each individual request's SLO by considering only its potential execution time and the First-Fit bin packing policy and not the queuing delay caused by the relative position of the request in the request queue. Furthermore, the PS may mis-predict future request loads and/or input size distributions, potentially leading to container mismanagement, thereby, adversely affecting SLO compliance.
To address these concerns, Cypress employs the RS to perform request queue management in addition to reactive container scaling. The RS performs IS Reordering to prioritize heavier requests over lighter ones in the incoming request queue (Heaviest Job First) ( a in Algorithm 2). This ensures that the heavier requests (that have lower slack) are served earlier so as to minimize SLO violations. This resultant container allocation policy resembles the First-Fit Descending Algorithm 2 Reactive Scaling Bin Packing algorithm. To deal with potential container under-provisioning, the RS leverages Overload Detection ( c in Algorithm 2) to, firstly, calculate the estimated wait times of queued requests at existing containers. Then, if it detects requests whose wait times exceed the cost of spawning a new container (the cold start of the function), overloading is said to have occurred at the function. If so, Cypress spawns new containers to serve the delayed requests as they would get served faster this way, as opposed to waiting at an overloaded container.
Similarly, the RS uses Idling Detection ( b in Algorithm 2) for functions where container over-provisioning has occurred. The RS gradually scales down its allocated containers to the appropriate number, if excess containers are detected for serving the current request load. Note that the RS incorporates IS Batching into all of its container scaling decisions.
For multi-function apps, as mentioned earlier, multiple predictions have to be made to provision containers proactively: request load prediction, input size distribution prediction for the initial IS function and Chained Prediction for the descendent IS functions. This may lead to inappropriate container allocation, which can be rectified using the RS. However, the reactive scaling entailed may lead to SLO violations when new containers are spawned. To mitigate this, Cypress leverages the LAS to appropriately provision containers in advance for all descendent IS functions when requests arrive at the initial function(s). It accomplishes this by utilizing Chained Prediction and IS Batching to predict the number of containers needed for the descendent functions based on the initial request queue ( a and b in Algorithm 3). Since the container scaling here is done based on the actual request queue at the initial IS function(s), as opposed to their predicted counterparts, it is more accurate. Additionally, it takes advantage of the buffer time between the requests arriving at the initial function(s) to finally reaching the concerned functions to spawn containers in advance, thereby, alleviating the potential cold start effects of reactive scaling.
Thus, Cypress, by leveraging its scaling services and resource management/scheduling policies (Figure 8), remains highly SLO compliant with a minimal resource footprint.
Cypress is implemented using Python and Go on top of OpenFaaS [17], an open-source serverless platform. Open-FaaS is deployed with Kubernetes [15] as the container orchestrator. We disable OpenFaaS's default Alert Manager module (that detects load surges) to deploy our scaling services (Figure 7) that leverage Cypress's policies (Table 3). Cypress uses dynamically populated hash tables (that are looked up on demand) to map input file names to their corresponding input sizes. Note that performing the lookup and IS Reordering (Table 3) together incur minimal overhead (e.g. ∼1 ms per request queue of 200 requests). Evaluation Methodology: We evaluate the Cypress prototype on a 6 node Kubernetes cluster with a dedicated manager node. Each node is equipped with 48 cores (Intel Cascade Lake), 192 GB of RAM, 1 TB of storage and a 10 Gigabit Ethernet connection [44]. For energy measurements, we use the Intel CPU Energy Meter [14] that measures the energy consumed by all sockets in a node. Request Traces: We use a synthetic Poisson arrival trace with an average rate 𝜇 = 250 rps and real-world traces from Wiki [60] and Twitter [4]. The Twitter trace is erratic and has a large peak-to-mean ratio (5450:3139) compared to that of the Wiki trace (331:302). We choose these traces and scale their request loads based on the trend of increasing request rates evidenced by a recent study on Azure traces [65] and also envisioned in other related work [27,55]. For most experiments, we use 3 input size distributions, namely, Heavy, Medial and Light, where input sizes are randomly generated such that the majority (50-55%) will be in the first, second or third terciles (∼33%, descending), respectively. Applications: We implement 5 apps in OpenFaaS by composing one or more IS functions based on those from the AWS Serverless Application Repository [11] and/or Open-FaaS Function Store [18]. To model the characteristics of the original functions, we invoke sleep timers within our functions (as in [27]), with their durations determined by adding a salt term (based on the model's error) to the value given by the fitted model obtained from IS Profiling. This includes the time for reading input and state recovery (if any), as they are also billable [11]. Note that we set all app SLOs to be ∼20% higher than the app's maximum possible execution time [27]. Resource Management schemes: We compare Cypress against the container provisioning schemes of Atoll [55], Kraken [27] and Fifer [40], which we will, henceforth, refer to as Atoll, Kraken and Fifer, respectively. Note that commercial providers spawn the same containers as Atoll [9,12,16], but have worse SLO compliance [27,55] and, hence, are not presented in our experiments. Additionally, we compare Cypress against the scheme, IS Batch, which uses all policies/features of Cypress except IS Reordering and LA Scaling. Large Scale Simulation: To evaluate the effectiveness of Cypress in large-scale systems, we built a high fidelity, multithreaded simulator in Python using container cold start latencies and function execution times profiled from our realsystem counterpart. We have validated its correctness for scaled-up versions of all traces by correlating various metrics of interest generated from experiments run on the real system (e.g. the Twitter trace was scaled up from having a peak of 250 rps in the real system to 5450 rps here). The simulator allows us to evaluate our model for a larger setup with a ∼6.4k core cluster which can handle up to ∼5500 requests (22× more than the real system). Additionally, it aids in comparing the resource footprint and SLO compliance of Cypress against that of a clairvoyant scheme (Oracle) that has 100% load and input prediction accuracy.
This section presents a thorough evaluation of Cypress using the real system and our simulator. Unless mentioned otherwise, most of the plots presented here pertain to either averaged or specific values for the Wiki and/or Poisson traces (which we will, henceforth, refer to as stable traces, owing to their relatively low peak-to-mean ratios) for various input size distributions. Note that, for isolated examples, similar results are seen for other apps and workload mixes, wherever applicable. Furthermore, the brick-by-brick analyses shown in Section 2.3 extend to the results presented here as well. IS Batching to only spawn the requisite containers while also performing IS Reordering to maximize SLO compliance. Heavy distributions tend to decrease the extent of request batching in Cypress (compared to the medial and light distributions), thereby increasing containers spawned, since the higher number of heavier requests in the trace would likely need dedicated containers to reduce app SLO violations. For instance, for Image Compression, Cypress spawns 43% fewer containers versus Atoll for the heavy distribution (Figure 11a), but for the light distribution, it spawns 66% fewer containers, due to batching more (Figure 11b). Kraken and Fifer have the same container scaling policies for single-function apps, where they use the average function execution time to statically calculate batch sizes for request batching. Owing to this, they inappropriately allocate containers. For the heavy distributions, since the average execution time would skew towards the higher side (due to the majority of heavy requests), the calculated batch size generally becomes lower (Section 4.2). This leads to container over-provisioning since there will be lighter requests that do not need as many containers as the heavier ones. On the other hand, Cypress, by leveraging IS Batching, only spawns the requisite containers. For example, Cypress spawns 34% fewer containers than Kraken/Fifer for Sentiment Analysis for the heavy distributions, while also matching its SLO compliance using IS Reordering (Figure 9a).
For the light and medial distributions, Kraken/Fifer tend to under-provision containers (leading to SLO violations) due to the calculated batch size being too high because of a low average execution time. For example, although Cypress spawns 9% more containers than Kraken/Fifer for Image Compression for the medial distribution, it has 99.99% SLO compliance compared to Kraken/Fifer's 98.05% (Figure 11c). Cypress spawns the same number of containers as IS Batch, since both schemes use IS Batching. Despite this, Cypress outperforms IS Batch in terms of SLO compliance in all cases as it uses IS Reordering.
For the same reasons as with the single-function apps, Atoll is seen to spawn the most containers in almost all scenarios, with Cypress provisioning much fewer containers than it (Figures 12,13). For example, Cypress spawns 33% fewer containers than Atoll for the Audio Translation app for the light distribution (Figure 13b). Moreover, Cypress has even better (if not, as good) SLO compliance compared to not only Atoll, but all other schemes, for multi-function apps, with a minimum of 99.97%. This is because the other 'input size-agnostic' RM frameworks are adversely affected by the presence of multiple IS functions in the app, as this exacerbates the effects of queued heavy requests on SLO violations (Challenge 2, Section 2.3).
Fifer is seen to suffer from the same effects of using static batch sizes as in single-function apps, leading to inappropriate container provisioning. For example, it over-provisions containers for Email Categorization for the heavy distribution, with Cypress spawning 30% fewer containers than it (Figure 12a). For the light distribution, although Cypress spawns 8% more containers than Fifer, it has an SLO compliance of 99.97% versus Fifer's 99.13% (Figure 12b). Kraken has a similar container provisioning strategy to Fifer, with the exception that it provisions extra containers for functions considered important, depending on their position in the function chain. As a result, Cypress is observed to spawn fewer containers than it, while also having higher SLO compliance in all cases. For instance, Cypress allocates 21% fewer containers than Kraken for Audio Translation for the heavy distribution while having an SLO compliance of 99.98% versus Kraken's 99.31% (Figure 13a). Compared to IS Batch, similar trends to those of single-function apps can be observed here as well. Note that Cypress leverages IS Reordering and LA Scaling to remain highly SLO compliant. 6.1.2 End-to-End Response Times and Latency Distribution we observed that Cypress has near-identical SLO compliance to Atoll, it also has slightly higher execution times (4% on average) than the latter for both single-function and multi-function apps. This is primarily due to Cypress spawning much fewer containers than Atoll (40% on average), thereby, causing queuing, in turn, increasing the queuing delay of requests. For example, the relatively higher queuing time of Cypress versus Atoll leads to an 11% increase in its response time for Audio Translation (Figure 14). However, in this case, Cypress spawns 32% fewer containers than Atoll. Moreover, as we will shortly see, Cypress remains within the SLO for all workload mixes for all functions at the tail (P99). These benefits more than compensate for the slightly higher execution times versus Atoll. It can be observed from Figure 14 that Cypress achieves 15%, 10% and 6% less execution time than Fifer, Kraken, and IS Batch, respectively. Although the difference in the number of containers is just within 6% compared to these schemes, Cypress achieves its lower execution time primarily by virtue of its IS Reordering, LA Scaling and IS Batching. From Figure 15, we observe that Atoll, like Cypress, meets the SLO at P99. However, it does this using 70% more containers than Cypress. Compared to Kraken/Fifer, although Cypress spawns 11% more containers, it remains SLO-compliant as opposed to those schemes, that exceed the SLO by 50% at P99. This is reflected in the SLO compliance of Kraken/Fifer, which is only 98.19% in this case 4 . Note that, since IS Reordering prioritizes heavier requests, the fastest executing requests of Cypress are slowed down slightly in exchange for a much lower tail latency. This ensures that no isolated request suffers from abysmal response times (unlike in Kraken/Fifer and IS Batch). 6.1.3 Analysis of other Key Benefits:This subsection discusses a few other key benefits offered by Cypress. 4 Note that not all numbers specified here have been shown in the graphs. Container Utilization: Here, we define container utilization as the jobs (requests served) per container. Hence, a scheme should ideally have high container utilization (by packing more jobs onto fewer containers) with minimal SLO violations. As per Figure 16, Cypress has 52% and 71% more container utilization compared to Atoll for the heavy and light distributions, respectively. This is because Cypress performs IS Batching, thereby, provisioning only the requisite containers as opposed to Atoll, that does not batch requests (and thus, over-provisions containers). For the heavy distribution, Kraken/Fifer use a static batch size of 1, thereby, behaving similarly to Atoll. However, for the light distribution, they have 11% more container utilization than Cypress since they under-provision containers as a result of inaccurate batching. In this case, Cypress has much better SLO compliance than them (99.98% versus 99.32%) and meets the SLO at P99, which they do not. Although, IS Batch has the same utilization as Cypress (due to provisioning the same number of containers), it has worse SLO compliance for both the heavy (99.82% versus 99.99%) and light (99.80% versus 99.98%) distributions than Cypress as a result of not having Cypress's additional policies. 5Energy Efficiency: We measure the energy consumption as the total energy consumed by a scheme divided by total time. Cypress consumes 19% and 22% less energy than Atoll for the heavy and light distributions, respectively (Figures 17a and17b). The energy savings of Cypress are a direct consequence of the savings in compute and memory used by the fewer containers it spawns. For the same reason, Cypress consumes 23% and 19% less energy than Kraken and Fifer, respectively, for the heavy distribution (Figure 17a). For the light distribution, Cypress consumes 1% less and 1% more energy than Kraken and Fifer, respectively (Figure 17b). This implies that the extra containers spawned by Cypress versus Fifer (9% in this case) translates to a much lower difference in energy consumption. Note that despite the relatively low difference in energy consumption between Cypress, Kraken, and Fifer, Cypress outperforms the others in terms of SLO compliance (99.96% versus 98.79% and 98.56%) and minimizing tail latency (the others exceed the SLO by 30% at the tail) 5 . Similarly, IS Batch, while consuming the same amount of energy, also has worse SLO compliance and tail latency, regardless of distribution.
Resilience to Erratic traces: As noted earlier (Section 5), the Twitter trace is highly erratic, with a high peak-tomean ratio (∼2:1) and therefore, can adversely affect the SLO compliance of various schemes. For the heavy distribution, it is observed that Cypress outperforms the other schemes, both in terms of containers spawned (34% lesser than Atoll, Kraken/Fifer and equal to IS Batch) and SLOs satisfied (99.72% versus 97.46% of Atoll, Kraken/Fifer and IS Batch's 97.65%) (Figure 18a). This is because, despite the erratic request load, Cypress's features such as input size distribution prediction, IS Batching and IS Reordering combined with its load prediction enable it to tolerate the influx of various input sizes that accompanies the variable load. For the light distribution (Figure 18b), almost all schemes improve their SLO compliance (including Cypress, with the highest, 99.91%), which may be due to the request trace inherently having a majority of lighter requests (which have more execution slack). To highlight the effects of the other schemes' low SLO compliance on their tail latencies, we can refer to Table 4 that shows all P99 values (in ms) corresponding to Figure 18. For both the heavy and light distributions, Cypress is the only scheme to remain SLO compliant at the tail, with Atoll, Kraken/Fifer and IS Batch violating the SLO at P99 by as much as 57%, 89% and 55%, respectively.
The numbers for IS (Batch+RR) are not depicted anywhere
Not all numbers have been shown in the Figures/Tables
Not shown in Table