这段时间在断断续续地看 bcachefs 的相关内容，这里记录一下快照的实现细节。
数据结构
简要介绍一下涉及的主要数据结构。
copy-on-write(COW) b+tree（参考资料 1）
这是 bcachefs 的核心数据结构，其中的每个节点都比较大，典型的节点大小是 256KB。之所以用这么大的节点，是因为对节点的修改方式是 append-only 的（术语叫 log-structured）。如果要删除其中的某个 item，并不是把它直接从树中删除，而是在节点最后追加一个类型为 KEY_TYPE_whiteout 的相同 key 的 item。这样当查找该 item 的时候，找到这个带有 KEY_TYPE_whiteout 的 key 时，就知道该元素被删除了，从而跳过该 item 的处理。当节点满了之后可能需要分裂并引发对从当前节点到根节点的修改，这时就是常规的 COW 操作了（参考资料 2）。因为节点都比较大，同时对于链路上的节点大部分是 append 操作，不会引发 COW，因此并不会导致太多的写放大。
对于文件系统中的组成部分，如 inode/dirent/extent 等，会分别存放在各自的 COW b+tree 中，即 inode 存放在 inode b+tree 中，item key 类型为 KEY_TYPE_inode，dirent 存放在 dirent b+tree 中，item key 类型为 KEY_TYPE_dirent，以此类推。
subvolume（参考资料 3）
按照 bcachefs 的定义，subvolume 的作用主要有两个：
- 隔离不同用途的文件，从而不同的 subvolume 可以有不同的设置，例如加密，压缩，nocow 等设置项。同时，只能对 subvolume 做快照，不能对单个文件或普通文件夹做快照。
- 用来访问快照的内容。
在形式上，subvolume 看起来和普通的目录一样，但是功能上有区别，包括以上两点提到的可以设置不同的功能，以及可以做快照等，这些都是普通的目录所不能做的。在 bcachefs 中，普通目录的类型是 KEY_TYPE_dirent，subvolume 的类型是 KEY_TYPE_subvolume，他们存放在不同的 b+tree 中。
struct bpos
inode/dirent/extent/... b+tree 中的每个 item key 都包含如下结构体：
struct bpos {
__u32 snapshot;
__u64 offset;
__u64 inode;
};其中的 snapshot 是创建该 item 时所在 subvolume 所关联的 inode 的 bpos::snapshot 值。也就是说，记录 subvolume 本身的 item，和 subvolume 关联的 inode，两者的 bpos::snapshot 是不同的值。
初始文件系统根目录的 bpos::snapshot 值为 UINT32_MAX。
每创建一个新的 subvolume 就会分配一个新的整数作为新的 subvolume inode 的 bpos::snapshot 值。新创建的 subvolume 有属于自己的独立于根目录的一整套 inode/dirent/extent/subvolume/... b+tree。
例如，在挂载的根目录下执行
bcachefs subvolume create subvol因为 subvol 是在根目录下创建的，它的类型为 KEY_TYPE_subvolume，存放在根目录的 subvolume b+tree 中，bpos::snapshot 的值为 UINT32_MAX，它关联的 inode 的 bpos::snapshot 的值是 UINT32_MAX-1。
接着执行
touch subvol/a.txt则 subvol/a.txt 的类型为 KEY_TYPE_dirent，对应的 bpos::snapshot 的值为 UINT32_MAX-1。
如果对 subvol 进行快照：
bcachefs subvolume snapshot subvol snap则会再分配两个新的 id，一个给原来的 subvol 所关联的 inode，另一个给 snap 所关联的 inode（顺序无关）。subvol 和 snap 这两个 item 的类型都是 KEY_TYPE_subvolume，它们的 bpos::snapshot 的值都是 UINT32_MAX，它们关联的 inode 的 bpos::snapshot 的值分别为 UINT32_MAX-2 和 UINT32_MAX-3（或者交换）。
虽然 snap 也是一个 subvolume，但由于它是从 subvol 生成的，它没有自己独立的一套新的各种 b+tree，而是和 subvol 共享所有的 b+tree，这个很关键。
snapshot tree
snapshot id 相关的信息也存放在一棵 cow b+tree 中，相关的字段如下：
struct bch_snapshot {
__le32 flags;
__le32 parent;
__le32 children[2];
......
};其中 flags 表示该快照的状态（empty，live，deleted），parent 表示被快照的 subvolume 所关联的 inode 在快照前的 bpos::snapshot，如果该 subvolume 也有快照，则会记录在 children[2] 中。例如某个 subvolume 的 inode 的 bpos::snapshot 值为 10，当对它进行快照之后，它的 inode 的 bpos::snapshot 变为 9，而快照（也是一个 subvolume） 的 inode 的 bpos::snapshot 的值为 8。9 和 8 在树中是 10 的子节点。
当一个快照被删除时，如果它的后代 subvolume 都被删除了，那么它对应的 bch_snapshot 才可以被删除。
由于 snapshot id 的值一直递减（snapshot id 用完了怎么办？），子节点的值要比父节点的大，加上在 b+tree 中 key 按照升序排列，在检索时就能尽早发现最新的值，从而跳过旧的值。
快照的实现逻辑
上面介绍 struct bpos 的时候其实已经把要做的事情说完了，就是在执行
bcachefs subvolume snapshot subvol snap的时候，会分配两个新的 snapshot id（都比 subvol 原来的 inode 的 bpos::snapshot 值要小），其中一个给 subvol 所关联的 inode，另一个给 snap 所关联的 inode，就完成了。这时 snap 的内容与 subvol 的内容完全一样，并且没有进行任何的数据复制操作。
为什么这样就能实现快照的功能了呢？这里以 subvol/a.txt 为例来说明，包含文件内容的数据块记为 subvol-a-data[0,5]，其中中括号内的范围表示数据块的起止偏移。
初始共享
下面表格中的 - 表示不存在或者可以忽略。
快照前：
| path | type | bpos::snapshot |
bpos::snapshot of inode |
b+tree |
|---|---|---|---|---|
| subvol | KEY_TYPE_subvolume |
100 | 10 | BTREE_ID_subvolumes |
| subvol/a.txt | KEY_TYPE_dirent |
10 | 10 | BTREE_ID_dirents |
| subvol-a-data[0,5] | KEY_TYPE_extent |
10 | - | BTREE_ID_extents |
snapshot tree 快照前：
| snapshot id | flags | parent | children |
|---|---|---|---|
| 10 | live | 0 | {0, 0} |
执行快照后新增/变化的部分（注意 subvol inode 的 bpos::snapshot 变化）：
| path | type | bpos::snapshot |
bpos::snapshot of inode |
b+tree |
|---|---|---|---|---|
| subvol | KEY_TYPE_subvolume |
100 | 9 | BTREE_ID_subvolumes |
| snap | KEY_TYPE_subvolume |
100 | 8 | BTREE_ID_subvolumes |
快照后的 snapshot tree：
| snapshot id | flags | parent | children |
|---|---|---|---|
| 10 | deleted | 0 | {9, 8} |
| 9 | live | 10 | {0, 0} |
| 8 | live | 10 | {0, 0} |
这里要介绍一下 snapshot tree 的作用。在查找的时候，如果遇到其它需要比较的字段都相等但是 bpos::snapshot 不相等，bcachefs 会检查遇到的 snapshot id 是否是需要查找的 snapshot id 的祖先节点（不直接查找树，而是在内存里有缓存，使用 bch2_snapshot_is_ancestor() 来辅助判断）。如果遇到祖先节点，则会使用最小的 snapshot id（即最近的版本） 所对应的 item。
前面还说过，snap 和 subvol 共享 inode/dirent/extent/... b+tree。因此如果要访问 snap/a.txt，当使用 "a.txt" 这个名字去检索的时候，会带上查找路径上最近的 subvolume（这里就是 snap）所关联的 inode 的 bpos::snapshot（在这里是 8）去查找，虽然找不到 snapshot id 为 8 的 item，但是找到了它的祖先 10 的版本（即 subvol/a.txt），因此最终返回的就是 subvol/a.txt，从而实现了 snap/a.txt 和 subvol/a.txt 共享同一份数据的效果。
修改内容
那么如果修改了文件内容呢？假设修改了 subvol/a.txt [2,3] 区间的内容，包含修改内容的数据块表示为 snap-a-data[2,3]，新增了一个 item：
| path | type | bpos::snapshot |
bpos::snapshot of inode |
b+tree |
|---|---|---|---|---|
| snap-a-data[2,3] | KEY_TYPE_extent |
8 | - | BTREE_ID_extents |
这样当读取 snap/a.txt 所有内容的时候，会根据读取的偏移，依次读取 subvol-a-data[0,1]，snap-a-data[2,3]，subvol-a-data[4,5] 三部分数据，从而得到修改后的 snap/a.txt 的所有内容。如果需要读取 subvol/a.txt 的内容，由于 snap-a-data[2,3] 的 snapshot id 8 并不是 10（subvol/a.txt 的 inode bpos::snapshot 是 10）的祖先，因此会略过 snap-a-data[2,3]，从而读取完整的 subvol-a-data[0,5]。
删除数据
承接前面的操作，接着删除 subvol/a.txt，会插入一个类型为 KEY_TYPE_whiteout 的 item：
| path | type | bpos::snapshot |
bpos::snapshot of inode |
b+tree |
|---|---|---|---|---|
| subvol/a.txt | KEY_TYPE_whiteout |
9 | - | BTREE_ID_dirents |
这样当在 subvol 下查找 "a.txt" 的时候，会先找到这个删除的标记，从而跳过没有被立刻删除的 item，并且会在后续的 gc 中把这个 item 以及标记都删掉，从而真正实现物理删除。
这里虽然把 subvol/a.txt 删除了，但是它原来的数据块 subvol-a-data[0,5] 因为有部分数据仍然被 snap/a.txt 使用，因此整个 extent 仍然会被保留。gc 的时候，会根据 bucket（磁盘数据块的分配单位）的碎片情况决定要不要 compaction，从而把原来的 subvol-a-data[0, 5] 拆成 [0,1]，[2,3]，[4,5] 三部分，这样在删除了 subvol/a.txt 但 snap/a.txt 还存在的情况下，及时清理不被使用的 subvol-a-data[2,3]（通过 backref 发现数据块已经没有有效的引用，就可以回收了）。
如果我们继续删除 snap/a.txt，一个 snapshot id 为 8 的 whiteout 会被插入 dirents b+tree 中，用来标记 snap/a.txt 已经被删除：
| path | type | bpos::snapshot |
bpos::snapshot of inode |
b+tree |
|---|---|---|---|---|
| snap/a.txt | KEY_TYPE_whiteout |
8 | - | BTREE_ID_dirents |
删除整个 subvolume
接着上面的步骤，删除 subvol 时，除了删除相关的 item（KEY_TYPE_inode，KEY_TYPE_subvolume 等）之外，还会把 snapshot tree 中 id 为 9 的节点标记为 deleted：
| snapshot id | flags | parent | children |
|---|---|---|---|
| 10 | deleted | 0 | {9, 8} |
| 9 | deleted | 10 | {0, 0} |
| 8 | live | 10 | {0, 0} |
这样当 gc 进行扫描的时候，会发现树中所有 snapshot id 为 9 没有后继节点，并且本身也被标记为 deleted，就可以把 snapshot id 为 9 的 item 都物理删除。但是因为 10 还有一个子节点 8（也就是 snap）还存活，因此不能把 snapshot id 为 10 的 item 删掉，这样 snap/a.txt 还能访问到 subvol-a-data[0,5] 的内容。
如果我们继续删除 snap：
| snapshot id | flags | parent | children |
|---|---|---|---|
| 10 | deleted | 0 | {9, 8} |
| 9 | deleted | 10 | {0, 0} |
| 8 | deleted | 10 | {0, 0} |
对 snapshot id 为 8 的 item 的处理同上。接着发现 10 以及它的子节点都被删除了，因此 snapshot id 为 10 的 item 也可以删除了。
reflink
从上面快照的描述可以看出，各种 item 的生命周期是由 snapshot tree 来决定的。为了实现在不同的 subvolume 中共享数据（不同的 subvolume 有各自独立的 snapshot tree），例如执行
cp --reflink=always subvol1/a.txt subvol2/a.txt的时候，如果发现 subvol1 和 subvol2 是两个没有关联的 subvolume，则会把 subvol1/a.txt 的数据块指针类型从 KEY_TYPE_extent 变为 KEY_TYPE_reflink_p，在额外的 reflink b+tree 中增加一个 KEY_TYPE_reflink_v 的 item 记录被共享的数据块，并增加这个 item 的引用计数。当其中一个文件被删除（例如删除了 subvol1/a.txt，还剩下 subvol2/a.txt）就会减少引用计数，但不会立即把数据块改回 KEY_TYPE_extent，只有 gc 执行 compact 的时候才有可能改回去（也可能不改）。
其它
从上面的介绍可以看到，bcachefs 的快照实现方式有点像是 leveldb 的加强变种，不同点在于使用 b+tree 替换了 lsm-tree 和用 snapshot id 替换了事务编号。鉴于 bcachefs 的作者 Kent Overstreet 曾在 google 工作过，看起来 log-structured 属于 google 的传统艺能了。
之前看过 btrfs 实现原理的文档还写了篇笔记 B+ 树 (2): snapshot, copy-on-write，原理应该是本文提到的三个文件系统中最容易理解的，就是引用计数，实现起来也相对简单。由于引用计数会导致写入过多，开发者也在考虑将部分操作转为异步 gc 的形式（参考资料 4），这部分工作统一归结到一项叫 extent tree v2 的改进中。不过到目前的 linux 6.19 为止，该项工作仍然处于未完成状态。
zfs 的代码我没深入看过，主要是通过参考资料 5 和 6 了解的。它使用了一个叫 txg 的事务编号来保证数据的修改是线性的，通过 deadlist 来管理数据的生命周期，因此它的快照不能修改。如果想修改快照的内容得先克隆一下，并且快照在有克隆存在的前提下不能被删除。zfs 也一直拒绝使用引用计数，不过也在 v2.3.0 加了个 Block Cloning Table(BRT) ，把需要共享的数据块保存到 BRT 中并使用了引用计数，从而实现了跨 dataset 的数据共享。
由于引用计数（例子就是 btrfs）和 all log-structured（例如 nilfs2）都会导致写入过多，我比较倾向像 zfs 的 txg 和 bcachefs 的 snapshot 这样的版本号机制来实现快照。backref 会影响写性能，像 bcachefs 这样依赖 gc 的实现无法避免。zfs 如果使用 log-structured，异步 gc 对于 txg 怎么处理是个问题，还要加上 backref 就更加复杂了。zfs 通过 deadlist 可以很方便确定两个快照之间的 diff，实现 send/recv 都很方便，bcachefs 则感觉不好实现。
最后是吐槽。zfs 是目前三者中最稳定也是功能最丰富的，开发也一直很积极，然而由于许可证的问题无法进入 mainline，导致每次更新内核都要重新编译，大大限制了在人群（尤其是新手）中的普及；btrfs 从诞生开始到现在就没真正稳定下来过，加上还有 extent tree v2，qgroup，raid5/6 这些未完成的坑，在可预见的 5~10 年内估计都不可能稳定下来；bcachefs 由于 Kent 跟 Linus 杠上了而被踢出 mainline，这下本来想支持一下的公司都退缩了，一直以来主要开发者就只有他自己一个，再加上他的性格，好担心 bcachefs 会像 reiserfs 一样最终变得无人问津。
参考资料
[1] bcachefs/Architecture
[2] B-trees, Shadowing, and Clones
[3] bcachefs/Snapshots
[4] Btrfs: how reference counting works
[5] Btrfs vs ZFS 实现 snapshot 的差异
[6] OpenZFS novel algorithms: snapshots, space allocation, RAID-Z - Matt Ahrens