Make a filesystem update survive interruption

Prerequisites: Files, blocks, and persistent storage.

Learning objectives

• Explain why a multi-block update can leave inconsistent state.
• Trace write-ahead logging and replay.
• Distinguish atomic visibility from durability.

A crash interrupts a sequence, not an intention

Appending data to a file can require several persistent changes: allocate a data block, write its contents, update the file’s block mapping and size, and update allocation metadata. These writes do not necessarily reach stable storage in source-code order. A crash can leave only some of them durable.

Suppose a filesystem marks a block allocated and updates the file mapping, but the new data never reaches storage. The file may point at stale content. If a block becomes referenced while the allocation bitmap still says free, a later allocation can give the same block to another file. Correctness therefore requires an ordering or recovery strategy, not merely eventual writes of all intended values.

Write a recoverable account first

A simplified redo journal records new metadata values in a log. The system first writes the transaction’s log records, then ensures they are durable, then makes a commit record durable. Only after that commitment may it safely install the recorded updates at their final locations and later reclaim the log space under the protocol.

If a crash occurs before a valid durable commit, recovery ignores the incomplete transaction. If it occurs after commitment but before all home-location writes complete, recovery reapplies the logged updates. Redo should be idempotent: writing the recorded final block image twice has the same effect as writing it once. A transaction identifier and integrity information help distinguish complete records from stale or torn content.

This is a simplified protocol. Actual storage has specific ordering, flushing, and atomicity guarantees. Journaling modes may protect only metadata or include file data, and the resulting promises differ. A log that is only in volatile memory has not yet established crash durability.

Visibility and durability are separate

An operation can appear complete to another process while its data remains in memory awaiting writeback. Conversely, a durable sequence may still need synchronization to make an application-level multi-step update appear atomic to concurrent readers. A successful buffered write is not a universal promise that the bytes survive power loss.

For application updates, a common pattern writes a replacement file, requests appropriate synchronization, then renames it into place and handles the containing directory’s durability according to the filesystem and API contract. The exact guarantees are platform dependent; rename atomicity alone is not a complete persistence proof.

To analyze a protocol, enumerate crash points after every persistence boundary. For each point, state what recovery sees and why it either restores the old state or completes a valid new state. Testing only a clean shutdown never exercises the failure model that persistence mechanisms exist to handle.

Primary reading

• Crash Consistency: FSCK and Journaling (Arpaci-Dusseau and Arpaci-Dusseau, OSTEP).

Practice problem

A redo transaction writes two log records, persists them, persists a commit record, and begins copying the two new block images to home locations. A crash occurs after only the first home write. What should recovery do? Contrast this with a crash before the commit record is durable. Explain the role of idempotent redo.

Worked solution

After the commit record is durable, recovery treats the transaction as committed and reapplies both recorded block images to their home locations. Rewriting the first block is safe because redo stores a final image rather than blindly repeating an increment or another non-idempotent operation. The second block is brought up to date, restoring a consistent committed state. If the crash occurs before a valid durable commit record, recovery must not assume the transaction completed; under this protocol it ignores the incomplete transaction, and home-location writes should not have been installed prematurely. Idempotence also matters if another crash interrupts recovery itself: replaying the same committed images again must preserve the same result rather than accumulating duplicate effects.

Check your understanding

Why must redo be idempotent?

• Recovery may repeat after a second crash.
• Every file contains only zeros.
• The journal never reaches storage.
• A commit record replaces all data permanently.

Explanation

Repeated recovery must not apply a logical effect twice.

Which statement about a successful buffered write is safest?

• It always survives immediate power loss.
• Its persistence depends on the API and storage synchronization contract.
• It atomically updates every file in the directory.
• It proves all journal records are durable.

Explanation

Visibility through memory and survival of a crash are separate properties.

Primary reading

• Crash Consistency: FSCK and Journaling: Arpaci-Dusseau and Arpaci-Dusseau, OSTEP

Open the study and save your work →