Calvin: Fast Distributed Transactions for Partitioned Database Systems, 2012

http://cs.yale.edu/homes/thomson/publications/calvin-sigmod12.pdf

Underlies FaunaDB.

ABSTRACT

Many distributed storage systems achieve high data access throughput via partitioning and replication, each system with its own advantages and tradeoffs. In order to achieve high scalability, however, today’s systems generally reduce transactional support, disallowing single transactions from spanning multiple partitions. Calvin is a practical transaction scheduling and data replication layer that uses a deterministic ordering guarantee to significantly reduce the normally prohibitive contention costs associated with distributed transactions. Unlike previous deterministic database system prototypes, Calvin supports disk-based storage, scales near-linearly on a cluster of commodity machines, and has no single point of failure. By replicating transaction inputs rather than effects, Calvin is also able to support multiple consistency levels—including Paxos-based strong consistency across geographically distant replicas—at no cost to transactional throughput.

Categories and Subject Descriptors

C.2.4 [Distributed Systems]: Distributed databases;
H.2.4 [Database Management]: Systems—concurrency, distributed
databases, transaction processing

General Terms

Algorithms, Design, Performance, Reliability

Keywords

determinism, distributed database systems, replication, transaction
processing