Low-Level Augmented Bayesian Optimization for Finding the Best Cloud VM

I. INTRODUCTION

• Experiments show that, for the same workload, choosing the optimal VM rather than the worst VM can be up to 20 times faster and 10 times less expensive.No single VM type is best for all workloads, and the same application may favor different VM types at different input sizes.Source: §I · pp. 1–2
• BO avoids extra historical training data and supports diverse objective functions, but its effectiveness can depend on insufficient VM characteristics, kernel choice, and initial measurements.The paper identifies core count, memory per core, and disk capacity among the instance characteristics that may not predict workload performance.Source: §I · pp. 1–2
• 50% of workloads required 6 measurements (33% of the search space), while 85% required 12 (66%), illustrating BO's variable search cost.The paper describes the failure modes as high search cost or a sub-optimal solution.Source: §I · p. 1, Figure 1 · p. 1
• Augmented BO integrates low-level performance information collected on measured VMs with high-level features to estimate performance on unmeasured VMs and update its belief during search.The authors identify I/O wait and memory usage as examples of low-level information that better captures application behavior.Source: §I · p. 2
• Search cost fell in 46 of 107 applications with Augmented BO, while performance remained the same or slightly better than Naive BO.For workloads with the fragility issue, the reported average search-cost reduction was about 20%, reaching 43% in some cases.Source: §I · p. 2

A. Problem Formalization

• The search objective is to minimize both the performance gap from the optimal VM and the number of measurements needed to find a near-optimal configuration.Performance is considered in terms of execution time and deployment cost.Source: A. Problem Formalization · p. 2

B. Large-scale evaluation on AWS

• The AWS evaluation measured 107 workloads across 18 VMs, covering 30 applications on Hadoop 2.7 and Spark 1.5 and 2.1.Workloads included data processing, OLAP, and machine learning; each was tested at three input sizes, with tests that ran out of memory on smaller VMs excluded.Source: B. Large-scale evaluation on AWS · pp. 2–3, Table I · p. 3
• The study varies workload inputs because behavior and the optimal VM can change with input size.The evaluation uses AWS with Apache Hadoop 2.7 and Apache Spark 1.5 and 2.1.Source: B. Large-scale evaluation on AWS · pp. 2–3
• Classification-Spark 1.5 ran 20 times slower on its worst VM than its best, while Linear Regression cost 10 times more to deploy on its worst VM.Figure 3 compares execution time and deployment cost across 18 VM types.Source: Figure 3 · p. 3

C. Choosing the best VM is troublesome

• A poor VM choice can make execution up to 20 times longer and cost ten times more than the optimal choice.The section also notes that more expensive VMs do not always deliver the best performance.Source: C. Choosing the best VM is troublesome · p. 3
• For Bayes, m4.2xlarge is most cost-effective with a small input, but its deployment cost rises by 40% with a large input.The best VM can change with input size or parameters.Source: C. Choosing the best VM is troublesome · p. 4, Figure 5 · p. 4
• Considering deployment cost compresses performance differences, making slower VMs competitive and cost-effective VM selection harder than choosing the fastest VM.For the regression workload, m4.2xlarge and r4.xlarge have deployment costs comparable to c4.2xlarge despite different execution times.Source: C. Choosing the best VM is troublesome · p. 4, Figure 6 · p. 4

D. Search-based optimization instead of complex models

• Complex performance models face noisy cloud measurements, high training-data requirements, and prediction error; PARIS reports up to 50% RMSE.Each workload execution is expensive, and cloud infrastructure sharing makes performance interference unavoidable.Source: D. Search-based optimization instead… · p. 4
• SMBO iteratively fits a surrogate from measured VM performance, selects and measures another VM, and updates its data until a stopping criterion is reached.The paper prefers SMBO as suitable for expensive black-box optimization and resistant to complex-model shortcomings.Source: D. Search-based optimization instead… · pp. 4–5

• The section introduces Bayesian Optimization and explains why it can be fragile when selecting cloud VMs.Source: §III · p. 5

A. What is Bayesian Optimization?

• Bayesian Optimization uses a probabilistic regression model to estimate unmeasured VM performance and an acquisition function to choose the next VM to measure.Gaussian Processes are the standard probabilistic model described here; Expected Improvement is used in CherryPick.Source: A. What is Bayesian Optimization? · p. 5
• Gaussian Process performance depends on kernel choice because its smoothness assumption can fail when nearby VM configurations have sharply different performance.CherryPick uses the Matérn 5/2 kernel because it does not require strong smoothness.Source: A. What is Bayesian Optimization? · p. 5

B. How to choose the right covariance kernel function?

• Matérn 1/2 finds the optimal VM faster for execution time, but performs worst when searching for a cost-effective VM.The examples show that kernel choice affects BO’s usefulness; selecting a kernel can rely on engineering or automatic model selection.Source: B. How to choose the right covariance… · p. 5
• A memory or disk bottleneck can make workloads perform very differently on nearby VMs, so architecture parameters alone may not predict performance sufficiently.Source: B. How to choose the right covariance… · pp. 5–6

C. No one-size-fits-all initial points!

• About 15% of applications failed to find the optimal configuration within six attempts with one set of initial VMs, while a different set found it within six attempts.The tested starting VMs were c4.xlarge, m4.large, and r3.2xlarge; the authors note that new VMs frequently change which initial VMs work well.Source: C. No one-size-fits-all initial points! · p. 6

D. Summary

• BO can incur high search cost or find a sub-optimal solution, so the paper aims to reduce fragility by augmenting BO with low-level information and less-sensitive variants.The authors identify kernel choice and initial VMs as factors affecting BO effectiveness, while noting that selecting a suitable kernel requires further study.Source: D. Summary · p. 6

IV. LOW-LEVEL INSIGHT

• Low-level performance metrics are used alongside VM characteristics because instance-space information alone is inadequate to characterize a VM fully.Memory commit size and I/O wait can indicate workload needs or bottlenecks; Figure 8 illustrates memory pressure and CPU utilization capturing a memory bottleneck.Source: A. Choosing the Low-Level Metrics · p. 6, Figure 8 · p. 6

A. Choosing the Low-Level Metrics

• The selected metrics cover workload progress, memory pressure, and I/O pressure, while the authors caution that too many features can cause overfitting.They list user-time CPU utilization, I/O wait, and task count for workload progress; memory commit percentage for memory pressure; and disk utilization and wait time for I/O pressure.Source: A. Choosing the Low-Level Metrics · p. 6

B. Low-Level Augmented Bayesian Optimization

• The approach predicts cost or time for a candidate VM from its characteristics and low-level metrics observed on VMs already measured.This is described as similar to expert reasoning and table-based models.Source: B. Low-Level Augmented Bayesian… · p. 6
• Augmented BO uses VM characteristics and observed low-level metrics as inputs, with workload performance as the target, and uses Extra-Trees instead of a Gaussian Process surrogate.The tree-based model is selected to capture complex performance behavior and avoid the careful kernel selection required by a Gaussian Process.Source: B. Low-Level Augmented Bayesian… · pp. 6–7
• Prediction Delta selects the VM with the best estimated performance and can stop the search when no better VM is predicted.The paper replaces Expected Improvement because it is not useful when the kernel cannot estimate the black-box function.Source: B. Low-Level Augmented Bayesian… · p. 7
• For each measured source VM, the model estimates performance on unmeasured destination VMs using that source VM’s low-level metrics, then averages estimates across source VMs.This allows model updates before low-level information is available for the destination VM.Source: B. Low-Level Augmented Bayesian… · p. 7

V. EVALUATION

• The evaluation compares Augmented BO with Naive BO.The section introduces the experimental setting and evaluation method for this comparison.Source: §V · p. 7

A. Experimental Method

• The study runs 107 workloads from HiBench and spark-perf on 18 VM types across six AWS families and three sizes, collecting low-level metrics with sysstat.The workloads use Hadoop 2.7 and Spark 2.1 or 1.5; the authors report no significant overhead from metric collection.Source: A. Experimental Method · p. 7

B. Comparison

• Within Region II, Augmented BO finds optimal VMs for 96% of workloads within ten measurements, versus 80% for Naive BO.It has a slow start, but becomes effective eventually.Source: B. Comparison · p. 8, Figure 9 · p. 8
• Augmented BO underperforms Naive BO in the first four steps, which the authors attribute to overfitting from its larger training-feature set.They identify Hybrid BO as a workaround but do not focus on it in this paper.Source: B. Comparison · p. 8
• The best VM found by Augmented BO can be 4% away from the optimum, a difference the authors say can be ignored in practice.They add that the difference may be amortized as the instance space and search cost grow.Source: B. Comparison · p. 8
• For deployment-cost minimization, six attempts find the best VM for 60% of applications with Augmented BO, versus 50% with Naive BO.Augmented BO also shows a clear win after five measurements, although it has a slow start.Source: B. Comparison · p. 8
• After six VM measurements, Naive BO fails to find the best VM for 36% of workloads when minimizing time and 50% when minimizing cost.Augmented BO increases by up to 20% the number of workloads for which it finds the optimal VM at step seven.Source: B. Comparison · p. 8
• Across three examples, Augmented BO reduces search cost and variance; the plotted line is median execution time over 100 repeats, with shaded IQR.The repeats use different initial points, and larger shaded regions indicate higher variance.Source: B. Comparison · pp. 8–9, Figure 10 · p. 8

A. Bayesian Optimization in Practice

• The stopping-criterion comparison varies Augmented BO's Prediction Delta threshold from 0.9 to 1.3 against Naive BO's expected improvement criterion.The authors examine the workload regions separately and relax optimality because users may accept some performance loss for lower search cost.Source: A. Bayesian Optimization in Practice · p. 9
• In Region I, Augmented BO at thresholds 1.25 and 1.3 performs similarly to Naive BO, with performance 1.04 rather than 1.0.Naive BO finds the optimal VM regardless of stopping criterion; the authors hypothesize that it cannot estimate when it has found the optimum.Source: A. Bayesian Optimization in Practice · p. 9

B. Time-Cost Trade-off

• The time-cost product gives equal importance to time and cost, treating a 10% time improvement and a 10% cost increase as desirable.The authors note that a 10% execution-time improvement can require a 50% increase in deployment cost.Source: B. Time-Cost Trade-off · p. 9

A. Bayesian Optimization in Practice

• Across 107 workloads, Augmented BO reduces search cost by 20% and finds VMs with 5% lower deployment cost on average; 46 workloads improve on both measures.The comparison uses a 1.1 threshold for Augmented BO and 10% EI for Naive BO.Source: A. Bayesian Optimization in Practice · p. 9, Figure 12 · p. 10

B. Time-Cost Trade-off

• With a 1.05 threshold, Augmented BO uses no more than six evaluations across all 107 applications, while Naive BO searches more than six times for 24%.Naive BO searches at least ten times for 13% of workloads; the authors say stopping criteria should vary with workload and objective.Source: B. Time-Cost Trade-off · p. 10

VII. RELATED WORK

• Ernest exploits workload structure, CherryPick applies Bayesian optimization without low-level information, and PARIS builds a performance model from large training data.The paper argues PARIS may be unsuitable for batch workloads because of low prediction accuracy.Source: §VII · p. 10
• Prior tuning methods often target the same workload on the same machine type, whereas this work seeks the best cloud-machine configuration for a given workload.Related low-level-performance work includes identifying VM interference and predicting storage or distributed-storage performance.Source: §VII · p. 10

VIII. CONCLUSION

• Augmented BO integrates low-level metrics into its surrogate model with negligible overhead; in 46 of 107 workloads, it outperforms state-of-the-art BO on performance and search cost.The method also modifies existing BO to make more informed decisions.Source: §VIII · p. 10
• The authors conclude that off-the-shelf BO is often insufficient for VM selection without systems knowledge such as CPU utilization, working memory size, and I/O wait time.Their future work plans to add historical performance data to further reduce search cost.Source: §VIII · p. 10