Accession Number:

ADA555882

Title:

Probabilistically Bounded Staleness for Practical Partial Quorums

Descriptive Note:

Technical rept.

Corporate Author:

CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Report Date:

2012-01-03

Pagination or Media Count:

15.0

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.

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE