Created by Turbolearn AI

Database Recovery Techniques

Recovery Concepts
The recovery process restores the database to the most recent consistent state
before a failure. Information is maintained in the system log.

Typical recovery strategies:

Restore a backed-up copy of the database (best for extensive damage).

Identify changes that may cause inconsistency (best for non-catastrophic
failure).
Some operations may require a redo.

Deferred Update Techniques

Do not physically update the database until after the transaction commits.
Undo is not needed; redo may be needed.

Immediate Update Techniques

The database may be updated by some operations of a transaction before
it reaches a commit point. Operations are also recorded in the log, making
recovery possible.

Idempotent Operations
Undo and redo operations are required to be idempotent.

Executing operations multiple times is equivalent to executing them just

once. The entire recovery process should also be idempotent.

Caching (Buffering)
DBMS cache: A collection of in-memory buffers.
The cache directory tracks which database items are in the buffers.

Page 1
 Created by Turbolearn AI

Cache Buffer Management

Cache buffers are replaced (flushed) to make space for new items.
Dirty bit: Indicates whether a buffer has been modified. Contents are written
back to disk before flushing if the dirty bit equals one.
Pin-unpin bit: A page is pinned if it cannot be written back to disk yet.

Main Strategies

Strategy Description

In-place Writes the buffer to the same original disk location, overwriting old
updating values.
Writes an updated buffer at a different disk location to maintain
Shadowing
multiple versions (not typically used).
Before-image (BFIM): Old value of a data item.
After-image: New value of a data item.

Write-Ahead Logging
Ensure the before-image (BFIM) is recorded and the appropriate log entry
is flushed to disk. Necessary for UNDO operation if needed. Includes
UNDO-type and REDO-type log entries.

Steal/No-Steal and Force/No-Force

Specify rules that govern when a page from the database cache can be
written to disk.

No-steal approach: A cache buffer page updated by a transaction cannot be

written to disk before the transaction commits.
Steal approach: Recovery protocol allows writing an updated buffer before the
transaction commits.
Force approach: All pages updated by a transaction are immediately written to
disk before the transaction commits. Otherwise, it's a no-force approach.
Typical database systems employ a steal/no-force strategy. This avoids the
need for very large buffer space and reduces disk I/O operations for heavily
updated pages.

Page 2
 Created by Turbolearn AI

Write-Ahead Logging Protocol

For recovery algorithms requiring both UNDO and REDO:

BFIM of an item cannot be overwritten by its after image until all UNDO-type
log entries have been force-written to disk.
The commit operation of a transaction cannot be completed until all REDO-type
and UNDO-type log records for that transaction have been force-written to
disk.

Checkpoints in the System Log and Fuzzy

Checkpointing

Taking a Checkpoint
1. Suspend execution of all transactions temporarily.
2. Force-write all main memory buffers that have been modified to disk.
3. Write a checkpoint record to the log and force-write the log to disk.
4. Resume executing transactions.

The DBMS recovery manager decides on the checkpoint interval.

Fuzzy Checkpointing
The system can resume transaction processing after a begin_checkpoint
record is written to the log. The previous checkpoint record is maintained
until the end_checkpoint record is written.

Transaction Rollback
When a transaction fails after an update but before a commit, it's necessary to roll
back the transaction. Old data values are restored using undo-type log entries.

Cascading Rollback
If transaction T is rolled back, any transaction S that has read a value of an
item written by T must also be rolled back. Almost all recovery
mechanisms are designed to avoid this.

Page 3
 Created by Turbolearn AI

Transactions That Do Not Affect the Database

Example actions include generating and printing messages and reports. If a
transaction fails before completion, the user may not want these reports. Reports
should be generated only after the transaction reaches a commit point. Commands
that generate reports are issued as batch jobs executed only after the transaction
reaches a commit point. Batch jobs are canceled if the transaction fails.

NO-UNDO/REDO Recovery Based on Deferred

Update
Postpone updates to the database on disk until the transaction completes
successfully and reaches its commit point. Redo-type log entries are
needed, but undo-type log entries are not necessary.

Can only be used for short transactions and transactions that change few items.
Buffer space is an issue with longer transactions.

Deferred Update Protocol

A transaction cannot change the database on disk until it reaches its commit
point.
All buffers changed by the transaction must be pinned until the transaction
commits (no-steal policy).
A transaction does not reach its commit point until all its REDO-type log entries
are recorded in the log, and the log buffer is force-written to disk.

Recovery Techniques Based on Immediate

Update
The database can be updated immediately, without waiting for the transaction to
reach a commit point. It is not a requirement that every update be immediate. UNDO-
type log entries must be stored.

Recovery algorithms:

UNDO/NO-REDO (steal/force strategy)

UNDO/REDO (steal/no-force strategy)

Page 4
 Created by Turbolearn AI

Shadow Paging
No log is required in a single-user environment. A log may be needed in a
multi-user environment for concurrency control.

Shadow paging considers the disk to be made of n fixed-size disk pages. A directory
with n entries is constructed. When a transaction begins executing, the directory is
copied into a shadow directory to save while the current directory is being used. The
shadow directory is never modified.

Process
1. A new copy of the modified page is created and stored elsewhere.
2. The current directory is modified to point to the new disk block.
3. The shadow directory still points to the old disk block.

Failure Recovery
1. Discard the current directory.
2. Free the modified database pages.

This is a NO-UNDO/NO-REDO technique.

The ARIES Recovery Algorithm

Used in many IBM relational database products. Uses a steal/no-force approach for
writing.

Concepts
Write-ahead logging
Repeating history during redo: Retrace all database system actions prior to a
crash to reconstruct the database state when the crash occurred.
Logging changes during undo: Prevents ARIES from repeating completed undo
operations if a failure occurs during recovery.

Steps

Page 5
 Created by Turbolearn AI

1. Analysis:
Identifies dirty (updated) pages in the buffer and the set of transactions
active at the time of the crash.
Determines the appropriate start point in the log for the REDO operation.
2. REDO:
Reapplies updates from the log to the database.
Only necessary REDO operations are applied.
3. UNDO:
The log is scanned backward.
Operations of transactions that were active at the time of the crash are
undone in reverse order.

Log Sequence Number (LSN)

Every log record has an associated log sequence number (LSN), which
indicates the address of the log record on disk and corresponds to a
specific change of some transaction.

Recovery in Multidatabase Systems

Requires a two-level recovery mechanism. A global recovery manager (coordinator)
is needed to maintain recovery information.

Two-Phase Commit Protocol

1. Phase 1: Prepare for commit message. A ready to commit or cannot commit
signal is returned.
2. Phase 2: Issue commit signal. Either all participating databases commit the
effect of the transaction, or none of them do.

It's always possible to recover to a state where either the transaction is committed or
it is rolled back. Failure during Phase 1 requires a rollback. Failure during Phase 2
means a successful transaction can recover and commit.

Database Backup and Recovery from

Catastrophic Failures

Page 6
 Created by Turbolearn AI

Database Backup
The entire database and log are periodically copied onto an inexpensive
storage medium.

The latest backup copy can be reloaded from disk in case of a catastrophic failure.
Backups are often moved to physically separate locations like subterranean storage
vaults.

System Log Backup

The system log is backed up at more frequent intervals and copied to
magnetic tape.

The system log is smaller than the database and can be backed up more frequently.
Benefit: users do not lose all transactions since the last database backup.

Page 7