Consistency Rationing in the Cloud: Pay only when it matters

Tim Kraska, Martin Hentschel, Gustavo Alonso, Donald KossmannPVLDB 2009 · DOI

TL;DR

This paper introduces "Consistency Rationing," a novel approach to cloud storage that dynamically adjusts data consistency levels based on cost and potential penalty for inconsistencies. By categorizing data and employing adaptive policies, it significantly reduces operational costs and improves response times compared to static consistency models.

What Problem Does This Paper Address?

Cloud storage solutions offer scalability and low cost, but often present a trade-off between consistency, cost, and availability. High consistency (e.g., serializability) is expensive per transaction and can sometimes reduce availability. Conversely, low consistency (e.g., eventual consistency) is cheaper but can lead to higher operational costs due to inconsistencies, such as overselling products in an e-commerce scenario. Existing systems typically offer fixed consistency levels, forcing developers to choose between high cost for strong consistency or potential financial/customer loss for weak consistency. This paper addresses the challenge of finding a balance by allowing dynamic adaptation of consistency levels based on the actual need and associated costs.

Methods

The core of the paper is the Consistency Rationing paradigm, which categorizes data into three types:

  • Category A (Serializable): Data requiring strong consistency (e.g., financial transactions). This is achieved using pessimistic concurrency protocols like two-phase locking (2PL).
  • Category C (Session Consistency): Data where temporary inconsistencies are acceptable and have low or no penalty cost (e.g., user preferences, logs). This is achieved using weaker consistency models like session consistency.
  • Category B (Adaptive): Data where consistency requirements vary. This is the focus of the adaptive policies.

The system dynamically switches between session consistency and serializability for Category B data based on various policies. These policies utilize:

  • Cost Model: A model that balances runtime transaction costs against the penalty costs of inconsistencies.
  • Statistical Analysis: Monitoring access frequencies and update patterns to predict the probability of conflicts.
  • Adaptive Policies:
    • General Policy: Adapts based on the probability of conflict.
  • Time Policies: Switches consistency based on time (e.g., approaching an auction deadline).
  • Numeric Policies (Fixed Threshold, Demarcation, Dynamic): Specifically for numerical data (like stock levels), these policies use thresholds or statistical models to decide when to enforce stronger consistency. The Dynamic policy is highlighted as particularly effective, using runtime statistics to adapt to changing access patterns and values.

Datasets

The paper evaluates its approach using the TPC-W benchmark. This benchmark simulates a web shop and includes 14 different actions and three mixes of these actions. The authors specifically used the "Ordering Mix," which is the most write-intensive, to better reveal the characteristics and trade-offs of their Consistency Rationing approach. They also note that the TPC-W benchmark typically requires strong consistency for all transactions, which they relax to study their adaptive strategies.

Key Insights and Ideas

  • Data-centric consistency: The paper argues for defining consistency at the data level rather than the transaction level, allowing for more granular control and optimization.
  • Probabilistic guarantees: The introduction of probabilistic consistency guarantees, especially using temporal statistics, is a novel way to manage uncertainty and optimize for cost.
  • Dynamic adaptation is key: Static consistency levels are suboptimal. Dynamically adjusting consistency based on real-time conditions (access patterns, time, data value) offers significant benefits.
  • Cost-benefit analysis is crucial: The core idea is to quantify the cost of transactions and the penalty of inconsistencies to make informed decisions about consistency levels.
  • Category B is where the magic happens: The most significant gains are realized by intelligently managing data in Category B, where consistency needs fluctuate.

Key Results

  • Significant Cost Reduction: The Dynamic policy for Category B data achieved the lowest overall cost per transaction, outperforming static A data (always serializable) and C data (always session consistent) policies, especially under skewed access patterns.
  • Improved Response Times: The Dynamic policy offered response times comparable to session consistency (Category C) and significantly faster than always-on serializability (Category A).
  • Adaptation to Penalty Costs: The Dynamic policy effectively adapts to varying penalty costs for inconsistencies. As penalty costs increase, it automatically enforces stronger consistency, converging towards the cost of always-using Category A data.
  • Fixed Threshold Policy Limitations: The Fixed Threshold policy for numeric data was shown to be highly sensitive to the chosen threshold and performed poorly under skewed distributions, highlighting the need for more sophisticated adaptive strategies.

Limitations and Future Work

  • Development Complexity: The paper acknowledges that Consistency Rationing introduces additional complexity for developers, requiring them to categorize data and specify policies. They suggest a split development model where data rationing is handled separately.
  • Statistical Accuracy: While runtime statistics are powerful, the paper notes that for new records or very small windows, statistics might be misleading. They propose using a default threshold initially and switching to dynamic policies once sufficient statistics are gathered.
  • Consolidating Statistics: The current implementation relies on local statistics. The authors suggest that consolidating statistics and broadcasting decisions could make the system more robust.
  • Relaxing Other ACID Properties: Future work could explore relaxing other ACID properties beyond isolation and consistency, such as durability.
  • Automatic Optimization: Exploring automatic optimization for other parameters like energy consumption and incorporating budget restrictions into the cost function are suggested future directions.

Summary updated

BibTeX
@article{kraska2009consistency,
  author = {Tim Kraska and Martin Hentschel and Gustavo Alonso and Donald Kossmann},
  title = {{Consistency Rationing in the Cloud: Pay only when it matters}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687657},
}
Figure