3 ms·

Copy on write filesystems describe changes as a structural diff, effectively.

klodolph 6y ago
That's not really true. The copy-on-write filesystems just allow multiple files to reference the same blocks, and only allow modifications to blocks if the refcount is 1. At least, at its simplest, that's how copy-on-write works. To copy a file, you copy the block references and increment the reference counts. You won't end up with a diff or deltas stored anywhere.
- barrkel 6y ago
  Sure it is. You just need to look at it a little differently. Even in classical COW of memory pages in a Unix forked process, the set of pages mapped into the process with refcount 1 are a diff to all those with refcount > 1. Virtual machine snapshots are more explicitly diff-oriented. Deltas to the base disk or snapshot are stored separately (that's your diff), and "deleting a snapshot" actually means remapping all the separately stored blocks and collecting the newly released blocks. There's two strategies snapshotting can follow: copy-then-write-in-place, or redirect-on-write. Either way, the set of copied or redirected blocks are a diff to the in-place blocks, just the polarity of the difference is switched. See e.g. https://www.dell.com/community/Student-Discussions/Copy-on-write-Redirect-on-write/td-p/7147904 https://www.dell.com/community/Student-Discussions/Copy-on-w... Things get more interesting with e.g. ZFS snapshots, where the whole filesystem, including metadata, is copy-on-write, and tree-structured to maximize sharing and permit atomic writes (how ZFS solves RAID5 write hole). There, snapshots hold on to one of the old roots in the tree. The diff is implicit in the difference in tree structure; shared blocks are common, different blocks are different. It's super-easy to do a recursive comparison between such trees, extracting a diff is a sublinear time operation because it can trivially skip over identical subtrees. It's a matter of perspective, when you're in the middle of a recursive tree compare, whether you think you're actually diffing data, or whether the data in one leg of compare is simply telling you which subtrees are shared and which subtrees are different, and thus the data is a delta, or diff. You certainly don't need a complete traversal, which tells me that the data is doing most of the work.
  - klodolph 6y ago
    > The diff is implicit in the difference in tree structure; I can only interpret this as, "the data is not described as diffs." There's a meaningful difference here and I'm not being picky about it. To some extent, you can convert between a diff structure and shared structure, but that doesn't mean that the differences aren't meaningful. Two structures may be isomorphic but they represent data in different ways and the operations have different algorithmic complexity.

That's not really true. The copy-on-write filesystems just allow multiple files to reference the same blocks, and only allow modifications to blocks if the refcount is 1. At least, at its simplest, that's how copy-on-write works. To copy a file, you copy the block references and increment the reference counts. You won't end up with a diff or deltas stored anywhere.

barrkel 6y ago
Sure it is. You just need to look at it a little differently. Even in classical COW of memory pages in a Unix forked process, the set of pages mapped into the process with refcount 1 are a diff to all those with refcount > 1. Virtual machine snapshots are more explicitly diff-oriented. Deltas to the base disk or snapshot are stored separately (that's your diff), and "deleting a snapshot" actually means remapping all the separately stored blocks and collecting the newly released blocks. There's two strategies snapshotting can follow: copy-then-write-in-place, or redirect-on-write. Either way, the set of copied or redirected blocks are a diff to the in-place blocks, just the polarity of the difference is switched. See e.g. https://www.dell.com/community/Student-Discussions/Copy-on-write-Redirect-on-write/td-p/7147904 https://www.dell.com/community/Student-Discussions/Copy-on-w... Things get more interesting with e.g. ZFS snapshots, where the whole filesystem, including metadata, is copy-on-write, and tree-structured to maximize sharing and permit atomic writes (how ZFS solves RAID5 write hole). There, snapshots hold on to one of the old roots in the tree. The diff is implicit in the difference in tree structure; shared blocks are common, different blocks are different. It's super-easy to do a recursive comparison between such trees, extracting a diff is a sublinear time operation because it can trivially skip over identical subtrees. It's a matter of perspective, when you're in the middle of a recursive tree compare, whether you think you're actually diffing data, or whether the data in one leg of compare is simply telling you which subtrees are shared and which subtrees are different, and thus the data is a delta, or diff. You certainly don't need a complete traversal, which tells me that the data is doing most of the work.
- klodolph 6y ago
  > The diff is implicit in the difference in tree structure; I can only interpret this as, "the data is not described as diffs." There's a meaningful difference here and I'm not being picky about it. To some extent, you can convert between a diff structure and shared structure, but that doesn't mean that the differences aren't meaningful. Two structures may be isomorphic but they represent data in different ways and the operations have different algorithmic complexity.