DBMS:Database Recovery Techniques:

Database systems must remain reliable even when failures occur. Recovery mechanisms ensure that after any type of failure the database can be restored to a consistent and correct state. This lecture provides an overview of fundamental recovery concepts, the role of logging, and various recovery techniques used in modern database management systems.

Introduction to Recovery

Recovery algorithms are designed to bring the database back to the most recent consistent state prior to a failure. This involves maintaining information in a system log that records every important operation. When a failure occurs, the recovery manager can restore a backup copy of the database in cases of severe damage or examine the log to detect and correct inconsistencies when the failure is noncatastrophic. Some transactions may require redo operations to reapply updates that were not reflected on disk.

Recovery techniques fall into two categories. Deferred update techniques postpone writing updates to the database on disk until the transaction successfully commits. Because changes are not applied until commit, undo operations are unnecessary, though redo operations may still be required. Immediate update techniques allow the database to be modified before the transaction commits. This requires that every update be recorded in the log so that both undo and redo operations remain possible.

Recovery relies heavily on the idea of idempotence. Undo and redo operations must produce the same result whether executed once or multiple times. Likewise, the entire recovery process must also be idempotent to prevent inconsistencies.

Buffer Management and Disk Interaction

Modern database systems make extensive use of caching. A database cache consists of in-memory buffers that hold copies of disk blocks. The system keeps a directory that tracks which items are currently in the cache. When a buffer needs to be replaced, it may be flushed to make space. Each buffer has a dirty bit that indicates whether it has been modified. Dirty buffers must be written to disk before they are replaced. A pin or unpin bit determines whether a page in the buffer is free to be written back to disk.

There are two primary strategies for writing updated pages. In-place updating writes the modified buffer back to its original disk location, overwriting the old data. Shadowing writes updated pages to new locations, preserving the old versions as shadows. Shadowing is rarely used in practice. Recovery operations refer to two versions of data: the before image, which is the old value, and the after image, which is the new value.

Write-Ahead Logging

Write-ahead logging, often called WAL, is a core recovery mechanism. WAL requires that the before image of an item be written to the log before the item itself is overwritten on disk. This ensures that undo operations can always restore the previous state if needed. Redo log entries must also be maintained to ensure that committed updates can be reapplied during recovery. WAL imposes two key conditions. The before image cannot be overwritten until all undo log entries have been safely written to disk. A transaction cannot be considered committed until all of its undo and redo log records have been flushed.

Steal, No Steal, Force, and No Force Policies

Recovery strategies depend on when the system allows modified pages to be written to disk. Under the no steal approach, a buffer page updated by an active transaction cannot be written to disk until the transaction commits. The steal approach allows the system to write updated buffers before commit, making better use of memory but requiring undo capability. The force approach requires that all updated pages be written to disk before commit, while the no force approach allows updated pages to remain in memory even after commit. Most systems use a steal and no force strategy because it balances memory usage and input output cost.

Checkpointing

Checkpointing reduces the amount of work needed during recovery. During a checkpoint the system briefly suspends transaction execution, writes all modified buffers to disk, records a checkpoint in the log, and then resumes normal processing. Recovery begins by locating the most recent checkpoint, which limits the portion of the log that must be examined. Fuzzy checkpointing allows the system to continue processing while the checkpoint is being recorded. A begin checkpoint entry is written first and the previous checkpoint remains valid until the end checkpoint entry is written.

Transaction Rollback

If a transaction fails after making updates but before committing, its effects must be undone. The system uses undo log entries that contain before images to restore old values. In some cases, rolling back one transaction might require rolling back others that read its uncommitted values. This is known as cascading rollback and occurs only in protocols that do not enforce strict or cascadeless schedules. Modern systems avoid cascading rollbacks through appropriate concurrency control.

Some transactions generate reports or messages that do not modify the database. These actions should be delayed until the transaction reaches its commit point to prevent users from receiving invalid output. If the transaction fails, the pending report operations are canceled.

Deferred Update Recovery

Deferred update uses a no undo and redo model. Updates are not written to disk until the transaction commits. Redo log entries are necessary to repeat changes during recovery, while undo entries are not needed because the database is not modified before commit. This method is suitable only for short transactions because all updated buffers must remain in memory until commit. The deferred update protocol requires that all changed buffers remain pinned until commit and that all redo log entries be flushed before the commit is finalized.

Immediate Update Recovery

Immediate update allows the database to be changed before the transaction commits. This requires both undo and redo capability. There are two variations. Undo and no redo is used in a steal and force strategy where every update is pushed to disk before commit, so redo is unnecessary. Undo and redo is more common and is used with a steal and no force policy. In this model the recovery manager may need to undo the effects of uncommitted transactions and redo the effects of committed ones.

To understand how Immediate Update Recovery works, let’s walk through a very simple schedule involving three transactions and two data items A and B.

Initial values:

• A = 10
• B = 20

In immediate update systems, changes can be written to the database before the transaction commits, so after a crash we may need to:

• UNDO uncommitted transactions
• REDO committed transactions

Here is our schedule:

| Time | T1        | T2         | T3        |
| ---- | --------- | ---------- | --------- |
| 1    | R(A)      |            |           |
| 2    | A = A + 5 |            |           |
| 3    | W(A)      |            |           |
| 4    | commit    |            |           |
| 5    |           | R(B)       |           |
| 6    |           | B = B + 10 |           |
| 7    |           | W(B)       |           |
| 8    |           | commit     |           |
| 9    |           |            | R(A)      |
| 10   |           |            | A = A + 7 |
| 11   |           |            | W(A)      |
| 12   |           |            | CRASH     |

STEP 1: Create the LOG

Immediate-update means every write has a before and after value.

| LSN | Transaction | Operation   | Item | Old | New |
| --- | ----------- | ----------- | ---- | --- | --- |
| 1   | T1          | UPDATE      | A    | 10  | 15  |
| 2   | T1          | COMMIT      |      |     |     |
| 3   | T2          | UPDATE      | B    | 20  | 30  |
| 4   | T2          | COMMIT      |      |     |     |
| 5   | T3          | UPDATE      | A    | 15  | 22  |
| 6   | T3          | (no commit) |      |     |     |

That is the whole log.

since READ operations do NOT change the database, and the recovery system only cares about things that change that is why there is no read operation log.

Values at the moment of crash

Apply each W(…) in time order.

Initial A = 10 B = 20

Time 3 → T1 W(A) A = 15 B = 20

Time 7 → T2 W(B) A = 15 B = 30

Time 11 → T3 W(A) A = 22 B = 30

Disk at crash A = 22 B = 30

STEP 3: Identify which transactions committed

| Transaction | Status            |
| ----------- | ----------------- |
| T1          | committed         |
| T2          | committed         |
| T3          | **not** committed |

Only T3 must be undone.

STEP 4: REDO committed transactions (T1 and T2)

Redo T1 → A should be 15 Redo T2 → B should be 30

These values are already correct on disk, so redo changes nothing.

Disk still: A = 22 B = 30

STEP 5: UNDO uncommitted transaction (T3)

T3 updated A from 15 → 22 Undo uses the before value = 15

So undo restores:

A = 15 B = 30

Final Values After Recovery

A = 15 B = 10