How do databases handle recovery

Table of Contents

• Recovery Logging

Recovery Logging

Database systems use Write-Ahead Logging (WAL) to ensure durability and crash recovery. Logs are stored in stable storage, which refers to storage systems that can survive crashes and media failures. Stability is usually achieved by maintaining multiple copies of data on non-volatile storage devices.

Every log record is assigned a unique identifier known as a Log Sequence Number (LSN). LSNs are monotonically increasing, meaning newer log records always have larger LSN values than older records. Recently generated log records are first buffered in main memory before being flushed to disk.

The recovery manager keeps track of the latest log record written to disk using a metadata value called flushedLSN. In addition, every data page maintains a pageLSN, which stores the LSN of the most recent update applied to that page.

The pageLSN helps the recovery system determine whether a log record has already been applied to a page during the redo phase. If the page's LSN on disk is greater than or equal to the log record's LSN, the recovery manager can safely skip reapplying that operation because the update is already persisted.

Transaction Table (TT)

The Transaction Table contains one entry for each active transaction.

Dirty Page Table (DPT)

The Dirty Page Table tracks pages in the buffer pool that have been modified but not yet written back to disk.

Unlike pageLSN, which stores the most recent update applied to a page, the recLSN in the Dirty Page Table stores the earliest log record that caused the page to become dirty. During recovery, this allows the redo phase to identify the correct starting point for replaying updates.

Update Log Records

Whenever a transaction updates a page P, the system generates an update log record r. The page's pageLSN is then updated to match the LSN ofr.

An update log record typically contains:

To undo the actions of a transaction, the recovery manager scans the transaction's log records in reverse order and restores each record's before-image.

Crash Recovery Phases

Modern recovery algorithms such as ARIES perform recovery in three phases:

During the undo phase, every rollback operation is itself logged using a Compensation Log Record (CLR). This ensures recovery can continue safely even if another crash occurs during the undo process.