Undo Phase - Learning Module

Loading content...

0/241

Undo Completion

The Final Steps of Recovery

After the backward scan has processed all loser transactions, writing CLRs for each undone operation and following chains to completion, the undo phase enters its final stage. This isn't merely a formality—proper completion ensures the database is truly ready for normal operation and that subsequent recoveries won't repeat work.

The completion phase handles several critical tasks: confirming all losers are fully undone, writing END records, optionally checkpointing to speed future recovery, and finally opening the database for new transactions. Each step must be correct to maintain the guarantees that ARIES provides.

What You Will Learn

By the end of this page, you will understand how the undo phase determines it's complete, the role and importance of END records, what happens between recovery completion and normal operation, post-recovery checkpointing strategies, and how to verify recovery correctness.

Termination Conditions

The undo phase terminates when the ToUndo set becomes empty. This happens when every loser transaction has been fully processed—either by undoing all its operations back to the BEGIN record, or by following CLR chains that indicate previous undo work is complete.

When Does a Transaction Leave ToUndo?

A transaction is removed from the ToUndo set when:

Its PrevLSN becomes null: After undoing the first update (the one right after BEGIN), the prevLSN of that record is null, indicating we've walked back to the start.
A CLR's undoNextLSN is null: If we encounter a CLR whose undoNextLSN is null, this means a previous partial rollback already completed undoing back to BEGIN.
We reach a BEGIN record: Though typically we stop at null prevLSN from an UPDATE, if we explicitly read a BEGIN record, the transaction is done.

termination_check.pseudo

Termination Logic

PROCEDURE ProcessUndoRecord(lsn, txnId, ToUndo, txnTable):
    record = Log.Read(lsn)
    
    IF record.type == UPDATE:
        // Undo the update
        PerformUndo(record)
        WriteCLR(record)
        
        // Determine next step
        IF record.prevLSN == NULL:
            // This was the first update after BEGIN
            // Transaction is fully undone
            FinalizeTransaction(txnId)
        ELSE:
            // More records to undo
            ToUndo.Insert(record.prevLSN, txnId)
            
    ELSE IF record.type == CLR:
        // Already-done undo, follow the shortcut
        IF record.undoNextLSN == NULL:
            // Previous undo reached the beginning
            // Transaction is fully undone
            FinalizeTransaction(txnId)
        ELSE:
            // Continue from where previous undo left off
            ToUndo.Insert(record.undoNextLSN, txnId)
            
    ELSE IF record.type == BEGIN:
        // Reached the transaction start
        FinalizeTransaction(txnId)
 
 
PROCEDURE FinalizeTransaction(txnId):
    // Write END record to mark completion
    Log.Write(END_RECORD, transactionId: txnId)
    
    // Remove from transaction table
    TransactionTable.Remove(txnId)
    
    // Don't add anything to ToUndo
    Log.Info("Transaction {txnId} fully rolled back")
 
 
PROCEDURE IsUndoComplete(ToUndo):
    RETURN ToUndo.IsEmpty()

Invariant at Termination:

When the undo phase completes:

ToUndo set is empty
Transaction table contains no ACTIVE or ABORTING entries
Every loser has an END record in the log
All uncommitted changes have been reversed in the database

This invariant guarantees that the database is consistent and ready for new transactions.

What About Running Transactions Before Crash?

All transactions that were running at crash time are now either: (1) Committed—their changes were preserved during redo and they were never in the loser set, or (2) Rolled back—they were losers, were fully undone during the undo phase, and have END records in the log. There are no "partially completed" transactions.

The END Record

When a loser transaction's undo is complete, an END record is written to the log. This record serves several important purposes:

1. Definitive Rollback Marker:

The END record is proof that the transaction has been fully rolled back. Future analysis phases will see this and know the transaction is completely finished—no further undo is needed.

2. Log Truncation Enabler:

Once a transaction's END record is written and forced to stable storage, all of that transaction's log records become candidates for truncation (assuming checkpoint requirements are met). Without END, the system couldn't be sure the undo was complete.

3. Transaction Lifecycle Closure:

Every transaction follows a lifecycle: BEGIN → [operations] → COMMIT/ABORT → END. The END record closes this lifecycle, whether the transaction committed normally or was rolled back during recovery.

Transaction Lifecycle and Log Records
Phase	Normal Commit	Normal Abort	Recovery (Loser)
Start	BEGIN	BEGIN	BEGIN
Operations	UPDATE, UPDATE, ...	UPDATE, UPDATE, ...	UPDATE, UPDATE, ...
Decision	COMMIT	ABORT	(crash—no decision)
Undo phase	(none needed)	CLR, CLR, ...	CLR, CLR, ...
Completion	END	END	END

end_record_structure.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * END Log Record Structure
 * 
 * Written when a transaction completes, either via commit or rollback.
 * This is the simplest log record type - it just marks completion.
 */
interface EndLogRecord {
    /** Log Sequence Number of this END record */
    lsn: LogSequenceNumber;
    
    /** 
     * Transaction ID that has completed.
     * After this record, no more log records will be written 
     * for this transaction.
     */
    transactionId: TransactionId;
    
    /** Record type identifier */
    recordType: LogRecordType.END;
    
    /**
     * PrevLSN for this transaction.
     * Points to the last CLR (if rolled back) or COMMIT record.
     * May be used for debugging/analysis but not for recovery.
     */
    prevLSN: LogSequenceNumber;
    
    /**
     * Optional: Final status of the transaction.
     * COMMITTED or ABORTED.
     * Not strictly necessary (can be inferred) but useful for tools.
     */
    finalStatus?: 'COMMITTED' | 'ABORTED';
}
 
// Example END record for a rolled-back transaction:
const endRecord: EndLogRecord = {
    lsn: 1500,
    transactionId: 'T42',
    recordType: LogRecordType.END,
    prevLSN: 1495,  // Points to the last CLR
    finalStatus: 'ABORTED'
};

END Record Durability:

The END record must be forced to stable storage before the transaction can be considered truly complete. During recovery, this forcing happens as part of the normal log write path. Some systems batch force multiple END records together for efficiency.

Idempotency:

Writing an END record is idempotent—if we crash after writing END but before some subsequent step, re-recovery will see the END record and know not to process this transaction again. The transaction will simply not appear in the loser set.

END vs COMMIT

COMMIT and END are different records with different purposes. COMMIT indicates the transaction's decision to commit (written during normal operation). END indicates the transaction is completely finished (written after any needed cleanup). A committed transaction has both COMMIT and END. A rolled-back transaction has only END (no COMMIT).

Post-Undo State Verification

After the undo phase completes, production database systems typically perform verification checks to ensure recovery was successful. These checks catch bugs, hardware errors, or corruption that might have occurred during recovery.

Verification Checks:

Transaction Table Audit:
- Should contain no ACTIVE or ABORTING entries
- May contain COMMITTED entries that haven't had END written yet (these get cleaned up)
- Any remaining entries are removed/finalized
Dirty Page Table Consistency:
- Pages in the dirty page table should have valid PageLSNs
- PageLSN values should be consistent with log state
- Optional: flush dirty pages to verify writability
Log Integrity:
- Verify log is not corrupted at the end
- Ensure tail of log is properly terminated
- Optional: checksum verification for log pages

post_undo_verification.pseudo

Verification Procedure

PROCEDURE VerifyUndoCompletion():
    errors = []
    
    // Check 1: No active transactions remain
    FOR EACH (txnId, entry) IN TransactionTable:
        IF entry.status IN {ACTIVE, ABORTING}:
            errors.Add("Transaction {txnId} still in {entry.status} state")
            // Attempt recovery: write END record
            Log.Write(END_RECORD, transactionId: txnId)
            TransactionTable.Remove(txnId)
    
    // Check 2: All loser transactions have END records
    // (This is implicit if we processed ToUndo correctly, but verify anyway)
    FOR EACH loserTxn IN OriginalLoserSet:
        IF NOT Log.HasEndRecord(loserTxn.id):
            errors.Add("Loser {loserTxn.id} missing END record")
    
    // Check 3: Buffer pool consistency
    FOR EACH (pageId, pageEntry) IN DirtyPageTable:
        page = BufferPool.Fetch(pageId)
        IF page.pageLSN < pageEntry.recoveryLSN:
            errors.Add("Page {pageId} has stale LSN")
    
    // Check 4: Database constraint verification (optional, expensive)
    IF Config.VERIFY_CONSTRAINTS_AFTER_RECOVERY:
        FOR EACH table IN Database.Tables:
            IF NOT table.VerifyConstraints():
                errors.Add("Constraint violation in {table.name}")
    
    // Report results
    IF errors.IsEmpty():
        Log.Info("Undo phase verification: PASSED")
    ELSE:
        Log.Error("Undo phase verification: FAILED")
        FOR EACH error IN errors:
            Log.Error("  - {error}")
        // Depending on configuration, may halt or continue
        IF Config.HALT_ON_VERIFICATION_FAILURE:
            RAISE RecoveryVerificationException(errors)
    
    RETURN errors.IsEmpty()

Constraint Verification:

Some databases optionally verify integrity constraints after recovery:

Primary key uniqueness
Foreign key references
Check constraints
Unique index integrity

This is expensive but catches subtle corruption. Most systems skip this for speed, relying on the correctness of the recovery algorithm.

Handling Verification Failures:

If verification fails, the system has several options:

Halt and require manual intervention: Safest, but delays availability
Log warnings and continue: Risky if corruption is serious
Attempt automated repair: Complex and may make things worse
Restore from backup: Last resort if recovery is fundamentally broken

Verification vs Production Speed

Full verification can significantly increase recovery time. Most production systems perform minimal verification (transaction table check) and rely on application-level validation. Critical systems may run full verification in a parallel process while the database comes online in limited mode.

Post-Recovery Checkpoint

After the undo phase completes, many database systems perform a checkpoint before opening for normal operation. This checkpoint captures the current clean state and significantly reduces the work required if another crash occurs.

Why Checkpoint After Recovery?

Reduce future recovery time: The checkpoint sets a new starting point. If we crash immediately after, we start from this checkpoint instead of the old one.
Enable log truncation: Records before the checkpoint (including all the CLRs we just wrote) can potentially be truncated.
Flush dirty pages: The checkpoint process may flush dirty pages, reducing the amount of data that could be lost if another crash occurs immediately.

With Post-Recovery Checkpoint

•Next recovery starts from new checkpoint
•Old log segments can be archived/deleted
•Clean transaction table state captured
•Dirty page table reflects current state
•Recovery time bounded by checkpoint frequency

Without Post-Recovery Checkpoint

•Next recovery starts from old checkpoint
•Must replay all CLRs again during redo
•Log continues to grow
•Recovery time accumulates over crashes
•Potential unbounded recovery work

post_recovery_checkpoint.pseudo

Post-Recovery Checkpoint

PROCEDURE PerformPostRecoveryCheckpoint():
    Log.Info("Performing post-recovery checkpoint...")
    
    // The transaction table should be empty or only have clean entries
    ASSERT TransactionTable.IsEmpty() OR 
           TransactionTable.AllEntriesAre(COMMITTED_AND_ENDED)
    
    // Begin checkpoint record
    checkpointBeginLSN = Log.Write(CHECKPOINT_BEGIN)
    
    // Capture dirty page table
    // (These are pages modified during redo/undo that haven't been flushed)
    dptSnapshot = DirtyPageTable.Snapshot()
    
    // Transaction table should be essentially empty
    ttSnapshot = TransactionTable.Snapshot()
    ASSERT ttSnapshot.IsEmpty()
    
    // Write checkpoint end with DPT snapshot
    checkpointEndLSN = Log.Write(CHECKPOINT_END, 
                                  dirtyPageTable: dptSnapshot,
                                  transactionTable: ttSnapshot)
    
    // Force the checkpoint to stable storage
    Log.Force(checkpointEndLSN)
    
    // Update the master record to point to this checkpoint
    MasterRecord.Update(lastCheckpointLSN: checkpointBeginLSN)
    
    // Optionally, flush some dirty pages now
    IF Config.FLUSH_PAGES_ON_POST_RECOVERY_CHECKPOINT:
        FOR EACH pageId IN dptSnapshot.Keys():
            BufferPool.FlushPage(pageId)
        DirtyPageTable.Clear()
    
    Log.Info("Post-recovery checkpoint complete at LSN {checkpointEndLSN}")
    
    // Now safe to truncate log up to certain point
    oldLogEnd = CalculateSafeTruncationPoint()
    Log.TruncateBefore(oldLogEnd)

Checkpoint Timing Tradeoff:

The post-recovery checkpoint adds time before the database becomes available. Some systems skip it to minimize recovery-to-availability time, accepting potentially longer recovery times if another crash occurs.

Fuzzy vs Sharp Checkpoint:

The post-recovery checkpoint is typically a fuzzy checkpoint—it doesn't require flushing all dirty pages. This is faster but means some dirty pages from redo/undo may still be in the buffer pool. If this is acceptable, recovery-to-availability is faster.

Recovery Checkpoint Best Practice

A common pattern is to perform a quick fuzzy checkpoint immediately after recovery (for log truncation benefits), then schedule a more thorough checkpoint soon after the system comes online (to flush dirty pages and clean up the buffer pool).

Transitioning to Normal Operation

Once undo is complete and any post-recovery tasks are finished, the database transitions to normal operation. This transition involves several steps to ensure the system is ready to accept new transactions safely.

Transition Steps:

Clear recovery mode flag: Internal state changes from RECOVERING to ONLINE
Reset sequence generators: Transaction IDs, LSNs, and other sequences continue from appropriate points
Resume background processes: Checkpointing, buffer pool flushing, statistics collection, etc.
Re-enable client connections: Accept new connections from applications
Process queued requests: Some systems queue connection attempts during recovery

transition_to_normal.pseudo

Transition Procedure

PROCEDURE TransitionToNormalOperation():
    Log.Info("=== TRANSITIONING TO NORMAL OPERATION ===")
    
    // Step 1: Final state validation
    ASSERT ToUndoSet.IsEmpty()
    ASSERT TransactionTable.HasNoActiveTransactions()
    
    // Step 2: Update system state
    SystemState.SetMode(ONLINE)
    SystemState.SetRecoveryComplete(true)
    SystemState.SetRecoveryEndTime(Now())
    
    // Step 3: Initialize transaction ID sequence
    // Next transaction ID should be higher than any seen during recovery
    maxSeenTxnId = Recovery.GetMaxTransactionId()
    TransactionIdGenerator.Initialize(maxSeenTxnId + 1)
    
    // Step 4: Initialize LSN sequence
    // Already correct - we've been appending to log during recovery
    // Just verify it's consistent
    ASSERT Log.GetNextLSN() > Recovery.GetMaxLSN()
    
    // Step 5: Start background processes
    CheckpointDaemon.Start()
    BufferPoolFlusher.Start()
    StatisticsCollector.Start()
    DeadlockDetector.Start()
    
    // Step 6: Enable client connections
    ConnectionManager.AcceptNewConnections()
    
    // Step 7: Process any queued connection requests
    FOR EACH queuedRequest IN ConnectionQueue:
        ConnectionManager.ProcessRequest(queuedRequest)
    
    // Step 8: Notify monitoring systems
    Metrics.RecordEvent("database.recovery.complete", {
        recoveryTimeMs: SystemState.GetRecoveryDuration(),
        loserTransactions: Recovery.GetLoserCount(),
        redoOperations: Recovery.GetRedoCount(),
        undoOperations: Recovery.GetUndoCount()
    })
    
    // Step 9: Log completion
    Log.Info("=== DATABASE ONLINE ===")
    Log.Info("Recovery completed in {SystemState.GetRecoveryDuration()}ms")
    Log.Info("Rolled back {Recovery.GetLoserCount()} transactions")

Gradual vs Immediate Availability:

Some systems offer gradual availability:

Tables/databases recovery independently
High-priority tables come online first
Applications can query recovered portions while recovery continues elsewhere

This is particularly useful for large databases where full recovery might take hours.

Warning: New Transactions During Transition:

Care must be taken that no new transactions begin until the system is truly ready. A premature transaction could:

Conflict with recovery operations
Use transaction IDs that overlap with recovered ones
Access inconsistent data

The Promise Fulfilled

When the database comes online after recovery: (1) All committed transactions' effects are present—durability guaranteed. (2) All uncommitted transactions' effects are absent—atomicity guaranteed. (3) All integrity constraints are satisfied—consistency guaranteed. This is the ARIES promise, fulfilled through the three-phase recovery process.

Measuring Recovery Performance

Understanding recovery performance is critical for capacity planning and ensuring the system meets availability requirements. Key metrics to track:

Recovery Time Metrics:

Total recovery time: From crash detection to database online
Analysis phase time: Time to scan log and build tables
Redo phase time: Time to replay operations
Undo phase time: Time to roll back losers
Post-recovery time: Checkpoint and transition overhead

Factors Affecting Recovery Time
Factor	Affects Which Phase	How to Reduce Impact
Checkpoint frequency	All phases	More frequent checkpoints = less log to process
Number of dirty pages	Redo	More aggressive page flushing reduces redo work
Number of active transactions	Undo	Shorter transactions = fewer losers
Transaction size	Undo	Smaller transactions = faster undo per loser
Log I/O speed	All phases	Faster storage for log files
Buffer pool size	Redo, Undo	Larger pool = more pages cached during recovery
Number of parallel workers	Redo, Undo	Some systems parallelize recovery

Undo Phase Specific Metrics:

Loser count: Number of transactions requiring undo
Total undo operations: Sum of operations across all losers
CLRs written: Number of compensation records created
Pages touched during undo: Measure of I/O for undo
Undo elapsed time per loser: Identify problematic long transactions

recovery_metrics.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * Recovery metrics collected during the undo phase.
 * Used for performance analysis and capacity planning.
 */
interface UndoPhaseMetrics {
    // Timing metrics
    undoPhaseStartTime: Date;
    undoPhaseEndTime: Date;
    undoPhaseElapsedMs: number;
    
    // Transaction metrics
    loserTransactionCount: number;
    transactionUndoTimes: Map<TransactionId, number>;  // ms per transaction
    
    // Operation metrics  
    totalUndoOperations: number;
    clrRecordsWritten: number;
    endRecordsWritten: number;
    
    // I/O metrics
    logPagesRead: number;
    dataPagesAccessed: number;
    dataPagesModified: number;
    bytesWrittenToLog: number;
    
    // Per-phase breakdowns (if tracked)
    timeReadingLog: number;
    timeApplyingUndo: number;
    timeWritingCLRs: number;
    
    // Derived metrics
    avgUndoOpsPerTransaction(): number;
    avgTimePerUndo(): number;
    undoThroughput(): number;  // operations per second
}
 
// Example metrics after undo phase:
const undoMetrics: UndoPhaseMetrics = {
    undoPhaseStartTime: new Date('2024-01-15T10:30:00'),
    undoPhaseEndTime: new Date('2024-01-15T10:30:15'),
    undoPhaseElapsedMs: 15000,
    
    loserTransactionCount: 3,
    transactionUndoTimes: new Map([
        ['T1', 5000],   // 5 seconds
        ['T2', 8000],   // 8 seconds (was a long transaction)
        ['T3', 2000],   // 2 seconds
    ]),
    
    totalUndoOperations: 450,
    clrRecordsWritten: 450,
    endRecordsWritten: 3,
    
    logPagesRead: 50,
    dataPagesAccessed: 200,
    dataPagesModified: 180,
    bytesWrittenToLog: 45000,
    
    timeReadingLog: 3000,
    timeApplyingUndo: 10000,
    timeWritingCLRs: 2000,
    
    avgUndoOpsPerTransaction: () => 450 / 3,  // 150 ops/txn
    avgTimePerUndo: () => 15000 / 450,        // 33ms per undo
    undoThroughput: () => 450 / 15,           // 30 ops/second
};

Recovery Time Objectives (RTO)

Many organizations have RTO requirements—the maximum acceptable time for recovery. If recovery consistently exceeds RTO, consider: increasing checkpoint frequency, reducing maximum transaction size, using faster log storage, or implementing parallel recovery.

Handling Edge Cases at Completion

Several edge cases can complicate undo completion. Robust implementations must handle these correctly.

Case 1: Crash During END Record Write

If we crash while writing an END record:

The transaction may or may not have the END in the log
On re-recovery, analysis will check for END
If missing, the transaction appears active but has undoNextLSN = null (all CLRs present)
Undo phase will see null undoNextLSN and simply write END again

This is safe because END is idempotent—writing it twice doesn't change anything.

Case 2: Prepared Transactions (2PC)

In distributed systems using Two-Phase Commit, some transactions may be in PREPARED state at crash:

They've voted to commit but haven't received the coordinator's decision
ARIES doesn't undo PREPARED transactions
They remain in the transaction table after recovery
The coordinator must be contacted to determine commit/abort

prepared_transaction_handling.pseudo

Prepared Transaction Handling

PROCEDURE HandlePreparedTransactions():
    preparedList = []
    
    FOR EACH (txnId, entry) IN TransactionTable:
        IF entry.status == PREPARED:
            preparedList.Add(txnId)
            // Do NOT undo this transaction!
            // It's waiting for 2PC resolution
    
    IF preparedList.IsNotEmpty():
        Log.Warn("Recovery found {preparedList.Count} prepared transactions")
        Log.Warn("These require manual or coordinator resolution")
        
        // Keep them in transaction table
        // Keep their locks held (if applicable)
        
        // Notify administrator
        Alert.Send("Prepared transactions need resolution: {preparedList}")
        
        // System can come online, but these resources are locked
        FOR EACH txnId IN preparedList:
            LockManager.MarkAsHeldByPrepared(txnId)
    
    RETURN preparedList
 
 
// Admin resolution:
PROCEDURE ResolvesPreparedTransaction(txnId, decision):
    IF decision == COMMIT:
        // Write COMMIT record, then END
        Log.Write(COMMIT_RECORD, transactionId: txnId)
        Log.Write(END_RECORD, transactionId: txnId)
        TransactionTable.Remove(txnId)
        LockManager.ReleaseAllLocks(txnId)
        Log.Info("Prepared transaction {txnId} committed")
        
    ELSE IF decision == ABORT:
        // Undo like a normal loser
        UndoTransaction(txnId)
        Log.Write(END_RECORD, transactionId: txnId)
        TransactionTable.Remove(txnId)
        LockManager.ReleaseAllLocks(txnId)
        Log.Info("Prepared transaction {txnId} aborted")

Case 3: Resource Cleanup

Some transactions hold resources beyond locks:

Temporary files created during query execution
In-memory structures (hash tables, sort buffers)
External resources (file handles, network connections)

These must be cleaned up:

PROCEDURE CleanupLoserResources(txnId):
    // Release any temporary tables
    TempTableManager.DropAllForTransaction(txnId)
    
    // Close any open cursors
    CursorManager.CloseAllForTransaction(txnId)
    
    // Release any held locks
    LockManager.ReleaseAllLocks(txnId)
    
    // Clean up any in-memory state
    TransactionContext.Cleanup(txnId)

Case 4: Very Long Undo

If a loser transaction is extremely large (millions of operations), undo might take a very long time:

Consider checkpointing periodically during undo
May need to bring system online in degraded mode
Monitor progress and provide estimates

Never Skip Undo

It might be tempting to skip undo for performance, but this would violate atomicity. All loser transactions MUST be fully undone before the database can safely accept new transactions. The alternative is a corrupted, inconsistent database.

Summary: Undo Completion

The completion of the undo phase marks the end of ARIES recovery and the beginning of normal database operation. Every step in this final stage is designed to ensure the database is truly consistent and ready to serve new transactions. Let's consolidate the key insights:

Key Takeaways

•Termination is deterministic — The undo phase completes when ToUndo is empty, meaning every loser has reached its BEGIN record or equivalent.
•END records are essential — They mark transaction completion, enable log truncation, and prevent re-processing on subsequent recoveries.
•Verification catches errors — Post-undo checks ensure the transaction table is clean and the database state is consistent.
•Post-recovery checkpoint reduces future work — Writing a checkpoint immediately after recovery speeds up subsequent recovery if another crash occurs.
•Transition must be careful — New transactions can only begin after recovery is truly complete and system state is properly initialized.
•Metrics guide optimization — Tracking recovery performance identifies bottlenecks and informs capacity planning.
•Edge cases require special handling — Prepared transactions, resource cleanup, and very long transactions need additional logic.

Module Complete:

You have now completed Module 5: Undo Phase. Over these five pages, you've learned:

Why undo is necessary: The steal policy and atomicity requirements
CLR mechanism: How undo operations are made durable
Backward scan: Efficient processing of all losers in one pass
Nested rollback: How savepoints and partial rollbacks interact with recovery
Undo completion: Finalization, verification, and transition to normal operation

The undo phase is the final piece of the ARIES recovery puzzle. Combined with the analysis and redo phases, it provides a complete, crash-resistant recovery system that guarantees ACID properties even in the face of arbitrary failures.

Module Complete

Congratulations! You now have a deep understanding of the ARIES undo phase—from the initial identification of loser transactions through the final END records and transition to normal operation. This knowledge represents the gold standard of database recovery understanding, applicable to any modern transactional database system.

Undo Completion

The Final Steps of Recovery

What You Will Learn

Termination Conditions

When Does a Transaction Leave ToUndo?

A transaction is removed from the ToUndo set when:

Its PrevLSN becomes null: After undoing the first update (the one right after BEGIN), the prevLSN of that record is null, indicating we've walked back to the start.
A CLR's undoNextLSN is null: If we encounter a CLR whose undoNextLSN is null, this means a previous partial rollback already completed undoing back to BEGIN.
We reach a BEGIN record: Though typically we stop at null prevLSN from an UPDATE, if we explicitly read a BEGIN record, the transaction is done.

termination_check.pseudo

Termination Logic

PROCEDURE ProcessUndoRecord(lsn, txnId, ToUndo, txnTable):
    record = Log.Read(lsn)
    
    IF record.type == UPDATE:
        // Undo the update
        PerformUndo(record)
        WriteCLR(record)
        
        // Determine next step
        IF record.prevLSN == NULL:
            // This was the first update after BEGIN
            // Transaction is fully undone
            FinalizeTransaction(txnId)
        ELSE:
            // More records to undo
            ToUndo.Insert(record.prevLSN, txnId)
            
    ELSE IF record.type == CLR:
        // Already-done undo, follow the shortcut
        IF record.undoNextLSN == NULL:
            // Previous undo reached the beginning
            // Transaction is fully undone
            FinalizeTransaction(txnId)
        ELSE:
            // Continue from where previous undo left off
            ToUndo.Insert(record.undoNextLSN, txnId)
            
    ELSE IF record.type == BEGIN:
        // Reached the transaction start
        FinalizeTransaction(txnId)
 
 
PROCEDURE FinalizeTransaction(txnId):
    // Write END record to mark completion
    Log.Write(END_RECORD, transactionId: txnId)
    
    // Remove from transaction table
    TransactionTable.Remove(txnId)
    
    // Don't add anything to ToUndo
    Log.Info("Transaction {txnId} fully rolled back")
 
 
PROCEDURE IsUndoComplete(ToUndo):
    RETURN ToUndo.IsEmpty()

Invariant at Termination:

When the undo phase completes:

ToUndo set is empty
Transaction table contains no ACTIVE or ABORTING entries
Every loser has an END record in the log
All uncommitted changes have been reversed in the database

This invariant guarantees that the database is consistent and ready for new transactions.

What About Running Transactions Before Crash?

The END Record

When a loser transaction's undo is complete, an END record is written to the log. This record serves several important purposes:

1. Definitive Rollback Marker:

The END record is proof that the transaction has been fully rolled back. Future analysis phases will see this and know the transaction is completely finished—no further undo is needed.

2. Log Truncation Enabler:

3. Transaction Lifecycle Closure:

Transaction Lifecycle and Log Records
Phase	Normal Commit	Normal Abort	Recovery (Loser)
Start	BEGIN	BEGIN	BEGIN
Operations	UPDATE, UPDATE, ...	UPDATE, UPDATE, ...	UPDATE, UPDATE, ...
Decision	COMMIT	ABORT	(crash—no decision)
Undo phase	(none needed)	CLR, CLR, ...	CLR, CLR, ...
Completion	END	END	END

end_record_structure.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * END Log Record Structure
 * 
 * Written when a transaction completes, either via commit or rollback.
 * This is the simplest log record type - it just marks completion.
 */
interface EndLogRecord {
    /** Log Sequence Number of this END record */
    lsn: LogSequenceNumber;
    
    /** 
     * Transaction ID that has completed.
     * After this record, no more log records will be written 
     * for this transaction.
     */
    transactionId: TransactionId;
    
    /** Record type identifier */
    recordType: LogRecordType.END;
    
    /**
     * PrevLSN for this transaction.
     * Points to the last CLR (if rolled back) or COMMIT record.
     * May be used for debugging/analysis but not for recovery.
     */
    prevLSN: LogSequenceNumber;
    
    /**
     * Optional: Final status of the transaction.
     * COMMITTED or ABORTED.
     * Not strictly necessary (can be inferred) but useful for tools.
     */
    finalStatus?: 'COMMITTED' | 'ABORTED';
}
 
// Example END record for a rolled-back transaction:
const endRecord: EndLogRecord = {
    lsn: 1500,
    transactionId: 'T42',
    recordType: LogRecordType.END,
    prevLSN: 1495,  // Points to the last CLR
    finalStatus: 'ABORTED'
};

END Record Durability:

Idempotency:

END vs COMMIT

Post-Undo State Verification

Verification Checks:

Transaction Table Audit:
- Should contain no ACTIVE or ABORTING entries
- May contain COMMITTED entries that haven't had END written yet (these get cleaned up)
- Any remaining entries are removed/finalized
Dirty Page Table Consistency:
- Pages in the dirty page table should have valid PageLSNs
- PageLSN values should be consistent with log state
- Optional: flush dirty pages to verify writability
Log Integrity:
- Verify log is not corrupted at the end
- Ensure tail of log is properly terminated
- Optional: checksum verification for log pages

post_undo_verification.pseudo

Verification Procedure

PROCEDURE VerifyUndoCompletion():
    errors = []
    
    // Check 1: No active transactions remain
    FOR EACH (txnId, entry) IN TransactionTable:
        IF entry.status IN {ACTIVE, ABORTING}:
            errors.Add("Transaction {txnId} still in {entry.status} state")
            // Attempt recovery: write END record
            Log.Write(END_RECORD, transactionId: txnId)
            TransactionTable.Remove(txnId)
    
    // Check 2: All loser transactions have END records
    // (This is implicit if we processed ToUndo correctly, but verify anyway)
    FOR EACH loserTxn IN OriginalLoserSet:
        IF NOT Log.HasEndRecord(loserTxn.id):
            errors.Add("Loser {loserTxn.id} missing END record")
    
    // Check 3: Buffer pool consistency
    FOR EACH (pageId, pageEntry) IN DirtyPageTable:
        page = BufferPool.Fetch(pageId)
        IF page.pageLSN < pageEntry.recoveryLSN:
            errors.Add("Page {pageId} has stale LSN")
    
    // Check 4: Database constraint verification (optional, expensive)
    IF Config.VERIFY_CONSTRAINTS_AFTER_RECOVERY:
        FOR EACH table IN Database.Tables:
            IF NOT table.VerifyConstraints():
                errors.Add("Constraint violation in {table.name}")
    
    // Report results
    IF errors.IsEmpty():
        Log.Info("Undo phase verification: PASSED")
    ELSE:
        Log.Error("Undo phase verification: FAILED")
        FOR EACH error IN errors:
            Log.Error("  - {error}")
        // Depending on configuration, may halt or continue
        IF Config.HALT_ON_VERIFICATION_FAILURE:
            RAISE RecoveryVerificationException(errors)
    
    RETURN errors.IsEmpty()

Constraint Verification:

Some databases optionally verify integrity constraints after recovery:

Primary key uniqueness
Foreign key references
Check constraints
Unique index integrity

This is expensive but catches subtle corruption. Most systems skip this for speed, relying on the correctness of the recovery algorithm.

Handling Verification Failures:

If verification fails, the system has several options:

Halt and require manual intervention: Safest, but delays availability
Log warnings and continue: Risky if corruption is serious
Attempt automated repair: Complex and may make things worse
Restore from backup: Last resort if recovery is fundamentally broken

Verification vs Production Speed

Post-Recovery Checkpoint

Why Checkpoint After Recovery?

Reduce future recovery time: The checkpoint sets a new starting point. If we crash immediately after, we start from this checkpoint instead of the old one.
Enable log truncation: Records before the checkpoint (including all the CLRs we just wrote) can potentially be truncated.
Flush dirty pages: The checkpoint process may flush dirty pages, reducing the amount of data that could be lost if another crash occurs immediately.

With Post-Recovery Checkpoint

•Next recovery starts from new checkpoint
•Old log segments can be archived/deleted
•Clean transaction table state captured
•Dirty page table reflects current state
•Recovery time bounded by checkpoint frequency

Without Post-Recovery Checkpoint

•Next recovery starts from old checkpoint
•Must replay all CLRs again during redo
•Log continues to grow
•Recovery time accumulates over crashes
•Potential unbounded recovery work

post_recovery_checkpoint.pseudo

Post-Recovery Checkpoint

PROCEDURE PerformPostRecoveryCheckpoint():
    Log.Info("Performing post-recovery checkpoint...")
    
    // The transaction table should be empty or only have clean entries
    ASSERT TransactionTable.IsEmpty() OR 
           TransactionTable.AllEntriesAre(COMMITTED_AND_ENDED)
    
    // Begin checkpoint record
    checkpointBeginLSN = Log.Write(CHECKPOINT_BEGIN)
    
    // Capture dirty page table
    // (These are pages modified during redo/undo that haven't been flushed)
    dptSnapshot = DirtyPageTable.Snapshot()
    
    // Transaction table should be essentially empty
    ttSnapshot = TransactionTable.Snapshot()
    ASSERT ttSnapshot.IsEmpty()
    
    // Write checkpoint end with DPT snapshot
    checkpointEndLSN = Log.Write(CHECKPOINT_END, 
                                  dirtyPageTable: dptSnapshot,
                                  transactionTable: ttSnapshot)
    
    // Force the checkpoint to stable storage
    Log.Force(checkpointEndLSN)
    
    // Update the master record to point to this checkpoint
    MasterRecord.Update(lastCheckpointLSN: checkpointBeginLSN)
    
    // Optionally, flush some dirty pages now
    IF Config.FLUSH_PAGES_ON_POST_RECOVERY_CHECKPOINT:
        FOR EACH pageId IN dptSnapshot.Keys():
            BufferPool.FlushPage(pageId)
        DirtyPageTable.Clear()
    
    Log.Info("Post-recovery checkpoint complete at LSN {checkpointEndLSN}")
    
    // Now safe to truncate log up to certain point
    oldLogEnd = CalculateSafeTruncationPoint()
    Log.TruncateBefore(oldLogEnd)

Checkpoint Timing Tradeoff:

Fuzzy vs Sharp Checkpoint:

Recovery Checkpoint Best Practice

Transitioning to Normal Operation

Transition Steps:

Clear recovery mode flag: Internal state changes from RECOVERING to ONLINE
Reset sequence generators: Transaction IDs, LSNs, and other sequences continue from appropriate points
Resume background processes: Checkpointing, buffer pool flushing, statistics collection, etc.
Re-enable client connections: Accept new connections from applications
Process queued requests: Some systems queue connection attempts during recovery

transition_to_normal.pseudo

Transition Procedure

PROCEDURE TransitionToNormalOperation():
    Log.Info("=== TRANSITIONING TO NORMAL OPERATION ===")
    
    // Step 1: Final state validation
    ASSERT ToUndoSet.IsEmpty()
    ASSERT TransactionTable.HasNoActiveTransactions()
    
    // Step 2: Update system state
    SystemState.SetMode(ONLINE)
    SystemState.SetRecoveryComplete(true)
    SystemState.SetRecoveryEndTime(Now())
    
    // Step 3: Initialize transaction ID sequence
    // Next transaction ID should be higher than any seen during recovery
    maxSeenTxnId = Recovery.GetMaxTransactionId()
    TransactionIdGenerator.Initialize(maxSeenTxnId + 1)
    
    // Step 4: Initialize LSN sequence
    // Already correct - we've been appending to log during recovery
    // Just verify it's consistent
    ASSERT Log.GetNextLSN() > Recovery.GetMaxLSN()
    
    // Step 5: Start background processes
    CheckpointDaemon.Start()
    BufferPoolFlusher.Start()
    StatisticsCollector.Start()
    DeadlockDetector.Start()
    
    // Step 6: Enable client connections
    ConnectionManager.AcceptNewConnections()
    
    // Step 7: Process any queued connection requests
    FOR EACH queuedRequest IN ConnectionQueue:
        ConnectionManager.ProcessRequest(queuedRequest)
    
    // Step 8: Notify monitoring systems
    Metrics.RecordEvent("database.recovery.complete", {
        recoveryTimeMs: SystemState.GetRecoveryDuration(),
        loserTransactions: Recovery.GetLoserCount(),
        redoOperations: Recovery.GetRedoCount(),
        undoOperations: Recovery.GetUndoCount()
    })
    
    // Step 9: Log completion
    Log.Info("=== DATABASE ONLINE ===")
    Log.Info("Recovery completed in {SystemState.GetRecoveryDuration()}ms")
    Log.Info("Rolled back {Recovery.GetLoserCount()} transactions")

Gradual vs Immediate Availability:

Some systems offer gradual availability:

Tables/databases recovery independently
High-priority tables come online first
Applications can query recovered portions while recovery continues elsewhere

This is particularly useful for large databases where full recovery might take hours.

Warning: New Transactions During Transition:

Care must be taken that no new transactions begin until the system is truly ready. A premature transaction could:

Conflict with recovery operations
Use transaction IDs that overlap with recovered ones
Access inconsistent data

The Promise Fulfilled

Measuring Recovery Performance

Understanding recovery performance is critical for capacity planning and ensuring the system meets availability requirements. Key metrics to track:

Recovery Time Metrics:

Total recovery time: From crash detection to database online
Analysis phase time: Time to scan log and build tables
Redo phase time: Time to replay operations
Undo phase time: Time to roll back losers
Post-recovery time: Checkpoint and transition overhead

Factors Affecting Recovery Time
Factor	Affects Which Phase	How to Reduce Impact
Checkpoint frequency	All phases	More frequent checkpoints = less log to process
Number of dirty pages	Redo	More aggressive page flushing reduces redo work
Number of active transactions	Undo	Shorter transactions = fewer losers
Transaction size	Undo	Smaller transactions = faster undo per loser
Log I/O speed	All phases	Faster storage for log files
Buffer pool size	Redo, Undo	Larger pool = more pages cached during recovery
Number of parallel workers	Redo, Undo	Some systems parallelize recovery

Undo Phase Specific Metrics:

Loser count: Number of transactions requiring undo
Total undo operations: Sum of operations across all losers
CLRs written: Number of compensation records created
Pages touched during undo: Measure of I/O for undo
Undo elapsed time per loser: Identify problematic long transactions

recovery_metrics.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * Recovery metrics collected during the undo phase.
 * Used for performance analysis and capacity planning.
 */
interface UndoPhaseMetrics {
    // Timing metrics
    undoPhaseStartTime: Date;
    undoPhaseEndTime: Date;
    undoPhaseElapsedMs: number;
    
    // Transaction metrics
    loserTransactionCount: number;
    transactionUndoTimes: Map<TransactionId, number>;  // ms per transaction
    
    // Operation metrics  
    totalUndoOperations: number;
    clrRecordsWritten: number;
    endRecordsWritten: number;
    
    // I/O metrics
    logPagesRead: number;
    dataPagesAccessed: number;
    dataPagesModified: number;
    bytesWrittenToLog: number;
    
    // Per-phase breakdowns (if tracked)
    timeReadingLog: number;
    timeApplyingUndo: number;
    timeWritingCLRs: number;
    
    // Derived metrics
    avgUndoOpsPerTransaction(): number;
    avgTimePerUndo(): number;
    undoThroughput(): number;  // operations per second
}
 
// Example metrics after undo phase:
const undoMetrics: UndoPhaseMetrics = {
    undoPhaseStartTime: new Date('2024-01-15T10:30:00'),
    undoPhaseEndTime: new Date('2024-01-15T10:30:15'),
    undoPhaseElapsedMs: 15000,
    
    loserTransactionCount: 3,
    transactionUndoTimes: new Map([
        ['T1', 5000],   // 5 seconds
        ['T2', 8000],   // 8 seconds (was a long transaction)
        ['T3', 2000],   // 2 seconds
    ]),
    
    totalUndoOperations: 450,
    clrRecordsWritten: 450,
    endRecordsWritten: 3,
    
    logPagesRead: 50,
    dataPagesAccessed: 200,
    dataPagesModified: 180,
    bytesWrittenToLog: 45000,
    
    timeReadingLog: 3000,
    timeApplyingUndo: 10000,
    timeWritingCLRs: 2000,
    
    avgUndoOpsPerTransaction: () => 450 / 3,  // 150 ops/txn
    avgTimePerUndo: () => 15000 / 450,        // 33ms per undo
    undoThroughput: () => 450 / 15,           // 30 ops/second
};

Recovery Time Objectives (RTO)

Handling Edge Cases at Completion

Several edge cases can complicate undo completion. Robust implementations must handle these correctly.

Case 1: Crash During END Record Write

If we crash while writing an END record:

The transaction may or may not have the END in the log
On re-recovery, analysis will check for END
If missing, the transaction appears active but has undoNextLSN = null (all CLRs present)
Undo phase will see null undoNextLSN and simply write END again

This is safe because END is idempotent—writing it twice doesn't change anything.

Case 2: Prepared Transactions (2PC)

In distributed systems using Two-Phase Commit, some transactions may be in PREPARED state at crash:

They've voted to commit but haven't received the coordinator's decision
ARIES doesn't undo PREPARED transactions
They remain in the transaction table after recovery
The coordinator must be contacted to determine commit/abort

prepared_transaction_handling.pseudo

Prepared Transaction Handling

PROCEDURE HandlePreparedTransactions():
    preparedList = []
    
    FOR EACH (txnId, entry) IN TransactionTable:
        IF entry.status == PREPARED:
            preparedList.Add(txnId)
            // Do NOT undo this transaction!
            // It's waiting for 2PC resolution
    
    IF preparedList.IsNotEmpty():
        Log.Warn("Recovery found {preparedList.Count} prepared transactions")
        Log.Warn("These require manual or coordinator resolution")
        
        // Keep them in transaction table
        // Keep their locks held (if applicable)
        
        // Notify administrator
        Alert.Send("Prepared transactions need resolution: {preparedList}")
        
        // System can come online, but these resources are locked
        FOR EACH txnId IN preparedList:
            LockManager.MarkAsHeldByPrepared(txnId)
    
    RETURN preparedList
 
 
// Admin resolution:
PROCEDURE ResolvesPreparedTransaction(txnId, decision):
    IF decision == COMMIT:
        // Write COMMIT record, then END
        Log.Write(COMMIT_RECORD, transactionId: txnId)
        Log.Write(END_RECORD, transactionId: txnId)
        TransactionTable.Remove(txnId)
        LockManager.ReleaseAllLocks(txnId)
        Log.Info("Prepared transaction {txnId} committed")
        
    ELSE IF decision == ABORT:
        // Undo like a normal loser
        UndoTransaction(txnId)
        Log.Write(END_RECORD, transactionId: txnId)
        TransactionTable.Remove(txnId)
        LockManager.ReleaseAllLocks(txnId)
        Log.Info("Prepared transaction {txnId} aborted")

Case 3: Resource Cleanup

Some transactions hold resources beyond locks:

Temporary files created during query execution
In-memory structures (hash tables, sort buffers)
External resources (file handles, network connections)

These must be cleaned up:

PROCEDURE CleanupLoserResources(txnId):
    // Release any temporary tables
    TempTableManager.DropAllForTransaction(txnId)
    
    // Close any open cursors
    CursorManager.CloseAllForTransaction(txnId)
    
    // Release any held locks
    LockManager.ReleaseAllLocks(txnId)
    
    // Clean up any in-memory state
    TransactionContext.Cleanup(txnId)

Case 4: Very Long Undo

If a loser transaction is extremely large (millions of operations), undo might take a very long time:

Consider checkpointing periodically during undo
May need to bring system online in degraded mode
Monitor progress and provide estimates

Never Skip Undo

Summary: Undo Completion

Key Takeaways

•Termination is deterministic — The undo phase completes when ToUndo is empty, meaning every loser has reached its BEGIN record or equivalent.
•END records are essential — They mark transaction completion, enable log truncation, and prevent re-processing on subsequent recoveries.
•Verification catches errors — Post-undo checks ensure the transaction table is clean and the database state is consistent.
•Post-recovery checkpoint reduces future work — Writing a checkpoint immediately after recovery speeds up subsequent recovery if another crash occurs.
•Transition must be careful — New transactions can only begin after recovery is truly complete and system state is properly initialized.
•Metrics guide optimization — Tracking recovery performance identifies bottlenecks and informs capacity planning.
•Edge cases require special handling — Prepared transactions, resource cleanup, and very long transactions need additional logic.

Module Complete:

You have now completed Module 5: Undo Phase. Over these five pages, you've learned:

Why undo is necessary: The steal policy and atomicity requirements
CLR mechanism: How undo operations are made durable
Backward scan: Efficient processing of all losers in one pass
Nested rollback: How savepoints and partial rollbacks interact with recovery
Undo completion: Finalization, verification, and transition to normal operation

Module Complete