Probabilistically Bounded Staleness for Practical Partial Quorums
Abstract
Modern storage systems employing quorum replication are often configured to use partial, non-strict quorums. These systems wait only for a subset of their replicas to respond to a request before returning an answer, without guaranteeing that read and write replica sets intersect. While these partial quorum mechanisms provide only basic eventual consistency guarantees, with no limit to the recency of data returned, these configurations are frequently "good enough" for practitioners given their latency benefits. In this work we discuss why partial quorums are often acceptable in practice by analyzing the staleness of data they return. Extending prior work on strongly consistent probabilistic quorums and using models of Dynamo-style anti-entropy processes, we introduce Probabilistically Bounded Staleness (PBS) consistency, which provides expected bounds on staleness with respect to both versions and wall clock time. We derive a closed-form solution for versioned staleness and model real-time staleness for representative Dynamo-style systems under internet-scale production workloads. We quantitatively demonstrate why, in practice, eventually consistent systems employing partial quorums often serve consistent data.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 03, 2012
- Accession Number
- ADA555882
Entities
People
- Ion Stoica
- Joseph M. Hellerstein
- Michael Franklin
- Peter Bailis
- Shivaram Venkataraman
Organizations
- University of California, Berkeley