Path Copying in a Copy-on-Write B-Tree

The general case of shadowing described earlier is simple to state and awkward to implement, because a filesystem’s metadata tree is not a binary tree whose nodes can be copied one at a time. It is a high-fanout B-tree, nodes are sized to the filesystem’s block size, and a single insertion can cause a node to split, which propagates a structural change to the parent, which can split in turn. Copying a path is easy when the path’s shape is fixed; it becomes intricate when the operation that motivated the copy also changes the shape.

The mechanics are worth working through at the node level, because they determine both the write amplification and the concurrency model of every copy-on-write filesystem built on a B-tree: btrfs, ZFS’s ZAP and directory structures, and the newer log-structured trees all share this skeleton.

A node, its keys, and its block pointer

A B-tree node in a filesystem holds a header and an array of items. The header carries a checksum, a generation or transaction number, a level (zero for leaves), a count of items, and the block address of the node’s owner or parent for back-reference. Each item in an internal node is a separator key plus a child block address; each item in a leaf is a key plus a payload, or a key plus an extent pointer.

The key is a tuple, not a scalar. In btrfs it is (objectid, type, offset), and the ordering is lexicographic over the three fields, which lets one tree hold several namespaces, such as inode numbers, directory entries, and extent records, without a separate tree per namespace. The ordering is the structure’s contract: a search at any level picks the last separator key less than or equal to the target, and descends. Changing the tuple layout changes every comparison in the tree, which is why it is fixed in the on-disk format rather than chosen per mount.

Because nodes are addressed by block number and blocks are never modified in place, a parent’s pointer to a child is the only thing that makes the child reachable. This is what makes path copying possible and what makes the free-space accounting hard: a node’s reachability is not recorded anywhere except the pointer that names it, so freeing a node requires knowing that no live root references it, which in turn requires the reference counts discussed elsewhere.

One insert, one path

Consider inserting a directory entry. The key is derived from the parent inode number, the entry’s name hash, and the name. The search descends from the root, reading one node per level, and lands on a leaf. If the leaf has room, the new item is inserted in key order and the work is done, except that the leaf cannot be modified, so a new leaf block is allocated and filled with the old leaf’s items plus the new one, and the parent’s pointer is updated. That update is itself a modification of the parent, so the parent is copied, and so on to the root.

The pattern is a bottom-up rewrite: the change is applied at the leaf, then each ancestor is rewritten with exactly one changed child pointer. The blocks that were rewritten form a path, and the number of blocks written is the height of the tree plus the new item. For a tree of height 4, a single small insert costs five block writes, of which four are near-copies of existing blocks.

This is where a copy-on-write B-tree differs from a persistent (functional) tree in the usual sense: the old nodes are not garbage-collected by a runtime. They remain on disk, referenced by the old root, until the transaction commits and the old root is retired. Between the leaf write and the root write, both trees exist simultaneously and the space accounting must reflect that both are allocated.

When the leaf is full

The interesting case is a leaf with no room. Splitting is required: the leaf’s items plus the new one are divided into two leaves, and a new separator key must be inserted into the parent. That separator insertion is itself an insert into an internal node, which may also be full, so the split propagates upward until it either finds a parent with room or reaches the root.

If the root splits, the tree grows by one level: a new root is allocated with two children, and the height increases. A tree that grows from height 4 to 5 adds one block to every path, so each subsequent operation rewrites six blocks instead of five; the increase is permanent, which is why implementations prefer a large branching factor and accept the occasional deep tree rather than balancing aggressively. Merging on deletion is optional in most filesystems, because underfull nodes cost space but not correctness, and merging requires the same upward propagation with an additional risk of touching a sibling that is concurrently being modified.

A split has a subtle consequence for path copying: the number of new blocks written is no longer just the height. A split at the leaf writes two new leaves, then rewrites the parent with a new separator and a new child pointer, and so on. If the separator travels up k levels before it reaches a parent with room, the cost is 2 + k new blocks; every ancestor along that path that also has to split adds one more block, and the new separator must be chosen so that the parent’s ordering remains valid. The choice of split point matters for future behaviour: splitting a leaf in half leaves both halves half-full and likely to split again soon, while an asymmetric split that leaves one node nearly full reduces future splits at the cost of a longer search path. Filesystems usually split at the midpoint and rely on the high branching factor to keep the height small.

/* Copy one leaf, insert the item, and return the new block number.
 * The old leaf is left untouched: it may still be reachable from a snapshot. */
static int cow_insert_leaf(struct tree *t, struct node *old, const struct item *it,
                           uint64_t *new_addr, struct split *sp)
{
    struct node *n = alloc_node(t, old->level);
    if (!n)
        return -ENOSPC;

    /* Copy the items, leaving a gap at the insertion point. */
    int pos = find_slot(old, it->key);
    memcpy(n->items, old->items, pos * sizeof(struct item));
    n->items[pos] = *it;
    memcpy(&n->items[pos + 1], &old->items[pos],
           (old->nritems - pos) * sizeof(struct item));
    n->nritems = old->nritems + 1;

    if (n->nritems <= t->max_items) {
        sp->kind = NO_SPLIT;
        *new_addr = write_node(t, n);      /* checksum and generation are stamped here */
        return 0;
    }

    /* Full: divide in half and hand the middle key up as the new separator. */
    int mid = n->nritems / 2;
    sp->kind = SPLIT;
    sp->sep = n->items[mid].key;
    sp->right = alloc_node(t, old->level);
    sp->right->nritems = n->nritems - mid - 1;
    memcpy(sp->right->items, &n->items[mid + 1],
           sp->right->nritems * sizeof(struct item));
    n->nritems = mid;
    *new_addr = write_node(t, n);
    sp->right_addr = write_node(t, sp->right);
    return 0;
}

The caller then walks up the path it descended, rewriting each ancestor with the returned address and, if a split was reported, inserting the separator. Each level’s rewrite is the same operation with a different payload, so the loop is uniform: descend once recording the path, then ascend rewriting it.

Why the path must be recorded before descending

The descend-then-ascend pattern requires the path to be known before any block is modified, which means the search phase must not allocate. A search that reaches a leaf and finds no room cannot simply backtrack to find the parent, because the parent’s block address is in the path and, if the search discarded it, the ascend has nothing to work from. Implementations record the path in a small stack, one entry per level, holding the node’s address and the slot index descended through. The stack depth is the tree height, typically under eight entries, so it costs nothing to keep on the call stack.

A second constraint follows: the path must be validated before use. If another thread modified an ancestor between the descent and the ascend, the recorded pointer may no longer name the node that should receive the separator. This is why copy-on-write filesystems either serialize writers per tree with a lock, or use a transaction-scoped snapshot where every writer sees a consistent view and conflicts are detected at commit. The read-copy-update style of concurrency that works for in-memory trees does not transfer directly, because the durable root cannot be swapped atomically without a flush.

What the path-copying cost implies for layout

Because every modification rewrites a path, the cost of an operation is dominated by the height, and the height is determined by the fanout, which is determined by the node size relative to the key and pointer sizes. Height grows only logarithmically in the item count but shrinks only logarithmically in the fanout, so enlarging a node buys less than the raw ratio suggests. Going from a 4 KiB node to a 16 KiB node quadruples the fanout, which divides the height by only log(4B)/log(B); for a fanout in the hundreds that is a reduction of roughly a fifth, not a halving, while the number of bytes rewritten per node copy is quadrupled. For a small modification the bytes written are height * node_size; for a large sequential write the tree is rewritten once regardless of node size, so the larger node amortizes better. This is why copy-on-write filesystems tend to use larger metadata nodes than in-place filesystems, and why the node size is a tunable with a real effect on both small-write latency and streaming throughput.

The same arithmetic explains the design’s interaction with snapshots. A snapshot is a copy of the root pointer, which costs one block. Every subsequent write to either tree copies the path from the root down, so the two trees diverge from the root and share everything below the divergence point. The sharing is what makes snapshots cheap, and the reference counts that track it are what make freeing correct. The transaction commit that publishes the new root is the point at which the old path becomes garbage, and the delay between the two is the source of the space amplification that snapshot-heavy workloads experience.