UCSC CS 277 - Notes 10 - More TP (56 pages)

Previewing pages 1, 2, 3, 4, 26, 27, 28, 53, 54, 55, 56 of 56 page document View the full content.
View Full Document

Notes 10 - More TP



Previewing pages 1, 2, 3, 4, 26, 27, 28, 53, 54, 55, 56 of actual document.

View the full content.
View Full Document
View Full Document

Notes 10 - More TP

19 views


Pages:
56
School:
University of California, Santa Cruz
Course:
Cs 277 - Database System Implementation
Database System Implementation Documents
Unformatted text preview:

CS 277 Database System Implementation Notes 10 More TP Arthur Keller CS 277 Spring 20 02 Notes 10 1 Sections 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 20 02 Notes 10 2 Chapter 19 More on transaction processing Topics Cascading rollback recoverable schedule Deadlocks Prevention Detection View serializability Distributed transactions Long transactions nested compensation CS 277 Spring 20 02 Notes 10 3 Tj Ti Wj A ri A Commit Ti Abort Tj Cascading rollback CS 277 Spring 20 02 Notes 10 Example Concurrency control recovery Bad 4 Schedule is conflict serializable Tj Ti But not recoverable CS 277 Spring 20 02 Notes 10 5 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 20 02 Notes 10 6 To model this two new actions Ci transaction Ti commits Ai transaction Ti aborts CS 277 Spring 20 02 Notes 10 7 Back to example Ti Tj ri A Wj A Ci CS 277 Spring 20 02 Notes 10 can we commit here 8 Definition Ti reads from Tj in S Tj S Ti if 1 wj A S ri A 2 aj S ri A precede does not 3 If wj A S wk A S ri A then ak S ri A CS 277 Spring 20 02 Notes 10 9 Definition Schedule S is recoverable if whenever Tj S Ti and j i and Ci S then Cj S Ci CS 277 Spring 20 02 Notes 10 10 Note 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 transaction CS 277 Spring 20 02 Notes 10 11 How to achieve recoverable schedules CS 277 Spring 20 02 Notes 10 12 With 2PL hold write locks to Tj Ti commit strict 2PL Wj A Cj uj A CS 277 Spring 20 02 ri A Notes 10 13 With validation no change CS 277 Spring 20 02 Notes 10 14 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 20 02 Notes 10 15 S is strict if each transaction may read and write only items previously written by committed transactions RC ST SERIAL Avoids cascading rollback ACR CS 277 Spring 20 02 Notes 10 16 Where are serializable schedules RC ST SERIAL Avoids cascading rollback ACR CS 277 Spring 20 02 Notes 10 17 Examples Recoverable w1 A w1 B w2 A r2 B c1 c2 Avoids Cascading Rollback w1 A w1 B w2 A c1 r2 B c Assumes w2 A is done 2 without reading Strict w1 A w1 B c1 w2 A r2 B c2 CS 277 Spring 20 02 Notes 10 18 Deadlocks Detection Wait for graph Prevention Resource ordering Timeout Wait die Wound wait CS 277 Spring 20 02 Notes 10 19 Deadlock Detection Build Wait For graph Use lock table structures Build incrementally or periodically When cycle found rollback victim T1 T4 CS 277 Spring 20 02 T5 T2 T6 T3 Notes 10 T7 20 Resource Ordering Order all elements A1 A2 An A transaction T can lock Ai after Aj only if i j Problem Ordered lock requests not realistic in most cases CS 277 Spring 20 02 Notes 10 21 Timeout If transaction waits more than L sec roll it back Simple scheme Hard to select L CS 277 Spring 20 02 Notes 10 22 Wait die Transactions given a timestamp when they arrive ts Ti Ti can only wait for Tj if ts Ti ts Tj else die CS 277 Spring 20 02 Notes 10 23 Example T1 wait ts 10 T2 wait wait ts 20 T3 ts 25 CS 277 Spring 20 02 Notes 10 24 Second Example T1 ts 22 requests A wait for T2 or T3 T2 Note ts between 20 and 25 wait A ts 20 T3 ts 25 CS 277 Spring 20 02 Notes 10 25 Second Example continued One option T1 waits just for T3 transaction holding lock But when T2 gets lock T1 will have to die T1 ts 22 T2 wait A wait A ts 20 T3 ts 25 CS 277 Spring 20 02 Notes 10 26 Second Example continued Another option T1 only gets A lock after T2 T3 complete so T1 waits for both T2 T3 T1 T1 dies right away wait A ts 22 T2 wait A wait A ts 20 T3 ts 25 CS 277 Spring 20 02 Notes 10 27 Second Example continued Yet another option T1 preempts T2 so T1 only waits for T3 T2 then waits for T3 and T1 may starve T1 ts 22 T2 wait A T2 wait A wait A T3 ts 25 CS 277 Spring 20 02 Notes 10 ts 20 redundant arc 28 Wound 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 Ti CS 277 Spring 20 02 Notes 10 29 Example T1 wait ts 25 T2 wait wait ts 20 T3 ts 10 CS 277 Spring 20 02 Notes 10 30 Second Example T1 ts 15 requests A wait for T2 or T3 T2 Note ts between 10 and 20 wait A ts 20 T3 ts 10 CS 277 Spring 20 02 Notes 10 31 Second Example continued One option T1 waits just for T3 transaction holding lock But when T2 gets lock T1 waits for T2 and wounds T2 T1 ts 15 T2 wait A wait A ts 20 T3 ts 10 CS 277 Spring 20 02 Notes 10 32 Second Example continued Another option T1 only gets A lock after T2 T3 complete so T1 waits for both T2 T3 T1 away wait A ts 15 T2 wounded right T2 wait A wait A ts 20 T3 ts 10 CS 277 Spring 20 02 Notes 10 33 Second Example continued Yet another option T1 preempts T2 so T1 only waits for T3 T2 then waits for T3 and T1 is spared T1 ts 15 T2 wait A T2 wait A wait A ts 20 T3 ts 10 CS 277 Spring 20 02 Notes 10 34 User Program commands Lots of variations but in general Begin work Commit work Abort work CS 277 Spring 20 02 Notes 10 35 Nested transactions User program Begin work If results ok then commit work else abort work CS 277 Spring 20 02 Notes 10 36 Nested transactions User program Begin work Begin work If results ok then commit work else abort work try something else If results ok then commit work else abort work CS 277 Spring 20 02 Notes …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Notes 10 - More TP and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Notes 10 - More TP and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?