Introduction

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)O(n) round-trips per transaction to zero.

Try It

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.

<!-- Calvin demo: sequencer panel + two replicas that step through the same ordered log -->
<div class="calvin-root">
  <div class="sequencer-panel">
    <div class="panel-title">Sequencer</div>
    <div class="panel-subtitle">assigns a global order — replicas replay this log</div>
    <div class="tx-controls">
      <select id="tx-type">
        <option value="deposit">Deposit</option>
        <option value="withdraw">Withdraw</option>
        <option value="transfer">Transfer out</option>
      </select>
      <input id="tx-amount" type="number" min="1" max="200" value="50" class="amount-input" aria-label="transaction amount">
      <button id="btn-add" type="button">Add Transaction</button>
    </div>
    <div class="seq-log-label">Ordered log</div>
    <div id="seq-log" class="seq-log" aria-label="sequencer transaction log"></div>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="replicas-panel">
    <div class="replica-box" id="replica-a">
      <div class="panel-title">Replica A</div>
      <div class="balance-display">
        <span class="balance-label">Balance</span>
        <span class="balance-value" id="bal-a">$1000</span>
      </div>
      <div class="applied-label">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>Step ▶</button>
    </div>
    <div class="replica-box" id="replica-b">
      <div class="panel-title">Replica B</div>
      <div class="balance-display">
        <span class="balance-label">Balance</span>
        <span class="balance-value" id="bal-b">$1000</span>
      </div>
      <div class="applied-label">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>Step ▶</button>
    </div>
  </div>
  <div id="status-bar" class="status-bar"></div>
</div>

/* Calvin demo styles */
* { 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; } }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Calvin Deterministic Database demo
// Sequencer assigns a global sequence number to every transaction. Replicas replay the log in order — no locks, no commit protocol.

const INITIAL_BALANCE = 1000; // starting balance for both replicas

// global state
let log = [];         // sequenced transaction log
let cursorA = 0;      // next entry for Replica A to apply
let cursorB = 0;      // next entry for Replica B to apply
let balA = INITIAL_BALANCE;
let balB = INITIAL_BALANCE;

// human-readable description of a transaction
function txDesc(tx) {
  if (tx.type === 'deposit')  return fmt('Deposit $%amount%', { amount: tx.amount });
  if (tx.type === 'withdraw') return fmt('Withdraw $%amount%', { amount: tx.amount });
  if (tx.type === 'transfer') return fmt('Transfer out $%amount%', { amount: tx.amount });
  return tx.type;
}

// apply one transaction to a balance and return the new balance
function applyTx(tx, balance) {
  if (tx.type === 'deposit')  return balance + tx.amount;
  if (tx.type === 'withdraw') return Math.max(0, balance - tx.amount);
  if (tx.type === 'transfer') return Math.max(0, balance - tx.amount);
  return balance;
}

function fmtBal(n) { return '


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.

 + n; }

function updateTotals() {
  document.getElementById('total-txs').textContent   = log.length;
  document.getElementById('total-txs-b').textContent = log.length;
}

function renderLog() {
  const container = document.getElementById('seq-log');
  container.innerHTML = '';
  log.forEach((tx, i) => {
    const div = document.createElement('div');
    const appliedA = i < cursorA;
    const appliedB = i < cursorB;
    let cls = 'log-entry';
    if (appliedA && appliedB) cls += ' applied-both';
    else if (appliedA)        cls += ' applied-a';
    else if (appliedB)        cls += ' applied-b';
    div.className = cls;
    div.innerHTML = `<span class="seq-num">#${tx.seq}</span><span class="tx-desc">${txDesc(tx)}</span>`;
    container.appendChild(div);
  });
  // keep the latest entry visible
  container.scrollTop = container.scrollHeight;
}

function refreshBalances() {
  const elA = document.getElementById('bal-a');
  const elB = document.getElementById('bal-b');
  elA.textContent = fmtBal(balA);
  elB.textContent = fmtBal(balB);
  elA.className = 'balance-value updated';
  elB.className = 'balance-value updated';
  setTimeout(() => { elA.className='balance-value'; elB.className='balance-value'; }, 400);
  document.getElementById('applied-a').textContent = cursorA;
  document.getElementById('applied-b').textContent = cursorB;
}

function updateButtons() {
  document.getElementById('btn-step-a').disabled = cursorA >= log.length;
  document.getElementById('btn-step-b').disabled = cursorB >= log.length;
}

function setStatus(msg, cls) {
  const el = document.getElementById('status-bar');
  el.textContent = msg;
  el.className = 'status-bar ' + (cls || '');
}

function checkSync() {
  if (cursorA === log.length && cursorB === log.length && log.length > 0) {
    if (balA === balB) setStatus('✓ Both replicas applied all transactions — identical balance!', '');
    else setStatus('✗ Balances differ — this should never happen in Calvin.', 'warn'); // should never happen — determinism guarantees equal outcomes
  } else if (cursorA !== cursorB) {
    setStatus('Replicas are at different points in the log — step both to sync.', 'info');
  } else {
    setStatus('', '');
  }
}

// add a new transaction to the sequencer log
document.getElementById('btn-add').addEventListener('click', () => {
  const type   = document.getElementById('tx-type').value;
  const amount = parseInt(document.getElementById('tx-amount').value, 10) || 50;
  const tx = { seq: log.length + 1, type, amount };
  log.push(tx);
  updateTotals();
  renderLog();
  updateButtons();
  setStatus(fmt('Sequencer stamped #%seq% — %txDesc% — step replicas to apply it.', { seq: tx.seq, txDesc: txDesc(tx) }), 'info');
});

// advance Replica A by one step
document.getElementById('btn-step-a').addEventListener('click', () => {
  if (cursorA >= log.length) return;
  balA = applyTx(log[cursorA], balA);
  cursorA++;
  refreshBalances();
  renderLog();
  updateButtons();
  checkSync();
});

// advance Replica B by one step
document.getElementById('btn-step-b').addEventListener('click', () => {
  if (cursorB >= log.length) return;
  balB = applyTx(log[cursorB], balB);
  cursorB++;
  refreshBalances();
  renderLog();
  updateButtons();
  checkSync();
});

// reset everything to initial state
document.getElementById('btn-reset').addEventListener('click', () => {
  log = []; cursorA = 0; cursorB = 0;
  balA = INITIAL_BALANCE; balB = INITIAL_BALANCE;
  updateTotals();
  renderLog();
  refreshBalances();
  updateButtons();
  setStatus('', '');
});

// initial render
updateTotals();
renderLog();
refreshBalances();
updateButtons();
Result
Console

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.

The Real Complexity

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)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 ∼\sim500k 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/calvin-deterministic-db/Content licensed under CC BY-NC 4.0.