Calvin Protocol (Deterministic Transaction Scheduling)

Calvin inverts the traditional replication model. Instead of executing a transaction locally and then replicating its effects (or coordinating a commit decision across replicas via 2PC), Calvin first establishes a globally agreed, deterministic order of incoming transactions and replicates that order via a consensus log (originally Paxos, commonly Raft in modern implementations like FaunaDB). Every replica then executes the same sequence of transactions using the same deterministic concurrency control rules, producing bit-for-bit identical state without ever needing to agree on the outcome after the fact — because determinism guarantees the outcome is already agreed upon by construction.

The architecture splits into two layers: a sequencing layer that batches incoming transactions into fixed-duration epochs and replicates the batch log, and a scheduling/execution layer that applies deterministic locking (acquiring locks for a transaction’s entire read/write set up front, in a globally consistent order) before executing. This eliminates the need for two-phase commit across partitions for a given transaction, since every partition independently replays the identical global order and reaches the identical conclusion about lock acquisition and commit. Cross-partition transactions still require agreement — but only on the read/write set membership at batch time, not on a live commit vote.

The critical constraint is that the transaction’s full read/write set must be knowable before execution begins, so the scheduler can pre-acquire locks deterministically. For transactions where the write set depends on a read performed mid-transaction (dependent logic, conditional branches based on data), Calvin requires a reconnaissance query phase: a preliminary read pass to discover the actual keys touched, which are then locked before the real deterministic execution runs. This adds an extra network round trip for exactly the class of transaction that’s most common in interactive application code, which is the main practical friction point.

• Advantage: replicas never block waiting on a distributed commit vote; consistency comes from log replication, which is cheaper and more predictable under contention than 2PC blocking.
• Advantage: failure recovery is simplified — a crashed replica just replays the deterministic log from its last checkpoint, rather than resolving in-doubt transactions.
• Cost: the sequencer is a logical bottleneck and adds epoch-batching latency (typically single-digit milliseconds) even to single-partition transactions.
• Cost: non-deterministic operations (wall-clock reads, random values, external I/O) must be resolved once at sequencing time and injected as fixed inputs, or replicas diverge.

Calvin is best understood as trading per-transaction coordination latency for a small, fixed batching latency and a harder upfront constraint on transaction shape. Systems like FaunaDB adopted a Calvin-derived design specifically to get serializable, multi-region writes without the tail-latency amplification and partial-failure complexity that 2PC introduces across wide-area links, accepting the reconnaissance-query cost as the price for workloads with dynamic read sets.