Undoing Incomplete Transactions

After a system crash, the ARIES recovery algorithm has completed two critical phases: the Analysis Phase has reconstructed the system state at the time of failure, and the Redo Phase has replayed all logged operations to bring the database to its pre-crash state. But there's a fundamental problem remaining: some transactions were still active when the crash occurred.

These incomplete transactions—sometimes called "loser transactions"—represent a serious threat to database consistency. They may have modified data that they never committed, violating the atomicity guarantee: either all of a transaction's changes should be visible, or none of them should be. The Undo Phase exists to solve this problem by systematically reversing every change made by transactions that never reached the commit point.

To understand why the undo phase is essential, we must first understand what happens during normal database operation and what state the database may be in after a crash.

The Steal Policy Problem:

ARIES uses a steal buffer management policy, which means dirty pages (pages modified by uncommitted transactions) can be written to disk before the transaction commits. This is done for performance reasons—waiting to flush all dirty pages until commit would create significant I/O bottlenecks.

However, this policy creates a critical challenge: after a crash, the disk may contain modifications from transactions that never committed. These "uncommitted changes on disk" must be removed to maintain atomicity.

The Chain of Reasoning:

1. Redo is blind: The redo phase replays ALL logged operations, regardless of transaction outcome. This ensures no committed work is lost, but it also means uncommitted changes get replayed.

2. Uncommitted changes violate atomicity: After redo, the database may contain partial results from transactions that never finished. These partial results could be seen by future transactions, violating isolation and consistency.

3. Undo restores atomicity: By reversing all changes from uncommitted transactions, the undo phase ensures the database state reflects only complete, committed transactions.

This is the fundamental contract of undo: erase all evidence that an uncommitted transaction ever existed.

The term "loser transaction" refers to any transaction that was active at the time of the crash and did not have a commit record in the log. Identifying these losers is straightforward because the analysis phase has already built the Transaction Table (TT) that tracks the state of all transactions.

How Losers are Identified:

During the analysis phase, ARIES scans the log from the most recent checkpoint to the end, updating the transaction table as it encounters:

• Begin records: Add transaction to the table with status ACTIVE
• Update records: Update lastLSN for the transaction
• Commit records: Change status to COMMITTED, then remove from table (or mark as complete)
• Abort records: Change status to ABORTING
• End records: Remove transaction from table entirely

At the end of analysis, any transaction remaining in the table with status ACTIVE or ABORTING is a loser that needs to be undone.

The UndoNextLSN Field:

This critical field in the transaction table tracks undo progress. For a transaction that was simply active (never started aborting), UndoNextLSN equals LastLSN—we start from the most recent operation and work backward.

For a transaction that was already aborting when the crash occurred, UndoNextLSN may point somewhere in the middle of the log record chain, indicating how far the undo had progressed before the crash. This is essential for avoiding redundant work and ensuring correctness.

When the undo phase begins, it constructs a loser set from the transaction table—the set of all transactions requiring undo. But how should these transactions be processed? ARIES makes a crucial design decision here: rather than processing each loser transaction sequentially, it processes them in parallel through a single backward pass of the log.

Why Parallel Processing Matters:

Consider a scenario with three loser transactions that each modified different pages at different times. Sequential processing would require:

• Walk T1's log chain backward (many disk seeks)
• Then walk T2's log chain backward (more disk seeks)
• Then walk T3's log chain backward (more disk seeks)

Instead, ARIES processes ALL losers in a single backward scan, undoing operations in reverse LSN order regardless of which transaction performed them.

In the diagram above:

• Red records are update records from loser transactions that need undoing
• Green records are commit records (transactions T1, T5 are winners)
• Yellow is an existing CLR (T4 was already aborting)
• Teal records are transaction begin records

Single Backward Pass Efficiency:

ARIES maintains a ToUndo set containing the UndoNextLSN for each loser. It repeatedly:

1. Picks the maximum LSN from ToUndo
2. Reads that log record
3. Either undoes it (if it's an update) or skips (if it's a CLR)
4. Updates ToUndo with the appropriate next pointer
5. Continues until ToUndo is empty

This approach minimizes random I/O by processing the log in order.

When the undo phase encounters an update log record from a loser transaction, it must reverse the effect of that update. This process involves several coordinated steps:

Step 1: Read the Log Record

Each update log record contains:

• TransactionID: Which transaction performed the update
• PageID: Which database page was modified
• PrevLSN: Previous log record for this transaction
• BeforeImage: The value before the update (for undo)
• AfterImage: The value after the update (for redo)
• Additional metadata (record ID, offset, length, etc.)

Step 2: Apply the Before Image

To undo an update, we restore the data to its before-image value. This is conceptually simple but requires care:

• The page must be latched (locked in memory) during the update
• The page's PageLSN might be examined (though undo is unconditional)
• The before-image is written to the appropriate location on the page

Step 3: Write a Compensation Log Record (CLR)

Critically, every undo operation is itself logged. This CLR serves multiple purposes:

• Makes the undo operation durable (if we crash during undo, we can redo the CLR)
• Tracks progress (the undoNextLSN field says what's left to undo)
• Avoids duplicate work on subsequent crashes

We'll explore CLRs in depth on the next page.

Step 4: Update Page and Transaction Metadata

After the undo:

• The page's PageLSN is updated to the CLR's LSN
• The transaction table's undoNextLSN advances to the previous record
• The transaction table's lastLSN updates to point to the CLR

Not all log records encountered during the backward scan require the same handling. The undo phase must distinguish between several types:

Update Records (Need Undo): These are the primary targets of the undo phase. Each update record from a loser transaction must be reversed by applying the before-image and writing a CLR.

CLR Records (Do Not Re-Undo): Compensation log records represent undos that already happened. When encountered, we don't undo them again—that would undo the undo! Instead, we follow the CLR's undoNextLSN to continue the undo chain from where it left off.

Begin Records (Transaction Complete): When we reach a transaction's begin record, that transaction's undo is complete. We write an END record and remove the transaction from the loser set.

The undo phase operates while the database is being recovered—it's not yet open for normal operations. However, maintaining consistency during this phase is still critical because crashes can occur during recovery itself.

The Crash-During-Recovery Problem:

Imagine we're halfway through undoing a transaction when power fails again. What happens?

1. On the next restart, we run the full ARIES recovery again
2. Analysis phase sees the incomplete transaction (still in the log as active)
3. Redo phase replays all operations, including the CLRs we wrote before the second crash
4. Undo phase resumes, but now the CLRs tell us how far we got

The system correctly continues from where it left off, without re-undoing operations that were already undone.

The Role of the END Record:

When a transaction's undo is complete—either by reaching its BEGIN record or by processing a CLR with null undoNextLSN—an END record is written to the log. This serves as definitive proof that the transaction has been fully rolled back.

The END record is important for log truncation: once a transaction's END record is written, all of its log records (including CLRs) are eligible for eventual removal. Without END records, the system couldn't determine which portions of the log are safe to reclaim.

Concurrent Undo Considerations:

While the basic ARIES undo is single-threaded (one backward scan), some implementations parallelize undo by assigning different loser transactions to different worker threads. This requires careful coordination:

• Different transactions should access different pages (or use latching)
• CLR writing must still be serialized to maintain LSN order
• The transaction table must be thread-safe

The undo phase terminates when the ToUndo set becomes empty, meaning every loser transaction has been fully rolled back. At this point:

Database State:

• All modifications from committed transactions are present
• All modifications from uncommitted transactions have been reversed
• The database reflects a consistent state as if only committed transactions ever ran

Log State:

• Contains END records for all loser transactions
• Contains CLRs documenting all undo operations
• Is ready for normal operation and future checkpointing

System State:

• Transaction table is empty (or contains only committed entries)
• Dirty page table reflects current buffer pool state
• The system can begin accepting new transactions