Snapshots in bcachefs:
======================

The plan for snapshots in bcachefs is radically different than anything that's
been done previously in other filesystems, and the end result should be
drastically more efficient than e.g. btrfs. Snapshots will be very cheap to
create and keep around; in particular sparse snapshots (many snapshots with only
a few changes each) will be very cheap.

First thing to note - bcachefs the filesystem is built on top of bcachefs the
key/value store; all filesystem objects are just key/value pairs indexed by
inode:offset in a small number of btrees, and the btree code just treats the key
as a large integer. If this was a relational database, we'd have an extents
table, an inodes table, a dirents table, etc.

To implement snapshots, the key will be extended so that the low 32 bits will
now be a snapshot ID (this already exists in struct bpos, it's just unused by
the existing code).

Snapshots themselves will form a tree, where each entry in the tree has a 32 bit
snapshot ID and - importantly - we enforce that child snapshots have a node ID
less than their parent; thus, the root snapshot will have the id U32_MAX.

Then, when looking up filesystem data, our search key will include the snapshot
ID of the snapshot we're currently in. The btree lookup returns the first key
greater than or equal to the search key, so a lookup will return either a key in
the current snapshot (if it exists) or (in the common case) a key in some
ancestor snapshot - the only additional work we have to do for snapshots is to
check the snapshot ID of the key return against our current snapshot and iterate
forwards until we find a key in the current snapshot or an ancestor.

That's pretty much the bcachefs snapshot design in a nutshell, for normal keys.
Given typical filesystem snapshot usage, I expect the overhead from linear scan
over unrelated snapshots to be minimal to nonexistent for most users. There are
instances where this won't be the case - i.e. using snapshots for a virtual
machine base image; many virtual machines would have their own overwrites to the
same part of the keyspace. Reflink - which is already implemented in bcachefs -
doesn't suffer from this problem, so either we would recommend users use reflink
for those cases, or ideally we would be able to detect this condition and
transparently do something like reflink when we detect a high density of
overwrites in part of the keyspace.

Extents:
========

Extents, however, are more complicated - a key in a child snapshot always
overwrites/replicas a key in an ancestor snapshot exactly, but extents can
partially overlap in arbitrary ways. Some examples below will illustrate the
problems that snapshots introduce, and then a proposed solution.

A note: in bcachefs, extents are indexed by their end position, not their start.
This is more natural given typical usage: when doing a read we want the first
extent that ends after the start of the range we're reading from.

In the examples below, 1 is the ancestor snapshot/extent and 2 is the child, and
extents are listed in their sort order in the btree.

Suppose we have these two extents:

    1:   |--------|
    2:       |---------|

This is a problem: on lookup (for snapshot 2), we find the extent in 1 first, as
we should - we do require data from it. But we cannot use all of that extent; 2
overwrites it, so we have to keep scanning forwards to find out how much of that
extent we can use. But that forward scan has no stopping condition - extents are
indexed by the end and there can be an arbitrary number of extents in unrelated
snapshots in between.

Suppose we add the restriction: a child extent cannot cross the boundary at the
end of the ancestor extent, instead we split the child extent:

    2:       |----|
    1:   |--------|
    2:            |----|

This is still a problem for lookups, for example:

        |------|
       |-------|
      |--------|
     |---------|
    |----------|

We must also add the restriction: start of child cannot land in middle of
ancestor. Then we have these extents.

    1:   |---|
    2:       |----|
    1:       |----|
    2:            |----|

This appears workable - however, given that we can have an arbitrary number of
extents in different snapshots at the same position, this means we'll have to
either split an unbounded number of existing extents - or we could only split
the extent that's visible in the child snapshot, but this seems to result in
invariants that would be difficult or impossible to check:

    5:      |----|
    4: |---||----|
    3: |---------|
    2: |---------|
    1: |---------|

A different approach:
---------------------

The original problem arises because introducing snapshots broke the invariant
that extents are (also) ordered by start of extent (which was a result of
sorting by end of extend and not having overlapping extents). Suppose we added a
method for iterating across keys in a btree node in order the extent start
position.

Back to the first example:

    1:   |--------|
    2:       |---------|

Suppose we're reading from snapshot 2 at the position where extent 1 starts.
Lookup returns extent 1, as it should - but we need to determine when to stop
reading from extent 1. If we can scan forwards from extent 1, ordered by extent
start position, we can scan forwards until we find an extent that overwrites 1
(is in a newer snapshot than 1 and a descendant of the snapshot we're reading),
or until we see an extent that starts after the position where extent 1 ends.

Example 2:

    2:      |----|
    1: |--------------|

Suppose we're reading at the position where extent 1 starts. Lookup will return
extent 2, but we actually want extent 1: What we can do is notice that the
extent lookup return starts after the lookup position - so then iterate
backwards, ordered by extent start position, until we find an extent that starts
at or before our search position.

Example 3:

    1:      |----|
    2: |--------------|

Reading from snapshot 2, at the position where extent 1 starts. Lookup returns
extent 1, but we actually want extent 2.

Example 4:

    2:          |----|
    1:     |--------------|
    3: |-----------------------|

Reading from 3, at the start of extent 1: Then what?

Lookup returns extent 2, then as in example 2 we scan backwards by start of
extent pos to get extent 1.





    2:      |-----|
    1: |----------------|

    2:      |-----|
    1: |----------------|
    2:            |------------|