Probabilistically Bounded Staleness for Practical Partial Quorums
Probabilistically Bounded Staleness for Practical Partial Quorums
复制标题
DOI：
10.14778/2212351.2212359
复制
发表时间：
2012-04-01
影响因子：
2.5
通讯作者：
Stoica, Ion
中科院分区：
文献类型：
--
作者：
Bailis, Peter;Venkataraman, Shivaram;Stoica, Ion
数据存储复制需要在操作延迟和数据一致性之间进行基本的权衡。在本文中，我们将在群体复制数据存储上下文中研究这种权衡。在部分或非严格仲裁复制下，数据存储在回答查询之前等待副本子集的响应，而不保证读和写副本集相交。在实际部署时，这些配置只提供基本的最终一致性保证，对返回的数据的近时性没有限制。然而，有趣的是，对于从业者来说，考虑到延迟的好处，部分法定群体通常“足够好”。在这项工作中，我们解释了为什么部分quorum在实践中通常是可接受的，分析了它们返回的数据的过时性和它们提供的延迟优势。我们引入了概率有界过期一致性，它提供了关于版本和挂钟时间的预期过期界限。我们推导了一个封闭形式的版本过时解决方案，并为互联网规模生产工作负载下具有代表性的dynamo风格系统建立了实时过时模型。使用PBS，我们测量了部分仲裁系统的延迟-一致性权衡。我们定量地演示了最终一致的系统如何经常在几十毫秒内返回一致的数据，同时提供显著的延迟优势。
Data store replication results in a fundamental trade-off between operation latency and data consistency. In this paper, we examine this trade-off in the context of quorum-replicated data stores. Under partial, or non-strict quorum replication, a data store waits for responses from a subset of replicas before answering a query, without guaranteeing that read and write replica sets intersect. As deployed in practice, these configurations provide only basic eventual consistency guarantees, with no limit to the recency of data returned. However, anecdotally, partial quorums are often "good enough" for practitioners given their latency benefits. In this work, we explain why partial quorums are regularly acceptable in practice, analyzing both the staleness of data they return and the latency benefits they offer. 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 as well as model real-time staleness for representative Dynamo-style systems under internet-scale production workloads. Using PBS, we measure the latency-consistency trade-off for partial quorum systems. We quantitatively demonstrate how eventually consistent systems frequently return consistent data within tens of milliseconds while offering significant latency benefits.