  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.
