CS 277: Database System Implementation Notes 10: More TPSections to Skim:Chapter 19 More on transaction processingConcurrency control & recoveryPowerPoint PresentationSlide 6To model this, two new actions:Slide 8DefinitionSlide 10Slide 11How to achieve recoverable schedules? With 2PL, hold write locks to commit (strict 2PL) With validation, no change!Slide 15Slide 16Where are serializable schedules?ExamplesDeadlocksDeadlock DetectionResource OrderingTimeoutWait-dieSlide 24Slide 25Slide 26Slide 27Slide 28Wound-waitSlide 30Slide 31Slide 32Slide 33Slide 34User/Program commandsNested transactionsSlide 37Parallel Nested TransactionsSlide 39Example:But underneath:Solution: view DB at two levelsSlide 43Slide 44Logging Logical ActionsSolution: Add Log Sequence NumberStill Have a Problem!Compensation Log RecordsAt Recovery: ExampleWhat to do with p2 (during T1 rollback)?Recovery StrategySlide 52Example: What To Do After CrashDuring Undo: Skip Undo’sRelated idea: SagasSummaryCS 277 – Spring 2002Notes 10 1CS 277: Database System ImplementationNotes 10: More TPArthur KellerCS 277 – Spring 2002Notes 10 2Sections to Skim:•Chapter 17: none (read all sections)•Chapter 18:–skim 18.8•Chapter 19:–skim 19.4, 19.5, 19.6, 19.7–maybe 19.2 (decide later...)•Chapter 20: none (read all sections)CS 277 – Spring 2002Notes 10 3Chapter 19 More on transaction processingTopics:•Cascading rollback, recoverable schedule•Deadlocks–Prevention–Detection•View serializability•Distributed transactions•Long transactions (nested, compensation)CS 277 – Spring 2002Notes 10 4Example: Tj Ti Wj(A) ri(A) Commit TiAbort TjConcurrency control & recovery………… ……Cascading rollback (Bad!)CS 277 – Spring 2002Notes 10 5•Schedule is conflict serializable•Tj Ti•But not recoverableCS 277 – Spring 2002Notes 10 6•Need to make “final” decision for each transaction:–commit decision - system guarantees transaction will or has completed, no matter what–abort decision - system guarantees transaction will or has been rolled back (has no effect)CS 277 – Spring 2002Notes 10 7To model this, two new actions:•Ci - transaction Ti commits•Ai - transaction Ti abortsCS 277 – Spring 2002Notes 10 8............Back to example: Tj Ti Wj(A)ri(A)Ci  can we commit here?CS 277 – Spring 2002Notes 10 9DefinitionTi reads from Tj in S (Tj S Ti) if(1) wj(A) <S ri(A)(2) aj <S ri(A) (< : does not precede)(3) If wj(A) <S wk(A) <S ri(A) then ak <S ri(A)CS 277 – Spring 2002Notes 10 10DefinitionSchedule S is recoverable if whenever Tj S Ti and j  i and Ci  Sthen Cj <S CiCS 277 – Spring 2002Notes 10 11Note: in transactions, reads and writes precede commit or abort If Ci  Ti, then ri(A) < Ci wi(A) < Ci  If Ai  Ti, then ri(A) < Ai wi(A) < Ai •Also, one of Ci, Ai per transactionCS 277 – Spring 2002Notes 10 12How to achieve recoverable schedules?CS 277 – Spring 2002Notes 10 13 With 2PL, hold write locks to commit (strict 2PL) Tj TiWj(A)Cjuj(A)ri(A).....................CS 277 – Spring 2002Notes 10 14 With validation, no change!CS 277 – Spring 2002Notes 10 15•S is recoverable if each transaction commits only after all transactions from which it read have committed.•S avoids cascading rollback if each transaction may read only those values written by committed transactions.CS 277 – Spring 2002Notes 10 16•S is strict if each transaction may read and write only items previously written by committed transactions.Avoids cascading rollbackRCACRSTSERIALCS 277 – Spring 2002Notes 10 17Where are serializable schedules?Avoids cascading rollbackRCACRSTSERIALCS 277 – Spring 2002Notes 10 18Examples•Recoverable:–w1(A) w1(B) w2(A) r2(B) c1 c2•Avoids Cascading Rollback:–w1(A) w1(B) w2(A) c1 r2(B) c2•Strict:–w1(A) w1(B) c1 w2(A) r2(B) c2Assumes w2(A) is donewithout readingCS 277 – Spring 2002Notes 10 19Deadlocks•Detection–Wait-for graph•Prevention–Resource ordering–Timeout–Wait-die–Wound-waitCS 277 – Spring 2002Notes 10 20Deadlock Detection•Build Wait-For graph•Use lock table structures•Build incrementally or periodically•When cycle found, rollback victimT1T3T2T6T5T4T7CS 277 – Spring 2002Notes 10 21Resource Ordering•Order all elements A1, A2, …, An•A transaction T can lock Ai after Aj only if i > jProblem : Ordered lock requests not realistic in most casesCS 277 – Spring 2002Notes 10 22Timeout•If transaction waits more than L sec., roll it back!•Simple scheme•Hard to select LCS 277 – Spring 2002Notes 10 23Wait-die•Transactions given a timestamp when they arrive …. ts(Ti)•Ti can only wait for Tj if ts(Ti)< ts(Tj) ...else dieCS 277 – Spring 2002Notes 10 24 T1(ts =10)T2(ts =20)T3 (ts =25)waitwaitExample:wait?CS 277 – Spring 2002Notes 10 25 T1(ts =22)T2(ts =20)T3 (ts =25)wait(A)Second Example:requests A: wait for T2 or T3?Note: ts between20 and 25.CS 277 – Spring 2002Notes 10 26 T1(ts =22)T2(ts =20)T3 (ts =25)wait(A)Second Example (continued):wait(A)One option: T1 waits just for T3, transaction holding lock.But when T2 gets lock, T1 will have to die!CS 277 – Spring 2002Notes 10 27 T1(ts =22)T2(ts =20)T3 (ts =25)wait(A)Second Example (continued):wait(A)wait(A)Another option: T1 only gets A lock after T2, T3 complete,so T1 waits for both T2, T3  T1 dies right away!CS 277 – Spring 2002Notes 10 28 T1(ts =22)T2(ts =20)T3 (ts =25)wait(A)Second Example (continued):wait(A)wait(A)Yet another option: T1 preempts T2, so T1 only waits for T3; T2 then waits for T3 and T1...  T2 may starve?redundant arcCS 277 – Spring 2002Notes 10 29Wound-wait•Transactions given a timestamp when they arrive … ts(Ti)•Ti wounds Tj if ts(Ti)< ts(Tj) else Ti waits“Wound”: Tj rolls back and gives lock to TiCS 277 – Spring 2002Notes 10 30 T1(ts =25)T2(ts =20)T3 (ts =10)waitwaitExample:waitCS 277 – Spring 2002Notes 10 31 T1(ts =15)T2(ts =20)T3 (ts =10)wait(A)Second Example:requests A: wait for T2 or T3?Note: ts between10 and 20.CS 277 – Spring 2002Notes 10 32 T1(ts =15)T2(ts =20)T3 (ts =10)wait(A)Second Example (continued):wait(A)One option: T1 waits just for T3, transaction holding lock.But when T2 gets lock, T1 waits for T2 and wounds T2.CS 277 – Spring 2002Notes 10 33 T1(ts =15)T2(ts =20)T3 (ts =10)wait(A)Second Example (continued):wait(A)wait(A)Another option: T1 only