Tributary: spot-dancing for elastic services with latency SLOs

Aaron Harlap, Andrew Chung, Alexey Tumanov, Gregory R. Ganger, Phillip B. Gibbons

TL;DR

This paper introduces "Tributary," a novel elastic cloud control system that leverages the cost savings of preemptible cloud instances (like AWS Spot Instances) while mitigating their inherent risk of sudden termination. By intelligently predicting preemption probabilities and diversifying resource acquisition across various spot markets, Tributary significantly reduces costs and improves reliability for latency-sensitive services.

What Problem Does This Paper Address?

Modern cloud services often need to scale dynamically to handle fluctuating user demand. Traditionally, this has been achieved using reliable, but more expensive, "on-demand" instances. A more cost-effective alternative is "preemptible" instances, which offer significant discounts but can be terminated by the cloud provider with little notice. This preemption risk, especially when it occurs in "bulk" across multiple instances, poses a major challenge for services with strict Service Level Objectives (SLOs), particularly those focused on low latency. Existing solutions either avoid preemptible instances altogether or use them with high-risk strategies that can lead to SLO violations. This paper tackles the problem of how to reliably and cost-effectively use preemptible instances for latency-sensitive elastic services.

Methods

Tributary's core innovation lies in its "AcquireMgr" component, which manages resource acquisition. Instead of simply reacting to demand, AcquireMgr proactively predicts preemption probabilities for different instance types and availability zones. It uses machine learning models, specifically Long Short-Term Memory (LSTM) Recurrent Neural Networks (RNNs), trained on historical AWS spot market data, to achieve highly accurate preemption predictions.

Key methodological aspects include:

  • Spot-Dancing: This refers to Tributary's strategy of acquiring diverse collections of resources from multiple, often uncorrelated, spot markets. This diversification helps mitigate the impact of bulk preemptions from a single market.
  • Probabilistic Cost and Utility Modeling: AcquireMgr calculates the expected cost and utility of various resource allocations, taking into account preemption probabilities and the partial refund policy of AWS EC2 spot instances.
  • Regularization for Diversity: A regularization term is introduced to encourage bidding in markets with low correlation, further enhancing robustness against correlated preemptions.
  • Buffer Allocation: Tributary inherently acquires more resources than immediately needed to act as a buffer against preemptions. This buffer also provides a natural advantage in handling unexpected workload bursts.

Datasets

The paper uses real-world request arrival traces for evaluation:

  • ClarkNet: From the ClarkNet ISP's HTTP servers.
  • Berkeley: From the Berkeley Home IP proxy service.
  • WITS: A sampled trace from the Waikato Internet Traffic Storage.
  • WorldCup98: The arrival trace of the workload on the 1998 FIFA World Cup HTTP Servers.

These traces were scaled to have an average of 125 requests per second for experimental purposes. The preemption prediction models were trained on historical AWS spot market price histories from 06/06/16 to 01/22/17 and evaluated on data from 01/23/17 to 03/20/17.

Key Insights and Ideas

  • Preemption is Predictable (and Exploitable): The paper demonstrates that preemption probabilities can be predicted with high accuracy using ML models, moving beyond simple historical averages. This predictability is key to leveraging spot instances effectively.
  • Diversity is Key to Robustness: Acquiring resources from uncorrelated spot markets is crucial for surviving bulk preemptions. This "spot-dancing" is a core differentiator from simpler diversification strategies.
  • Buffers as a Double Win: The resources acquired to buffer against preemptions also naturally handle unexpected load spikes, providing both cost savings and improved reliability.
  • Partial Refunds Matter: Tributary's cost model explicitly accounts for AWS's partial refund policy for preempted instances, allowing it to bid more aggressively and achieve greater savings.
  • LSTM's Temporal Advantage: The LSTM RNN's ability to capture the temporal nature of spot market prices significantly improves preemption prediction accuracy compared to static models.

Key Results

Tributary demonstrates significant improvements across various metrics:

  • Cost Savings:
    • 81-86% cost reduction compared to traditional scaling on non-preemptible on-demand instances.
  • 47-62% cost reduction compared to a high-risk approach using spot instances with traditional scaling.
  • Up to 41% cost reduction compared to standard bidding policies for spot instances.
  • SLO Attainment:
    • Significantly reduces "slow" requests (requests not meeting latency SLOs) compared to all baselines. For example, on the ClarkNet trace, it reduced slow requests by 72%, 61%, and 64% for different scaling policies compared to AutoScale.
  • Outperforms state-of-the-art resource managers like ExoSphere and Proteus in both cost and SLO attainment.
  • Prediction Accuracy:
    • Tributary's LSTM RNN model achieved 11% higher accuracy and 27% higher F1 score than historical median-based prediction methods.
  • This improved prediction accuracy leads to 37% lower cost compared to using historical medians.

Limitations and Future Work

  • Computational Complexity: The AcquireMgr algorithm's computational expense grows with the number of spot markets considered. The authors suggest grouping similar, correlated spot markets and using regularization to manage this.
  • Future Cloud Market Dynamics: The paper discusses potential future changes in AWS billing (elimination of refunds, free market behavior) and how Tributary would adapt. They believe Tributary's core principles would still offer advantages.
  • Generalizability: While Tributary is designed for AWS EC2, the authors suggest its principles could apply to other clouds offering preemptible resources, provided they expose sufficient information for preemption prediction. They note that Google Compute Engine currently lacks such signals.
  • Mass Adoption Effects: The paper acknowledges that a detailed analysis of the potential effects of widespread adoption of systems like Tributary on EC2 spot markets is beyond its scope, but suggests evaluating these effects in future work.

Summary updated

BibTeX
@inproceedings{harlap2018tributary,
  author = {Aaron Harlap and Andrew Chung and Alexey Tumanov and Gregory R. Ganger and Phillip B. Gibbons},
  title = {{Tributary: spot-dancing for elastic services with latency SLOs}},
  booktitle = {USENIX ATC},
  year = {2018},
}
Figure