Technical Report: Optimistic Execution in Key-Value Store
share
Limitations of CAP theorem imply that if availability is desired in the presence of network partitions, one must sacrifice sequential consistency, a consistency model that is more natural for system design. 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 continue 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 practical graph 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 50-80% increase in throughput when compared with sequential consistency. We also show that the overhead of the monitoring itself is low (typically less than 4%) and the latency of detecting violations is small. In particular, more than 99.9% violations are detected in less than 50 milliseconds in regional AWS networks, and in less than 5 seconds in global AWS networks.
READ FULL TEXT