The Crash-Consistency Problem: A Detailed Example

File-system structures must persist — survive power loss and crashes. That makes updating them surprisingly hard: a single logical operation often needs several disk writes, but the disk commits only one at a time. Crash between them, and the on-disk image is left half-updated.

The Crux: How To Update The Disk Despite Crashes

The system may crash between any two writes, leaving the on-disk state only partially updated. Since crashes strike at arbitrary times, how do we keep the file system in a reasonable state? This is the crash-consistency problem .

42.1 A Detailed Example

Take a concrete workload: append one 4 KB block to an existing file (open, lseek to the end, write, close). In a small file system — inode bitmap, data bitmap, 8 inodes, 8 data blocks — one file already exists (inode 2, pointing to data block 4). Watch what the append must change:

A tiny file system: an inode bitmap and data bitmap (gold), inodes and data blocks (brown). One file exists; we append a block to it. Green outlines mark the three structures the append must update.

1Before: one file

Inode 2 is allocated (I[v1], size 1) and points to data block 4 (Da). The inode bitmap has bit 2 set; the data bitmap has bit 4 set. Everything is consistent.

step 1 / 2

The inode goes from I[v1] (size 1, one pointer → block 4) to I[v2] (size 2, pointers → blocks 4 and 5). So the append is three writes: the inode I[v2], the data bitmap B[v2], and the new data block Db. These sit dirty in the page cache and get flushed later — and a crash can strike after only some of them reach disk.

The crash scenarios

Suppose the crash lets only one or two of the three writes complete. Each partial outcome leaves a different mess:

The append needs three writes (I[v2], B[v2], Db), but the disk does one at a time. If a crash lands after only some succeed, here is what remains on disk — and what's wrong.
	writes that succeeded	on-disk state	problem?
Db only	Db only	data is on disk, but no inode points to it and the bitmap says block 5 is free	none (for FS consistency)
I only	I[v2] only	inode points to block 5, but Db was never written there; bitmap still says 5 is free	garbage read + inconsistency
B only	B[v2] only	bitmap says block 5 is allocated, but no inode references it	inconsistency + space leak
I + B	I[v2] + B[v2]	metadata fully agrees (inode → 5, bitmap says 5 used), but Db never landed	garbage data
I + Db	I[v2] + Db	inode points to correct data on disk, but the bitmap still says 5 is free	inconsistency (inode vs bitmap)
B + Db	B[v2] + Db	bitmap and data are written, but no inode points to the block	inconsistency + orphan data

Dotted-underlined cells have explanations — click one.

Several of these are a file-system inconsistency : the FS’s own structures disagree (the inode says block 5 is used; the bitmap says it’s free). One case even leaks space forever; another looks perfectly consistent yet hides garbage data. What we really want is to move the file system from one consistent state to another atomically — but the disk won’t let us, because it commits one write at a time. The rest of the chapter is about how to get that atomicity anyway.

Check yourself: the crash-consistency problem

1.What makes updating on-disk file-system structures tricky across crashes?

2.Appending one block to a file requires updating which three structures?

3.If a crash lets ONLY the data block (Db) reach disk — not the inode or bitmap — what's the consequence?

4.If ONLY the updated inode (I[v2]) reaches disk, what goes wrong?

5.If ONLY the updated data bitmap (B[v2]) reaches disk, what's the result?

6.The case where I[v2] AND B[v2] are written but NOT Db is especially nasty. Why?

6 questions