CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 3 of 7 · 3 min read

Two-phase commit

Ask everyone if they can commit, record the decision, then tell everyone.

Think of a teacher organising a school trip. Phase one: ask each parent "can your child come, yes or no?" Every parent who says yes has promised, and may not change their mind. Phase two: if all said yes, the teacher announces "we go", otherwise "trip cancelled". The teacher writes the decision down before telling anyone.

Two-phase commit (2PC) is the classic way to get atomic commit across nodes. It is used inside some databases and offered to applications as XA transactions. It adds a coordinator (also called the transaction manager), often a library inside the application process. The nodes doing the work are participants.

Two-phase commit (2PC)

Two-phase commit is an algorithm in which a coordinator first asks all participants whether they can commit (the prepare phase) and then, only if all said yes, tells them all to commit (the commit phase). If any said no, it tells them all to abort.

Example: the coordinator asks shard 1 and shard 2 "can you commit transaction 77?" Both say yes. The coordinator records "commit 77" on disk and tells both to commit.

Steps, following the book:

  1. The application asks the coordinator for a globally unique transaction id.
  2. The application runs a normal single-node transaction on each participant, tagged with that id.
  3. When ready to commit, the coordinator sends prepare to every participant. If any request fails or times out, it sends abort to all.
  4. A participant that receives prepare makes sure it can definitely commit: it writes all data to disk and checks for conflicts. Replying yes is a promise to commit if asked. It gives up the right to abort, but has not committed yet.
  5. When all replies are in, the coordinator decides: commit only if all voted yes. It writes the decision to its transaction log on disk. This is the commit point.
  6. It sends commit or abort to all participants, retrying forever until it succeeds. If a participant crashed meanwhile, it commits when it recovers, because it had voted yes.

The two points of no return: a participant's yes (it promises it can commit) and the coordinator's decision (irrevocable). Those two promises give atomicity. A single-node commit merges both into one write of the commit record.

2PC and 2PL (module 3) have similar names and nothing else in common: 2PC is atomic commit across nodes, 2PL is a way to get serializable isolation.

A worked example. Transfer 100 from account A on shard 1 to account B on shard 2.

Step Coordinator Shard 1 Shard 2
1 Begin transaction 77 Debit A by 100 (locked) Credit B by 100 (locked)
2 Send prepare Writes data to disk, replies yes Writes data to disk, replies yes
3 Both yes: writes "commit 77" to its log Waiting Waiting
4 Send commit Commits, releases lock Commits, releases lock

If shard 2 had replied no (say B's account is closed), the coordinator writes "abort 77" and tells both to roll back. Shard 1's debit disappears.

Check yourself:

  • What does a participant promise when it votes yes?
  • Where is the commit point of 2PC?