Warp: Multi-Key Transactions for Key-Value Stores
📜 Abstract
Implementing ACID transactions has been a long-standing challenge for NoSQL systems. Because these systems are based on a sharded architecture, transactions necessarily require coordination across multiple servers. Past work in this space has relied either on heavyweight protocols such as Paxos or clock synchronization for this coordination. This paper presents a novel protocol for coordinating distributed transactions with ACID semantics on top of a sharded data store. Called linear transactions, this protocol achieves scalability by distributing the coordination task to only those servers that hold relevant data for each transaction. It achieves high performance by serializing only those transactions whose concurrent execution could potentially yield a violation of ACID semantics. Finally, it naturally integrates chain-replication and can thus tolerate faults of both clients and servers. We have fully implemented linear transactions in a commercially available data store. Experiments show that the throughput of this system achieves 1-9× more throughput than MongoDB, Cassandra and HyperDex on the Yahoo! Cloud Serving Benchmark, even though none of the latter systems provide transactional guarantees.
✨ Summary
Summary
Warp presents linear transactions, a protocol for providing one-copy-serializable ACID transactions over a sharded key-value store without placing a consensus protocol on the normal data path. Clients optimistically execute reads and buffer writes locally. At commit time, the client constructs a deterministic chain containing the servers responsible for the transaction’s keys. A forward pass validates the read set and detects conflicts; a reverse pass propagates the commit or abort decision and applies writes.
The protocol distinguishes disjoint transactions from overlapping transactions. Disjoint transactions proceed without coordination, while overlapping transactions are ordered only when necessary. Warp propagates happens-before and needs-ordering dependencies through the chain and directs compatible transactions in a way that prevents dependency cycles. Replicas can be inserted into the chain to tolerate failures, while a replicated state machine is used primarily for cluster membership, key-range mappings, and reconfiguration rather than for normal transaction ordering. (code.garrettmills.dev)
The implementation supports rich data types, nested transactions, conditional operations, multiple schemas, and client libraries. The evaluation reports throughput above 50,000 transactions per second across the tested YCSB workloads, low transaction latency, approximately linear scaling as servers are added, and an abort rate below 1% for sufficiently large write-key sets. In the credit-card workload, Warp preserved account invariants that were violated by the non-transactional comparison system. (code.garrettmills.dev)
Documented influence
The protocol was subsequently developed in a revised work, Warp: Lightweight Multi-Key Transactions for Key-Value Stores, which retained the central goal of lightweight serializable transactions over sharded storage while presenting a later protocol formulation and evaluation. (arxiv.org)
The Warp transaction protocol was also reused or adapted in later systems research. The Warp Transactional Filesystem used Warp-related transactional mechanisms to provide transactions spanning multiple files in a distributed filesystem, and the Tyr blob-storage system explicitly describes using the Warp optimistic transaction protocol for distributed blob transactions. (usenix.org) The original work has additionally been cited in subsequent academic writing and patent literature concerning transactional layers over distributed key-value stores. (bholt.org)