SQLite Internals: Pages, Rollback Journal and WAL

The idea: a database is one file of pages

A SQLite database is one ordinary file. The file is cut into pages of the same size, set by PRAGMA page_size (4096 bytes by default, any power of two from 512 to 65536). Page n sits at byte offset (n − 1) × page_size. SQLite never reads or writes less than a page. Page 1 starts with the 100-byte database header: the 16 bytes "SQLite format 3\0", the page size, the file change counter and the database size in pages. The rest of page 1 is the root of sqlite_schema, the table that lists every table and index and its root page.

The canvas follows a write through three places: connection A's page cache in memory, the database file app.db, and the second file that makes the commit atomic, app.db-journal or app.db-wal. Connection B is a reader that runs SELECT name FROM users WHERE rowid = 5.

Table b-trees and index b-trees

Every table is a table b-tree keyed by the 64-bit rowid. Its leaf pages hold the records, sorted by rowid. Its interior pages hold only divider keys and child page numbers: on page 2, ≤3→p3 means "rowids up to 3 are under page 3", and the right-most pointer →p4 takes everything larger. To find rowid 5, B reads root page 2 and then leaf page 4. A real tree is usually only 3 or 4 levels deep, because one 4 KB interior page holds hundreds of pointers.

Every index is a separate index b-tree whose keys are (indexed columns, rowid) and that holds no other data. Page 5 is the only page of idx_users_name. So an UPDATE of a name changes two b-trees: the record on leaf page 4 and the key in index page 5.

When a leaf is full, an insert splits it. For the common case of appending the largest rowid, SQLite uses a quick balance: the new row goes alone on a newly allocated page, and the parent gets a new divider. In Demo: INSERT that splits a leaf page, row 7 lands on new page 6, page 2 gains ≤6→p4 and points right to p6, and page 1's database size goes from 5 to 6.

The pager and the page cache

The b-tree code never touches the file. It asks the pager for page n, and the pager returns a copy from its page cache (PRAGMA cache_size, about 2 MB by default), reading it from disk first if needed. Before the b-tree may change a page, it tells the pager, which marks the page dirty (orange on the canvas). The pager alone decides when dirty pages reach the file, and how the change is made atomic: either every page of a transaction is on disk, or none is. It has two ways to do that, chosen with PRAGMA journal_mode.

A commit with a rollback journal

In the default mode, journal_mode=DELETE, the pager keeps the old pages aside and writes the new ones in place (Demo: commit with a rollback journal):

1. Take a SHARED lock and read the needed pages into the cache.
2. Take RESERVED: this connection is going to write.
3. Before changing each page, write its original content to app.db-journal. The journal header records the original size of the file. Pages past the original end (a new page from a split) need no copy: rollback just truncates the file.
4. Change the pages in the cache. Page 1's change counter goes up too, so other connections know their caches are stale.
5. COMMIT: fsync the journal.
6. Take PENDING, then EXCLUSIVE, write the dirty pages into app.db, fsync it.
7. Delete the journal. That delete is the commit point.

The journal is not the slow part people expect: the two fsync calls are. That is why a batch of inserts in one transaction is so much faster than the same inserts each in its own.

The five lock states

In rollback mode every connection holds one of five locks on the database file. They make "many readers or one writer" work across processes, with only the operating system's file locks.

Lock	Means	Others may
UNLOCKED	no access	anything
SHARED	reading	read; one may take RESERVED
RESERVED	will write, changes only in its cache so far	keep reading, start new reads
PENDING	wants EXCLUSIVE, waits for readers to leave	finish their reads, but no new SHARED
EXCLUSIVE	writing app.db	nothing

A lock that can't be had returns SQLITE_BUSY. With PRAGMA busy_timeout set, SQLite's busy handler sleeps and retries for that long first. In Demo: reader vs writer, rollback journal, B holds SHARED, so A's COMMIT stops at PENDING with SQLITE_BUSY. When B ends its read and tries to begin a new one, B gets SQLITE_BUSY: PENDING keeps new readers out so a writer can't be starved by a stream of readers. Only after A commits does B read the new name.

Crash recovery: the hot journal

If the power fails while A writes app.db, the file is a mix of new and old pages. The journal, already fsynced, still holds every original. The next connection that opens the database and wants to read finds the journal and checks that no one holds RESERVED: the journal is hot. It takes EXCLUSIVE, copies the originals back, truncates the file to its original size, fsyncs and deletes the journal. The cut-off transaction is gone, as if it had never started (Demo: crash mid-commit, hot journal rollback). If the power failed before the journal was fsynced, app.db had not been touched yet, so there is nothing to undo.

Other journal modes change only step 7: TRUNCATE truncates the journal to zero bytes, PERSIST zeroes its header. Both are commit points like the delete, and faster on some filesystems.

Write-ahead logging: frames and the wal-index

With journal_mode=WAL the pager works the other way round: it leaves app.db alone and appends the new pages to app.db-wal. Each page goes into a frame: a 24-byte header (page number, salt values, checksum) and the page. The last frame of a transaction is a commit frame: its header holds the size of the database after the commit. Once the commit frame is fsynced the transaction is durable. Unlike the rollback journal, page 1 is not rewritten on every commit; it changes only when the database grows.

To find the newest copy of a page, readers use the wal-index, a hash table kept in the shared-memory file app.db-shm. It maps page number → frame and holds mxFrame, the last valid commit frame. When a reader begins, it records mxFrame as its read mark. For every page it reads, it takes the newest frame at or before its mark, or the page in app.db if there is none.

A crash in WAL mode needs no undo. At the next open the wal-index is rebuilt from app.db-wal: frames are checked by checksum and salt, and only frames up to the last commit frame count. In Demo: WAL crash before the commit frame, the committed UPDATE (frames 1–2) survives even though it was never checkpointed, and the INSERT's lone frame 3 is ignored and later overwritten.

Checkpoints and wal_autocheckpoint

The WAL can't grow for ever. A checkpoint copies the newest frame of each page back into app.db, fsyncs it and records how far it got (nBackfill). When every frame is copied and no reader still uses the WAL, the next writer starts again at frame 1. By default the connection that commits runs a checkpoint once the WAL holds 1000 pages (PRAGMA wal_autocheckpoint = 1000); the canvas uses 8 frames so you can see it. A checkpoint can't copy a frame newer than an active reader's mark: that reader still reads the older page from app.db, and overwriting it would change data under it. PASSIVE (the automatic kind) copies what it can and stops there; FULL, RESTART and TRUNCATE wait for readers.

Readers and the writer in the two modes

In Demo: reader vs writer, WAL, B begins with mark 0 and reads 'Eve' from app.db. A commits 'Zoe' into frames 1–2 without waiting. B reads again in the same transaction and still gets 'Eve': a consistent snapshot. The checkpoint copies nothing while B reads. After B ends and begins again, its mark is 2 and it reads page 4 from frame 1: 'Zoe'.

	Rollback journal (DELETE)	WAL
Where new pages go	into app.db, after the originals are saved	appended to app.db-wal
Commit point	deleting the journal	the fsynced commit frame
fsyncs per commit (synchronous=FULL)	2+ (journal, db)	1 (wal)
Writer vs readers	writer waits at PENDING; readers get SQLITE_BUSY while it writes	neither blocks the other
A reader sees	the file as it is (no writer can change it meanwhile)	a snapshot as of its read mark
Crash recovery	roll back from the hot journal	rebuild the wal-index, drop frames after the last commit
Limits	works everywhere	all processes on one machine (shared memory); writers still one at a time

Other databases solve the same problem with a log too: see Write-Ahead Logging and ARIES, PostgreSQL WAL internals, and InnoDB's doublewrite buffer for torn pages. For the page layout of another engine, see Inside an InnoDB index page; for the trees themselves, B+ trees and a B+ tree as a database index.

What the page leaves out

Real pages hold cells with varint headers, a cell pointer array, freeblocks and overflow pages for big records; SQLite's table b-trees are B+ trees and its index b-trees plain B-trees. The page leaves out the freelist, auto-vacuum and pointer-map pages, the full balance algorithm that redistributes cells over three siblings, the journal's two-step header write (nRec, then a second fsync), the statement journal, master journals for multi-database commits, locking_mode=EXCLUSIVE, synchronous=NORMAL (no fsync per commit in WAL), the WAL's salts and checksum chain, the five read-mark slots and how a reader can use one already set, BEGIN IMMEDIATE and the SQLITE_BUSY deadlock when two readers both try to upgrade, mmap I/O, and the page cache's own eviction and spill.

References

Database File Format (sqlite.org)

Atomic Commit In SQLite (sqlite.org)

File Locking And Concurrency In SQLite Version 3 (sqlite.org)

Write-Ahead Logging (sqlite.org)