Topics for the day Reliability Three phase commit 3PC Majority 3PC Distributed Databases Network partitions Committing with partitions Concurrency control with partitions CS347 Lecture 16 June 6 2001 1 3PC non blocking commit Recall 2PC is blocking Coordinator P1 P2 W P3 W 2 Assume failed node is down forever Key idea before committing coordinator tells participants everyone is ok I exec exec I nok go ok nok exec abort W abort A A W pre ok ack pre P4 W Case I P1 W coordinator sent commits P1 C Case II P1 NOK P1 A ack commit P2 P3 P4 surviving participants cannot safely abort or commit transaction 3 P P commit C Coordinator C Participant 4 1 3PC recovery termination protocol Termination rules survivors Let S1 S2 Sn be survivor sites Make decision on commit abort based on following rules If one or more Si COMMIT COMMIT T If one or more Si ABORT ABORT T If one or more Si PREPARE COMMIT T T could not have aborted If no Si PREPARE or COMMIT ABORT T T could not have committed Survivors try to complete transaction based on their current states Goal If dead nodes committed or aborted then survivors should not contradict Otherwise survivors can do as they please 5 6 Points to Note Examples P I W W Once survivors make a decision they must elect a new coordinator and continue with 3PC W W W W P P C C P C C P P C Decide to commit C P P When survivors continue 3PC failed nodes do not count Example OK OK from every non failed participant 7 8 2 Points to Note Node recovery 3PC unsafe with network partitions After node N recovers from failure what must it do W P W P N must not participate in termination protocol Wait until it hears commit abort decision from operational nodes W abort commit W P later on 9 All failed problem W A 10 Majority 3PC Waiting for commit abort decision is fine unless all nodes fail W Nodes are assigned votes Total votes V For majority need V 1 2 votes Majority rule For every state transition coordinator requires messages from nodes with a majority of votes Two possible solutions Option A Recovering node waits for either Majority rule ensures that any decision preparing committing is known to a future decision making group commit abort outcome for T from some other node all nodes that participated in T are up and running Then 3PC can continue decision 1 Option B Use Majority 3PC 11 1 2 1 1 2 2 2 decision 2 12 3 Example 1 Coordinator P1 Example 2 Coordinator P2 W P3 W P1 P4 W P2 Each node has 1 vote V 5 P4 W Right thing to do since Coordinator P1 P2 may later abort Majority 3PC go exec ok preC W P C PC W ackC commit C 15 Participant I I W 14 introduce prepare to abort state Coordinator Previously we disallowed recovering nodes from participating Now any set of nodes with majority can progress How do we fix the problem below W A Termination rule says P3 P4 can commit But P3 P4 do not have majority so block Problem P Nodes fail after entering states shown P3 and P4 recover 13 P P3 Each node has 1 vote V 5 Nodes P2 P3 P4 enter W state and fail When they recover coordinator and P1 are down Since P2 P3 P4 have majority they know coord could not have gone to P without at least one of their votes Therefore T can be aborted exec ok nok preA PA ackA abort A W preC ackC PC exec nok preA ackA A abort PA commit C 16 4 Example Revisited II Example Revisited No decision Transaction could have aborted or could have committed Block OK to commit since transaction could not have aborted PC W PC C PC W W PA W PA W PA W PA 17 18 Summarizing commit protocols Majority 3PC Rules 2PC If survivors have majority and states in W PC C try to commit Blocking protocol Key coordinator does not move to C state unless every participant is in W state If survivors have majority and states in W PA A try to abort 3PC Non blocking protocol Key coordinator broadcasts that all are ok before committing Failed nodes must wait Any set of non failed nodes can terminate transaction even a single node If all nodes fail must wait for all to recover Otherwise block Blocking Protocol 19 20 5 Network partitions Summarizing commit protocols Majority 3PC Groups of nodes may be isolated or may be slow in responding Blocking protocol Key Every state transition requires majority of votes Any majority group of active recovered nodes can terminate transaction When are partitions of interest True network partitions disaster Single node failure cannot be distinguished from partition e g NIC fails Loosely connected networks Phone in wireless 21 Quorums Problems Commit and Abort Quorums Given set S of nodes define Commit quorum C 2S Abort quorum C 2S X Y X Y such that X C and Y A Partitions during commit A C A C 22 Example S a b c d C C a b c a b d a c d b c d A a b a c a d b c b d c d Updates to replicated data in isolated partitions T1 update X X X X T2 X update 23 Quorums can be implemented with vote assignments Va Vb Vc Vd 1 1 1 a c To commit 3 votes b To abort 2 votes d 1 1 24 6 Quorums 3PC Example However not all quorums can be implemented with votes C a b c d A a c a d b c b d To make commit decision commit quorum votes for commit VC 3 To make abort decision abort quorum votes for abort VA 3 Commit protocol must enforce quorum Quorum condition is in addition to whatever rules the commit protocol might have old coordinator If node knows transaction could have committed aborted if cannot abort commit even if abort commit quorum available 2 1 w 1 w 1 w new coordinator Old coordinator could not have committed since all other nodes are in W state Surviving nodes have abort quorum With network partitions all commit protocols are blocking Attempt to abort 25 Another 3PC Example 1 old coordinator 2 P 1 w 1 w Old coordinator could not have aborted since one node is in P state Surviving nodes have commit quorum 26 Yet Another 3PC Example VC 3 VA 3 old coordinator 2 1 P 1 w 1 w VC 3 VA 3 new coordinator new coordinator Attempt to commit Note When using 3PC with quorums we must use the Prepare to Abort PA state as in majority commit for the same reasons Old coordinator could not have aborted since one node is in P state However surviving nodes do not have commit quorum 27 Block 28 7 Coteries Partitions and data replication Used to …