Part 5 of 7 · 6 min read
Copy-on-write trees
Think of a family tree drawn on paper, which you must change without damaging the old copy. You copy only the branch that leads to the changed name, and glue it to the rest. Both trees then exist, and they share all the other branches. The analogy stops in one place: paper copies are separate, while two versions in a file system share the blocks that have not changed.
In plain words: Copy-on-write (COW) keeps the file system as a tree of blocks with one root. A write never changes an existing block. It writes the new data block, then copies every pointer block on the path up to the root, with the new pointer in each, and finally writes a new root. The change becomes visible when the pointer to the root is switched, which is a single small write. A crash before that leaves the old tree fully intact, so there is no inconsistent state and no journal is needed. The old root and the blocks reachable from it are a free snapshot of the earlier version.
A worked example. The program below builds a tree of fanout 4: one root, 4 blocks, 16 blocks and 64 data blocks, which makes 1 + 4 + 16 + 64 = 85 blocks. It then updates one data block with copy-on-write and counts.
#include <stdio.h>
/* A copy-on-write tree: fanout 4, three levels of pointer blocks above 64 data blocks.
A block is a node id. A write never changes a block: it makes new copies up to a new root. */
#define FAN 4
#define LEVELS 3 /* levels of pointer blocks: 1 root, 4, 16 */
#define MAXB 1000
static int child[MAXB][FAN]; /* child[b][i] = block that slot i of block b points to */
static int nblocks = 0, nwrites = 0;
static int new_block(void) { nwrites++; return nblocks++; }
static int build(int level) { /* level 0 = data block, level LEVELS = root */
int b = new_block();
if (level > 0) for (int i = 0; i < FAN; i++) child[b][i] = build(level - 1);
return b;
}
/* Copy the path from the root down to the data block 'leaf' (0..63) and give it new contents. */
static int update(int root, int leaf) {
int b = new_block(), idx = leaf, span = FAN * FAN;
for (int i = 0; i < FAN; i++) child[b][i] = child[root][i]; /* share the other children */
int slot = idx / span, rest = idx % span;
int mid = child[root][slot];
int m = new_block();
for (int i = 0; i < FAN; i++) child[m][i] = child[mid][i];
int slot2 = rest / FAN, slot3 = rest % FAN;
int low = child[mid][slot2];
int l = new_block();
for (int i = 0; i < FAN; i++) child[l][i] = child[low][i];
child[l][slot3] = new_block(); /* the new data block */
child[m][slot2] = l;
child[b][slot] = m;
return b;
}
static int count(int b, int level, int *seen) { /* blocks reachable from b that are not yet seen */
int n = seen[b] ? 0 : 1; seen[b] = 1;
if (level > 0) for (int i = 0; i < FAN; i++) n += count(child[b][i], level - 1, seen);
return n;
}
int main(void) {
int root0 = build(LEVELS), built = nwrites;
nwrites = 0;
int root1 = update(root0, 37);
int w = nwrites, seen[MAXB] = {0};
int v0 = count(root0, LEVELS, seen), extra = count(root1, LEVELS, seen);
printf("version 0 has %d blocks (written once: %d)\n", v0, built);
printf("updating one data block wrote %d new blocks (data + 3 pointer blocks)\n", w);
printf("version 1 shares %d blocks with version 0 and adds %d\n", v0 - extra, extra);
return 0;
}
Output:
version 0 has 85 blocks (written once: 85)
updating one data block wrote 4 new blocks (data + 3 pointer blocks)
version 1 shares 81 blocks with version 0 and adds 4
One changed data block cost 4 writes: the data block and the 3 pointer blocks on its path. Both versions are complete, and 81 of their blocks are shared. With a fanout of 256 and the same three levels of pointer blocks, the tree would hold 256^3 = 16,777,216 data blocks, and an update would still cost only 4 block writes. The cost grows with the depth of the tree, not with the size of the file system.
The key lines. A snapshot costs almost nothing to make, since it is just a second root that is kept. It costs space only as the live tree and the snapshot diverge, which is 4 blocks for each changed data block in the model. When a snapshot is deleted, the blocks that only it used become free.
Copy-on-write
Copy-on-write is the technique of changing data by writing a modified copy to a new location, and then switching a pointer to the copy, instead of overwriting the original. In a copy-on-write tree, the change is copied up the path to the root, so the old and the new versions share all the unchanged blocks.
Example: the program writes 4 new blocks to update one of 64 data blocks, and keeps the old tree as a snapshot.
Read it as
The cost of a COW update is the height of the tree, plus one. The cost of a snapshot is the number of blocks that change, not the size of the file system.
Check yourself: 1. How many blocks does the model write to change one data block? 2. Why is no journal needed in a copy-on-write file system? 3. Why is a snapshot cheap to make and cheap to keep while little changes?