DBMS Internals: Recovery Management and The Log System

database applications 15 415 n.w
1 / 51
Embed
Share

Explore the concepts of Recovery Management in DBMS, covering topics such as ARIES Algorithm, log sequence numbers, log tail, and when to write log records. Understand the importance of stable storage, flushed LSN, and the WAL protocol. Dive into the intricate workings of database recovery systems.

  • DBMS
  • Recovery Management
  • Log System
  • ARIES Algorithm
  • Database Applications
rayaanacharya
akab 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. Database Applications (15-415) DBMS Internals- Part XIV Lecture 27, April 23, 2020 Mohammad Hammoud

  2. Today Last Session: Recovery Management- Part I Today s Session: Recovery Management (Continue) Announcements: PS5 is due tomorrow by midnight The final exam is on Thursday, April 30 from 8:30 to 11:30AM (it is open book, open notes)

  3. DBMS Layers Queries Query Optimization and Execution Relational Operators Files and Access Methods Transaction Manager Recovery Manager Buffer Management Lock Manager Disk Space Management Continue DB

  4. Outline The Log A Simple Transaction Abort Checkpointing The ARIES Algorithm

  5. The Log The log is a file of records stored in stable storage Every log record is given a unique id called the Log Sequence Number (LSN) LSNs are assigned in a monotonically increasing order (this is required by the ARIES recovery algorithm- later) Every page contains the LSN of the most recent log record, which describes a change to this page This is called the pageLSN

  6. The Log (Contd) The most recent portion of the log, called the log tail, is kept in main memory and forced periodically to disk Log records flushed to disk The DBMS keeps track of the maximum LSN flushed to disk so far This is called the flushedLSN pageLSN As per the WAL protocol, before a page is written to disk, pageLSN flushedLSN Log tail in RAM

  7. When to Write Log Records? A log record is written after: Updating a Page An update log record is appended to the log tail The pageLSN of the page is set to the LSN of the update log record Committing a Transaction A commitlog record is appended to the log tail The log tail is written to stable storage, up to and including the commit log record Aborting a Transaction An abort log record is appended to the log tail An undo is initiated for this transaction

  8. When to Write Log Records? A log record is written after: Ending (After Aborting or Committing) a Transaction: Additional steps are completed (later) An endlog record is appended to the log tail Undoing an Update When the action (described by an update log record) is undone, a compensation log record (CLR) is appended to the log tail CLR describes the action taken to undo the action recorded in the corresponding update log record

  9. Log Records The fields of a log record are usually as follows: Can be used to redo and undo the changes! prevLSN transID Type pageID Length Offset Before-Image After-Image Fields common to all log records: Update Log Records Commit Log Records Abort Log Records End Log Records Compensation Log Records Additional Fields for only the Update Log Records

  10. Other Recovery-Related Structures In addition to the log, the following two tables are maintained: The Transaction Table One entry E for each active transaction E fields are: Transaction ID Status, which can be Progress , Committed or Aborted lastLSN, which is the most recent log record for this transaction The Dirty Page Table One entry E for each dirty page in the buffer pool E fields are: Page ID recLSN, which is the LSN of the first log record that caused the page to become dirty

  11. An Example PageID PageID PageID recLSN recLSN recLSN P500 P500 P500 P600 P600 P600 P505 P505 P505 prevLSN prevLSN prevLSN prevLSN transID transID transID transID Type Type Type Type pageID pageID pageID pageID Length Length Length Length Offset Offset Offset Offset Before- Before- Before- Before- Image Image Image Image After- Image Image Image Image After- After- After- Dirty Page Table T1000 T1000 T1000 T1000 Update Update Update Update P500 P500 P500 P500 3 3 3 3 21 21 21 21 ABC ABC ABC ABC DEF DEF DEF DEF T2000 T2000 T2000 T2000 Update Update Update Update P600 P600 P600 P600 3 3 3 3 41 41 41 41 HIJ HIJ HIJ HIJ KLM KLM KLM KLM T2000 T2000 T2000 T2000 Update Update Update Update P500 P500 P500 P500 3 3 3 3 20 20 20 20 GDE GDE GDE GDE QRS QRS QRS QRS T1000 T1000 T1000 T1000 Update Update Update Update P505 P505 P505 P505 3 3 3 3 21 21 21 21 TUV TUV TUV TUV WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  12. An Example PageID PageID PageID recLSN recLSN recLSN P500 P500 P500 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  13. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  14. Outline The Log A Simple Transaction Abort Checkpointing The ARIES Algorithm

  15. A Simple Transaction Abort For now, let us consider an explicit abort of a transaction T That is, no system crash is involved We want to play back the log in reverse order, undoingT s updates Step 1: We get the lastLSN of T from the Transaction table Step 2: We lock the corresponding data to be undone (we can use strict 2PL)

  16. A Simple Transaction Abort (Contd) Step 3: Before restoring an old value of a page, we write a respective Compensation Log Record (CLR) CLR has one extra field, that is, undoNextLSN, which points to the next LSN to undo undoNextLSN is assigned the prevLSN of the record that is currently being undone CLRs are never undone (but they might be Redone) Step 4: Repeat steps 2 and 3 by following a chain of log records backward via the undoNextLSN field Last Step: At the end of UNDO, write an end log record

  17. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Let us assume T1000 is aborted! P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  18. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 1: Get the lastLSN of T1000 from the Transaction table P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  19. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 2: Lock P505 P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  20. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 3: Write CLR P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN LOG T1000 T1000 T1000 T2000 T2000 T2000 Transaction Table

  21. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 3: Write CLR P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 LOG Transaction Table

  22. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 4: Restore old value TUV P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 LOG Transaction Table

  23. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 4: Restore old value TUV P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- P505 P505 P505 P505 Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 LOG Transaction Table

  24. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 4: Restore old value TUV P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 LOG Transaction Table

  25. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 5: Lock P500 P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 LOG Transaction Table

  26. An Example Note that P500 should NOT be updated by two concurrent & active (not committed yet) transactions if strict 2PL is used. Otherwise, cascaded aborts shall be pursued (i.e., T2000 should be aborted as well). PageID PageID PageID PageID recLSN recLSN recLSN recLSN P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 LOG Transaction Table

  27. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 6: Write CLR P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 Undo T1000- LSN 10 CLR Transaction Table LOG

  28. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 7: Restore old value ABC P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T1000 T2000 T2000 T2000 Undo T1000- LSN 10 CLR Transaction Table LOG

  29. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 7: Restore old value ABC P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T2000 Undo T1000- LSN 10 CLR Transaction Table LOG

  30. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 7: Restore old value ABC P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T2000 Undo T1000- LSN 10 CLR Transaction Table LOG

  31. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 8: Write an end log record P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T2000 Undo T1000- LSN 10 CLR Transaction Table LOG

  32. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN Step 8: Write an end log record P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T2000 Undo T1000- LSN 10 CLR Transaction Table T1000 End- LSN 10 END

  33. An Example PageID PageID PageID PageID recLSN recLSN recLSN recLSN P500 P500 P500 P500 P600 P600 P600 P600 prevLSN prevLSN prevLSN prevLSN prevLSN transID transID transID transID transID Type Type Type Type Type pageID pageID pageID pageID pageID Length Length Length Length Length Offset Offset Offset Offset Offset Before- Before- Before- Before- After- After- After- After- Before- Image Image Image Image Image After- Image Image Image Image Image Dirty Page Table 10 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 21 21 21 21 21 ABC ABC ABC ABC ABC DEF DEF DEF DEF DEF T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P600 P600 P600 P600 P600 3 3 3 3 3 41 41 41 41 41 HIJ HIJ HIJ HIJ HIJ KLM KLM KLM KLM KLM T2000 T2000 T2000 T2000 T2000 Update Update Update Update Update P500 P500 P500 P500 P500 3 3 3 3 3 20 20 20 20 20 GDE GDE GDE GDE GDE QRS QRS QRS QRS QRS 50 T1000 T1000 T1000 T1000 T1000 Update Update Update Update Update P505 P505 P505 P505 P505 3 3 3 3 3 21 21 21 21 21 TUV TUV TUV TUV TUV WXY WXY WXY WXY WXY TransID TransID TransID lastLSN lastLSN lastLSN Undo T1000- LSN 50 CLR T1000 T1000 T2000 Undo T1000- LSN 10 CLR Transaction Table T1000 End- LSN 10 END

  34. Outline The Log A Simple Transaction Abort Checkpointing The ARIES Algorithm

  35. Checkpointing To reduce the amount of work to do during recovery, DBMSs typically take checkpoints A checkpoint is like a snapshotof a DBMS state A checkpoint can be taken by writing to the log: A begin_checkpoint record This indicates the start of the checkpoint An end_checkpoint record This indicates the end of the checkpoint It encapsulates the contents of the transaction table and the dirty page table A master record This contains the LSN of the begin_checkpoint record

  36. Outline The Log A Simple Transaction Abort Checkpointing The ARIES Algorithm

  37. Recovering From a System Crash: ARIES We will study the ARIES algorithm for recovering from system crashes ARIES is designed to work with a steal, no-force approach When the recovery manager is invoked after a crash, restart proceeds sequentially in three phases: Analysis Redo Undo

  38. Recovering From a System Crash: ARIES The Analysis Phase: Identifies dirty pages in the buffer pool and active transactions at the time of the crash Oldest log rec. of Xact active at crash Undo Smallest recLSN in dirty page table after Analysis Redo The Redo Phase: Redoes all actions Analysis The Undo Phase: Undoes the actions of transactions that were active and did not commit Last chkpt CRASH

  39. ARIES: The Analysis Phase The Analysis phase performs three tasks: 1. It determines the point in the log at which to start the Redo pass 2. It determines (a conservative superset of the) pages in the buffer pool that were dirty at the time of the crash 3. It identifies transactions that were active at the time of the crash and must be undone

  40. ARIES: The Analysis Phase More precisely, the Analysis phase proceeds as follows: It examines the most recent begin_checkpoint log record It locates the corresponding end_checkpoint log record and initializesthe dirty page table and transaction table from its content It scans the log in the forward direction till its end and reconstructsalong the way the dirty page table and transaction table (bringing them back to almost how they looked just before the crash)

  41. ARIES: The Analysis Phase More precisely, the Analysis phase proceeds as follows: In particular, while scanning the log: If an end log record is encountered for a transaction T T is removed from the transaction table If a different log record (say, L) is encountered for a transaction T If L is an update log record affecting page P Add entry, E, for P in the dirty page table (if it is not already there) Set E s recLSN to the LSN of L Add an entry, Q, for T in the transaction table (if it is not already there) Set the lastLSN field in Q to the LSN of L Set the status field in Q to C if L is a commit record, or to U otherwise (i.e., indicating T should be undone)

  42. ARIES: The Redo Phase During the Redo phase, ARIES reapplies the updates of all transactions (i.e., committed and aborted) This paradigm is referred to as Repeating History The Redo phase scans forward until the end of the log, and redoes every action unless: The affected page is not in the dirty page table The affected page is in the dirty page table , but its recLSN > the current record s LSN The pageLSN of the affected page >= the current record s LSN Wouldn t checking this be enough?

  43. ARIES: The Redo Phase During the Redo phase, ARIES reapplies the updates of all transactions (i.e., committed and aborted) This paradigm is referred to as Repeating History The Redo phase scans forward until the end of the log, and redoes every action unless: The affected page is not in the dirty page table The affected page is in the dirty page table , but its recLSN > the current record s LSN The pageLSN of the affected page >= the current record s LSN YES, but it requires retrieving the page from the disk, thus made last!

  44. ARIES: The Redo Phase If the logged action must be redone: The logged action is reapplied The pageLSN on the page is set to the LSN of the redone log record No additional record is written at this time!

  45. ARIES: The Undo Phase This phase will undo the actions of all transactions that were active before the crash These transactions are referred to as loser transactions and were identified by the Analysis phase The Undo phase: Considers the set of lastLSN values for all loser transactions This is denoted as the ToUndoset Repeatedly chooses the largest (i.e., the most recent) LSN value in ToUndo and processes it, until ToUndo is empty

  46. ARIES: The Undo Phase In particular, the Undo phase proceeds as follows: Repeat: Choose largest LSN among ToUndo If this LSN is a CLR and undoNextLSN==NULL Write an End record for this Xact If this LSN is a CLR, and undoNextLSN != NULL Add undonextLSN to ToUndo Else this LSN is an update Undo the update Write a CLR Assign prevLSN to undoNextLSN and add it to ToUndo Until ToUndo is empty

  47. An Example LSN LOG 00,05 10 20 30 40,45 50 60 begin_checkpoint, end_checkpoint update: T1 writes P5 update: T2 writes P3 T1 abort CLR: Undo T1 LSN 10, T1 End update: T3 writes P1 update: T2 writes P5 CRASH, RESTART CLR: Undo T2 LSN 60 CLR: Undo T3 LSN 50, T3 end CRASH, RESTART CLR: Undo T2 LSN 20, T2 end prevLSN undoNextLSN 70 80,85 90

  48. Additional Crash Issues What happens if the system crashes while Restart is in the Analysis phase? All the work done is lost! On a second Restart, the Analysis phase starts afresh What happens if the system crashes while Restart is in the Redo phase? Restart starts again with the Analysis phase then the Redo phase

  49. Summary Recovery Manager guarantees Atomicity & Durability WAL is used to allow STEAL/NO-FORCE without sacrificing correctness LSNs identify log records; linked into backwards chains per transaction (via prevLSN) pageLSNs allow comparisons of data pages and log records

  50. Summary Checkpointing: A quick way to limit the amount of log to scan on recovery Recovery works in 3 phases: Analysis: Forward from checkpoint Redo: Forward from oldest recLSN Undo: Backward from end to first LSN of oldest transaction alive at crash Upon Undo, write CLRs Redo repeats history : Simplifies the logic!

Related


Missouri State Highway Patrol - Uniform Crash Report Training Overview

Missouri State Highway Patrol - Uniform Crash Report Training Overview

jill
Best 24 Hour Car Recovery in Firswood

Best 24 Hour Car Recovery in Firswood

Parker1
Survive Winter Plane Crash - Team Problem Solving Game Overview

Survive Winter Plane Crash - Team Problem Solving Game Overview

smith
Crash Investigation Procedures

Crash Investigation Procedures

odin
Empowering Recovery Allies: A Comprehensive Training Overview

Empowering Recovery Allies: A Comprehensive Training Overview

cinnamon
Crash Carts and Their Importance in Medical Emergencies

Crash Carts and Their Importance in Medical Emergencies

kalila
Guam Joint Recovery Office Overview

Guam Joint Recovery Office Overview

aurelie
The Role of Corps Safety Engineering Office in Enhancing Road Safety

The Role of Corps Safety Engineering Office in Enhancing Road Safety

tanaquil
Database Backup and Recovery Models Explained

Database Backup and Recovery Models Explained

amna
Empowerment Through Education: Mayo Recovery College Workshop

Empowerment Through Education: Mayo Recovery College Workshop

jazmin
Lifeline Peer Project: Raising Awareness for Recovery Services

Lifeline Peer Project: Raising Awareness for Recovery Services

anson
Recovery Support Services and Building Recovery Capital

Recovery Support Services and Building Recovery Capital

lucian
Assessment of Cost Recovery Methodology Alignment with General Assembly Resolution 67-226

Assessment of Cost Recovery Methodology Alignment with General Assembly Resolution 67-226

aza_sol
Fast Crash Recovery in RAMCloud - Overview and Architecture

Fast Crash Recovery in RAMCloud - Overview and Architecture

victorian_e
Windows Azure Recovery Services Overview

Windows Azure Recovery Services Overview

waer286
KYTC District 6 Great Eight Incident Management Task Force Meeting Recap

KYTC District 6 Great Eight Incident Management Task Force Meeting Recap

dracel
Report on Effective Cost Recovery Rates by UNDP for 2014-2017

Report on Effective Cost Recovery Rates by UNDP for 2014-2017

nric
Development of Crash Severity Models for Highway Safety Manual

Development of Crash Severity Models for Highway Safety Manual

acrid
Impact of Vehicle Mix on Crash Frequency and Severity

Impact of Vehicle Mix on Crash Frequency and Severity

jaos859
Health Impact Assessments for Natural Disaster Recovery

Health Impact Assessments for Natural Disaster Recovery

victori
Asset Recovery Practices in England and Wales: Criminal vs. Civil Proceedings

Asset Recovery Practices in England and Wales: Criminal vs. Civil Proceedings

jola923
Estate Recovery in Wisconsin: A Comprehensive Guide

Estate Recovery in Wisconsin: A Comprehensive Guide

jalva

More Related Content