ARIES Analysis for Crash Recovery

The ARIES Recovery Roadmap

ARIES recovery is a methodical, three-phase process designed to be restartable even if a crash occurs during recovery itself.

1. Phase 1: Analysis (Our focus today)

   • Goal: Scan the log forward from the last checkpoint to the crash point.
   • Output: Reconstruct the Active Transaction Table (ATT) and Dirty Page Table (DPT) as they were at the moment of the crash. This tells us which transactions need to be undone and which pages might need their changes reapplied.

2. Phase 2: Redo

   • Goal: "Repeat history." Reapply all updates from the log for all transactions (even losers) to ensure the database reflects the state at the crash, including the effects of uncommitted changes that might have been written to disk.

3. Phase 3: Undo

   • Goal: "Clean up the mess." Roll back all "loser" transactions (those that did not commit) in reverse order, writing Compensation Log Records (CLRs) for each change that is undone.

Without a successful Analysis phase, the system has no map to guide the Redo and Undo operations. Let's learn how to draw that map.

The Analysis Algorithm

After a crash, the recovery manager starts the Analysis phase. The process is algorithmic and, given your background, you can think of it as a single forward pass over a file (the log) to build two in-memory hash tables (the ATT and DPT).

Here are the rules:

1. Start: The system finds the LSN of the last successful CHECKPOINT-BEGIN record via a pointer called the MasterRecord. It initializes an empty ATT and an empty DPT.

2. Scan Forward: It scans the log from that checkpoint record to the end (the crash point). For each log record it encounters, it applies the following logic:

   • For any record from a transaction T: If T is not in the ATT, add it with status = U (Undo-candidate). This is the default assumption; a transaction is considered a loser until we see proof otherwise. Update T's lastLSN in the ATT to the LSN of the current record.
   • For an UPDATE record: If the modified page P is not in the DPT, add it. Set P's recLSN to the LSN of this update record, because this is the first change that has made this page dirty since the checkpoint began.
   • For a COMMIT record: Change the status of the corresponding transaction in the ATT to C (Committed).
   • For a TXN-END record: This signifies that a transaction is well and truly finished, and any cleanup is done. We can remove its entry from the ATT.
   • For a CHECKPOINT-END record: This record contains the ATT and DPT as they existed when the checkpoint began. The recovery manager merges this information with the ATT and DPT it is currently building. This is crucial for finding transactions and dirty pages that existed before the checkpoint but were still active.

At the end of this pass, we have a complete picture of the database state at the moment of the crash.

Walkthrough: Analysis in Action

Let's see this algorithm in practice. The following video from CMU's database course provides an excellent, detailed walkthrough of the Analysis phase on a sample log.

To solidify what you just saw, let's trace the example from the video textually.

The Log:

...
010: <CHECKPOINT-BEGIN>
...
020: <T96, UPDATE P33, ...>
...
030: <CHECKPOINT-END ATT={T96,T97}, DPT={P20(recLSN=008)}>
...
040: <T96, COMMIT>
...
050: <T96, TXN-END>
...
CRASH!

The Analysis Trace:

Outcome of the Analysis:

• Active Transaction Table (ATT): The only transaction left is T97, with status U (Undo-candidate). This is our "loser" transaction. Its changes must be rolled back in the Undo phase.
• Dirty Page Table (DPT): Two pages, P33 and P20, were potentially dirty in memory. The Redo phase will need to ensure their changes are on disk. It will start its scan from the smallest recLSN in this table, which is 008.

LSN  Log Record
---  ----------
1    <T1, UPDATE P1, ...>
2    <T2, UPDATE P1, ...>
3    <T2, UPDATE P2, ...>
4    <T1, UPDATE P2, ...>
5    <T1, COMMIT>
CRASH!

Conclusion

In this lesson, you learned how to perform the first and most fundamental phase of ARIES recovery. By systematically scanning the log forward, the Analysis phase acts as a detective, piecing together the state of the database at the exact moment of a crash from the evidence left behind.

Key Takeaways:

• The Analysis phase is a forward pass over the log, starting from the last checkpoint.
• Its purpose is to reconstruct the Active Transaction Table (ATT) and Dirty Page Table (DPT).
• The final ATT identifies which transactions are "losers" (status U) that must be undone.
• The final DPT identifies pages that might not have their latest versions on disk. The smallest recLSN in the DPT determines the starting point for the Redo phase.

Preview of the Next Lesson

We have successfully analyzed the crash scene and have our map: the final ATT and DPT. In the next lesson, we will begin the actual restoration work by executing the Redo phase. You will learn how ARIES uses the DPT to "repeat history," ensuring that all changes up to the crash point—including those from both winner and loser transactions—are correctly applied to the database on disk.