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



Yüklə 165,5 Kb.
tarix29.12.2016
ölçüsü165,5 Kb.
#3846


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



Yüklə 165,5 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin