Calvin, order first, execute later.
Two-phase commit, the long-time default for distributed transactions, blocks if the coordinator fails. Calvin proposes a radically different approach: agree on the order of all transactions globally before any of them execute. Once ordered, each transaction can be executed deterministically on each shard — no coordinator, no commit phase, no blocking. The paper is the cleanest articulation of "deterministic concurrency" you'll find, and the protocol underneath FaunaDB.
TL;DR
Conventional distributed transactions execute concurrently and use 2PC to reach consensus on whether to commit. Calvin inverts this: all transactions are submitted to a Paxos-replicated sequencer that assigns each a global order. Each shard then executes transactions in that order. Because the order is deterministic and each shard knows the full read/write set ahead of execution, there's no need for distributed locking or 2PC at execution time — replicas execute identical sequences and reach identical states. The trade-off: transactions must declare their read/write set in advance, which excludes "interactive" transactions that decide what to read based on previous reads.
The problem
Distributed transactions over partitioned data had traditionally meant Two-Phase Commit (2PC): execute the transaction's operations on each participating shard, then run a vote-and-commit protocol. The protocol is correct, but it has two practical problems. First, the coordinator is a blocking single point of failure — if it crashes between vote and commit, participants hold locks until it recovers. Second, the latency cost is significant: every commit requires at least one extra round-trip for the vote-commit messages.
By 2010 distributed databases like Cassandra had given up on cross-shard transactions entirely; Spanner/F1 had accepted the 2PC cost. The Calvin team asked: is there a protocol that gives you cross-shard ACID without 2PC at all?
The key idea
The insight is that if you decide on the global order before execution, execution can be deterministic. A Paxos-replicated sequencer accepts incoming transactions and assigns them a sequence number. The sequence is the canonical order. Each shard then replays the sequence: for each transaction, it executes the operations that touch its data, in order. Across all replicas of a shard, the executions are identical — because they apply identical transactions in identical order to identical starting states.
There's no 2PC because there's nothing to vote on. The order is already decided. The only "failure" is if a transaction can't complete — say, because a participant is unreachable — and Calvin handles that by aborting the transaction in the canonical sequence (so every replica sees the abort at the same logical step).
The catch is that the read/write set of each transaction must be known in advance. Calvin can't handle transactions like "SELECT x FROM t WHERE k=1; if x > 0 then UPDATE u SET y = 1" because the read in the first statement determines whether the write in the second statement happens. Calvin requires the application to either declare the full set up front (sometimes via an optimistic execution that runs the transaction without the locks and provides the set) or to restructure the transaction.
Contributions
Deterministic transaction scheduling. Order first, execute later. No 2PC, no coordinator, no blocking. The single biggest contribution.
Active replication without quorum reads. Because every replica executes the same deterministic sequence, every replica's state is identical at every logical step. You can read from any replica without a quorum — useful for cross-region reads.
Latency vs throughput trade-off. Calvin trades higher latency per transaction (Paxos round-trip in the sequencer) for higher cluster throughput (no distributed locks, no 2PC). The paper shows Calvin handles 500K TPC-C transactions/second on 100 nodes — competitive with the best 2PC-based systems at the time.
OLLP. The optimistic-locking-with-validation pattern for handling interactive transactions. Influential in FoundationDB and FaunaDB.
Criticisms and limitations
Static read/write sets. The requirement that transactions declare their full read/write set in advance is restrictive. Real applications often use interactive transactions that depend on previous reads. Calvin's OLLP mitigation works but adds complexity and a re-execution risk.
Sequencer is the bottleneck. Every transaction goes through the global sequencer. As cluster size grows, the sequencer's throughput becomes the limit. The paper proposes sharded sequencers, but sharding the sequencer adds coordination overhead that partially negates the no-2PC benefit.
Workload assumption. Calvin's wins are biggest on read-heavy workloads with predictable write sets. For write-heavy workloads with high contention, the sequence-then-execute model can serialise contention that 2PC-style optimistic concurrency would handle in parallel.
Limited production deployment. Compared to Spanner/F1, Calvin has had far less production adoption. FaunaDB is the main commercial descendant; few others have built on it.
Where it shows up today
FaunaDB — the most direct commercial descendant. Implements Calvin's deterministic ordering on top of an internal log. Marketed as a serverless distributed database with strict serializability.
Aerospike — uses a similar order-first approach for cross-shard transactions, though without the formal Calvin protocol.
Redpanda Transform — uses deterministic execution of stream transformations, conceptually similar to Calvin's sequence-then-execute.
Microsoft's research database "Hyper" and Yale's research database "Caracal" both build on Calvin's deterministic scheduling.
Conceptually, blockchain consensus protocols (Bitcoin, Ethereum, Solana) all use Calvin-style "order first, execute later" — the consensus layer orders transactions; the execution layer replays them deterministically. The pattern is identical.
Follow-up reading
- Spanner: Google's Globally Distributed Database — Corbett et al · 2012 · OSDI. The contrasting design: 2PC over Paxos with TrueTime. Annotated.
- CalvinFS: Consistent WAN Replication and Scalable Metadata Management for Distributed File Systems — Thomson et al · 2015 · FAST. Calvin's authors applied to a distributed file system. Same deterministic-ordering principle.
- Architecture of a Distributed SQL Database — Abadi et al · 2017 · blog. Fauna's explanation of how they productised Calvin.
- FoundationDB: A Distributed Unbundled Transactional Key-Value Store — Zhou et al · 2021 · SIGMOD. A different take on deterministic transactions, with OLLP-style optimistic concurrency.
- Building on Quicksand — Helland · 2009 · CIDR. Why deterministic execution is harder than it sounds. Annotated.