Part 4 of 7 · 2 min read
Write-ahead logging
Think of a builder who writes in a notebook "I will move wall A, then door B, then window C" before touching anything. If the builder is called away in the middle, the notebook shows exactly what was planned, and the work can be finished or cancelled. The analogy stops in one place: a builder reads the notebook by eye, and the OS replays a log by rule.
In plain words: A journal is a small area of the disk that holds a log of planned changes. For one transaction, the file system first writes all the blocks that it intends to change into the journal, then writes a commit record that says the transaction is complete. Only then does it write the blocks to their real places, which is the checkpoint. After a crash, the file system reads the journal at mount time. A transaction with a commit record is replayed: its blocks are written to their real places again, which is safe to repeat. A transaction without a commit record is ignored. Either way, the disk ends in the old state or in the new one, and nothing in between. The tool dumpe2fs -h shows that a new ext4 file system had a journal of 4 MiB (4,194,304 bytes).
A worked example (made up to show the idea). An append changes three metadata blocks: the inode block, the bitmap block and (say) a directory block. The journal writes are one descriptor block, the three blocks and one commit block: 5 writes, in a sequential area. The checkpoint then writes the 3 blocks to their real places: 3 writes. The total is 8 writes for 3 changes. Metadata is written twice, which is the price of the safety. Recovery needs no scan of the whole disk: it reads the journal. Reading 4 MiB at 100 MB/s takes 4,194,304 / 100,000,000 s = 42 ms, instead of the 11.5 minutes of fsck.
The key lines. The order is the point. The commit record must reach the disk after the logged blocks, and the checkpoint must start after the commit. If the disk reorders writes, the file system uses a barrier or a cache flush to keep that order (Level 8, page 5).
Journal (write-ahead log)
A journal is an area of a file system in which changes are first recorded as a transaction, with a commit record at the end. After a crash, a committed transaction is replayed and an uncommitted one is discarded, so that every change is applied completely or not at all.
Example: a transaction that logs the inode, bitmap and directory blocks, then a commit block, and is later checkpointed to the real locations.
Check yourself:
1. What is written first, and what is written last, in one transaction?
2. After a crash, what happens to a transaction without a commit record?
3. Why is recovery with a journal faster than fsck?