Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen, “Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS,” SOSP, 2011. [PDF]

Summary

This paper introduces a new consistency model, causal+, that extends the causal consistency model and lies between sequential and causal consistency models. The authors claim that causal+ is the strongest consistency model achievable for ALPS systems (i.e., systems that require availability, low latency, partition-tolerance, and high scalability), but they do not prove why something stronger cannot be achieved.

The claimed novel part of the proposal that made the authors create a new consistency model instead of using causal itself is convergent conflict handling. Essentially, it requires all conflicting puts to be handled in the same manner at all replicas using the same handler function, h, which must be associative and commutative. The authors propose COPS (Clusters of Order-Preserving Servers) that executes all puts/gets in the underlying key-value store in a linearizable fashion within the same datacenter and replicates across datacenters in causal+ consistent order. In order to allow get transactions without locking in a non-blocking manner that will enable consistency across multiple keys, they also propose COPS-GT. Understandably, COPS-GT is more expensive; however, it is not more expensive than comparable systems.

Comments

The convergent conflict handling mechanism is related to the way Dynamo allows handling conflicts using user-defined functions. The cross-datacenter replication mechanism is similar to that in PNUTS. While COPS-GT provides transaction guarantees across multiple keys without much application logic, it is quite complicated. May be, it’s better to leave this to application developers as PNUTS argued from real-world experience (i.e., online services do not require this functionality often enough to make it a part of the system).

Btw, I liked the summary of consistency models in Section 3.2, where the authors put causal+ in a partial order of different consistency models.