Transactional storage for geo-replicated systems
📜 Abstract
We describe the design and implementation of Walter, a key-value store that supports transactions and replicates data across distant sites. A key feature behind Walter is a new property called Parallel Snapshot Isolation (PSI). PSI allows Walter to replicate data asynchronously, while providing strong guarantees within each site. PSI precludes write-write conflicts, so that developers need not worry about conflict-resolution logic. To prevent write-write conflicts and implement PSI, Walter uses two new and simple techniques: preferred sites and counting sets. We use Walter to build a social networking application and port a Twitter-like application.
✨ Summary
Summary
Walter is a geo-replicated transactional key-value store designed to combine low-latency local commits with asynchronous replication between distant sites. Its central contribution is Parallel Snapshot Isolation (PSI): transactions read from a consistent snapshot at their local site; committed concurrent transactions cannot have overlapping write sets; and causal dependencies are preserved across sites. Unlike conventional snapshot isolation, PSI permits different sites to observe non-conflicting transactions in different orders, enabling replication without imposing a global commit order.
The implementation uses multi-version concurrency control, vector timestamps, and per-object histories. Preferred sites allow transactions that write objects at their designated sites to commit without cross-site coordination. Counting sets (csets) represent set-like or counter-like data through commutative add and remove operations, allowing concurrent updates from different sites without write conflicts. Transactions involving regular objects outside their preferred sites use a slower two-phase commit protocol among the relevant preferred sites.
Walter provides normal and disaster-safe durability, asynchronous propagation, and a distinction between local commitment, disaster-safe durability, and global visibility. Its principal consistency limitation is the possibility of a temporary long fork, in which different sites expose different orders of concurrent, non-conflicting updates until replication converges. The prototype supported WaltSocial and a port of ReTwis; experiments on four Amazon EC2 sites reported fast-commit 99.9th-percentile latency of 27 ms, WaltSocial operation latency below 50 ms at the 99.9th percentile, and useful throughput for the evaluated workloads. The design also showed that applications could often avoid slow commits by structuring shared data with csets. (cs.cornell.edu)
Subsequent influence
Later research used PSI as a formal point of comparison. Seeing is Believing analyzed PSI’s relationship to earlier consistency models, concluding that PSI is equivalent to lazy consistency (PL-2+) under the relevant client-observable semantics and showing how PSI can be enforced without requiring the same per-site ordering constraints as the original formulation. (arxiv.org) Automated-analysis research subsequently modeled PSI to detect serializability violations in transactional applications, finding long-fork anomalies in TPC-C under PSI. (arxiv.org)