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

Abstract

📜 Abstract

Geo-replicated, distributed data stores that support complex online applications, such as social networks, must provide an “always-on” experience where operations always complete with low latency. Today’s systems often sacrifice strong consistency to achieve these goals, exposing inconsistencies to their clients and necessitating complex application logic. In this paper, we identify and define a consistency model—causal consistency with convergent conflict handling, or causal+—that is the strongest achieved under these constraints. We present the design and implementation of COPS, a key-value store that delivers this consistency model across the wide-area. A key contribution of COPS is its scalability, which can enforce causal dependencies between keys stored across an entire cluster, rather than a single server like previous systems. The central approach in COPS is tracking and explicitly checking whether causal dependencies between keys are satisfied in the local cluster before exposing writes. Further, in COPS-GT, we introduce get transactions in order to obtain a consistent view of multiple keys without locking or blocking. Our evaluation shows that COPS completes operations in less than a millisecond, provides throughput similar to previous systems when using one server per cluster, and scales well as we increase the number of servers in each cluster. It also shows that COPS-GT provides similar latency, throughput, and scaling to COPS for common workloads.

Description

✨ Summary

The paper introduces causal+ consistency, combining causal consistency with convergent handling of concurrent conflicting writes. Causal consistency preserves dependencies between operations—for example, ensuring that a reference to an object is not visible before the referenced object—while convergent conflict handling ensures that replicas eventually produce the same result for concurrent updates. The default COPS conflict policy is last-writer-wins, implemented using Lamport-timestamp-based versions.

COPS is designed for ALPS systems: systems emphasizing availability, low latency, partition tolerance, and high scalability. Each datacenter contains a locally linearizable, partitioned key-value cluster. Client operations complete locally, while writes are replicated asynchronously to other datacenters. A replicated write is not exposed at a remote cluster until its causal dependencies have been satisfied there. This is implemented with dependency metadata, asynchronous put_after replication, and dep_check operations.

A central systems insight is that causal dependencies can be tracked across independently partitioned servers without imposing a single global serialization point. COPS reduces replication overhead by retaining only “nearest” dependencies: dependencies that transitively cover other dependencies in the causality graph. This allows causal ordering across keys and machines while preserving scale-out behavior.

COPS-GT extends the system with non-blocking get transactions. A transaction first reads all requested keys in parallel, examines their dependency metadata, and then performs a second parallel round only for keys whose versions are too old to form a causally consistent snapshot. The algorithm therefore completes in at most two rounds of local reads and avoids locks and blocking. COPS-GT uses multiple retained versions and dependency metadata, with garbage collection to bound storage overhead.

The evaluation reports sub-millisecond median operation latency. In the single-server experiments, COPS achieves approximately 52 Kops/s for reads and 30 Kops/s for single-dependency writes; COPS-GT achieves similar read latency but lower write throughput because of version and dependency management. Across tested configurations, COPS scales nearly linearly as servers are added to a datacenter. COPS-GT incurs greater overhead for write-heavy and highly interdependent workloads, but approaches COPS performance for read-heavy workloads, larger values, lower dependency rates, and higher inter-operation delays.

The paper had a clear influence on subsequent causal-consistency research. The authors’ follow-up system, Eiger, explicitly builds on COPS and extends its approach from a basic key-value model to Cassandra’s column-family data model, while adding scalable write-only transactions and broader read-only transaction support. (cs.cmu.edu) Later systems and surveys continued to use COPS as a reference design and comparison point for dependency tracking, causal replication, and non-blocking read-only transactions. (sciencedirect.com)

The available evidence supports substantial research influence, particularly through Eiger and later causal-consistency protocols. The sources reviewed do not establish that the original COPS implementation itself became a widely deployed commercial product; the documented industry connection is primarily through the follow-up Eiger work implemented with Cassandra-related technology. (da-data.blogspot.com)