ARIES Redo for Database Recovery

The ARIES Recovery Roadmap: Phase 2

Let's revisit our recovery roadmap. We've completed Analysis; now we're on to Redo.

1. Phase 1: Analysis - Done! We have the final ATT and DPT.
2. Phase 2: Redo (Our focus today)
   • Goal: "Repeat history." Reapply all updates from a specific point in the log to ensure the database reflects the state at the crash. This includes the effects of uncommitted ("loser") transactions.
3. Phase 3: Undo
   • Goal: "Clean up the mess." Roll back all "loser" transactions.

The Redo Phase: Repeating History

The core principle of the Redo phase is to ensure that all changes recorded in the log are reflected on the data pages on disk. Why is this necessary? Because of the NO-FORCE buffer management policy, a transaction can commit (and its log records flushed to disk) without its modified data pages being flushed. If a crash occurs, those changes exist in the log but not on the data pages. The Redo phase fixes this discrepancy.

Where Does Redo Start?

The Analysis phase gave us the DPT, which contains a recLSN for every page that was dirty at the time of the checkpoint. The Redo phase starts its forward scan of the log from the smallest recLSN found in the DPT.

This LSN represents the earliest point in the log where a change was made to a page that might not have been written to disk. By starting here, we guarantee that we consider every single modification that could possibly be missing from the persisted data pages.

The Redo Algorithm

The Redo algorithm is a single forward pass over the log. Given your experience with C++ and data structures, you can think of it as iterating through a file (the log) and, for each entry, deciding whether to perform an action based on information in a hash table (the DPT) and metadata on the page itself.

For a deeper look into the logic, the following video segment provides a clear and concise explanation.

As you saw in the video, the logic is very specific to ensure changes are applied if and only if they are needed. This makes the Redo process idempotent—running it multiple times has the same effect as running it once, which is critical if the system crashes during recovery.

Here are the rules for redoing an action for a log record with LSN = L:

1. Find the page P affected by the log record.
2. The change is re-applied only if all of the following conditions are true:
   • The page P is present in the DPT constructed during the Analysis phase.
   • The recLSN for page P in the DPT is less than or equal to L.
   • The pageLSN on the actual data page on disk is strictly less than L.

This final check is the most important. If the page's pageLSN is already greater than or equal to L, it means the change from this log record (and possibly later ones) has already been successfully written to the page on disk. There's no need to do it again.

To "redo" an action, the system:

1. Fetches the page P from disk into the buffer pool (if not already there).
2. Applies the "after" value from the log record to the page.
3. Sets the pageLSN of the in-memory page to L.

Crucially, no new log records are generated during this process. We are simply replaying what has already been logged.

A Worked Example

Let's walk through a concrete example to solidify these rules. This document from the University of Washington provides an excellent scenario.

Let's break down the Redo phase from that example:

• Analysis Outcome: The DPT is { (P1, recLSN=1), (P2, recLSN=3) }. The smallest recLSN is 1. The Redo phase starts at LSN 1.
• Log on Disk (after crash): LSN 1 to LSN 5.

Here is the trace of the Redo phase:

• LSN 1: (T1, UPDATE P1)

  • Is P1 in the DPT? Yes.
  • Is recLSN for P1 (1) <= current LSN (1)? Yes.
  • Assume P1 was not flushed, so its pageLSN on disk is old (e.g., 0). Is pageLSN (0) < 1? Yes.
  • Result: Redone. The change to A is applied to page P1.

• LSN 2: (T2, UPDATE P1)

  • Is P1 in DPT? Yes. recLSN is 1. pageLSN is now 1 (from previous step).
  • Is pageLSN (1) < 2? Yes.
  • Result: Redone. The change to B is applied to page P1.

• LSN 3: (T2, UPDATE P2)

  • Is P2 in DPT? Yes. recLSN is 3.
  • The scenario states P2 was flushed to disk after this update. This means the pageLSN on the disk version of P2 is 3.
  • Is pageLSN (3) < 3? No.
  • Result: Skipped. The change is already on disk.

• LSN 4: (T1, UPDATE P2)

  • Is P2 in DPT? Yes. recLSN is 3. pageLSN on disk is 3.
  • Is pageLSN (3) < 4? Yes.
  • Result: Redone. The change to D is applied to page P2.

• LSN 5: (T1, COMMIT) - This is not an update record, so it is skipped in this part of the Redo phase.

At the end of this scan, any transaction with status 'C' (Committed) in the ATT has a TXN-END record written for it. In this case, a TXN-END for T1 is appended to the log.

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

Conclusion

In this lesson, we executed the second crucial phase of ARIES recovery. By "repeating history," the Redo phase ensures the fundamental database promise of durability. Even though a crash occurred, the changes from all committed transactions are now safely reflected in the database state.

Key Takeaways:

• The Redo phase is a forward pass that ensures all logged changes are applied to disk, fulfilling the durability property of ACID.
• It starts from the smallest recLSN in the Dirty Page Table that was constructed during the Analysis phase.
• It re-applies changes for all transactions (winners and losers) to bring the database to its exact state at the moment of the crash.
• The process is idempotent, using the pageLSN on disk to decide whether to skip or re-apply a logged change.

Preview of the Next Lesson

We have successfully restored the database to the state it was in at the moment of the crash. However, this state includes changes from "loser" transactions that never committed. The job isn't done yet. In our next lesson, we will tackle the final step: the Undo phase. We will learn how ARIES rolls back the changes made by these loser transactions, leaving the database in a final, clean, and consistent state.