Search Knowledge

© 2026 LIBREUNI PROJECT

Page 21 of 29

Crash Consistency and Journaling

Crash-state reasoning, write ordering, write-ahead logs, checkpointing, recovery idempotence, and the boundary between model output and storage guarantees.

Lesson briefPersistence · 6 h · 4 outcomes

Required knowledge

  • Filesystem inodes, directories, allocation bitmaps, and buffer caches
  • State machines, invariants, and concurrent critical sections
  • Block-device queues, DMA, caches, and completion semantics

Learning outcomes

  • Enumerate every crash-visible state of a multi-block filesystem update under explicit persistence assumptions.
  • Derive write-ahead logging order from namespace and allocation invariants.
  • Prove whether a recovery procedure is atomic and idempotent for a bounded transaction model.
  • Distinguish modeled crash outcomes, syscall visibility, acknowledged persistence, and measured device behavior.

Assessment target

Given an unfamiliar metadata update and a stated device model, construct its crash matrix, identify illegal states, derive a recovery protocol, and defend the protocol's assumptions and omissions.

Scope boundary

  • Distributed consensus, database ARIES, persistent-memory ordering, RAID write holes, and full ext4/JBD2 implementation details are outside the bounded recovery model.
  • The simulator assumes atomic sector writes and an honest stable-storage acknowledgement; torn writes and lying devices require additional mechanisms.

A file grows from one block to two. The kernel must initialize a new data block, mark it allocated, and publish its address and the new size in the inode. Power fails after the inode reaches stable storage but before the data and bitmap. After reboot, the inode exposes a block the allocator considers free; another file can receive the same block, and the first read may disclose stale bytes.

Locks cannot repair this failure. They constrain live interleavings, but a crash erases lock state and volatile memory. Recovery correctness requires a protocol over persistence order: which subsets of writes may survive, which subset becomes authoritative, and how reboot code distinguishes complete from incomplete updates.

The crash model is part of the theorem

Use a bounded block-device model unless a problem states otherwise:

  • a block write may be delayed or reordered before stable acknowledgement;
  • after an acknowledged flush or equivalent barrier, preceding writes in the specified domain are stable;
  • a sector write is atomic: recovery observes its old or new value, not a torn mixture;
  • volatile kernel and controller state disappears at the crash;
  • the device does not silently lose a write it acknowledged as stable; and
  • recovery itself may crash and run again.

These are assumptions, not universal hardware facts. A controller without protected write-back power, a filesystem mounted with weaker barriers, or a device that violates flush semantics invalidates the proof. Checksums and duplicated headers can detect some torn writes; they cannot manufacture durability from a device that lies about persistence.

Define four properties separately:

propertyquestion
runtime atomicitycan another live operation observe an intermediate namespace state?
crash atomicityafter recovery, is the update entirely absent or entirely present?
durabilityafter the documented success/barrier point, must the update survive the modeled crash?
recovery idempotencedoes running recovery twice produce the same authoritative state as running it once?

A filesystem may provide one without all four. An atomic rename constrains concurrent name visibility; it does not, by itself, state that the renamed data or directory entry is durable.

Crash consistency, write ordering, and journaling invariants

0 / 4 answered

Evaluate each statement regarding filesystem crash consistency, journaling, and recovery idempotence:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Installing modified blocks directly to their home locations before writing log descriptors preserves crash recovery invariants.
2
Physical block redo logging is strictly idempotent because installing full-block images repeatedly yields identical disk state.
3
Write-ahead logging mandates that transaction log blocks must be durable on media before the commit record is written.
4
A successful rename call guarantees that file data blocks are completely committed to persistent storage across sudden crashes.

Derive invariants before ordering writes

Model one append with Boolean state (D,B,I)(D,B,I)

  • DD new block contains the intended bytes;
  • BB allocation bitmap marks the block owned;
  • II inode size and block map expose the block.

The minimum safety invariants are

I⇒BandI⇒D.I \Rightarrow B \qquad\text{and}\qquad I \Rightarrow D.

B∧¬IB\land\neg I is unreachable allocated space: a leak, but not cross-file aliasing. D∧¬B∧¬ID\land\neg B\land\neg I is an unreachable overwrite of a free block and can destroy data if the allocator had concurrently assigned it; the single-operation model assumes the allocator reserved the block in volatile state while the operation ran. I∧¬BI\land\neg B is dangerous because the same block can be reallocated. I∧¬DI\land\neg D exposes stale or partial content.

Worked crash trace: metadata-first append

Suppose home-location writes reach stable storage in this order: inode, bitmap, data. Crashes produce:

crash cutdurable tuplediagnosis
before any write(0,0,0)complete pre-state
after inode(0,0,1)dangling reference and stale-data exposure
after bitmap(0,1,1)inode exposes uninitialized content
after data(1,1,1)complete post-state

Reversing the writes to data, bitmap, inode avoids an exposed uninitialized block in this one append:

crash cutdurable tuplediagnosis
after data(1,0,0)namespace remains old; new bytes unreachable
after bitmap(1,1,0)leaked allocation
after inode(1,1,1)complete post-state

Ordering reduces damage but does not give crash atomicity: the leak is neither the complete pre-state nor post-state. More complex operations have cyclic dependencies. Replacing a file can require the new directory edge before removing the old to avoid loss, while link counts and replacement targets require another order. A general mechanism needs a commit point separate from home locations.

Application checkpoint: derive, do not memorize

A directory insertion requires a new directory data block. The operation changes bitmap bit BB directory-inode pointer PP directory size SS and entry bytes EE State necessary implications for a visible new name, then propose a data-before-metadata order and identify its remaining non-atomic state.

Reveal the dependency analysisExpand

If lookup can reach the new entry, then the directory’s block pointer and size must expose the block, the block must be allocated, and the entry bytes must be initialized. One compact set is

(P∧S)⇒B,(P∧S)⇒E.(P\land S)\Rightarrow B, \qquad (P\land S)\Rightarrow E.

A conservative home-write order is initialize EE persist BB then publish PP and SS together if they occupy one atomically written inode block. Crashing after BB but before publication leaks the block. If PP and SS can tear or occupy different atomic units, more intermediate states exist. The correct diagnosis is “ordered but not atomic,” not “safe because metadata was last.”

Prediction before the recovery model

The journal contains a complete redo image for every block in transaction 9. Its commit record is stable. None of transaction 9’s home-location writes is stable when power fails. Predict the recovered state and name the ordering rule your answer relies on.

Interactive exploration

Pull the power during a file-system update

Append block B to a one-block file. Move the crash point through unsafe ordering, ordered metadata, write-ahead journaling, and copy-on-write publication; then inspect what recovery can prove.

Crash after: journal commit record reaches stable storage
Crash point: 2 of 6
  1. 1. journal records the complete transaction
  2. 2. journal commit record reaches stable storage
  3. 3. home data block is written
  4. 4. home bitmap is written
  5. 5. home inode is written
  6. 6. journal transaction is checkpointed

On disk when power fails

data block 2
old / absent
allocation bitmap
free
inode / active root
old file only

Visible after recovery

data block 2
B written
allocation bitmap
allocated
inode / active root
references block 2
Recovery result: Committed journal transaction is replayed: post-state is restored.

Model scope: one append, atomic sector writes, stable write order once acknowledged, and no torn writes. Real file systems must also handle caches that reorder or lose writes, checksums, concurrent transactions, device flush semantics, and recovery idempotence.

Pull the power during a file-system update

On disk when power fails

data block 2
old / absent
allocation bitmap
free
inode / active root
old file only

Visible after recovery

data block 2
B written
allocation bitmap
allocated
inode / active root
references block 2
Recovery result: Committed journal transaction is replayed: post-state is restored.

Static state: power fails after a durable journal commit but before home-location writes. Recovery replays the committed transaction and restores the complete post-state.

The modeled answer is the complete post-state: recovery recognizes the durable commit and replays every logged block to its home location. The conclusion depends on all transaction records becoming stable before the commit record and on the commit record being atomically recognizable. Move the crash point to one step before commit; the same records are ignored because no authoritative commit exists.

Transfer after changing one assumption

Replace the atomic-sector assumption with “a commit sector may tear into a mixture of old and new bytes.” What additional evidence must recovery require before replay?

Reveal the strengthened commit ruleExpand

Recovery needs a commit representation whose validity can be distinguished from every relevant torn state—for example a checksummed, versioned record with redundancy or an atomic write unit guaranteed by the actual device. The checksum domain must cover transaction identity and the record set it commits; otherwise a valid old commit could be paired with unrelated new records. Recovery must reject an invalid or incomplete commit and preserve the pre-state.

A checksum makes corruption detectable with a quantified residual collision risk; it does not force preceding records to stable storage. Ordering/barrier semantics and commit integrity solve different obligations.

Write-ahead logging from three obligations

A physical redo log stores intended new block images in a reserved region before installing them at home locations. Let R(T)R(T) be all records for transaction TT and C(T)C(T) its commit record. The protocol follows from three obligations:

  1. Write ahead: every member of R(T)R(T) is stable before C(T)C(T) may become stable.
  2. Publish once: C(T)C(T) is the sole recovery-visible decision that TT is committed.
  3. Do not overwrite evidence early: log space for TT is reusable only after its committed records are installed at home and that checkpoint state is stable.
Code
participant "filesystem operation" as FS
participant "buffer/log manager" as LM
participant "stable log" as LOG
participant "home blocks" as HOME
participant "recovery" as REC
FS -> LM : begin transaction T
FS -> LM : dirty blocks A, B, C
LM -> LOG : write descriptor + redo A, B, C
LOG --> LM : records stable
LM -> LOG : write commit C(T)
LOG --> LM : commit stable
LM -> HOME : install A, B, C
HOME --> LM : home writes stable
LM -> LOG : release/checkpoint T
... crash and reboot ...
REC -> LOG : scan valid records and commits
alt C(T) valid
REC -> HOME : replay all of R(T)
else C(T) absent or invalid
REC -> REC : ignore R(T)
end
filesystem operationfilesystem operationbuffer.log managerbuffer.log managerstable logstable loghome blockshome blocksrecoveryrecoveryfilesystem operationfilesystem operationbuffer/log managerbuffer/log managerstable logstable loghome blockshome blocksrecoveryrecoverybegin transaction Tdirty blocks A, B, Cwrite descriptor + redoA, B, Crecords stablewrite commit C(T)commit stableinstall A, B, Chome writes stablerelease/checkpoint Tcrash and rebootscan valid records andcommitsalt[C(T) valid]replay all of R(T)[C(T) absent or invalid]ignore R(T)

The home installation may write A, B, and C in any order after commit because the log retains a complete post-state. If power fails midway, recovery replays all three. Replaying a physical block image twice is idempotent: writing the same final bytes again does not change the result.

Recovery proof obligation. For every crash cut, recovery returns a state observationally equivalent to the pre-state of every uncommitted transaction and the post-state of every committed transaction, while preserving filesystem invariants.

This statement requires a transaction-serialization model. If two committed transactions update the same block, recovery must respect their log order or replay the latest committed image. If a log record is reused before all earlier home writes are stable, the only repair evidence may be destroyed.

Worked trace: atomic name replacement

Transaction 12 replaces directory entry config -> inode 40 with config -> inode 71 and decrements inode 40’s link count from 1 to 0. Its physical log contains new images for directory block D and inode block I.

durable log/home state at crashrecovery actionvisible result
D record stable, I record absent, no commitignore transaction 12old name and old link count
both records stable, no commitignore transaction 12old name and old link count
both records and commit stable, no home writesreplay D and Inew name; old inode unlinked
commit stable, only home D installedreplay bothnew name; old inode unlinked
commit stable, both home blocks installed, log not clearedreplay both harmlesslysame complete post-state

Replaying only the missing-looking inode block would require recovery to infer which home bytes are current, a harder protocol. Whole-transaction redo keeps the decision local: valid commit means install every record.

Proof checkpoint: idempotence is not optional

Recovery replays transaction 12’s directory block, then power fails before it replays the inode block. Explain why restarting recovery must replay the directory block again and why an increment-style log record would be dangerous.

Reveal the proof stepExpand

The commit is still present, so the restarted scan cannot assume that any subset reached home. A physical redo record says “set block D to these bytes”; applying it twice yields the same D. An operation record saying “decrement inode 40’s link count” is not idempotent: replaying it twice decrements twice unless the protocol carries transaction identity and per-object application state. Logical logging can be correct, but it needs a stronger replay design than blind repetition.

Concurrency changes transaction admission

Compact xv6 brackets filesystem system calls with begin_op and end_op. It reserves enough log capacity for worst-case operations before admitting more work. Modified buffers are registered with log_write; repeated modifications to one block are absorbed into one transaction entry. A commit occurs only when no filesystem operations remain active, preventing a commit from installing a block that still contains another operation’s uncommitted update.

This design is intentionally restrictive:

  • several system calls may share one log transaction;
  • long operations must fit the bounded log reservation model;
  • one outstanding commit simplifies ordering but limits throughput; and
  • a syscall joining other active operations may return before their shared transaction commits, depending on the exact implementation path and completion timing.

Therefore a user-visible “write returned” claim must not be silently upgraded to “power-safe.” The documented synchronization interface and the implementation’s actual commit semantics determine that boundary.

Application checkpoint: reservation arithmetic

A log has 30 data slots. Each admitted operation reserves a worst-case 10 slots, although duplicate-block absorption often makes actual use smaller. Why may begin_op block the fourth concurrent operation even when the first three currently occupy only six unique slots?

Reveal the safety argumentExpand

Admission must remain safe if every active operation reaches its worst case after the check. Three operations can require all 30 slots. Admitting a fourth based on current use can deadlock or overflow later, when none can surrender partial work without violating atomicity. Conservative reservation trades concurrency for a simple capacity proof. A more concurrent design needs finer-grained preclaims, multiple transactions, abort support, or dynamically extensible log space; observed average use is not a proof.

Production contrast: ext4 modes are different contracts

Linux ext4 uses JBD2 to journal metadata updates. The journal contains descriptors, logged blocks, and a commit record; replay applies transactions with valid commits. The documented data modes differ:

modejournaled contentrelevant promise boundary
data=journalfile data and metadatastrongest of these modes, with additional write cost
data=orderedmetadata; associated new data is ordered before metadata commitdefault documented mode, avoiding some stale-data exposure
data=writebackmetadata; data need not precede metadataweaker post-crash file-content expectations

The table is not a complete ext4 guarantee. Delayed allocation, direct I/O, fsync, directory persistence, device flushes, fast commits, checksums, and kernel versions affect a real claim. A teaching log and JBD2 share write-ahead reasoning; their scale, concurrency, record formats, and user-visible contracts are not interchangeable.

Failure boundaries that invalidate easy proofs

  • Torn sectors: an apparently present header may be half old and half new.
  • Reordered caches: issuing records before commit is insufficient unless stable order is enforced.
  • Lost acknowledgement: a device claiming a flush completed but losing it violates the model.
  • Log checksum omission: recovery may replay corrupted or mismatched records.
  • Log reuse before checkpoint: a second transaction can overwrite the only redo image for the first.
  • Recovery side effects: a non-idempotent replay operation can corrupt more on each boot.
  • Unbounded transaction: a rename or allocation path that exceeds reserved log capacity cannot be made atomic by wishing it fit.
  • Interface confusion: runtime atomicity and a successful return are not equivalent to post-crash durability.
Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 6.3.1: The Three Write-Ahead Logging Ordering Rules

Verificationapplication

State the three fundamental write-ordering rules governing physical block redo journaling. For each rule, state the catastrophic crash failure mode that occurs if that rule is violated.

HintExpand

Rule 1: Log before Commit. Rule 2: Commit before Home. Rule 3: Home before Log Reuse.

Worked solutionExpand

The three write-ahead logging (WAL) invariants are:

  1. Rule 1 (Log records before Commit): All transaction data and metadata blocks written into the journal must reach stable storage before the commit record is written.
    • Failure if violated: If the commit record arrives on disk first and power fails while journal blocks are still inflight, recovery will observe a “committed” transaction header and replay garbage or unwritten bytes into home filesystem structures, corrupting the filesystem.
  2. Rule 2 (Commit before Home installation): The commit record must reach stable storage before any modified block is written back to its permanent home location.
    • Failure if violated: If a block is written directly to its home location before commit and power fails, home data is modified but the transaction is uncommitted. Recovery discards uncommitted transactions, leaving home structures permanently inconsistent or partially updated.
  3. Rule 3 (Home installation before Log reuse / checkpoint): All home-location writes for a transaction must be completely flushed to disk before the log header is updated to free that transaction’s journal slots.
    • Failure if violated: If log space is reclaimed while home blocks remain buffered in volatile RAM and a crash occurs, the journal record is gone and home blocks never reached disk. Updates are silently and permanently lost.

Exercise 6.3.2: Crash Cut State Enumeration and Consistency Analysis

Constructionapplication

A filesystem appends a block to an existing file by updating three distinct structures:

  • DD newly written data block.
  • BB block allocation bitmap.
  • II inode size and pointer.

Suppose a naive filesystem writes these blocks directly to home disk locations in the order I→B→DI \rightarrow B \rightarrow D without journaling.

  1. Enumerate the durable disk state (D,B,I)∈{0,1}3(D, B, I) \in \{0, 1\}^3 across all possible crash points.
  2. For each state, determine whether filesystem consistency and user data security are preserved or violated.
HintExpand

Check invariants: I implies B (no free block aliasing) and I implies D (no stale data exposure).

Worked solutionExpand

The sequence of writes is: (1) Inode II (2) Bitmap BB (3) Data DD

  • Cut 0 (Crash before II is written): Durable state (D,B,I)=(0,0,0)(D, B, I) = (0, 0, 0) Evaluation: Consistent. The file retains its original size; no blocks are leaked or corrupted.
  • Cut 1 (Crash after II before BB Durable state (D,B,I)=(0,0,1)(D, B, I) = (0, 0, 1) Evaluation: Critical violation. The inode claims the block, but the bitmap marks it free I∧¬BI \land \neg B A subsequent file creation will allocate the identical block, causing cross-file aliasing and corruption. Furthermore, reading the block exposes uninitialized garbage I∧¬DI \land \neg D
  • Cut 2 (Crash after BB before DD Durable state (D,B,I)=(0,1,1)(D, B, I) = (0, 1, 1) Evaluation: Security violation. The block is marked allocated in the bitmap and mapped in the inode, but data write DD never reached disk. Reading the block exposes stale disk contents left behind by prior deleted files.
  • Cut 3 (Crash after DD Durable state (D,B,I)=(1,1,1)(D, B, I) = (1, 1, 1) Evaluation: Consistent. All metadata and data updates completed successfully.

Exercise 6.3.3: Proving Idempotence in Physical Redo Journaling

Proofsynthesis

Let RR denote a physical redo recovery procedure that reads a valid committed log transaction containing blocks {(b1,data1),…,(bk,datak)}\{(b_1, \text{data}_1), \dots, (b_k, \text{data}_k)\} and writes each datai\text{data}_i into disk block bib_i

  1. Prove that R∘R=RR \circ R = R (idempotence).
  2. Explain why a logical log record of the form “increment link count of inode 12” is NOT idempotent, and show how a crash during recovery causes catastrophic corruption under logical logging.
HintExpand

Physical logging writes absolute block contents; logical logging applies relative operations.

Worked solutionExpand
  1. Proof of physical redo idempotence: Let SS denote the disk state. Physical redo logging defines the state transition: R(S)[bi]=dataifor all i∈{1,…,k}.R(S)[b_i] = \text{data}_i \quad \text{for all } i \in \{1, \dots, k\}. Applying the recovery procedure a second time R(R(S))R(R(S)) (R∘R)(S)[bi]=datai=R(S)[bi].(R \circ R)(S)[b_i] = \text{data}_i = R(S)[b_i]. For all other blocks b∉{b1,…,bk}b \notin \{b_1, \dots, b_k\} RR does not alter S[b]S[b] Because setting fixed byte contents is an idempotent assignment x←cx \leftarrow c executing recovery nn times produces the identical disk state as executing it once: Rn=Rfor all n≥1.R^n = R \quad \text{for all } n \ge 1.
  2. Failure of logical logging without version numbers: If the log records a relative transition link_count(12)←link_count(12)+1\text{link\_count}(12) \leftarrow \text{link\_count}(12) + 1
    • Recovery starts: executes link increment, writing link_count(12)=2\text{link\_count}(12) = 2
    • Power fails before recovery completes the transaction checkpoint.
    • Upon reboot, recovery starts again from the beginning of the log. It executes the link increment again, producing link_count(12)=3\text{link\_count}(12) = 3
    • The file now has a phantom link count, preventing it from ever being deallocated when unlinked and corrupting filesystem reference integrity.

Exercise 6.3.4: Contrasting ext4 Journal, Ordered, and Writeback Data Modes

Descriptionapplication

Contrast the write ordering and durability guarantees provided by the three ext4 JBD2 journaling modes: data=journal, data=ordered, and data=writeback. Explain why data=ordered represents the default industry choice.

HintExpand

Consider performance cost of writing data twice versus stale data disclosure risks.

Worked solutionExpand
  • data=journal: Both file payload data and filesystem metadata are written to the JBD2 journal before being flushed to home locations.
    • Guarantee: Full crash atomicity for data and metadata. No stale data exposure; data modifications never roll back if metadata commits.
    • Drawback: Severe performance penalty (every byte of file data is written to disk twice: once to the log, then to home).
  • data=ordered (Default): Only metadata is written to the journal. However, the kernel enforces a strict write-ordering barrier: dirty file data blocks must be flushed to their permanent home locations before the corresponding metadata transaction commit record is written to the journal.
    • Guarantee: Prevents stale data leakage. If the system crashes, recovery never replays an inode pointing to unwritten blocks. File data is written only once, providing excellent performance while preserving data integrity.
  • data=writeback: Only metadata is journaled. Data blocks are written back asynchronously whenever the OS page cache flushes, with no ordering dependency with respect to the metadata commit record.
    • Guarantee: Highest throughput, but vulnerable to data disclosure. A crash after metadata commit but before data flush leaves inodes pointing to unwritten blocks containing previous file data.

Exercise 6.3.5: Log Reservation Sizing and Concurrency Control

Constructiontransfer

An xv6 filesystem log has a fixed capacity of L=30L = 30 disk blocks. Each system call must reserve its maximum worst-case block consumption MopM_{\text{op}} in begin_op() before modifying any buffers.

  1. If a file append can touch at most 10 unique blocks (bitmap, indirect block, data block, inode, etc.), compute the maximum number of concurrent operations that begin_op() can safely admit.
  2. Explain why admitting a 4th operation when the first 3 operations have currently dirtied only 2 blocks each would risk deadlock.
HintExpand

A thread holding an active transaction cannot abort or surrender partial work on log overflow.

Worked solutionExpand
  1. Admissible operations: To guarantee that the log never overflows even if every admitted operation simultaneously consumes its worst-case reservation: Nmax=⌊LMop⌋=⌊3010⌋=3 operations.N_{\text{max}} = \left\lfloor \frac{L}{M_{\text{op}}} \right\rfloor = \left\lfloor \frac{30}{10} \right\rfloor = 3\text{ operations}.
  2. Deadlock hazard of optimistic admission: Suppose the kernel optimistically admits a 4th operation because the first 3 operations have currently modified only 3×2=63 \times 2 = 6 unique blocks:
    • All 4 operations continue executing concurrently.
    • Workload conditions demand that each of the 4 operations now allocates additional blocks, requiring their full 10 blocks: total demand = 4×10=404 \times 10 = 40 blocks.
    • The log fills completely to 30 blocks.
    • All 4 operations stall waiting for additional log space to become free in log_write().
    • However, in xv6, a log transaction cannot commit until all active operations call end_op().
    • None of the 4 operations can finish without more log space, and the log cannot commit and free space until the operations finish. The system enters an unrecoverable deadlock. Conservative reservation strictly prevents this state.

References & Further Reading