ARIES Recovery Phases

The ARIES Three-Phase Protocol: An Overview

ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) is celebrated for its correctness and robustness, particularly its ability to recover even if a crash occurs during the recovery process itself. It achieves this through a carefully orchestrated, three-phase protocol that runs after the database system restarts from a crash.

The three phases are:

1. Analysis: Scans forward through the log to figure out the state of the system at the moment of the crash.
2. Redo: Scans forward to "repeat history," ensuring the database state on disk reflects all changes up to the crash, including those from uncommitted transactions.
3. Undo: Scans backward to remove the changes made by any "loser" transactions (those that were active but not committed at the time of the crash).

The diagram below provides a visual map of the recovery process. Think of it as a timeline of the Write-Ahead Log (WAL), where time flows from top to bottom. The recovery process uses this log to navigate through time.

To get a concise, formal definition of each phase, let's turn to the CMU lecture notes.

A Walkthrough of the ARIES Phases

Now that you have a high-level map, let's see the protocol in action. The following video from CMU's Introduction to Database Systems provides a clear, conceptual walkthrough of the three phases, explaining the purpose and direction of each step.

Dissecting Each Phase

The video gave us a great dynamic overview. Now, let's solidify our understanding by examining the goal and process of each phase more closely, using a technical blog post that you might find useful for review.

Let's recap the key points from the video and the blog post for each phase.

Phase 1: Analysis

• Goal: To determine which transactions had committed, which were in-flight ("losers"), and which pages might have been dirty in the buffer pool at the time of the crash.
• Process:
  1. Start at the BEGIN_CHECKPOINT record of the last successful checkpoint (found via the Master Record).
  2. Scan forward to the end of the log.
  3. Use the CHECKPOINT record's ATT and DPT as a starting point.
  4. Update the ATT and DPT based on the log records encountered. For example, add new transactions to the ATT, change their status to COMMIT upon seeing a commit record, and add pages to the DPT upon seeing an update.
• Result: A final version of the Active Transaction Table (ATT) and the Dirty Page Table (DPT) that accurately reflects the state at the moment of the crash.

Phase 2: Redo

• Goal: To "repeat history," ensuring the database on disk is brought to the exact state it was in at the moment of the crash.
• Process:
  1. Find the smallest recLSN (Recovery LSN) among all pages in the DPT. This identifies the earliest log record of a change that might not have made it to disk. This is the starting point for the Redo phase.
  2. Scan forward from this starting LSN to the end of the log.
  3. For each UPDATE or CLR record, check if the change is already reflected on the page on disk (by comparing the page's pageLSN with the log record's LSN).
  4. If the change is not on disk, re-apply it (i.e., redo the operation).
• Crucial Principle: This phase is simple and robust because it re-applies changes from all transactions—winners and losers alike. This ensures that any effects of aborted transactions that were on disk are correctly restored before we attempt to undo them.

Phase 3: Undo

• Goal: To reverse all changes made by "loser" transactions (those still in the ATT with a non-committed status after the Analysis phase).
• Process:
  1. Identify the set of loser transactions from the ATT.
  2. Scan backward from the end of the log.
  3. For each log record belonging to a loser transaction, write a Compensation Log Record (CLR) to the log, and then apply the undo operation (using the before-image from the original UPDATE record).
  4. The lastLSN in the ATT and the prevLSN in each log record allow for efficiently traversing only the relevant records for each loser transaction.
• Crucial Principle: By logging the undo operations as CLRs, ARIES ensures that if a crash happens during recovery, the system won't undo the same operation twice. The CLRs will simply be redone in the next recovery attempt.

Conclusion

You have now seen the high-level architecture of ARIES recovery. By orchestrating these three phases—Analysis, Redo, and Undo—the system can reliably restore a consistent database state after any failure, fulfilling its promise of atomicity and durability.

Key Takeaways:

• Analysis: Scans forward from the last checkpoint to identify winner/loser transactions and dirty pages. Its goal is to build a map for the other two phases.
• Redo: Scans forward from the oldest potentially unpersisted change, repeating history to bring the database to its exact state at the time of the crash.
• Undo: Scans backward from the end of the log, reversing the actions of all loser transactions and writing Compensation Log Records (CLRs) to log these reversals.

Preview of the Next Lesson

We have described what the phases do. In the upcoming lessons, we'll focus on how they do it. We will take a sample log file and manually perform the Analysis phase, reconstructing the Active Transaction Table and Dirty Page Table just as the database would. This will turn these abstract concepts into a concrete, step-by-step procedure.