Introduction

Maintaining order is important in all computer systems. This implies, the same holds true for distributed systems. We maintain order by ensuring at least some consistency. In the world of distributed systems, ensuring consistency across multiple nodes is a challenging task. When there are multiple nodes to agree on the outcome of operation, then multiple kinds of failure can arise. Failure of communication links and failure of the hardware are just one of them. To make sure all sub-transactions commit despite any combination of failures we need reliable protocol. One such protocol is the Two-Phase Commit (2PC) protocol, which guarantees atomicity and consistency in distributed transactions. In this blog post, we will explore the basics of the Two-Phase Commit protocol and its importance in maintaining data integrity.

Understanding the Two-Phase Commit Protocol

The Two-Phase Commit algorithm allows multi-partition atomic updates. It ensures that either all nodes commit or all nodes abort. This pattern may be used by any applications, but it’s most widely discussed in the context of databases. The Two-Phase Commit protocol is the most straight forward and because of that most widely used when atomic transactions are required. During the explanation following concepts will be used:

coordinator (sometimes called transaction manager) – node the transaction originates

subordinates (sometimes called participants) – nodes the sub-transactions are executed on

Transaction flow

Transaction originates on some node (coordinator) and all sub-transactions are distributed across subordinates. Steps required for distributed transaction using 2PC protocol are written down below.

I. BEGIN

1. Application wants to start transaction.
2. Application obtains globally unique transaction ID (TID) from coordinator node to begin distributed transaction. Globally unique TID is required to identify the transaction.
3. Application begins a single-node transaction on each of the subordinates participating in transaction. The globally unique TID is attached to each of the single-nodes transactions.
4. All necessary steps (reads, writes etc.) on a single node are done.
5. When the transaction is executed (not yet committed!) – when all the subordinates at which transaction was executed inform coordinator that transaction has completed – coordinator kicks off the 2PC protocol described below.

II. Phase 1 (Prepare phase)

1. The coordinator adds the record <prepare TID> to the log and forces the log onto the stable storage.
2. The coordinator sends a prepare TID message to all subordinates.
3. The subordinate decides whether it is willing to commit its portion of transaction.
   1. If no, it adds a record <abort TID> to the log, forces the log onto the stable storage and responds to the coordinator by sending abort TID message.
   2. If yes, it adds a record <ready TID> to the log, forces the log onto the stable storage and responds to the coordinator by sending ready TID message.

III. Phase 2 (Commit phase)

1. Based on responses coordinator decides whether the transaction can be committed or aborted. When all subordinates respond with ready TID then transaction can be committed. When any subordinate responds with abort then transaction must be aborted.
   1. If all subordinates respond with ready, coordinator adds a record <commit TID> to the log, forces the log onto the stable storage and responds to the subordinates by sending commit message.
   2. If any of the subordinates respond with abort, coordinator adds a record <abort TID> to the log, forces the log onto the stable storage and responds to the subordinates by sending abort TID message.
2. Depending on the answer subordinate force-writes to the log either <commit TID> or <abort TID>. Either way subordinate sends ack message to the coordinator.
3. When ack from all subordinates is received coordinator writes <end TID> to the log.

The name “Two-Phase” refers to the fact that there are two rounds of messages are exchanged between coordinator and subordinates. First round: coordinator asks for preparation (ready, abort), second round: coordinator asks for termination (commit, abort).

Failures & Recovery

The 2PC protocol handles different types of failure.

1. Failure of subordinate. Depending on the phase, when coordinator detects that subordinate has failed, coordinator can take actions:
   1. Abort. If subordinator failed before responding <ready TID> to coordinator.
   2. Proceed. If subordinator failed after responding <ready TID> to coordinator.
   When failed subordinate recovers, depending on the log record proper action is taken. If there either <commit TID> or <abort TID> log record the situation is clear. Invoke redo or undo respectively. Where there are no log records: undo. When the log contains <ready TID> subordinate needs to establish what should be done. When coordinator is up, subordinate verifies with coordinator what is the status and applies redo or undo depending on the answer. When coordinator is down then querystatus TID message is sent to the other subordinates and applies redo or undo depending on the answer. If there are no nodes responding, either coordinator or subordinates, the recovered node periodically queries coordinator and subordinates. Decision is postponed until some other nodes are up.
2. Failure of coordinator. The subordinates must decide the status of transaction.
   1. If active node has either <commit TID> or <abort TID> log record the situation is clear. Invoke redo or undo respectively.
   2. When the log contains <ready TID> entry or there is no log entry, then subordinate needs to establish what should be done. Decision is postponed until coordinator is up. Coordinator have not yet decided about the fate of the transaction, so we need to wait.
3. Network partition.
   1. If coordinator and some subordinates are in the same partition protocol proceeds, but with less subordinates nodes.
   2. If coordinator and some subordinates are not in the same partition then from the perspective of subordinate it looks like coordinator is down, so procedure from Failure of coordinator is applied.

Importance of the Two-Phase Commit Protocol

The Two-Phase Commit protocol plays a crucial role in ensuring data consistency in distributed systems. By involving all participating nodes in the decision-making process, it prevents inconsistencies that could arise from individual nodes making independent decisions. The protocol guarantees that a transaction is either committed on all nodes or aborted on all nodes, eliminating the possibility of partial commits or inconsistent states. In banking systems, for example, ensuring the consistency of transactions is of utmost importance to avoid any financial discrepancies. By using the Two-Phase Commit protocol, banks can guarantee that funds are transferred accurately and reliably between accounts.

Downsizes

1. Latency. Obvious disadvantage. Each transaction requires communication between coordinator and all subordinates. Communication and coordination overhead impacts the overall performance of the distributed system.
2. Single point of failure. Coordinator participates in all stages of the transaction. From the beginning (obtaining transaction ID) up to the end. In case of failure sometimes subordinates need to wait for the coordinator to be up.
3. Blocking problem. Waiting for the coordinator blocks some resources. When there are multiple transactions at once waiting for the coordinator to recover multiple data items may be unavailable for a long period of time.

Conclusion

In the realm of distributed systems, the Two-Phase Commit protocol stands as a reliable mechanism for achieving distributed transaction consistency. By incorporating a preparing phase and a commit phase, the protocol ensures that all participating nodes are in agreement before committing or aborting a transaction. This guarantees data integrity and prevents inconsistencies that could arise from independent decision-making. The protocol’s fault tolerance and recoverability features further enhance its importance in ensuring the stability and reliability of distributed systems. As distributed systems continue to evolve, there are other variations of the 2PC. These alternatives aim to address some of the challenges associated with the 2PC protocol and enhance the efficiency and fault tolerance of distributed systems. Yet, the Two-Phase Commit protocol remains a cornerstone in achieving transactional integrity across multiple nodes.

References

1. Kleppmann, M. (2017), Designing Data-Intensive Applications , O’Reilly.
2. Silberschatz, A.; Korth, H. F. & Sudarshan, S. (2019), Database system concepts 7th Edition , McGraw-Hill.
3. Ramakrishnan, R.; Gehrke, J. (2014), Database Management Systems 3rd Edition , McGraw-Hill.