Metis: Robustly Tuning Tail Latencies of Cloud Systems

Zhao Lucis Li, Chieh-Jan Mike Liang, Wenjia He, Lianjie Zhu, Wenjun Dai, Jin Jiang, Guangzhong Sun

TL;DR

Cloud systems are notoriously difficult to tune for optimal performance, especially when it comes to tail latencies. This paper introduces Metis, an auto-tuning service that uses a customized Bayesian optimization approach to robustly find the best system configurations, significantly reducing tuning time and improving latency.

What Problem Does This Paper Address?

Operating modern cloud systems is a complex task. The sheer scale, diverse workloads, and vast parameter spaces make it incredibly challenging for human experts to manually tune systems for optimal performance. A key performance metric for many web-scale applications is tail latency (e.g., 99th percentile), which, while rare for individual requests, can significantly impact the end-user experience in multi-stage architectures. Existing auto-tuning methods, while promising, struggle with the robustness required for real-world cloud environments. Specifically, they often don't adequately handle:

  • Noisy performance metrics: Tail latencies can be sensitive to unpredictable factors like OS updates or background processes, making them prone to non-Gaussian noise.
  • Balancing exploration and exploitation: Auto-tuning needs to explore new configurations while also exploiting knowledge of promising ones. Existing methods can be inefficient in this balance.
  • Data outliers: Inaccurate or noisy benchmark results can mislead the tuning process.

Methods

Metis tackles these challenges by building upon Bayesian Optimization (BO) with Gaussian Processes (GP), but with several key customizations to enhance robustness:

  • Latin Hypercube Sampling (LHS) for Bootstrapping: Instead of random sampling, Metis uses LHS to select initial configurations. LHS is a stratified sampling technique that provides better coverage of the parameter space with fewer samples, leading to a more informed starting point for BO.
  • Customized Acquisition Function: This is the core innovation. Metis's acquisition function is a mixture of three sub-acquisition functions, each targeting a specific goal:
  • Exploration: Identifies configurations with high uncertainty in the GP model.
  • Exploitation: Identifies configurations with a high probability of being near the optimal.
  • Re-sampling: Crucially, Metis includes a mechanism to identify and suggest re-sampling of potentially noisy data points. This is achieved through a diagnostic model that quantifies the difference between measured and expected values.
  • Diagnostic Model for Outlier Detection: Metis builds a GP model without a specific data point to estimate its expected value and confidence interval. If the actual measured value falls outside this interval, the point is flagged as a potential outlier and can be re-sampled.
  • Decoupled Actions: Metis independently evaluates the potential information gain from exploration, exploitation, and re-sampling, allowing for a more nuanced decision on the next best action.

Datasets

The paper uses two main types of datasets for evaluation:

  • Production Workload Traces: Two 12-day traces (Prod_Trace1 and Prod_Trace2) from Microsoft Bing Ads key-value (KV) store clusters were used. These traces represent real-world query patterns.
  • Synthesized Workload Traces: Three synthetic traces (Synth_Trace1, Synth_Trace2, Synth_Trace3) were generated using the Yahoo! Cloud Serving Benchmark (YCSB) framework, with variations in key-value size distributions to test different scenarios.

Key Insights and Ideas

  • Robustness is Key for Cloud Auto-Tuning: The paper strongly argues that simply applying standard BO techniques is insufficient for real-world cloud systems due to inherent noise and complexity.
  • Re-sampling is a Game-Changer: The ability to identify and re-sample noisy data points significantly improves the accuracy and reliability of the auto-tuning process, especially in environments with intermittent background activities.
  • Decoupling Acquisition Goals Enhances Flexibility: Separating exploration, exploitation, and re-sampling allows Metis to adapt its strategy more effectively to different stages of the tuning process and varying data quality.
  • LHS Provides a Stronger Starting Point: Using LHS for bootstrapping trials leads to a more efficient initial exploration of the parameter space compared to random sampling.

Key Results

Metis demonstrated significant improvements across various metrics:

  • Reduced Tuning Time: Metis reduced the overall tuning time by 98.41% compared to manual tuning by human experts. For example, a manual tuning process that took weeks was completed by Metis in hours.
  • Improved Tail Latency: Metis reduced the 99-percentile latency by an average of 3.43% in production Bing Ads KV store clusters compared to expert-tuned configurations.
  • Higher Winning Rate: In controlled experiments, Metis picked the best configuration 84.67% of the time on production traces and 48.97% on synthesized traces, outperforming baselines like iTuned, CherryPick, and TPE.
  • Faster Convergence: Metis showed a faster convergence rate in finding optimal configurations, meaning it achieved good performance with fewer trials.
  • Robustness to Outliers: In the presence of data outliers, Metis had a 56.77% higher chance of picking a better configuration compared to other approaches.

Limitations and Future Work

  • Parameter Types: Metis currently does not directly support categorical parameters or multi-step parameters, which require specific handling.
  • Configuration Change Costs: While Metis can be configured to only push changes that offer significant improvement, it doesn't explicitly model the cost of server reboots or service interruptions. Future work could involve incorporating these costs into the optimization objective.
  • System Dependencies: The paper notes that while Metis can handle dependencies between parameters to some extent through its GP model, complex interdependencies might require more advanced modeling techniques.

The authors suggest that future work could explore extending Metis to handle categorical and multi-step parameters, and to more explicitly model the costs associated with configuration changes.

Summary updated

BibTeX
@inproceedings{li2018metis,
  author = {Zhao Lucis Li and Chieh-Jan Mike Liang and Wenjia He and Lianjie Zhu and Wenjun Dai and Jin Jiang and Guangzhong Sun},
  title = {{Metis: Robustly Tuning Tail Latencies of Cloud Systems}},
  booktitle = {USENIX ATC},
  year = {2018},
}
Figure