Shadow Paging and Copy-on-Write Trees

In-place update has a structural problem that no amount of careful ordering fixes: the moment the write begins, the only copy of the old data is being overwritten. A crash during that write leaves a mixture, and a crash after it leaves no way back. Shadow paging avoids the problem by never overwriting. A modified block is written to a fresh location, and the pointer that names it is updated only after the new copy is durable. The old copy stays where it was, untouched and still reachable through the old pointer, until something decides it is no longer needed.

Two copies exist for the duration of an update

The mechanism is easiest to see in a flat page table. A file has an array of block pointers, and block 7 currently points to physical block 100. An update modifies block 7’s contents. Instead of writing to physical block 100, the system writes the new contents to physical block 250, flushes it, and then writes the pointer array with entry 7 set to 250. The pointer array itself is a block, so it cannot be updated in place either; it too moves to a new location, and the pointer that names it, in the inode or in the root structure, is updated.

The recursion terminates at a single root: one block, one sector, one atomic write. That is the whole trick. A tree of any depth becomes an atomic update because the only write whose atomicity matters is the last one, and the last one is small enough that the media can make it atomic.

/* Write data to a fresh block and return its number; the old block stays
 * allocated and still reachable through the pointer that named it. */
static uint64_t write_cow(uint64_t old, const void *data, size_t len)
{
    uint64_t fresh = alloc_block();      /* never reuses old */
    write_block(fresh, data, len);
    flush_block(fresh);                  /* durable before any pointer names it */
    return fresh;                        /* the caller rewires its parent */
}

The flush before the pointer write is not optional. Without it, the pointer can reach media while the block it names is still in the device cache; a crash then leaves a pointer to a block that holds stale data or nothing at all. The failure is silent because the pointer is valid and the block is allocated; only the contents are wrong, and only a checksum on the block would detect it.

The pointer tree is the atomicity unit

The reason the technique is called shadow paging rather than copy-on-write is historical: the new copy is the “shadow” of the old, and the pointer tree is what makes the pair meaningful. Every level of the tree amplifies the cost of a small update by one block, and every level also removes one level of risk. A tree of depth d turns one logical update into d block writes, and turns an arbitrary multi-block update into a single atomic sector write at the root.

The cost is therefore proportional to depth, not to the size of the change. Modifying one byte in a 1 TiB file with a four-level tree writes four blocks of 4 KiB, which is 16 KiB, four orders of magnitude more than the payload. Modifying a thousand bytes spread across a thousand blocks writes a thousand leaves plus their interior nodes, which is far more than the payload but amortizes the interior cost across the leaves. The amplification is worst exactly when the update is smallest, which is why copy-on-write filesystems perform well on large sequential writes and poorly on metadata-heavy small writes.

The alternative is to update in place with a journal, which writes each changed block once plus a log record. For a small update, the journal writes the page to the log and later to its home location, so two writes and one barrier, versus four writes and one barrier for the copy-on-write path. The journal wins on write amplification and loses on the atomicity of the whole tree: after a crash, the journal’s replay must be run before the tree can be trusted, whereas the copy-on-write tree is always loadable as it stands, provided the root is intact.

Space is not reclaimed by the update

The old blocks are still allocated after the update, and they are still reachable from the old root. That is what makes snapshots possible: the old root can be kept as a snapshot, and the blocks it references remain valid indefinitely. It is also what makes deletion expensive. When a snapshot is removed, every block that was referenced only by that snapshot becomes free, and finding them requires either a reference count per block or a traversal that compares the snapshot’s tree against the live tree.

Reference counting is the usual answer, and it has a cost that scales with the number of snapshots. Each block carries a count; a copy-on-write update decrements the old block’s count and sets the new block’s to one; a snapshot increments every block it references. Creating a snapshot of a tree with a million blocks requires a million increments, which is a full traversal and a million writes unless the counts are stored elsewhere. That is why some systems keep per-snapshot block lists and compute sharing at delete time, trading a slow delete for a fast create, and why deleting a snapshot of a large dataset can take minutes while creating it took milliseconds.

The root must be a single atomic write

Everything above depends on the root being replaceable atomically. If the root is a single 512-byte sector and the device programs sectors atomically, a write of the root either happens or does not. If the root is larger, or if the device can tear a sector, the root needs redundancy: two slots with sequence numbers and checksums, or a copy in a fixed location that is never overwritten, or a superblock ring of several slots where the newest valid one wins.

The sequence number is what makes the choice well defined. On recovery, both slots are read, both checksums verified, and the one with the higher sequence number and a valid checksum is taken. If the higher one is torn, the lower one is used, and the update that was in progress is lost. That loss is bounded: the update had not been published, so no reader ever saw it, and the only consequence is that the work must be redone.

A subtlety is that the sequence number must itself be covered by the checksum and must not be reused. If the sequence wraps, an old slot can appear newer than a new one. A 64-bit counter at one update per microsecond takes centuries to wrap, which is why 64 bits is the usual choice and why 32 bits is a defect that shows up only on systems that update constantly for years.

Interaction with the cache and the device

The flush-before-pointer rule is the same rule described in Cache Flushes and FUA, applied at every level of the tree. A tree of depth four needs four flushes per update if each level’s pointer must be durable before the next, which is why implementations batch: they build the whole new path in memory, issue the block writes, issue one flush covering all of them, and then issue the root write. The interior pointers do not need to be durable before their parents if all of them are flushed together before the root.

That batching is only valid if the interior writes cannot be reordered relative to each other in a way that matters. Since every interior block is new and the pointers to it are written after the flush, the relative order of interior writes is irrelevant; only the root’s position in the sequence matters. This is a real simplification, and it is why copy-on-write trees need fewer barriers per update than a naive reading of the recursion suggests.

The device’s own cache complicates the space accounting. A block that has been freed but whose free is not yet durable may be reallocated after a crash, and a block that was allocated but whose allocation record is not durable may be lost. The allocator’s own metadata therefore needs the same treatment as the tree: either it is copy-on-write too, or it is journaled, or it is rebuilt by scanning at mount time. Rebuilding by scanning is the simplest and the slowest, and it is why a filesystem that loses its free-space map can take a long time to mount.

What the technique cannot do

Shadow paging gives atomicity for a single tree, not across trees. An update that touches two independent trees, a file’s data and the directory that names it, requires two root writes, and there is a window in which one has landed and the other has not. That window is what the rename protocol in What fsync Actually Waits For closes for the specific case of publishing a name, and what a transaction log closes in general.

It also does not give durability by itself. A new block written to a fresh location is durable only after a flush; a root written after it is durable only after its own flush. A system that omits the flushes has the atomicity of the pointer update but not the persistence of what it points to, and the two are easy to conflate because the code path looks the same. The final article in this cluster, Verifying Crash Consistency with Fault Injection, is largely about the fact that this confusion is invisible without a test that cuts power at the wrong moment.