paper

Calvin: Fast Distributed Transactions for Partitioned Database Systems

  • Authors:
Read the paper

📜 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.

✨ Summary

Main idea

Calvin is a transaction scheduling and replication layer that can be placed above a basic CRUD-oriented storage engine. Its central design choice is to establish a global order for transaction inputs before transaction execution begins. Nodes and replicas then execute the same ordered input deterministically, allowing them to reach equivalent database states without replicating every physical data change.

Technical contributions

  • Deterministic transaction ordering: A distributed sequencing layer collects requests into short epochs and constructs a globally agreed transaction order. The sequencing layer is partitioned and replicated, avoiding the single-point-of-failure and scalability limitations of a centralized sequencer.
  • Deterministic locking: Transactions declare their complete read and write sets in advance. Locks are requested and granted according to the predetermined serial order, preventing distributed deadlocks and allowing Calvin to avoid holding locks during a traditional two-phase commit protocol.
  • Distributed transaction execution: Transactions may span multiple partitions. Local reads are performed in parallel, remote read results are forwarded between participating nodes, and writes are applied at the relevant partitions. Only nodes that modify data need to execute the transaction logic fully.
  • Replication of inputs rather than effects: As replicas receive the same transaction inputs and follow the same deterministic execution rules, they can independently reproduce the same logical database history. Calvin supports asynchronous replication as well as Paxos-based synchronous replication, including geographically separated replicas. The replication agreement affects latency but does not extend the transaction’s lock-holding period.
  • Disk-based storage: Calvin moves disk work before lock acquisition. The sequencer predicts storage latency, delays scheduling when necessary, and prefetches cold records so that execution generally operates on memory-resident data. This preserves the principal contention advantage of deterministic scheduling, although inaccurate latency prediction and limited disk bandwidth remain practical constraints.
  • Checkpointing and recovery: Because transaction inputs provide a logical recovery history, Calvin does not require physical REDO logging. Periodic snapshots bound replay work. The paper evaluates synchronous snapshots, an asynchronous modified Zig-Zag scheme, and snapshotting over multiversion storage engines.

Limitations and trade-offs

Calvin requires transaction read and write sets to be known before execution. Transactions whose access pattern depends on earlier reads use Optimistic Lock Location Prediction: a preliminary reconnaissance query predicts the access set, after which the actual transaction validates that prediction and deterministically restarts if necessary. The architecture also has difficulty with phantom protection and key-range locking because the transactional layer is deliberately separated from physical storage structures. Additional overhead arises from remote-read processing, context switching, and execution-progress skew among nodes. These costs become more visible as the number of machines and the workload’s contention increase.

Evaluation

The prototype was evaluated on commodity Amazon EC2 instances using TPC-C New Order transactions and a configurable microbenchmark. In the reported TPC-C experiment, approximately 10% of transactions were deliberately made multipartition. Throughput reached about 5,000 transactions per second per node on larger deployments and nearly 500,000 transactions per second on a 100-node cluster. The microbenchmark showed near-linear aggregate scaling under low contention, while high contention and multipartition execution produced gradual per-node throughput degradation. Compared with a modeled System R*-style design using two-phase commit, Calvin showed substantially lower slowdown for highly contended multipartition workloads because it removed the commit protocol from the transaction’s contention footprint.

Influence on subsequent research and industry

The deterministic ordering approach became a reference point for later distributed transaction research. The authors’ subsequent research program produced systems including SLOG, which investigates serializable, low-latency, geo-replicated transactions and is listed as a later publication in the Calvin research lineage. (dslam.cs.umd.edu)

The design also influenced commercial database systems. Fauna states that its distributed transaction engine was inspired by Calvin and uses preordering, replicated logs, and deterministic processing to provide strongly consistent transactions across geographically distributed regions. (fauna.com) CockroachDB’s SIGMOD paper cites Calvin among systems using strict serializability-oriented distributed transaction designs, particularly for partitionable workloads. (cockroachlabs.com) Later research on deterministic concurrency control and geo-distributed transaction processing continues to describe Calvin’s preordering and deterministic lock acquisition as a foundational approach. (pmc.ncbi.nlm.nih.gov)