Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 79 ยท Recovery

Logging and Write-Ahead Logging

Learn log records, the write-ahead logging rule, undo and redo recovery and how SQLite uses a rollback journal or a WAL file, with a live crash simulation.

The previous lesson ended with the conclusion that a database which uses steal and no-force buffering needs a log. This lesson shows what the log contains, the one rule that makes it trustworthy (write-ahead logging), and how restart recovery uses it to undo unfinished transactions and redo finished ones. You will run a miniature database engine in Python, crash it at the worst moment, and recover it.

What a log is

Append-only New records go at the end, never in the middle.
Numbered Each record gets a log sequence number (LSN).
Forced at commit Commit means the commit record is on stable storage.
1 / 2

Log records

A log is a sequence of log records. The most common kinds, for a transaction T, are:

Record Meaning
<T, START> T began
<T, X, old, new> T changed item X from old to new (an update record)
<T, COMMIT> T finished successfully
<T, ABORT> T was rolled back and its undo is complete

An update record carries a before-image (old) and an after-image (new). The before-image is what allows undo, and the after-image is what allows redo. Real systems log changes to a page or a row rather than a single variable, and some store only the difference, but the principle is the same.

Every record has a log sequence number (LSN), a number that grows with each new record (in practice it is the position in the log file). Every data page remembers the LSN of the last record that changed it (its pageLSN), which will matter a lot in ARIES.

Log records first go into an in-memory log buffer and are then flushed to disk. Anything still in the buffer at the moment of a crash is lost, so the question "has this record been flushed yet?" matters.

The write-ahead logging rule

Write-ahead logging (WAL) is a pair of rules about the order of disk writes:

  1. Before a modified data page is written to disk, all log records describing changes to that page must already be on stable storage. This is what makes steal safe: if an uncommitted change reaches disk, the before-image that can remove it is already in the log.
  2. A transaction is committed only when all of its log records, including the commit record, are on stable storage. This is what makes no-force safe: committed changes may be missing from the data pages, but the after-images that restore them are in the log.

Break rule 1 and an uncommitted value can sit on disk with no record of what it replaced. Break rule 2 and a transaction can report success to the user, then lose its changes in a crash. The next example runs a toy engine and shows the consequences. The engine has a disk of pages, a buffer pool, a log with a "flushed up to" mark, and a crash() that throws away memory and the unflushed tail of the log. recover() does the usual two things: redo every logged update (repeating history), then undo the updates of transactions that never committed, last first.

Python A mini database engine with a write-ahead log

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study scenario 1. After the crash the disk is wrong in two ways: A holds the uncommitted 150 (stolen page), and B is missing the committed 250 (no-force). The log tail with T1's update of C is gone, but that is harmless because the page never reached disk. Recovery's redo pass reinstalls B = 250, and its undo pass restores A = 100 from the before-image. In scenario 2 the update record was never flushed, so after the crash the log has no trace of T1 at all. Rule 1 exists to prevent exactly this.

Undo and redo

The two passes of recovery correspond to the two ACID properties they protect:

  • Redo brings back the effects of committed transactions that never made it to disk. It uses after-images and is needed because of no-force.
  • Undo removes the effects of transactions that had no commit record. It uses before-images and is needed because of steal.

Two properties make this procedure safe to run again. First, redo and undo are idempotent: setting a value to new ten times has the same result as once. That matters because the machine can crash during recovery, and recovery then starts over. Second, the log is treated as the truth. Real systems add refinements: the redo pass skips an update if the page's LSN shows it is already applied, and every undo step writes a compensation log record so that a repeated recovery does not undo the same step twice. These refinements are the heart of ARIES, which comes next.

Rollback of a single transaction during normal operation uses the same undo logic: walk that transaction's records backwards and restore each before-image.

Deferred and immediate update

Textbooks distinguish two log-based schemes by when a transaction may change the database itself.

  • Deferred update (NO-UNDO/REDO): a transaction writes only to the log (and its private workspace) until it commits. After the commit record is on disk, the changes are applied to the database. A crash before commit needs no undo, because nothing reached the data pages; a crash after commit may need redo. Log records need only the new value. The drawback is that a transaction cannot read its own uncommitted changes from the database without extra bookkeeping, and every change must wait until commit.
  • Immediate update (UNDO/REDO): changes may reach the database before the transaction commits, always after the matching log record (the WAL rule). Recovery may need undo for unfinished transactions and redo for committed ones, so each record keeps the old and new value, such as <T1, Balance, 500, 600>. This is the scheme real systems use (steal and no-force).

A recovery example: the log has <T1,start> <T1,A,10,20> <T1,commit> <T2,start> <T2,B,5,9> and the machine crashes. T1 committed, so recovery redoes it (A = 20). T2 has no commit record, so recovery undoes it (B = 5, which immediate update restores from the before-image; deferred update simply ignores it). Variants named in exams: UNDO/NO-REDO forces every change to disk before commit, and NO-UNDO/NO-REDO is shadow paging (Shadow Paging).

How SQLite does it

SQLite is a good study object because its two durability mechanisms are the two halves of the theory, each in a file next to your database:

  • Rollback journal (the default, journal_mode = DELETE). Before SQLite overwrites a page in the database file, it copies the original page into a -journal file. The database file is then changed in place. If a crash happens, the next opener finds the journal and copies the old pages back (undo). Committing means the journal is deleted. This is an undo-only design: changed pages go to the database before commit, so it is "steal, force".
  • Write-ahead log (journal_mode = WAL). Changed pages are appended to a -wal file and the database file is left alone. A commit adds a commit mark to the log. If a crash happens, committed frames are in the log and uncommitted ones are ignored (redo). Later, a checkpoint copies pages from the WAL into the database file and resets the log. This is a redo-only design: uncommitted changes never reach the database file, so, as far as the database file is concerned, it is "no-steal, no-force".

You can inspect and change these settings with PRAGMA statements. The browser editor below runs SQLite in memory, so there are no real journal files, but the statements and a transaction still run:

SQL SQLite settings that control durability

Press Run (or Ctrl + Enter) to see the result here.

Because the data lives in memory, COMMIT here protects nothing across a browser reload. On a real database file, the same COMMIT is the moment SQLite makes the journal or WAL durable. The two other statements you would use in an application are shown below. They are read-only here, because they only make sense with a database file:

SQL
PRAGMA journal_mode = WAL;     -- switch to write-ahead logging (the setting persists in the file)
PRAGMA synchronous = FULL;     -- fsync the log at every commit, even on power loss

synchronous is the durability dial: lower settings skip some fsync calls and are faster, but a power failure (not just an application crash) can lose the latest commits or, at the lowest setting, damage the file.

Why logs make databases fast

It seems wasteful to write every change twice, once to the log and once to the data page. But the two writes are very different in cost. The log is written sequentially, in large chunks, and many transactions share one disk flush (group commit). The data pages are written randomly and can be postponed and merged: a page changed a hundred times needs only one write. The extra log write buys durability at sequential-I/O speed, while the data file catches up in the background.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the write-ahead logging rule require?

    The log must be ahead of the data. Then any change that reaches disk can always be undone or redone from the log.
  2. 2. After a crash the log shows T1 with a START and an update but no COMMIT, and the update's page is on disk. What does recovery do?

    T1 is a loser. The undo pass restores the before-image of every update that belongs to a transaction without a commit record.
  3. 3. Which information in an update record makes REDO possible?

    Redo reinstalls the new value, so it needs the after-image. Undo needs the before-image.
  4. 4. In SQLite's WAL mode, why do uncommitted changes never need to be undone in the database file?

    New page versions are appended to the WAL. Readers ignore frames of uncommitted transactions, and a checkpoint copies only committed frames into the database file.
  5. 5. Why must redo and undo be idempotent?

    A second crash during recovery restarts the process. Applying the same step again must give the same result as applying it once.

Summary

  • A log is an append-only sequence of records: start, update (with before-image and after-image), commit and abort, each with an LSN.
  • The WAL rule says log records go to stable storage before the data page they describe, and all records of a transaction before its commit completes.
  • Recovery redoes updates (repeating history) and then undoes updates of transactions without a commit record, newest first.
  • SQLite's rollback journal is an undo log, its WAL is a redo log, and PRAGMA journal_mode and PRAGMA synchronous select the mode and the durability level.
  • Sequential log writes make durable commits cheap, which is why the data pages can be flushed lazily.

Next: Checkpoints, ARIES and Backups.