Snapshot Reference Counts and Why Deleting One Costs So Much

Creating a snapshot in a copy-on-write filesystem writes one block. The block holds a copy of the root pointer, a generation number, and a checksum; nothing else changes. Every block reachable from the snapshotted root stays exactly where it is, and both the live tree and the snapshot now point at it. The operation is O(1) in the size of the data, which is why snapshots are taken freely and why they accumulate unnoticed.

Deleting a snapshot is not symmetric. The same tree that cost one block to create can take minutes to destroy, because destruction requires determining which blocks the snapshot was the last holder of and freeing exactly those. The asymmetry is not an implementation oversight; it follows from the direction of the information. Creation adds a reference to everything; deletion must subtract one from everything and free the remainder. A filesystem that does not maintain per-block counts must discover the remainder by traversal.

What sharing looks like after a write

A snapshot taken at generation 100 and a live tree that has advanced to generation 140 share every block that neither has modified since the fork. Each modification to the live tree rewrites a path from the leaf to the root, so the divergence grows from the root downward: the two trees have different roots, different upper nodes, and, below the deepest node the modification touched, identical pointers into the same blocks.

The accounting structure records, for each allocated extent, how many references point at it. After the snapshot, every extent that was previously held once is held twice. Performing that increment over every block at snapshot time would make the operation O(size), so implementations avoid it. One strategy records the snapshot as a reference to the root and derives sharing later, when a block is first about to be overwritten: a block whose reference count is above one is written to a new location rather than updated. Another updates the counts eagerly, in the same transaction that creates the snapshot, which costs a walk of the tree nodes but keeps the invariant exact at all times.

Whichever strategy is used, the invariant is the same: an extent is freed only when its count reaches zero. The count must be exact, because a count that is too low frees data the snapshot still needs and a count that is too high leaks space permanently. There is no recovery from a wrong count short of a full scan, which is why the counts are themselves checksummed and why the accounting structures are the most carefully transactional part of the design.

Why deletion is a traversal

Deleting the snapshot decrements the count of every extent reachable from the snapshot’s root and frees the extents whose count reaches zero. The set of extents to visit is the snapshot’s entire tree, so the cost is proportional to the number of blocks the snapshot owned, not to the amount of space actually reclaimed.

The distinction matters. If the snapshot diverged only slightly from the live tree, most of its blocks are shared and their counts stay above zero. The deletion still visits all of them to decrement. So a snapshot of a terabyte filesystem that was modified in one directory takes as long to delete as a snapshot that was modified everywhere, because the traversal is over the snapshot’s tree, not over the difference.

Implementations split this work. The parts that can be done immediately, namely the root block and the upper nodes that are exclusively owned, are freed synchronously. The bulk of the traversal is deferred to a background thread, and the snapshot enters a state in which its root is unreachable from the namespace but its blocks are still being released. Until that thread finishes, the space is not available. This is the observable behaviour that makes deleting a snapshot appear to hang or to return before the space is reclaimed, and it is why a filesystem with many deletions in flight can run out of space temporarily even though the deletions have completed.

/* Release one snapshot: walk its tree, decrement each extent, free at zero.
 * Runs in a background thread after the root is detached from the namespace. */
static void release_tree(struct fs *fs, uint64_t node_addr, int level)
{
    struct node *n = read_node(fs, node_addr);

    if (level > 0) {
        for (int i = 0; i < n->nritems; i++)
            release_tree(fs, n->items[i].child, level - 1);
    } else {
        for (int i = 0; i < n->nritems; i++) {
            struct extent_ref *r = lookup_ref(fs, &n->items[i]);
            if (--r->count == 0) {
                free_extent(fs, r->start, r->len);
                drop_ref_record(fs, r);
            }
        }
    }
    free_block(fs, node_addr);   /* the node itself is exclusively owned by this tree */
}

The recursion depth is the tree height, so the stack is not a concern; the work is dominated by the number of leaves. Note that the node blocks themselves are freed unconditionally, because a node reachable from the deleted snapshot’s root and not from any other root was exclusively owned by it. The code as written assumes that exclusivity; a real implementation checks the node’s own reference count before freeing it, because two snapshots can share an upper node if neither modified the subtree beneath it.

The deletion that is not proportional to anything small

The worst case for snapshot deletion is a snapshot that is nearly identical to the live tree. Every block is shared, so nothing is freed, but every block is visited. The best case is a snapshot taken of a tree that was subsequently rewritten entirely, so the snapshot’s blocks are exclusively owned and each visit frees something.

This inverts the intuition that deletion cost should track reclaimed space. A filesystem whose snapshots are short-lived and taken frequently, each covering a small delta, will spend its time walking shared trees and freeing almost nothing. A filesystem whose snapshots are long-lived and divergent reclaims a great deal per unit of traversal. The operational consequence is that the expensive pattern is the common one: periodic snapshots of a mostly-unchanged volume.

There is a second asymmetry, in metadata. The traversal reads every node it visits, which for a terabyte of shared data is a full pass over the metadata tree, the very cost that journaling was designed to avoid at mount time. It runs in the background, so it does not block the mount, but it consumes I/O bandwidth and page cache, and it competes with foreground work. A filesystem under snapshot churn is doing a continuous metadata scan in the background.

Space accounting and the overcommit trap

Because the free-space count that the filesystem reports excludes blocks pinned by snapshots but includes blocks that are pending release, the number is a lower bound on what is available rather than an exact figure. The relevant quantity for a writer is not “free blocks” but “blocks that can be allocated without violating a snapshot’s contents”, and those differ by everything the snapshots hold.

A copy-on-write filesystem that reports free space as total minus allocated, where allocated includes snapshot-pinned blocks, is telling the truth about what is pinned and misrepresenting what is usable, because the pinned blocks will never become free while the snapshot exists. The reverse convention, reporting total minus live-tree usage, overstates available space and leads to a volume that fills up with an ENOSPC that the caller cannot explain. Implementations pick a convention and document it; the distinction between “free” and “reclaimable” is the one that matters, and it is why snapshot retention policy is a capacity decision and not merely a convenience.

The reclaimability question interacts with the transaction group lifetime: a block freed by a committed transaction group cannot be reused until no live root references the group in which it was allocated. In a filesystem with snapshots, “live root” includes every snapshot, so a long-retained snapshot can pin transaction groups indefinitely. This is the mechanism behind the observed behaviour that space is not released after deleting files while a snapshot exists: the deletion did free the blocks in the live tree, but the snapshot still holds them.

Generation tracking instead of per-block counts

The cost of reference counting is paid on every allocation and every free, which is why some designs avoid exact counts. A filesystem can instead maintain, per transaction group, the set of blocks allocated in it, and free a group’s blocks when no live root references that group or any earlier one. The check is a comparison of generation numbers rather than a per-block count, so allocation does not update a count and deletion does not traverse. The price is granularity: a whole group is retained until every root that references it is gone, so space is released in group-sized units rather than block-sized ones, and a single long-lived snapshot can pin an entire group’s worth of unrelated blocks.

A hybrid approach carries the birth transaction group in each block and defers the free decision to a background process that compares birth groups against the oldest referenced group, with explicit reference counts used where sharing is fine-grained. The choice between counting and generation-tracking is a choice about which waste is acceptable: wasted space from group-granular retention, or wasted CPU from per-block counting.

The path-copying structure is what makes all of this possible, and it is also what makes the snapshot cheap: sharing is a consequence of never modifying a reachable block. An in-place filesystem has no shared block to point at, so the closest it can come to a snapshot is a volume-level copy underneath the filesystem, which duplicates every block whether or not it changed.