Copy-on-write, block by block

A file system can copy a 10 TiB disk as fast as a 1 GiB disk, because the copy writes almost nothing. NetApp’s WAFL file system was doing it when its designers described it in 1994, and ZFS and btrfs are built on the same idea. To see how it works, start from what a file system is made of, and add one idea at a time.

A file system is a tree of blocks§

A disk is an array of fixed-size blocks, each with a number, its address. A file system stores your files’ data in those blocks, and it stores the map of which blocks hold which file in blocks too. An inode records a file’s size, owner, and the addresses of its first blocks. For more information about inodes, see From a path to an inode. A large file needs more addresses than fit in its inode, so the inode points at indirect blocks, which hold nothing but more addresses.

Follow that chain upward and you reach one block that everything hangs from. The 1994 paper that describes WAFL puts it plainly: “A WAFL file system is best thought of as a tree of blocks.”Dave Hitz, James Lau, and Michael Malcolm, File System Design for an NFS File Server Appliance, USENIX Winter 1994 Technical Conference, section 3.3. Its root is the inode of the inode file, the file that holds every other inode. The leaves are the data blocks of every file. The file system has to find the root when it starts, so the root’s location is the one thing written at a fixed address.

Everything on this page follows from that shape. A file system whose blocks form a tree can describe its entire state with the address of one block.

Updating a tree without overwriting it§

Appending one block to a file changes several blocks at once: the new data block, the indirect block that gains its address, the inode whose size grows, and the bitmap that records the block as used. Classic UNIX file systems such as the Berkeley Fast File System keep their metadata at fixed locations and update it in place.Hitz, Lau, and Malcolm, section 3.2, compare WAFL with FFS, where “meta-data, such as inodes and bit maps, is kept in fixed locations.” If the power fails after some of those blocks reach the disk and before the rest do, the disk holds a file system that never existed. Something has to prevent or repair the damage before the file system can be trusted again. A journal, which Where fsync returns from describes, is one answer.

WAFL’s answer was different: never overwrite a block that the tree still points at. To change a data block, write the new version to an unused block. Its parent now has to point at the new address, so write a new copy of the parent too, with that one pointer changed. That parent’s parent changes for the same reason, and so on up to a new root. The final step is a single small write: move the root pointer from the old root to the new one.

The technique came from databases. The WAFL paper notes that it is “well known for databases” and cites the shadow paging in IBM’s System R.Hitz, Lau, and Malcolm, section 3.5: “See, for instance, [Astrahan76] which describes the shadow paging technique used in System R.” Ohad Rodeh, whose work on shadowed B-trees underlies btrfs, sums up the rule in two lines: the file system is “a tree of fixed-sized pages”, and you “never overwrite a page.”Ohad Rodeh, B-trees, Shadowing, and Clones, slides from the 2007 Linux Storage and File Systems Workshop, slide 4. The btrfs design notes name this work as the basis of btrfs’s copy-on-write design: see btrfs design.

The cost of a write is the depth of the tree, not its size. In a tree of fifteen blocks, a write writes four. In a real file system each block holds many pointers, so even a tree that covers a huge disk is only a few levels deep. A write still copies a handful of blocks, whether the disk holds a megabyte or a petabyte. Try it in the following figure: each block is labeled with its address, so you can see which blocks are new and which never moved.

Copying a path for every write would still be a lot of writing if the file system did it one write at a time. It doesn’t. WAFL gathers “many hundreds of NFS requests” before it writes, so busy blocks, such as indirect blocks and blocks of the inode file, “are written only once per write episode instead of once per NFS request.”Hitz, Lau, and Malcolm, section 3.4. Rodeh’s slides list the same optimization: once a page is shadowed, it doesn’t need to be shadowed again until the next checkpoint. ZFS groups writes into transaction groups and, by default, writes one out at least every 5 seconds.The zfs_txg_timeout parameter, documented in OpenZFS’s zfs(4) manual page: “Flush dirty data to disk at least every this many seconds (maximum TXG duration).” Many writes share one path copy and one root move.

Crash consistency for free§

WAFL wrote anywhere to make snapshots possible, but the design brings something else with it. Until the root pointer moves, the tree it names is the old tree, untouched, because every new block went to free space. After the root pointer moves, it names the new tree, already complete on disk. No moment exists when the disk describes a half-applied change.

There is one condition. The new blocks must reach stable storage before the root pointer that names them. ZFS writes this down in its source: before writing the uberblock, its name for the root pointer, it flushes the write cache of every disk it wrote, which “ensures that all blocks written in this txg will be committed to stable storage before any uberblock that references them.”OpenZFS module/zfs/vdev_label.c, in vdev_config_sync(). The same file explains that each device keeps “a redundant array of uberblocks”, and that ZFS picks the best one when it loads a pool. btrfs does the same with its super block: the new tree blocks are flushed first, and “once the super block has been properly written to disk, the transaction is considered complete.”From the btrfs design notes, “Copy on write logging”.

The WAFL paper calls each committed tree a consistency point, and it treats one as a snapshot that has no name. WAFL took one at least every 10 seconds. After an unclean shutdown, it “simply reverts to the most recent consistency point,” which let a server with 20 GB of data reboot in about a minute without checking the file system.Hitz, Lau, and Malcolm, section 3.5. Reverting would lose the last few seconds of requests, so WAFL also logged each NFS request to battery-backed memory and replayed the log on restart. That split is worth remembering: the tree gives you consistency, and a log of recent operations gives you durability between commits.

A snapshot is a root you keep§

After a commit, the old root and the blocks only it reached become free. Don’t free them, and you have a snapshot. The old root still names a complete tree, and it stays complete because the file system never overwrites a block that a tree reaches.

That’s how WAFL takes one: “To create a virtual copy of this tree of blocks, WAFL simply duplicates the root inode.” A new snapshot “consumes no disk space except for the Snapshot inode itself.”Hitz, Lau, and Malcolm, section 3.4. btrfs describes its snapshots the same way: once dirty data is flushed, a snapshot “is instantaneous and only creates a new tree root copy in the metadata.”From the btrfs-subvolume(8) manual page, “Performance”. In ZFS, snapshots “can be created extremely quickly, and initially consume no additional space within the pool.”From OpenZFS’s zfsconcepts(7), “Snapshots”.

Notice the condition in the btrfs quote. A snapshot captures the tree, and the tree holds only what has been written to it. Writes still in memory have to be flushed first. btrfs warns that this step “may take some time.” WAFL’s 1994 snapshot procedure is mostly about that flush, and it finished “in less than a second” under normal loads. ZFS promises that a snapshot “includes all modifications to the dataset made by system calls that have successfully completed before that point in time.”From OpenZFS’s zfs-snapshot(8).

On a local file system, every completed write is in the kernel’s own memory, so the file system can flush it before the snapshot. Storage built from several machines has a harder version of this problem. A write can be acknowledged by one machine while the tree lives on others. What a snapshot includes then depends on which writes have reached the tree, and that’s a property to test, not to assume.

Writable clones§

A snapshot is read-only. A clone is a second tree you can write to: a new root that points at the same blocks as a snapshot, and then moves on its own. In ZFS, “clones can only be created from a snapshot,” and “creating a clone is nearly instantaneous, and initially consumes no additional space.” In btrfs, snapshots are writable by default, and “they can be snapshotted again any number of times.”From zfsconcepts(7), “Clones”, and the btrfs design notes, “Snapshots and subvolumes”.

Rodeh lists what a good cloning scheme needs: clones should share as many blocks as possible, a clone should take little time to make, you should be able to clone a tree many times, and you should be able to clone a clone. A full copy fails all four.

With shadow paging, a write to either tree copies one path in that tree and leaves everything else shared. In the following figure, the checkpoint and main share a root. The branch has its own root, a copy of the original that points at the same children. Write to main or to the branch and watch which blocks stay shared.

ZFS ties a clone to the snapshot it came from: “the original snapshot cannot be destroyed as long as a clone exists.” Its promote command reverses the relationship, so the clone becomes the parent and the old file system can be destroyed. That rule exists because of the problem in the next section.

Deciding when a block is free§

In a file system with one tree, freeing is easy: when a write replaces a block, the old one is free as soon as the new root is in place. With snapshots and clones, the replaced block may still be reached by another tree. Before the file system can reuse it, it has to know whether any tree still points at it. Walking every tree to find out would take time in proportion to the whole disk. Three file systems answer the question three ways.

One bit per snapshot

WAFL keeps a block-map file with a 32-bit entry for every 4 KB block. “Bit 0 is set if the active file system references the block, bit 1 is set if the first Snapshot references the block, and so on. A block is in use if any of the bits in its block-map entry are set.”Hitz, Lau, and Malcolm, section 4.1, and figure 5, which the following figure animates.

The bitmap answers “is this block free?” with one lookup, but it moves the cost elsewhere. Taking a snapshot means copying the active bit into the new snapshot’s bit in every entry of the map. Deleting one means clearing that bit in every entry. Both are a pass over a map the size of the disk. The bits also cap the count: the paper describes keeping up to 20 snapshots online. Rodeh’s slides spell out the arithmetic: 32 bits per block allow 32 clones, and 256 clones would need 32 bytes for every block on the disk.

Reference counts

Rodeh’s design, which btrfs adopted, keeps a reference count for each block instead: the number of tree nodes that point at it. A count of zero means the block is free.Rodeh, slides 24 to 30. The btrfs design notes: “Reference counting is the basis for the snapshotting subsystems.” The trick is to update the counts lazily:

• To clone a tree, copy its root and add one to the count of each of the root’s children. Nothing deeper changes yet, however large the tree.
• To write to a block whose count is above one, shadow it as usual, subtract one from the old block’s count, and add one to the count of each of its children. The children now have one more parent.
• To delete a tree, walk down from its root. At a block whose count is above one, subtract one and stop: another tree shares everything below it. At a block whose count is one, keep walking, and free the block on the way back up.

The counts in the earlier figure, such as ×3, are the same idea, counted in full rather than lazily. Deleting a tree visits the blocks that only it owns, plus the edge where sharing begins. That’s less than the whole disk, but it’s still real work, and it grows with how far the tree has diverged. btrfs does it in the background. Deleting a subvolume removes its name at once, but “the data blocks are removed later,” and this cleaning “can take some time depending on the amount of shared blocks.”From the btrfs-subvolume(8) manual page, “Performance” and “delete”. The design notes add that the walk records its progress, so a crash partway through doesn’t lose its place.

Birth times

ZFS needs no per-block counter. Each ZFS block pointer records, beside the block’s address and a 256-bit checksum of its contents, the transaction group in which the block was born.The block pointer layout is in OpenZFS’s include/sys/spa.h: “Each block is described by its DVAs, time of birth, checksum, etc.” A transaction group number only grows, so it works as a clock, and a snapshot is a point on it.

When the live file system stops using a block, one comparison decides its fate. If the block was born after the most recent snapshot, no snapshot can reach it, so it’s freed at once. Otherwise it goes on a dead list: the blocks the previous snapshot reaches that the file system after it doesn’t.The rule is in dsl_dataset_block_kill() in OpenZFS’s module/zfs/dsl_dataset.c. Deleting a snapshot reads the dead list of the snapshot after it. Each block on that list that was born after the snapshot before it is now unreachable, and is freed. The rest are still held by that older snapshot.In dsl_destroy_snapshot_sync_impl() in OpenZFS’s module/zfs/dsl_destroy.c. The work is in proportion to the dead list, which is what changed, not to the size of the disk. Try the rule in the following figure.

Set the three designs side by side and one pattern stands out. Taking a snapshot is cheap in all of them, because it only keeps a root. Deleting one is the expensive half, because the file system has to find exactly the blocks that no other tree reaches. WAFL pays with a pass over the whole map, btrfs with a walk of the deleted tree, and ZFS with a walk of a dead list. Any storage that offers forks has to solve deletion as well, and deletion is the harder half.

Space accounting§

Once trees share blocks, “how much space does this snapshot use?” has two honest answers. ZFS reports both. A dataset’s referenced space is “the amount of data that is accessible by this dataset, which may or may not be shared with other datasets in the pool.” A snapshot’s used space is the space “referenced exclusively by this snapshot,” which deleting it would free.From OpenZFS’s zfsprops(7), “Native Properties”.

Those two numbers can be far apart. Space that two snapshots share counts in neither one’s used, so the used values don’t add up to what the snapshots hold together. Delete one snapshot and its neighbors’ used can grow, because blocks they shared become theirs alone. For a clone, ZFS leaves out the space it shares with its origin.

Two lessons carry over to any storage that forks. First, a fork costs what it changes, so a fork that rewrites its whole workspace saves nothing over a copy. Second, the space you get back by deleting a fork is its own blocks, not its size. Deleting a snapshot that every clone still reads frees nothing at all.

What copy-on-write costs§

The design isn’t free, and its costs follow from the same tree. Every write rewrites a path, which batching amortizes but doesn’t remove. Snapshots hold on to blocks that the live file system has replaced: the WAFL paper reports that keeping snapshots for a week consumed 10 to 20 percent of disk space in typical environments of the time. And deletion is deferred work, done in the background, so space comes back later than the command that freed it.

A worked example: Archil’s branches§

Archil-managed disks, the default, use the same structure across a network. A disk’s state in object storage is a small root object that names immutable, content-addressed objects, which in turn name blocks of data. A flush writes new objects and then a new root, so it’s atomic for the same reason a WAFL consistency point is. A branch starts a new disk that reads its parent’s objects and cached chunks without copying them, and writes its own from then on. We bill each branch for the data it owns, so a shared chunk isn’t charged once per descendant. Disks synced to your own bucket keep ordinary objects at their paths instead, so this section doesn’t describe them.

So a checkpoint or a branch takes the same time at any disk size. Our documentation gives median times of 13 ms for a checkpoint and 33 ms for a branch.From Branches and checkpoints, Limits, and Metering in Archil’s documentation. Deletion, the hard half, is what we haven’t shipped: today you can’t delete an individual branch or checkpoint. Branches also don’t merge back into their parent. A merge has to compare two trees, so its cost grows with the changes on each side.

For how agents use forks to run several attempts from one starting state, see Storage for agents.