Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS

COPS (Clusters of Order-Preserving Servers) addresses the same problem as PNUTS, namely, that online applications need to be scalable and provide high availability with low latency and partition tolerance, sacrificing some level of consistency. The authors present a wide-area distributed key-value store that provides "causal+" consistency, i.e. causal consistency with convergent conflict handling. Causal consistency ensures that causal dependencies between operations are preserved in the data store. Convergent conflict handling guarantees that replicas don't permanently diverge and that conflicting updates are handled identically at all sites (i.e. if there are two put() operations on the same key that conflict, then they are resolved in the same way at all replicas). Two versions of COPS are provided: the first provides causal+ consistency between individual keys, while the second provides consistent views of multiple keys (more expensive).

The main tradeoffs here are complexity versus performance, and the COPS approach opts for more complexity general (given the stronger consistency guarantees). I don't think there is very much new here -- this seems like a rehash of ideas we saw in PNUTS and Dynamo, though I agree that the multiple key causal consistency seems valuable (though expensive performance-wise). That said, it seems like Yahoo has been able to get along pretty well without this, so it might not be worth the extra overhead. I doubt this paper specifically will have significant influence over the next decade, simply because there isn't too much novelty here, but the general idea of highly available, scalable, low latency geographically distributed data stores is certainly relevant, especially for web applications.