Copy-on-Write and Block Shadowing Instead of a Log

A journal achieves atomicity by recording intent before acting on it, so that an interrupted action can be completed from the record. Copy-on-write achieves the same end by refusing to act destructively in the first place. A block that is reachable from the current filesystem root is never overwritten. Any change produces new blocks, and those new blocks are linked into a new tree whose root replaces the old root in one write. Until that final write lands, the old tree is intact and the new blocks are unreachable garbage; after it lands, the new tree is intact and the old blocks become garbage. There is no intermediate state in which the filesystem’s structures disagree, because there is no intermediate state at all: the state is either the old tree or the new one.

This is a stronger property than journaling provides, and it costs more to produce. Understanding where the cost falls and why it cannot be avoided is most of understanding copy-on-write filesystems.

What shadowing means at the block level

Take a file with one data block and an inode that points to it, and a request to overwrite that block. An in-place filesystem writes the new bytes to the same physical block and is done. A copy-on-write filesystem allocates a fresh block, writes the new bytes there, and then must update the pointer that names the old block. The pointer lives in the inode, and the inode is reachable from the root, so the inode cannot be modified in place either. A fresh inode block is allocated, its contents are copied from the old inode with the block pointer changed, and the directory entry that names the inode must now be updated. That means a fresh directory block, and a fresh parent, and so on up to the root.

For a file in a filesystem organized as a tree of blocks with fanout B and height h, a single overwrite of one data block rewrites h + 1 blocks: the data block, one block per level, and the root. With 16 KiB nodes and keys of a few dozen bytes each, B lands in the low hundreds, so a tree holding a billion blocks has height 4 or 5. A single overwrite therefore writes about five blocks for every one block of data changed, and the cost is not proportional to the size of the change: modifying one byte in a 4 KiB block still rewrites that whole block. Counted in bytes the ratio is higher whenever metadata nodes are larger than data blocks, since each node is rewritten at its full size whatever part of it changed.

Sequential writes amortize this because consecutive data blocks can share ancestors: writing a whole run of blocks updates the data blocks once each and the tree once for the entire run, so the overhead per byte falls toward the height divided by the run length. Random overwrites of single blocks pay the full cost every time, which is the opposite of the in-place filesystem’s profile, where a random single-block overwrite is exactly one block write. This inversion is the central performance fact about copy-on-write: it is excellent for streaming writes and snapshots, and poor for random overwrites of live data.

Publishing the new tree

The atomic step is the root pointer update. Every copy-on-write filesystem has a location where the current root is named: a fixed offset, a well-known block, or a small ring of them. Writing that one block, or one sector of it, replaces the entire tree in one atomic act, provided the write itself is atomic.

The requirement on the write is that it either lands completely or not at all, because a root pointer that is half-old and half-new names neither tree. A single sector is the usual granularity assumed atomic, which is why the root pointer and its checksum are packed into one sector rather than spread across a block. On devices where a sector write is not atomic, and some are not, the design needs either a double-buffered root with a generation counter and a checksum, or an indirection through a ring of root blocks where the newest valid one wins. ZFS uses an array of labelled uberblocks at multiple offsets, each with a transaction group number and a checksum, so that at least one survives any single failure; btrfs keeps a superblock mirror set at fixed offsets with a generation number and checksums. In both cases, recovery is: read all candidate roots, verify checksums, pick the one with the highest generation, and that is the filesystem.

No replay is needed. The new tree was complete before the root write was issued; the old tree is complete and untouched. If the root write never lands, the filesystem is exactly as it was. If it lands, the filesystem is exactly the new tree. There is no partial state to reconstruct, and this is why copy-on-write filesystems can mount a dirty volume without a journal replay pass.

Freeing the old tree is the hard part

The superseded blocks must eventually be freed, and freeing them is where the elegant atomicity runs into the real world. The old tree cannot be freed before the root write lands, because until then the old tree is still the live filesystem. After the root write lands, the old tree’s blocks are unreachable and can be reclaimed, but only if the filesystem knows they are unreachable, and knowing that requires either reference counts or a traversal.

Reference counting is the direct approach: every block carries a count of how many pointers name it, and the old tree’s blocks are freed by walking down from the old root, decrementing each count, and freeing the blocks whose count reaches zero. This walk is proportional to the size of the old tree, which for a single-block overwrite is the height of the tree, small. But for a large deletion or a snapshot removal it is proportional to everything the old tree owned, which is what makes snapshot deletion expensive.

The alternative is a mark-and-sweep or space-map approach: maintain a bitmap or extent tree of allocated blocks, and periodically compute which allocated blocks are reachable from any live root, freeing the rest. This turns the per-operation cost into a periodic batch, at the price of needing to hold blocks that were freed but not yet reclaimed. The btrfs extent tree records the reference count of each extent directly, so freeing is per-operation but requires the count updates themselves to be transactional, and those updates are themselves copy-on-write, so freeing a block modifies tree nodes, which allocate blocks, which may need freeing. The recursion is bounded but it is the reason freeing is the most intricate part of a copy-on-write implementation.

The transaction group and the ordering inside it

Between two root publishes, a copy-on-write filesystem accumulates many changes in memory. The set of changes that will be made durable together is the transaction group. Within the group, new blocks are written to their allocated locations as they are created, but nothing is reachable from the live root until the group commits. The commit sequence is ordered:

1. Write all new data and metadata blocks, and the new tree nodes that link them.
2. Write any auxiliary structures the new tree depends on, such as the free-space tree’s updated nodes and the space accounting for the new allocations.
3. Issue a flush so that all of the above are durable.
4. Write the new root, with its generation number and checksum.

A crash before step 3 leaves the old root valid and the new blocks unreferenced, leaked until a scrubber or the next mount’s free-space rebuild finds them. A crash between step 3 and step 4 has the same outcome. A crash during step 4 either leaves the old root or the new one, depending on whether the sector write was atomic. The cost of this discipline is that the root write must wait for the flush, so a transaction group commits at the rate the device can flush, and batching is the only way to amortize it.

The free-space bookkeeping deserves attention because it breaks the recursion. If allocating a block requires updating the free-space tree, and that update requires allocating a block, the filesystem would never make progress. Implementations solve this by reserving space at transaction start, by keeping the free-space structures in a form that can be updated without allocation (a log-structured space map appended to a reserved region), or by deferring free-space updates to a separate pass that runs at commit time with pre-reserved blocks. ZFS’s space map and btrfs’s delayed refs and pinned extent handling are two different resolutions of the same problem.

What copy-on-write does not fix

The absence of replay does not mean the absence of recovery. A copy-on-write filesystem can still be inconsistent if a block it believes is written is not, if the root write is torn on a device that does not honour sector atomicity, or if the checksum on a root is computed over data that was itself corrupted. Checksums on every block, including the root, are what make the design work on hardware that lies; without them the generation counter alone is not enough, because a root with a plausible generation but a corrupted tree behind it will be selected and the filesystem will fail to mount.

The other limit is space. Because old blocks cannot be freed until the new root is durable, and because a snapshot pins every block reachable from its root, a copy-on-write filesystem under a snapshot-heavy workload can consume space much faster than the logical data it holds. The snapshot and reference count mechanics are the next layer of this problem. The design also interacts badly with in-place update assumptions in the rest of the system: a database that overwrites the same pages repeatedly, or a swap file, or a preallocated virtual machine image with random writes, all produce the worst case for shadowing, which is why those filesystems offer ways to opt out of copy-on-write for specific files and why the ordered-update alternatives remain relevant for workloads that cannot pay the amplification.