Pointer Walk

The Write Path and the Write-Ahead Log

Five stops before a write is done: parse, lock, append to the log, flush to disk, acknowledge.

DatabasesAdvanced10 min read

What "saved" has to mean

When a database tells your app a write succeeded, it is making a promise: this change will still be there after a crash. Not "probably". Even if the power fails one millisecond later.

That promise is called durability, and keeping it is harder than it sounds.

  • Memory is fast, and it is wiped when the power goes.
  • Disk survives, but writing to the right place in a large data file is slow. A single change can touch several places, and a crash halfway through leaves the file in a broken state.

Databases solve both problems with one idea.

Write the intention down first

Before changing anything permanent, the database appends a short note to the end of a separate file: "set balance of account 7 from 100 to 50". That file is the write-ahead log, often shortened to WAL.

Appending to the end of a file is the fastest thing a disk can do. Once the note is safely on disk, the change cannot be lost. The slow work of updating the real data file can then happen later, in the background.

The rule: the log is written before the data. Hence "write-ahead".

One write, five stops

One write, five stops before "done"Interactive
App
Database memory
Log (disk)
empty
Data file (disk)
balance = 100

Follow one change to an account balance through the database.

  1. Parse

    Read the statement, check it, and plan how to run it.

  2. Lock

    Lock the rows involved so nothing else changes them at the same time. The change is then made in memory.

  3. Append to the log

    A description of the change is added to the end of the log.

  4. Flush to disk

    The database waits until the operating system confirms the log entry is physically stored. This step dominates the time a write takes.

  5. Acknowledge

    Only now does the app hear "done".

Look at the data file at the moment of "done": it still holds the old value. That is not a mistake. The log is what makes the write safe. The data file catches up afterwards.

Why the log makes a crash survivable

A crash, and the recoveryInteractive
App
Database memory
Log (disk)
empty
Data file (disk)
balance = 100

Follow one change to an account balance through the database.

After a restart the database reads the log from its last known safe point and replays it: every change recorded there is applied again. Any write that was acknowledged is in the log, so it comes back.

What about a transaction that was halfway through when the power failed? It never reached "flush and acknowledge", so the app was never told it succeeded. The database discards it. That gives the other half of the promise: a transaction is applied completely or not at all.

Checkpoints: keeping the log short

If the log grew for ever, recovery would have to replay years of history. So every so often the database makes sure all changes up to some point are written into the data files, and records that point. This is a checkpoint. Recovery only needs to replay what came after it, and older log can be recycled.

One write, five stops before "done"Interactive
Scenario
App
Database memory
Log (disk)
empty
Data file (disk)
balance = 100

Follow one change to an account balance through the database.

What else the log is used for

Once every change is written down in order, that record turns out to be useful for much more than crashes.

  • Replication. A second server receives the same log and replays it, staying a copy of the first.
  • Backups to a point in time. Restore an old backup, then replay the log up to the minute before the mistake.
  • Streaming changes. Other systems read the log to hear about every insert and update as it happens.

Key takeaways

  • A write is only safe once it is on disk, and updating data files directly is slow and fragile.
  • The database first appends a description of the change to a log and flushes it to disk.
  • Only after that flush is the app told the write succeeded.
  • The data files are updated later. After a crash, replaying the log restores every acknowledged change.
  • The same log powers replication and point-in-time recovery.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress