ARIES Crash Recovery: Problem and Solution

Problem Statement

A DBMS uses the ARIES algorithm for system recovery. The latter part of the log file after a system crash is shown below. This part of the log consists of 11 log records with LSNs from 1002 to 1012.

The figure does not show the PrevLSN and UndoNextLSN fields in the log records. The last completed checkpoint is the log record with LSN 1009.

ARIES supports the steal policy, which means that dirty pages may be written to disk whenever the buffer manager or a background flushing process considers it appropriate, regardless of whether the transactions that modified those pages have committed.

Log Records

1002: <T1, 6001.1, 11, 22>
1003: <T2 begin>
1004: <T2, 6001.2, 33, 44>
1005: <T3 begin>
1006: <T3, 6002.1, 55, 66>
1007: <T1 commit>
1008: <T2, 6001.3, 88, 99>

1009: checkpoint

Transaction Table:
| Transaction | LastLSN |
|-------------|---------|
| T2          | 1008    |
| T3          | 1006    |

Dirty Page Table:
| PageID | PageLSN | RecLSN |
|--------|---------|--------|
| 6001   | 1008    | ?      |
| 6002   | 1006    | 1006   |

1010: <T3, 6002.2, 66, 77>
1011: <T3, 6003.1, 11, 22>
1012: <T2 commit>

Answer the following questions.

Question 1

What are the possible values of RecLSN for page 6001 in the Dirty Page Table?

A) 1002
B) 1004
C) 1008
D) An LSN less than 1002
E) 1009

Question 2

During the analysis phase, which of the following disk data pages will be read into the buffer?

A) 6001
B) 6002
C) 6003
D) None of the above
E) None, some, or all of the above

Question 3

During the redo phase, which of the following disk data pages will be updated?

A) 6001
B) 6002
C) 6003
D) None of the above
E) None, some, or all of the above

Question 4

During the undo phase, which of the following disk data pages will be updated?

A) 6001
B) 6002
C) 6003
D) None of the above
E) None, some, or all of the above

---

Solution

Key ARIES Concepts

ARIES normally uses:

steal + no-force

These terms mean:

• Steal: A dirty page may be written to disk even if it contains updates made by an uncommitted transaction.

• No-force: When a transaction commits, its modified data pages do not have to be written to disk immediately.

• WAL — Write-Ahead Logging: Before a dirty data page is written to disk, the corresponding log records must already be persistent.

• PageLSN: The LSN of the latest update already reflected in a page.

• RecLSN: The earliest LSN that may not yet have been written to disk for a dirty page.

A transaction commit guarantees that the relevant log records are durable. It does not guarantee that the updated data pages have already been written to disk.

---

Question 1: Possible RecLSN Values for Page 6001

The updates to page 6001 are:

1002: <T1, 6001.1, 11, 22>
1004: <T2, 6001.2, 33, 44>
1008: <T2, 6001.3, 88, 99>

At checkpoint LSN 1009, the Dirty Page Table contains:

PageID = 6001
PageLSN = 1008
RecLSN = ?

The buffer-pool version of page 6001 contains all updates up to LSN 1008. However, because the DBMS supports the steal policy, page 6001 may have been flushed to disk at different times.

Possible cases include:

Scenario	Possible RecLSN
Page 6001 became dirty at LSN 1002 and was not flushed afterward	1002
Page 6001 was flushed after LSN 1002, then became dirty again at LSN 1004	1004
Page 6001 was flushed after LSN 1004, then became dirty again at LSN 1008	1008
Page 6001 was already dirty before the displayed log fragment began	An LSN less than 1002

LSN 1009 cannot be the RecLSN, because it is a checkpoint record rather than an update to page 6001.

Answer

A, B, C, and D

---

Question 2: Pages Read During the Analysis Phase

The analysis phase scans log records to reconstruct:

• the Transaction Table;

• the Dirty Page Table;

• the set of winner and loser transactions.

It does not need to read disk data pages.

Starting from the checkpoint at LSN 1009, the analysis phase scans:

1010: <T3, 6002.2, 66, 77>
1011: <T3, 6003.1, 11, 22>
1012: <T2 commit>

At LSN 1011, page 6003 is added to the Dirty Page Table:

PageID	RecLSN
6003	1011

However, this update to the Dirty Page Table does not require reading page 6003 from disk.

Answer

D) None of the above

---

Question 3: Pages Updated During the Redo Phase

After the analysis phase, the Dirty Page Table contains at least:

PageID	RecLSN
6001	Unknown
6002	1006
6003	1011

The redo phase begins at:

RedoLSN = minimum RecLSN in the Dirty Page Table

Because the RecLSN of page 6001 is unknown, the exact redo starting point cannot be determined uniquely.

The redo pass repeats history, including updates made by transactions that later turn out to be losers.

For each update log record, ARIES applies the following logic:

if page is not in the Dirty Page Table:
    skip the log record

else if log_record.LSN < DirtyPageTable[page].RecLSN:
    skip the log record

else:
    read the disk page

    if disk_page.PageLSN >= log_record.LSN:
        skip the log record
    else:
        redo the update

The relevant updates are:

6001:
    1002: <T1, 6001.1, 11, 22>
    1004: <T2, 6001.2, 33, 44>
    1008: <T2, 6001.3, 88, 99>

6002:
    1006: <T3, 6002.1, 55, 66>
    1010: <T3, 6002.2, 66, 77>

6003:
    1011: <T3, 6003.1, 11, 22>

The exact disk PageLSN values are not provided. Therefore:

• none of the pages may need to be updated;

• some of the pages may need to be updated;

• all of the pages may need to be updated.

Answer

E) None, some, or all of the above

---

Question 4: Pages Updated During the Undo Phase

At the time of the crash:

Transaction	Status	Undo Required?
T1	Committed at LSN 1007	No
T2	Committed at LSN 1012	No
T3	Uncommitted	Yes

Only loser transactions are rolled back during the undo phase.

T3 performed the following updates:

1006: <T3, 6002.1, 55, 66>
1010: <T3, 6002.2, 66, 77>
1011: <T3, 6003.1, 11, 22>

Undo proceeds in reverse LSN order:

undo 1011: page 6003
undo 1010: page 6002
undo 1006: page 6002

Therefore, the undo phase updates pages 6002 and 6003.

Page 6001 is not undone because its updates were made by committed transactions T1 and T2.

Answer

B) 6002
C) 6003

---

Final Answers

Question	Answer
1	A, B, C, D
2	D
3	E
4	B, C

---

Redo Phase Summary

The redo phase follows this general procedure:

1. Compute RedoLSN:
       RedoLSN = minimum RecLSN in the Dirty Page Table

2. Scan the log forward starting from RedoLSN.

3. For each update record or CLR:
       a. Skip it if the page is not in the Dirty Page Table.
       b. Skip it if the record LSN is smaller than the page's RecLSN.
       c. Otherwise, read the page from disk.
       d. Skip it if disk_page.PageLSN >= log_record.LSN.
       e. Otherwise, redo the update.

4. After redo finishes, undo all loser transactions.

The redo phase is called repeat history because it reconstructs the state of the database immediately before the crash, including updates made by uncommitted transactions. Those uncommitted updates are removed afterward during the undo phase.