Calvin: Deterministic Transactions

Every distributed database faces the same embarrassing conversation: two replicas both think they can modify the same record, so they start a choreographed argument — locks, prepare messages, abort votes — just to decide who goes first. In large clusters this argument eats most of the time that could be spent doing actual work.

Calvin (Thomson, Diamond, and Weihl, SIGMOD 2012) bets that the argument is unnecessary. Its core idea is startlingly simple: decide the global order of transactions before any of them touch a single byte of data. A component called the sequencer collects incoming transactions and stamps a global sequence number on each one. Every replica receives the same stamped log and executes each transaction in that exact order — no locks needed, no votes, no coordinator.

The result is that every replica is mathematically guaranteed to end in identical state after any prefix of the log, a property called deterministic execution. Coordination cost shrinks from $O(n)$ round-trips per transaction to zero.

Below is a tiny Calvin cluster: a sequencer that stamps every transaction with a sequence number, and two replicas that replay the log independently. Click Add Transaction to submit a new operation, or step each replica forward one entry at a time.

<!-- {{c_html_intro}} -->
<div class="calvin-root">
  <div class="sequencer-panel">
    <div class="panel-title">{{lbl_sequencer}}</div>
    <div class="panel-subtitle">{{lbl_seq_sub}}</div>
    <div class="tx-controls">
      <select id="tx-type">
        <option value="deposit">{{op_deposit}}</option>
        <option value="withdraw">{{op_withdraw}}</option>
        <option value="transfer">{{op_transfer}}</option>
      </select>
      <input id="tx-amount" type="number" min="1" max="200" value="50" class="amount-input" aria-label="{{aria_amount}}">
      <button id="btn-add" type="button">{{btn_add}}</button>
    </div>
    <div class="seq-log-label">{{lbl_log}}</div>
    <div id="seq-log" class="seq-log" aria-label="{{aria_seq_log}}"></div>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="replicas-panel">
    <div class="replica-box" id="replica-a">
      <div class="panel-title">{{lbl_replica_a}}</div>
      <div class="balance-display">
        <span class="balance-label">{{lbl_balance}}</span>
        <span class="balance-value" id="bal-a">$1000</span>
      </div>
      <div class="applied-label">{{lbl_applied}} <span id="applied-a">0</span> / <span id="total-txs">0</span></div>
      <button id="btn-step-a" type="button" class="step-btn" disabled>{{btn_step}}</button>
    </div>
    <div class="replica-box" id="replica-b">
      <div class="panel-title">{{lbl_replica_b}}</div>
      <div class="balance-display">
        <span class="balance-label">{{lbl_balance}}</span>
        <span class="balance-value" id="bal-b">$1000</span>
      </div>
      <div class="applied-label">{{lbl_applied}} <span id="applied-b">0</span> / <span id="total-txs-b">0</span></div>
      <button id="btn-step-b" type="button" class="step-btn" disabled>{{btn_step}}</button>
    </div>
  </div>
  <div id="status-bar" class="status-bar"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; background: transparent; }
.calvin-root { display: flex; flex-direction: column; gap: .8rem; padding: .6rem; }
.sequencer-panel, .replica-box {
  background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 10px; padding: .8rem 1rem;
}
.replicas-panel { display: flex; gap: .8rem; }
.replica-box { flex: 1; }
.panel-title { font-weight: 700; font-size: 1rem; margin-bottom: .1rem; color: #1d3557; }
.panel-subtitle { font-size: .8rem; color: #556; margin-bottom: .5rem; }
.tx-controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; align-items: center; }
select, .amount-input { font-size: .9rem; padding: .35rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; background: #fff; }
.amount-input { width: 70px; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.seq-log-label { font-size: .78rem; color: #556; font-weight: 600; margin: .3rem 0 .2rem; }
.seq-log { max-height: 130px; overflow-y: auto; display: flex; flex-direction: column; gap: .25rem; }
.log-entry { font-size: .82rem; background: #fff; border: 1px solid #d0dae3; border-radius: 6px;
             padding: .25rem .55rem; display: flex; gap: .5rem; align-items: center; }
.log-entry .seq-num { font-weight: 700; color: #1d3557; min-width: 22px; }
.log-entry .tx-desc { color: #333; flex: 1; }
.log-entry.applied-a { border-left: 3px solid #2a9d5c; }
.log-entry.applied-b { border-left: 3px solid #e07b28; }
.log-entry.applied-both { border-left: 3px solid #7c3aed; }
.balance-display { display: flex; align-items: baseline; gap: .4rem; margin: .4rem 0 .2rem; }
.balance-label { font-size: .82rem; color: #556; }
.balance-value { font-size: 1.5rem; font-weight: 700; color: #1d3557; }
.balance-value.updated { animation: pop .35s ease; }
@keyframes pop { 0%{transform:scale(1.18)} 100%{transform:scale(1)} }
.applied-label { font-size: .8rem; color: #556; margin-bottom: .4rem; }
.step-btn { width: 100%; }
.status-bar { font-size: .9rem; font-weight: 600; min-height: 1.3em; color: #0a7d33; }
.status-bar.warn { color: #b45309; }
.status-bar.info { color: #1d3557; }
@media (max-width: 480px) { .replicas-panel { flex-direction: column; } }

// Code not found

Notice what never appears: there is no lock request, no "prepare" message, no abort. Both replicas simply execute the log in order and always end at the same balance. Add transactions in any order — the sequencer fixes the sequence, and the replicas converge regardless.

Why does pre-ordering work, and what does Calvin actually have to give up?

Traditional approach — coordinate during execution. Two-phase locking (2PL) acquires locks as transactions run; two-phase commit (2PC) synchronises replicas at the end. Both require $O(n)$ round-trips that block forward progress.

Calvin's approach — coordinate before execution. The sequencer batches incoming requests into fixed-length epochs (typically 10 ms). All replicas receive the batch simultaneously. Because the input is identical and the execution engine is deterministic, every replica independently produces the same output state — a property that follows directly from the theory of deterministic state machines.

The catch: read-write sets must be declared up front. Calvin needs to know which records a transaction will touch before it runs, so it can assign locks in a deterministic order and avoid deadlock. For complex transactions that discover their read set dynamically (e.g., "read record A, then read whichever record A points to"), Calvin uses optimistic lock location prediction (OLLP): a quick pre-execution read that declares the likely set, with a retry on misprediction.

Throughput and latency. Because replicas never block each other, throughput scales linearly with shard count. Latency equals one sequencer epoch plus local execution time — typically 10–50 ms, competitive with or better than 2PC-based systems under high contention.

Calvin is solved and deployed: the original SIGMOD 2012 paper showed $\sim$500k transactions per second on a 3-node cluster with strict serializability, outperforming systems that rely on 2PC under contention. Successor systems (FaunaDB, CockroachDB's deterministic mode, and others) adopted its ideas.

Deterministic execution is not just a research curiosity — it reshapes how engineers build reliable distributed systems:

• NewSQL databases: FaunaDB (now Fauna) was built directly on Calvin's design, offering globally consistent transactions without distributed locking. CockroachDB's closed-loop replication borrows deterministic ordering ideas.
• Financial systems: ledgers and payment rails need strong serializability under heavy contention. Calvin's approach lets a cluster scale horizontally without sacrificing correctness.
• Geo-replication: placing sequencer epochs at the WAN level lets geographically distant replicas stay consistent without per-transaction cross-ocean round-trips.
• Database testing and reproducibility: a deterministic log is also a perfect replay artifact. Any failure can be reproduced exactly by replaying the same epoch sequence on a fresh cluster — a property that traditional locking-based systems cannot offer.

The core insight — separate ordering from execution — echoes through consensus protocols like Raft and Paxos and through deterministic scheduling research in operating systems.

Calvin's insight is almost philosophical: most of the complexity in distributed databases comes not from the work itself, but from letting replicas discover their disagreements mid-flight. Move the agreement to before execution, and the work becomes trivially parallelisable.

A sequencer stamps the log. Every replica reads the same log. Every replica runs the same deterministic engine. The outcome is the same — not by luck, not by coordination, but by mathematical necessity. Locks and commit protocols dissolve, throughput scales linearly, and failures replay perfectly.

It is a reminder that the hardest distributed-systems problems sometimes yield not to cleverer algorithms but to a shift in when the agreement happens.