Log-based recovery and checkpoints

Why it exists

A transaction promises two things that a crash can break. Atomicity: all of its changes or none. Durability: once it has committed, its changes survive. But the database lives in two places. The disk keeps data safely but is slow, so changes are made in memory buffers and written out later. When the machine crashes, the memory is lost: the disk may then hold half of an uncommitted transaction's work (a page was written out early) and may lack the work of a transaction that already committed (its pages were not yet written). The system needs a record, kept safely, of what every transaction did, so that after a crash it can undo the unfinished work and redo the finished work. That record is the log.

Prerequisites

You need the four properties of a transaction (transactions and ACID), and the idea that a rolled-back transaction is undone by restoring the values it overwrote, which is only safe when nobody else has touched them (strict schedules, obtained by strict two-phase locking). Everything on this page assumes strict schedules: a value written by an unfinished transaction is not read or overwritten by another.

Precise definitions

Failures. A transaction failure (a logical error, a deadlock victim) affects one transaction. A system crash (power, operating system) loses the memory but not the disk. A media failure destroys the disk; the remedy is a backup plus the archived log, and it is not treated here. The model of this page is the system crash, with stable storage (the disk and the log on it) assumed to survive.

The log is a sequence of records appended in order and written to stable storage. In the notation of the textbook of Silberschatz, Korth and Sudarshan, a transaction $T_i$ writes:

The old value $V_1$ is what undo uses; the new value $V_2$ is what redo uses.

The write-ahead rules.

1. Write-ahead logging (WAL): before a modified page is written to the database on disk, the log records that describe its changes must already be on stable storage. Otherwise a crash could leave an uncommitted change on the disk with no record of the old value.
2. Commit rule: a transaction counts as committed only after its commit record, and with it every earlier record of the log, is on stable storage. Otherwise a crash could lose a transaction that was reported as committed.

Buffer policies. Steal: the buffer manager may write a page that contains uncommitted changes to disk (to free a frame). No steal: it may not. Force: at commit, every page the transaction changed is written to disk before the commit completes. No force: commit writes only the log; the pages follow later. Real systems use steal and no force, because they are the fastest.

What each policy makes necessary. Steal means an uncommitted value can be on the disk after a crash, so undo information is needed. No force means a committed value can be missing from the disk after a crash, so redo information is needed.

Immediate and deferred modification. In immediate modification the changes reach the buffer (and possibly the disk) as the transaction runs; the log needs old and new values (UNDO/REDO). In deferred modification nothing is changed in the database until the transaction commits: its writes are only logged (new value only, <Ti, X, V>) and held in a private workspace, and are applied after the commit record is on the log. An uncommitted value never reaches the disk, so only redo is ever needed (NO-UNDO/REDO).

Checkpoint (simple form). The system writes the log to stable storage, writes every modified page to disk, and then appends <checkpoint L>. After a checkpoint, everything done by transactions that had already committed is on the disk, so recovery need not look at the log before the checkpoint for them.

Recovery by repeating history (the algorithm of the textbook), run after a crash on the stable log:

• Redo pass. Find the last checkpoint record. Set the undo-list to its list $L$. Scan forward from it: redo every update (and compensation) record by writing the new value; when <Ti start> is read, add $T_i$ to the undo-list; when <Ti commit> or <Ti abort> is read, remove $T_i$.
• Undo pass. Scan backward from the end of the log. For every update record of a transaction in the undo-list, write the old value and append a compensation record <Ti, X, V1>; when <Ti start> of a transaction in the undo-list is reached, append <Ti abort> and remove it. Stop when the undo-list is empty.

Idempotence. Writing a value is idempotent: doing it twice equals doing it once. So recovery can be started again, from the beginning, if the system crashes while recovering.

How it works

One history, event by event

Look at three things in the table. First, the log on disk mark lags behind the log: a record is forced only at a commit, a checkpoint, or when a page it describes is written out. Second, the memory and disk lines differ: after $T_1$ commits, $A = 90$ is in memory only (no force); after event 10 the disk holds $C = 310$ written by $T_3$, which never commits (steal). Third, the last update, $T_3$ writing $B = 260$, is in the volatile tail and is lost with the memory: recovery will never hear of it, and it need not, because it never reached the disk (the page could only be written after its log record was forced).

Recovery of that crash

The last checkpoint lists $T_2$ as active, so the undo-list starts as {T2}. The redo pass repeats everything after the checkpoint, including the update of $T_3$ that is going to be undone (this is what "repeating history" means) and the update $A = 120$ of $T_2$, which was never on the disk. At the end of the redo pass, $T_2$ is out of the undo-list (its commit record was read) and $T_3$ is in it (no commit record). The undo pass walks back, restores $C = 300$ and writes the compensation record and <T3 abort>. The result, $A = 120$, $B = 250$, $C = 300$, is exactly the work of the committed transactions $T_1$ and $T_2$.

The quick rule for exam questions

For a log without rollbacks, the same final database follows from two lists:

• undo-list: the transactions that have a start record but no commit record. Restore their old values, scanning the log backward.
• redo-list: the transactions that committed after the last checkpoint. Write their new values, scanning forward.
• Transactions that committed before the last checkpoint need nothing: the checkpoint wrote their pages.

A transaction that was active at the checkpoint and committed after it is in the redo-list (its updates after the checkpoint may be missing from the disk; the ones before it were written by the checkpoint, and redoing them again does no harm). Undo comes first and redo second: an item may have been written by a committed transaction and then by an unfinished one.

The table crashes the history of the first table after every event. The redo and undo lists change as commits and the checkpoint reach the stable log; in this history nothing at all is on stable storage before the first commit, so a crash in the first four events leaves a disk that was never touched, and recovery has nothing to do. In all twelve cases both procedures give the committed work.

Deferred against immediate modification

The two schemes meet the same crash. With immediate modification the page of $B$ reached the disk before $T_2$ committed, so the disk holds an uncommitted value and the log must supply the old value $200$. With deferred modification $T_2$'s write never left the log, so there is nothing to undo, the log records need only the new value, and recovery only redoes. The price of deferral: every write must be kept in a private workspace, and a transaction must be able to read its own writes from there.

Why steal and no force force the design

The table enumerates every crash state of two small transactions under each buffer policy. Steal produces states with uncommitted data on the disk (undo needed) and no force produces states with committed data missing (redo needed); a policy that forbids both needs neither. The last row is a warning: forcing pages one at a time before the commit record is not atomic, and a crash in the middle leaves part of the transaction on the disk, so undo is needed again. The "neither undo nor redo" row is therefore only true if the commit can switch all of a transaction's pages at once; that is what shadow paging provides, at a high price (see below).

Each ingredient is necessary

A check with deliberately broken variants confirms that nothing in the design is decoration: if the write-ahead rule is dropped (pages written before their log records), some crashes leave a stolen value on the disk with no old value to restore; recovery with only a redo pass, or only an undo pass, is wrong on roughly one random history in six. The log must reach the disk before the page; the commit record must reach the disk before the commit is reported.

Crash during recovery

Every action of the recovery passes is a write of a value to the disk or an append to the log. The compensation records written during the undo pass make a partly finished undo look like a transaction that was rolled back partway, and the next recovery handles it by undoing the same updates again. The check stopped recovery after every single action and ran it again: the result was the same database every time. In an exam this is the statement "recovery is idempotent: a crash during recovery is handled by running recovery again".

Shadow paging and ARIES (quoted)

Shadow paging keeps two page tables: the current one, used by the running transaction, and the shadow one, which points to the pages as they were before the transaction. A write goes to a new copy of the page. Commit makes the current table the shadow table with one atomic write. No log is needed and a crash needs no undo or redo (the shadow table is simply used), but the pages scatter over the disk, old pages must be reclaimed, and concurrent transactions are hard to support, so it is rarely used. ARIES is the recovery method of most real systems: it uses steal and no force, write-ahead logging, a sequence number on every log record and on every page, an analysis pass (to rebuild the list of active transactions and modified pages), a redo pass that repeats history and an undo pass that writes compensation records, exactly the structure above plus the bookkeeping that makes it fast. These two paragraphs are textbook content; they are not computed by the tools of this page.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The log is what makes atomicity and durability true. Undo by before-images is correct only for strict schedules, which strict two-phase locking produces. Steal and no force are buffer-management decisions of the same kind as the write policies of a cache (cache replacement and write policies): write-back against write-through, with a log added because a database cannot lose a committed update.

PYQs

Suppose a database system crashes again while
recovering
from
a
previous
crash.
Assume
checkpointing is not done by the database either during
the transactions or during recovery. Which of the
following statements is/are correct?

Consider a simple checkpointing protocol and the
following set of operations in the log.

(Start, T4);

(write, T4, y, 2, 3);

(Start, T1);

(commit, T4);

(write, T1, z, 5, 7);

(check point);

(Start, T2);

(write, T2, x, 1, 9);

(commit, T2);

(start, T3);

(write, T3, z, 7, 2);

If a crash happens now and the system tries to recover
using both undo and redo operations, what are the
contents of the undo list and the redo list?

Consider the following log sequence of two transactions on
a bank account, with initial balance 12000, that transfer
2000 to a mortgage payment and then apply a 5% interest.

1. T1 start

2. T1 B old=12000 new=10000

3. T1 M old=0 new=2000

4. T1 commit

5. T2 start

6. T2 B old=10000 new=10500

7. T2 commit

Suppose the database system crashes just before log record
7 is written. When the system is restarted, which one
statement is true of the recovery procedure?

Self-check

Revision card

References