Technical Reports
HPL-2010-98
Click here for full text:
What consistency does your key-value store actually provide?
Anderson, Eric; Li, Xiaozhou; Shah, Mehul; Tucek, Joseph; Wylie, Jay
HP Laboratories
HPL-2010-98
Keyword(s): Consistency, graph algorithms, key-value stores
Abstract: Many key-value stores have recently been proposed as platforms for always-on, globally-distributed, Internet scale applications. To meet their needs, these stores often sacrifice consistency for availability. Yet, few tools exist that can verify the consistency actually provided by a key-value store, and quantify the violations if any. How can a user check if a storage system meets its promise of consistency? If a system only promises eventual consistency, how bad is it really? In this paper, we present efficient algorithms that help answer these questions. By analyzing the trace of interactions between the client machines and a key-value store, the algorithms can report whether the trace is safe, regular, or atomic, and if not, how many violations there are in the trace. We run these algorithms on traces of our eventually consistent key value store called Pahoehoe and find few or no violations, thus showing that it often behaves like a strongly consistent system during our tests.
10 Pages
Additional Publication Information: Published in HotDep 2010, Vancouver BC, Canada, Oct. 30, 2010
External Posting Date: October 21, 2010 [Fulltext]. Approved for External Publication
Internal Posting Date: October 21, 2010 [Fulltext]