![](https://csdnimg.cn/release/download_crawler_static/11838461/bg11.jpg)
Given that a preemption occurs when a market’s spot
price exceeds the bid price given at resource acquisition
time, AcquireMgr can affect the preemption probability
via the delta between its bid price and the current price,
informed by historical pricing trends. In our implemen-
tation, which is specialized to AWS EC2, the predictions
use machine learning (ML) models trained on historical
EC2 Spot Price data. The expected cost of the computa-
tion takes into account EC2’s policy of partial refunds for
preempted instances, which often results in AcquireMgr
choosing high-risk instances and achieving even bigger
savings than just the discount for preemptibility.
In addition to the expected cost savings, Tributary’s
spot-dancing provides a burst tolerance benefit. Any
elastic control scheme has some reaction delay between
an unexpected burst and any resulting addition of re-
sources, which can cause SLO violations. Because Trib-
utary’s resource collection is almost always bigger than
the scaling policy’s most recent target in order to accom-
modate bulk preemptions, extra resources are often avail-
able to handle unexpected bursts. Of course, traditional
elastic control schemes can also acquire extra resources
as a buffer against bursts, but only at a cost, whereas the
extra resources when using Tributary are a bonus side-
effect of AcquireMgr’s robust cost savings scheme.
Results for four real-world web request arrival traces
and real AWS EC2 spot market data demonstrate Tribu-
tary’s cost savings and SLO benefits. For each of three
popular scaling policies (one reactive and two predic-
tive), Tributary’s exploitation of AWS spot instances re-
duces cost by 81–86% compared to traditional scaling
with on-demand instances for achieving a given SLO
(e.g., 95% of requests below 1 second). Compared to un-
safely using traditional scaling with spot instances (AWS
AutoScale [2]) instead of on-demand instances, Tribu-
tary reduces cost by 47–62% for achieving a given SLO.
Compared to other recent systems’ policies for exploit-
ing spot instances to reduce cost [24, 16], Tributary pro-
vides higher SLO attainment at significantly lower cost.
This paper makes four primary contributions. First,
it describes Tributary, the first resource acquisition sys-
tem that takes advantage of preemptible cloud resources
for elastic services with latency SLOs. Second, it in-
troduces AcquireMgr algorithms for composing resource
collections of preemptible resources cost-effectively, ex-
ploiting the partial refund model of EC2’s spot markets.
Third, it introduces a new preemption prediction ap-
proach that our experiments with EC2 spot market price
traces show is significantly more accurate than previous
preemption predictors. Fourth, we show that Tributary’s
approach yields significant cost savings and robustness
benefits relative to other state-of-the-art approaches.
2 Background and Related Work
Elastic services dynamically acquire and release machine
resources to adapt to time-varying client load. We distin-
guish two aspects of elastic control, the scaling policy
and the resource acquisition scheme. The scaling pol-
icy determines, at any point in time, how many resources
the service needs in order to satisfy a given SLO. The
resource acquisition scheme determines which resources
should be allocated and, in some cases, aspects of how
(e.g., bid price or priority level). This section discusses
AWS EC2 spot instances and resource acquisition strate-
gies to put Tributary and its new approach to resource
acquisition into context.
2.1 Preemptible resources in AWS EC2
In addition to non-preemptible, or reliable resources,
most cloud infrastructures offer preemptible resources as
a way to increase utilization in their datacenters. Pre-
emptible resources are made available, on a best-effort
basis, at decreased cost (in for-pay settings) and/or at
lower priority (in private settings). This subsection de-
scribes preemptible resources in AWS EC2, both to pro-
vide a concrete example and because Tributary and most
related work specialize to EC2 behavior.
EC2 offers “on-demand instances”, which are reli-
able VMs billed at a flat per-second rate. EC2 also of-
fers the same VM types as “spot instances”, which are
preemptible but are usually billed at prices significantly
lower (70% - 80%) than the corresponding on-demand
price. EC2 may preempt spot instances at any time, thus
presenting users with a trade-off between reliability (on-
demand) and cost savings (spot).
There are several properties of the AWS EC2 spot mar-
ket behavior that affect customer cost savings and the
likelihood of instance preemption. (1) Each instance type
in each availability zone has a unique AWS-controlled
spot market associated with it, and AWS’s spot mar-
kets are not truly free markets [9]. (2) Price movements
among spot markets are not always correlated, even for
the same instance type in a given region [23]. (3) Cus-
tomers specify a bid in order to acquire a spot instance.
The bid is the maximum price a customer is willing to
pay for an instance in a specific spot market; once a bid
is accepted by AWS, it cannot be modified. (4) A cus-
tomer is billed the spot market price (not the bid price)
for as long as the spot market price for the instance does
not exceed the bid price or until the customer releases
it voluntarily. (5) As of Oct 2nd, 2017, AWS charges
for the usage of an EC2 instance up to the second, with
one exception: if the spot market price of an instance ex-
ceeds the bid price during its first hour, the customer is
refunded fully for its usage. No refund is given if the
spot instance is revoked in any subsequent hour. We de-
fine the period where preemption makes the instance free
2 2018 USENIX Annual Technical Conference USENIX Association