2015/09/25 by Robert Escriva, Escriva, Robert, Bernard Wong +3
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1509.07815
openalex publication_date 2015/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Traditional NoSQL systems scale by sharding data across multiple servers and by performing each operation on a small number of servers. Because transactions on multiple keys necessarily require coordination across multiple servers, NoSQL systems often explicitly avoid making transactional guarantees in order to avoid such coordination. Past work on transactional systems control this coordination by either increasing the granularity at which transactions are ordered, sacrificing serializability, or by making clock synchronicity assumptions. This paper presents a novel protocol for providing serializable transactions on top of a sharded data store. Called acyclic transactions, this protocol allows multiple transactions to prepare and commit simultaneously, improving concurrency in the system, while ensuring that no cycles form between concurrently-committing transactions. We have fully implemented acyclic transactions in a document store called Warp. Experiments show that Warp achieves 4 times higher throughput than Sinfonia's mini-transactions on the standard TPC-C benchmark with no aborts. Further, the system achieves 75% of the throughput of the non-transactional key-value store it builds upon.