The Write-Ahead Log

Why this stage exists

Your commit writes every page the transaction changed, then syncs. Look at the moment between the first page and the last. A CREATE TABLE on a new file writes the header, the catalog's root and the table's root: three pages. If the power goes after the first, the header says the catalog has a root that the file does not hold. The database is not missing a commit; it is broken.

A disk writes one page at a time, at best. No ordering of page writes into the database file can make a commit of several pages atomic. The answer, which every serious database uses, is to make the commit a single small write somewhere else first:

1. Write down, in a separate file, the new contents of every page the commit will change.
2. Write one short record that says "this transaction is complete", and sync.
3. Only then change the database file.

If the program stops during step 1, the transaction never happened: there is no commit record. If it stops during step 3, the log holds everything needed to finish the job. The log is written ahead of the data, which gives it its name. This stage writes the log; the next one reads it back after a crash.

What changes: a second file

The log lives beside the database: x.db has x.db.wal. It starts with a 16-byte header and then holds records back to back, in the order they were written:

Every record starts with the same 16 bytes and ends with a checksum. A page record carries a full page in between; a commit record carries nothing:

The first 16 bytes of transaction 1's page record for page 2, the table's root. The page's 4096 bytes follow them, then the record's checksum:

The commit record of transaction 1, whole:

Why whole pages, and not "insert row 7 into users"? A record that names an operation can only be replayed by running the operation again, on a tree that must be exactly as it was the first time, and running it twice inserts twice. A page image needs none of that: recovery copies bytes to a page number, without knowing what a row or a tree is, and copying the same bytes twice gives the same page. The log does not care what is inside a page. The price is size: a 60-byte row costs a 4096-byte record.

Real engines mix both. PostgreSQL logs a full page image the first time a page changes after a checkpoint and compact operation records after that; InnoDB logs operations on pages. Both need recovery code that understands the page format, which this engine avoids.

A record's log sequence number is where it starts in the file. The first record is at 16; a page record moves the next one 4116 bytes on, a commit record 20. Transaction ids are handed out at commit, one more than the largest in the log.

PostgreSQL's LSN is also a position in its log, which never goes back. SQLite's WAL file is the same idea as this one: a header, then frames of one page each, and a commit marked in the last frame of a transaction.

What changes: a commit in four steps

Each note is a fail-point. Start the program with DROID_FAILPOINT=after_log_sync and it stops there the first time it gets there, exactly as .crash does. That is how the tests look at the files in each state, and how you can too:

A clean end of session leaves no work for the log: every committed page is in the database file. So .exit, the end of input and the end of -c cut the log back to its header. After a crash it keeps everything.

Output contract for this stage

The full definition is on the output contract page, sections 32 and 35.

size is the whole file. The records listed are the good ones, from the first up to the first that is cut short or fails its checksum. Writing the log does not count in pager stats: writes counts database pages only.

What you should see when done

On a new file:

$droid --db notes.db
Welcome to droid!
>wal status
[WAL] Status: size=0 records=0
>create table notes (id int, text varchar(100));
Create table statement executed successfully
>insert into notes (id, text) values (1, 'buy milk');
Insert statement executed successfully (1 rows)
>wal status
[WAL] Status: size=16520 records=6
[WAL]   Record 1: lsn=16 tx=1 type=PAGE page=0
[WAL]   Record 2: lsn=4132 tx=1 type=PAGE page=1
[WAL]   Record 3: lsn=8248 tx=1 type=PAGE page=2
[WAL]   Record 4: lsn=12364 tx=1 type=COMMIT
[WAL]   Record 5: lsn=12384 tx=2 type=PAGE page=2
[WAL]   Record 6: lsn=16500 tx=2 type=COMMIT
>.exit
exiting.. good bye!
$ls -l notes.db notes.db.wal
-rw-r--r-- 1 you you 12288 notes.db
-rw-r--r-- 1 you you    16 notes.db.wal

The CREATE TABLE changed three pages, the header, the catalog's root and the new table's root, and the INSERT changed the table's root again. The size is the header, three page records, a commit record, one more page record and its commit record: 16 + 3 × 4116 + 20 + 4116 + 20 = 16520. After .exit the log is its header and nothing else.

Then stop a commit half way and look at both files:

$DROID_FAILPOINT=after_log_sync droid --db notes.db -c "insert into notes (id, text) values (2, 'call mom');"
$echo $?
3
$ls -l notes.db notes.db.wal
-rw-r--r-- 1 you you 12288 notes.db
-rw-r--r-- 1 you you  4152 notes.db.wal

The database file did not change. The log holds the new page and the commit record. What to do with them when the program starts again is the next stage.

Common bugs in this stage

• Writing the database file first. The whole stage is the order. A test stops the program after the log sync and checks that the database file is byte for byte what it was.
• Logging the page as it was. A page record holds the page after the transaction, the bytes the database file is about to get, with their trailer computed. The old bytes are what ROLLBACK needs, and they never go in the log.
• A commit record before the pages. The commit record must come after every page record of its transaction, or a crash between them leaves a "committed" transaction with missing pages.
• Forgetting to sync, or syncing the wrong file. The log is the file that must be durable before the commit counts. Syncing only the database file at the end gives no guarantee about the log at all.
• Logging a transaction that changed nothing. BEGIN and COMMIT around a SELECT, or a failed INSERT in autocommit, append nothing: no page records and no commit record.
• Deleting the log at exit. A clean end cuts it back to its 16-byte header; the file stays.
• Counting the checksum from the wrong place. It covers every byte of the record before it, length included, and nothing of the record after it.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: open the log with O_APPEND or keep its end offset yourself; fsync(fd) after the commit record. ftruncate(fd, 16) empties it. The fail-points are getenv("DROID_FAILPOINT") read once at start and compared with strcmp where each point is, then _exit(3).
• C++: std::getenv for the fail-point; the file descriptor (open, write, fsync) is simpler here than streams, which have no portable sync.
• Rust: OpenOptions::new().append(true) for the log, sync_all after the commit record, set_len(16) to empty it. Build each record in a Vec<u8> and write it with one write_all, so a record is never half in a buffer.
• Zig: std.posix.getenv for the fail-point, file.sync() for the log, file.setEndPos(16) to empty it. Write each record from one buffer.