Loading learning content...
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.
By the end of this page, you will understand the complete operational model of deferred update recovery, including its log structure, commit protocol, recovery procedure, performance characteristics, and the specific scenarios where this approach excels or falls short.
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.
| Aspect | Policy | Rationale |
|---|---|---|
| Write Timing | Only after commit | Eliminates need for undo operations |
| Buffer Management | Hold changes in memory until commit | Uncommitted data never pollutes the database |
| Log Content | New values only (REDO information) | Old values unnecessary since database unchanged |
| Recovery Action | REDO committed transactions only | No uncommitted data exists in database |
| Commit Protocol | Write log first, then database | Ensures recoverability via log |
The invariant that no uncommitted data reaches the database is the foundation of deferred update. Every design decision—buffer management, logging, commit sequence—exists to preserve this invariant.
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:
This sequence repeats for every modification. At no point during active execution does any change reach the stable database.
123456789101112131415161718192021222324
PROCEDURE Transaction_Write(transaction T, data_item X, new_value V): // Step 1: Ensure data item is in buffer IF X not in buffer_pool THEN load_page_containing(X) into buffer_pool END IF // Step 2: Apply modification to buffer ONLY buffer_copy[X] := V // Step 3: Create REDO log record log_record := { transaction_id: T.id, data_item: X, new_value: V, // REDO information LSN: next_LSN() // Log Sequence Number } // Step 4: Append to log buffer log_buffer.append(log_record) // Step 5: Database disk page is NOT modified // The stable database remains unchanged until commit RETURN successThe Commit Sequence:
The commit phase is where deferred update enforces its invariant through careful sequencing:
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.
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.
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.
12345678910111213141516171819202122232425262728
PROCEDURE Commit_Transaction(transaction T): // Phase 1: Force all log records to stable storage // (Log records were created during execution) // Create COMMIT record commit_record := { transaction_id: T.id, type: COMMIT, LSN: next_LSN() } log_buffer.append(commit_record) // Force entire log buffer to stable storage FORCE_LOG_TO_DISK() // At this point, the transaction is COMMITTED // Even if the system crashes now, recovery will redo // Phase 2: Write modified data to database FOR EACH data_item X modified by T: write_buffer_to_disk(X) END FOR // Phase 3: Transaction complete release_all_locks(T) notify_client(T, "COMMITTED") RETURN successThe 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:
Notably Absent:
| Record Type | Contents | Purpose |
|---|---|---|
| [START, T] | Transaction ID | Marks transaction beginning |
| [WRITE, T, X, new_value] | Transaction ID, Data Item, New Value | Records modification for potential REDO |
| [COMMIT, T] | Transaction ID | Marks successful completion (point of commitment) |
| [ABORT, T] | Transaction ID | Marks transaction failure (no database changes to undo) |
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:
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.
Because deferred update logs only new values (not old values), log records are approximately half the size of those in systems that support undo. This can significantly reduce I/O for write-intensive workloads.
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:
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.
12345678910111213141516171819202122232425262728293031323334353637383940
PROCEDURE Recover_Database(): // Initialize transaction tracking sets committed := {} // Transactions with COMMIT records incomplete := {} // Transactions with START but no COMMIT redo_list := [] // WRITE records to replay // Pass 1: Scan log to classify transactions FOR EACH log_record IN log (from start/checkpoint to end): CASE log_record.type OF: START: incomplete.add(log_record.transaction_id) WRITE: // Store for potential redo redo_list.append(log_record) COMMIT: committed.add(log_record.transaction_id) incomplete.remove(log_record.transaction_id) ABORT: incomplete.remove(log_record.transaction_id) // No action needed - database unchanged END CASE END FOR // Pass 2: REDO all committed transactions FOR EACH record IN redo_list (in log order): IF record.transaction_id IN committed THEN // Apply the modification write_to_database(record.data_item, record.new_value) END IF END FOR // Incomplete transactions are simply ignored // Their changes never reached the database LOG("Recovery complete. Committed: {committed.size}, " "Ignored: {incomplete.size}") RETURN successRecovery 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:
| Transaction | Status | Action |
|---|---|---|
| T1 | Has COMMIT | REDO writes to A and B |
| T2 | No COMMIT | Ignore (database unchanged) |
| T3 | Has COMMIT | REDO write to D |
After recovery:
Deferred update recovery is conceptually simple: find what was committed, replay its effects, ignore everything else. This simplicity reduces implementation complexity and potential bugs in the recovery code path—a critical advantage given that recovery code is rarely tested but crucial when needed.
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:
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:
In practice, this limits deferred update to systems with:
Memory Pressure Handling:
When buffer memory becomes scarce, a deferred update system has limited options:
None of these are ideal, which is why deferred update is less common in modern general-purpose DBMS implementations.
Deferred update is unsuitable for bulk operations like 'UPDATE all rows in a 10-million-row table' or large batch inserts. Such operations would quickly exhaust the buffer pool. Systems using deferred update must carefully control transaction sizes or provide sufficient memory.
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:
During Commit:
| Metric | Deferred Update | Immediate Update |
|---|---|---|
| Write latency (during execution) | Very low (memory only) | Variable (may include disk) |
| Commit latency | Higher (all writes at once) | Lower (writes spread over time) |
| Log record size | Smaller (new value only) | Larger (old + new values) |
| Total log I/O | Lower overall | Higher overall |
| Recovery time | REDO only (faster) | UNDO + REDO (slower) |
| Abort cost | Near zero (nothing to undo) | Proportional to changes made |
| Memory requirement | High (buffer all changes) | Moderate (can write early) |
Recovery Performance:
Deferred update recovery tends to be fast:
When Deferred Update Excels:
When Deferred Update Struggles:
One often-overlooked advantage: transaction abort in deferred update is essentially free. Since no changes reached the database, aborting simply discards the transaction's log records and releases its buffers. This makes deferred update attractive for speculative execution or optimistic concurrency control schemes with high abort rates.
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:
Modern Applications:
Today, pure deferred update appears in:
Hybrid Approaches:
Many modern systems use hybrid strategies that incorporate deferred update principles:
Deferred update embodies a broader principle in systems design: pushing work to commit time trades complexity during normal operation for complexity at commit. This is the opposite of 'eager' approaches that spread work throughout transaction execution. Understanding both philosophies helps in evaluating any recovery or consistency mechanism.
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.
You now understand the deferred update recovery algorithm in depth—its philosophy, mechanics, logging requirements, recovery procedure, and practical trade-offs. This knowledge forms the foundation for understanding more complex recovery strategies like ARIES.