Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 42, Arpaci-Dusseau & Arpaci-Dusseau

Crash Consistency: FSCK and Journaling

Persistent structures must survive power loss. Updating several on-disk blocks is not atomic — a crash between writes leaves an inconsistent image.

Crux: how do we keep the on-disk FS in a reasonable state despite crashes at arbitrary times?

Example: append one block

An append dirties (at least) inode, data bitmap, and new data block. Any subset may reach disk:

Survives	Result
Data only	Looks like no-op (OK for metadata)
Inode only	Points to garbage; bitmap disagrees
Bitmap only	Space leak
Inode + bitmap	Consistent metadata, garbage data
Inode + data	Bitmap inconsistency
Bitmap + data	Orphan block

Ideal: move atomically from one consistent state to another. Disks write one request at a time → crash-consistency / consistent-update problem.

Solution 1: fsck

Old approach: allow inconsistency, repair before mount [MK96].

Checks include: superblock sanity, rebuild bitmaps from inodes, inode fields/links, duplicate/bad pointers, directory structure (. / .., no cycles). Orphans → lost+found.

Limits: can’t fix “consistent but wrong data”; cost is O(volume) — minutes/hours on large disks/RAIDs. Overkill for a three-block update.

Solution 2: Journaling (write-ahead logging)

Before overwriting final locations, write a note of the update to a journal (Cedar [H87]; ext3/4, XFS, NTFS, …). Recovery scans the log, not the whole disk.

Data journaling protocol

Journal write — TxB + physical blocks (+ metadata/data)
Journal commit — TxE (only after body durable)
Checkpoint — write blocks to final addresses
Free — mark tx reusable in journal superblock (circular log)

Issue TxE too early (or with reordered internals) and garbage can look like a valid transaction — hence ordered commit / barriers / transaction checksums (ext4) [P+05].

Batch many dirty blocks into one global transaction to avoid rewriting the same bitmap/dir over and over.

Quiz

Rank the sequence

1 / 1

Order the steps of the data journaling protocol (top = first).

OrderDrag the handle to rearrange — top should be first.

1Journal commit (write TxE)
2Free the transaction (mark reusable)
3Journal write (TxB + blocks)
4Checkpoint: write blocks to final locations

Drag items into the correct order (or use ↑↓), then check.

Metadata (ordered) journaling

Journal metadata only; write user data first (pointees before pointers) so recovery never makes an inode point at garbage. Cuts roughly half the write traffic vs full data journaling — the common default.

Block reuse after delete is subtle: replaying old journaled directory data can clobber a new file that reused the LBA → revoke records (ext3) [T00].

Other approaches

Approach	Idea
Soft Updates [GP94]	Order every write so disk is never illegal
COW / ZFS	Never overwrite in place; flip root atomically
Backpointers	Lazy check: forward ptr must match back ptr [C+12]
Optimistic journaling	Fewer waits via richer checksums [C+13]

Interactive

Try: partial-update failures · fsck · journal protocol · alternatives.

Check your understanding

Quiz