Write Ordering and the Crash Window Between Metadata Updates

Appending one block to a file touches three separate on-disk structures. The free-space bitmap gains a set bit for the newly allocated block. The data block itself receives the bytes. The inode gains a new block pointer and a larger size field. An implementation that performs those three writes in exactly that sequence, in program order, has done everything a programmer can reasonably be asked to do. Yet after a power failure at the wrong instant the resulting filesystem can be worse than one that lost the append entirely: the inode can point at a block the allocator still believes is free, so the next allocation hands the same block to another file and two inodes share storage.

The gap between “wrote things in the right order” and “the disk received them in that order” is the subject of every crash-consistency mechanism in a filesystem. Journaling, copy-on-write, and ordered metadata writes are three different answers to the same question: how does a system that cannot control the timing of a crash leave its metadata in a state that some recovery procedure can repair, or that needs no repair at all.

The three writes and what each one can break

The append above is small enough to work through case by case. Each subset of the three writes that might reach stable storage, and each field-level partial write inside a single block, produces its own combination of loss and damage.

If only the data block reaches the disk, nothing observable changes: the bitmap still marks the block free, the inode has no pointer to it, and the bytes are garbage in an unallocated region. The filesystem is consistent, and the append is simply lost.

If the bitmap reaches the disk but the inode does not, the block is marked allocated with no owner. Space leaks. The filesystem is consistent in the sense that no invariant is violated, since every allocated block either has an owner or is a leak, but the leak accumulates and only a checker that scans for unreferenced allocated blocks can reclaim it. A block bitmap set for a block that no inode references is the classic orphaned-block state that fsck resolves.

If the inode reaches the disk but the bitmap does not, the inode points to a block that the allocator considers free. Nothing in the metadata says this is wrong; the inode and the bitmap each look plausible in isolation. The corruption only manifests later, when the block is allocated to a second file and the two files’ contents interleave. This is the dangerous case, because it is silent and because the damage is deferred.

If the inode reaches the disk with the new block pointer but a stale size field, the file appears shorter than it is. The block is allocated and referenced, so no structural check complains, but it lies beyond the recorded end of file: reads at that offset return nothing, and the appended bytes are silently invisible. Whether a later extension reuses the existing mapping or allocates a fresh block depends on how the filesystem treats a pointer past the size, so the same on-disk state can end in either a recovered append or a pinned, unreachable block.

Three writes admit eight subsets. Two leave the append cleanly lost, because no inode write reached the disk. Two leave the block allocated and unreferenced: a leak. Two leave the inode pointing at a block the allocator still considers free: the aliasing case that corrupts data later. The remaining two leave the structures consistent, differing only in whether the data block itself arrived. The state space grows combinatorially with the number of structures touched: a rename over an existing name touches a directory entry, a second directory entry, a link count in the source inode, a link count in the target inode, and possibly a directory index. Every metadata operation is a small distributed transaction over blocks that the hardware will persist independently.

Ordering is a separate guarantee from atomicity

Two properties are often conflated. Ordering says that if write A is issued before write B, then at any crash point either both are on media or A is on media and B may be missing, but never B without A. Atomicity says a group of writes either all appear or none do.

Neither property is provided by default. The block layer accepts writes and dispatches them; a device with a volatile write cache is free to destage them in any order it finds convenient, and a copyback-cached RAID controller or a flash translation layer adds further reordering. Even without a cache, a write that spans multiple sectors can be split by a power loss mid-transfer, leaving the early sectors updated and the later ones holding their previous contents. The common working assumption is that a single sector, 512 bytes on drives with 512-byte logical sectors and 4096 on 4Kn devices, is written atomically, but drives exist that violate even this, which is why storage stacks talk about torn writes and why higher layers add checksums rather than trusting the sector.

Ordering can be bought. A flush or write-barrier operation forces previously issued writes to stable media before later writes are allowed to proceed, and a force-unit-access write is a write the device must persist before reporting completion. The cost is the cost of the flush: on a rotating disk it waits for the platter to reach the right position and the cache to drain, on flash it waits for the program operation to complete. A filesystem that emits a barrier between every dependent pair of writes converts a stream of parallel writes into a chain of serialized ones, and throughput collapses toward the latency of the slowest device in the chain.

Atomicity cannot be bought with barriers at all. Barriers constrain order; they do not make five block writes into one. A filesystem that wants an indivisible multi-block update must build it out of ordering plus a recovery procedure, which is what every real mechanism does.

What the ext2 generation left to fsck

The first widely deployed UNIX filesystem designs accepted the ordering problem and pushed the consequences to a repair tool. The Berkeley Fast File System and its descendants allocated blocks, wrote inodes, and updated bitmaps with no ordering discipline beyond whatever the driver happened to enforce, on the theory that a full filesystem check at mount time would find and fix the inconsistencies. The check works from redundancy: it walks every inode, builds a reference count per block, compares that against the bitmap, and reconciles. Blocks marked free but referenced get marked allocated; blocks marked allocated but unreferenced get freed; inodes whose link counts disagree with the directory tree get moved to a lost-and-found directory.

This design is correct in the sense that it converges, and its cost is proportional to filesystem size rather than to the amount of work done before the crash. A multi-terabyte volume takes minutes to hours to check even when the only damage is one misplaced pointer, because proving the absence of damage requires reading every inode and every indirect block. It also assumes the checker can distinguish “referenced” from “should be referenced”, which it cannot for the case of an inode pointing at a block that was reallocated: the reference counts agree with each other while the data is already shared. Redundancy recovers structure, not content.

Three ways to avoid the subset problem

The mechanisms that follow in this cluster each attack the problem differently, and the differences are instructive because they trade along distinct axes.

Journaling writes the intended changes to a separate log area first, then commits the log with a single-sector marker, then applies the changes in place. A crash before the commit marker means the log is discarded and nothing happened; a crash after means the log is replayed and the changes are completed. The three-phase commit structure converts many unordered writes into one atomic unit at the cost of writing everything twice and paying a barrier per transaction.

Copy-on-write never modifies a block that is reachable from a live root. New data goes to a fresh block, the pointer to it is rewritten in a fresh parent block, and the process repeats up the tree until a new root is published. The shadowing of live blocks means the old tree remains intact and self-consistent at every instant, so there is nothing to replay; the price is write amplification proportional to tree depth and a constant background cost of freeing the superseded blocks.

Ordered metadata writes keep the in-place layout but impose a dependency graph on the writes and emit barriers so that a block is never persisted before the blocks it depends on. The dependency rules used by soft updates allow full parallelism among independent writes and no double-writing, at the cost of intricate reasoning about which orderings are safe and a recovery pass that must roll back partially completed operations.

The window is not only a power-loss problem

The crash window is usually described in terms of power failure, but the same analysis applies to any event that interrupts a sequence of writes: a kernel panic, a hypervisor pause that loses an in-flight request, a device that reports a write as complete while the data sits in a cache that later loses power, a network block device that disconnects. It also applies to process crashes at a higher level: an application that writes a file, calls rename, and expects the pair to be atomic is relying on the filesystem’s own ordering guarantees, and those guarantees are narrower than most callers assume.

Two consequences follow. First, the correctness of a filesystem’s metadata handling is a property of the whole stack, from the filesystem’s write sequence through the block layer’s barrier implementation to the device’s cache policy. A journal on a device with a volatile write cache that ignores flushes provides no guarantee at all, which is why the flush semantics of the storage stack matter as much as the log format. Second, the recovery procedure defines the real contract. A filesystem that can only guarantee “the metadata will be structurally consistent” is making a weaker promise than one that can guarantee “the last completed transaction is present”, and callers who need the stronger promise must know which one their storage provides.

The rest of this cluster follows those two threads: how the log format and its commit point work, how copy-on-write avoids the log entirely, and what the durability primitives at the bottom of the stack actually deliver.