_____________ LECTURE11 Irene Zhang _____________ Table of Contents _________________ 1 Introduction .. 1.1 What is a transaction? .. 1.2 What if the transaction is distributed .. 1.3 2pc 2 The 2pc protocol .. 2.1 the actors .. 2.2 the RPCs: prepare, commit, abort .. 2.3 The steps: .. 2.4 Invariants in the protocol ..... 2.4.1 All processes that reach a decision reach the same one ..... 2.4.2 A process cannot reverse its decision once it has reached one ..... 2.4.3 The commit decision can only be reached if all processes voted prepare-ok/yes ..... 2.4.4 If there are no failures and all votes are prepare-ok/yes, then the transaction will commit ..... 2.4.5 If all failures are eventually repaired, then every processes will eventually reach a decision 3 Failures .. 3.1 What happens if a participant fails? ..... 3.1.1 before sending a response? ..... 3.1.2 after sending a response but before receiving decision? ..... 3.1.3 after receiving decision .. 3.2 What happens if the coordinator fails? ..... 3.2.1 Before sending prepare? ..... 3.2.2 After sending prepare but before receiving responses? ..... 3.2.3 After receiving responses? ..... 3.2.4 After sending decision .. 3.3 What if the participants knew about each other? 4 The blocking problem 1 Introduction ============== 1.1 What is a transaction? ~~~~~~~~~~~~~~~~~~~~~~~~~~ - atomic, consistent, isolated, durable piece of code - consistent does not mean consistency! Bad naming again!! 1.2 What if the transaction is distributed ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - if the database is distributed, then the transaction might touch two servers - we need to make sure that these properties are maintained across the servers 1.3 2pc ~~~~~~~ - an atomic commitment protocol, either all servers execute the operation or none of them do - there are other ACPs but 2PC is the most popular - Also, you can think about why you need at least 2 phases to achieve distributed atomicity 2 The 2pc protocol ================== 2.1 the actors ~~~~~~~~~~~~~~ - participants: a server that holds data from the transaction - coordinator: can be any node, including one of the participants 2.2 the RPCs: prepare, commit, abort ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2.3 The steps: ~~~~~~~~~~~~~~ 1. The coordinator sends a prepare (this is vote-req in the reading) to all the participants 2. The participants respond either prepare-ok (yes) or abort (no) 3. The coordinator collects all of the votes. If all votes are prepare-ok and its own vote is also prepare-ok, then the coordinator decides commit, otherwise, it decides abort. The coordinator sends the decision to all participants that responded prepare-ok (the other participants are no longer waiting because they know the transaction will abort). 4. The participant records the decision from the coordinator 2.4 Invariants in the protocol ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2.4.1 All processes that reach a decision reach the same one ------------------------------------------------------------ - this guarantees atomicity 2.4.2 A process cannot reverse its decision once it has reached one ------------------------------------------------------------------- - once a participant votes prepare-ok, it must be able to commit the transaction - What might happen if a participant can't commit after voting prepare-ok? It would violate atomicity because it can't stop the other participants from committing the transaction 2.4.3 The commit decision can only be reached if all processes voted prepare-ok/yes ----------------------------------------------------------------------------------- - In other words, any participant or the coordinator can unilaterally vote to abort the transaction - Why is this necessary? if any participant can't finish the transaction, it should be able to keep the others from committing to preserve atomicity 2.4.4 If there are no failures and all votes are prepare-ok/yes, then the transaction will commit ------------------------------------------------------------------------------------------------- - this ensures progress (i.e., the protocol actually commits transactions), given no failures - the protocol trivially provides this but if it did not then it wouldn't do anything 2.4.5 If all failures are eventually repaired, then every processes will eventually reach a decision ---------------------------------------------------------------------------------------------------- - this ensures that the protocol will commit transactions eventually, even if there are failures, as long as the processes all recover eventually 3 Failures ========== 3.1 What happens if a participant fails? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3.1.1 before sending a response? -------------------------------- - the coordinator could timeout and abort, participant finds out what happened after recovering 3.1.2 after sending a response but before receiving decision? ------------------------------------------------------------- - if coordinator receives an abort vote, participant can find out what happened after recovering - if coordinator receives a prepare-ok vote, participant can't abort the transaction any more, so must find out what everyone else decided to do from the coordinator (Better log this!) - if coordinator doesn't receive vote, same as last situation, coordinator can time out and abort 3.1.3 after receiving decision ------------------------------ - can get it again from the coordinator or another participant but better log it in case someone else needs it 3.2 What happens if the coordinator fails? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3.2.1 Before sending prepare? ----------------------------- - as long as it logged, it can just start up again when it recovers 3.2.2 After sending prepare but before receiving responses? ----------------------------------------------------------- - ask all of the participants again, if any say abort, abort, otherwise, proceed as usual - this is ok even if some of the participants said abort last time because none of the other participants know about it 3.2.3 After receiving responses? -------------------------------- - same as before, can do anything because no one else knows anything yet 3.2.4 After sending decision ---------------------------- - needs to recover decision, so MUST LOG because some participants might have committed! - if any participants either committed or aborted, then the coordinator knows the decision - if none have aborted or committed, then the coordinator can still make a decision(i.e., if all prepare-ok, commit, otherwise abort) 3.3 What if the participants knew about each other? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - if the coordinator fails, they could ask each other what their votes were and come to a decision on their own. BUT they must commit if all votes prepare-ok because the coordinator might still send commit. If any abort, then ok to abort - BUT, the coordinator can no longer time out and abort because the participants might have decided that they haven't heard from the coordinator and decided to commit - this lead us to 4 The blocking problem ====================== - once a process has responded prepare-ok, it must wait for any failed process to recover because it can't do anything until it knows everyone's vote (even one abort could cause the transaction to fail or it might get a commit decision and have to commit). - fine for fault-tolerance, but no good for availability! (You don't want to know that your bank transaction won't be lost if you have to wait for ever to find out whether it went through) - we will see how Paxos does not have this problem. Essentially, the participants vote out the coordinator after long enough! - However, you have to have enough replicas to vote the coordinator out (a majority quorum). - this limitation is fundamental and called the Two generals problems, which Tom will talk about on Monday. - Hipsters generalizes this problem to CAP.