Understanding Database Logging Strategies for Concurrency Control

csce 608 database systems n.w
1 / 74
Embed
Share

Explore the importance of logging strategies in database systems to ensure Atomicity and Durability. Learn about Undo, Redo, and Undo/Redo logging techniques, their formats, rules, and recovery processes. Dive into the concept of checkpoints for effective management of system failures.

  • Database Systems
  • Logging Strategies
  • Concurrency Control
  • Undo/Redo Logging
  • System Failures
rayaanacharya
eyos Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-608 Database Systems Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 37: Concurrency Control

  2. lock table DDL complier concurrency control file logging & recovery manager User-1 DDL User-2 transaction manager User-3 index/file manager buffer manager query execution engine DML User-n DML complier main memory buffers secondary storage (disks) DBMS

  3. Coping with System Failures Therefore, the logging strategy must be carefully designed to ensure Atomicity and Durability. If you are going to be in the logging business, one of the things that you have to do is to learn about heavy equipment. Robert VanNatta, Logging History of Columbia County We will study three logging strategies: Undo-logging Redo-logging Undo/Redo-logging

  4. Undo/Redo Logging The format of the Undo/Redo log: <T, start> <T, A,aold,anew> <T, B,bold,bnew> <T, commit> (or <T, abort>) transaction T starts transaction T wrote on A/B, both old and new values are recorded transaction T commits/abort Main idea of Undo/Redo logging: Increase flexibility and compromise undo logging and redo logging (at the expense of using more space).

  5. Undo/Redo Logging Undo/Redo logging rule (UR): Log records reach disk before the corresponding changes reach disk. Algorithms for Undo/Redo logging Undo/Redo log recording 1. Add <T, start> to memory-log; 2. When T writes on A, add <T, A, aold, anew> in memory-log; \\ output(A) can be performed now, \\ either before or after step 3 3. Add <T, commit> to memory-log. Recovery with Undo/Redo log 1. Bring disk-log to memory; 2. Scan the log forwards; 3. For T with <T, commit> in log For <T, A, aold, anew> in log Redo by assigning anew to A; 4. Scan the log backwards; 5. For T without <T, commit> in log For <T, A, aold, anew> in log Undo by assigning aold to A. Undo/Redo logging rule (Rule UR): An undo/redo log record must reach disk before the corresponding change reaches disk.

  6. Checkpoint for Undo/Redo logging log <T1,start> <T2,commit> <T3,start> <T4,commit> 6 6

  7. Checkpoint for Undo/Redo logging log Place a log record <Start CKPT(T1, , Tk)>, where T1, , Tk are the currently active transactions; <T1,start> <T2,commit> <T3,start> <T4,commit> <Start CKPT (T1,T3)> 7 7

  8. Checkpoint for Undo/Redo logging log Place a log record <Start CKPT(T1, , Tk)>, where T1, , Tk are the currently active transactions; Copy all dirty data in main memory to disk, this can be due to either committed or incomplete transactions; \\ at the meanwhile, the system can continuously \\ accept new transactions (non-quiescent) <T1,start> <T2,commit> <T3,start> <T4,commit> <Start CKPT (T1,T3)> copy dirty data to disk <T5,start> copy dirty data to disk 8 8

  9. Checkpoint for Undo/Redo logging log Place a log record <Start CKPT(T1, , Tk)>, where T1, , Tk are the currently active transactions; Copy all dirty data in main memory to disk, this can be due to either committed or incomplete transactions; \\ at the meanwhile, the system can continuously \\ accept new transactions (non-quiescent) When step 2 is done, place a log record <End CKPT>. <T1,start> <T2,commit> <T3,start> <T4,commit> <Start CKPT (T1,T3)> copy dirty data to disk <T5,start> copy dirty data to disk <End CKPT> 9 9

  10. Checkpoint for Undo/Redo logging log Place a log record <Start CKPT(T1, , Tk)>, where T1, , Tk are the currently active transactions; Copy all dirty data in main memory to disk, this can be due to either committed or incomplete transactions; \\ at the meanwhile, the system can continuously \\ accept new transactions (non-quiescent) When step 2 is done, place a log record <End CKPT>. \\ at this point, nothing beyond <Start CKPT( )> \\ needs Redone, but Undo still has to trace back to \\ the earliest <Ti, start> among (T1, , Tk). <T1,start> <T2,commit> <T3,start> <T4,commit> <Start CKPT (T1,T3)> copy dirty data to disk <T5,start> copy dirty data to disk <End CKPT> 10 10

  11. Checkpoint for Undo/Redo logging log Place a log record <Start CKPT(T1, , Tk)>, where T1, , Tk are the currently active transactions; Copy all dirty data in main memory to disk, this can be due to either committed or incomplete transactions; \\ at the meanwhile, the system can continuously \\ accept new transactions (non-quiescent) When step 2 is done, place a log record <End CKPT>. \\ at this point, nothing beyond <Start CKPT( )> \\ needs Redone, but Undo still has to trace back to \\ the earliest <Ti, start> among (T1, , Tk). \\ if crash occurs between <Start CKPT(T1, , Tk)> \\ and <End CKPT>, then look for a previous \\ <End CKPT> <End CKPT> <T1,start> <T2,commit> <T3,start> <T4,commit> <Start CKPT (T1,T3)> copy dirty data to disk <T5,start> copy dirty data to disk <End CKPT> 11 11

  12. Coping with System Failures Therefore, the logging strategy must be carefully designed to ensure Atomicity and Durability. If you are going to be in the logging business, one of the things that you have to do is to learn about heavy equipment. Robert VanNatta, Logging History of Columbia County We have studied three logging strategies: Undo-logging Redo-logging Undo/Redo-logging

  13. Tranactions Transaction ACID: Atomicity: either all steps of a transaction happen, or none happen Consistency: a transaction transforms a consistent DB into a consistent DB Isolation: execution of a transaction is isolated from that of other transactions Durability: if a transaction commits, its effects persist. using logging What can affect transaction ACID? Accident system failures may destroy Atomicity and Durability, thus Consistency; Concurrent executions of transactions (which is highly desired) may affect Isolation, thus Consistency.

  14. Tranactions Transaction ACID: Atomicity: either all steps of a transaction happen, or none happen Consistency: a transaction transforms a consistent DB into a consistent DB Isolation: execution of a transaction is isolated from that of other transactions Durability: if a transaction commits, its effects persist. T1 Tn What can affect transaction ACID? Accident system failures may destroy Atomicity and Durability, thus Consistency; Concurrent executions of transactions (which is highly desired) may affect Isolation, thus Consistency. Database

  15. lock table DDL DDL language concurrency database file logging & administrator complier control manager recovery transaction manager index/file buffer manager manager query database execution programmer DML (query) DML engine main language complier memory secondary buffers storage DBMS (disks) Graduate Database

  16. lock table DDL DDL language concurrency database file logging & administrator complier control manager recovery transaction manager index/file buffer manager manager query database execution programmer DML (query) DML engine main language complier memory secondary buffers storage DBMS (disks) Graduate Database

  17. Observation. In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition.

  18. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Observation. Constraint: A=B In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition.

  19. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Observation. Constraint: A=B In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B)

  20. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Observation. Constraint: A=B In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition. Such a schedule is called a serial schedule. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B)

  21. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Observation. Constraint: A=B In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition. Such a schedule is called a serial schedule. A serial schedule can be given by a permutation of the transactions that indicates the order of the execution: T1T2 Tk. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B)

  22. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Observation. Constraint: A=B In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition. Such a schedule is called a serial schedule. A serial schedule can be given by a permutation of the transactions that indicates the order of the execution: T1T2 Tk Thus, if a schedule is equivalent to a serial schedule, then it ensures Isolation. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B)

  23. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Observation. Constraint: A=B In a schedule of a collection of transactions, if for every transaction T, the actions of T are scheduled consecutively without interlacing with actions from other transactions, then surely all transactions satisfy the Isolation condition. Such a schedule is called a serial schedule. A serial schedule can be given by a permutation of the transactions that indicates the order of the execution: T1T2 Tk Thus, if a schedule is equivalent to a serial schedule, then it ensures Isolation. (two schedules S1 and S2 are equivalent if starting with any initial DB state, they always result in the same DB state.) T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B)

  24. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Scheduling: Examples Constraint: A=B

  25. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule A A serial schedule Constraint: A=B T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B);

  26. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule A A serial schedule Constraint: A=B A 25 B 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 125 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); 250 250 250 250

  27. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule B Another serial schedule Constraint: A=B T1 T2 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); Read(A); A A+100 Write(A); Read(B); B B+100; Write(B);

  28. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule B Another serial schedule Constraint: A=B A 25 B 25 T1 T2 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); 50 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); 50 150 150 150 150

  29. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule C A non-serial schedule Constraint: A=B T1 Read(A); A A+100 Write(A); T2 Read(A);A A 2; Write(A); Read(B); B B+100; Write(B); Read(B);B B 2; Write(B);

  30. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule C A non-serial schedule Constraint: A=B A 25 B 25 T1 Read(A); A A+100 Write(A); T2 125 Read(A);A A 2; Write(A); Read(B); B B+100; Write(B); 250 125 Read(B);B B 2; Write(B); 250 250 250

  31. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule D Another non-serial schedule Constraint: A=B T1 Read(A); A A+100 Write(A); T2 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); Read(B); B B+100; Write(B);

  32. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule D Another non-serial schedule Constraint: A=B A 25 B 25 T1 Read(A); A A+100 Write(A); T2 125 Read(A);A A 2; Write(A); Read(B);B B 2; Write(B); 250 Read(B); B B+100; Write(B); 50 250 150 150

  33. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule E Same as Schedule D but with new T2 Constraint: A=B T1 Read(A); A A+100 Write(A); T2 Read(A);A A 1; Write(A); Read(B);B B 1; Write(B); Read(B); B B+100; Write(B);

  34. T1: Read(A) A A+100 Write(A) Read(B) B B+100 Write(B) T2: Read(A) A A 2 Write(A) Read(B) B B 2 Write(B) Schedule E Same as Schedule D but with new T2 Constraint: A=B A 25 B 25 T1 Read(A); A A+100 Write(A); T2 125 Read(A);A A 1; Write(A); Read(B);B B 1; Write(B); 125 Read(B); B B+100; Write(B); 25 125 125 125

  35. Want schedules that are good, regardless of initial state and transaction semantics

  36. Want schedules that are good, regardless of initial state and transaction semantics Only look at order of read and writes

  37. Want schedules that are good, regardless of initial state and transaction semantics Only look at order of read and writes Schedule C T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 Example: Read(A); A A 2; Write(A); Read(B); B B 2; Write(B);

  38. Want schedules that are good, regardless of initial state and transaction semantics Only look at order of read and writes Schedule C T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 Example: Read(A); A A 2; Write(A); Read(B); B B 2; Write(B); Schedule C = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

  39. Action Swapping

  40. Action Swapping SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) Schedule C A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 Read(A); A A 2; Write(A); 250 125 Read(B); B B 2; Write(B); 250 250 250

  41. Action Swapping SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) Schedule C A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 Read(A); A A 2; Write(A); 250 125 Read(B); B B 2; Write(B); 250 250 250

  42. Action Swapping swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) Schedule C A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 Read(A); A A 2; Write(A); 250 125 Read(B); B B 2; Write(B); 250 250 250

  43. Action Swapping swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) SA= r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) Schedule C A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 Read(A); A A 2; Write(A); 250 125 Read(B); B B 2; Write(B); 250 250 250

  44. Action Swapping swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) A serial schedule SA= r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T1 T2 Schedule C A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 Read(A); A A 2; Write(A); 250 125 Read(B); B B 2; Write(B); 250 250 250

  45. Action Swapping swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) A serial schedule SA= r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T1 T2 Schedule A Schedule C A B 25 25 A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 125 Read(A); A A 2; Write(A); 125 250 Read(A); A A 2; Write(A); Read(B); B B 2; Write(B); 250 125 Read(B); B B 2; Write(B); 250 250 250 250 250 250

  46. Action Swapping SD = r1(A)w1(A)r2(A)w2(A)r2(B)w2(B)r1(B)w1(B) Schedule D T1 Read(A); A A+100 Write(A); Read(B); B B 2; Write(B); Read(B); B B+100; Write(B); T2 Read(A); A A 2; Write(A);

  47. Action Swapping SD = r1(A)w1(A)r2(A)w2(A)r2(B)w2(B)r1(B)w1(B) If we want it to be equivalent to the schedule T1T2 Schedule D T1 Read(A); A A+100 Write(A); Read(B); B B 2; Write(B); Read(B); B B+100; Write(B); T2 Read(A); A A 2; Write(A);

  48. Action Swapping SD = r1(A)w1(A)r2(A)w2(A)r2(B)w2(B)r1(B)w1(B) If we want it to be equivalent to the schedule T1T2 Schedule D T1 Read(A); A A+100 Write(A); Read(B); B B 2; Write(B); Read(B); B B+100; Write(B); T2 Read(A); A A 2; Write(A);

  49. Action Swapping SD = r1(A)w1(A)r2(A)w2(A)r2(B)w2(B)r1(B)w1(B) If we want it to be equivalent to the schedule T1T2 Schedule D T1 Read(A); A A+100 Write(A); Read(B); B B 2; Write(B); Read(B); B B+100; Write(B); T2 Read(A); A A 2; Write(A);

  50. Action Swapping SD = r1(A)w1(A)r2(A)w2(A)r2(B)w2(B)r1(B)w1(B) If we want it to be equivalent to the schedule T2T1 Schedule D T1 Read(A); A A+100 Write(A); Read(B); B B 2; Write(B); Read(B); B B+100; Write(B); T2 Read(A); A A 2; Write(A);

Related


1st Quarter Budget Performance Report for Year 2018 by Ministry of Budget and Planning

1st Quarter Budget Performance Report for Year 2018 by Ministry of Budget and Planning

rio

More Related Content