Lampson and Lomet’s Paper: a new Presumed Commit Optimization for Two Phase Commit Doug Cha coen 317 – scu spring 05

Lampson and Lomet’s Paper: A New Presumed Commit Optimization for Two Phase Commit

• Doug Cha

• COEN 317 – SCU Spring 05

About the authors

• Butler Lampson

• Currently at MSFT
• Formerly at Xerox PARC, DEC research, and a professor at MIT and Berkeley
• ACM Turing Award in 1992

• David Lomet

• Also at MSFT, formerly at DEC research
• Key work on database systems
• One of the inventors of the transaction concpet
• ACM Fellow

Outline

• Review of 2PC

• More on 2PC / Optimizations

• Presumed Nothing
• Presumed Abort
• Presumed Commit

• Recovery requirements

• The new PrC protocol

• Summary

Review of 2PC

• Distributed Atomic Commit problem (DC9 p2)

• How to get all members of a group to commit/abort together?

• Two Phase Commit, Gray 1987 (DC9 p3):

• First phase is the voting phase
• Coordinator sends all participants (cohorts) a vote request (PREPARE)
• All participants (cohorts) respond COMMIT-VOTE or ABORT-VOTE
• Second phase, coordinator decides commit or abort: if any participant voted ABORT, then decision must be abort. Otherwise, commit.
• Coordinator sends all participants decision (COMMIT or ABORT)
• Participants (who have been waiting for decision) commit or abort as instructed and ACK.

2 Phase Commit

2PC Variations

• Presumed Nothing (PrN)

• Presumed Abort (PrA)

• Presumed Commit (PrC)

• Variations deal with how to handle recovery and vary on how recovery data is logged.

Presumed Nothing (PrN)

PrN Failure Recovery

PrA Optimization

Presumed Commit (PrC) - COMMIT

Presumed Commit (PrC) - ABORT

Comparison For Now

Improving PrC

• Messaging is low already, try to reduce forced log writes.

• In PrC a forced write happens at PREPARE
• Any transactions with a PREPARE, but no transaction end are aborted
• Non existence of a transaction record assumes commit
• To remove the forced PREPARE write, we need to:
• Find another way to identify transactions that may have started before the crash but did not finish
• Keep these transaction records around so we know to abort them (since we are still presuming commits)

Improving PrC

• Instead of recording trans init, record timestamps:

• tidl –lowest possible time of an undocumented transaction
• tidh –most recent undocumented transaction
• tidsta – most recent record of a transaction

• So we have:

• REC = { tid | tidl < tid < tidh} = recent transactions
• COM = commited and stable transactions
• IN = REC – COM = transactions maybe active during crash

• On recovery:

• Cohorts asking status of a transaction assume commit unless the record exists in the IN set
• The IN set must be stored forever! (But data size is small)

The New PrC Protocol ABORT

The New PrC Protocol COMMIT

The New PrC Protocol ABORT/CRASH

Analysis of New PrC Protocol

• We reduce the # of forced writes but require permanent storage of IN records

Summary

• Two-Phase Commit

• Presumed Nothing
• Presumed Abort
• Presumed Commit
• Requirements for logging/recovery
• New Presumed Commit

References

• A New Presumed Commit Optimization for Two Phase Commit – Lampson and Lomet, 1993.

• Distributed Systems Concepts and Design – Coulouris, Dollimore, Kindberg

• Santa Clara Univ, COEN 317 class notes – Holliday