Stronger Semantics for Low-Latency Geo-Replicated Storage
📜 Abstract
We present the first scalable, geo-replicated storage system that guarantees low latency, offers a rich data model, and provides “stronger” semantics. Namely, all client requests are satisfied in the local datacenter in which they arise; the system efficiently supports useful data model abstractions such as column families and counter columns; and clients can access data in a causally-consistent fashion with read-only and write-only transactional support, even for keys spread across many servers. The primary contributions of this work are enabling scalable causal consistency for the complex column-family data model, as well as novel, non-blocking algorithms for both read-only and write-only transactions. Our evaluation shows that our system, Eiger, achieves low latency (single-ms), has throughput competitive with eventually-consistent and non-transactional Cassandra (less than 7% overhead for one of Facebook’s real-world workloads), and scales out to large clusters almost linearly (averaging 96% increases up to 128 server clusters).
✨ Summary
Summary
The paper presents Eiger, a geo-replicated storage system designed to combine three properties that were difficult to obtain simultaneously: low-latency operations confined to the local datacenter, a Cassandra-like column-family data model with counter columns, and semantics stronger than eventual consistency. Eiger provides causal consistency by attaching compact, operation-based dependency metadata to writes and checking dependencies before applying replicated operations.
Its main algorithmic contributions are two non-blocking transaction mechanisms. Read-only transactions use logical-time validity intervals to construct a consistent snapshot across keys and servers, normally in one round and in at most two local read rounds. Write-only transactions use a variant of two-phase commit with positive cohorts and indirection, allowing atomic updates across multiple keys within the originating datacenter without locks or wide-area coordination. Replicas apply the transaction atomically during asynchronous propagation.
The evaluation reports single-millisecond local latency, including sub-5-millisecond 99th-percentile latency for the tested multi-key transactional writes. On a workload modeled on Facebook’s TAO, Eiger’s throughput was within 7% of eventually consistent Cassandra, and throughput increased almost linearly from 8 to 128 servers per cluster. The paper also identifies important limits: Eiger does not provide global linearizability or serializability, and permanent datacenter loss can lose acknowledged writes that have not yet been replicated.
Subsequent research cites Eiger as foundational prior work in low-latency causal consistency and geo-distributed transactions. Cure compares its stronger causal semantics and failure tolerance with earlier systems including Eiger; Blotter cites Eiger among systems addressing low-latency transactions for geo-replicated storage; and RAMP Transactions cites Eiger in the development of scalable atomic visibility techniques. These citations indicate that Eiger’s combination of causal consistency, multi-key read snapshots, and low-latency transactional writes became part of the reference design space for later geo-replicated storage research. (dd.thekkedam.org)
The paper’s publication metadata is corroborated by the authors’ publication record and the USENIX/DBLP records, which identify the work as an NSDI 2013 paper published in April 2013. (cs.cmu.edu)