Using weaker
consistency models with monitoring and recovery for improving performance of
key-value stores.
Duong
N. Nguyen, Aleksey Charapko, Sandeep S. Kulkarni
Abstract
Consistency properties provided by most key-value
stores can be classified into sequential consistency and eventual consistency.
The former is easier to program with but suffers from lower performance whereas
the latter suffers from potential anomalies while providing higher performance.
We focus on the problem of what a designer should do if he/she has an algorithm
that works correctly with sequential consistency but is faced with an
underlying key-value store that provides a weaker (e.g., eventual or causal)
consistency. We propose a detect-rollback based approach: The designer identifies
a correctness predicate, say P, and continues to run the protocol, as our
system monitors P. If P is violated (because the underlying key-value store
provides a weaker consistency), the system rolls back and resumes the
computation at a state where P holds.
We evaluate this approach with graph-based
applications running on the Voldemort key-value store. Our experiments with
deployment on Amazon AWS EC2 instances shows that using eventual consistency
with monitoring can provide a 50% { 80% increase in throughput when compared
with sequential consistency. We also observe that the overhead of the
monitoring itself was low (typically less than 4%) and the latency of detecting
violations was small. In particular, in a scenario designed to intentionally
cause a large number of violations, more than 99:9% of violations were detected
in less than 50 milliseconds in regional networks (all clients and servers in
the same Amazon AWS region), and in less than 3 seconds in global networks.
We find that for some applications, frequent
rollback can cause the program using eventual consistency to effectively stall.
We propose alternate mechanisms for dealing with re-occurring rollbacks.
Overall, for applications considered in this paper, we find that even with
rollback, eventual consistency provides better performance than using
sequential consistency.
Keywords: predicate detection; distributed debugging; distributed monitoring;
distributed snapshot; distributed key-value stores; rollback
Paper:
Return to the publication list
Return to the Sandeep's home page