Two Phase Commit
Last updated
Last updated
The high level ideas of two-phase commit: (1) the leader blocks until it is sure that an operation is complete (2) an operation is only executed if every follower agrees to do so
Given an operation (i.e. PUT or DELETE), the leader (a.k.a. the global coordinator) will use a PREPARE phase where it asks every follower if it agrees to the operation.
Each of the followers can respond with a vote, which is either COMMIT (yes) or ABORT (no). The leader blocks until it has received a vote from every follower. If a follower does not respond within a timeout, the leader automatically assumes that the follower votes ABORT.
When the leader has received the vote from every follower, it will enter the COMMIT phase and send either a global COMMIT (if every follower voted to commit) or a global ABORT (if even a single follower voted no) to all of the followers.
The followers then execute the global command and respond with an ACK to acknowledge to the leader that it has completed the operation.
Only after the leader has received an ACK from every follower does it consider the operation complete and becomes available to handle the next command. If a follower does not respond within a timeout, the leader retransmits the global command until it does.
Two phase commit is implemented as a state machine, where communications between the leader and the followers result in state transitions. Below are the state diagrams for both the leader and the follower, respectively, which you will implement in this homework. Normally, completion of the global ABORT and COMMIT states should transition both the follower and the leader back into INIT.
However in this homework, we skip the actual ABORT/COMMIT states as they only exist during execution of the global command and do not persist between commands. We instead only use TPC_INIT to designate a Follower ready to vote and TPC_READY to designate a Follower ready to execute a global command. The Leader does not require explicitly keeping track of what state it is on.
