2PC and 3PC

Two phase commit (2PC) originates from a simple idea. For example, you want to arrange a game with three friends on some day, what would you do? First, you need to propose a time and ask each of your picked friends to see if they are available on that time. If all of them reply you with a yes, then you need to tell your friends to settle on that time. Otherwise, if any of them is not free on that moment, you need to tell your friends to cancel that meeting.

In the 2PC algorithm there are two roles: one coordinator and several worker. Here is how the algorithm works:

  1. The coordinator sends a proposal to all workers.
  2. The worker reply to the coordinator with either agree or disagree.
  3. If all workers replies with agree, the coordinator send a commit message to all workers; otherwise it will send abort to all workers.
  4. When a worker receives a commit/abort message, acknowledge that message.

After one iteration of the protocol, each worker will reach a consensus state: all committed or all aborted. Everything seems to work well if none of them encounters a failure. Though 2PC is easy to implement and understand, there are also many defects:

  1. It's a blocking algorithm since it has to wait for all workers to finish one iteration. If any of the worker failed, the execution is blocked.
  2. The coordinator is a single point failure.

To circumvent problems in 2PC, an improved version has been proposed, which basically adds an extra phase to 2PC:

  1. Phase one: Proposal
    • The coordinator sends a proposal to each worker to ask them if they can commit this proposal.
    • Each worker replies with yes or no.
  2. Phase two: Prepare commit
    • If any of the worker replies with no or the coordinator failed to receive response from some worker, the coordinator decides to abort this transaction and will send abort command to each worker. Otherwise, the coordinator will send a prepare commit message to each worker.
    • When a worker receives the prepare commit message, it prepare for commit and replies with yes.
  3. Phase three: Commit
    • If the coordinator receives yes from all workers, it will send a commit message to them. Otherwise, if any worker replies with no or failed to reply after timeout, it will send abort message.
    • The worker will do the commit and send an ack. If has not received commit message after timeout, it will continue with commit.

Though 3PC no longer blocks the execution when a worker failed, it still has some problems when network partition happens. For example, in the prepare commit phase, after all worker received prepare commit message from coordinator network partition happened, when some of the workers can not communicate with coordinator. Coordinator can't receive replies from some workers and will send abort to workers, while the split out workers can not receive abort or commit message from coordinator will continue with commit. After network merges the system state will become inconsistent.

In this chapter I've talked about the pros and cons of 2PC and 3PC. Though they are easy to understand and implement, they are not strong enough. In the next chapter, I'll talk about paxos, a real consensus algorithm.