Calvin & FaunaDB: Deterministic Transactions
Most distributed databases do transactions the same way. Each participant executes its part, holds locks, and then everyone runs two-phase commit to decide together whether the transaction happened. Spanner, CockroachDB, YugabyteDB, TiDB and classic distributed SQL all follow this pattern in some form. It works, but it is expensive in a specific way: locks are held across network round trips, so the busiest records become bottlenecks.
In 2012, Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao and Daniel Abadi published "Calvin: Fast Distributed Transactions for Partitioned Database Systems" at SIGMOD. Its idea is simple to state and has big consequences:
Agree on the order of transactions first. Then have every node execute them deterministically in that order.
If every replica and every partition processes the same input in the same order with deterministic code, they all reach the same result without talking to each other about commit. There is nothing left for two-phase commit to decide. Consensus moves from the output (did this commit?) to the input (what is the order of requests?).
FaunaDB (later just "Fauna") built a commercial globally distributed database on this idea, changing it in important ways. This page explains Calvin from first principles, works through its mechanisms with examples, states its guarantees and limits precisely, describes FaunaDB's adaptation, and ends with when determinism is the right tool.
Prerequisites on Archon
This page assumes you know two-phase commit and its failure modes — see Distributed Transactions. For isolation levels, see Isolation Levels. For the Spanner side of the comparison, see Spanner and NewSQL.
1. The Problem: What Two-Phase Commit Really Costs
1.1 The setting
Calvin targets partitioned, replicated OLTP databases: data is split across many machines (partitions), and each partition is copied to several replicas, possibly in different data centres. Transactions may touch records on several partitions. The goal is ACID with serializability across partitions, at high throughput, without forcing the application to avoid multi-partition transactions.
1.2 Two costs of a classic distributed transaction
Consider a transfer from account X (on partition 1) to account Y (on partition 2) in a design that uses locking plus two-phase commit, with each partition replicated by Paxos or Raft:
sequenceDiagram
autonumber
participant C as Coordinator
participant P1 as Partition 1 leader
participant P2 as Partition 2 leader
C->>P1: execute debit X, take lock on X
C->>P2: execute credit Y, take lock on Y
P1-->>C: done
P2-->>C: done
C->>P1: PREPARE
C->>P2: PREPARE
Note over P1: Replicate prepare record<br/>to its followers (consensus round)
Note over P2: Replicate prepare record<br/>to its followers (consensus round)
P1-->>C: YES
P2-->>C: YES
Note over C: Replicate the commit decision
C->>P1: COMMIT
C->>P2: COMMIT
Note over P1,P2: Locks on X and Y released only now
The paper names two problems:
-
Contention footprint. Locks on X and Y are held from the moment they are taken until the commit message arrives. That spans several network round trips and several replicated log writes. If replicas are in different regions, that is tens to hundreds of milliseconds. Any other transaction touching X or Y waits that whole time. For hot records — a popular product's inventory count, a warehouse row in TPC-C — throughput collapses. Throughput on a hot record is roughly .
-
Agreement is about the outcome, and it is needed because nodes can fail independently. Two-phase commit exists because a participant might be unable to commit — it crashed, ran out of disk, hit a deadlock and was chosen as the victim. Nobody knows until they ask. So every distributed transaction pays a voting round.
Calvin's authors make a sharp observation about the second point. The reasons a participant votes "no" fall into two groups:
- Nondeterministic reasons: node failure, deadlock victim choice, timeouts, running out of memory. These depend on timing and luck, not on the transaction or the data.
- Deterministic reasons: application logic — "abort if balance < amount", a constraint violation. Any node that sees the same data computes the same answer.
If you can remove the nondeterministic reasons, then every participant can compute the outcome on its own, and no vote is needed. Calvin removes them like this:
- Node failures stop being reasons to abort. A failed node recovers by replaying the replicated input log from a checkpoint, or another replica takes over. Neither changes the outcome.
- Deadlocks cannot happen, because locks are requested in a fixed global order.
- Ordering differences between replicas cannot happen, because everyone uses the same order.
What is left is application logic, which every participant evaluates the same way.
1.3 The deterministic database idea
The idea did not start with Calvin. Thomson and Abadi's earlier VLDB 2010 paper "The Case for Determinism in Database Systems" argued for it. Systems like H-Store and VoltDB used deterministic, serial execution of stored procedures per partition. Calvin's contribution is a complete architecture for partitioned and replicated deterministic transactions, including multi-partition transactions, disk-resident data, and transactions whose read/write sets aren't known in advance.
The core invariant is:
This is the same principle as state machine replication — the idea behind Raft and Paxos logs (see Raft in Plain English). Calvin applies it to a whole partitioned database: one logical log of transactions for all partitions, instead of one log per partition plus a commit protocol to tie them together.
2. Architecture
Calvin is a layer that sits on top of a storage engine. The storage system can be any engine with a basic CRUD interface; Calvin does not need it to support transactions. Calvin has three layers, and every machine runs all three for its partition:
flowchart TB
Cl["Clients submit transactions<br/>(stored procedures + args)"]
subgraph RA["Replica A (e.g. US-East)"]
direction TB
SA1["Sequencer A1"] --> SchA1["Scheduler A1"]
SA2["Sequencer A2"] --> SchA2["Scheduler A2"]
SA1 --> SchA2
SA2 --> SchA1
SchA1 --> StA1[("Storage<br/>partition 1")]
SchA2 --> StA2[("Storage<br/>partition 2")]
end
subgraph RB["Replica B (e.g. EU-West)"]
direction TB
SB1["Sequencer B1"] --> SchB1["Scheduler B1"]
SB2["Sequencer B2"] --> SchB2["Scheduler B2"]
SB1 --> SchB2
SB2 --> SchB1
SchB1 --> StB1[("Storage<br/>partition 1")]
SchB2 --> StB2[("Storage<br/>partition 2")]
end
Cl --> SA1
Cl --> SA2
SA1 <-.->|"replicate batches<br/>(async or Paxos)"| SB1
SA2 <-.->|"replicate batches<br/>(async or Paxos)"| SB2
- Sequencing layer. Takes transaction requests, groups them into batches every epoch (10 ms in the paper), replicates each batch, and sends the batch's transactions to the schedulers of the partitions they touch. Its output is a global serial order of all transactions.
- Scheduling layer. One scheduler per partition. It takes locks on local records in the global order and runs transactions once they hold all their local locks. It coordinates with other partitions only to exchange read results, never to vote.
- Storage layer. Holds the data. Any key-value-like engine works. Calvin's paper uses an in-memory store for most experiments and also discusses disk-based storage.
The important design choice: there is no commit protocol anywhere in this picture. Replicas don't talk about outcomes. Partitions don't vote. The only cross-replica agreement is about the input batches.
2.1 Programming model
A Calvin transaction is a stored procedure submitted with its arguments. Before sequencing, Calvin must know its read set and write set — the keys it will read and write. For many transactions this is easy: "transfer(X, Y, 50)" touches X and Y. For others, the keys depend on data (see §5 on OLLP).
What a transaction cannot do:
- Be interactive. There's no "BEGIN, SELECT, think, UPDATE, COMMIT" conversation with the client. The client sends the whole transaction logic at once.
- Use nondeterministic functions at execution time. Anything like
now()orrandom()must be resolved before sequencing — for example, the sequencer stamps a timestamp or seed into the request — so every replica sees the same value. - Abort for nondeterministic reasons. It can abort only through its own logic, evaluated on the data.
That is the price of removing two-phase commit. It fits OLTP workloads that are already written as stored procedures, and APIs where one request is one transaction, such as FaunaDB's query language.
3. The Sequencer Layer and Epochs
3.1 Batching into epochs
Every sequencer node collects incoming transaction requests for one epoch (10 ms). At the end of the epoch it has a batch. The global order is defined by three values, compared in order:
- epoch number
- sequencer id (a fixed order between sequencer nodes)
- position within that sequencer's batch
So the global log is the concatenation, epoch by epoch, of every sequencer's batch, in sequencer-id order. No single node creates the whole log. Each sequencer creates its own slice, and the slices fit together by a fixed rule. This lets sequencing scale out: adding partitions adds sequencers.
3.2 Distribution to schedulers
After replicating its batch (§3.3), each sequencer sends every scheduler a message with: its sequencer id, the epoch number, and the transactions from its batch that touch that scheduler's partition. A scheduler waits until it has a message from every sequencer for epoch e (possibly empty), then interleaves them in sequencer-id order. Now it knows its partition's slice of the global order for epoch e.
sequenceDiagram
autonumber
participant S1 as Sequencer 1
participant S2 as Sequencer 2
participant Sch1 as Scheduler P1
participant Sch2 as Scheduler P2
Note over S1: Epoch 42 batch = T1 (P1,P2), T2 (P1)
Note over S2: Epoch 42 batch = T3 (P2), T4 (P1,P2)
Note over S1,S2: Replicate each batch to the other replicas
S1->>Sch1: epoch 42 from S1 = T1, T2
S1->>Sch2: epoch 42 from S1 = T1
S2->>Sch1: epoch 42 from S2 = T4
S2->>Sch2: epoch 42 from S2 = T3, T4
Note over Sch1: Order for P1 = T1, T2, T4
Note over Sch2: Order for P2 = T1, T3, T4
Both schedulers see T1 before T4, because the global order is T1, T2, T3, T4 and each scheduler takes the subsequence that touches it. This is the property that makes everything work: any two transactions that share a partition appear in the same relative order at every partition and every replica.
3.3 Replicating the input
Since the batches are the database's truth, they must be durable and agreed upon before anyone executes them. Calvin supports two modes:
- Asynchronous replication. One replica is the master. All transactions go to its sequencers, which forward batches to the other replicas and continue without waiting. Low latency, but if the master replica fails, the last few epochs may be lost, and failover is complex.
- Paxos-based synchronous replication. Sequencers for the same partition across replicas agree on each batch through Paxos before it is released to schedulers. A transaction is durable once its batch is agreed by a majority of replicas. Failover is clean: any replica holding the agreed log can carry on.
The paper found that synchronous replication increases latency — every transaction waits for one cross-replica consensus round on its batch — but has little effect on throughput, because consensus is done once per batch rather than per transaction, and it happens before any locks are taken. That is the key asymmetry with two-phase commit: in Calvin the wide-area round trip happens outside the contention window.
3.4 Worked example: the cost of a hot record
Suppose replicas are 80 ms apart round-trip, and a hot row (say, a warehouse year-to-date total) is touched by every transaction.
| Classic 2PC over Paxos groups | Calvin with Paxos input replication | |
|---|---|---|
| Wide-area rounds per transaction | Prepare + commit, each with a replicated log write — about 2 consensus rounds | 1 consensus round on the batch (shared by every transaction in the epoch) |
| When those rounds happen | While holding locks | Before locks are requested |
| Lock hold time on the hot row | about 160 ms or more | local execution time plus any remote-read wait inside one replica — often well under a millisecond for single-partition, a LAN round trip for multi-partition |
| Max throughput on the hot row | about 1 / 0.16 s ≈ 6 tx/s | about 1 / 0.0005 s ≈ 2,000 tx/s or more |
| Latency of each transaction | about 160+ ms | about epoch wait (avg 5 ms) + 80 ms + execution |
The numbers are illustrative, but the shape is the whole argument. Calvin does not make each transaction faster. Often it makes them slower, because of the epoch batching. It makes the system much faster under contention, because the expensive coordination no longer happens while locks are held.
4. The Scheduler: Deterministic Locking and Execution
4.1 The locking rule
Each scheduler uses a lock manager that is like strict two-phase locking, with one extra rule from the paper:
If transactions A and B both request exclusive locks on a local record R, and A comes before B in the global order, then A must request its lock on R before B does.
Calvin enforces this simply: one thread requests all locks for transactions in global order. A transaction requests all its locks at once, when the lock manager reaches it. Each scheduler only locks records stored on its own partition.
Consequences:
- No deadlocks. Locks are always requested in the same global order, so there is no cycle in the waits-for graph. No deadlock detector, no timeouts, no victims.
- Equivalence to the serial order. Conflicting transactions run in log order, so the result equals running them one by one in that order.
- Parallelism where possible. Non-conflicting transactions get their locks right away and run in parallel on worker threads.
A transaction that has all its local locks goes to a worker thread to execute.
4.2 The five execution phases
A multi-partition transaction is executed by every partition it touches. Partitions that write are active participants. Partitions that only provide reads are passive participants. Each worker runs five phases:
- Read/write set analysis. Find which local records are read and written, and which participants are active.
- Perform local reads. Read the local records in the read set.
- Serve remote reads. Send local read results to every active participant.
- Collect remote read results. Active participants wait for reads from all other participants.
- Execute and apply local writes. With every read value in hand, run the transaction logic and write only the local records in the write set. Writes to other partitions are done by those partitions, which run the same logic on the same inputs.
sequenceDiagram
autonumber
participant W1 as Worker on P1 (holds X)
participant W2 as Worker on P2 (holds Y)
Note over W1,W2: transfer(X, Y, 50) — both already hold their local locks
W1->>W1: read X = 120
W2->>W2: read Y = 30
W1->>W2: X = 120
W2->>W1: Y = 30
Note over W1: Run logic, 120 ≥ 50 → write X = 70
Note over W2: Run the same logic → write Y = 80
Note over W1,W2: Release locks. No votes, no commit messages
Both workers run the full transaction logic. P1 discards the write to Y; P2 discards the write to X. Each applies what it owns. If the logic says "abort, insufficient funds", both reach that decision from the same inputs. A deterministic abort is just another outcome.
4.3 Why there is no commit protocol
Ask what could make P1 and P2 disagree:
| Cause in a classic system | In Calvin |
|---|---|
| A participant crashed before voting | The input log is durable. The crashed node, or a replacement, replays from its checkpoint and reaches the same state. No one waits for its vote. |
| Deadlock victim | No deadlocks. |
| Different serialization order on different nodes | Same global order everywhere. |
| Different data seen | Same order of prior transactions, so same data. |
| Application-level abort | Both compute it. |
There is one remaining dependency: in phase 4, an active participant waits for remote reads. If P2 crashes, P1 waits until P2 (or a replica of P2) recovers and sends the reads. That is a liveness cost, not a safety issue, and replicas keep it short.
4.4 A subtle point: the write-only participant still needs the reads
Look again at the transfer. P2 must know X's value to decide whether to credit Y, because the transfer aborts if X is too low. That is why reads are sent to every active participant. Passive participants (pure readers) don't need anyone else's data.
This is also why a Calvin system needs to know which partitions are active before execution: it decides who waits for whom.
5. Dependent Transactions: OLLP and Reconnaissance
5.1 The problem
Deterministic locking requests every lock up front. That requires knowing the full read/write set before execution. Many real transactions only learn what they touch by reading:
- "Update the order whose id is stored in
customer.last_order." - "Decrement stock for every item in this cart" — where the cart contents live in the database.
- Any lookup through a secondary index: find rows by email, then update them.
The paper calls these dependent transactions: the read/write set depends on the results of reads in the same transaction.
5.2 OLLP: optimistic lock location prediction
Calvin's solution is Optimistic Lock Location Prediction (OLLP):
- Reconnaissance. Before sequencing, run an inexpensive, low-isolation, unreplicated reconnaissance query that performs the reads needed to discover the full read/write set. Nothing is locked; it is just a lookup.
- Annotate and sequence. Send the transaction to the sequencer annotated with the predicted read/write set.
- Check during execution. When the transaction runs (now holding locks on the predicted keys), it re-reads the values that determined the set. If they are unchanged, the prediction was right and execution continues.
- Deterministic restart. If they changed — another transaction modified the index between reconnaissance and execution — the transaction is deterministically aborted (every participant sees the same change, so they all agree) and restarted with a new reconnaissance step.
sequenceDiagram
autonumber
participant Cl as Client
participant R as Recon reader
participant Seq as Sequencer
participant Sch as Schedulers
Cl->>R: ship_cart(cart 9)
R->>R: read cart 9 = items A, B (no locks)
R->>Seq: ship_cart(9), predicted set = cart 9, A, B
Seq->>Sch: sequenced in epoch 77
Note over Sch: Lock cart 9, A, B and re-read cart 9
alt cart still holds A, B
Sch->>Sch: decrement A, B, mark shipped
else cart changed to A, B, C
Note over Sch: Every participant sees the mismatch,<br/>abort deterministically
Sch-->>R: restart with fresh reconnaissance
end
5.3 When OLLP works and when it doesn't
OLLP is optimistic, so it's cheap when the data that determines the read/write set changes rarely compared with how often it's read. Secondary indexes on mostly stable values (like email addresses) and foreign keys that are set once are good cases. The paper's evaluation reported that OLLP overhead was small for workloads like TPC-C, where a few transactions are dependent.
It is a poor fit when the "pointer" data is itself hot. Then the reconnaissance result keeps going stale, transactions restart repeatedly, and you can get livelock under contention. That is the deterministic-database version of optimistic concurrency's starvation problem.
5.4 Worked example: a secondary index update
A table users(id, email, tier) is partitioned by id, with a secondary index email → id partitioned by email. The transaction "set tier = gold for the user with email e" needs to know the id.
- Reconnaissance reads
index[e]and finds id 4471. - Sequenced with read set
{index[e], users[4471]}and write set{users[4471]}. - During execution, the index partition re-reads
index[e]. Still 4471: proceed. The users partition updates the tier. - If someone changed the email in between, the index entry now points elsewhere or is gone. Both partitions see the same re-read result, both abort, and the client library retries.
Notice that no partition had to ask "did you commit?" The abort decision came from data they all saw at the same point in the order.
6. Disk-Resident Data: The Prefetch Delay
Deterministic execution has a weakness. In a normal database, if transaction T1 stalls waiting for a disk read, the scheduler can let T2 (later in time) go ahead and maybe commit first. In Calvin, if T1 and T2 conflict, T2 must wait for T1, because the order is fixed. One slow disk read blocks everything queued behind it on that record — and with multi-partition transactions, potentially on other partitions too.
Calvin's answer: when a sequencer gets a transaction that will probably touch data that isn't in memory, it delays forwarding the transaction to the scheduler while sending a prefetch ("warm-up") request to the storage layer. By the time the transaction reaches the lock manager, its data is likely in memory, and it holds locks only for in-memory execution.
This needs two estimates: how long disk I/O takes, and which records are cold. The paper discusses tracking these and accepting some error. The cost is extra latency for transactions touching cold data. The benefit is that locks are never held across disk I/O.
7. Checkpointing and Recovery
Because the input log is replicated and execution is deterministic, recovering a node is just: load a checkpoint, replay the log from the checkpoint's position. Calvin never logs physical changes (redo/undo records). The log of transaction inputs is enough. This is command logging, the same approach as VoltDB.
The paper describes three ways to take a checkpoint that is consistent with a log position:
- Naive synchronous mode. Pause one replica at a point in the log, write its state to disk, then let it catch up by replaying. Simple, but that replica falls behind during the checkpoint. Other replicas keep serving.
- Asynchronous, Zig-Zag variant. Based on the Zig-Zag algorithm (Cao et al.): keep two versions of each record so a checkpoint thread can read a frozen consistent state while transactions continue updating the other version. No pause, more memory.
- Storage-provided snapshots. If the storage engine supports multi-versioning, take a snapshot at a log position directly.
Replaying is fast when checkpoints are frequent. And since every replica holds the same log and runs the same code, a lost machine can be rebuilt from any replica's checkpoint plus the log.
8. Guarantees — Precisely
| Property | Calvin provides | Caveats from the paper and design |
|---|---|---|
| Isolation | Serializability, equivalent to the global log order | Holds for transactions whose read/write sets are declared or predicted (OLLP) and checked |
| Strict serializability | A transaction's position in the log is fixed after it is submitted, so log order respects real-time order of submission and completion | Read-only transactions that bypass the log to read from a local snapshot can be stale and are not strictly serializable unless they go through the log |
| Atomicity | All-or-nothing across partitions without 2PC | Depends on the transaction code being deterministic. A bug that makes it nondeterministic (calling the clock, iterating a hash map in random order) makes replicas diverge silently |
| Durability | A transaction is durable once its batch is replicated | In asynchronous mode, recent epochs can be lost if the master replica fails |
| Availability | Survives replica failures as long as the input log is available (a Paxos majority in synchronous mode) | A transaction waiting on remote reads stalls while the remote partition is down and recovering in that replica |
| Deadlock freedom | Yes — ordered lock acquisition | — |
| Interactive transactions | No | All logic must be submitted at once |
The deeper point: Calvin's correctness rests on determinism, and determinism is a property of code. Spanner-style systems are robust to arbitrary transaction code. Calvin is robust only to code that behaves the same way everywhere. Production deterministic systems put a lot of effort into making the execution environment deterministic — fixed iteration orders, no wall-clock reads, controlled floating point, the same code version on every replica.
9. Fault Tolerance
flowchart TB
F["Failure"] --> Q{"Which component?"}
Q -->|"Sequencer node"| A["Batch replication via Paxos:<br/>peers in other replicas hold the agreed batch.<br/>New sequencer resumes from the next epoch"]
Q -->|"Scheduler or storage node"| B["Other replicas keep serving.<br/>Failed node restores a checkpoint<br/>and replays the input log"]
Q -->|"Whole replica / data centre"| C["Clients go to another replica.<br/>Synchronous mode loses nothing.<br/>Async mode can lose last epochs"]
Q -->|"Network partition between replicas"| D["Majority side keeps agreeing on batches.<br/>Minority side stops sequencing (no new input)"]
Some observations:
- Replicas don't need to be in sync in time. Replica B can be several epochs behind replica A. Both will reach the same state at each log position. That makes slow replicas harmless to the others.
- No dual failure of coordinator and participant. The classic 2PC blocking problem — the coordinator dies after participants vote yes, leaving them holding locks with no decision — has no counterpart. There is no coordinator and no vote.
- Partitions in the paper's sense are within a replica. Calvin replicates the whole database at each replica. Cross-partition reads (phase 3) happen within a replica, over a LAN. Only batch replication crosses the WAN.
10. Performance Numbers From the Paper
The paper evaluated Calvin on Amazon EC2 with an in-memory storage engine. Some important results, in the authors' framing:
- TPC-C throughput. On the TPC-C benchmark (New Order transactions in the main experiments), Calvin scaled near-linearly to 100 machines and reached over 500,000 transactions per second on commodity EC2 instances. These were not audited, official TPC-C results, and the data was memory-resident.
- Contention microbenchmark. In a microbenchmark that varies a contention index (the fraction of transactions touching a hot set of records) and the share of multi-partition transactions, Calvin's throughput fell much less under high contention than a system that held locks during a distributed commit protocol. That matches the contention-footprint argument in §1.2.
- Replication. Paxos-based synchronous replication of the input increased transaction latency by roughly the cost of a consensus round across replicas but did not noticeably reduce throughput, because one consensus round covers a whole batch.
- Disk-based storage. With the prefetch delay, Calvin kept high throughput when data was larger than memory, at the cost of extra latency for transactions that touched cold data. Without it, a cold read holds locks for the whole disk access and blocks every conflicting transaction queued behind it.
These results are from 2012-era EC2 instances and an in-memory store, using stored-procedure transactions that declare their read/write sets. They show the shape of the trade-off rather than numbers to expect from a modern deployment.
11. FaunaDB: Calvin in Production
Fauna, Inc. (founded by former Twitter engineers Evan Weaver and Matt Freels) built FaunaDB as a globally distributed, strictly serializable, document-relational database inspired by Calvin. It ran as a serverless cloud service. It changed Calvin in three important ways.
11.1 Optimistic execution instead of declared read/write sets
Calvin needs to know the read/write set before sequencing. Fauna's query language (FQL) lets queries read data and then decide what to do. Fauna handled this with an optimistic approach rather than OLLP:
- A query coordinator receives the transaction and executes it speculatively against a recent snapshot. It records every read (with the version it saw) and buffers every write without applying it.
- The coordinator submits the transaction's read set (with versions) and write set to the distributed transaction log.
- The log orders it and assigns it a position (and hence a timestamp).
- When data nodes that own the affected records apply the log entry, each checks deterministically whether the read versions are still current at that log position. If yes, the writes are applied. If any read is stale, the transaction is aborted, and the coordinator can retry it.
sequenceDiagram
autonumber
participant Cl as Client
participant QC as Query coordinator
participant Log as Replicated transaction log
participant DN1 as Data node (owns X)
participant DN2 as Data node (owns Y)
Cl->>QC: FQL transaction
QC->>DN1: snapshot read X at t=100
QC->>DN2: snapshot read Y at t=100
Note over QC: Run the logic, buffer writes.<br/>Reads = X v97, Y v88
QC->>Log: append(reads with versions, writes)
Note over Log: Consensus across regions,<br/>assigns position 5012
Log->>DN1: entry 5012
Log->>DN2: entry 5012
Note over DN1,DN2: Each checks the read versions are<br/>still current at 5012 — same answer everywhere
DN1-->>QC: applied
DN2-->>QC: applied
QC-->>Cl: committed at 5012
The validation step is deterministic: every data node sees the same log, so they all agree on whether the reads are still valid. This is optimistic concurrency control with a deterministic commit check, layered on Calvin's "order first" log. It supports transactions whose keys depend on reads, without a separate reconnaissance phase. The cost is aborts and retries when concurrent transactions touch the same records.
11.2 A replicated log built on consensus
Fauna replaced Calvin's per-epoch batch agreement with a log replicated by a Raft-style consensus protocol across regions, split into several segments for throughput, with batching of entries at a fixed interval. A write commits once a majority of log replicas accept it, typically in different regions. That gives cross-region durability and strict serializability for read-write transactions with one global consensus round per transaction batch — no two-phase commit, no atomic clocks.
11.3 Reads without the log
Fauna served read-only queries from a local replica's snapshot, without going through the log, which made reads fast (a local round trip). Those reads are serializable but may lag slightly behind the newest writes. Fauna documented an option to make reads go through the log (or wait for the replica to catch up) when strict serializability was needed for a read. This is the same trade-off as §8: in Calvin-style systems, reads are where you choose between latency and strictness.
11.4 Testing and history
Jepsen analysed FaunaDB 2.5.4 in 2019. The report found several bugs, which Fauna fixed in subsequent releases; see the report itself for the specifics rather than relying on summaries. Fauna also added features like temporal queries (reading data "as of" a past time), document-relational modelling, and ABAC.
The company announced in March 2025 that it would shut down the Fauna service (the service ended in May 2025) and said it planned to release the core technology as open source. The architecture remains one of the few production-scale deterministic databases, which is why it's still worth studying. If you're reading this later, check the status of the open-source release before planning around it.
12. Calvin vs Spanner-Style Designs
Daniel Abadi's 2017 comparison essays (on his blog and Fauna's) framed the debate. Here it is in table form:
| Spanner-style (Spanner, CockroachDB, YugabyteDB) | Calvin-style (Calvin, Fauna, SLOG) | |
|---|---|---|
| Consensus is about | Each partition's log; plus 2PC across partitions | One global input log |
| Wide-area rounds per multi-partition write | 2PC across Paxos/Raft groups: about two consensus rounds, plus commit wait in Spanner | One consensus round per batch |
| Locks held during WAN rounds | Yes | No |
| Throughput under contention | Lower — limited by lock hold time | Higher |
| Latency for single-partition writes | One consensus round in that partition's group, possibly local if the group's leader is near | Global log round — every write pays it, even single-partition ones |
| Clock dependency | Spanner: TrueTime bounds. Others: hybrid logical clocks with max-offset assumptions | None for correctness |
| Interactive transactions / SQL sessions | Yes | No (stored procedures or one-shot queries) |
| Read-only transactions | Lock-free snapshot reads at any sufficiently up-to-date replica | Snapshot reads at local replica (maybe stale), or via log (slower) |
| Arbitrary code in transactions | Safe | Must be deterministic |
| Failure of one partition | Transactions touching it block until its group elects a new leader | Transactions waiting for its reads stall until a replica of it recovers |
| Data placement flexibility | Per-partition leaders can be placed near users | A single global log — SLOG adds per-region "homes" to fix this |
When to read this table as a decision: Spanner-style is the safe default because it supports SQL sessions and any code, and its single-partition, leader-local writes are fast. Calvin-style wins when there are many multi-partition transactions on contended data, the transactions can be expressed as one-shot procedures, and you'd rather pay a fixed latency than a contention-dependent one.
13. What Calvin Got Right, What It Got Wrong, and the Successors
13.1 Right
- Moving consensus to the input. This removes two-phase commit and its blocking failure mode, and shrinks the contention window to local execution.
- Scalable sequencing. Per-partition sequencers with a fixed merge rule avoid a single sequencer bottleneck.
- Deadlock freedom by construction, which removes a whole class of tail-latency problems.
- Command logging and replay for recovery — simpler than physical logging and cheap replica rebuilds.
13.2 Wrong, or costly
- Read/write sets up front. OLLP works, but it's awkward and can livelock on hot pointers. Fauna's optimistic variant and Aria (below) removed the requirement.
- Every transaction pays global ordering latency. A purely local transaction in Tokyo still waits for a log round that may include other continents. For globally distributed users this is the biggest practical issue.
- Head-of-line blocking. A slow transaction (cold data, a big scan) delays every conflicting transaction after it. The prefetch delay helps; it doesn't eliminate the problem.
- No interactive transactions. This shuts out most existing SQL applications and ORMs.
13.3 Successors
| System | Year | What it changed |
|---|---|---|
| BOHM (Faleiro & Abadi, VLDB 2015) | 2015 | Multi-version deterministic concurrency control; reads don't block writes |
| PWV (Faleiro, Abadi, Hellerstein, VLDB 2017) | 2017 | Makes writes visible early to reduce latency in deterministic systems |
| SLOG (Ren, Li, Abadi, VLDB 2019) | 2019 | Each record has a home region. Single-home transactions are ordered only in their home region's log (low latency); multi-home transactions go through a global order. Fixes §13.2 point 2 for workloads with locality |
| Aria (Lu, Yu, Cao, Madden, VLDB 2020) | 2020 | Deterministic without read/write sets: execute a batch against a snapshot, then deterministically detect conflicts and reorder or abort |
| Detock (Nguyen et al., SIGMOD 2023) | 2023 | Deterministic, multi-region, detects and resolves "deadlocks" in the global order graph deterministically to avoid waiting for a global sequencer |
| FaunaDB | 2016–2025 | Optimistic execution + deterministic validation over a replicated log (§11) |
The CACM 2018 article "An Overview of Deterministic Database Systems" (Abadi and Faleiro) summarises the line of work. Note also that deterministic ideas appear in non-database places: blockchain execution (every node replays the same ordered blocks — see Distributed Ledgers), event sourcing, and deterministic simulation testing (used by FoundationDB to test its own non-deterministic database).
14. When Determinism Is the Right Choice
Use this checklist in a design discussion:
Determinism is a good fit when:
- Transactions are one-shot — an API request maps to a single transaction, as with stored procedures or a query language like FQL.
- Many transactions touch multiple partitions and contended records (inventory, balances, counters, seat maps, order books).
- You need strict serializability across regions and don't have TrueTime-quality clocks.
- You value predictable latency under contention over the lowest possible single-key latency.
- Replay-based recovery and audit (the log is the history) are useful features.
Choose something else when:
- Applications need interactive SQL transactions or existing ORMs.
- Most transactions are single-partition and users are spread globally. Per-partition consensus with local leaders will give lower latency.
- Transaction logic calls external services or is otherwise hard to make deterministic.
- Workloads have long-running or scan-heavy transactions that would cause head-of-line blocking.
War Story (illustrative)
A ticketing team builds seat reservation on a Spanner-style database. On a big concert's sale, thousands of transactions per second try to update the same few seat-map rows across partitions, each holding locks through a cross-region commit. Throughput drops to tens of transactions per second and retries pile up. Moving reservations to one-shot "reserve(seat_ids)" procedures on a deterministic, log-ordered store gets throughput up by two orders of magnitude, at the cost of a fixed ~100 ms added latency for every reservation. For a ticket sale that is a good trade. For a chat app it would not be.
15. Lessons for System Design Interviews
- "Agree on input, not output." The most transferable idea. It shows up in state machine replication, event sourcing, blockchains and deterministic replay. Mention it when a question involves replicas that must agree.
- Name the contention footprint. When asked why distributed transactions are slow, say "locks are held across network round trips, so hot keys limit throughput to about one over the lock hold time." Then mention that ordering-first designs take the WAN round trip out of the lock window.
- Determinism has requirements. One-shot transactions, known or validated read/write sets, no nondeterministic functions. Name them; interviewers look for them.
- Every write pays the global log. Be ready to say how you'd reduce that (SLOG-style home regions, or keep single-region data on a regional log).
- Reads are the place for trade-offs. Snapshot reads from the local replica (fast, maybe stale) or through the log (strict).
- Compare with Spanner fairly. Spanner gives interactive SQL and local-leader writes. Calvin gives contention tolerance and no clock dependency.
16. Interview Questions
1. Why can Calvin commit a multi-partition transaction without two-phase commit?
2PC exists to agree on the outcome when a participant might fail to commit for nondeterministic reasons. Calvin removes those reasons: the input order is agreed and replicated in advance, locks are taken in that order (no deadlocks), and failed nodes recover by replaying the log rather than aborting. The only aborts left come from transaction logic, which every participant computes identically from the same reads. So each participant knows the outcome without asking.
2. How does Calvin build a global order without a single sequencer bottleneck?
Each sequencer node creates a batch every epoch. The global order is defined by (epoch, sequencer id, position in batch). Each scheduler waits for every sequencer's (possibly empty) message for an epoch and interleaves them in sequencer-id order, so all schedulers derive consistent subsequences of the same global order. Sequencers scale with partitions.
3. What is deterministic locking and why is it deadlock-free?
A single lock-manager thread per partition requests locks for transactions in global log order, and each transaction requests all its locks at once. If A precedes B and both need record R, A requests R first. All waits point from later transactions to earlier ones, so the waits-for graph can't have a cycle.
4. A transaction must update all rows matching a secondary index lookup. How does Calvin handle it?
OLLP: run an unlocked reconnaissance read to find the matching rows, sequence the transaction with that predicted read/write set, and during execution re-read the index entry under lock. If it matches, continue. If not, every participant sees the mismatch and aborts deterministically, then the transaction is retried with fresh reconnaissance. Works well when the index changes rarely, poorly when it's hot.
5. Why does synchronous Paxos replication in Calvin hurt latency but not throughput?
Consensus happens once per batch, covering all transactions in an epoch, so its cost is amortised. And it happens before any locks are taken, so it doesn't extend lock hold time — contention, which limits throughput, is unaffected. Each transaction still waits one consensus round before it executes, which adds latency.
6. What happens in Calvin if a partition crashes while another partition waits for its remote reads?
The waiting active participant stalls until the crashed partition, in that replica, recovers from a checkpoint and replays the log up to that transaction, or until the system redirects to another replica. It's a liveness issue only: no transaction is aborted and no state diverges, because the outcome doesn't depend on timing.
7. How did FaunaDB avoid requiring declared read/write sets?
A coordinator speculatively executes the transaction at a snapshot, recording read versions and buffering writes, then appends both to the replicated log. When data nodes apply the entry, each deterministically checks that the read versions are still current at that log position. If so, the writes apply; if not, the transaction aborts and retries. It's OCC with a deterministic validation step on a shared ordered log.
8. Compare the latency of a single-partition write in Spanner and in Calvin with globally distributed replicas.
Spanner: one Paxos round in that partition's group. If the leader and a majority are in one region near the client, it can be fast, plus commit wait (a few ms). Calvin: the write must enter the global input log, which needs a consensus round across replicas — often cross-continent — plus epoch batching delay. Calvin is slower for this case; SLOG's home regions were designed to fix it.
9. Why is nondeterminism dangerous in Calvin, and how would you guard against it?
Replicas apply transactions independently; if code behaves differently on two replicas, their states diverge with no error raised. Guards: forbid wall-clock and random calls (inject values at sequencing), fixed iteration orders, the same code and library versions on all replicas (versioned procedures in the log), deterministic floating point, and periodic cross-replica state checksums to detect divergence.
10. Design question — a global auction platform needs strict serializability for bids on hot items. Would you choose Calvin-style or Spanner-style?
Calvin-style is attractive: bids are one-shot, contention on hot items is extreme, and strict ordering is needed. Keep bid logic as a deterministic procedure, accept the global log latency (bids already tolerate ~100 ms), and serve item pages from local snapshots. If most activity is regional, use SLOG-style home regions per auction. If the platform needs interactive multi-step SQL for other features, keep those on a separate Spanner-style store.
11. What does "contention footprint" mean and why does it decide throughput on hot records?
It's how long a transaction holds locks (or otherwise blocks conflicting transactions). On a single hot record, conflicting transactions serialise, so maximum throughput is roughly one over the hold time. In 2PC over replicated groups, hold time includes several WAN rounds. Calvin shrinks it to local execution plus LAN remote reads.
Further Reading
- A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, D. J. Abadi. Calvin: Fast Distributed Transactions for Partitioned Database Systems. SIGMOD 2012. — primary source for Calvin's design and numbers.
- A. Thomson, D. J. Abadi. The Case for Determinism in Database Systems. VLDB 2010.
- D. J. Abadi, J. M. Faleiro. An Overview of Deterministic Database Systems. Communications of the ACM, 2018.
- K. Ren, D. Li, D. J. Abadi. SLOG: Serializable, Low-latency, Geo-replicated Transactions. VLDB 2019.
- Y. Lu, X. Yu, L. Cao, S. Madden. Aria: A Fast and Practical Deterministic OLTP Database. VLDB 2020.
- Jepsen. FaunaDB 2.5.4. 2019.
- J. C. Corbett et al. Spanner: Google's Globally-Distributed Database. OSDI 2012.
Related Archon pages: Distributed Transactions · Isolation Levels · Consistency Models · Raft in Plain English · NewSQL · Spanner