vault

Calvin and Deterministic Transactions

15 min read

Calvin and Deterministic Transactions

Calvin is a transaction scheduling and replication layer that makes a distributed database atomic and isolated without an agreement protocol at commit time. Described by Thomson, Diamond, Weng, Ren, Shao, and Abadi in Calvin: Fast Distributed Transactions for Partitioned Database Systems (SIGMOD 2012), its central idea belongs to distributed-systems theory rather than to any storage engine: if every replica agrees on the total order of transactions before executing any of them, and if execution is deterministic, then two replicas fed the same ordered input independently reach the same state — so there is never any divergence to reconcile, and therefore nothing to vote on. The one place coordination survives is a replicated input log; once that order is fixed, two-phase commit disappears. The paper’s own words: a “deterministic locking mechanism enables the elimination of distributed commit protocols.” This note treats determinism as a coordination-avoidance technique — where it moves the agreement, why that is cheaper, and what it costs. For the database-engine view of the same system — the lock manager, the five execution phases, checkpointing, FaunaDB — see the sibling Deterministic Databases and Calvin; this note deliberately does not re-derive those.

Mental Model — Agree the Order, Not the Outcome

Every classical distributed-transaction protocol executes first and then pays to agree on the result. In a System R*-style database, participants run their local work, then run 2PC: each votes, and only a unanimous “yes” commits. The vote exists because a participant might have failed, or hit a constraint, or deadlocked — the coordinator cannot know the outcome until it asks. Crucially, isolation forces every participant to hold its locks for the entire duration of that vote, so the commit protocol sits inside the transaction’s lock-holding window.

Calvin inverts the sequence. It performs the agreement first — pinning down a single global order of transactions in a replicated log — and only then executes. Because the order is already fixed and execution is deterministic, the outcome is a foregone conclusion the moment the order is agreed. No participant ever asks another “did you commit?”, because a correctly functioning replica cannot reach a different answer.

flowchart LR
  subgraph CLASSIC["Classic 2PC: agree the OUTCOME, after execution"]
    A1["execute<br/>(hold locks)"] --> A2["PREPARE<br/>vote yes/no<br/>(still hold locks)"] --> A3["COMMIT<br/>(release locks)"]
  end
  subgraph CALVIN["Calvin: agree the ORDER, before execution"]
    B1["sequence<br/>replicate INPUT log<br/>(no locks yet)"] --> B2["acquire locks<br/>in sequenced order"] --> B3["execute<br/>deterministically<br/>→ commit, no vote"]
  end

The two protocols place their one unavoidable round of agreement at opposite ends of the transaction. What it shows: 2PC’s agreement (green box A2) lands in the middle of the lock-holding window, so every round-trip of the vote extends the time locks are held. Calvin’s agreement (B1) happens on the inputs, before any lock is taken, so it never sits inside the lock window at all. The insight to take: determinism does not make agreement free — it relocates it out of the transaction’s “contention footprint,” which is the part of agreement that actually throttles throughput.

The Two Reasons a Transaction Aborts — and Why Only One Needs a Vote

The theoretical core of Calvin is a precise decomposition of why an atomic-commit protocol is needed at all. Abadi (2019) sharpens the paper’s argument: in a sharded system, 2PC exists to resolve two entirely different kinds of would-be abort, and only one of them genuinely requires the participants to talk.

  • Deterministic aborts are dictated by the transaction logic and the data — for example, “abort if this order would drive inventory below zero.” Every node that can see the relevant data reaches the same verdict independently. There is no disagreement to resolve; each node can evaluate the condition and act on it. Calvin turns such logic into a one-way message: a node “waits for a one-way message from each node that could potentially deterministically abort,” then commits once those arrive — a conditional, not a negotiation.
  • Nondeterministic aborts are caused by events outside the transaction’s logic — a node crashes mid-transaction, a lock manager deadlocks, a disk fails. These are the real reason 2PC exists: one participant might be unable to complete while others can, so the group must agree to roll everyone back.

The paper’s key observation is that a nondeterministic event need not force an abort if a live replica is running the identical plan in parallel. When a node fails, “it can recover from a replica that had been executing the same plan,” or replay the planned history for that node; other nodes that needed data from the failed node can request it from the replica instead of waiting. In the words of the paper, “there is no fundamental reason that a transaction must abort as a result of any nondeterministic event.” Remove that reason, and the “primary justification for an agreement protocol at the end of distributed transactions” — checking for a failure that could force an abort — is gone.

Determinism is what makes the surviving replica a valid stand-in. If replicas could process the same input in different equivalent serial orders (because of thread scheduling, message interleaving, or lock-acquisition races), their states would diverge and a replica could not transparently replace a failed peer. So Calvin enforces that all nondeterminism is squeezed out: given the same ordered input, every replica produces the same sequence of states. That is exactly the state-machine-replication contract applied to whole transactions — and it is why replicating the input log is sufficient.

"Input, not effects" is the load-bearing distinction

Megastore and Spinnaker also replicate synchronously via Paxos, but they replicate transactional effects — the writes a transaction produced. Calvin replicates the unexecuted transaction requests and re-derives the effects deterministically on each replica. The paper puts it plainly: they “must use Paxos to replicate transactional effects, whereas Calvin only has to use Paxos to replicate transactional inputs.” Replicating inputs is cheaper (a transaction request is smaller than its write-set for many workloads) and, more importantly, it is what lets a replica complete a transaction a failed peer started, rather than merely inheriting its already-computed writes.

The Sequencing Layer — Where the One Round of Agreement Lives

Calvin still needs consensus; it just confines it to a single, contention-free place. Time is divided into fixed 10-millisecond epochs. During an epoch every sequencer node collects the client transaction requests that arrive at it; at the epoch boundary those requests are compiled into a batch, and that batch is what gets replicated. Sequencers are grouped into replication groups — all replicas of a given partition — and Calvin offers two ways to replicate the batch:

  • Asynchronous replication. One replica is the master; its sequencers forward each batch to the slave sequencers after compiling it. This gives very low latency before execution can begin at the master, at the cost of complex failover (on master failure, the group must agree which batch was the last valid one).
  • Paxos-based synchronous replication. All sequencers in a replication group run Paxos to agree on the combined batch for each epoch (the implementation uses ZooKeeper). This is the strongly-consistent mode, including across geographically distant replicas.

The decisive point for coordination theory is the paper’s measured claim that throughput is identical under both modes. Synchronous replication adds latency equal to the inter-replica round-trip — “this is intrinsically a latency cost only, and need not necessarily affect contention or throughput” — because the Paxos round happens before locks are acquired. A batch waits out one wide-area round-trip to be agreed, but no transaction is holding any lock while it waits. This is the whole trick stated as a measurement: consensus moved out of the contention footprint is a latency tax, not a throughput tax. Contrast that with 2PC, whose every message is inside the lock window and therefore does cap throughput (see the model below).

Because the sequencing layer is itself partitioned across every machine and replicated across every replica, it is not a single point of failure — a limitation that sank earlier deterministic-database prototypes built around a single-node “echo server” sequencer.

Determinism Also Kills Deadlock — Another Source of Aborts

Agreeing the order removes the commit protocol; deterministic locking removes a second, subtler source of nondeterministic aborts: deadlock. Distributed pessimistic locking normally admits distributed deadlock, whose detection-and-rollback aborts transactions nondeterministically (which node’s transaction gets killed depends on timing). Calvin’s scheduler forbids this by construction. Its lock manager resembles strict two-phase locking with two extra invariants, both keyed to the sequenced order:

  1. For any two transactions A and B that both need an exclusive lock on a local record, if A precedes B in the sequence then A must request its lock before B does. Calvin realizes this by serializing all lock requests through a single thread that scans the global order and requests every lock a transaction will ever need, in order.
  2. The lock manager grants each lock strictly in request order — B cannot acquire the record until A has acquired it, run to completion, and released it.

Requesting all of a transaction’s locks up front, in a globally consistent order, means the classic circular-wait condition for deadlock can never form. No deadlock means no deadlock-induced aborts means no nondeterminism from that quarter. The cost is the precondition that makes invariant 1 possible: every transaction must declare its full read and write set in advance, before it is sequenced — because you cannot pre-order lock requests you do not yet know about.

The Precondition and Its Escape Hatch: Known Read/Write Sets and OLLP

The read/write-set requirement is the sharpest edge of the whole approach and the natural first objection to it. Many transactions are dependent: their access set is not known until they read something — “update the row whose secondary-index entry equals X” cannot name its target key until the index is consulted.

Calvin’s answer is Optimistic Lock Location Prediction (OLLP). A dependent transaction is preceded by a cheap, low-isolation, unreplicated, read-only reconnaissance query that performs exactly the reads needed to discover the transaction’s real read/write set. The actual transaction is then submitted to the sequencer annotated with that predicted set. Because the underlying data may have changed between the reconnaissance and the real execution, the predicted set is re-validated deterministically at execution time; if it is stale, the transaction is deterministically restarted (re-reconnoitred and re-sequenced). The scheme is optimistic precisely because it bets the access set is stable — which, the paper notes, holds for common cases like secondary-index lookups on rarely-updated fields (a TPC-C Payment transaction never needs a restart because it depends on an index the benchmark never modifies). The mechanical detail of OLLP lives in Deterministic Databases and Calvin; the theoretical point here is that determinism does not forbid dependent transactions — it pushes their discovery into a coordination-free pre-phase and pays for staleness with a deterministic retry, never with an abort that other nodes must agree to.

Why This Scales: The Contention Footprint and the 2PC Ceiling

Calvin names the quantity it optimizes: a transaction’s contention footprint is “the total duration that a transaction holds its locks — which includes the duration of any required commit protocol.” Throughput under contention is governed by this footprint, because the number of transactions that can run concurrently on a hot record is bounded by how fast each releases its lock. The paper formalizes the ceiling 2PC imposes. Under a contention index C (the fraction of hot records each transaction touches, so at most 1/C transactions can run concurrently), a system that runs two-phase commit inside the lock window can never exceed

                1
   throughput ≤ ─────────      (transactions per second)
              C · D_2PC

where D_2PC is the duration of the commit protocol — walked symbol by symbol: C fixes the maximum concurrency 1/C; each of those concurrent slots turns over once every D_2PC seconds because a lock is held for the whole protocol; multiply and invert. With realistic intra-datacenter round-trips the paper estimates locks are held roughly 8 ms per distributed transaction under 2PC. Calvin’s footprint excludes the agreement entirely, so its D is just local execution — which is why it sustained roughly half a million TPC-C New-Order transactions per second on 100 commodity EC2 nodes, immediately competitive with the contemporary TPC-C world-record of 504,161 New-Order transactions/second that Oracle achieved on far higher-end hardware. The scaling curve is near-linear once past a handful of nodes; residual degradation comes from execution progress skew (a straggler replica or partition holds back conflicting work elsewhere in the sequence), not from the commit protocol, which no longer exists.

A Note on “High Availability” — Not the CAP Meaning

Calvin’s abstract advertises “high availability,” and this is a genuine trap for a distributed-systems reader. The paper is explicit in a footnote: it uses “high availability” in the database sense — the system can fail over to an active replica with no downtime — not the CAP sense, which demands that even minority replicas keep serving during a partition. In the synchronous (Paxos) mode Calvin is a EC system: it needs a quorum of the sequencing group to make progress, so a partitioned minority stalls. Determinism buys coordination avoidance for the commit, and hot-failover availability, but it does not repeal CAP — the input log still requires consensus, and consensus still cannot be both consistent and available under partition. This is the exact axis on which the sibling Highly Available Transactions pushes the other way: HAT keeps availability by giving up serializability, whereas Calvin keeps serializability and accepts CAP-consistency’s unavailability.

Where Calvin Sits Among the Alternatives

  • Two-Phase Commit agrees the outcome after execution; simple and general, but its vote is inside the lock window and it blocks if the coordinator dies. Calvin needs neither vote nor coordinator, but demands pre-declared access sets and deterministic logic.
  • Spanner Distributed Transactions keeps 2PC but runs each participant as a Paxos group and uses TrueTime commit-wait for external consistency; it supports arbitrary interactive transactions (no pre-declared sets) at the cost of a real commit protocol plus a bounded clock-uncertainty wait. Calvin trades interactivity for the elimination of that protocol.
  • Percolator layers client-driven snapshot-isolation transactions on Bigtable via a timestamp oracle; it optimizes for throughput of incremental batch work, tolerating high per-transaction latency — the opposite trade-off from Calvin’s low-footprint locking.
  • Serial execution (H-Store / VoltDB) also fixes an order in advance but runs transactions one-at-a-time per partition and still needs 2PC for multi-partition transactions because order adherence is not strictly enforced under failure. Calvin keeps concurrent execution (equivalent to the chosen serial order) while enforcing the order strictly enough to drop 2PC.
  • Hyder composes a global log of transactions’ after-effects validated by an optimistic “meld”; Calvin’s log holds unexecuted requests, and OLLP is the conceptual analogue of Hyder’s optimistic validation on the input side.

The general lesson generalizes past databases: determinism is a way to substitute agreement-in-advance for agreement-at-commit. Anywhere replicas must stay identical, if you can agree an input order once and make processing deterministic, you convert an expensive per-operation vote into one cheap ordering decision plus independent, coordination-free replay — the same move Raft and the replicated log make for a state machine, here applied to transactions.

Production Notes and Lineage

Calvin is the direct descendant of Thomson and Abadi’s The Case for Determinism in Database Systems (VLDB 2010), which argued the thesis for in-memory databases; Calvin’s contribution was making it work with disk-based storage (via prefetch-before-lock), horizontal scale, and no single-point-of-failure sequencer. Abadi’s later manifesto, It’s Time to Move on from Two Phase Commit (2019), reframes the whole line of work as removing 2PC’s two pathologies — the blocking problem (workers cannot decide among themselves when the coordinator dies) and the cloggage problem (workers hold resources until mid-phase-two) — by removing system-induced aborts so there is nothing left to negotiate.

Uncertain

Verify: the claim that FaunaDB implements the Calvin protocol in production. Reason: widely repeated (and asserted in the sibling Deterministic Databases and Calvin note) but I did not fetch a FaunaDB primary source this session; the Calvin project page consulted did not mention Fauna. To resolve: consult current FaunaDB architecture documentation or a Fauna engineering write-up. #uncertain

See Also

Graph View