Analyzing Consistency Properties for Fun and Profit

Golab, Wojciech ; Li, Xiaozhou ; Shah, Mehul A.

HP Development Company

关键词: data consistency;    algorightms;    key-value stores;   

RP-ID  :  HPL-2011-6

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Motivated by the increasing popularity of eventually consistent key-value stores as a commercial service, we address two important problems related to the consistency properties in a history of operations on a read/write register (i.e., the start time, finish time, argument, and response of every operation). First, we consider how to detect a consistency violation as soon as one happens. To this end, we formulate a specification for online verification algorithms, and we present such algorithms for several well-known consistency properties. Second, we consider how to quantify the severity of the violations, if a history is found to contain consistency violations. We investigate two quantities: one is the staleness of the reads, and the other is the commonality of violations. For staleness, we further consider time- based staleness and operation-count-based staleness. We present efficient algorithms that compute these quantities. We believe that addressing these problems helps both key-value store providers and users adopt data consistency as an important aspect of key-value store offerings.