Ics 214B: Transaction Processing and Distributed Data Management Lecture 12: Three-Phase Commits (3PC)



Yüklə 158,5 Kb.
tarix29.12.2016
ölçüsü158,5 Kb.
#3852


ICS 214B: Transaction Processing and Distributed Data Management

  • Lecture 12: Three-Phase Commits (3PC)

  • Professor Chen Li


2PC is blocking

  • Sample scenario:

  • Coord P2

  • W

  • P1 P3

  • W

  • P4 W



Case I:

  • Case I:

  • P1  “W”; coordinator sent commits

  • P1  “C”

  • Case II:

  • P1  NO; P1  A

  •  P2, P3, P4 (surviving participants)

  • cannot safely abort or commit transaction



Complexity analysis

  • Count number of messages, rounds

    • N participants
  • Centralized 2PC

    • Ignore DONE messages
    • If there are no failures:
      • 3 rounds
      • 3N messages


Variants of 2PC

  • Linear

    • Coord
  • Hierarchical



Variants of 2PC

  • Distributed

    • Nodes broadcast all messages
    • Every node knows when to commit


Exercise

  • Compare 2PC variants in terms of

    • Number of rounds
    • Number of messages


Cooperative Termination Protocol

  • Bad case

    • Participant P recovers from failure
    • Has prepared record for transaction T
    • No commit or abort record for T
    • Coordinator is down
  • Participant P is blocked until coordinator recovers



Cooperative termination protocol

  • But perhaps some other participant can help?

  • Requires participants “know” each other!



Cooperative Termination Protocol

  • Participant P sends a DECISION-REQUEST message to other participants

  • Alive participants respond with COMMIT, ABORT, or UNCERTAIN

  • If any participant replies with a decision (COMMIT or ABORT), P acts on decision

    • And sends decision to UNCERTAIN participants


Cooperative Termination Protocol

  • When P receives a DECISION-REQUEST

    • If it knows decision, responds with COMMIT or ABORT
    • If it has not prepared transaction, responds ABORT
    • If it is prepared but does not know decision, responds UNCERTAIN


Cooperative Termination

  • Sample scenario:

  • Coord P1

  • C

  • P2

  • W

  • P3 W



Cooperative Termination

  • Sample scenario:

  • Coord P1

  • W

  • P2

  • W

  • P3 A



Cooperative Termination

  • Sample scenario:

  • Coord P1

  • W

  • P2

  • W

  • P3 W



Is there a non-blocking protocol?

  • Theorem:

  • If communications failure or total site failures (i.e., all sites are down simultaneously) are possible, then every atomic protocol may cause processes to become blocked.



Next…

  • Three-phase commit (3PC)

    • Nonblocking if reliable network (no communications failure) and no total site failures
    • Handling communications failures


Three-Phase Commit

  • Sample scenario:

  • Coord P1

  • W

  • P2

  • W

  • P3 W





3PC Principle

  • If ANY operational site is in the “uncertain” state, NO site (operational or failed) could have decided to commit

  • Reminder: Assume reliable network











Process categories

  • Three categories

    • Operational
      • Process has been up since start of 3PC
    • Failed
      • Process has halted since start of 3PC, or is recovering
    • Recovered
      • Process that failed and has completed recovery


Termination Protocol





Termination Protocol

  • Elect new coordinator

    • Use Election Protocol (coming soon…)
  • New coordinator sends STATE-REQUEST to participants

  • Makes decision using termination rules

  • Communicates to participants











Termination Protocol

  • Sample scenario:

  • Coord P1

  • W

  • P2

  • W

  • P3 W



Termination Protocol

  • Sample scenario:

  • Coord P1

  • W

  • P2

  • W

  • P3 PC



Note: 3PC unsafe with communication failures!

  • Note: 3PC unsafe with communication failures!



Yüklə 158,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