Distributed transactions — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 5: Correctness across machines

Prerequisites: Lesson 29 and the preceding foundations.

Learning outcomes

• Distinguish replicated agreement on state from atomic commitment across participants.
• Trace two-phase commit, participant recovery, and uncertainty after a coordinator failure.
• Explain distributed MVCC timestamps, clock uncertainty, and saga compensation as different mechanisms.

Prepared is not committed

A transfer touches accounts on two partitions. Both participants validate their local changes and report prepared. The coordinator crashes before they learn a final decision. A participant cannot simply abort on a timeout if the transaction might already have committed elsewhere. It cannot simply commit because local preparation succeeded either.

Distributed transactions need both atomic outcome agreement and appropriate isolation across participants. Consensus inside each partition can preserve local replicated state, while an atomic-commit protocol coordinates one transaction across partitions. These are related but distinct responsibilities.

Two-phase commit

In the prepare phase, a coordinator asks participants whether they can commit. A prepared participant records enough durable state to honor a later decision and retains the resources required by the protocol. If preparation succeeds everywhere, the coordinator durably records the commit decision and communicates it. Otherwise it records abort under the protocol’s rules.

coordinator:
    collect durable prepare outcomes from all required participants
    if all prepared:
        durably record COMMIT
    else:
        durably record ABORT
    send recorded decision until participants learn it

The pseudocode hides participant discovery, failure recovery, retries, and durable coordinator replication. Those are required in a real implementation. The important ordering is that a final decision exists durably before the coordinator communicates it as authoritative.

A participant that voted no can abort its local work. A participant already prepared may be unable to decide safely without learning the durable global outcome. This is the classic blocking issue under relevant coordinator failures. Replicating the coordinator state improves resilience but does not make prepare and outcome semantics unnecessary.

Consensus versus atomic commit

Consensus can establish a durable decision among replicas of a group. Atomic commit requires all transaction participants to reach compatible outcomes according to their votes and the transaction protocol. A database can use consensus for each participant’s log and for the coordinator’s decision state, then use a commit protocol across those groups.

Saying “the database uses Raft” therefore does not fully explain distributed transaction behavior. The design must identify which log contains the decision, how prepared participants find it after failure, and how stale coordinators are fenced. Conversely, using two-phase commit does not imply a single unreplicated coordinator with no recovery plan.

The performance path includes local execution, participant communication, replication, and decision dissemination. Some steps can overlap or be optimized under proven conditions. Removing a round trip requires explaining which fact is already established, not merely skipping a message in the diagram.

Isolation across partitions

Atomic commit alone does not prevent inconsistent observations. Transactions can read snapshots and write across partitions in ways that require serializable validation or locking. A distributed snapshot must have a defined relationship to concurrent commits.

Distributed MVCC uses versions and timestamp or transaction-status rules across owners. Read timestamps, provisional writes, conflict metadata, and final commit timestamps must agree. A reader encountering an unresolved intent may wait, consult status, push a transaction under protocol rules, or read another valid version depending on the guarantee.

A range predicate can span participants. Protecting only returned rows misses inserts, just as in a local engine. Distributed serializable execution must include the relevant predicate or dependency boundaries. Sharding changes the location of the proof, not the invariant itself.

Time and uncertainty

A timestamp can provide a convenient ordering, but physical clocks have uncertainty. Spanner’s original paper describes TrueTime and a commit-wait mechanism within its architecture. The historical paper’s assumptions and mechanisms should be studied directly rather than reduced to “accurate clocks remove coordination.”

A globally ordered transaction can require waiting until an uncertainty interval is safely passed under the model. Other engines use logical or hybrid timestamps and different conflict protocols. The important question is how the timestamp relates to visibility, real time, and replicated durability.

A clock service is itself infrastructure with failure behavior. An implementation must define what happens when uncertainty grows or time assumptions fail. A fast path valid only under bounded uncertainty should not silently continue outside its contract.

Communication-cost analysis

Suppose a prepare request contacts three participants in parallel, with illustrative RTTs 2, 5, and 8 milliseconds. The communication wait for the parallel phase is dominated by approximately 8 milliseconds, not the sum 15, before execution and durability costs. A subsequent dependent decision phase adds its own delay.

If one participant is across an 80-millisecond WAN path, local CPU optimization cannot remove that propagation dependency. Placement can keep common transactions local, while cross-region transactions pay a different cost. A useful benchmark reports the participant and replica topology rather than only transaction count.

Contention extends the cost further. Prepared work may retain locks or intents while waiting for the global decision. A slow participant can therefore block other transactions on a fast participant. Shortening transaction duration and avoiding unnecessary participant spread can improve throughput as well as individual latency.

Sagas and compensation

A saga performs a sequence of locally committed steps with compensating actions for selected failures. It is useful when one atomic database transaction cannot or should not span the full workflow. It does not provide the same visibility or rollback semantics as an atomic transaction.

If a seat is reserved, payment is charged, and a later step fails, a refund is a new business event. It may fail, be delayed, or have fees and external consequences. Other observers may have seen the intermediate reservation. The application must specify states such as pending, compensating, and manual reconciliation.

Idempotency is essential for both forward and compensating actions. Retrying a refund must not issue several refunds. Compensation cannot always restore the exact prior world, especially when physical goods or irreversible actions are involved. The workflow’s contract should acknowledge these realities.

Case comparison

The Spanner paper, FoundationDB paper, and CockroachDB transaction-layer documentation provide different implementations around distributed transactional guarantees. They differ in architecture, historical scope, and interfaces. A fair comparison asks where ordering occurs, what is replicated, how conflicts are resolved, and which participant paths a workload creates.

FoundationDB’s published architecture separates transactional roles and storage responsibilities. CockroachDB documents a transaction layer over distributed replicated storage. Spanner’s paper explains a global database architecture with explicit time uncertainty. These brief implementation facts motivate mechanism-level study; they do not establish a universal performance winner.

Enumerate the durable participant states

A participant begins with no transaction state, performs tentative work, and either votes no or durably enters prepared. Prepared means it has promised to follow the eventual authoritative decision and retained enough state to do so after restart. It cannot forget that promise merely because its coordinator is temporarily unreachable.

A duplicate prepare request should not create a second transaction or reset an existing decision. A duplicate commit request should not apply the business effect twice. Transaction identity and durable terminal state make these handlers idempotent within the protocol’s scope. Garbage collection must wait until no supported recovery path can ask an ambiguous question about discarded state.

The coordinator similarly has durable states describing participants and final decision. If it tells one participant commit before recording a recoverable decision, it can crash and later choose abort, violating atomicity. Persisting the decision before authoritative dissemination prevents that failure. An unreplicated coordinator can still block progress while unavailable even if its disk retains the correct record.

Trace failure after prepare without guessing

A transfer debits account A on partition P and credits account B on Q. Both prepare. The coordinator records commit durably, tells P, then crashes before telling Q. P commits. Q sees only prepared. Q cannot abort on a timeout because P may already have committed; this execution demonstrates that exact possibility.

If the coordinator instead crashed before any final durable decision, the recovery rules determine whether it can choose abort or must resolve additional evidence. A participant cannot infer which case occurred from silence alone. A replicated coordinator record, status lookup, termination protocol, or documented presumed-outcome optimization provides the needed authority under its assumptions.

P: prepared -> receives COMMIT -> committed
C: all votes -> durable COMMIT -> crash
Q: prepared --------------------> waits/resolves durable decision

The diagram shows why replication and atomic commit solve different layers. Consensus can keep C’s decision record available across some failures. P and Q still need rules for preparing, retaining intents, discovering the decision, and exposing results. “Replicated coordinator” is an improvement in failure tolerance, not a replacement for those state transitions.

An operator manually forcing Q to abort can restore local availability while breaking global atomicity. Such emergency procedures must be recognized as outside ordinary safe recovery unless the operator has authoritative evidence. Operational pressure does not make an unresolved prepared transaction logically equivalent to an aborted one.

Atomic outcome does not guarantee serializable decisions

Suppose two distributed transactions each read a shared invariant across P and Q and write disjoint rows. Two-phase commit can make each transaction’s writes atomic while both transactions still exhibit write skew under a snapshot-isolation model. Atomic commit decides all-or-nothing outcome; isolation decides whether their combined reads and writes form a permitted history.

A distributed lock-based engine may retain logical locks through prepare and final decision. A versioned optimistic engine may validate read dependencies across participants. A timestamp-based engine needs a coherent commit order and visibility rule. Every method must include predicates and absent rows when those influenced the decision.

The transaction’s participant set can expand as execution discovers keys or index entries. The coordinator must know all required participants before it can finalize a valid outcome. A forgotten participant can remain tentative forever or expose changes outside the intended decision. Participant discovery, enlistment, and late messages are therefore correctness concerns.

Global secondary indexes can add hidden participants. An application updating one row may touch an index stored elsewhere and thus take a distributed commit path. Performance analysis should use the actual ownership footprint, not merely the number of SQL tables or application API calls.

Distributed snapshots need a coherent cut

A read-only transaction asking for a global total should not combine one shard before a transfer and another after it. A snapshot timestamp can identify a coherent version boundary if every participant understands which transactions are committed and visible at that timestamp. Assigned timestamps alone are insufficient when some lower-timestamp work remains unresolved.

A participant may wait until it has applied all necessary history through the read boundary. Another approach can consult transaction status for provisional intents. The protocol must distinguish “no value exists” from “the relevant commit has not been applied here.” Otherwise a fast local read can return a state that never existed globally.

Logical and hybrid timestamps provide ordering tools, while physical clock uncertainty affects real-time guarantees. A transaction can be serializable without strictly respecting observed real-time order. Adding strict serializability requires a mechanism connecting transaction order to nonoverlapping invocation/completion relationships.

Spanner’s historical paper explains one such design using a time uncertainty interval and commit wait. FoundationDB’s published architecture and CockroachDB’s transaction layer describe other organizations of ordering and conflict handling. Their common lesson is that timestamps participate in a larger protocol; accurate clocks or monotonic counters alone do not implement distributed transactions.

Resolve provisional intents without inventing an outcome

A reader or writer can encounter another transaction’s provisional write. It needs to learn whether that transaction is active, prepared, committed, or aborted under the authoritative status protocol. A stale cached status can be unsafe if terminal decisions have not been propagated or if identity reuse is possible.

Some engines permit a competing transaction to push another transaction’s timestamp or request its abort according to priority rules. Those actions require a protocol that prevents the old coordinator from later committing under obsolete assumptions. Fencing generations, transaction records, and validation tie the decision together. A timeout-triggered local cleanup without that authority can erase a transaction that committed elsewhere.

Intent cleanup can be asynchronous after a decision because readers can consult status and interpret the provisional version correctly. This reduces foreground work while adding lookup and retention costs. The terminal status must remain available until every relevant intent is resolved or another safe representation replaces it.

Large abandoned transactions can therefore create operational debt. Metrics should expose unresolved intents, prepared duration, status-resolution traffic, and cleanup backlog. A database can accept new work while old transaction state accumulates toward a capacity problem, just as it can accumulate version or compaction debt.

Put the communication model on the critical path

Assume three participants have prepare request/response paths of 2, 5, and 8 milliseconds, and each requires an additional 1 millisecond of local work and persistence in this simplified model. Parallel prepare completes in roughly 9 milliseconds, governed by the slowest participant. Add a 2-millisecond coordinator decision persistence stage and an 8-millisecond dependent dissemination/acknowledgment path if the chosen response contract waits for it. The modeled total is nineteen milliseconds before initial execution and client transport.

An implementation may overlap stages, replicate decisions differently, or return before every participant applies the result. Those are legitimate optimizations only when recovery and visibility remain correct. The model should name what the client response waits for. Omitting a stage from a diagram without explaining the resulting guarantee is not a latency improvement.

Participant count affects tail latency as well as average bytes. Waiting for every required participant makes the slowest response significant. More participants also increase chances that at least one experiences a pause or conflict. Co-locating common transaction records or narrowing the invariant can reduce both communication and retained-resource time.

One-phase or parallelized fast paths can apply when prerequisites make some facts redundant. For example, a single-participant transaction may not need a general cross-participant prepare protocol. The engine must still detect when secondary indexes or dynamically discovered accesses invalidate the fast-path assumptions. Fast and general paths must agree on terminal outcome semantics.

A saga provides a different visible history

A travel workflow reserves a room, buys a flight, and charges a card through separate authorities. Treating all three as one local ACID transaction is usually impossible. A saga records durable workflow state and executes local steps, then compensates selected earlier steps when later work fails.

The compensation for a purchased flight may be a refund request, not erasure of the purchase. It can have a fee, be delayed, or require manual handling. Other users can observe the room as reserved during the workflow. These intermediate states are part of the application’s contract and UX.

Each step and compensation needs an operation identity. If a worker crashes after issuing a refund but before recording success, retrying must resolve or deduplicate the refund. A workflow log helps resume progress but does not make the external service’s response reliable. Reconciliation compares authoritative external state with workflow intent when outcomes remain uncertain.

A saga is appropriate when business semantics permit these visible states and compensations. It is not a transparent faster implementation of an atomic bank transfer. Choosing it changes what observers can see and what failure means, so that choice belongs in the architecture’s correctness contract.

Prepared work is a capacity commitment

A prepared transaction can retain locks, versions, log records, and memory while waiting for a coordinator. If many coordinators fail or slow simultaneously, a healthy participant can become overloaded by retained state. Admission control should consider unresolved work rather than count only currently executing statements.

A hundred thousand prepared transactions each retaining four kilobytes of metadata and intent payload account for an illustrative 400 MB before lock-table, index, and allocator overhead. Their logical conflicts can block much more business activity than that memory figure suggests. Duration and conflict footprint matter alongside count.

A robust deployment provides status recovery, bounded discovery retries, alerts for old prepared transactions, and documented safe operational procedures. The correct resolution is based on authoritative decision evidence. Automatically aborting everything older than a threshold may improve a dashboard while violating atomicity.

Use distributed transactions where the invariant needs them

A partitionable SaaS workload can keep most transactions tenant-local and reserve cross-tenant coordination for genuinely shared facts. A marketplace may deliberately colocate item ownership and purchase state to keep its dominant action local. A shared world may use separate regions for independent activity but define explicit handoff semantics for movement and trade.

These are workload design decisions rather than universal prohibitions against distributed transactions. A correct distributed engine can make cross-owner work usable, but it must pay for the evidence required by its guarantee. The engineering goal is to minimize unnecessary coordination while preserving the invariants that motivated the system in the first place.

A recovery-state sequence for the transfer

Coordinator C        Participant P             Participant Q
PREPARE -----------> validate; durable prepare
PREPARE --------------------------------------> validate; durable prepare
             <------ YES, retain intent
             <--------------------------------- YES, retain intent
persist COMMIT
COMMIT ------------> install/resolve committed
        crash before Q receives decision
                      terminal COMMIT           PREPARED, cannot decide alone
recovery reads COMMIT -------------------------> resolve COMMIT

The participant votes require durable recovery state under this model. P’s completed decision does not authorize Q to guess based on a timeout, but an authoritative recovered commit record resolves Q safely. If the coordinator record itself is replicated, its availability depends on that group’s protocol and surviving quorum. The transaction’s participant groups and the coordinator group can have different failures and resource bottlenecks.

Transaction retries can cross ownership changes

A client retry may encounter a new gateway, a new shard owner, or a recovered coordinator. The transaction identity should remain stable enough for the supported protocol to determine whether it is a repeated attempt or a genuinely new operation. A newly allocated transaction attempt can still refer to the same business operation through an idempotency record.

This two-level distinction is useful. Internal retries may need a fresh snapshot and fresh transaction identifier, while the purchase itself should not be charged twice. An application operation key survives those internal attempts and is committed atomically with the accepted result. Confusing attempt identity with business identity can either suppress legitimate recomputation or duplicate the final effect.

A retry must obey the original deadline and contention budget. After repeated serialization conflicts, returning a controlled retryable result can be safer than allowing one operation to monopolize resources. The business-facing error should distinguish a known failure from an outcome that still requires status resolution. Large concurrency makes these rare branches common in aggregate, so they belong in the main design.

A transaction coordinator should expose the age of its oldest unresolved decision and the participants still awaiting resolution. That evidence helps distinguish a blocked correctness obligation from an ordinary slow query. Operational tooling must resolve the authoritative transaction state before deleting intents or releasing protected ownership.

Design conclusion

A distributed transaction design must resolve durable outcome, isolation, timestamp meaning, stale authority, retries, and participant cleanup. Placement and workload shape determine how often the expensive cross-owner path occurs.

The next part focuses on scale beyond correctness: distributed query work, caches, maintained results, client delivery, and overload. Correct coordination establishes what may happen; resource-aware execution determines whether it can happen at the required rate and latency.

Sources and further reading

• Spanner original paper, Google, 2012
• FoundationDB architecture paper, 2021
• CockroachDB transaction layer

Course index · Lesson plan