Atomic Commitment is a property of distributed systems whereby state changes (e.g. transactions) involving multiple nodes either commit on all nodes or abort on all nodes. Notably, atomic commitment is distinct from Atomic Composability, which pertains to transactions’ consensus and execution rather than their later commitment.
Overview
Atomicity guarantees that an entire transaction occurs across the distributed system or none of it occurs. Atomic commitment protocols are needed to coordinate committing transactions across multiple datastores, especially in distributed systems spread across multiple nodes.
The key motivation for atomic commitment is consistency - if a transaction makes updates to a database on multiple nodes, those updates ought to be applied consistently across nodes. Without atomicity, a situation might occur where the transaction commits on some nodes but not others, leaving the global state fractured or inconsistent. Enforcing atomic commitment avoids these kinds of anomalies and upholds invariants that may span multiple nodes.
Two-Phase Commit Protocol
The standard protocol for implementing atomic commitment across a distributed system is called two-phase commit (2PC). This protocol relies on a dedicated transaction coordinator node to orchestrate the commit.
When a client wants to commit a distributed transaction, it sends the request to the coordinator rather than directly to the database nodes. The coordinator then starts the Prepare phase. In this phase, the coordinator asks each node participating in the transaction to promise that they are able to commit. To promise, each node writes any necessary transaction updates to persistent storage and checks any integrity constraints. The node then replies back to the coordinator with a yes vote if it can commit or a no vote if it cannot commit. Once the coordinator has received votes from every participating node, it decides whether to commit or abort the overall transaction. If all nodes voted yes, the coordinator moves on to phase two, the actual Commit phase. If any node voted no, the coordinator aborts the transaction.
In the Commit phase, the coordinator sends a message to all nodes directing them to commit the transaction. The nodes then commit all the transaction updates, release any locks, and notify the coordinator of the outcome.
This two-phase approach ensures that no node is committed unless all nodes are prepared to commit. However, the coordinator introduces a vulnerability - if the coordinator fails, especially between phases, all other nodes can end up blocked and unable to release locks or updates until the coordinator recovers.
Fault-Tolerant Atomic Commitment
To avoid the coordinator bottleneck in standard two-phase commit, a fault-tolerant protocol for atomic commitment can leverage total order broadcast algorithms. In this approach, the prepare phase works similarly - the coordinator sends prepare requests and nodes check if they can commit. However, rather than replying directly to the coordinator, each node broadcasts a commit or abort vote using a total order broadcast algorithm. This ensures all nodes receive the votes even if the coordinator fails.
A failure detector can also supplement the protocol - if a node appears to not have broadcast its vote within a timeout, the detector will broadcast an abort vote on behalf of the potentially failed node. However, the total order property of the broadcast ensures that duplicate votes for any node will still be reconciled identically at each node. Each node collects the votes and can decide to commit only if votes to commit are received from all participants. A single vote to abort causes the whole transaction to abort. Relying on the total order delivery of messages, each node uses only the first vote received from any other node when deciding on the outcome.
With this approach, no single node failure can block progress - the transaction can still commit or abort as long as any majority quorum of the nodes is operational. In particular, coordinator failure during voting will not prevent other nodes from reaching a consistent commit/abort decision. This enhances the fault tolerance of atomic commitment significantly.
Atomic Composability vs Atomic Commitment
Atomic composability and atomic commitment aim for different guarantees in distributed transactions:
- Execution - Atomic composability ensures all-or-nothing transaction execution, rolling back on any failure. Atomic commitment focuses on coordinating state commitment.
- Coordination - Atomic composability depends on application-level logic. Atomic commitment requires consensus protocols across validators.
- Scope - Atomic composability handles complex application transactions. Atomic commitment works at the data layer for state changes.
- Failures - Atomic composability assumes execution failures will roll back. Atomic commitment handles commit coordination failures.
- Sharding - Atomic composability operates within a shard. Atomic commitment coordinates across shards.
In summary, atomic composability provides atomic execution useful for complex transactional logic. Atomic commitment enforces coordinated commitment of state changes across shards, preventing inconsistencies.
Shard 1 receives a simple token transfer transaction from Bob -> Carol. Shard 1 can see that Bob has the funds so executes the transaction, commits it, and changes the state of Bob to reflect the transfer.
Shard 1 communicates the transaction to Shard 2 and that it was successful.
Shard 2 now processes the transaction. It has information from Shard 1 about Bob's balance and that it executed correctly. Shard 2 now executes the transaction but there is a problem, Carol has JUST disabled deposits to her wallet! The transaction can not execute correctly at Shard 2, so it fails.
Shard 2 communicates the failure to Shard 1, which must now undo the changes it committed for the transaction.
If the protocol exhibited atomic commitment, Shard 1 would not have committed anything until Shard 2 had also executed the transaction and communicated the result. Shard 1 would then simply have also failed the transaction and would not have to do any additional work to undo the erroneous state changes.
-- Dan Hughes, Twitter, Feb 19, 2024.