Distributed transactions and recovery research

Why it matters

Every globally distributed SQL database has to answer the same questions: how transactions on different partitions commit atomically, how their order is decided, and what happens when a machine or data center fails mid-protocol. The answers involve clocks, consensus and determinism, and the papers mix proofs with deployment measurements. Separating the two is the skill this topic trains.

Core ideas

2PC and its blocking window. A participant that votes yes must keep its locks and wait for the coordinator's decision; if the coordinator fails, participants cannot safely decide alone. Three-phase commit avoids blocking only under timing assumptions that real networks violate, so practical systems make the coordinator and every participant a consensus-replicated group: the vote and the decision are logged in replicated state machines and survive minority failures. Gray and Lamport's "Consensus on Transaction Commit" frames this as running consensus on each participant's vote (Paxos Commit) and compares its message delays with 2PC.

Spanner. Data is split into Paxos groups. Read-write transactions take locks at group leaders (wound-wait prevents deadlock), buffer writes at the client and commit with 2PC across groups. TrueTime returns an interval assumed to contain the absolute time. The coordinator picks a commit timestamp no smaller than the interval's latest bound at the time it receives the commit request, then waits until that timestamp is certainly in the past before making the commit visible (commit wait). Hence, if one transaction commits before another starts, it receives the smaller timestamp: external consistency. Read-only transactions read at a chosen timestamp without locks, on any replica that is sufficiently up to date. The guarantee is conditional: if the uncertainty bound is violated, the ordering argument fails. The costs are commit wait, which grows with clock uncertainty, plus Paxos and wide-area 2PC latency.

Calvin. Calvin moves agreement before execution. A sequencing layer collects transaction requests into batches and replicates this input log; every replica then executes the transactions in the logged order with a deterministic locking scheduler. Because execution is deterministic and a node failure cannot cause an abort, partitions need no 2PC to agree on outcomes. The price is that a transaction's read and write sets must be known in advance, or discovered by a preliminary reconnaissance read, and that the schedule couples nodes, so a slow node can delay transactions that depend on it.

Evaluating designs. Harding et al. implemented six distributed concurrency-control protocols, including a deterministic one, in a single framework on cloud machines. They found that none scaled well across servers, that the best protocol depended on contention and update rate, and that the deterministic protocol suffered when transactions needed lookups to determine their access sets. As with single-node studies, conclusions depend on workload parameters such as the share of multi-partition transactions and on the platform.

Recovery and durability research. All of these protocols assume a log record is durable once flushed. Studies of crash consistency show that applications rely on ordering and atomicity properties file systems do not guarantee, and the fsync-failure study by Rebello et al. shows file systems and applications, databases included, mishandling fsync errors, leading to data loss or corruption. Recovery time research matters too, because availability depends on how quickly a failed node replays its log.

Common misconceptions

• "Spanner proves clocks can be trusted." It shows how to use a clock with explicit uncertainty; correctness rests on the bound holding, an engineering assumption supported by measurements.
• "Calvin eliminates coordination." It moves coordination into the sequencing layer and requires known access sets.
• "Replicating participants makes 2PC non-blocking for free." It replaces waiting for one machine with consensus rounds and still stalls if a group loses its majority.
• "External consistency is the same as serializability." It is strict serializability: serializable and respecting real-time order between non-overlapping transactions.
• "Durable means fsync returned success." Storage-stack behavior on errors and reordering can break that assumption.

How to approach it

Draw message diagrams for plain 2PC, 2PC over Raft groups, a Spanner read-write transaction with commit wait, and a Calvin batch. For each, count wide-area round trips and mark where a failure blocks progress. Read Spanner with its guide on the paper route, then Calvin and the Harding et al. evaluation, recording which statements are guarantees and which are measurements. For research interviews, prepare a short comparison of the three designs and one experiment you would run to test a claim.