{'fraction_non_alphanumeric': 0.033185999712519766, 'fraction_numerical': 0.010636768722150353, 'mean_word_length': 4.569041424854913, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RobustScaler: QoS-Aware Autoscaling for Complex Workloads

Autoscaling is a critical component for efficient resource utilization with satisfactory quality of service (QoS) in cloud computing. This paper investigates proactive autoscaling for widely-used scaling-per-query applications where scaling is required for each query, such as container registry and function-as-a-service (FaaS). In these scenarios, the workload often exhibits high uncertainty with complex temporal patterns like periodicity, noises and outliers. Conservative strategies that scale out unnecessarily many instances lead to high resource costs whereas aggressive strategies may result in poor QoS. We present RobustScaler to achieve superior trade-off between cost and QoS. Specifically, we design a novel autoscaling framework based on non-homogeneous Poisson processes (NHPP) modeling and stochastically constrained optimization. Furthermore, we develop a specialized alternating direction method of multipliers (ADMM) to efficiently train the NHPP model, and rigorously prove the QoS guarantees delivered by our optimization-based proactive strategies. Extensive experiments show that RobustScaler outperforms common baseline autoscaling strategies in various real-world traces, with large margins for complex workload patterns.


I. INTRODUCTION
Autoscaling has been a fundamental tool in elastic cloud services that dynamically adds (scales out) or deletes (scales in) computing resources, such as instances, CPU and memory, to closely match the ever-changing computing demand [1], [2]. Real-world workload can change drastically over time, and reactive autoscaling that conducts scaling actions only after the workload changes often leads to underprovision during increasing traffic and in turn degradation of quality of service (QoS). Therefore, proactive autoscaling is becoming increasingly popular [3]- [6] in that it scales out beforehand when a demand increase is expected so that resource shortfalls can be avoided and satisfactory QoS is consistently maintained.
In this paper, we consider proactive autoscaling in the scaling-per-query scenario of on-demand cloud service: When a query comes in, it will be served by one of the available idle instances (warm start) or a new instance will be initiated for that query (cold start); meanwhile, each instance is terminated after processing one query and is not reused/shared by other queries. The scaling-per-query scenario is common in cloud computing [7], [8]: One example is the container registry [9], [10] for storing, managing, and securing custom container images; another example can be found in Continuous Integration (CI) and Continuous Delivery (CD) [11] to avoid user's account/data being hijacked/spoofed. Note that scalingper-query is in contrast to other cloud services where an instance keeps running and processing new queries until it is terminated for other reasons (e.g., scaled in when traffic goes down). A purely reactive scaling mechanism in the scalingper-query scenario would simply create an instance for every new query and terminate the instance after processing the query. The main drawback of this mechanism is the cold-start delay, i.e., the startup time of an instance is not negligible compared to the actual processing time of the query, making the total response time unnecessarily long. One way to reduce the cold-start delay is to maintain a pool of running instances in anticipation of future queries so that processing can start immediately upon arrival of a query, however, this can incur a considerable overhead cost since the instances may stay idle without processing any query, especially when the pool size is large, and it is not clear what pool size is needed to achieve a certain QoS.
In practice, proactive autoscaling also encounters several challenges. One challenge lies in capturing the complex and variable periodic patterns in the workload. The workloads of database and cloud computing often exhibit notable periodic patterns [12]- [17]. By identifying and utilizing the periodicity, we can perform effective autoscaling of resources in these scenarios to save a significant amount of resources. However, real-world workload may come with lots of missing data, anomalies, large noises that, on one hand, obscure many structural patterns such as periodicity that are crucial for prediction, and on the other hand requires strong robustness from the workload prediction algorithm. We leverage robust decomposition [18], [19] to extract periodic patterns from the queriesper-second (QPS) time series for query arrival modeling and forecasting, even in the presence of a considerable amount of noises, missing data and anomalies. Another challenge concerns the control of the trade-off between resource saving and QoS improvement. As more resources are allocated, the QoS gets improved, and vice versa. For scaling-per-query, the more instances are maintained and the earlier they are created, the less cold starts will occur. Proper control of this tradeoff becomes more challenging for scaling-per-query due to its per-query scaling dynamics. For example, the lifecycle (hence the cost) of an instance also depends on the arrival and the execution time of the query, and whether cold start occurs is related to the temporal order between the arrival time of the query and the time the instance finishes startup which is not known beforehand when creating the instance. Therefore, even evaluating the cost and QoS (e.g., cold-start delay) requires knowledge of the query arrival dynamics. Moreover, instances created before will be consumed by incoming queries and therefore the number of available instances changes after every query arrival, making scaling-per-query a sequential decision making problem. All these necessitate the modeling of the query arrival process for which we develop a nonhomogeneous Poisson process (NHPP) framework with novel periodicity regularization that can flexibly approximate variable periodicity patterns. Moreover, we formally investigate the trade-off through the lens of stochastically constrained optimization [20] from which scaling decisions that respect either QoS constraints or cost constraints can be efficiently computed.
The main goal of this study is a proactive autoscaling framework that can properly create instances before the queries arrive to guarantee a certain QoS with a low overhead cost. To the best of our knowledge, no previous work has investigated proactive autoscaling to reduce cold-start delay in the scaling-per-query scenario. To this end, we design a novel autoscaling framework called RobustScaler which can generate robust scaling decisions that optimally balance the trade-off between cost and QoS and are robust to noise, missing data and anomalies. In summary, our contributions are: 1) develop the first NHPP framework for demand modeling in autoscaling to capture both periodicity and stochasticity of query arrivals, along with an efficient alternating direction method of multipliers (ADMM) training algorithm; 2) propose a stochastically constrained optimization formulation to compute Pareto-optimal scaling decisions in terms of cost and QoS; 3) design a sequential scaling scheme based on the stochastically constrained optimization that enjoys provable probabilistic QoS guarantees; 4) conduct an extensive set of experiments that demonstrate the superiority of RobustScaler compared to heuristic strategies.
The rest of the paper is organized as follows. Section II reviews the related literature. Section III introduces the setting and challenges for scaling-per-query. Section IV describes the proposed autoscaling framework. Section V then presents our NHPP arrival model with periodicity regularization, whereas Section VI details the QoS-cost trade-off in scaling decision making, the constrained optimization formulations, and the consequent sequential scaling schemes. Section VII presents experimental results including a comparison of the proposal with two heuristic autoscaling methods. Section VIII concludes the paper.

II. RELATED WORK
Autoscaling is an active research area in various types of cloud systems, such as database [3], [21], [22], microservices [23]- [25], stream processing [26]- [28], and web applications [29], [30]. Recent surveys include [2], [31]- [34]. These autoscaling systems have been successfully applied in their respective types of systems, but cannot handle the scalingper-query scenario considered in this paper where the key difficulty is to mitigate cold start for future queries. Similar cold start issues also appear in serverless FaaS platforms, and are typically mitigated by either maintaining a pool of prewarmed instances [35], [36] or reusing warm instances after they finish current function invocations [37]. However, unlike the serverless environment, instances are not reused in our case and hence the scaling dynamics are different.
Based on the scaling timing, autoscaling methods can be categorised into proactive and reactive ones [2]. Note that the full potential of proactive autoscaling can be utilized when the workload has predictable and periodic/cyclic patterns. Fortunately, many real-world workloads exhibit such patterns [12]- [17]. However, in practice we often face highly noisy and variable periodic patterns with missing data and outliers [3], [18], which calls for robust workload prediction. For example, P-Store [3] is a predictive autoscaling scheme for database systems under workload with a diurnal pattern, but it does not automatically capture other periodicity patterns. Meanwhile, P-store does not characterize uncertainties in workload forecasting. Periodic workload patterns are also utilized in the Turbine of Facebook [26] for stream processing systems, where it forecasts future load patterns in a heuristic way without carefully considering pattern variations or outliers. In contrast, we leverage robust decomposition [18], [19] of time series in workload forecasting to deal with complex variable periodic patterns under challenging noise and outliers.
To properly characterize uncertain query arrivals in the workload, a conventional modeling tool is Poisson processes [7], [38] that is analytically tractable with elegant statistical properties and accurate enough when the traffic consists of many independent users with weak temporal dependency [39]. Otherwise, Markovian arrival processes [40] and hierarchical bundling models [41] have been developed to capture bursts and temporal dependency. See [16] for a comprehensive survey. However, in these approaches periodicity patterns are either not considered or assumed not to vary over time, whereas we adopt NHPP with a novel periodicity regularization to flexibly approximate variable periodicity patterns.
Existing autoscalers generate scaling decisions based on control theory [42]- [44], reinforcement learning [45], [46], queuing theory [47], [48], and rule-based methods [49]. Most of these methods either make scaling decisions based on a mean demand estimate without considering uncertainty, or handle uncertainty in a heuristic way. For example, model predictive control is adopted for predictive autoscaling in [42] which utilizes ARMA model for workload forecasting and look-ahead controller for resource allocation without considering uncertainty. The autoscaling scheme RobustT2Scale [43] integrates a fuzzy controller with an online learning mechanism that can cope with certain uncertainties but is not general enough to handle variable periodic patterns. Instead we directly incorporate workload uncertainty into scaling decisions via stochastic constraints that are expressive of QoS requirements to derive robust scaling decisions.
the query is processed immediately 4: else if x i ≤ ξ i < x i + τ i then 5: the query waits until x i +τ i and then processing starts 6: else 7: an instance is created to process the query 8: end if 9: end for

III. THE AUTOSCALING PROBLEM
Formally, let ∆t be a fixed time step, and {Q t : t = 1, . . . , T } be a sequence of historical query counts from an application deployment within each time interval of length ∆t, that is, Qt ∆t is the QPS. Suppose the current time is 0, and let 0 < ξ 1 < ξ 2 < · · · < ξ i < · · · be an ascending sequence of random arrival times of the queries, where ξ i is the time of arrival of the i-th upcoming query, let 0 < x 1 < x 2 < · · · < x i < · · · be an ascending sequence of deterministic instance creation times (the i-th instance to be used to process the i-th query). Let s 1 , s 2 , . . . , s i , . . . be a sequence of i.i.d. random processing times of the queries, and τ 1 , τ 2 , . . . , τ i , . . . be a sequence of i.i.d. random pending/startup times of the instances. Therefore the i-th instance shall get ready for processing queries at time x i +τ i . Let µ s := E[s i ], µ τ = E[τ i ] be the expected values of each s i , τ i respectively. To illustrate the dynamics of the query arrivals, their interplay with scaling actions, and the associated resource cost, Figure 1 shows a sample of the query arrival process. If the arrival time ξ i of the i-th query is later than the time x i + τ i when the i-th instance gets ready (e.g., the first query in Figure 1), the query is said to be "hit" and can be processed right away, but the instance stays idle for a time span of ξ i − (x i + τ i ) which incurs an unnecessary cost. If the arrival time is earlier than the ready time (e.g., the second query), the query is not hit and needs to wait until the instance gets ready to start processing. Otherwise if the i-th instance is not even created before ξ i (e.g., the fourth query), it will be immediately created to handle the query and the originally scheduled creation at time x i is canceled. Finally, once the instance finishes processing the query, it gets deleted immediately. These dynamics are formalized in Algorithm 1.
Our framework aims to recommend the scaling action sequence 0 < x 1 < x 2 < · · · < x i < · · · based on historical data so that • (QoS) the response time of a query, i.e., the time between its arrival and the completion of its processing, is short, • (cost) the idling time of a instance, i.e., the period between the time it gets fully started and the time it starts to process a query, is short. Note that these two metrics compete against each other as illustrated before in Figure 1, and balancing their trade-off serves as a fundamental challenge in making scaling decisions. In this section we introduce the framework of the proposed RobustScaler algorithm. Specifically, it consists of four main components, including periodicity detection, historical query arrival modeling, query arrival prediction, and scaling plan, as illustrated in Figure 2. In the following we introduce each component in detail.

IV. FRAMEWORK OF ROBUSTSCALER
The first periodicity detection module takes in historical query data and discovers any present cyclic patterns by leveraging robust periodicity detection [18]. Depending on the size of fluctuation of the traffic and the time resolution of the data, periodicity patterns can be obscured by the inherent randomness of the traffic and thus can not be easily detected. Therefore, to reduce random effects and reveal potentially hidden periodicity patterns, we perform a time aggregation by averaging the QPS series in each time window of a fixed size and then perform periodicity detection on the aggregated series.
The second historical query arrival modeling module is the key modeling step that learns the stochasticity of the query arrival process and makes it possible 1) to make fine-grained query-wise scaling decisions and 2) to make robust scaling decisions that are guaranteed to attain a certain QoS level under traffic uncertainty. In particular, a regularized NHPP with periodicity penalty is used, a more detailed exposition for which shall be given in Section V. Note that this step on its own is a workload modeling technique that is generally applicable to other settings, although the focus of this work is on scaling-per-query.
The third query arrival prediction module extrapolates the trained point process model to infer the dynamics of the incoming traffic in the near future. In the case of NHPP, the estimated historical intensity is extrapolated to predict future intensity of the arrival process.
The last scaling plan module utilizes the predicted traffic dynamics to create scaling plans, i.e., a list of scaling in/out actions to be performed in the near future, through a stochastically constrained optimization formulation that characterizes a trade-off between resource cost and QoS. User-specified QoS or cost levels can be directly fed into the formulation to obtain scaling decisions that satisfy the stipulated QoS/cost requirements. Section VI discusses in detail the stochastically constrained formulation and our sequential scaling scheme.

V. QUERY ARRIVAL MODELING
This section explains the details of our second module that models the query traffic as a point process [7]. Specifically, we consider modeling query arrivals as an NHPP. Suppose that within each time step ∆t the Poisson intensity is a constant λ t := exp(r t ), where an exponential transform is adopted to ensure the positiveness of the intensity, so that the query count during the t-th time interval has a Poisson distribution with rate exp(r t )∆t. Then the likelihood of observing Q t queries within the t-th time interval is exp(− exp(r t )∆t)(exp(r t )∆t) Qt /Q t ! and the negative log-likelihood of query count series {Q t : is the element-wise exponential of r, and 1 is the all-one vector of length T . With the likelihood loss alone, the learned intensities will be identical to the QPS Q t /∆t for each t which are susceptible to noises and outliers and cannot handle periodic patterns. Therefore, we impose an L 1 penalty on the second order difference to regularize the intensity curve, and further introduce periodicity by imposing an additional periodicity regularization term if periodicity patterns are detected, arriving at a regularized loss where the matrix D 2 is the second order differential matrix to capture the smoothness between every set of three consecutive points [50], [51], β 1 ≥ 0 is the smoothness regularization parameter, L is the period length obtained from periodicity detection, the matrix ×T is the L-step forward differential matrix to capture the smoothness across period length L, and β 2 is the periodicity regularization parameter. Additionally, the time step ∆t for the QPS series also affects the accuracy of the arrival model. Ideally, ∆t shall be chosen by cross validation, but in practice, if the query arrival rate is not expected to vary drastically over time, using a time step in minutes yields reasonably accurate arrival models.
It is not efficient to directly solve the optimization problem (1). Therefore, we design a quadratically approximated ADMM algorithm to efficiently solve it. Introducing auxiliary Algorithm 2 ADMM for solving (1) input: initial guess r 0 , ν y,0 , ν z,0 , y 0 = D 2 r 0 , z 0 = D L r 0 1: for k = 0, 1, 2, · · · until convergence do 2: variables y = D 2 r and z = D L r, we have the augmented Lagrangian for (1) where ρ > 0 is the penalty parameter, and ν y , ν z are dual variables. Note that solutions to the subproblems with respect to y and z can be computed from the proximal operators of · 1 and · 2 2 respectively in closed form. The subproblem with respect to r, however, does not admit a closed-form solution due to the exponential term in the loss. To ensure fast ADMM iterations, we leverage linearized ADMM to solve a quadratically approximated subproblem which can be efficiently solved. Specifically, given the k-th iterate (r k , y k , z k , ν y,k , ν z,k ), we consider the second order Talyor approximation to the exponential term in the augmented Lagrangian where diag(e r k ) denotes the diagonal matrix with e r k on the diagonal, and update the iterate r k+1 = argmin r L ρ (r, y, z; ν y , ν z ) which reduces to solving a sparse linear system. There are other ways to approximate the subproblem (e.g., by linearizing the proximal penalty only or both the loss and the proximal penalty), but this particular way performs empirically the best for our problem. The complete ADMM scheme is summarized in Algorithm 2, where the "SoftThreshold" in line 3 is the soft thresholding operator defined as We remark on the computational complexity of the ADMM iteration. The bottleneck of each iteration in Algorithm 2 lies in solving the linear system A −1 k B k . The size of the matrix A k is the same as the length of QPS time series, i.e., T , and note that A k is sparse banded with a bandwidth of order O(L) (L being the length of period) and a total of O(T ) nonzero entries due to the structure of the differential matrices D 2 and D L . Therefore, the general computational cost in Section 2.4 in [52]). In our experiments below, T is in tens of thousands and the linear system can be solved fairly fast.

VI. SCALING DECISION
This section elaborates on the last module of our framework, where the final scaling plan is derived from the predicted traffic dynamics. We first introduce the QoS and cost metrics and their trade-off, and then present the optimization formulations ((2), (4), and (6)) and the final scaling scheme Algorithm 4.

A. The QoS-Cost Trade-Off
We measure QoS by two criteria: Response Time (RT): The RT of each query is the time span between its arrival and the completion of its processing as or equivalently in a more compact form Hitting Probability (HP): The HP of a query is the probability that the corresponding instance is ready for processing upon arrival. Formally, the HP of i-th query is From a cloud user's perspective, RT seems more tangible than HP, and here HP is considered as an alternative in that it is a good proxy for RT and as a metric is more universal as the range is always [0, 1]. In particular, note that both HP and the expected RT are monotone in x i , and when the pending time τ i = µ τ is a constant, it is not hard to see that E[RT i ] ≤ µ s +µ τ (1−HP i ). Therefore the expected RT can be controlled below a given threshold by making the HP higher than a corresponding level.
We measure the resource cost of an instance by its lifecycle length, i.e., the time span between its creation and deletion. The total resource cost is the total length of all instances' lifecycles. To calculate the lifecycle length, note that if the query arrives before the instance becomes ready then the instance starts processing the query immediately after it is ready, hence the lifecycle length in this case is the pending time plus the processing time, i.e., τ i + s i ; Otherwise the instance stays idle for a certain amount of time until the query arrives, leading to a lifecycle length ξ i + s i − x i . Putting both cases together gives the cost of the i-th instance as cost i = (ξ i −x i −τ i ) + +τ i +s i where τ i +s i is the irreducible fixed cost of pending and processing times, and the first term is the idling time. Note that an earlier instance creation time x i improves the QoS but increases the cost cost i . Therefore, the key challenge lies in balancing the fundamental trade-off between QoS improvement and cost reduction.

B. Optimization Formulations
We use a constrained optimization to formally study the aforementioned trade-off. Assuming the current time is zero, we consider the planning of the next K instances.
1) QoS-constrained formulation: Using HP as the QoS criterion, we can specify a desired service level 1 − α, and consider minimizing the expected total cost of the next K instances subject to each query's HP being above where the fixed cost µ τ + µ s is ignored in the objective for simplicity. The stochastic constraint here is a chance constraint which is notiriously hard to solve because of nonconvexity [20]. Fortunately, this problem is separable into K individual subproblems, each having a single decision variable Therefore the optimal solution of (2) is (x * 1 , . . . , x * K ) with each x * i given by (3). Note that, however, the right hand side of (3) can be negative, due to the pending time τ i , in which case a 1 − α hitting probability is unachievable for the i-th query and the problem (2) becomes infeasible. This potential infeasibility suggests the necessity of proactively creating the i-th instance in advance in order to achieve the desired QoS level.
Alternatively, replacing the HP with the expected RT as the QoS metric yields an optimization with similar structure. In particular, with a user-specified threshold d for the expected RT, the RT-based formulation is also separable and has the optimal solution 2) Cost-constrained formulation: If a user prioritizes cost control over QoS, a cost budget B can be specified and we flip the objective and constraint in (4) to solve min x1,..., where the fixed processing time µ s is ignored in the response time objective. Again this problem is separable as for (2) and its optimal solution is Algorithm 3 Sort-and-Search for solving (5) input: Monte Carlo samples τ r i , ξ r i , r = 1, . . . , R, d, µ s 1: Sort {ξ r i } R r=1 and {ξ r i − τ r i } R r=1 into ascending order (ξ if r 1 > R and r 2 > R then  (3), (5) and (7) for the optimal scaling decisions boils down to stochastic root finding problems, which in general can be approximated via Monte Carlo sampling. We provide a sort-and-search algorithm (Algorithm 3) for approximately solving (5), and similar ones can be designed for (3) and (7)  , thus the idea is to iterate over these linear pieces from the left to the right until the piece that contains the value d − µ s is reached. Specifically, steps 4-10 of Algorithm 3 update the slope at each break point (minus 1 R when passing a ξ r i , plus 1 R when passing a ξ r i − τ r i ), step 11 updatesÊ(x) at the endpoints x l , x u using the slope in O(1) time rather than the direct summation that costs O(R) time. Since the sorting step can be done in O(R log R) time, and the search step has a linear time complexity, therefore the overall complexity of Algorithm 3 is O(R log R). The number of actions K to consider usually scales linearly with the QPS of the traffic, hence the practical computational cost is roughly O(QPS · R log R). The linear complexity in both QPS and sampling size makes our method highly scalable both in theory and practice.

C. Proactive Strategies and QoS Guarantees
As briefly mentioned in the last subsection, proactively scaling out instances is necessary for consistently maintaining a desired level of QoS, and this subsection presents a novel proactive strategy. We will use HP as our QoS criterion.
We explain the main idea of our proactive strategies. A naive strategy based on the solution (3) is to plan the instance creation time at the current time for a batch of K upcoming Algorithm 4 Sequential scaling: HP-constrained input: intensity λ t for t ≥ 0, an upper bound λ for λ t ≤ λ, target hitting probability 1−α, planning frequency m ≥ 1 initialization: total number of queries seen so far N = 0 1: Compute the threshold κ := max{i : α quantile of (γ i /λ − τ i ) < 0, i ≥ 1} (8) where γ i , τ i are independent, and γ i follows the Gamma distribution with shape i and scale 1 2: repeat Planning Step: N = N + m 10: until forever queries, and then wait until all planned K instances are consumed to do planning for the next batch of K queries. A key issue of this naive strategy however is that we may not be able to have the instances ready in time for the first few queries in each batch, because all previously created instances have been consumed at the time of planning. Therefore, a crucial step is to start planning for the next batch of queries once the number of instances left reaches a certain carefully chosen threshold κ, rather than after all are used, so that the first few upcoming queries are taken care of by the left instances and only queries that arrive further later need to be included in planning. Algorithm 4 details our proposal.
To explain Algorithm 4, in line 1 the aforementioned threshold κ is calculated in (8) by assuming the queries arrive according to a constant intensity λ that upper bounds the true λ t . According to the way κ is computed and the discussion in Section VI-B, if the query arrivals follow the constant intensity λ, for each k > κ, one is able to get the instance ready in time for the k-th upcoming query to achieve a 1 − α hitting probability. Since the actual λ t ≤ λ, the k-th upcoming query under the actual intensity always arrives later than that under λ, and thus the 1 − α hitting probability must be attainable under the actual intensity too. Lines 2-10 then updates the instance creation plan every m query arrivals. Note that in each round of planning we only need to calculate instance creation times for the (κ + 1)-th to (κ + m)-th upcoming queries because the first κ upcoming queries already have their instances scheduled in the last round. This way, we always plan instance creation times at least κ + 1 arrivals ahead, therefore the desired 1 − α hitting probability can be achieved for every single arrival.
We provide two propositions below on the hitting probability achieved by Algorithm 4 under different conditions. Proposition 1 shows that the hitting probability is exactly 1 − α when the underlying arrival process is an NHPP and the intensity is known, serving as an ideal case for Algorithm 4. In practice, however, the intensity needs to be predicted or estimated with a certain error, and in this case Proposition 2 shows that the hitting probability error grows at most linearly in the relative error of the intensity estimate that is used to make scaling decisions, therefore the attained hitting probability quickly approaches 1 − α as the intensity estimate becomes more accurate. They are formally stated as: Proposition 1. If the query arrivals {ξ i : i ≥ 1} follow an NHPP with intensity λ t , t ≥ 0 and Algorithm 4 is used with λ t as an input, then P (ξ i ≥ x * i + τ i ) = 1 − α for every i > κ. Moreover, for every N > κ the variance of the hitting ratio Note that Proposition 1 also shows that the empirical hitting ratio has a quickly diminishing variance as the queries accumulate and hence should be close to the target 1 − α.
Proposition 2. Suppose that the queries arrive according to an NHPP with unknown intensity λ * t , and that Algorithm 4 is used with an estimate λ t such that |λ t − λ * t | ≤ λ * t for some small > 0, then for each i > κ the hitting probability where q κ+m,α is the α-quantile of the Gamma distribution with shape κ + m and scale 1.
We sketch the main ideas in proving the two results. In Proposition 1, the exact 1 − α hitting probability can be established because scaling for each incoming query is planned sufficiently ahead of time as explained before. The variance of the hitting ratio of the first N queries can be controlled because scaling is planned at most κ + m steps ahead and hence by the independent-increment property of a Poisson process the hitting events of two queries are statistically independent whenever they are at least κ + m apart. This is why the usual reciprocal relationship of variance and sample size N shows up with the additional factor κ + m in the numerator. Proposition 2 is proved by first representing the hitting probability in terms of Gamma distribution functions through a time rescaling of the NHPP into a homogeneous one, so that the error analysis of hitting probabilities boils down to that of the associated integrated intensities, and then bounding the error of the latter.
The detailed proofs are as follows: Proof for Proposition 1. Denote by H t the arrival history, i.e., a list of times of arrivals, up to time t, and by h i := 1(ξ i ≥ x * i + τ i ). For each i > κ, let c i be the integer such that κ + c i m < i ≤ κ + (c i + 1)m, then the design of Algorithm 4 ensures that x * i is planned when the c i m-th query arrives, therefore by the way x * i is calculated in (7), To calculate the variance of the empirical hitting ratio, we first note that, because of the independent-increment property of NHPP and that the horizon of the scaling plan is κ + m, h i and h j are independent whenever |i − j| ≥ κ + m.
Secondly, by Cauchy-Schwartz inequality, Cov(h i , h j ) ≤ Var(h i )Var(h j ) = α(1 − α). Therefore, we can write and dividing the right hand side by (N − κ) 2 gives the desired variance bound.
Proof for Proposition 2. It follows from Proposition 1 that where the subscript λ t is used to represent the probability when the underlying intensity is λ t . Therefore, it suffices to bound the difference To proceed, we borrow the symbol c i from the proof of Proposition 1, and we know that ξc i m λ * t dt, and F k the cdf of Gamma distribution with shape parameter k and scale parameter 1. By conditioning on the instance pending time τ i and the history H cim , and timerescaling, we can express the hitting probability as where Γ denotes a Gamma random variable, and similarly , we need to use the intensity error bound and a simple bound of the Gamma pdf 1 (k−1)! x k−1 e −x ≤ 1 for all x > 0 and all integer k ≥ 1. So we have where the last inequality follows from Jensen's inequality, we obtain the probability error This concludes the error bound in the proposition.
Some practical guidelines for using Algorithm 4 are as follows. First, Proposition 1 suggests a QoS variance that scales with κ, thus we suggest using estimates of the local intensity at the current time instead of a global upper bound λ in (8) to obtain a smaller value for κ so that the QoS is stabler. Second, the hitting probability can be calibrated for better accuracy by choosing a set of nominal levels 0 < p 1 < · · · < p B < 1 to run Algorithm 4 on training data so that the resulting actual hitting probabilities 0 <p 1 < · · · <p B < 1 cover a wide range of [0, 1]. This gives a mapping between the nominal and actual hitting probabilities, which can then be used to pick the right nominal level to ensure a desired actual hitting probability.

VII. EXPERIMENTAL RESULTS
We evaluate and compare various proactive autoscaling methods on three real-world datasets to demonstrate the advantages of the proposed RobustScaler. We also evaluate and analyze various aspects, such as scalability, robustness, accuracy, and performance in real environments, of our framework.
A. Algorithms, Datasets, and Metrics 1) Autoscaling Algorithms: We consider two heuristic autoscaling strategies and three variants of our RobustScaler: • Backup Pool (BP): This strategy constantly maintains a pool of B instances. Upon each query arrival, one of the instances is used to process the query, and then the pool is immediately replenished with a new instance. Using B = 0 is equivalent to a purely reactive strategy. • Adaptive Backup Pool (AdapBP): This heuristic is an adaptive version of Backup Pool where the pool size is regularly adjusted according to the QPS level. Specifically, the average QPS during the most recent ten minutes is used as an estimate of the current arrival rate, and every ten minutes the pool size is reset to be the estimate multiplied by a pre-fixed constant. • RobustScaler-HP: This is our framework with scaling scheme Algorithm 4 but with two changes: 1) κ is chosen time-dependent according to the local intensity at each planning step to improve cost efficiency, and 2) planning frequency is specified by a fixed time interval of ∆ seconds instead of number of queries, meaning that planning is performed every ∆ seconds and in each round instance creation times that lie within the next ∆ interval are all computed. • RobustScaler-RT and RobustScaler-cost: The same as RobustScaler-HP except that the scaling decisions are computed from the solution (5) and (7), respectively. Note that many existing autoscaling algorithms rely on system metrics such as CPU and memory utilization, whereas in the scaling-per-query scenario the time of query arrival and its uncertainty are the main factors considered in making scaling decisions, therefore these method cannot handle the scaling-per-query scenario directly, and we do not include them (such as Horizontal Pod Autoscaler (HPA) scheme in Kubernetes [53]) in comparison.

2) Datasets:
We test the autoscaling methods on 3 realworld traces. The first trace, "CRS", is from the container registry service of a top cloud service provider that contains time information of a total of 21059 queries for building container images, including start and end times of query processing, over 4 weeks. The first three weeks of the CRS trace are used as training data and the last week for testing. The second dataset is the Google cluster data 2019 trace [54] that describes workloads running on eight Borg clusters for the month of May 2019. We use the job trace data of "cluster b" and use a subset of 24 hours for the experiments which has 20254 job queries in total, among which the first 18 hours of data are training and the last 6 hours are testing data. The third dataset is the Alibaba Cluster Trace 2018 [55] that contains job information of around 4000 machines over 8 days. We select 5 days of data with a total of 503850 job records, among which the first four days are for training and the last day for testing. We find that the selected parts of Google and Alibaba trace are representative of the original traces in terms of workload patterns and at the same time allow faster experimental runs and discoveries. We replay these real-world traces with various autoscalers to evaluate their performance. Figure 3 plots the QPS series of the three traces after aggregating job/query counts with a time resolution ∆t = 60 seconds. We can see that the CRS trace is quite noisy because of the relatively low traffic but seems to have a weekly pattern, and that Alibaba trace and Google trace both have recurrent spikes but the Alibaba trace has an unexpected burst/spike on the fourth day which brings challenges to modeling and prediction. Therefore, these datasets are challenging enough for differentiating different autoscaling algorithms.
3) Metrics: We use the following evaluation metrics: • hit rate: the proportion of queries for which at least one instance is ready upon arrival • total cost: the sum of lifecycle lengths in seconds of all instances • relative cost: ratio of total cost versus the cost of the pure reactive BP with B = 0 • rt avg: average response time in seconds of all queries. each of these autoscalers we vary the parameter that controls this trade-off over a sufficiently wide range and analyze the corresponding QoS and cost metrics. Specifically, in BP the pool size B is varied from 0 to 8 for CRS trace, from 0 to 450 for Alibaba trace, and from 0 to 40 for the Google trace, so that the resulting hitting probability covers a sufficiently wide range in [0, 1]. In AdapBP the pre-fixed constant is varied from zero to hundreds for each trace. Similarly, in our three RobustScaler variants the corresponding constraint values (the target HP, RT, or cost) are varied. The planning frequency ∆ is set to 1 second for our RobustScalers.
To visualize the comparison, two types of Pareto plots, hit rate vs relative cost and rt avg vs relative cost, are given for each dataset. On each Pareto plot, each line represents a certain autoscaler and each point on the line is the (hit rate, relative cost) or (rt avg, relative cost) pair generated by the autoscaler with a particular value of the controlled parameter. Therefore, in the hit rate vs relative cost plot, the closer a line stays to the top-left, the more efficient the corresponding autoscaler is in the sense that a higher hitting probability is achieved with the same cost. Similarly, in the rt avg vs relative cost plot lines that are closer to the bottom-left corner are better autoscalers. Figure 4 summarizes all Pareto plots, in which Figures 4(a), 4(c), 4(e) are hit rate vs relative cost plots and Figures 4(b), 4(d), 4(f) are rt avg vs relative cost plots. These plots clearly shows the QoS-cost trade-off for each autoscaler. E.g., in CRS trace, as the pool size of BP increases from 0 to 8, the relative cost increases to 2.2 whereas the hit rate increases from 0 to 1 and rt avg goes down from above 192 to below 180. Similar phenomena persist for our RobustScaler variants as the target hitting probability, response time, or cost varies, as well as for AdapBP.
Compared to the heuristic strategy BP, RobustScaler-HP and RobustScaler-RT are consistently better in that they achieve higher hitting rate or lower average RT than BP under the same cost in all the considered cases. All these gains are tied to our stochastically constrained optimization formulation that explicitly quantifies and optimizes the trade-off. RobustScalercost also outperforms BP in most cases, except for some cases with large relative costs on the CRS trace. However, we argue that in these high-cost scenarios the potential marginal gain in hitting probability and response time is already quite small, e.g., the hit rate is already around 95% and the rt avg only slightly above 180 (minimum is slightly below 180) when the lines of RobustScaler-cost and BP cross. Therefore from a user's perspective a relatively low overhead cost might be preferred because of the larger marginal gain in QoS, for which all our RobustScaler variants are more efficient than BP. AdapBP outperforms BP on the CRS and Alibaba traces, which is expected since the pool size is regularly adjusted to match the QPS to avoid wasting instances when queries are rare, however slightly underperforms BP on the Google trace.
Compared to AdapBP, all our RobustScaler variants are superior on the Alibaba and Google traces as they all achieve better response time (Figures 4(d), 4(f)) or hitting probability (Figures 4(c), 4(e)) under the same cost. On the CRS trace (Figures 4(a), 4(b)) the result is mixed: The RobustScaler variants underperform AdapBP when the cost is relatively low, but gradually catch up with or even surpass AdapBP (e.g., RobustScaler-HP and RobustScaler-RT) as the cost increases. Although RobustScalers do not perform the best in low-cost cases, they deliver a much stabler hitting probabilities and response times across time as the plots of QoS variance in Figure 5 show. Specifically, Figure 5(b) is plotted as follows: We first collect the response times of all the queries, and with the queries ordered by their times of arrival we average the response times of every 50 queries, and then calculate the variance of all these averaged response times which is plotted against the mean response time of all queries. Figure 5(a) is constructed via a similar procedure on hitting rate. Therefore, each line there clearly shows the variability of QoS at different mean QoS levels as each method is applied with different parameter values. It can be observed that RobustScaler-HP and RobustScaler-RT have much smaller variances hence stabler QoS than AdapBP, and RobustScaler-cost lies in between.
Motivated by the unstable QoS of AdapBP, we conduct further experiments to compare AdapBP and RobustScaler as perturbations of growing sizes are introduced into the CRS trace, and the results summarized in Figures 6 and 7 show that AdapBP is more sensitive to data changes and its performance quickly deteriorates to a worse level than RobustScalers as the perturbation size grows. The CRS trace is perturbed as follows: On one hand, starting from the beginning of the trace, for every one hour queries within a five-minute time window are deleted; on the other hand, starting from the sixth minute of the trace, for every one hour c more times of queries are added to a five-minute time window. AdapBP and RobustScaler-HP are then applied to the perturbed trace with increasing perturbation size c = 1, 2, 4, 6. Their relative performance in terms of response time and hitting rate are plotted in Figures 6 and 7, respectively, both of which clearly show that as c increases from 1 to 6 RobustScaler-HP is closing the performance gap at low-cost scenarios and finally becomes superior to AdapBP globally. This demonstrates the weakness of the simple heuristic AdapBP in handling complex workloads and the robustness of our RobustScaler.
Regarding the choice between the three RobustScaler variants, we find that none of them dominates the other two in all scenarios, but we do see that RobustScaler-HP and RobustScaler-RT perform very similarly on all the three traces. Figure 5 also shows that RobustScaler-HP and RobustScaler-RT deliver stabler QoS than RobustScaler-cost, which is related to the imposed constraints on QoS metrics in their mathematical formulations (2) and (4). Therefore, we generally recommend RobustScaler-HP and RobustScaler-RT, whereas RobustScaler-cost is prefered in scenarios with a strict cost budget constraint since RobustScaler-cost places an explicit constraint on the cost (see Section VII-B4 and Figure 10(c) for the accuracy of cost control).
2) Scalability Towards High QPS: We investigate how favorably the computation cost of our framework scales with the system workload. In the three real-world traces with a typical QPS between 0.03 and 6.3, the training time of modules 1-3 of our model is around 100 seconds with three weeks of data (CRS trace) and no more than 7 seconds with four days of data (Alibaba trace), which is short enough given that the NHPP model only needs to be retrained at a low frequency (e.g., every half an hour), and the runtime of the fourth module to generate scaling decisions is under 5 millisecond for all the three traces which therefore allows for almost instant updates of scaling decisions to accommodate rapidly changing traffic.
In order to further test the computational efficiency when facing even higher QPS, we expand the experiment to a simulated trace with a much higher QPS level up to 10000. Specifically, we use intensity function λ(t) = 1000 · 4 40 ( t mod 3600 3600 ) 40 (1− t mod 3600 3600 ) 40 +0.001 for t ∈ [0, 25200] that has an exact period of 3600 seconds to generate query arrival data over a duration of 7 hours. Note that the intensity, or the average QPS, ranges from 0.001 to 10000 which is way beyond that of the three real-world trace. A fixed pod pending time of 13 seconds is used, and an exponentially distributed query processing time with a mean of 20 seconds is used in simulation. The first 6 hours of the generated data are then used as training data and the last 1 hour as test data to evaluate our framework. All the three variants (RobustScaler-HP, RobustScaler-RT, RobustScaler-cost) are tested, where scaling decisions are updated every 5 seconds using Monte Carlo approximation with a fixed sample size 1000. The runtime of each decision update is summarized in Figure 8, and the corresponding QoS metrics are shown in Table I.
The scattered plot for runtime and QPS in Figure 8 clearly demonstrates the high scalability of all the three variants of RobustScaler. In particular, the method can still deliver scaling decision in seconds even when the QPS is in thousands which is far beyond that of the three real-world traces. The plot also shows a linear growth of the runtime relative to QPS, which is in accordance with our theoretical investigations in Section VI-B. In the case of higher QPS, the computation of decisions takes longer and hence the decisions are delayed and may become obsolete by the time they become available. This, however, can be alleviated by extending the planning horizon to compute instance creations for the next "∆+delay" instead of ∆ seconds (see the description in Section VII-A1) to compensate for the delay, or by using less Monte Carlo samples in Algorithm 3 to speed up the computation. Overall the computational burden of RobustScalers scales favorably with the workload size. In addition, such a level of scalability does not come at the expense of the accuracy of scaling decisions, since the Monte Carlo approximated decisions with sample size 1000 seem good enough for maintaining a QoS level that is close to the target level set for each variant, as shown in Table I. Note that in Table I the target level, 1 second, for response time by RobustScaler-RT is set with the processing time excluded, i.e., for the quantity d − µ s in (5). Similarly, the target cost level, 2 seconds per instance, set by RobustScaler-cost, is for the average idling time of an instance.
3) Robustness Against Missing Data and Anomalies: We test the robustness of our autoscalers on Alibaba trace that has an unexpected burst/anomalies, and also on the CRS trace by injecting missing data. In particular, we erase the burst in the Alibaba trace to make the pattern more clear and obvious, and for CRS we inject missing data by removing all the queries in one entire day of the fourth week. We then rerun the experiments with the new modified traces. If (a) hit rate vs relative cost on CRS trace (b) rt avg vs relative cost on CRS trace (c) hit rate vs relative cost on Alibaba trace (d) rt avg vs relative cost on Alibaba trace Fig. 9. Comparison before and after anomaly removal or missing data injection, line legends that end with "w/" are results with anomaly/missing data, and those ending with "w/o" are results without anomaly/missing data. the QoS and cost metrics generated by the autoscaler before and after the modifications are similar then the autoscaler can be considered robust against anomalies and missing data. Figure 9 summarizes the results for RobustScaler-HP and RobustScaler-cost and it is clear that the resulting QoS and cost metrics are almost identical on the original and modified traces. We also examine the corresponding high-level quantiles (75%, 95%, 99% and 99.9%) of the response times to better characterize the sensitivity to anomalies and missing data. It turns out that both RobustScaler variants have the exactly same response time quantiles at all considered levels before and after removing the anomalies on Alibaba trace, and the changes of the quantiles on the CRS trace are very tiny as shown in Table II. In addition, the comparison with AdapBP under perturbed QPS data in Figures 6 and 7 also reveals the stable performance of RobustScaler under data perturbations. All these demonstrate the robustness of our autoscalers against missing data and anomalies.

4) Accurate Control of QoS/Cost Levels and Effects of Planning Frequency:
Our theory suggests that RobustScaler is guaranteed to achieve a pre-specified hitting probability if the arrival process is approximately Poisson, and here we test the accuracy of RobustScaler in maintaining a pre-specified level of QoS in practice on the CRS trace. Figures 10(a), 10(b), 10(c) show the comparison of the actual HP, RT, and cost values collected from the results and the corresponding nominal values used in our RobustScalers. Ideally, these two sets of values shall be on the straight line y = x which is marked as dotted line in each plot, and we see that they are indeed very close to the line, demonstrating the advantage of our RobustScalers in achieving a promised level of QoS/cost. Another aspect of our autoscalers that we study here is the planning frequency. We mentioned that more frequent decision planning leads to more savings in cost, and to validate this claim on real data, we increase the ∆ of RobustScaler-HP from 1 to 60 seconds and the corresponding results are summarized in Figure 10(d). It clearly shows that as the planning interval ∆ gets larger, the more costly the decisions will be in order to attain the same level of response time.
Apart from the stochastically constrained optimization used to generate scaling decisions, another key ingredient that affects the accuracy of scaling decisions is the estimation accuracy of the query arrival intensity, as explained by our Proposition 2. To quantitatively examine the impact of our periodicity regularization on the estimation accuracy, we compare the mean squared error (MSE) and mean absolute error (MAE) of the intensity estimate given by (1) and another estimate by the same loss but without the periodicity regularization term. Specifically, we generate arrival data from the ground truth intensity λ(t) = 4 10 ( t mod 86400 86400 ) 10 (1 − t mod 86400 86400 ) 10 + 0.1 for t ∈ [0, 604800] with a period length of 86400, and apply (1) with or without the periodicity regularization to train the intensity model. The errors of the intensity estimates are summarized in Table III, which shows that the periodicity regularization boosts the accuracy for 40-60% as measured by MSE or MAE. This demonstrates the advantage of the periodicity regularization in practical scenarios where periodicity is common.

5) Deployment in A Real Environment:
We also deploy and test our framework in a real-world autoscaled system. In the simulated environment, the time elapsed in computing scaling decisions are not taken into account in the autoscaling procedure and hence the obtained decisions never become obsolete, e.g., a scaling decision that says "create a pod in 5 seconds from now" is assumed available and executed exactly at the prescribed time even if the computation of the decision itself takes longer than 5 seconds in physical time. Therefore a key difference of real environments from the simulated one, among others, is that not only the scaling decision itself but also the runtime of our algorithm execution will directly affect the scaling process.
The CRS trace is used to generate queries from a client and then send to a server. When the server receives a query, it finds an available instance if there is any or create a new one in an Alibaba Serverless Kubernetes (ASK) cluster, and the instance then sleeps for a certain amount of time to mimic the processing time of a real meaningful query. When the sleeping ends, the instance is immediately deleted. Each instance is built with the Alpine container image with a 4-core CPU and 8GB RAM. We test the performance of RobustScaler-HP in autoscaling the system with a target hitting probability level of 0.9. Like in the previous simulated environment, the first three weeks of the trace are used as training data and the last week as testing. Table IV summarizes the performance of RobustScaler-HP under real and simulated environments. It can be seen that the achieved hitting probabilities, response times, and costs in seconds are close to each other. This shows that our algorithm continues to work as expected in real environments, and that thanks to the high computational efficiency of our method the adversarial impact of delay of scaling decisions is minimal.
VIII. CONCLUSION In this paper we propose a novel proactive autoscaling scheme RobustScaler for the scaling-per-query cloud computing scenario, which achieves superior trade-off between cost and QoS and is robust to noise, missing data and anomalies. We leverage NHPP with specialized regularization techniques to flexibly capture both periodicity and stochasticity of query arrivals with an efficient ADMM solution. Furthermore, we formulate a stochastically constrained optimization and a sequential scaling scheme with provable probabilistic performance guarantees to achieve better scaling decisions than heuristic strategies. Our extensive experiments demonstrate the effectiveness and efficiency of RobustScaler in both simulated and real environments.