Checkpoints and ARIES Recovery Algorithm in DBMS

21
0

Introduction

After a crash, a database may contain a mixture of saved changes and missing updates. Some transactions committed successfully, while others stopped halfway through their work. Recovery must preserve committed results and remove incomplete effects.

Checkpoints save information that helps recovery find the relevant work. ARIES is a recovery method that uses this information and the transaction log to recover through three phases: Analysis, Redo, and Undo.

Example Table

Consider an Account table containing account identifiers, holder names, and balances.

Account: initial data

AccountID

HolderName

Balance

1

Asha

1000.00

2

Ravi

500.00

AccountID is the primary key and uniquely identifies each account.

Two separate transactions perform the following operations:

Transaction

Operation

Outcome before the crash

T1

Add 100 to Asha’s balance.

Commits successfully.

T2

Subtract 50 from Ravi’s balance.

Remains uncommitted.

These are independent transactions, not two parts of a transfer.

After recovery, Asha’s committed addition must remain, while Ravi’s incomplete deduction must disappear.

Why Does Recovery Need Checkpoints?

Databases commonly update working copies of data in memory before writing them to storage.

A page is a unit of data managed by the database. A dirty page is a page that has changed in memory but has not yet been written back to its data file.

The recovery log records information about these changes. However, a database may have a long log history. Starting recovery from the beginning of that history would involve unnecessary work.

A checkpoint records recovery information at a known point. This helps the database locate the transactions and pages that may still need attention after a crash.

A checkpoint does not mean every transaction has committed, and it is not a backup.

Blocking and Fuzzy Checkpoints

Checkpoint designs differ in how much they interrupt normal processing.

Checkpoint approach

Basic idea

Main trade-off

Blocking checkpoint

Temporarily pauses relevant database activity while checkpoint work is completed.

Simpler coordination, but transactions may wait.

Fuzzy checkpoint

Records recovery information while transactions continue.

Less interruption, but recovery must account for changes made during the checkpoint.

The exact page-writing steps depend on the database and checkpoint design.

Fuzzy Checkpoints in ARIES

ARIES uses fuzzy checkpoints. A checkpoint records information about:

  • Transactions still in progress: Their status and relevant log positions.

  • Dirty pages: Pages whose changes may not yet be safely reflected in their data files.

ARIES writes checkpoint-begin and checkpoint-end information into the log. A persistent pointer identifies the latest completed checkpoint so recovery can find it.

A fuzzy checkpoint does not require every dirty page to be flushed before it completes. Flushing means writing buffered information to persistent storage.

For this reason, recovery may still need log records from before the checkpoint.

What a fuzzy checkpoint keeps

What a fuzzy checkpoint keeps

What Is ARIES?

ARIES stands for Algorithms for Recovery and Isolation Exploiting Semantics.

Its central idea is:

Reconstruct the necessary logged history first, then remove unfinished transaction effects.

ARIES builds on Write-Ahead Logging (WAL). WAL requires the necessary log records to become durable before their corresponding changed data pages are written to storage.

ARIES supports two useful storage policies:

  • STEAL: A page containing uncommitted changes may be written to storage. Recovery must be able to remove those incomplete effects.

  • NO-FORCE: Commit does not require all changed data pages to be written immediately. Recovery must be able to restore missing changes.

These policies help database performance, but they make both Redo and Undo important.

Information ARIES Uses

A few small pieces of information help ARIES avoid guessing during recovery.

Information

Meaning

Purpose

LSN

Log Sequence Number: a position identifying a log record.

Tracks the order of logged actions.

Transaction table

Tracks transactions that have not finished recovery bookkeeping, including their status and latest log record.

Helps determine which transactions need further action.

Dirty Page Table (DPT)

Tracks pages that may contain changes not yet written to storage.

Helps locate possible Redo work.

recLSN

The earliest log position from which a tracked dirty page might need Redo.

Helps determine where Redo should begin.

pageLSN

The log position of the latest change reflected in a page.

Helps avoid reapplying a change already present on that page.

The Dirty Page Table can be conservative: a listed page may already have been written. Recovery checks the page itself before deciding whether a change needs replaying.

The Three ARIES Recovery Phases

ARIES performs recovery in the following order:

Phase

Main question

Main task

Analysis

What was happening when the crash occurred?

Rebuild transaction and dirty-page information.

Redo

Which logged changes are missing from pages?

Repeat the necessary logged history.

Undo

Which transaction effects must not remain?

Reverse unfinished transaction work.

Three phases of ARIES

Three phases of ARIES

1. Analysis: Identify the Required Work

Analysis uses the latest completed checkpoint and scans forward through the log.

It reconstructs transaction status and information about pages that may need recovery.

For the account example, Analysis determines that:

  • T1 committed, so its addition must remain.

  • T2 did not commit, so its deduction must be removed.

Analysis also identifies a possible starting position for Redo using the Dirty Page Table.

2. Redo: Repeat the Necessary History

Redo reconstructs missing logged changes in forward log order.

An important point is that Redo is not limited to committed transactions. It can also replay changes made by transactions that will later be undone.

This restores a known state before incomplete effects are removed.

Redo does not blindly repeat every operation. For example, if a page’s pageLSN shows that a particular change is already present, that change does not need to be applied again.

The Redo starting position may be earlier than the checkpoint if a page has older changes that still need recovery.

3. Undo: Reverse Unfinished Work

Undo reverses the necessary changes of transactions that did not commit.

It follows their log history backward so that later changes are undone before earlier ones.

For the account example, Undo removes T2’s deduction and restores Ravi’s balance from 450.00 to 500.00. It does not remove T1’s committed addition.

A Small ARIES Recovery Example

Suppose the following events occur. The log shown is conceptual, not actual database log syntax.

Log position

Event

10

T1 starts.

20

T1 changes Asha’s balance from 1000.00 to 1100.00.

30

A fuzzy checkpoint begins.

40

The checkpoint completes and records that Asha’s page may still need recovery from log position 20.

50

T1 commits durably.

60

T2 starts.

70

T2 changes Ravi’s balance from 500.00 to 450.00.

After 70

The database crashes before T2 commits.

For this example, assume:

  • The two accounts are stored on separate pages.

  • Asha’s changed page has not reached its data file.

  • Ravi’s changed page has reached its data file.

  • The required log records through position 70 are durable.

  • No other transactions change these accounts.

Writing Ravi’s uncommitted page is allowed by the STEAL policy. WAL ensures that its recovery information reaches durable storage first.

State at the Crash

The data files contain:

AccountID

HolderName

Balance in data file

1

Asha

1000.00

2

Ravi

450.00

This is a physical storage state, not the correct final result.

Analysis

Analysis identifies T1 as committed and T2 as unfinished.

Asha’s page may need Redo from log position 20. This demonstrates why a fuzzy checkpoint at positions 30 and 40 does not make all earlier log records unnecessary.

Redo

Recovery restores Asha’s missing addition.

Ravi’s page already contains the change at position 70, so its pageLSN allows Redo to skip applying that deduction again.

AccountID

HolderName

Balance after Redo

1

Asha

1100.00

2

Ravi

450.00

Undo

Recovery reverses T2’s incomplete deduction.

Final recovered result

AccountID

HolderName

Balance

1

Asha

1100.00

2

Ravi

500.00

The committed addition remains. The uncommitted deduction is removed.

ARIES recovery example

ARIES recovery example

What If Another Crash Happens During Recovery?

Undo itself changes database pages. A second crash could interrupt that work.

ARIES records Undo actions using Compensation Log Records (CLRs).

A CLR describes an action taken to undo an earlier change. It also helps recovery locate the next action that still needs undoing.

For example, reversing Ravi’s deduction creates a CLR describing the restoration from 450.00 to 500.00.

If another crash occurs after that CLR becomes durable:

  • Redo can reapply the CLR’s action if the restored page was not saved.

  • Undo can continue from the remaining work.

  • The CLR itself is not undone.

Recording recovery progress makes repeated crashes manageable.

A Compact SQL Example

The following queries demonstrate the same committed and rolled-back outcomes as the recovery example.

They do not run the ARIES phases or control which pages reach disk. Recovery internals differ across database systems.

1. Create the Initial Data

Objective: Create the starting account balances.

Consider the following queries to create and populate Account.

CREATE TABLE Account (
AccountID INT PRIMARY KEY,
HolderName VARCHAR(50) NOT NULL,
Balance DECIMAL(10, 2) NOT NULL
);
START TRANSACTION;
INSERT INTO Account (AccountID, HolderName, Balance)
VALUES
(1, 'Asha', 1000.00),
(2, 'Ravi', 500.00);
COMMIT;
SELECT AccountID, HolderName, Balance
FROM Account
ORDER BY AccountID;

Expected result

AccountID

HolderName

Balance

1

Asha

1000.00

2

Ravi

500.00

2. Preserve T1 and Cancel T2

Objective: Keep Asha’s addition while removing Ravi’s deduction.

Consider the following queries to commit T1 and roll back T2.

-- T1: Keep Asha's addition.
START TRANSACTION;
UPDATE Account
SET Balance = Balance + 100.00
WHERE AccountID = 1;
COMMIT;
-- T2: Cancel Ravi's deduction.
START TRANSACTION;
UPDATE Account
SET Balance = Balance - 50.00
WHERE AccountID = 2;
ROLLBACK;
SELECT AccountID, HolderName, Balance
FROM Account
ORDER BY AccountID;

Expected result

AccountID

HolderName

Balance

1

Asha

1100.00

2

Ravi

500.00

COMMIT completes T1. The later ROLLBACK affects only T2, so it does not remove Asha’s committed addition.

The result matches the required outcome after the conceptual ARIES recovery.

Checkpoint, Commit, and Backup Are Different

Operation

Main purpose

What it does not mean

Commit

Successfully completes a transaction.

Every changed data page has been written immediately.

Checkpoint

Records recovery progress and helps limit restart work.

All active transactions have committed or all earlier logs are disposable.

Backup

Provides a recoverable copy of database data.

No later logs are needed to recover more recent changes.

Checkpoint frequency involves a trade-off. More frequent checkpoint work can reduce recovery effort, but it also adds processing and storage activity. The exact effect depends on the database’s checkpoint and page-flushing design.

Summary

Checkpoints help recovery locate relevant transaction and page information. ARIES uses fuzzy checkpoints, allowing normal work to continue without requiring every dirty page to be flushed. Recovery may still need log records from before the checkpoint.

ARIES performs Analysis, Redo, and Undo: identify the required work, reconstruct necessary logged history, and remove unfinished transaction effects. Page log positions prevent unnecessary replay, while compensation log records allow recovery to continue safely after another crash.

CS Core

Read Similar Blogs

Comments0