# Lifting the Fog of Uncertainties: Dynamic Resource Orchestration for the
Containerized Cloud

Yuqiu Zhang<EMAIL_ADDRESS>University of TorontoDepartment of
Electrical and Computer EngineeringCanada ,  Tongkun Zhang
<EMAIL_ADDRESS>University of TorontoDepartment of Electrical
and Computer EngineeringCanada ,  Gengrui Zhang
<EMAIL_ADDRESS>University of TorontoDepartment of Electrical
and Computer EngineeringCanada and  Hans-Arno Jacobsen
<EMAIL_ADDRESS>University of TorontoDepartment of Electrical and
Computer EngineeringCanada

###### Abstract.

The advances in virtualization technologies have sparked a growing transition
from virtual machine (VM)-based to container-based infrastructure for cloud
computing. From the resource orchestration perspective, containers’
lightweight and highly configurable nature not only enables opportunities for
more optimized strategies, but also poses greater challenges due to additional
uncertainties and a larger configuration parameter search space. Towards this
end, we propose Drone, a resource orchestration framework that adaptively
configures resource parameters to improve application performance and reduce
operational cost in the presence of cloud uncertainties. Built on Contextual
Bandit techniques, Drone is able to achieve a balance between performance and
resource cost on public clouds, and optimize performance on private clouds
where a hard resource constraint is present. We show that our algorithms can
achieve sub-linear growth in cumulative regret, a theoretically sound
convergence guarantee, and our extensive experiments show that Drone achieves
an up to 45% performance improvement and a 20% resource footprint reduction
across batch processing jobs and microservice workloads.

##  1\. Introduction

The last decade has witnessed the rise of cloud computing, a paradigm which
revolutionized the entire IT industry (Fox et al., 2009; Jonas et al., 2019).
More recently, the rise of containerization technologies (Soltesz et al.,
2007) has further necessitated the prevalence of using the cloud to deploy
large-scale analytical computing jobs or user-facing web applications thanks
to containers’ lightweight nature compared to their predecessor virtual
machines (VMs). In terms of resource orchestration, containers also showcase
much finer-grained controllability. For example, the smallest unit of resource
configuration of a single container is in the magnitude of bytes for memory
and millicores for CPU (doc, 2023; k8s, 2023), while for VMs users are usually
only able to select from a pre-configured family and instance type which
differ from each other in the granularity of entire CPU cores and gigabytes
for memory (e.g., ¡2vCPU, 4GiB Memory¿ for m5.large and ¡4vCPU, 16GiB Memory¿
for m5.xlarge instances on AWS EC2 (aws, 2023a)). Furthermore, being smaller
in size and having lower overhead to start, stop or schedule, containers are
particularly suitable for deploying microservices, a new software architecture
that breaks a monolithic application down to a set of loosely coupled
components for independent and faster deployment and iteration (Luo et al.,
2021; Eismann et al., 2020).

Despite the benefits, due to additional fluidity they bring to the cloud, the
wide adoption of containers also introduces greater _cloud uncertainties_ ,
which has already been an active research area (Kabir et al., 2021). A major
uncertainty that significantly influences resource orchestration decisions is
workload uncertainty (Kabir et al., 2021; Luo et al., 2022; Dean and Barroso,
2013). Should a resource orchestration strategy fail to adjust to workload
traffic in time, resource _under-_ or _over-provisioning_ might be caused,
which results in service level agreement (SLA) violations or higher
operational cost. Both cases are cost-inefficient and are hence undesirable.
Consequently, numerous studies (Luo et al., 2022; Al-Sharif et al., 2017;
Ghobaei-Arani et al., 2018; Zhang et al., 2019; Qiu et al., 2020; Rzadca et
al., 2020; Kannan et al., 2019; Baarzi and Kesidis, 2021) have proposed more
intelligent approaches to adapt resource orchestration policies to workload
changes. However, other uncertainties, though sometimes minor, can also become
non-negligible factors that affect application performance or operational
cost. Examples include existing cloud resource usage, inter-container traffic
patterns, and the underlying computing framework on which the application runs
(Shi et al., 2015). The shared nature of the cloud along with volatile
incentives promoted by public cloud vendors (e.g., Spot and Burstable
Instances on AWS (aws, 2023b, c)) further makes the resource-performance/cost
relationship non-structural and time-variant. Failing to consider these
uncertainties may also lead to inefficient resource allocation policies, as we
show in Section 3.

To address resource orchestration challenges induced by cloud uncertainties,
we design Drone, an online resource orchestration framework for the
containerized cloud. The idea is to progressively optimize a containerized
application’s resource configuration over its lifespan with minimum manual
intervention and the often-costly explicit workload profiling phase. At its
core, Drone is built upon recent advances in Gaussian process-based contextual
bandits (Krause and Ong, 2011). By encompassing time-variant cloud
uncertainties as contextual parameters, Drone follows an iterative procedure
to continuously refine resource configurations based on the previous context-
action pairs and collected performance metrics. Assuming a minimal structural
relationship between application performance and resource configurations, the
power of such a non-parametric model makes Drone versatile across a diverse
range of cloud environments and adaptable to various application types and
workloads. Specifically, we examine two settings within a shared cloud
infrastructure: a) _public cloud_ , where computational resources can be
effectively considered unlimited and Drone demonstrates adeptness in striking
an efficient balance between performance and cost, and b) _private cloud_ ,
where there exists a stringent cap on computational resources and Drone proves
capable of optimizing application performance within these resource
constraints. Drone is also theoretically sound in both settings since it
achieves a sublinear growth of cumulative regret, meaning that the algorithm
converges fast with respect to its running time.

We evaluate Drone by deploying various applications on our cloud-hosted
Kubernetes cluster using Drone as an integrable resource orchestrator. Our
extensive experimental analysis, employing realistic workloads, demonstrates
Drone’s superior performance compared to alternative solutions in several
respects. First, for recurring analytical jobs for which bandit-based
approaches have been shown to be efficient (Alipourfard et al., 2017; Liu et
al., 2019), Drone exhibits further improvement in performance by accounting
for a broader spectrum of cloud uncertainties, coupled with its adherence to
resource constraints in the private cloud environment. Second, for user-facing
microservices where workload variability is more ad-hoc and no explicit
profiling phase is available, Drone also achieves a 37% improvement on P90
latency compared to state-of-the-art alternatives, a result further amplified
by our bespoke enhancements over the standard bandit optimization procedure,
including a sliding window-based data sampler, empirically optimized starting
point selection and latency-aware scheduling mechanisms. To the best of our
knowledge, Drone is the first work to harness the potential of resource
allocation in a containerized cloud using bandit-based approaches. It
showcases superior adaptability across diverse settings in comparison to the
preceding VM-based efforts. To sum up, we make the following contributions in
this paper:

  1. (1)

Through comprehensive experimental analysis, we validate the non-structural
performance-resource relationship and the significant influence of
uncontrollable time-variant environment variables (the cloud uncertainties) on
application performance under multiple cloud scenarios.

  2. (2)

Leveraging recent advances in bandit algorithms, we design Drone, a general-
purpose online resource orchestration framework for container-based cloud
systems. Drone progressively optimizes the performance-cost tradeoff in public
cloud environments, while maintaining strict adherence to resource constraints
in resource-limited private clouds. In both cases, Drone theoretically
exhibits a fast convergence rate, guaranteeing its performance.

  3. (3)

We implement Drone as a customized resource orchestrator on top of Kubernetes.
Using realistic cloud workloads, we show through extensive experiments that
Drone outperforms state-of-the-art alternatives in terms of application
performance, cost efficiency and resource constraint compliance.

##  2\. Background and Related Work

###  2.1. Cloud Resource Orchestration

Framework Application Computing Platform Optimization Objective Acquisition
Function Cloud Uncertainties (contexts) Resource Limits (safety) Workload
Convergence Guarantee Dremel (Zhao et al., 2022) DB Tuning - DB IOPS UCB ✗ -
DB queries ✗ CGPTuner (Cereda et al., 2021) DB Tuning - Performance
Improvement GP-Hedge Workload only - Recurring DB queries ✗ Cherrypick
(Alipourfard et al., 2017) VM config. selection VM Customized Cost EI ✗ ✗
Recurring analytical jobs ✗ Accordia (Liu et al., 2019) VM config. selection
VM Customized Cost GP-UCB ✗ ✗ Recurring analytical jobs ✓ RAMBO (Li et al.,
2021) Resource orchestration Container Customized Cost SMSego ✗ ✗
Microservices ✗ Drone Resource orchestration Container Performance-cost
tradeoff (public cloud) Performance opt. (private cloud) GP-UCB ✓ ✓ General ✓

Table 1. Computer systems studies using bandit algorithms.

Intelligent resource orchestration on the cloud has long been an active
research area which can be categorized as follows based on the underlying
techniques adopted.

Heuristic-based Approaches. A simple yet practically effective resource
orchestration choice is based on heuristics. They are usually intuitive and
easy to implement and hence are widely adopted in industrial solutions
(Autoscalers., 2023; aws autoscaling service., 2021; cloud compute engine
autoscaler., 2021; azure autoscaler., 2021). For example, the default
container autoscalers in Kubernetes (Autoscalers., 2023) include _Horizontal
Pod Autoscaler (HPA)_ and _Vertical Pod Autoscaler (VPA)_ , both of which
follow a rule-based scaling policy. Such policies enable cloud tenants to
define thresholds for interested metrics according to which the system
performs autoscaling. However, setting appropriate thresholds for such metrics
is a non-trivial task. The optimal values are often application-specific and
require expert knowledge from the developer or system administrator.
Therefore, such heuristic approaches can hardly generalize across various
cloud applications and often involve significant manual efforts.

Model-based analytical approaches. Another line of work establishes analytical
models to encapsulate the relationship between performance objectives and
resource orchestration decisions. The problem is thus often modelled as an
optimization problem and certain assumptions are usually made on the problem
structure (e.g., linearity and convexity) so that theoretical properties can
be utilized to efficiently solve the problem (Keller and Karl, 2014;
Liakopoulos et al., 2019; Chouayakh and Destounis, 2022; Chen et al., 2017;
Ali-Eldin et al., 2012; Jiang et al., 2013). Control theory and queuing theory
are also common theoretical tools for designing resource management solutions
(Gias et al., 2019; Ali-Eldin et al., 2012; Grimaldi et al., 2015; Baarzi and
Kesidis, 2021). Despite the favorable theoretical characteristics of such
solutions, real-life cloud applications generally fail to satisfy the desired
problem structure due to varying workload profiles and other cloud
uncertainties (Alipourfard et al., 2017).

Predictive approaches using machine learning (ML). To mitigate over-
provisioning overhead and human effort of heuristic-based solutions,
predictive approaches predict future workload or system behavior with past
statistics and adjust resource allocation in advance to meet future
application needs. This type of approaches usually employs well-established
machine learning models, such as linear regression (Bodík et al., 2009;
Venkataraman et al., 2016), support vector machine (Yadwadkar et al., 2014)
and various types of neural networks (Hazelwood et al., 2018; Zhang et al.,
2019; Gan et al., 2019b; Park et al., 2021; Luo et al., 2022; Wang et al.,
2022; Borkowski et al., 2016). Although effective in certain conditions, these
ML-based approaches have their intrinsic limitations. First, to deploy such
solutions, an exclusive profiling/training phase is generally needed, which
can be costly and not available in production-level realistic systems. Second,
such ML-based solutions perform best with general workloads or workloads with
repeating patterns similar to their training data, but they adapt poorly to
fluctuating workloads (Zhang et al., 2019). Moreover, training data quantity
and quality impact the performance of an ML model to a significant extent. It
is also non-trivial and requires specialized domain knowledge to select
representative training data and costly retraining is often needed if workload
shift happens.

More recently, Reinforcement learning (RL) has captured attention from the
resource management community (Qiu et al., 2020; Mao et al., 2019b, a; Rossi
et al., 2019), thanks to its ability to interact with the environment while
optimizing its resource allocation actions. However, apart from the fact that
RL frameworks also need to pre-train their agents and hence share similar
limitations to the aforementioned ML models, they usually fail to achieve a
convergence guarantee. Also, in RL models, actions taken are in turn affecting
the environment (i.e., the states), while in real-life clouds, many
environment variables are independent of actions, such as workload uncertainty
which comes directly from the end users.

###  2.2. Bandit Algorithms

The limitations of existing work suggest that an ideal resource orchestration
framework should optimize resource allocation decisions in an online manner
with minimum model pre-training and human intervention. More importantly, it
should work efficiently in today’s complex containerized cloud, taking various
cloud uncertainties into account and fitting in different cloud settings. To
this end, we resort to the contextual bandit approach (Krause and Ong, 2011),
a data-efficient non-parametric solution. Contextual bandit is an extension of
the well-studied Multi-Armed Bandit (MAB) problem (Slivkins et al., 2019) by
incorporating contextual information about uncontrollable environment
variables, such as cloud uncertainties in the cloud computing context. The
original MAB problem is a sequential optimization problem, where a player
sequentially selects from a finite set of options with probabilistic rewards
to maximize the total reward over time. Bayesian Optimization (BO) is a
continuous variant of the MAB problem which aims to find the optimizer of a
black-box function by incrementally building a model of the objective
function. Although part of our control domain (e.g., fine-grained container
resource scaling) can be considered continuous which makes our problem
essentially a BO with contextual extension, we stick to the term contextual
bandits throughout this paper to highlight the contextual nature and align
with the theoretical literature.

Bandit algorithms in computer systems research. Due to the ability to model
arbitrary performance functions, bandit algorithms have also been employed in
computer system-related research, such as database parameter tuning (Cereda et
al., 2021; Zhao et al., 2022; Marcus and Papaemmanouil, 2017) and VM
configuration selection (Alipourfard et al., 2017; Liu et al., 2019; Hsu et
al., 2018). Dremel and CGPTuner (Cereda et al., 2021; Zhao et al., 2022) use
bandit algorithms to fine-tune DBMS-specific parameters and the sole objective
is to maximize database performance without constraints, while we focus on a
lower level of resource orchestration and consider the performance-cost
tradeoff. The closest works to ours are Cherrypick (Alipourfard et al., 2017)
and Accordia (Liu et al., 2019). Cherrypick is among the first works to apply
bandit algorithms to systems research, aiming to pick the best VM
configuration using Bayesian Optimization for big data analytical jobs. It
uses Expected Improvement (EI) as its acquisition function, which lacks a
convergence guarantee. Accordia studies the exact same problem, and advances
one step further by employing the recent GP-UCB algorithm (Srinivas et al.,
2009) with convergence guarantee. However, both Cherrypick and Accordia have
inherent limitations which prevent them from being readily applicable to the
current containerized cloud. First, both works study the VM configuration
selection problem where only a finite set of options are available, while
finer-grained, almost-continuous control is possible for containers, as
mentioned in Section 1. Second, both Cherrypick and Accordia focus on
_recurring_ analytical jobs, whose workload patterns are regular and
predictable. Therefore, they are implicitly using the first few runs of the
recurring job as the training phase and thus cannot generalize to workload
variations. Last but not least, their performance objectives are solely
dependent on the actions taken, and they assume infinite resources without
considering the uncontrollable cloud uncertainties and resource-limited
private clouds. Drone, on the other hand, is uncertainty-aware and generalizes
to different cloud workloads and settings. We would also like to mention RAMBO
(Li et al., 2021), a BO-based resource allocation framework for microservices.
Although RAMBO solves a similar problem to our work, technical details of
implementation and design choices are not sufficiently provided in the paper.
A detailed comparison between Drone and closely related works is summarized in
Table 1.

##  3\. Problem Analysis

In this section, we show through experimental analysis important observations
which motivate our work. To justify the complex performance-cost relationship
and the substantial impact of cloud uncertainties on application performance
in a containerized cloud, we set up a cloud-hosted testbed consisting of 16
VMs (see Section 5 for detailed specifications) to run benchmarking jobs. All
jobs are submitted as Kubernetes-managed containers unless otherwise
specified.

(a) Spark on Kubernetes.

(b) Spark on VMs.

Figure 1. Performance of representative Spark analytical workloads under
different RAM allocations.

Figure 2. Sort performance on Flink and Spark.

Figure 3. The Sockshop architecture.

Figure 4. CDF of microservice end-to-end latency with two node affinity rules.

Non-structural performance-cost relationship. To study the relationship
between application performance and allocated resources, we benchmark three
representative analytical workloads running on the native Spark Operator on
Kubernetes (on-k8s-operator by Google Cloud Platform, 2023): PageRank, Sort
and Logistic Regression (LR). PageRank is a graph-processing algorithm for
which we use the Pokec social network graph data (Takac and Zabovsky, 2012)
with 1.6M vertices and 30M edges. We use gensort (Benchmark, 2022) to generate
150GB of randomly permuted 100-byte records for sorting. For LR, we use a
4-year span of ~400k stock price records from the Nifty 100 Index (min) data,
2022) to train the model. Experiments are repeated five times and the results
are shown in Figure. 1(a). While allocating more RAM generally leads to better
performance, beneficial theoretical attributes such as linearity and convexity
are not manifested in this relationship. For example, LR does not suffer from
performance gain saturation when given excessively more RAM, displaying an
over 2x performance improvement with increasing RAM allocation from 96GB to
192GB because it benefits from more RAM as a memory-bound job. More
interestingly, the performance-cost relationship can even be non-monotonic,
meaning more resources does not necessarily lead to performance improvement,
as can be observed for PageRank. This is largely due to the fact that PageRank
is an iterative network-intensive algorithm where data shuffling between not-
co-located containers is needed in each operation. In this case network
bandwidth is the major bottleneck instead of RAM.

We repeat the same experiments using identical configurations on the vanilla
Spark cluster deployment without involving containers and report the results
in Figure. 1(b). Although the performance metrics and the performance-cost
relationship patterns are similar to the containerized setting, an important
finding is that the variance of performance measurements in the VM-based
setting (indicated by black confidence intervals on each bar) is much smaller.
The stability is in part owing to the more mature architectural support, but
also corroborates our insight that greater uncertainties and anomalies are
introduced in a containerized cloud. In fact, we do observe more frequent
Spark executor errors and restarts on Kubernetes.

Impact of cloud uncertainties. We also show that besides workload intensity,
other uncontrollable cloud uncertainties can also significantly impact
application performance. To better model adverse situations in a shared cloud,
we apply interference injection across experiments to create random resource
contention (Qiu et al., 2020), including CPU utilization, RAM bandwidth and
network latency and bandwidth. The interferences’ occurrence follows a poisson
process with average rate of 0.5 per second. The intensity of each
interference is uniformly and independently chosen at random between [0,50%]
of the total capacity. We first study the performance of sorting varying sizes
of data on the Kubernetes deployment of Spark and Flink (on Kubernetes, 2023).
All experiments are conducted five times with the same resource configuration
(36 CPU cores and 192GB of total RAM) and identical data for one size. The
results are shown in Figure 2. We can observe that the variance across
multiple runs increases with data size, reporting a coefficient of variation
of up to 23% for Spark and 27% for Flink, indicating that application
performance can be quite variable due to cloud uncertainties other than
workload, especially with a large volume of data which is common in the
current “big data era”. From the performance discrepancy between Spark and
Flink, we can also see that the performance is platform-dependent, meaning
that even if we have found the optimal resource configuration for one specific
workload, it is not readily transferable to other platforms running the same
workload and thus additional configuration tuning may be required.

The impact of cloud uncertainties can be even more serious for microservice
applications, due to their complicated calling graphs and the resulting inter-
container communication patterns (Luo et al., 2021; Zhou et al., 2018).
Towards this end, we deploy an example microservice application Sockshop
(Inc., 2021) consisting of 10+ stateless and database microservices which
simulates an online shopping web service. The architecture of Sockshop is
shown in Figure 3. It is evident that the Order microservice can be a
performance bottleneck due to its connection with several other microservices.
With the same resource configuration and workload, we compare the end-to-end
latency of two affinity rules and show the Cumulative Distribution Function
(CDF) in Figure 4. We can find that if we forcefully isolate Order from other
microservices (by setting node-affinity rules for corresponding pods in
Kubernetes), the performance is 26% worse in terms of P90 latency than the
case where we try to colocate Order with other microservices in a best-effort
manner. This finding further verifies our claim that the impact of non-
workload uncertainties can be significant, and amount-irrelevant resource
orchestration decisions can also be deciding factors for application
performance.

##  4\. Drone Design

In this section, we present Drone, our dynamic resource orchestrator for the
containerized cloud. Starting with a brief introduction of contextual bandits
and why it is a promising choice for the problem context, we then detail our
design and algorithms under both public and private cloud settings. Finally,
the implementation and domain-specific optimizations are discussed which
complement practically our algorithmic contribution.

###  4.1. Overview of Contextual Bandits

As briefly discussed in Sec. 2.2, it is natural to deduce the mapping from
contextual bandits to the cloud resource orchestration problem. The ultimate
goal is to dynamically adjust resource allocation decisions to optimize an
objective value (e.g., performance and/or cost) in the presence of time-
variant cloud uncertainties. Formally speaking, we want to find the best
resource configuration $x^{*}$ from action space $\mathcal{X}$ with
uncertainty context $\mathbf{\omega}\in\Omega$ such that the objective
function $f$ is optimized:

(1) $x^{*}=\operatorname*{arg\,max}_{x\in\mathcal{X}}f(x,\mathbf{\omega})$

From this formulation, we can see that $f$ is dependent on not only the
decision variable $x$, but also the context $\mathbf{\omega}$. The output of
$f$ can be any scalar value that is of the most interest to the user. Common
choices include application performance indicators (e.g., latency, throughput,
response time), utility, and cost. Note that (1) is also often formulated as a
minimization problem if $f$ is a cost function or captures latency/response
time, but the essence of the problem remains unchanged. The action $x$ and
context $\mathbf{\omega}$ are vectors with domain-specific dimensions,
containing all possible resource orchestration decisions and contextual
parameters, respectively. We discuss the concrete dimensions we consider in
our problem context in Sec. 5.1. Since the objective function has no
structural relationship with the resource orchestration actions, as we point
out in Sec. 3, we can only obtain an objective value by querying the
corresponding action. In this case, an exhaustive search of the optimal action
is clearly intractable, especially when the action space
$\mathcal{X}\in\mathrm{R}^{d}$ is a continuous domain, and the dimension $d$
is high.

Towards this end, the contextual bandit approach significantly reduces the
search cost by intelligently guiding the next action to search for in an
iterative optimization process. Specifically, in each time step $t$, the
optimization agent receives a context $\mathbf{\omega}_{t}$ from the
environment. Based on the context, the agent then chooses an action $x_{t}$
from the action space $\mathcal{X}$, executes this action, and then receives a
reward $y_{t}=f(x_{t},\mathbf{\omega}_{t})+\varepsilon_{t}$ as a result of the
action taken, where $\varepsilon_{t}$ is a Gaussian noise
$\varepsilon_{t}\sim\mathcal{N}(0,\sigma^{2})$. The noise term well
encapsulates the fact that in practice we can only observe a perturbed
function value due to unavoidable measurement error. The optimization process
then proceeds on to time step $t+1$ with the reward-input pair
$(y_{t},x_{t},\mathbf{\omega}_{t})$ appended to the history information to
further guide searching in the next iteration.

To evaluate the quality of the actions taken, we use _cumulative regret_
$R_{T}$ which measures the cumulative performance gap over the complete
algorithm running span of $T$ time steps, a common metric to assess an online
sequential optimization algorithm (Srinivas et al., 2009):

(2)
$R_{T}=\sum_{t=1}^{T}\left(\max_{x^{*}\in\mathcal{X}}f\left(x^{*},\mathbf{\omega}_{t}\right)-f\left(x_{t},\mathbf{\omega}_{t}\right)\right)$

A desired property for an efficient online algorithm is to have _sub-linear
regret growth_ : $\lim_{T\rightarrow\infty}{R_{T}/T\rightarrow 0}$, meaning
that we can quickly find (near-)optimal actions so that the performance gap
converges to zero relatively fast. As we will show in the following sections,
Drone achieves sub-linear regret growth in both public and private cloud
settings.

###  4.2. Public Cloud: Cost-aware Performance Optimization

We first propose our contextual bandit-based algorithm to jointly optimize
application performance and resource cost in public cloud environments where
computational resources are unlimited.

Why can we assume infinite resources? It seems natural to assume that
computational resources are infinite on public clouds, as previous works
(Alipourfard et al., 2017; Liu et al., 2019) also instinctively did. While the
assumption is plausible given the massive scale of major cloud providers111For
example, it was reported that over 1.4 million servers were hosted on AWS back
in 2014 (how big is Amazon’s AWS business?, hint: it’s absolutely massive).,
it may not be readily justifiable from the perspective of individual users or
small businesses. For instance, if users are at the edge of their budget for
cloud resource renting, they may not be willing to acquire more resources even
if that can bring better application performance. In fact, this assumption can
be rationalized by cost-saving incentives provided by public cloud, such as
Spot Instance (aws, 2023b) and Burstable Instance (aws, 2023c) on
AWS222Similar offerings are also available on other major providers, such as
Spot Virtual Machines on Azure (azu, 2023) and Google Cloud (gcp, 2023).. Spot
instances are preemptive, low-priority VMs at a considerably lower price than
on-demand instances333Here, we focus on the cost-saving benefit of spot
instances. Users may choose to only deploy non-critical jobs and stateless
microservices on spot instances to minimize issues due to potential
revocations.. Burstable instances are VMs that have the ability to “burst” to
a significantly higher resource configuration than their normal capacity to
handle ephemeral and infrequent workload peaks, which is much cheaper than on-
demand instances with the same full capacity. We profile the cost-saving
effects of spot and burstable instances by issuing the same batch processing
(Sort) and microservice workload with the regular instance m5.large as
baseline. Table 2 depicts the normalized cost savings of running the same
workload across cloud incentive combinations. We observe an up to 7.19x cost
saving by employing burstable spot instances and 6.1x cost savings with spot
instances alone, both showing notable cost efficiency over on-demand regular
instances. Therefore, by judiciously adopting these cloud incentives, one can
expect a significant cost reduction achieving the same application
performance, meaning that under the same budget, a significantly larger
resource configuration search space is available, and this in turn justifies
the infinite resources assumption.

| m5.large | Spot only | Spot + Burstable
---|---|---|---
Batch jobs | 1x | 6.10x | 7.19x
Microservices | 1x | 5.28x | 6.73x
Table 2. Normalized cost savings from cloud incentives. Figure 5. Spot
instance prices from April 2023 for m5.16xlarge, c5.18xlarge and r5.16xlarge
instance types on AWS.

Another interesting finding is that spot prices can vary drastically with time
in an unpredictable manner. Figure 5 shows spot prices of three instance types
over a 1-month time span, which exhibit no regular patterns and vary across
instance types to a great extent. This suggests that the spot price is an
additional contextual dimension to be considered which can greatly impact the
resource cost.

Problem formulation. Given the assumption of unlimited resources, the
optimization objective on public clouds is to keep a balance between
application performance and the monetary resource cost. Formally, our
optimization problem can be formulated as maximizing a reward function $f$:

(3) $\displaystyle\max_{\mathbf{x_{t}}}\quad$ $\displaystyle
f(x_{t},\mathbf{\omega}_{t})=\alpha p(x_{t},\mathbf{\omega}_{t})-\beta
c(x_{t},\mathbf{\omega}_{t})$ (4) $\displaystyle s.t.\quad$
$\displaystyle\mathbf{x_{t}}\in\mathcal{X},\mathbf{\omega}_{t}\in\Omega,\quad\forall{t}$

where $p(x_{t},\mathbf{\omega}_{t})$ is the application performance indicator
which can be measured at the end of each time step $t$;
$c(x_{t},\mathbf{\omega}_{t})$ is the resource cost associated with the
resource orchestration decision $x_{t}$ and cloud uncertainties enclosed in
the context $\mathbf{\omega}_{t}$. $\alpha$ and $\beta$ are configurable
weights that capture a user’s preference between performance and cost.

How to guide the search process? By a sequential optimization process,
contextual bandit-based algorithms are able to learn more about the objective
function $f$ in every iteration with newly observed data resulting from
evaluating $f$ at point $(x_{t},\omega_{t})$. Therefore, a key design choice
of contextual bandits algorithms is to determine how to choose the next point
to evaluate so as to learn the most about the objective function. Towards this
purpose, we first need to put a surrogate model on $f$ so that it can be
efficiently updated iteratively. In Drone, we choose Gaussian Process (GP)
(Williams and Rasmussen, 2006), a common choice adopted by prior works
(Alipourfard et al., 2017; Liu et al., 2019; Cereda et al., 2021; Li et al.,
2021). As a non-parametric model, GP assumes a function is sampled from a
Gaussian distribution, which adds a minimal smoothness assumption on the
objective function such that function values evaluated at close inputs will
also be close. Formally, let $z\in\mathcal{X}\times\Omega$ be a joint action-
context pair, a GP$(\mu,k)$ is fully specified by its mean function
$\mu(z)=\mathbb{E}[f(z)]$ and covariance or kernel function
$k(z,z^{\prime})=\mathbb{E}[f(z)-\mu(z)(f(z^{\prime})-\mu(z^{\prime}))]$ which
acts as the data-independent prior distribution. Now define that
$y_{t}=f(z_{t})+\epsilon_{t}$ is a noisy sample of true function value
$f(z_{t})$ and $\mathbf{y}_{T}=[y_{1},y_{2},\cdots,y_{T}]$ are evaluated at
points $Z_{T}=[z_{1},z_{2},\cdots,z_{T}]$ (the past data points). Assume now
we are given a new $z^{*}$ and would like to infer the function value $f^{*}$,
we can get a closed-form posterior distribution which is also a GP with the
following mean and variance:

(5) $\displaystyle\mu_{T}\left(z^{*}\right)$
$\displaystyle=\mathbf{k}_{T}\left(z^{*}\right)^{\top}\left(\mathbf{K}_{T}+\sigma^{2}\mathbf{I}\right)^{-1}\mathbf{y}_{T}$
(6) $\displaystyle\sigma_{T}^{2}\left(z^{*}\right)$
$\displaystyle=k\left(z^{*},z^{*}\right)-\mathbf{k}_{T}\left(z^{*}\right)^{\top}\left(\mathbf{K}_{T}+\sigma^{2}\mathbf{I}\right)^{-1}\mathbf{k}_{T}\left(z^{*}\right)$

where
$\mathbf{k}_{T}(z^{*})=[k(z_{1},z^{*}),k(z_{2},z^{*}),\cdots,k(z_{T},z^{*})]$
and $\left[\mathbf{K}_{T}\right]_{ij}=k\left(z_{i},z_{j}\right)$ is the kernel
matrix. We choose the widely adopted Matern kernel with $\nu=\frac{3}{2}$
following empirical practices. These analytical equations allow us to
efficiently infer the function value at a new point based on previous
observations and action-context pairs.

Another key element of contextual bandits is to determine how to suggest the
next point to evaluate so as to learn most about the objective function. This
is achieved by choosing the point maximizing the _acquisition function_ , a
function that assesses the quality of an action point and is much cheaper to
optimize than the original objective function. Next to other popular choices
such as Probability Improvement (PI), Expected Improvement (EI) and Thompson
Sampling (TS) (Vermorel and Mohri, 2005; Chowdhury and Gopalan, 2017), we
choose Upper Confidence Bound (UCB) (Srinivas et al., 2009), the update rule
of which is given as follows:

(7)
$x_{t}=\operatorname*{arg\,max}_{x\in\mathcal{X}}\;\mu_{t-1}(x,\omega_{t})+\sqrt{\zeta_{t}}\sigma_{t-1}(x,\omega_{t})$

An important rationale behind choosing UCB, as can be perceived from the
equation, is that it efficiently balances _exploration_ of undiscovered
resource configurations and _exploitation_ of configurations that have already
been observed to be well-performing. The hyperparameter $\zeta_{t}$ serves to
balance the tradeoff: choosing a small $\zeta_{t}$ indicates we value the
first mean term more, hence will more likely select an action close to one
which previously led to better performance; choosing a large $\zeta_{t}$, on
the other hand, focuses more on the variance term so that under-explored
actions with higher uncertainty are more likely to be selected. Moreover, in
the GP setting, UCB is superior in terms of both computational efficiency
(Wilson et al., 2020; Vakili et al., 2021) and convergence rate (Chowdhury and
Gopalan, 2017) compared to alternatives such as GP-TS.

Combining these design choices, we summarize our GP-UCB-based online resource
orchestration algorithm in Algorithm 1.

Algorithm 1 Contextual Bandits for Public Clouds

Input: Performance-cost balance weights $\alpha,\beta$;

Action Space $\mathcal{X}$;

1:$S_{0}\leftarrow\emptyset$; $\triangleright$ $S_{t}$ stores action-context
pairs up to time $t$

2:$\mathbf{y}_{0}\leftarrow\emptyset$; $\triangleright$ $\mathbf{y}_{t}$
stores noisy rewards up to time $t$

3:for $t=1,2,\cdots$ do

4: Observe current context $\omega_{t}$;

5: Select resource configuration $x_{t}$ according to (7);

6: Observe noisy reward $y_{t}=f(x_{t},\omega_{t})+\epsilon_{t}$;

7: $S_{t}\leftarrow S_{t-1}\cup(x_{t},\omega_{t})$;

8: $\mathbf{y}_{t}\leftarrow\mathbf{y}_{t-1}\cup y_{t}$;

9: Update $\mu_{t}$ and $\sigma_{t}$ by posterior update rule (5)-(6);

10:end for

Regret analysis. A desired property of a bandit algorithm is to have sub-
linear cumulative regret growth. Our algorithm achieves this with high
probability by setting appropriate hyperparameters, as shown in the following
theorem:

###### Theorem 4.1.

Let $\delta\in(0,1)$, $\forall T\geq 1$, the cumulative regret of Alg. 1 is
upper bounded by $O(\sqrt{T\gamma_{T}\zeta_{T}})$ with high probability.
Precisely,

(8) $Pr\\{R_{T}\leq\sqrt{C_{1}T\gamma_{T}\zeta_{T}}+2\\}\geq 1-\delta$

where $C_{1}=\frac{8}{\log(1+\sigma^{-2})}$,
$\zeta_{t}=2B^{2}+300\gamma_{t}\log^{3}(\frac{t}{\delta})$.

Here, $\gamma_{T}$ is the maximum information gain in the order of
$O(T^{l}\log T)$ where $l<1$. $B\geq||f||_{k}$ is the upper bound of the
Reproductive Kernel Hilbert Space (RKHS) norm of $f$, a common assumption in
bandit algorithms. Due to space constraint, please refer to (authors, 2023)
for proof of the theorems.

###  4.3. Private cloud: Resource-constrained Performance Optimization

For security or data privacy concerns, organizations often resort to a private
cloud solution instead of running their jobs on a public cloud. A private
cloud is a self-hosted computing cluster that the organization has full
control of. The organization is also able to fully unlock the power of
computing nodes by customizing their hardware and software architectures
tailored to its own needs which is often constrained on public clouds.
Compared to the pay-as-you-go model on public clouds, organizations pay the
resource cost upfront at the purchase of the hardware to build the private
cloud. The update cycle is generally up to several years when the hardware is
too old or the business scale has been significantly expanded. In this case,
any resource orchestration decision must respect the private cloud’s total
resource limit, which is a hard constraint. The optimization objective under
such scenarios is thus optimizing application performance subject to the hard
resource constraints (Sui et al., 2015, 2018; Amani et al., 2020). Formally,
the resource orchestration optimization problem in the private cloud can be
formulated as:

(9) $\displaystyle\max_{\mathbf{x_{t}}}\quad$ $\displaystyle
p(x_{t},\mathbf{\omega}_{t})$ (10) $\displaystyle s.t.\quad$ $\displaystyle
x_{t}\in\mathcal{X}_{t}^{S},\mathbf{\omega}_{t}\in\Omega,\quad\forall{t}$

where $\mathcal{X}_{t}^{S}$ is the _safe_ set from the action domain at time
step $t$ so that actions can only be selected from the safe set to comply with
resource constraints. Specifically, denote $P_{max}$ as the resource
constraint and let $P(x_{t},\omega_{t})$ be the total resource usage resulting
from action $x_{t}$ and context $\omega_{t}$ at time step $t$, we have

(11) $\mathcal{X}_{t}^{S}=\\{x_{t}\in\mathcal{X}:P(x_{t},\omega_{t})\leq
P_{\max}\\}$

Note that $P(x_{t},\omega_{t})$ and $P_{\max}$ contain multiple dimensions in
practice. Each of the dimensions is a resource type (e.g., CPU, RAM, and
network bandwidth) and has its own limit in a private cloud. For presentation
brevity, here, we abstract them as an overall constraint, without loss of
generality. Moreover, $P(x_{t},\omega_{t})$ is also an unknown function since
it depends on the contextual variables $\omega_{t}$ as well. This is
reasonable since resource contention is common in a shared cloud (a private
cloud can also be shared within the organization across several development
teams). As a result, the performance indicator function
$p(x_{t},\mathbf{\omega}_{t})$ and the resource usage function
$P(x_{t},\omega_{t})$ need to be modelled separately. At each time step $t$
throughout the optimization process, our algorithm needs to select an action
$x_{t}$ from the safe set ${X}_{t}^{S}$ so that the performance
$p(x_{t},\omega_{t})$ is optimized. Towards this end, we use two GPs to model
the performance function and the resource function, respectively. Reusing the
notation $z\in\mathcal{X}^{S}\times\Omega$ as a joint safe action-context
pair, at each time step $t$, noisy values of both functions are observed as
$y_{t}=p(z_{t})+\epsilon_{t}$ and $\phi_{t}=P(z_{t})+\epsilon_{t}$. We now
present our solution in Algorithm 2.

Algorithm 2 Contextual Safe Bandits for Private Clouds

Input: Action Space $\mathcal{X}$, Initial Safe Set $\mathcal{X_{\zeta}^{S}}$,
Exploration Duration $T^{\prime}$

1:Step 1: Exploration

2:for $t=1,\cdots,T^{\prime}$ do

3: Observe context $\omega_{t}$;

4: Randomly choose $x_{t}\in\mathcal{X_{\zeta}^{S}}$;

5: Observe noisy performance $y_{t}=r(x_{t},\omega_{t})+\epsilon_{t}$;

6: Observe noisy resource usage $\phi_{t}=P(x_{t},\omega_{t})+\epsilon_{t}$;

7:end for

8:Step 2: Exploration + Exploitation

9:for $t=T^{\prime},\cdots$ do

10: Update $\mu_{t-1}$, $\sigma_{t-1}$ by posterior update rule (5)-(6);

11: Observe context $\omega_{t}$;

12:
$l_{P}(x_{t},\omega_{t})\leftarrow\mu_{P,t-1}(x_{t},\omega_{t})-\sqrt{\beta_{t}}\sigma_{P,t-1}(x_{t},\omega_{t})$;

13:
$u_{p}(x_{t},\omega_{t})\leftarrow\mu_{p,t-1}(x_{t},\omega_{t})+\sqrt{\beta_{t}}\sigma_{p,t-1}(x_{t},\omega_{t})$;

14:
$\mathcal{X}_{t}^{S}\leftarrow\\{x_{t}\in\mathcal{X}:l_{P}(x_{t},\omega_{t})\leq
P_{max}\\}$;

15:$\triangleright$ The new, expanded safe set

16:
$x_{t}\leftarrow\operatorname*{arg\,max}_{x\in\mathcal{X}_{t}^{S}}u_{p}(\omega_{t},x)$;

17: Observe noisy performance, resource usage and update corresponding
vectors;

18:end for

The core idea of this algorithm is a two-phase process. In the first phase,
starting from a guaranteed safe set, the algorithm is dedicated to exploration
by randomly querying actions to gather more information to characterize the
safe set. The second phase acts similarly to Alg. 1 which balances exploration
and exploitation by following the GP-UCB procedure to update the posterior GP
model. However, on top of the standard GP-UCB algorithm, it leverages
information from previous exploration to iteratively expand the safe set based
on the lower confidence interval of the resource usage function $P$ (Line 14).
We show through the following theorem that Alg. 2 also achieves sub-linear
cumulative regret growth:

###### Theorem 4.2.

Let $\delta\in(0,1)$, for sufficiently large $T\geq 1$, the cumulative regret
of Alg. 2 is upper bounded by $O(\sqrt{T\gamma_{T}\zeta_{T}})$ with high
probability. Precisely,

(12) $Pr\\{R_{T}\leq BT^{\prime}+\sqrt{C_{1}T\gamma_{T}\zeta_{T}}\\}\geq
1-\delta$

where the parameters $C_{1},\gamma_{T}$ and $\zeta_{T}$ take the same value as
the previous theorem.

###  4.4. Drone Implementation

We implemented a prototype of Drone as an integrable resource orchestrator on
top of Kubernetes. The overall system architecture of Drone is depicted in
Figure 6, which contains the following components:

Monitoring Module. The monitoring module is a key component of the Drone
framework. It is responsible for periodically collecting both performance
metrics and contextual information from the cloud environment. In Drone, we
choose Prometheus (Prometheus., 2023) for this purpose. Prometheus is a
market-leading monitoring system shipping with a time series database and
powerful querying capabilities through its specialized query language PromQL.
It is able to collect system-level real-time metrics such as CPU, RAM and
network bandwidth usage through node-exporter (node exporter., 2023) along
with other potential contextual variables. By exposing a metrics exporter,
applications are also enabling Prometheus to collect their performance metrics
like throughput and response time. The collected metrics are stored in the
time series database which can be efficiently queried upon request. The
collected real-time contextual information, along with stored history
performance data and action-context pairs, provides input to guide the
optimization process of Drone’s algorithms.

Figure 6. Drone Architecture.

Application Identifier. The application identifier helps identify the type of
the submitted application to make tailored resource orchestration decisions
for batch processing jobs and microservices, respectively. While users can
explicitly specify the application type, as discussed in 4.5, the application
identifier is also able to automatically detect the application type if it is
evident in the deployment specification. For example, a Spark application has
an exclusive kind: SparkApplication specification field which can be easily
utilized by the application identifier.

Objective and Resource Enforcer. Depending on whether the environment is a
public cloud or a private cloud, this module specifies the optimization
objective for the optimization engine. Users can tune model parameters here
based on their needs, such as performance-cost preference coefficients in the
public cloud setting and resource limit in the private cloud setting. In a
private cloud, if the user does not specify the desired resource limit, the
enforcer will set the limit according to the cluster resource usage.

Optimization Engine. As the core part of the framework, the optimization
engine is responsible for carrying out the optimization process. Based on the
cloud setting set by the application identifier and the enforcer, the
optimization engine continuously receives performance and contextual metrics
from the monitoring module and suggests a resource orchestration action in
each decision period. The action is a combination of container rightsizing and
scheduling. Actions are executed by directly interacting with the Kubernetes
API server to minimize additional overhead.

###  4.5. Cloud-specific Optimizations

On top of the algorithmic efforts, we also make practical optimizations
tailored to the cloud resource orchestration problem context to further
improve Drone’s usability and efficiency in practice.

Encoding of actions and contexts. Unlike CPU cores and RAM allocation/usage
which take numerical values and thus naturally fit in our contextual bandit-
based framework, some action and contextual variables do not readily manifest
a numerical representation such as container scheduling decisions from the
action space and possible traffic bottleneck from the context space. We
address this issue by scalarizing these variables with numerical encoding. For
example, we encode the scheduling decisions as a sub-vector
$\underline{x}=[x_{1},x_{2},\cdots,x_{m}]$ of the entire decision vector $x$,
where $m$ is the number of computing nodes or VMs on which a container can be
scheduled. The elements $x_{i}\in\mathbb{N}$ represent the number of
containers that should be scheduled to node $i$. Note that having an
individual entry for each single node may lead to dimension explosion when the
cloud scale is large. However, in practice, we can further group nodes by
physical distance into zones within which nodes perceive almost no network
latency when communicating with each other. The scheduling decisions will thus
be executed at the zone level, significantly reducing dimensionality to the
number of zones. This is particularly useful when the cloud is geographically
distributed where high latency can be incurred by inter-zone communication.
For traffic between nodes, we can use an integer $a\in[0,2^{m}-1]$ to encode
the possible traffic contention, which can be proven trivially by the binomial
theorem.

Characterization of applications. We consider two representative application
profiles for Drone, namely batch processing jobs and long-running web services
in the form of microservices. Also referred to as Best Effort (BE) and Latency
Critical (LC) applications in the recent literature (Lu et al., 2023; Zhang et
al., 2022; Cheng et al., 2018), these two types cover the majority of
applications running on a massive-scale production cloud (Lu et al., 2023).
When using Drone as the resource orchestrator, users have the option to
specify their application type as either batch jobs or microservices so as for
Drone to make specialized decisions. Essentially, Drone can run in two modes.
For batch jobs, Drone follows previous works (Alipourfard et al., 2017; Liu et
al., 2019) to run the algorithm in a quasi-online manner in order to further
leverage the additional optimization opportunities brought forth by recurring
workload patterns, but achieves better performance by incorporating other
cloud uncertainties and resource constraint compliance under private cloud
setting. For microservices, Drone runs as a fully online algorithm so that all
resource orchestration actions are updated on the fly as time progresses.
These options enable Drone to make wiser resource orchestration decisions to
best fit the application characteristics.

Reducing computational complexity. A well-known limitation of the GP-UCB
approach is the cubic $O(n^{3})$ computational complexity associated with the
matrix inverse operation, where $n$ is the number of data points. At each time
step $t$, all previous data points $(S_{t},\mathbf{y}_{t})$ are used with the
same weight to update the surrogate model, and this gradually becomes
computationally intractable as time progresses. Based on the insight that data
points from the long-ago past may not be as representative as recent ones in
terms of modeling capability, we adopt a sliding-window approach to address
this issue. Instead of using them all, we only consider the most recent $N$
data points for updating the model. This significantly reduces the running
time complexity of Drone over time. Across our experiments, we set $N=30$
which empirically entails a good balance between algorithm performance and
running time.

Initial point selection. Just like gradient-based optimization approaches,
bandit algorithms usually need a set of initial data samples to bootstrap the
function estimation process (e.g., PI- and EI-based approaches). The algorithm
performance can depend on the quality of these initial selections to a great
degree and designing a selection strategy is non-trivial and domain-specific.
Although UCB-based algorithms suffer less from this problem by valuing the
variance term to motivate exploration, as also pointed out in (Liu et al.,
2019), it is still a practical concern under the private cloud setting since a
poorly chosen initial configuration may violate the resource constraints and
hence invalidate the algorithm. An intuitive approach is to start from minimum
resource configurations which almost surely lie in the safe set and expand
possible action choices from there. However, we observe from experiments in
Sec. 3 that running a job with minimum resources can be problematic. For
example, running the same PageRank job on Spark with a total RAM of less than
12GB would leave the job in a halt stage so that no performance metrics can be
collected and hence no progress can be made by our algorithm. Therefore, we
follow a heuristic approach to allocate half of the currently available
resources by querying the monitoring module for the current total resource
utilization as a starting point. In our experiments, this proves to be a good
selection with a low error rate across workloads. As a safety measure, we also
implement a failure recovery mechanism that if a job errors out with no
metrics produced in a pre-defined timeout period, it will be restarted with a
higher resource configuration at the midpoint of the previous trial and the
maximum resources available.

##  5\. Experimental Evaluation

###  5.1. Experimental Setup

Testbed setup. Our testbed cluster is hosted on Compute Canada (Baldwin,
2012), a shared national cloud platform. The cluster consists of 16 virtual
machines with one control node and 15 worker nodes, a scale comparable to
related work. The control node is equipped with 16 vCPU cores and 180GB of
RAM, while the worker nodes have 8 vCPU cores and 30GB of RAM. Each node runs
Ubuntu 20.04.5 LTS with Linux kernel v5.4. Nodes are interconnected by 10Gb
Ethernet in the same data center. Kubernetes v1.25 is deployed as the
container orchestration platform.

Applications. Representative applications for both batch processing jobs and
microservices are deployed to evaluate Drone. For batch jobs, we benchmark
three Spark applications that stress different computational resources,
including (1) Spark-Pi, a pi-computation job with configurable number of
iterations to control precision as a representative compute-intensive job, (2)
PageRank as a jointly memory- and network-intensive job and (3) Logistic
Regression to serve as a typical ML training task. For microservices, we use
the Social Network application containing 36 microservices from DeathStarBench
(Gan et al., 2019a), a prevalent microservice banchmarking choice in the
research community. Various calling patterns are present between the
microservices to mimic production microservice applications. All microservices
are running as Docker containers managed by Kubernetes in the form of pods.

Workloads. We use the same workloads as discussed in Sec. 3 for batch jobs
with configurable intensity. For microservices, we use a 6-hour sample from
the Twitter Streaming trace (twi, 2022) which exhibits diurnal patterns, a
good representation of real-life web service requests. The workload is
generated by wrk2, a multi-threaded workload generator in which several
parameters can be fine-tuned to control workload characteristics, such as
request rates, distribution and elapsed time. We tailor these parameters to
properly fit the workload to the scale of our cluster. Different request types
are also customized to randomly stress multiple microservices. Workloads are
all sent from a separate node than the ones that host the microservices to
simulate external users.

Comparison baselines. We compare Drone with Cherrypick (Alipourfard et al.,
2017) and Accordia (Liu et al., 2019) in the case of batch job processing. For
the sake of fair comparison, batch jobs are run repeatedly, a case for which
Cherrypick and Accordia are specifically designed. For microservices, our
baselines include SHOWAR (Baarzi and Kesidis, 2021), a hybrid autoscaling
approach specialized for microservices combining both vertical and control
theory-based horizontal autoscaling, and Google Autopilot (Rzadca et al.,
2020). Autopilot is Google’s hybrid autoscaler in production use. Its basic
model works by a moving-window approach to aggregate resource utilization
statistics in recent time windows to produce the resource utilization targets
and linearly scale resources with respect to the targets. In both cases, we
also run experiments with the default rule-based Kubernetes Horizontal Pod
Autoscaler (HPA) and its native scheduler to serve as a standard baseline.

(a) Batch job (LR) elapsed time under the public cloud.

(b) Resource cost savings across batch jobs under the public cloud.

(c) Overall memory utilization for batch jobs under the private cloud.

Figure 7. Comparison between Drone and alternatives for batch processing jobs.

Performance metrics and input spaces. The performance metrics, utilized as
objective functions in our formulations presented in Section 4, are measured
according to their distinct specifications. The performance indicator
$p(x_{t},\omega_{t})$ represents job elapsed time (i.e., the wall-clock time
between its submission and completion) for batch jobs, and P90 end-to-end
latency (i.e., the 90th percentile of latency for requests sent) for
microservices. To more appropriately model our formulations, the resource cost
$c(x_{t},\omega_{t})$ is estimated using the resource-based pricing scheme
adopted by Google cloud (cloud compute engine resource-based pricing., 2021)
which charges users by actual resource usage as opposed to AWS which charges
users according to VM types. These performance metrics along with low-level
resource utilization metrics are collected by the monitoring module every 60
seconds to align with the Prometheus scrape-interval, which is also our
decision period when running fully online. In our evaluations, we also group
our nodes into four zones with artificial latency between each other using
Linux traffic control (tc). Therefore, our action space is a 7-dimension space
including the number of pods to schedule to each zone along with CPU, RAM and
network bandwidth allocation for each pod. The context space on the other hand
contains workload intensity, current CPU, RAM and network bandwidth
utilization in the cloud, potential traffic contention and spot prices. To
incorporate the influence of spot prices, we randomly fill 10-30% of the
resource cost with spot prices. The spot prices are sampled from the E2
instance family spot prices on Google Cloud. In the private cloud setting, the
spot price dimension is omitted.

Spark-Pi LR PageRank Framework Time(s) # Errors Time(s) # Errors Time(s) #
Errors k8s 53±2 0 328±17 1 1436±88 4 Accordia 46±1 0 303±26 17 1172±95 98
Cherrypick 43±1 0 298±24 13 1226±102 107 Drone 41±1 0 226±9 5 785±42 9

Table 3. Drone significantly reduces OOM errors by conforming with resource
constraints.

###  5.2. Drone for Batch Processing Jobs

We start off by investigating Drone’s effectiveness in handling recurring
batch processing workloads. In the public cloud setting, we set
$\alpha=\beta=0.5$ to model a general user who does not have a specific
preference and normalize the performance and cost values to the same magnitude
for fair comparison with alternatives. Our results are summarized in Figure.
7. First, Figure. 7(a) depicts the performance measurements for the same LR
job running with different schemes in the public cloud setting. Starting from
the same starting point, it can be seen that all three bandit algorithm-based
approaches are able to improve application performance by learning the
performance-input relationship function over time. On the other hand, as a
completely reactive rule-based autoscaler, the default Kubernetes solution
cannot benefit from history information, and hence only manages to maintain a
low performance, which is slightly perturbed over time by environment
uncertainties and measurement errors. Drone significantly outperforms
Cherrypick and Accordia by adaptively learning from the contextual variables
while Cherrypick and Accordia are oblivious to such environment changes and
can only leverage information from their resource decisions, i.e., the action
space. The benefit of considering contextual information can further be
observed from the post-convergence behaviour when $T>10$. Both Cherrypick and
Accordia sporadically experience performance oscillations while Drone is able
to stabilize after convergence. This is because Cherrypick and Accordia regard
any performance feedback as the exclusive result of the actions taken.
Therefore, whenever a performance discrepancy is observed they will adjust
their resource allocations even though it is primarily owing to changes in
contextual cloud uncertainties. It is also worth noting that Drone converges
slightly slower at the 10th iteration compared to the other two schemes which
converge around the 7th iteration because the search space is larger in Drone
due to additional dimensions in the action spaces (e.g., the scheduling
vector) and the new contextual dimensions. This is a common performance-
dimension tradeoff which we will briefly discuss in Sec. 6.

(a) The Twitter streaming workload in a 6-hour window.

(b) CDF of overall RAM allocation for SocialNet under the public cloud.

(c) CDF of end-to-end latency for SocialNet under the public cloud.

Figure 8. Comparison between Drone and alternatives for microservices.

Figure. 7(b) depicts the normalized resource cost saving compared to the
Kubernetes native solution across all three representative batch workloads.
While all three frameworks show cost-saving benefits thanks to their cost-
aware problem formulation, Drone is the most cost-efficient one with over 20%
cost savings across workloads, since it can more accurately search for the
(near-)optimal resource configuration based on the information from both
performance feedback and environment contexts, without need to over-allocate
resources to maintain reasonable performance. Moreover, Drone makes its own
scheduling decision by incorporating the scheduling sub-vector into its action
space. Thus, even if given the same total amount of resources, Drone also
learns the best strategy to assign the execution pods to computing nodes,
which Cherrypick and Accordia cannot achieve. This effect is most evident when
benchmarking PageRank, a network-intensive workload, where Drone achieves an
average of 53% resource cost saving compared to the Kubernetes native
solution, a number significantly higher than 20% from Accordia and 17% from
Cherrypick.

Similar benefits are also manifested in the resource-limited private cloud
setting. We focus on Drone’s impact on memory limit compliance since memory is
a non-negotiable resource type. Unlike CPU and network bandwidth where
inadequate allocation would cause throttling (for CPU) or congestion (for
network) but applications are still available, an application that requires
more memory than allocated will incur an out-of-memory (OOM) error and the
hosting pod will simply be killed and rescheduled if possible. OOM errors can
significantly jeopardize application availability and degrade application
performance. In our preliminary experiments in Sec. 3, a Spark job with
insufficient memory allocation can experience a 20x longer elapsed time and
even get halted in an intermediate stage and fail to make progress. We set the
memory limit as 65% of the total memory capacity available in the cluster and
run all three representative batch workloads and record the memory utilization
metric as shown in Figure. 7(c). We can observe that only Drone manages to
abide by the memory constraint in the long run, showing an approximately 16%
lower memory profile than baselines, despite the first few exploration rounds
where Drone actively explores around to identify the feasible safe action
space. To see the benefit of resource limit compliance in action, we run
memory-stressing tasks in parallel using stress-ng to simulate significant
resource contention which occupies around 30% of total memory. Table 3
summarizes the performance and number of Spark executor errors in different
settings. We can observe that the Kubernetes native solution suffers from the
least number of OOM errors by using memory utilization as one of its scaling
rules. Therefore, it always respects the resource constraints and even
suspends invoking executor pods when it detects memory is under stress, which
in part contributes to its low performance. Memory constraint-oblivious
solutions Cherrypick and Accordia on the other hand experience a large number
of executor errors, especially for memory-intensive jobs such as LR and
PageRank. In this case, Drone is able to fully utilize the algorithmic
effectiveness of contextual bandits to optimize performance while complying
with resource constraints, achieving up to 36% performance improvement and 10x
less OOM errors compared to Cherrypick and Accordia.

###  5.3. Drone for Microservices

We also evaluate the efficacy of Drone to orchestrate resources for
microservice applications by performing end-to-end experiments. Driving the
SocialNet microservice benchmark with a realistic workload trace as shown in
Figure 8(a), we collected aggregated performance metrics over the entire
application running span. Figure 8(b) shows the cumulative distribution of RAM
allocation for Drone and the other three baselines. As hybrid autoscalers,
both SHOWAR and Autopilot are able to reduce memory footprint compared to
Kubernetes HPA by combining vertical and horizontal autoscaling to mitigate
over-allocation. However, Drone outperforms the alternatives by more
accurately modelling the performance-action relationship by incorporating a
much broader array of factors, instead of only heavily relying on past
resource usage information as SHOWAR and Autopilot do. Specifically, Drone is
able to serve around 60% of user requests within 50GB of overall RAM
allocation, which is 55% less than SHOWAR and 60% less than Autopilot,
manifesting an outstanding resource-saving capability.

Figure 8(c) depicts the end-to-end latency distribution across frameworks.
Autopilot exhibits a similar performance to Kubernetes HPA since they share a
similar reactive scaling strategy based on recent resource statistics.
Specifically designed for microservices, SHOWAR performs better by identifying
microservice correlations to create locality-oriented affinity rules, which is
more likely to schedule closely related microservices to the same node and
hence reduces latency. Drone, on the other hand, steps further by encoding the
more efficient scheduling opportunities into its decision vector, so it does
effectively both rightsizing (i.e., autoscaling by prioritizing vertical
scaling) and scheduling. As an integrated resource orchestration solution,
Drone lowers the P90 latency by 37% compared to SHOWAR and by 45% compared to
Autopilot.

k8s Autopilot SHOWAR Drone # of dropped packets $4.8\times 10^{4}$ $3.4\times
10^{4}$ $1.4\times 10^{4}$ 7809

Table 4. Number of dropped requests.

Having run the experiment in the private cloud setting, we also observe a
similar effect as in the previous subsection. Table 4 records the total number
of dropped user requests over the running span. Unlike in the batch processing
case where the Kubernetes solution manages to maintain a low error rate by not
invoking pods when memory is low, in this user-facing microservice case, it
experiences the largest number of packet drops due to poor resource allocation
decisions. Again, Drone incurs the least number of packet drops thanks to its
resource limit-aware algorithm which progressively learns about the safe set
for resource orchestration decisions.

##  6\. Discussion

Application-level configuration tuning. An application’s performance can
greatly depend on its own configurable parameters as well. For example, Xin et
al. (Xin et al., 2022) identifies 38 performance-deciding parameters for
SparkQL. While Drone is not readily applicable to application-level parameter
tuning out of the box, the idea of the underlying contextual bandits as an
algorithmic foundation can be naturally transferable, which has also been
recently explored in the database research community, as mentioned in Sec.
2.2. In fact, Drone operates at a lower level of hardware resource
orchestration and can be used in parallel with other efficient application-
level configuration tuning techniques to jointly optimize an application’s
performance.

Tradeoff between precision and cost. In theory, the function modelling
capability of bandit algorithms can always benefit from more information. It
is also true in our resource orchestration context. Incorporating more
dimensions for tunable parameters from the action space such as disk I/O and
last level cache (LLC) bandwidth, or more contextual information such as the
graph structure of the running microservices would help Drone more accurately
characterize the complex coupling of performance, action and environment.
However, it is well-known that bandit algorithms (especially its continuous
variant Bayesian Optimization) tend to perform poorly in high dimensions
(Moriconi et al., 2020). Therefore, in practice, we need to selectively
incorporate the “more important” dimensions with domain knowledge and employ
several optimizations (see Sec. 4.5) to make the algorithms practically
efficient. Actually, as different applications and workloads have divergent
resource request profiles, it would be interesting to investigate how to
dynamically pick the most critical dimensions based on application and
workload properties. We leave that as a future work of Drone.

Overhead of Drone. Drone is designed to embrace the latest cloud paradigms and
technologies, working seamlessly with the Kubernetes ecosystem. It utilizes
the Prometheus-based Kubernetes monitoring stack for metrics collection and
modifies resource configurations by directly communicating with the Kubernetes
API server and updating the cgroup configuration values for the pods of
concern if possible. Thanks to the optimizations we employ, the computation
time for each iteration in the online mode is on the order of seconds, well
within the metrics updating interval. There is also no additional cost of
potential container migration during scheduling since Drone follows the
standard Kubernetes-native rolling-update procedure. Therefore, minimal
overhead is incurred for using Drone.

Limitations. One major limitation of Drone is its insufficient capability to
deal with “flash crowds”, workloads that burst to a significantly higher level
in a very short period of time (e.g., seconds). This situation inherently
breaks the Gaussian Process prior assumption of the function and intrinsic
limitations of iterative algorithms restrict Drone from reacting fast to such
sudden changes. Fortunately, such cases are rare in reality and cloud
providers often prepare backup resources for over-allocation in addition to
their routine resource allocation frameworks. Moreover, Drone is yet to
achieve its full potential to work with microservices since it is oblivious to
the microservice dependency graph structure, which has been shown to be
instrumental in microservice-oriented resource management (Qiu et al., 2020;
Luo et al., 2021; Baarzi and Kesidis, 2021; Luo et al., 2022; Park et al.,
2021). Efficiently integrating dependency information into Drone without
incurring significant overhead would be another promising direction to
explore.

##  7\. Conclusions

In this paper, we present Drone, a resource orchestration framework
specifically designed for the containerized cloud. Based on recent advances in
contextual bandit algorithms, Drone encapsulates various cloud uncertainties
as contextual parameters to aid the search process for optimal resource
orchestration decisions. The uncertainty-aware approach enables Drone to
progressively balance the performance and resource cost tradeoff in a shared
public cloud, and optimize performance while adhering to resource constraints
in a resource-limited private cloud. Our empirical analysis shows that Drone
achieves up to 45% performance improvement and 20% resource cost savings
compared to state-of-the-art alternatives.

## References

  * (1)
  * twi (2022) 2022\.  Archive Team: The Twitter Stream Grab.  https://archive.org/details/twitterstream/.
  * aws (2023a) 2023a.  Amazon EC2 Instance Types – Amazon Web Services (AWS).  https://aws.amazon.com/ec2/instance-types/.
  * aws (2023b) 2023b.  Amazon EC2 Spot Instances Pricing – Amazon Web Services (AWS).  https://aws.amazon.com/ec2/spot/pricing/.
  * azu (2023) 2023\.  Azure Spot Virtual Machines.  https://azure.microsoft.com/en-us/products/virtual-machines/spot/.
  * aws (2023c) 2023c.  Burstable performance instances – Amazon Web Services (AWS).  https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/burstable-performance-instances.html.
  * doc (2023) 2023\.  Limit a container’s resources — Docker Documentation.  https://docs.docker.com/config/containers/resource_constraints/.
  * k8s (2023) 2023\.  Resource Management for Pods and Containers — Kubernetes Documentation.  https://kubernetes.io/docs/concepts/configuration/manage-resources-containers/.
  * gcp (2023) 2023\.  Spot VMs - Google Cloud Platform.  https://cloud.google.com/spot-vms.
  * Al-Sharif et al. (2017) Ziad A Al-Sharif, Yaser Jararweh, Ahmad Al-Dahoud, and Luay M Alawneh. 2017.  ACCRS: autonomic based cloud computing resource scaling.  _Cluster Computing_ 20, 3 (2017), 2479–2488.
  * Ali-Eldin et al. (2012) Ahmed Ali-Eldin, Johan Tordsson, and Erik Elmroth. 2012\.  An adaptive hybrid elasticity controller for cloud infrastructures. In _2012 IEEE Network Operations and Management Symposium_. IEEE, 204–212.
  * Alipourfard et al. (2017) Omid Alipourfard, Hongqiang Harry Liu, Jianshu Chen, Shivaram Venkataraman, Minlan Yu, and Ming Zhang. 2017.  CherryPick: Adaptively Unearthing the Best Cloud Configurations for Big Data Analytics.. In _NSDI_ , Vol. 2. 4–2.
  * Amani et al. (2020) Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. 2020\.  Regret bound for safe gaussian process bandit optimization. In _Learning for Dynamics and Control_. PMLR, 158–159.
  * authors (2023) Anony. authors. 2023\.  Due to double-blind review policy, proofs are provided at the request of the program chair or included in a technical report upon acceptance.
  * Autoscalers. (2023) Kubernetes Autoscalers. 2023\.  https://github.com/kubernetes/autoscaler.
  * aws autoscaling service. (2021) Amazon aws autoscaling service. 2021\.  https://aws.amazon.com/autoscaling/.
  * azure autoscaler. (2021) Microsoft azure autoscaler. 2021\.  https://docs.microsoft.com/en-us/azure/cloud-services/cloud-services-how-to-scale-portal/.
  * Baarzi and Kesidis (2021) Ataollah Fatahi Baarzi and George Kesidis. 2021.  Showar: Right-sizing and efficient scheduling of microservices. In _Proceedings of the ACM Symposium on Cloud Computing_. 427–441.
  * Baldwin (2012) Susan Baldwin. 2012\.  Compute Canada: advancing computational research. In _Journal of Physics: Conference Series_ , Vol. 341. IOP Publishing, 012001.
  * Benchmark (2022) CloudSort Benchmark. 2022\.  http://sortbenchmark.org/.
  * Bodík et al. (2009) Peter Bodík, Rean Griffith, Charles Sutton, Armando Fox, Michael Jordan, and David Patterson. 2009\.  Statistical machine learning makes automatic control practical for internet datacenters. In _Proceedings of the 2009 conference on Hot topics in cloud computing_. USENIX Association, 12.
  * Borkowski et al. (2016) Michael Borkowski, Stefan Schulte, and Christoph Hochreiner. 2016\.  Predicting cloud resource utilization. In _Proceedings of the 9th International Conference on Utility and Cloud Computing_. 37–42.
  * Cereda et al. (2021) Stefano Cereda, Stefano Valladares, Paolo Cremonesi, and Stefano Doni. 2021.  Cgptuner: a contextual gaussian process bandit approach for the automatic tuning of it configurations under varying workload conditions.  _Proceedings of the VLDB Endowment_ 14, 8 (2021), 1401–1413.
  * Chen et al. (2017) Tianyi Chen, Qing Ling, and Georgios B Giannakis. 2017\.  An online convex optimization approach to proactive network resource allocation.  _IEEE Transactions on Signal Processing_ 65, 24 (2017), 6350–6364.
  * Cheng et al. (2018) Yue Cheng, Ali Anwar, and Xuejing Duan. 2018.  Analyzing alibaba’s co-located datacenter workloads. In _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 292–297.
  * Chouayakh and Destounis (2022) Ayman Chouayakh and Apostolos Destounis. 2022.  Towards no regret with no service outages in online resource allocation for edge computing. In _ICC 2022-IEEE International Conference on Communications_. IEEE, 4378–4383.
  * Chowdhury and Gopalan (2017) Sayak Ray Chowdhury and Aditya Gopalan. 2017.  On kernelized multi-armed bandits. In _International Conference on Machine Learning_. PMLR, 844–853.
  * cloud compute engine autoscaler. (2021) Google cloud compute engine autoscaler. 2021\.  https://cloud.google.com/compute/docs/autoscaler/.
  * cloud compute engine resource-based pricing. (2021) Google cloud compute engine resource-based pricing. 2021.  https://cloud.google.com/compute/resource-based-pricing.
  * Dean and Barroso (2013) Jeffrey Dean and Luiz André Barroso. 2013.  The tail at scale.  _Commun. ACM_ 56, 2 (2013), 74–80.
  * Eismann et al. (2020) Simon Eismann, Cor-Paul Bezemer, Weiyi Shang, Dušan Okanović, and André van Hoorn. 2020\.  Microservices: A performance tester’s dream or nightmare?. In _Proceedings of the ACM/SPEC International Conference on Performance Engineering_. 138–149.
  * Fox et al. (2009) Armando Fox, Rean Griffith, Anthony Joseph, Randy Katz, Andrew Konwinski, Gunho Lee, David Patterson, Ariel Rabkin, Ion Stoica, et al. 2009\.  Above the clouds: A berkeley view of cloud computing.  _Dept. Electrical Eng. and Comput. Sciences, University of California, Berkeley, Rep. UCB/EECS_ 28, 13 (2009), 2009.
  * Gan et al. (2019a) Yu Gan, Yanqi Zhang, Dailun Cheng, Ankitha Shetty, Priyal Rathi, Nayan Katarki, Ariana Bruno, Justin Hu, Brian Ritchken, Brendon Jackson, et al. 2019a.  An open-source benchmark suite for microservices and their hardware-software implications for cloud & edge systems. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_. 3–18.
  * Gan et al. (2019b) Yu Gan, Yanqi Zhang, Kelvin Hu, Dailun Cheng, Yuan He, Meghna Pancholi, and Christina Delimitrou. 2019b.  Seer: Leveraging big data to navigate the complexity of performance debugging in cloud microservices. In _Proceedings of the twenty-fourth international conference on architectural support for programming languages and operating systems_. 19–33.
  * Ghobaei-Arani et al. (2018) Mostafa Ghobaei-Arani, Sam Jabbehdari, and Mohammad Ali Pourmina. 2018\.  An autonomic resource provisioning approach for service-based cloud applications: A hybrid approach.  _Future Generation Computer Systems_ 78 (2018), 191–210.
  * Gias et al. (2019) Alim Ul Gias, Giuliano Casale, and Murray Woodside. 2019\.  ATOM: Model-driven autoscaling for microservices. In _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 1994–2004.
  * Grimaldi et al. (2015) Domenico Grimaldi, Valerio Persico, Antonio Pescapé, Alessandro Salvi, and Stefania Santini. 2015\.  A feedback-control approach for resource management in public clouds. In _2015 IEEE Global Communications Conference (GLOBECOM)_. IEEE, 1–7.
  * Hazelwood et al. (2018) Kim Hazelwood, Sarah Bird, David Brooks, Soumith Chintala, Utku Diril, Dmytro Dzhulgakov, Mohamed Fawzy, Bill Jia, Yangqing Jia, Aditya Kalro, et al. 2018\.  Applied machine learning at facebook: A datacenter infrastructure perspective. In _2018 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 620–629.
  * how big is Amazon’s AWS business? (hint: it’s absolutely massive) Just how big is Amazon’s AWS business? (hint: it’s absolutely massive). 2014.  https://web.archive.org/web/20191223045710/https://www.geek.com/chips/just-how-big-is-amazons-aws-business-hint-its-absolutely-massive-1610221/.
  * Hsu et al. (2018) Chin-Jung Hsu, Vivek Nair, Vincent W Freeh, and Tim Menzies. 2018.  Arrow: Low-level augmented bayesian optimization for finding the best cloud vm. In _2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 660–670.
  * Inc. (2021) Weaveworks Inc. 2021\.  Sock Shop.  https://github.com/microservices-demo/microservices-demo.
  * Jiang et al. (2013) Jing Jiang, Jie Lu, Guangquan Zhang, and Guodong Long. 2013\.  Optimal cloud resource auto-scaling for web applications. In _2013 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing_. IEEE, 58–65.
  * Jonas et al. (2019) Eric Jonas, Johann Schleier-Smith, Vikram Sreekanti, Chia-Che Tsai, Anurag Khandelwal, Qifan Pu, Vaishaal Shankar, Joao Carreira, Karl Krauth, Neeraja Yadwadkar, et al. 2019\.  Cloud programming simplified: A berkeley view on serverless computing.  _arXiv preprint arXiv:1902.03383_ (2019).
  * Kabir et al. (2021) H. M. Dipu Kabir, Abbas Khosravi, Subrota K. Mondal, Mustaneer Rahman, Saeid Nahavandi, and Rajkumar Buyya. 2021.  Uncertainty-Aware Decisions in Cloud Computing: Foundations and Future Directions.  _ACM Comput. Surv._ 54, 4, Article 74 (may 2021), 30 pages.  https://doi.org/10.1145/3447583
  * Kannan et al. (2019) Ram Srivatsa Kannan, Lavanya Subramanian, Ashwin Raju, Jeongseob Ahn, Jason Mars, and Lingjia Tang. 2019.  Grandslam: Guaranteeing slas for jobs in microservices execution frameworks. In _Proceedings of the Fourteenth EuroSys Conference 2019_. 1–16.
  * Keller and Karl (2014) Matthias Keller and Holger Karl. 2014.  Response time-optimized distributed cloud resource allocation. In _Proceedings of the 2014 ACM SIGCOMM workshop on Distributed cloud computing_. 47–52.
  * Krause and Ong (2011) Andreas Krause and Cheng Ong. 2011.  Contextual gaussian process bandit optimization.  _Advances in neural information processing systems_ 24 (2011).
  * Li et al. (2021) Qian Li, Bin Li, Pietro Mercati, Ramesh Illikkal, Charlie Tai, Michael Kishinevsky, and Christos Kozyrakis. 2021.  RAMBO: Resource allocation for microservices using Bayesian optimization.  _IEEE Computer Architecture Letters_ 20, 1 (2021), 46–49.
  * Liakopoulos et al. (2019) Nikolaos Liakopoulos, Georgios Paschos, and Thrasyvoulos Spyropoulos. 2019.  No regret in cloud resources reservation with violation guarantees. In _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 1747–1755.
  * Liu et al. (2019) Yang Liu, Huanle Xu, and Wing Cheong Lau. 2019.  Accordia: Adaptive cloud configuration optimization for recurring data-intensive applications. In _Proceedings of the ACM Symposium on Cloud Computing_. 479–479.
  * Lu et al. (2023) Chengzhi Lu, Huanle Xu, Kejiang Ye, Guoyao Xu, Liping Zhang, Guodong Yang, and Chengzhong Xu. 2023.  Understanding and Optimizing Workloads for Unified Resource Management in Large Cloud Platforms. In _Proceedings of the Eighteenth European Conference on Computer Systems_. 416–432.
  * Luo et al. (2021) Shutian Luo, Huanle Xu, Chengzhi Lu, Kejiang Ye, Guoyao Xu, Liping Zhang, Yu Ding, Jian He, and Chengzhong Xu. 2021.  Characterizing Microservice Dependency and Performance: Alibaba Trace Analysis. In _Proceedings of the ACM Symposium on Cloud Computing_. 412–426.
  * Luo et al. (2022) Shutian Luo, Huanle Xu, Kejiang Ye, Guoyao Xu, Liping Zhang, Guodong Yang, and Chengzhong Xu. 2022.  The power of prediction: microservice auto scaling via workload learning. In _Proceedings of the 13th Symposium on Cloud Computing_. 355–369.
  * Mao et al. (2019a) Hongzi Mao, Parimarjan Negi, Akshay Narayan, Hanrui Wang, Jiacheng Yang, Haonan Wang, Ryan Marcus, Mehrdad Khani Shirkoohi, Songtao He, Vikram Nathan, et al. 2019a.  Park: An open platform for learning-augmented computer systems.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Mao et al. (2019b) Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. 2019b.  Learning scheduling algorithms for data processing clusters.  In _Proceedings of the ACM special interest group on data communication_. 270–288.
  * Marcus and Papaemmanouil (2017) Ryan Marcus and Olga Papaemmanouil. 2017.  Releasing Cloud Databases for the Chains of Performance Prediction Models.. In _CIDR_.
  * min) data (2022) Stock Market Data Nifty 100 Stocks (1 min) data. 2022.  https://www.kaggle.com/datasets/debashis74017/stock-market-data-nifty-50-stocks-1-min-data.
  * Moriconi et al. (2020) Riccardo Moriconi, Marc Peter Deisenroth, and KS Sesh Kumar. 2020.  High-dimensional Bayesian optimization using low-dimensional feature spaces.  _Machine Learning_ 109 (2020), 1925–1943.
  * node exporter. (2023) Prometheus node exporter. 2023\.  https://github.com/prometheus/node_exporter.
  * on-k8s-operator by Google Cloud Platform (2023) Spark on-k8s-operator by Google Cloud Platform. 2023.  https://github.com/GoogleCloudPlatform/spark-on-k8s-operator.
  * on Kubernetes (2023) Flink on Kubernetes. 2023\.  https://nightlies.apache.org/flink/flink-docs-master/docs/deployment/resource-providers/native_kubernetes/.
  * Park et al. (2021) Jinwoo Park, Byungkwon Choi, Chunghan Lee, and Dongsu Han. 2021\.  GRAF: A graph neural network based proactive resource allocation framework for SLO-oriented microservices. In _Proceedings of the 17th International Conference on emerging Networking EXperiments and Technologies_. 154–167.
  * Prometheus. (2023) Prometheus. 2023\.  https://prometheus.io/.
  * Qiu et al. (2020) Haoran Qiu, Subho S Banerjee, Saurabh Jha, Zbigniew T Kalbarczyk, and Ravishankar K Iyer. 2020\.  FIRM: An intelligent fine-grained resource management framework for slo-oriented microservices. In _Proceedings of The 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘20)_.
  * Rossi et al. (2019) Fabiana Rossi, Matteo Nardelli, and Valeria Cardellini. 2019\.  Horizontal and vertical scaling of container-based applications using reinforcement learning. In _2019 IEEE 12th International Conference on Cloud Computing (CLOUD)_. IEEE, 329–338.
  * Rzadca et al. (2020) Krzysztof Rzadca, Pawel Findeisen, Jacek Swiderski, Przemyslaw Zych, Przemyslaw Broniek, Jarek Kusmierek, Pawel Nowak, Beata Strack, Piotr Witusowski, Steven Hand, et al. 2020\.  Autopilot: workload autoscaling at Google. In _Proceedings of the Fifteenth European Conference on Computer Systems_. 1–16.
  * Shi et al. (2015) Juwei Shi, Yunjie Qiu, Umar Farooq Minhas, Limei Jiao, Chen Wang, Berthold Reinwald, and Fatma Özcan. 2015.  Clash of the titans: Mapreduce vs. spark for large scale data analytics.  _Proceedings of the VLDB Endowment_ 8, 13 (2015), 2110–2121.
  * Slivkins et al. (2019) Aleksandrs Slivkins et al. 2019\.  Introduction to multi-armed bandits.  _Foundations and Trends® in Machine Learning_ 12, 1-2 (2019), 1–286.
  * Soltesz et al. (2007) Stephen Soltesz, Herbert Pötzl, Marc E. Fiuczynski, Andy Bavier, and Larry Peterson. 2007\.  Container-Based Operating System Virtualization: A Scalable, High-Performance Alternative to Hypervisors. In _Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007_. ACM, Lisbon Portugal, 275–287.  https://doi.org/10.1145/1272996.1273025
  * Srinivas et al. (2009) Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. 2009.  Gaussian process optimization in the bandit setting: No regret and experimental design.  _arXiv preprint arXiv:0912.3995_ (2009).
  * Sui et al. (2015) Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. 2015\.  Safe exploration for optimization with Gaussian processes. In _International conference on machine learning_. PMLR, 997–1005.
  * Sui et al. (2018) Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue. 2018\.  Stagewise safe bayesian optimization with gaussian processes. In _International conference on machine learning_. PMLR, 4781–4789.
  * Takac and Zabovsky (2012) Lubos Takac and Michal Zabovsky. 2012.  Data analysis in public social networks. In _International scientific conference and international workshop present day trends of innovations_ , Vol. 1. Present Day Trends of Innovations Lamza Poland.
  * Vakili et al. (2021) Sattar Vakili, Henry Moss, Artem Artemev, Vincent Dutordoir, and Victor Picheny. 2021.  Scalable Thompson sampling using sparse Gaussian process models.  _Advances in neural information processing systems_ 34 (2021), 5631–5643.
  * Venkataraman et al. (2016) Shivaram Venkataraman, Zongheng Yang, Michael Franklin, Benjamin Recht, and Ion Stoica. 2016\.  Ernest: Efficient performance prediction for large-scale advanced analytics. In _13th $\\{$USENIX$\\}$ symposium on networked systems design and implementation ($\\{$NSDI$\\}$ 16)_. 363–378.
  * Vermorel and Mohri (2005) Joannes Vermorel and Mehryar Mohri. 2005.  Multi-armed bandit algorithms and empirical evaluation. In _Machine Learning: ECML 2005: 16th European Conference on Machine Learning, Porto, Portugal, October 3-7, 2005. Proceedings 16_. Springer, 437–448.
  * Wang et al. (2022) Ziliang Wang, Shiyi Zhu, Jianguo Li, Wei Jiang, KK Ramakrishnan, Yangfei Zheng, Meng Yan, Xiaohong Zhang, and Alex X Liu. 2022.  DeepScaling: microservices autoscaling for stable CPU utilization in large scale cloud systems. In _Proceedings of the 13th Symposium on Cloud Computing_. 16–30.
  * Williams and Rasmussen (2006) Christopher KI Williams and Carl Edward Rasmussen. 2006.  _Gaussian processes for machine learning_. Vol. 2.  MIT press Cambridge, MA.
  * Wilson et al. (2020) James Wilson, Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, and Marc Deisenroth. 2020\.  Efficiently sampling functions from Gaussian process posteriors. In _International Conference on Machine Learning_. PMLR, 10292–10302.
  * Xin et al. (2022) Jinhan Xin, Kai Hwang, and Zhibin Yu. 2022.  LOCAT: Low-Overhead Online Configuration Auto-Tuning of Spark SQL Applications [Extended Version].  _arXiv preprint arXiv:2203.14889_ (2022).
  * Yadwadkar et al. (2014) Neeraja J Yadwadkar, Ganesh Ananthanarayanan, and Randy Katz. 2014.  Wrangler: Predictable and faster jobs using fewer resources. In _Proceedings of the ACM Symposium on Cloud Computing_. 1–14.
  * Zhang et al. (2019) Chengliang Zhang, Minchen Yu, Wei Wang, and Feng Yan. 2019\.  Mark: Exploiting cloud services for cost-effective, slo-aware machine learning inference serving. In _2019 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 19)_. 1049–1062.
  * Zhang et al. (2022) Yongkang Zhang, Yinghao Yu, Wei Wang, Qiukai Chen, Jie Wu, Zuowei Zhang, Jiang Zhong, Tianchen Ding, Qizhen Weng, Lingyun Yang, et al. 2022\.  Workload consolidation in alibaba clusters: the good, the bad, and the ugly. In _Proceedings of the 13th Symposium on Cloud Computing_. 210–225.
  * Zhao et al. (2022) Chenxingyu Zhao, Tapan Chugh, Jaehong Min, Ming Liu, and Arvind Krishnamurthy. 2022.  Dremel: Adaptive Configuration Tuning of RocksDB KV-Store. In _Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems_. 61–62.
  * Zhou et al. (2018) Xiang Zhou, Xin Peng, Tao Xie, Jun Sun, Chao Ji, Wenhai Li, and Dan Ding. 2018\.  Fault analysis and debugging of microservice systems: Industrial survey, benchmark system, and empirical study.  _IEEE Transactions on Software Engineering_ (2018).