Chapter 34 of 41

Recovery & Logging

Suppose you transfer ₹500 from your account to a friend's. The database subtracts ₹500 from your account, and just before it adds ₹500 to your friend's account, the power goes out.

When the server restarts, what should the database contain? The transfer did not finish, so the correct answer is: as if it never happened. And if the transfer had finished and you saw "Transaction successful", the money must still be there after the restart, even if it was only in memory at the time of the crash.

These two promises are the Atomicity and Durability in ACID (see Transactions & ACID Properties). The part of the DBMS that keeps them is the recovery manager, and its main tool is the log.

Recovery is the process of bringing the database back to a correct, consistent state after a failure: effects of committed transactions are kept, and effects of uncommitted transactions are removed.


Types of Failures

Failure

Example

What is lost

Transaction failure

Logical error (division by zero, constraint violation), or the system aborts it (deadlock victim)

Only that transaction's work

System crash

Power failure, OS crash, DBMS bug

Contents of main memory (buffer pool); disk survives

Disk (media) failure

Head crash, corrupted disk

Data on that disk

Log-based recovery mainly handles the first two. Disk failure needs backups and copies of the log on other devices, plus replication.

Storage Types

  • Volatile storage (RAM, caches): fast but lost on crash.

  • Non-volatile storage (SSD, HDD): survives crashes but can fail.

  • Stable storage: an idealised storage that never loses data, approximated by keeping multiple copies on independent non-volatile devices. The log is assumed to be on stable storage.


Why Is Recovery Hard? The Buffer Problem

A DBMS does not write to disk on every update. It reads disk blocks (pages) into a buffer pool in memory, modifies them there, and writes them back later. This is essential for speed but creates two dangers:

  • A committed transaction's changes may still be only in memory when the crash happens → they must be redone.

  • An uncommitted transaction's changes may already have been written to disk (the buffer manager needed the space) → they must be undone.

Two buffer policies decide which of these can happen:

Policy

Meaning

Consequence

Steal

Dirty pages of an uncommitted transaction may be written to disk

Need UNDO

No-steal

Uncommitted changes never reach disk

No undo needed, but buffer can fill up

Force

All pages changed by a transaction are written to disk at commit

No redo needed, but slow commits

No-force

Pages may stay in memory after commit

Need REDO

Real systems choose steal + no-force because it gives the best performance, and therefore need both undo and redo. The log makes both possible.


The Log

The log (or journal) is a sequential, append-only file that records every change made to the database. Common log records are:

<Ti start>                 Ti has started
<Ti, X, V_old, V_new>      Ti changed item X from V_old to V_new
<Ti commit>                Ti has committed
<Ti abort>                 Ti has finished rolling back
<checkpoint L>             a checkpoint; L = list of active transactions

With the old value we can undo a change, and with the new value we can redo it:

  • undo(Ti): go backwards through Ti's log records and set each X back to V_old.

  • redo(Ti): go forwards through Ti's log records and set each X to V_new.

Both operations are idempotent: doing them twice gives the same result as doing them once. This matters because the system might crash again during recovery and have to start over.

Why is appending to a log cheap enough? Because log writes are sequential, while writing modified data pages means random writes all over the disk. Writing a small log record at commit is far faster than forcing every changed page.


Write-Ahead Logging (WAL)

The log only helps if it reaches stable storage before it is needed. The Write-Ahead Logging rule says:

1. Before a modified data page is written to disk, all log records describing changes to that page must already be on stable storage.
2. A transaction is considered committed only after its <Ti commit> record (and all its earlier log records) has been written to stable storage.

Rule 1 makes undo possible: if an uncommitted change is on disk, its old value is guaranteed to be in the log. Rule 2 makes redo possible: if the user was told "committed", the new values are guaranteed to be in the log.

That is why a commit is so fast in practice: the DBMS only flushes the log, not the data pages.


Deferred vs Immediate Database Modification

Deferred Modification (NO-UNDO / REDO)

A transaction's writes are kept aside and applied to the database only after it commits. The log needs only new values.

  • After a crash: transactions with <Ti commit> in the log are redone; others are simply ignored, because they never touched the database.

  • Downside: all changes must be held until commit (a no-steal policy).

Immediate Modification (UNDO / REDO)

Writes may reach the database before commit. The log needs both old and new values. This is what real systems do.

  • Ti must be redone if the log contains <Ti start> and <Ti commit> (or <Ti abort> — redoing the undo actions, as we will see).

  • Ti must be undone if the log contains <Ti start> but neither commit nor abort.

Scheme

Undo needed?

Redo needed?

Log stores

Deferred modification

No

Yes

New values

Immediate modification

Yes

Yes

Old and new values


Checkpoints

Without help, recovery would have to scan the entire log since the database was created. A checkpoint limits how far back recovery must look. A simple checkpoint works like this:

  1. Temporarily stop new updates.

  2. Write all log records in memory to stable storage.

  3. Write all modified (dirty) buffer pages to disk.

  4. Write a <checkpoint L> record, where L lists the transactions active at that moment.

After this, any transaction that committed before the checkpoint is safely on disk and can be ignored during recovery. Only transactions in L, and those that started after the checkpoint, need attention.

Real systems use fuzzy checkpoints that do not stop the whole system while dirty pages are flushed, but the purpose is the same: bound the recovery work.


Worked Example: Recovery After a Crash

Initial values: A = 1000, B = 2000, C = 700, D = 500. The system uses immediate modification. This is the log at the moment of the crash:

 1  <T1 start>
 2  <T1, A, 1000, 950>
 3  <T2 start>
 4  <T2, C, 700, 600>
 5  <T1, B, 2000, 2050>
 6  <T1 commit>
 7  <checkpoint {T2}>
 8  <T3 start>
 9  <T3, A, 950, 900>
10  <T2, D, 500, 550>
11  <T2 commit>
12  <T4 start>
13  <T4, B, 2050, 2000>
    ─────── CRASH ───────

Step 1: Classify the Transactions

Transaction

Situation

Action

T1

Committed before the checkpoint

Nothing — its changes were flushed at the checkpoint

T2

Active at checkpoint, committed after it

Redo

T3

Started after checkpoint, no commit

Undo

T4

Started after checkpoint, no commit

Undo

Redo list = {T2}, undo list = {T3, T4}.

Step 2: Redo Phase (forward from the checkpoint)

The modern approach (used in Silberschatz-style recovery and in ARIES) is to repeat history: scan forward from the checkpoint and redo every logged update, committed or not, so that the database looks exactly as it did at the crash.

line  9: A = 900     (T3)
line 10: D = 550     (T2)
line 13: B = 2000    (T4)
(T2's update of C at line 4 is before the checkpoint, so it is already on disk: C = 600)

Step 3: Undo Phase (backward from the end)

Scan the log backwards and undo every update of transactions in the undo list:

line 13: undo T4 → B = 2050      log <T4, B, 2050>   (redo-only record)
line  9: undo T3 → A = 950       log <T3, A, 950>    (redo-only record)
then write <T4 abort> and <T3 abort>

Result

A = 950    (T1's committed change kept, T3's change removed)
B = 2050   (T1's committed change kept, T4's change removed)
C = 600    (T2 committed)
D = 550    (T2 committed)

We verified with a short Python script that this final state is reached whatever subset of the post-checkpoint updates (lines 9, 10 and 13) had actually reached the disk before the crash.

Notice the special redo-only (compensation) records written during undo. If the system crashes again in the middle of recovery, those records let the next recovery simply redo the undo work instead of getting confused. ARIES calls them Compensation Log Records (CLRs).

The older textbook version — "undo the incomplete transactions, then redo only the committed ones" — gives the same final answer in this example and is perfectly fine for exam questions that only ask for the undo and redo lists.


ARIES in Brief

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics), developed at IBM, is the basis of recovery in many real systems. Key ideas:

  • Every log record gets a Log Sequence Number (LSN). Each data page stores the PageLSN of the last change applied to it, so redo can skip changes already on the page.

  • Supports steal + no-force, fine-grained (row-level) locking and fuzzy checkpoints.

  • Recovery runs in three passes:

  1. Analysis: from the last checkpoint, find which transactions were active and which pages may be dirty.

  2. Redo: repeat history from the earliest relevant point, bringing every page to its state at the crash.

  3. Undo: roll back the transactions that were active at the crash, writing CLRs.


Shadow Paging

Shadow paging is a recovery technique that does not need a log in its basic form.

  • The database keeps a page table that points to the disk pages. When a transaction starts, the current page table is saved as the shadow page table.

  • When a page is modified, it is written to a new location on disk and only the current page table is changed to point there. The shadow table still points to the old page.

  • Commit = atomically switch a single pointer so the current page table becomes the official one.

  • Abort or crash = simply keep using the shadow page table. Nothing to undo or redo.

Shadow table       Disk pages        Current table
  page 1 ───────▶ [P1 old]  ◀─────── page 1
  page 2 ───────▶ [P2 old]
                  [P2 new]  ◀─────── page 2   (modified)
  page 3 ───────▶ [P3 old]  ◀─────── page 3

Drawbacks: copying the page table is expensive for large databases, data gets fragmented because pages move around, old pages must be garbage collected, and it is hard to support many concurrent transactions. The same "copy-on-write" idea, however, lives on in copy-on-write file systems such as ZFS and Btrfs.


How MySQL InnoDB Does It

InnoDB follows the same principles with its own names:

Concept

InnoDB component

Redo information

Redo log — physical page changes, written ahead of data pages (WAL). Size set by innodb_redo_log_capacity (100 MB by default in 8.4).

Undo information

Undo logs — old row versions, used for rollback and for MVCC consistent reads

Buffer pool

InnoDB buffer pool of 16 KB pages; steal + no-force

Checkpoints

Fuzzy checkpoints that flush dirty pages in the background

Torn-page protection

Doublewrite buffer: pages are first written to a separate area, so a page half-written during a crash can be restored

The setting innodb_flush_log_at_trx_commit controls the durability rule from WAL:

  • 1 (default): the redo log is written and flushed to disk at every commit. Fully durable.

  • 2: written to the OS at commit, flushed about once per second. An OS crash or power failure can lose up to about a second of commits.

  • 0: written and flushed about once per second. Even a mysqld crash can lose up to about a second of commits.

MySQL also has a separate binary log (binlog) of logical changes, used for replication and point-in-time recovery from backups. It is a different thing from the InnoDB redo log, which exists purely for crash recovery.


Common Mistakes

  • Undoing in forward order. Undo must go backwards so that the oldest old value ends up in place; redo goes forwards.

  • Redoing transactions that committed before the checkpoint. Not needed; the checkpoint already flushed them.

  • Forgetting transactions that were active at the checkpoint. They appear in the checkpoint's list L and may have log records before the checkpoint that need undoing.

  • Thinking WAL means "write the data before the log". It is the opposite: the log goes first.

  • Thinking deferred modification needs undo. It doesn't, because uncommitted changes never reach the database.


Interview Questions

What is write-ahead logging?

The rule that log records describing a change must reach stable storage before the changed data page does, and that a transaction commits only once its commit record is on stable storage.

Why do databases prefer steal/no-force?

Steal lets the buffer manager evict any page, and no-force makes commits fast because only the log is flushed. The price is needing both undo and redo during recovery.

What is the purpose of a checkpoint?

To limit how much of the log must be scanned and how many transactions must be redone after a crash.

Which transactions are undone and which are redone after a crash?

Transactions with a start record but no commit or abort record are undone. Transactions whose commit record appears after the last checkpoint are redone.

Why must undo and redo be idempotent?

The system can crash again during recovery and restart it from the beginning; applying the same operations again must not change the result.

Difference between InnoDB redo log and undo log?

The redo log records page changes so committed work can be reapplied after a crash. The undo log records old row versions so uncommitted work can be rolled back and so readers can see consistent snapshots.


Summary

  • Recovery guarantees atomicity (undo incomplete work) and durability (redo committed work).

  • Because of buffering, a crash can leave committed changes off disk and uncommitted changes on disk; steal/no-force needs both undo and redo.

  • The log records <start>, <update with old and new values>, <commit> and <abort>; WAL forces log records to stable storage first.

  • Deferred modification → redo only; immediate modification → undo and redo.

  • Checkpoints bound recovery; after a crash, redo committed transactions after the checkpoint and undo incomplete ones (backwards).

  • ARIES uses LSNs and three passes (analysis, redo, undo); shadow paging avoids a log by copy-on-write pages.

  • MySQL InnoDB uses a redo log, undo logs, a doublewrite buffer and innodb_flush_log_at_trx_commit to implement these ideas.

Both the log and the database live in files made of disk blocks. In the next chapter, File Organization, we look at how records are actually laid out in those blocks and files.