CS 186 Exam Prep 9

Recovery

Recovery

WAL, Undo Logging, Redo Logging, ARIES

​

Recovery Policies

​

• Steal/No Force
• Steal - Uncommitted transactions can overwrite the most recent committed value of an object on disk
• Necessitates UNDO for Atomicity (all or none of Xact’s operations persist)
• No Force - Don’t have to write all pages modified by a transaction from the buffer cache to disk before committing the transaction
• Necessitates REDO for Durability (not losing results of committed Xacts)
• Harder to enforce atomicity and durability, but gives best performance
• No Steal locks buffer pages from optimal use, but keeps uncommitted changes away from disk (easy atomicity)
• Force necessitates extra writes on commit, but everything is guaranteed to be there (easy durability)

Write-Ahead Logging

​

​

1. Log records must be on disk before the data page gets written to disk.
• How we achieve atomicity
• Can’t undo an operation if data page written before log - don’t know operation happened
2. All log records must be written to disk when a transaction commits.
• How we achieve durability
• We know what operations to redo in case of crash

Undo Logging

• Write log records to ensure atomicity after a system crash:
• <START T>: transaction T has begun
• <COMMIT T>: T has committed
• <ABORT T>: T has aborted
• <T,X,v>: T has updated element X, and its old value was v
• If T commits, then FLUSH(X) must be written to disk before <COMMIT T>
• Force – we can UNDO any modifications if a Xact crashes before COMMIT
• If T modifies X, then <T,X,v> log entry must be written to disk before FLUSH(X)
• Steal – we can UNDO any modifications if a Xact crashes before FLUSH

Recovery with Undo Log

• Determine which txns are completed
• Undo all modifications made by incomplete txns
• Recovery manager must:
• Read log from the end:
• Actions to perform on records:
• <T, X, v>: if T is not completed� then write X=v to disk� else ignore (T would have committed or aborted)

​

• How far back in the log should we go?
• All the way to the start (there could be a very long transaction)

​

6

Undo Log Example

Redo Logging

• Write log records to ensure durability after a system crash:
• <START T>: transaction T has begun
• <COMMIT T>: T has committed
• <ABORT T>: T has aborted
• <T,X,v>: T has updated element X, and its new value was v
• If T modifies X, then both <T,X,v> and <COMMIT T> must be written to disk before FLUSH(X)
• No-Steal, No-Force – we can REDO any modifications if a Xact crashes before FLUSH

Recovery with Redo Log

• Determine which txns are completed
• Redo all updates of committed transactions
• Recovery manager must:
• Read log from the beginning:
• Actions to perform on records:
• <T, X, v>: if T is committed� then write X=v to disk� else ignore (T either aborted or was not committed)

9

Redo Log Example

Undo/Redo Logging Summary

• Undo logging:
• Uses Steal/Force policies
• Undoes all updates for running transactions
• Redo logging:
• Uses No Steal/No Force policies
• Redoes all updates for committed transactions

​

Aries Recovery - LSNs

​

​

• LSN (Log Sequence Number): stored in each log record. Unique, increasing, ordered identifier for each log record
• flushedLSN: stored in memory, keeps track of the most recent log record written to disk
• pageLSN: LSN of the last operation to update the page (in memory page may have a different pageLSN than the on disk page)
• prevLSN: stored in each log record, the LSN of the previous record written by the current record’s transaction
• lastLSN: stored in the Xact Table, the LSN of the most recent log record written by the transaction
• recLSN: stored in the DPT, the log record that first dirtied the page since the last checkpoint
• undoNextLSN: stored in CLR records, the LSN of the next operation we need to undo for the current record’s transaction

Recovery Structures

​

​

• Transaction Table - stores information on active transactions. Fields include
• Xid (Transaction ID)
• Status (Running, Committing, Aborting)
• lastLSN
• Dirty Page Table (DPT) - tracks dirty pages (pages whose changes have not been flushed to disk)
• pageID
• recLSN

Record Types

​

​

​

• Records have LSN, common fields include xid (transaction ID), pageID (for modified page), type
• UPDATE - write operation (SQL insert/update/delete). Also includes fields for offset (where data change started), length (how much data was changed), old_data (old version of changed data - used for undos), new_data (updated version of data - used for redos)
• COMMIT - Xact is beginning committing process (ARIES: flush log up to and including COMMIT record)
• ABORT - Xact is beginning aborting process (ARIES: begin writing CLRs for undone UPDATEs)
• Compensation Log Record (CLR) - indicates a given UPDATE has been undone
• END - Xact is finished (as in, finished committing or aborting)

Record Types (cont.)

​

​

​

​

• Checkpoint Records
• Useful for ARIES analysis so we don’t start from very beginning of log
• Checkpoint serves as snapshot of Xact Table/DPT
• Fuzzy checkpoints - Xacts operating during checkpoint; Xact
• BEGIN CHECKPOINT - checkpoint start, earliest point Xact Table/DPT could represent
• END CHECKPOINT - checkpoint end, holds Xact Table/DPT snapshot
• Master Record - stores location of most recent checkpoint for recovery purposes, usually LSN 0

ARIES: Analysis (Part 1)

​

​

​

​

​

• Reconstructing Xact Table and DPT
• Need to know which transactions started/committed/aborted, which pages dirtied
• Start from begin checkpoint log record (or start of log), go until end of log
• On any record that is not an END record:
• Add the Xact to the Xact Table if not in table
• Set the lastLSN of the transaction to the current operation’s LSN
• If the record is a COMMIT or an ABORT record, change the status of Xact to Committing/Aborting
• If the record is an UPDATE record and the page being updated is not in the DPT, add the page to the DPT and set recLSN equal to the LSN
• If the record is an END record, remove the transaction from the Xact table.

ARIES: Analysis (Part 2)

​

​

​

​

​

​

• After going through the log, clean up the Xact Table
• For each Xact in the Xact Table:
• Write END records for committing Xacts. Because they’re committing, they must be finished - preserve durability
• For running Xacts, change status to aborting and write ABORT record - preserve atomicity since not finished

ARIES: Redo

​

​

​

​

​

​

​

• Redo updates and CLRs from the earliest recLSN in the DPT to get back unflushed changes from before crash, unless:
• page not in DPT
• page on disk must be up to date, since we have no changes!
• recLSN of page > LSN
• no need to undo here: recLSN of page is first record that dirtied page, so this change must have been flushed
• pageLSN (disk) >= LSN
• page LSN for disk (LSN of last record with change written to disk) is the authoritative source for determining which changes have been applied in disk
• Redo with after-image (redo state), update pageLSNs as you go

ARIES: Undo

​

​

​

​

​

​

​

• Undo each Xact in the Xact Table
• Only UNDO updates (ignore CLRs)
• Start at end of log and work backwards to the beginning
• For every UPDATE the undo phase undoes, write a corresponding CLR to the log.
• undoNextLSN stores the LSN of the next operation to be undone for that transaction (the prevLSN of the operation that you are undoing).
• Once you have undone all the operations for a transaction, write the END record for that transaction to the log.

ARIES: Overall

​

​

​

​

​

​

​

• Why does redo happen before undo?
• If failure happens during redo or undo, next recovery can pick up what previous recovery has left and continue
• E.g. Crash while writing CLRs in UNDO, we have to redo them
• When are transactions removed from the xact table?
• END log record
• When is a page removed from the DPT?
• When that page flushed to disk (pages aren’t necessarily flushed to disk on commit - no force)

ARIES Recovery Summary

1. Analysis

​

Goal: Rebuild the Xact Table and DPT at time of crash

Start at LSN after begin_checkpoint

If record != END

- Add xact to Xact Table if not there

- Set lastLSN of xact to record.LSN

If record = COMMIT or record = ABORT

- Change status in Xact Table accordingly

​

If record = UPDATE and record.page NOT IN DPT

- Add to DPT & Set recLSN to record.LSN in DPT

​

If record = END

- Remove xact from Xact Table

At the end:

If transaction is Committing

- Write END record and remove from Xact Table

If transaction is Running

- Write ABORT record and change status to Aborting

​

​

2. Redo

Goal: Maintain durability by getting back unflushed changes from before the crash

​

Redo everything from the earliest recLSN unless:

​

Page not in DPT

- Page on disk must be up to date, since we have no changes!

recLSN of page > LSN

- No need to redo here: recLSN of page is first record that dirtied page, so this change must have been flushed

On-Disk pageLSN >= LSN

- On-Disk Page LSN is the authoritative source for determining which changes have been applied already

​

​

3. Undo

Goal: Maintain atomicity by undoing any operations done by transactions running at the time of the crash

​

For all xacts in xact table not committing, change status to abort

​

Start from largest lastLSN in transaction table and work your way up the log.

- Write the relevant CLRs for any actions done by aborting transactions

For CLRs:

- prevLSN = lastLSN of associated transaction

- undoNextLSN = current record’s prevLSN

​

Performance optimization:

- Make a set containing the last undoNextLSN of each transaction (or lastLSN if no CLRs written for transaction yet)

- Undo the largest LSN, repeat

​

​

​

Worksheet

Conceptual Recovery

Question 1

Consider a scenario where we update the recLSN in the dirty page table to reflect each update to a page, regardless of when the page was brought into the buffer pool. What bugs might you see after recovery? Select all that apply. Explain your reasoning:

• Some writes of committed transactions would be lost.
• Some writes of aborted transactions would be visible in the database.
• The system tries to commit or abort a transaction that is not in the transaction table.

​

Answer: a, b.

• A is correct because during the REDO phase of recovery, some UPDATE log records that reflect writes that never made it to disk will be skipped.
• Similarly, B is correct, because some CLR’s that reflect UNDO’s that never made it to disk will be skipped.
• C is incorrect because even if REDO begins at a later LSN, the system does not add any new transactions to the transaction table during REDO.

Question 2

Suppose that you are forced to flush pages in the DPT to disk upon making a checkpoint. Which of the following cases are now guaranteed? There is one correct answer. Explain your reasoning.

• We can skip one of the three phases (analysis/redo/undo) completely
• We must start analysis from the beginning of the log
• Redo will start at the checkpoint.
• Redo must start from the beginning of the log
• Undo can start at the checkpoint
• Undo must run until the beginning of the log

​

Answer: c.

In general, we redo everything from the earliest recLSN in the DPT to get back unflushed changes from before crash. Since we can guarantee that all changes up to a checkpoint have been flushed, all unflushed changes from before the crash happened after the checkpoint. Therefore, we can redo starting from the checkpoint.

Question 3

If the buffer pool is large enough that uncommitted data is never forced to disk, is UNDO still necessary? How about REDO? Explain your reasoning.

Answer: UNDO isn’t necessary in terms of undoing operations on disk.

Having a buffer pool large enough to hold all uncommitted data means we don’t have to STEAL (allow an uncommitted transaction to overwrite the most recent committed value of an object on disk). Since all the updates will be sitting in the buffer pool at the time of crash, no changes will be made to disk, so no operations need to be undone. REDO is still necessary. REDO is needed to get back unflushed changes from before the crash. If everything is held in the buffer, this must be redone

Question 4

If updates are always forced to disk when a transaction commits, is UNDO still necessary? Will ARIES perform any REDOs? Explain your reasoning.

Answer: Only UNDO is necessary.

UNDO is necessary because we still have to finish aborting transactions that were in progress and weren’t committing. The updates that these transactions have gotten through so far must be rolled back. As for REDOs, ARIES might perform some redoes because there may be transactions still in progress at the time of a crash, but these will be undone in the UNDO phase.

Recovery Practice

Question 1

What is the latest LSN that this checkpoint is guaranteed to be up-to-date to?

Answer: LSN 50 - the begin-checkpoint record.

Question 2

What do the transaction table and dirty page table look like at the end of analysis, and what log records do we write during analysis?

​

Question 3

The next phase of ARIES is redo. What LSN do we start the redo from?

Answer: LSN 10 - the oldest recLSN in the Dirty Page Table

Question 4

From that record, we will redo the effects of all the following records, except we will not redo certain records. What are the LSNs of the records we do NOT redo?

Answer:

• LSN 20 is not redone; the recLSN of P2 is already higher than 20, so the effects of LSN 20 are already on disk.
• LSN 40 is not redone; page P3 is not in the dirty page table, and thus also already on disk.
• LSNs 50, 70, 80, 100, and 110 are not update operations, so we don’t do anything for them.

Question 5

The last phase of ARIES is undo. What do we do for this phase? Answer this question by writing out the log records that will be recorded for each step. Stop after you write your first CLR record (make sure your CLR record specifies the nextLSN!).

Question 6

You load up the checkpoint. What does the transaction table and dirty page table look like?

Answer: Same as before, we never made another checkpoint!

​

Question 7

You run the analysis phase. What do the transaction table and dirty page look like at the end of analysis?

Question 8

You run the redo phase. In order, what are the LSNs that we redo?

Answer: 10, 30, 60, 90, 120.

Importantly, note that we redid T1 even though it committed, and that we ARE redoing CLRs.

Question 9

Now we run the undo phase. What do we do? (Answer again with the log records that you have to add.)

Attendance Link

​

https://cs186berkeley.net/attendance