Recovery Algorithm Types

When a database transaction modifies data, a fundamental question arises: When should those changes become visible in the database? The answer to this question defines the very nature of a recovery algorithm. The Deferred Update approach—also known as NO-UNDO/REDO—takes a conservative stance: never write uncommitted data to the database.

This philosophy may seem restrictive, but it offers profound simplicity in recovery. If uncommitted changes never reach the database, there's nothing to undo when a transaction fails. The only recovery operation needed is redo—replaying committed transactions whose effects were lost due to failure.

The Deferred Update technique is built on a single, powerful invariant:

No uncommitted data is ever written to the stable database.

This invariant has profound implications. During transaction execution, all modifications are recorded in the log and held in volatile memory (buffers), but the actual database pages on disk remain untouched until the transaction commits. Only after a transaction's commit record is safely written to stable storage do its modifications propagate to the database.

Why 'NO-UNDO/REDO'?

The name describes the recovery operations required:

• NO-UNDO: Since uncommitted changes never reach the database, there's nothing to reverse when a transaction aborts or a failure occurs during an active transaction.

• REDO: Committed transactions whose changes were only in memory (not yet written to the database) must be replayed during recovery to restore the database to its committed state.

Understanding how deferred update works in practice requires examining the lifecycle of a transaction from start to commit, including the precise sequencing of log writes and database writes.

Transaction Execution Phase:

When a transaction begins, it operates entirely in the buffer pool (memory). For each write operation:

1. The transaction reads the relevant data item into a buffer (if not already present)
2. The modification is applied to the buffer copy
3. A log record is created containing the new value (REDO information)
4. The log record is written to the log buffer
5. The database page on disk remains unchanged

This sequence repeats for every modification. At no point during active execution does any change reach the stable database.

The Commit Sequence:

The commit phase is where deferred update enforces its invariant through careful sequencing:

1. Force the log to stable storage: All log records for the transaction, including the COMMIT record, are written to disk. This is the point of no return—if the system fails after this, the transaction is considered committed.

2. Write modified data to database: Only now, with the log safely on disk, can the modified buffers be written to the database. If failure occurs during this phase, recovery will use the log to redo the writes.

3. Acknowledge commit to client: The transaction is complete.

This sequence is critical. The log contains all information needed to reconstruct the transaction's effects. By forcing the log first, we guarantee recoverability.

The log in a deferred update system is optimized for REDO operations. Since UNDO is never needed, log records contain only the information required to reconstruct committed changes.

Essential Log Record Components:

• Transaction ID: Identifies the transaction that generated the record
• Log Sequence Number (LSN): A monotonically increasing identifier for ordering
• Record Type: START, WRITE, COMMIT, or ABORT
• Data Item Identifier: For WRITE records, identifies what was changed
• New Value: The value to write during REDO (after-image)

Notably Absent:

• Old Value: Since we never undo, the original value (before-image) is unnecessary
• UNDO Information: No mechanism for reversing operations needed

Example Log Sequence:

Consider a transaction T1 that transfers $100 from account A (balance $500) to account B (balance $200):

[START, T1]
[WRITE, T1, A, 400]      // A's new balance
[WRITE, T1, B, 300]      // B's new balance  
[COMMIT, T1]

Notice that we don't record the old values (500 for A, 200 for B). If T1 aborts before commit, the database is unchanged—there's nothing to undo. If the system fails after the COMMIT record is written but before the database updates, recovery simply replays the WRITE records.

Log Forcing and Write-Ahead Logging:

Deferred update follows a variant of the Write-Ahead Logging (WAL) protocol:

1. All WRITE log records must be on stable storage before their corresponding database changes
2. The COMMIT record must be on stable storage before acknowledging commit

However, since database changes only occur after commit in deferred update, rule #1 is automatically satisfied—log records are always written before database changes by design.

Recovery in a deferred update system is remarkably straightforward. The algorithm follows a simple two-pass approach:

Pass 1: Identify Committed Transactions

Scan the log from the beginning (or from the last checkpoint) to the end, building two lists:

• Committed: Transactions with both START and COMMIT records
• Incomplete: Transactions with START but no COMMIT

Pass 2: REDO Committed Transactions

For each transaction in the Committed list, replay its WRITE operations in log order. This restores all committed changes that may have been lost.

What About Incomplete Transactions?

Transactions in the Incomplete list are simply ignored. Since deferred update never wrote their changes to the database, there's nothing to undo. They vanish as if they never existed—which, from the database's perspective, is exactly true.

Recovery Example:

Consider a log with the following sequence when a crash occurs:

[START, T1]
[WRITE, T1, A, 100]
[WRITE, T1, B, 200]
[COMMIT, T1]
[START, T2]
[WRITE, T2, C, 300]
[START, T3]
[WRITE, T3, D, 400]
[COMMIT, T3]
[WRITE, T2, E, 500]
--- CRASH ---

Recovery Analysis:

After recovery:

• A = 100, B = 200, D = 400 (from committed T1, T3)
• C and E are unchanged (T2's writes were never applied)

The deferred update policy places significant constraints on the buffer manager. Pages modified by active transactions cannot be written to disk, which has far-reaching implications for memory management and concurrency.

The NO-STEAL Policy:

Deferred update implements what is called a NO-STEAL buffer management policy:

• Steal: The buffer manager can 'steal' a buffer frame by writing its dirty page to disk, even if the page was modified by an uncommitted transaction
• No-Steal: The buffer manager cannot evict pages containing uncommitted modifications

With NO-STEAL, if a transaction has modified data in a buffer, that buffer is 'pinned'—it cannot be written to disk or reused until the transaction either commits (allowing the write) or aborts (discarding the modification).

The Critical Constraint: Transaction Size

The most significant limitation of deferred update is that a transaction cannot modify more data than can fit in the buffer pool. Consider:

• Transaction T modifies 10,000 pages
• Buffer pool has 5,000 frames
• After modifying 5,000 pages, all frames are pinned
• T cannot proceed—it needs more buffers, but none can be freed

In practice, this limits deferred update to systems with:

1. Small transactions relative to buffer size
2. Very large buffer pools
3. Workloads where transaction size is bounded and predictable

Memory Pressure Handling:

When buffer memory becomes scarce, a deferred update system has limited options:

1. Wait: Hope active transactions commit soon, freeing buffers
2. Abort: Kill long-running transactions to free pinned buffers
3. Reject: Refuse new transactions until space is available

None of these are ideal, which is why deferred update is less common in modern general-purpose DBMS implementations.

Deferred update exhibits distinct performance characteristics that make it optimal for certain workloads and suboptimal for others. Understanding these trade-offs is essential for system design.

Normal Operation Performance:

During Transaction Execution:

• Low latency writes: Modifications only update memory buffers, avoiding disk I/O
• Log writes: Each modification generates a log record, but log writes can be buffered
• No database I/O: Disk pages aren't touched until commit

During Commit:

• Log force: All buffered log records plus COMMIT must be written to disk (synchronous I/O)
• Database writes: Modified pages written to disk (can be asynchronous after log force)
• Commit latency: Bounded by log force time + database write time

Recovery Performance:

Deferred update recovery tends to be fast:

1. Single-pass REDO: Only forward-scanning REDO is needed, no backward UNDO pass
2. Fewer operations: Only committed transactions are processed
3. Smaller logs: Without before-images, logs are more compact
4. Simpler logic: Reduced complexity means faster execution

When Deferred Update Excels:

• Short transactions with few modifications
• Write-intensive workloads (benefits from reduced log I/O)
• High abort rates (aborts are nearly free)
• Systems prioritizing recovery speed and simplicity

When Deferred Update Struggles:

• Long-running transactions
• Large batch operations
• Memory-constrained environments
• Unpredictable transaction sizes

While pure deferred update is rare in modern commercial DBMS implementations, understanding its principles illuminates design trade-offs present in all recovery systems.

Historical Usage:

Deferred update was more common in earlier database systems when:

• Transactions were typically small (single-record updates)
• Memory was expensive, but transactions were bounded
• Simplicity in recovery code was highly valued (bugs could lose data)
• Systems served specialized, predictable workloads

Modern Applications:

Today, pure deferred update appears in:

1. Embedded databases: Where transactions are small and predictable
2. In-memory databases: Where 'disk' is really persistence to NVM/SSD
3. Specialized systems: Financial trading, telecommunications, etc.
4. Research prototypes: Testing new concurrency/recovery ideas

Hybrid Approaches:

Many modern systems use hybrid strategies that incorporate deferred update principles:

• Log-structured storage: All writes go to a log first (essentially deferred)
• Copy-on-write B-trees: New versions created instead of in-place updates
• MVCC with deferred cleanup: Old versions retained until safe to remove

The deferred update (NO-UNDO/REDO) algorithm represents a fundamental approach to database recovery. Let's consolidate the key concepts:

What's Next:

In the next page, we'll explore Immediate Update—the contrasting approach that allows uncommitted changes to reach the database. This introduces the need for UNDO operations but removes transaction size limitations, making it suitable for general-purpose database systems.