Btrfs vs ZFS 实现 snapshot 的差异

1.1   子卷和快照的术语

在 btrfs 中，存在于存储媒介中的只有「子卷」的概念，「快照」只是个创建「子卷」的方式， 换句话说在 btrfs 的术语里，子卷（subvolume）是个名词，而快照（snapshot）是个动词。 如果脱离了 btrfs 术语的上下文，或者不精确地称呼的时候，也经常有文档把 btrfs 的快照命令创建出的子卷叫做一个快照，所以当提到快照的时候，根据上下文判断这里是个动词还是名词， 把名词的快照当作用快照命令创建出的子卷就可以了。或者我们可以理解为， 互相共享一部分元数据（metadata）的子卷互为彼此的快照（名词） ， 那么按照这个定义的话，在 btrfs 中创建快照（名词）的方式其实有两种：

1. 用 btrfs subvolume snapshot 命令创建快照
2. 用 btrfs send 命令并使用 -p 参数发送快照，并在管道另一端接收

定义中「互相共享一部分 元数据 」比较重要，因为除了快照的方式之外， btrfs 的子卷间也可以通过 reflink 的形式共享数据块。我们可以对一整个子卷（甚至目录）执行 cp -r --reflink=always ，创建出一个副本，副本的文件内容通过 reflink 共享原本的数据，但不共享元数据，这样创建出的就不是快照。

说了这么多，其实关键的只是 btrfs 在传统 Unix 文件系统的「目录/文件/inode」 这些东西之外只增加了一个「子卷」的新概念，而子卷间可以共享元数据或者数据， 用快照命令创建出的子卷就是共享一部分元数据。

1.2   于是子卷在存储介质中是如何记录的呢？

首先要说明， btrfs 中大部分长度可变的数据结构都是 CoW B-tree ，一种经过修改适合写时拷贝的B树结构，所以在 on-disk format 中提到了很多个树。这里的树不是指文件系统中目录结构树，而是写时拷贝B树（CoW B-tree，下文简称B树） ，如果不关心B树细节的话可以把 btrfs 所说的一棵树理解为关系数据库中的一个表， 和数据库的表一样 btrfs 的树的长度可变，然后表项内容根据一个 key 排序。

B树结构由索引 key 、中间节点和叶子节点构成。每个 key 是一个 (uint64_t object_id, uint8_t item_type, uint64_t item_extra) 这样的三元组，三元组每一项的具体含义由 item_type 定义。 key 三元组构成了对象的概念，每个对象（object）在树中用一个或多个表项（item）描述，同 object_id 的表项共同描述一个对象。B树中的 key 只用来比较大小而不必连续，从而 object_id 也不必连续，只是按大小排序。有一些预留的 object_id 不能用作别的用途，他们的编号范围是 -255ULL 到 255ULL，也就是表中前 255 和最后 255 个编号预留。

B树中间节点和叶子节点结构大概像是这个样子：

由此，每个中间节点保存一系列 key 到叶子节点的指针，而叶子节点内保存一系列 item ，每个 item 固定大小，并指向节点内某个可变大小位置的 data 。从而逻辑上一棵B树可以包含任何类型的 item ，每个 item 都可以有可变大小的附加数据。通过这样的B树结构，可以紧凑而灵活地表达很多数据类型。

有这样的背景之后，比如在 SysadminGuide 这页的 Flat 布局 有个子卷布局的例子。

toplevel         (volume root directory, not to be mounted by default)
    +-- root       (subvolume root directory, to be mounted at /)
    +-- home       (subvolume root directory, to be mounted at /home)
    +-- var        (directory)
    |   \-- www    (subvolume root directory, to be mounted at /var/www)
    \-- postgres   (subvolume root directory, to be mounted at /var/lib/postgresql)

用圆柱体表示子卷的话画成图大概是这个样子：

上图例子中的 Flat 布局在 btrfs 中大概是这样的数据结构， 其中实线箭头是B树一系列中间节点和叶子节点，逻辑上指向一棵B树，虚线箭头是根据 inode 号之类的编号的引用：

上图中已经隐去了很多和本文无关的具体细节，所有这些细节都可以通过 btrfs inspect-internal 的 dump-super 和 dump-tree 查看到。

ROOT_TREE 中记录了到所有别的B树的指针，在一些文档中叫做 tree of tree roots 。「所有别的B树」 举例来说比如 2 号 extent_tree ，3 号 chunk_tree ， 4 号 dev_tree ，10 号 free_space_tree ，这些B树都是描述 btrfs 文件系统结构非常重要的组成部分，但是在本文关系不大， 今后有机会再讨论它们。在 ROOT_TREE 的 5 号对象有一个 fs_tree ，它描述了整个 btrfs pool 的顶级子卷，也就是图中叫 toplevel 的那个子卷（有些文档用定冠词称 the FS_TREE 的时候就是在说这个 5 号树，而不是别的子卷的 FS_TREE ）。除了顶级子卷之外，别的所有子卷的 object_id 在 256ULL 到 -256ULL 的范围之间，对子卷而言 ROOT_TREE 中的这些 object_id 也同时是它们的 子卷 id ，在内核挂载文件系统的时候可以用 subvolid 找到它们，别的一些对子卷的操作也可以直接用 subvolid 表示一个子卷。 ROOT_TREE 的 6 号对象描述的不是一棵树，而是一个名叫 default 的特殊目录，它指向 btrfs pool 的默认挂载子卷。最初 mkfs 的时候，这个目录指向 ROOT_ITEM 5 ，也就是那个顶级子卷，之后可以通过命令 btrfs subvolume set-default 修改它指向别的子卷，这里它被改为指向 ROOT_ITEM 256 亦即那个名叫 "root" 的子卷。

每一个子卷都有一棵自己的 FS_TREE （有的文档中叫 file tree），一个 FS_TREE 相当于传统 Unix 文件系统中的一整个 inode table ，只不过它除了包含 inode 信息之外还包含所有文件夹内容。在 FS_TREE 中， object_id 同时也是它所描述对象的 inode 号，所以 btrfs 的 子卷有互相独立的 inode 编号 ，不同子卷中的文件或目录可以拥有相同的 inode 。 或许有人不太清楚子卷间 inode 编号独立意味着什么，简单地说，这意味着你不能跨子卷创建 hard link ，不能跨子卷 mv 移动文件而不产生复制操作。不过因为 reflink 和 inode 无关， 可以跨子卷创建 reflink ，也可以用 reflink + rm 的方式快速「移动」文件（这里移动加引号是因为 inode 变了，传统上不算移动）。

FS_TREE 中一个目录用一个 inode_item 和多个 dir_item 描述， inode_item 是目录自己的 inode ，那些 dir_item 是目录的内容。 dir_item 可以指向别的 inode_item 来描述普通文件和子目录， 也可以指向 root_item 来描述这个目录指向一个子卷。有人或许疑惑，子卷就没有自己的 inode 么？其实如果看 数据结构定义 的话 struct btrfs_root_item 结构在最开头的地方包含了一个 struct btrfs_inode_item 所以 root_item 也同时作为子卷的 inode ，不过用户通常看不到这个子卷的 inode ，因为子卷在被（手动或自动地）挂载到目录上之后， 用户会看到的是子卷的根目录的 inode 。

比如上图 FS_TREE toplevel 中，有两个对象，第一个 256 是（子卷的）根目录，第二个 257 是 "var" 目录，256 有4个子目录，其中 "root" "home" "postgres" 这三个指向了 ROOT_TREE 中的对应子卷，而 "var" 指向了 inode 257 。然后 257 有一个子目录叫 "www" 它指向了 ROOT_TREE 中 object_id 为 258 的子卷。

1.3   那么快照又是如何记录的呢？

以上是子卷、目录、 inode 在 btrfs 中的记录方式，你可能想知道，如何记录一个快照呢？ 特别是，如果对一个包含子卷的子卷创建了快照，会得到什么结果呢？如果我们在上面的布局基础上执行：

btrfs subvolume snapshot toplevel toplevel/toplevel@s1

那么产生的数据结构大概如下所示：

在 ROOT_TREE 中增加了 260 号子卷，其内容复制自 toplevel 子卷，然后 FS_TREE toplevel 的 256 号 inode 也就是根目录中增加一个 dir_item 名叫 toplevel@s1 它指向 ROOT_ITEM 的 260 号子卷。这里看似是完整复制了整个 FS_TREE 的内容，这是因为 CoW b-tree 当只有一个叶子节点时就复制整个叶子节点。如果子卷内容再多一些，除了叶子之外还有中间节点， 那么只有被修改的叶子和其上的中间节点需要复制。从而创建快照的开销基本上是 O( level of FS_TREE )，而B树的高度一般都能维持在很低的程度，所以快照创建速度近乎是常数开销。

从子卷和快照的这种实现方式，可以看出： 虽然子卷可以嵌套子卷，但是对含有嵌套子卷的子卷做快照的语义有些特别 。上图中我没有画 toplevel@s1 下的各个子卷到对应 ROOT_ITEM 之间的虚线箭头， 是因为这时候如果你尝试直接跳过 toplevel 挂载 toplevel@s1 到挂载点， 会发现那些子卷没有被自动挂载，更奇怪的是那些子卷的目录项也不是个普通目录， 尝试往它们中放东西会得到无权访问的错误，对它们能做的唯一事情是手动将别的子卷挂载在上面。 推测原因在于这些子目录并不是真的目录，没有对应的目录的 inode ，试图查看它们的 inode 号会得到 2 号，而这是个保留号不应该出现在 btrfs 的 inode 号中。 每个子卷创建时会记录包含它的上级子卷，用 btrfs subvolume list 可以看到每个子卷的 top level subvolid ，猜测当挂载 A 而 A 中嵌套的 B 子卷记录的上级子卷不是 A 的时候， 会出现上述奇怪行为。嵌套子卷的快照还有一些别的奇怪行为，大家可以自己探索探索。

btrfs 的子卷可以设置「可写」或者「只读」，在创建一个快照的时候也可以通过 -r 参数创建出一个只读快照。通常只读快照可能比可写的快照更有用，因为 btrfs send 命令只接受只读快照作为参考点。子卷可以有两种方式切换它是否只读的属性，可以通过 btrfs property set <subvol> ro 直接修改是否只读，也可以对只读子卷用 btrfs subvolume snapshot 创建出可写子卷，或者反过来对可写子卷创建出只读子卷。

只读快照也有些特殊的限制，在 SysadminGuide#Special_Cases 就提到一例，你不能把只读快照用 mv 移出包含它的目录，虽然你能用 mv 给它改名或者移动包含它的目录 到别的地方。 btrfs wiki 上给出这个限制的原因是子卷中记录了它的上级， 所以要移动它到别的上级需要修改这个子卷，从而只读子卷没法移动到别的上级（ 不过我还没搞清楚子卷在哪儿记录了它的上级，记录的是上级目录还是上级子卷）。不过这个限制可以通过 对只读快照在目标位置创建一个新的只读快照，然后删掉原位置的只读快照来解决。

2.1   ZFS 设计中和快照相关的一些术语和概念

2.2   ZFS 的概念与 btrfs 概念的对比

先说书签和检查点，因为这是两个 btrfs 目前完全没有的功能。

书签功能完全围绕 ZFS send 的工作原理，而 ZFS send 位于 ZFS 设计中的 DSL 层面，甚至不关心它 send 的快照的数据是来自文件系统还是 zvol 。在发送端它只是从目标快照递归取数据块，判断 TXG 是否老于参照点的快照，然后把新的数据块全部发往 send stream ；在接收端也只是完整地接收数据块， 不加以处理，。与之不同的是 btrfs 的 send 的工作原理是工作在文件系统的只读子卷层面， 发送端在内核代码中根据目标快照的 b 树和参照点快照的 generation 生成一个 diff （可以通过 btrfs subvolume find-new 直接拿到这个 diff ），然后在用户态代码中根据 diff 和参照点、目标快照的两个只读子卷的数据产生一连串修改文件系统的指令， 指令包括创建文件、删除文件、让文件引用数据块（保持 reflink ）等操作；在接收端则完全工作在用户态下， 根据接收到的指令重建目标快照。可见 btrfs send 需要在发送端读取参照点快照的数据（比如找到 reflink 引用），从而 btrfs 没法（或者很难）实现书签功能。

检查点也是 btrfs 目前没有的功能。 btrfs 目前不能对顶层子卷做递归的 snapshot ，btrfs 的子卷也没有类似 ZFS 数据集的层级关系和可继承属性，从而没法实现类似检查点的功能。

除了书签和检查点之外，剩下的概念可以在 ZFS 和 btrfs 之间有如下映射关系：

对 ZFS 数据集的操作，大部分也可以找到对应的对 btrfs 子卷的操作。

可见虽然功能上类似，但是至少从管理员管理的角度而言， zfs 对文件系统、快照、克隆的划分更为清晰， 对他们能做的操作也更为明确。这也是很多从 ZFS 迁移到 btrfs ，或者反过来从 btrfs 换用 zfs 时，一些人困惑的起源（甚至有人据此说 ZFS 比 btrfs 好在 cli 设计上）。

不过 btrfs 子卷的设计也使它在系统管理上有了更大的灵活性。比如在 btrfs 中删除一个子卷不会受制于别的子卷是否存在，而在 zfs 中要删除一个快照必须先保证先摧毁掉依赖它的克隆。 再比如 btrfs 的可写子卷没有主次之分，而 zfs 中一个文件系统和其克隆之间有明显的区别，所以需要 promote 命令调整差异。还有比如 ZFS 的文件系统只能回滚到最近一次的快照， 要回滚到更久之前的快照需要删掉中间的快照，并且回滚之后原本的文件系统数据和快照数据就被丢弃了； 而 btrfs 中因为回滚操作相当于调整子卷的挂载，所以不需要删掉快照， 并且回滚之后原本的子卷和快照还可以继续保留。

加上 btrfs 有 reflink ，这给了 btrfs 在使用中更大的灵活性，可以有一些 zfs 很难做到的用法。 比如想从快照中打捞出一些虚拟机镜像的历史副本，而不想回滚整个快照的时候，在 btrfs 中可以直接 cp --reflink=always 将镜像从快照中复制出来，此时的复制将和快照共享数据块； 而在 zfs 中只能用普通 cp 复制，会浪费很多存储空间。

2.3   ZFS 中是如何存储这些数据集的呢

要讲到存储细节，首先需要 了解一下 ZFS 的分层设计 。不像 btrfs 基于现代 Linux 内核，有许多现有文件系统已经实现好的基础设施可以利用， 并且大体上只用到一种核心数据结构（CoW的B树）； ZFS 则脱胎于 Solaris 的野心勃勃， 设计时就分成很多不同的子系统，逐步提升抽象层次， 并且每个子系统都发明了许多特定需求下的数据结构来描述存储的信息。 在这里和本文内容密切相关的是 ZPL 、 DSL 、 DMU 这些 ZFS 子系统。

Sun 曾经写过一篇 ZFS 的 On disk format 对理解 ZFS 如何存储在磁盘上很有帮助，虽然这篇文档是针对 Sun 还在的时候 Solaris 的 ZFS ，现在 ZFS 的内部已经变化挺大，不过对于理解本文想讲的快照的实现方式还具有参考意义。这里借助这篇 ZFS On Disk Format 中的一些图示来解释 ZFS 在磁盘上的存储方式。

3.1   日志结构文件系统中用的垃圾回收算法

讲 btrfs 和 zfs 用到的删除算法之前，先讲一下日志结构（log-structured）文件系统中的垃圾回收（ GC, Garbage Collection）算法。对熟悉编程的人来说，讲到空间释放算法，大概首先会想到 GC ，因为这里要解决的问题乍看起来很像编程语言的内存管理中 GC 想要解决的问题：有很多指针相互指向很多数据结构，找其中没有被引用的垃圾然后释放掉。

首先要澄清一下 日志结构文件系统（log-structured file system） 的定义，因为有很多文件系统用日志，而用了日志的不一定是日志结构文件系统。 在维基百科上有个页面介绍 日志结构文件系统 ，还有个 列表列出了一些日志结构文件系统 。通常说，整个文件系统的存储结构都组织成一个大日志的样子，就说这个文件系统是日志结构的， 这包括很多早期学术研究的文件系统，以及目前 NetBSD 的 LFS 、Linux 的 NILFS ，用在光盘介质上的 UDF ，还有一些专门为闪存优化的 JFFS 、 YAFFS 以及 F2FS 。日志结构文件系统不包括那些用额外日志保证文件系统一致性，但文件系统结构不在日志中的 ext4 、 xfs 、 ntfs 、 hfs+ 。

简单来说，日志结构文件系统就是把存储设备当作一个大日志，每次写入数据时都添加在日志末尾， 然后用写时复制重新写入元数据，最后提交整个文件系统结构。因为这里用了写时复制，原本的数据块都还留着， 所以可以很容易实现快照之类的功能。从这个特征上来说，写时拷贝文件系统（CoW FS）像 btrfs/zfs 这些在一些人眼中也符合日志结构文件系统的特征， 所以也有人说写时拷贝文件系统算是日志结构文件系统的一个子类。不过日志结构文件系统的另一大特征是利用 GC 回收空间，这里是本文要讲的区别，所以在我看来不用 GC 的 btrfs 和 zfs 不算是日志结构文件系统。

举个例子，比如下图是一个日志结构文件系统的磁盘占用，其中绿色是数据，蓝色是元数据（比如目录结构和 inode），红色是文件系统级关键数据（比如最后的日志提交点），一开始可能是这样，有9个数据块， 2个元数据块，1个系统块：

现在要覆盖 2 和 3 的内容，新写入 n2 和 n3 ，再删除 4 号的内容 ，然后修改 10 里面的 inode 变成 n10 引用这些新数据，然后写入一个新提交 n12 ，用黄色表示不再被引用的垃圾，提交完大概是这样：

日志结构文件系统需要 GC 比较容易理解，写日志嘛，总得有一个「添加到末尾」的写入点，比如上面图中的 n12 就是当前的写入点。空盘上连续往后写而不 GC 总会遇到空间末尾，这时候就要覆盖写空间开头， 就很难判断「末尾」在什么地方，而下一次写入需要在哪里了。 这时文件系统也不知道需要回收哪些块（图中的 o2 o3 o4 o10 和 o12），因为这些块可能被别的地方还继续 引用着，需要等到 GC 时扫描元数据来判断。

和内存管理时的 GC 不同的一点在于，文件系统的 GC 肯定不能停下整个世界跑 GC ，也不能把整个地址空间对半分然后 Mark-and-Sweep ，这些在内存中还尚可的简单策略直接放到文件系统中绝对是性能灾难。所以文件系统的 GC 需要并行的后台 GC ，并且需要更细粒度的分块机制能在 Mark-and-Sweep 的时候保持别的地方可以继续写入数据而维持文件系统的正常职能。

通常文件系统的 GC 是这样，先把整个盘分成几个段（segment）或者区域(zone)，术语不同不过表达的概念类似， 然后 GC 时挑一个老段，扫描文件系统元数据找出要释放的段中还被引用的数据块，搬运到日志末尾，最后整个释放一段。 搬运数据块时，也要调整文件系统别的地方对被搬运的数据块的引用。

物理磁盘上一般有扇区的概念，通常是 512B 或者 4KiB 的大小，在文件系统中一般把连续几个物理块作为一个数据块， 大概是 4KiB 到 1MiB 的数量级，然后日志结构文件系统中一个段(segment)通常是连续的很多块，数量级来看大约是 4MiB 到 64MiB 这样的数量级。相比之下 ufs/ext4/btrfs/zfs 的分配器通常还有 block group 的概念， 大概是 128MiB 到 1GiB 的大小。可见日志结构文件系统的段，是位于数据块和其它文件系统 block group 中间的一个单位。段大小太小的话，会显著增加空间管理需要的额外时间空间开销，而段大小太大的话， 又不利于利用整个可用空间，这里的抉择有个平衡点。

继续上面的例子，假设上面文件系统的图示中每一列的4块是一个段，想要回收最开头那个段， 那么需要搬运还在用的 1 到空闲空间，顺带修改引用它的 n10 ，最后提交 n12 ：

要扫描并释放一整段，需要扫描整个文件系统中别的元数据（图中的 n12 和 n10 和 11）来确定有没有引用到目标段中的地址，可见释放一个段是一个 \(O(N)\) 的操作，其中 N 是元数据段的数量，按文件系统的大小增长， 于是删除快照之类可能要连续释放很多段的操作在日志文件系统中是个 \(O(N^2)\) 甚至更昂贵的操作。 在文件系统相对比较小而系统内存相对比较大的时候，比如手机上或者PC读写SD卡，大部分元数据块（ 其中包含块指针）都能放入内存缓存起来的话，这个扫描操作的开销还是可以接受的。 但是对大型存储系统显然扫描并释放空间就不合适了。

段的抽象用在闪存类存储设备上的一点优势在于，闪存通常也有擦除块的概念，比写入块的大小要大， 是连续的多个写入块构成，从而日志结构的文件系统中一个段可以直接对应到闪存的一个擦除块上。 所以闪存设备诸如U盘或者 SSD 通常在底层固件中用日志结构文件系统模拟一个块设备，来做写入平衡。 大家所说的 SSD 上固件做的 GC ，大概也就是这样一种操作。

基于段的 GC 还有一个显著缺陷，需要扫描元数据，复制搬运仍然被引用到的块，这不光会增加设备写入， 还需要调整现有数据结构中的指针，调整指针需要更多写入，同时又释放更多数据块， F2FS 等一些文件系统设计中把这个问题叫 Wandering Tree Problem ，在 F2FS 设计中是通过近乎「作弊」的 NAT 转换表 放在存储设备期待的 FAT 所在位置，不仅能让需要扫描的元数据更集中，还能减少这种指针调整导致的写入。

不过基于段的 GC 也有一些好处，它不需要复杂的文件系统设计，不需要特殊构造的指针， 就能很方便地支持大量快照。一些日志结构文件系统比如 NILFS 用这一点支持了「连续快照（continuous snapshots）」，每次文件系统提交都是自动创建一个快照，用户可以手动标记需要保留哪些快照， GC 算法则排除掉用户手动标记的快照之后，根据快照创建的时间，先从最老的未标记快照开始回收。 即便如此， GC 的开销（CPU时间和磁盘读写带宽）仍然是 NILFS 最为被人诟病的地方，是它难以被广泛采用的原因。 为了加快 NILFS 这类日志文件系统的 GC 性能让他们能更适合于普通使用场景，也有许多学术研究致力于探索和优化 GC ，使用更先进的数据结构和算法跟踪数据块来调整 GC 策略，比如这里有一篇 State-of-the-art Garbage Collection Policies for NILFS2 。

3.2   WAFL 早期使用的可用空间位图数组

从日志结构文件系统使用 GC 的困境中可以看出，文件系统级别实际更合适的， 可能不是在运行期依赖扫描元数据来计算空间利用率的 GC ，而是在创建快照时或者写入数据时就预先记录下快照的空间利用情况， 从而可以细粒度地跟踪空间和回收空间，这也是 WAFL 早期实现快照的设计思路。

WAFL 早期记录快照占用数据块的思路从表面上来看也很「暴力」，传统文件系统一般有个叫做「位图（bitmap ）」的数据结构，用一个二进制位记录一个数据块是否占用，靠扫描位图来寻找可用空间和已用空间。 WAFL 的设计早期中考虑既然需要支持快照，那就把记录数据块占用情况的位图，变成快照的数组。 于是整个文件系统有个 256 大小的快照利用率数组，数组中每个快照记录自己占用的数据块位图， 文件系统中最多能容纳 255 个快照。

上面每个单元格都是一个二进制位，表示某个快照有没有引用某个数据块。有这样一个位图的数组之后， 就可以直接扫描位图判断出某个数据块是否已经占用，可以找出尚未被占用的数据块用作空间分配， 也可以方便地计算每个快照引用的空间大小或者独占的空间大小，估算删除快照后可以释放的空间。

需要注意的是，文件系统中可以有非常多的块，从而位图数组比位图需要更多的元数据来表达。 比如估算一下传统文件系统中一块可以是 4KiB 大小，那么跟踪空间利用的位图需要 1bit/4KiB ， 1TiB 的盘就需要 32MiB 的元数据来存放位图； 而 WAFL 这种位图数组即便限制了快照数量只能有255个，仍需要 256bit/4KiB 的空间开销， 1TiB 的盘需要的元数据开销陡增到 8GiB ，这些还只是单纯记录空间利用率的位图数组，不包括别的元数据。

使用这么多元数据表示快照之后，创建快照的开销也相应地增加了，需要复制整个位图来创建一个新的快照， 按上面的估算 1TiB 的盘可能需要复制 32MiB 的位图，这不再是一瞬能完成的事情， 期间可能需要停下所有对文件系统的写入等待复制完成。 位图数组在存储设备上的记录方式也很有讲究，当删除快照时希望能快速读写上图中的一整行位图， 于是可能希望每一行位图的存储方式在磁盘上都尽量连续， 而在普通的写入操作需要分配新块时，想要按列的方式扫描位图数组，找到没有被快照占用的块， 从而上图中按列的存储表达也希望在磁盘上尽量连续。 WAFL 的设计工程师们在位图数组的思路下，实现了高效的数据结构让上述两种维度的操作都能快速完成， 但是这绝不是一件容易的事情。

位图数组的表达方式也有其好处，比如除了快照之外，也可以非常容易地表达类似 ZFS 的克隆和独立的文件系统这样的概念，这些东西和快照一样，占用仅有的 256 个快照数量限制。 这样表达的克隆可以有数据块和别的文件系统共享，文件系统之间也可以有类似 reflink 的机制共享数据块，在位图数组的相应位置将位置1即可。

使用位图数组的做法，也只是 WAFL 早期可能采用的方式，由于 WAFL 本身是闭源产品， 难以获知它具体的工作原理。哈佛大学和 NetApp 的职员曾经在 FAST10 (USENIX Conference on File and Storage Technologies) 上发表过一篇讲解高效跟踪和使用 back reference 的论文，叫 Tracking Back References in a Write-Anywhere File System ，可以推测在新一代 WAFL 的设计中可能使用了类似 btrfs backref 的实现方式，接下来会详细介绍。

3.3   ZFS 中关于快照和克隆的空间跟踪算法

OpenZFS 的项目领导者，同时也是最初设计 ZFS 中 DMU 子系统的作者 Matt Ahrens 在 DMU 和 DSL 中设计并实现了 ZFS 独特的快照的空间跟踪算法。他也在很多地方发表演讲，讲过这个算法的思路和细节， 比如右侧就是他在 BSDCan 2019 做的演讲 How ZFS snapshots really work And why they perform well (usually) 的 YouTube 视频。

其中 Matt 讲到了三个删除快照的算法，分别可以叫做「🐢乌龟算法」、「🐰兔子算法」、「🐆豹子算法」， 接下来简单讲讲这些算法背后的思想和实现方式。

🐢乌龟算法：概念上 ZFS 如何删快照

乌龟算法没有实现在 ZFS 中，不过方便理解 ZFS 在概念上如何考虑快照删除这个问题，从而帮助理解 后面的🐰兔子算法和🐆豹子算法。

要删除一个快照， ZFS 需要找出这个快照引用到的「独占」数据块，也就是那些不和别的数据集或者快照共享的 数据块。 ZFS 删除快照基于这几点条件：

1. ZFS 快照是只读的。创建快照之后无法修改其内容。
2. ZFS 的快照是严格按时间顺序排列的，这里的时间指 TXG id ，即记录文件系统提交所属事务组的严格递增序号。
3. ZFS 不存在 reflink 之类的机制，从而在某个时间点删除掉的数据块，不可能在比它更后面的快照中「复活」。

第三点关于 reflink 造成的数据复活现象可能需要解释一下，比如在（支持 reflink 的） btrfs 中有如下操作：

btrfs subvolume snapshot -r fs s1
rm fs/somefile
btrfs subvolume snapshot -r fs s2
cp --reflink=always s1/somefile fs/somefile
btrfs subvolume snapshot -r fs s3

我们对 fs 创建了 s1 快照，删除了 fs 中某个文件，创建了 s2 快照，然后用 reflink 把刚刚删除的文件从 s1 中复制出来，再创建 s3 。如此操作之后，按时间顺序有 s1、s2、s3 三个快照：

其中只有 s2 不存在 somefile ，而 s1 、 s3 和当前的 fs 都有，并且都引用到了同一个数据块。 于是从时间线来看， somefile 的数据块在 s2 中「死掉」了，又在 s3 中「复活」了。

而 ZFS (目前还）不支持 reflink ，所以没法像这样让数据块复活。一旦某个数据块在某个快照中「死」了， 就意味着它在随后的所有快照中都不再被引用到了。

ZFS 的快照具有的上述三点条件，使得 ZFS 的快照删除算法可以基于 birth time 。回顾上面 ZFS 的块指针 中讲到， ZFS 的每个块指针都有一个 birth txg 属性，记录这个块诞生时 pool 所在的 txg 。于是可以根据这个 birth txg 找到快照所引用的「独占」数据块然后释放掉它们。

具体来说，🐢乌龟算法可以这样删除一个快照：

1. 在 DSL 层找出要删除的快照（我们叫他 s ），它的前一个快照（叫它 ps ），后一个快照（叫它 ns ），分别有各自的 birth txg 叫 s.birth, ps.birth, ns.birth 。
2. 遍历 s 的 DMU 对象集指针所引出的所有块指针。 这里所有块指针在逻辑上构成一个由块指针组成的树状结构，可以有间接块组成的指针树，可以有对象集的 dnode 保存的块指针，这些都可以看作是树状结构的中间节点。
   1. 每个树节点的指针 bp，考察如果 bp.birth <= ps.birth ，那么这个指针和其下所有指针都还被前一个快照引用着，需要保留这个 bp 引出的整个子树。
   2. 按定义 bp.birth 不可能 > s.birth 。
   3. 对所有满足 ps.birth < bp.birtu <= s.birth 的 bp ，需要去遍历 ns 的相应块指针（同样文件的同样偏移位置），看是否还在引用 bp 。
      • 如果存在，继续递归往下考察树状结构中 bp 的所有子节点指针。因为可能共享了这个 bp 但 CoW 了新的子节点。
      • 如果不存在，说明下一个快照中已经删了 bp 。这时可以确定地说 bp 是 s 的「独占」数据块。
3. 释放掉所有找到的 s 所「独占」的数据块。

上述算法的一些边角情况可以自然地处理，比如没有后一个快照时使用当前数据集的写入点， 没有前一个快照时那么不被后一个快照引用的数据块都是当前要删除快照的独占数据块。

分析一下乌龟算法的复杂度的话，算法需要分两次，读 s 和 ns 中引用到的所有 ps 之后创建的数据块的指针，重要的是这些读都是在整个文件系统范围内的随机读操作，所以速度非常慢……

🐰兔子算法：死亡列表算法（ZFS早期）

可以粗略地认为🐢乌龟算法算是用 birth txg 优化代码路径的 GC 算法，利用了一部分元数据中的 birth txg 信息来避免扫描所有元数据，但是概念上仍然是在扫描元数据找出快照的独占数据块， 而非记录和跟踪快照的数据块，在最坏的情况下仍然可能需要扫描几乎所有元数据。

🐰兔子算法基于🐢乌龟算法的基本原理，在它基础上跟踪快照所引用数据块的一些信息， 从而很大程度上避免了扫描元数据的开销。ZFS 在早期使用这个算法跟踪数据集和快照引用数据块的情况。

🐰兔子算法为每个数据集（文件系统或快照）增加了一个数据结构，叫死亡列表（dead list）， 记录 前一个快照中还活着，而当前数据集中死掉了的数据块指针 ，换句话说就是在本数据集中「杀掉」的数据块。举例画图大概是这样

上图中有三个快照和一个文件系统，共 4 个数据集。每个数据集维护自己的死亡列表， 死亡列表中是那些在该数据集中被删掉的数据块。于是🐰兔子算法把🐢乌龟算法所做的操作分成了两部分， 一部分在文件系统删除数据时记录死亡列表，另一部分在删除快照时根据死亡列表释放需要释放的块。

在当前文件系统删除数据块（不再被当前文件系统引用）时，负责比对 birth txg 维护当前文件系统的死亡列表。每删除一个数据块，指针为 bp 时，判断 bp.birth 和文件系统最新的快照（上图为 s3）的 birth：

• bp.birth <= s3.birth： 说明 bp 被 s3 引用，于是将 bp 加入 fs1 的 deadlist
• bp.birth > s3.birth：说明 bp 指向的数据块诞生于 s3 之后，可以直接释放 bp 指向的块。

创建新快照时，将当前文件系统（图中 fs1）的死亡列表交给快照，文件系统可以初始化一个空列表。

删除快照时，我们有被删除的快照 s 和前一个快照 ps 、后一个快照 ns ，需要读入当前快照 s 和后一个快照 ns 的死亡列表：

1. 对 s.deadlist 中的每个指针 bp
   • 复制 bp 到 ns.deadlist
2. 对 ns.deadlist 中的每个指针 bp （其中包含了上一步复制来的）
   • 如果 bp.birth > ps.birth ，释放 bp 的空间
   • 否则保留 bp

换个说法的话， 死亡列表记录的是每个数据集需要负责删除，但因为之前的快照还引用着所以不能删除的数据块列表 。从当前文件系统中删除一个数据块时，这个职责最初落在当前文件系统身上，随后跟着创建新快照职责被转移到新快照上。 每个负责的数据集根据数据块的出生时间是否早于之前一个快照来判断现在是否能立刻释放该块， 删除一个快照时则重新评估自己负责的和下一个快照负责的数据块的出生时间。

从所做的事情来看，🐰兔子算法并没有比🐢乌龟算法少做很多事情。🐢乌龟算法删除一个快照， 需要遍历当前快照和后一个快照两组数据块指针中，新写入的部分； 🐰兔子算法则需要遍历当前快照和后一个快照两个死亡列表中，新删除的块指针。 但是实际🐰兔子算法能比🐢乌龟算法快不少，因为维护死亡列表的操作只在文件系统删除数据时和删除快照时， 顺序写入，并且删除快照时也只需要顺序读取死亡列表。在磁盘这种块设备上，顺序访问能比随机访问有数量级的差异。

不过记录死亡列表也有一定存储开销。最差情况下，比如把文件系统写满之后，创建一个快照， 再把所有数据都删掉，此时文件系统引用的所有数据块的块指针都要保存在文件系统的死亡列表中。 按 ZFS 默认的 128KiB 数据块大小，每块需要 128 字节的块指针，存储这些死亡列表所需开销可能要 整个文件系统大小的 1/1024 。如果用 4KiB 的数据块大小，所需开销则是 1/32 ， 1TiB 的盘会有 32GiB 拿来存放这些块指针，将高于用位图数组所需的存储量。

🐆豹子算法：死亡列表的子列表

🐆豹子算法是 ZFS 后来在 2009 年左右实现的算法。在🐰兔子算法中就可以看到，每次删除快照操作死亡列表的时候， 都需要扫描死亡列表中的块指针，根据指针中记录的 birth txg 做判断是否能直接释放或是需要保留到另一个快照的死亡列表。 于是🐆豹子算法的思路是，在死亡列表中记录块指针时，就把其中的块指针按 birth txg 分成子列表（sublist）。

比如上面🐰兔子算法中那4个死亡列表，可以这样拆成子列表：

这样拆成子列表之后，每次从死亡列表中释放数据块都能根据出生时间找到对应的子列表， 然后连续释放整个子列表。每次合并死亡列表时，也能直接用单链表穿起需要合并的子列表，不需要复制块指针。

死亡列表并不在跟踪快照的独占大小，而是在跟踪快照所需负责删除的数据块大小， 从这个数值可以推算出快照的独占大小之类的信息。 有了按出生时间排列的死亡列表子列表之后，事实上给任何一个出生时间到死亡时间的范围， 都可以找出对应的几个子列表，从而根据子列表的大小可以快速计算出每个快照范围的「独占」数据块、 「共享」数据块等大小，这不光在删除快照时很有用，也可以用来根据大小估算 zfs send 或者别的基于快照操作时需要的时间。

从直觉上理解，虽然 ZFS 没有直接记录每个数据块属于哪个数据集，但是 ZFS 跟踪记录了每个数据块的归属信息，也就是说由哪个数据集负责释放这个数据块。 在文件系统中删除数据块或者快照时，这个归属信息跟着共享数据块转移到别的快照中，直到最终被释放掉。

生存日志：ZFS 如何管理克隆的空间占用

Fast Clone Deletion by Sara Hartse

以上三种算法负责在 ZFS 中跟踪快照的空间占用，它们都基于数据块的诞生时间，所以都假设 ZFS 中对数据块的分配是位于连续的快照时间轴上。但是明显 ZFS 除了快照和文件系统， 还有另一种数据集可能分配数据块，那就是 克隆 ，于是还需要在克隆中使用不同的算法单独管理因克隆而分配的数据块。 OpenZFS Summit 2017 有个演讲 Fast Clone Deletion by Sara Hartse 解释了其中的细节。

首先克隆的存在本身会锁住克隆引用到的快照，不能删除这些被依赖的快照， 所以克隆无须担心靠快照共享的数据块的管理问题。因此克隆需要管理的，是从快照分离之后， 新创建的数据块。

和🐢乌龟算法一样，原理上删除克隆的时候可以遍历克隆引用的整个 DMU 对象集，找出其中晚于快照的诞生时间的数据块，然后释放它们。也和🐢乌龟算法一样， 这样扫描整个对象集的开销很大，所以使用一个列表来记录数据块指针。 克隆管理新数据块的思路和快照的🐰兔子算法维持死亡列表的思路相反， 记录所有新诞生的数据块，这个列表叫做「生存日志（livelist）」。

克隆不光要记录新数据块的诞生，还要记录新数据块可能的死亡，所以磁盘上保存的生存日志虽然叫 livelist ，但不像死亡列表那样是列表的形式，而是日志的形式，而内存中保存的生存日志则组织成了棵 自平衡树（AVLTree） 来加速查找。

磁盘上存储的生存日志如上图，每个表项记录它是分配（A）或者删除（F）一个数据块，同时记录数据块的地址。 这些记录在一般情况下直接记录在日志末尾，随着对克隆的写入操作而不断增长，长到一定程度则从内存中的 AVL Tree 直接输出一个新的生存日志替代掉旧的，合并其中对应的分配和删除操作。

生存日志可以无限增长，从而要将整个生存列表载入内存也有不小的开销，这里的解决方案有点像快照管理中用 🐆豹子算法改进🐰兔子算法的思路，把一个克隆的整个生存日志也按照数据块的诞生时间拆分成子列表。 Sara Hartse 的演讲 Fast Clone Deletion 中继续解释了其中的细节和优化方案，感兴趣的可以看看。

3.4   btrfs 的空间跟踪算法：引用计数与反向引用

理解了 ZFS 中根据 birth txg 管理快照和克隆的算法之后，可以发现它们基于的假设难以用于 WAFL 和 btrfs 。 ZFS 严格区分文件系统、快照、克隆，并且不存在 reflink ，从而可以用 birth txg 判断数据块是否需要保留，而 WAFL 和 btrfs 中不存在 ZFS 的那些数据集分工，又想支持 reflink ，可见单纯基于 birth txg 不足以管理 WAFL 和 btrfs 子卷。

让我们回到一开始日志结构文件系统中基于垃圾回收（GC）的思路上来，作为程序员来看， 当垃圾回收的性能不足以满足当前需要时，大概很自然地会想到：引用计数（reference counting）。 编程语言中用引用计数作为内存管理策略的缺陷是：强引用不能成环， 这在文件系统中看起来不是很严重的问题，文件系统总体上看是个树状结构，或者就算有共享的数据也是个 上下层级分明的有向图，很少会使用成环的指针，以及文件系统记录指针的时候也都会区分指针的类型， 根据指针类型可以分出强弱引用。

write fs/file1
cp --reflink=always fs/file1 fs/file2
btrfs subvolume snapshot fs sn1
btrfs subvolume snapshot fs sn2
rm fs/file2

4.1   ZFS 是如何实现 dedup 的？

ZFS 是在 Sun/OpenSolaris 寿命相当晚期的 2009 年获得的 dedup 功能，就在 Oracle 收购 Sun ，OpenSolaris 分裂出 Illumos 从而 ZFS 分裂出 Oracle ZFS 和 OpenZFS 的时间点之前。因此 关于 ZFS dedup 如何实现的文档相对匮乏 ，大部分介绍 ZFS 的文档或者教程会讲到 ZFS dedup 的用法，但是对 dedup 的实现细节、性能影响、乃至使用场景之类的话题就很少提了（甚至很多教程讲了一堆用法之后说类似， 「我评估之后觉得我不需要开 dedup ，你可以自己评估一下」这样的建议）。

OpenZFS Summit 2017 上 Matt 有个演讲，主要内容关于今后如何改进 dedup 性能的计划，其中讲到的计划还没有被具体实现，不过可以窥探一下 dedup 现在在 ZFS 中是如何工作的。 Chris 的博客也有两篇文章《 What I can see about how ZFS deduplication seems to work on disk 》和《 An important addition to how ZFS deduplication works on the disk 》介绍了他对此的认识，在这里我也尝试来总结一下 ZFS dedup 特性如何工作。

ZFS dedup 是存储池级别（pool-wide）开关的特性，所以大概在 MOS 之类的地方有存储一个特殊的数据结构， 叫 DeDup Table 简称 DDT 。DDT 目前是存储设备上的一个 hash table ，因为是存储池级别的元数据， 所以在 ZFS 中存储了三份完全一样的 DDT ，DDT 的内容是大概如下结构：

DDT 中对每个数据块存有3个东西：数据块的 checksum 、DVA （就是 ZFS 的块指针 中的 DVA）和引用计数。在存储池开启 dedup 特性之后，每次新写入一个数据块，都会先计算出数据块的 checksum ，然后查找 DDT ，存在的话增加 DDT 条目的引用计数，不存在的话插入 DDT 条目。每次释放一个数据块，同样需要查找 DDT 调整引用计数。

除了 DDT 之外，文件系统中记录的块指针中也有个特殊标志位记录这个块是否经过了 DDT 。读取数据不需要经过 DDT ，但是子卷、克隆或者文件系统正常删除数据块的时候， 需要根据块指针中的标志位判断是否需要检查和调整 DDT 。

从而关于 dedup 的实现可以得知以下一些特点：

• 开启 dedup 之后，每个写入操作放大成 3+1 个随机位置的写入操作，每个删除操作变成 1 个写入操作。没有 dedup 时删除块并不需要立刻写入，只需要记录在内存中并在 MOS 提交的时候调整磁盘占用情况即可。
• 只有开启 dedup 期间写入的数据块才会参与 dedup 。对已经有数据的存储池，后来开启的 dedup 不会影响已经写好的数据，从而即使后来新的写入与之前的写入有重复也得不到 dedup 效果。 DDT 中没有记录的数据块不会参与 dedup 。换句话说 DDT 中那些引用计数为 1 的记录也是必须存在的，否则这些数据块没有机会参与 dedup 。
• 关闭 dedup 之后，只要 DDT 中还存有数据，那么对这些数据的删除操作仍然有性能影响。

从直觉上可以这样理解：在 ZFS 中每个数据块都有其「归属」，没有 dedup 的时候，数据块归属于某个数据集（文件系统、快照、克隆）， 该数据集需要负责释放该数据块或者把从属信息转移到别的数据集（快照）上。 而在开启 dedup 期间，产生的写入的数据块实际归属于 DDT 而不是任何一个数据集，数据集需要查询和调整 DDT 中记录的引用计数来决定是否能释放数据块。

乍看起来 DDT 貌似挺像 btrfs 的 EXTENT_TREE ，但是本质上 EXTENT_TREE 是根据区块地址排序的， 而 DDT 因为是个 hashtable 所以是根据 checksum 排序的。并且 EXTENT_TREE 中记录的区块可以是任意大小，而 DDT 中记录的数据块是固定大小的，所以碎片不严重的情况下 DDT 要比 EXTENT_TREE 多记录很多数据块。这些区别都非常影响操作 DDT 时的性能。

DDT 本身是个 DMU 对象，所以对 DDT 的读写也是经过 DMU 的 CoW 读写，从而也经过 ARC 的缓存。想要有比较合理的 dedup 性能，需要整个 DDT 都尽量保持在内存 ARC 或者 L2ARC 缓存中， 于是 dedup 特性也有了非常占用内存的特点。每个 DDT 表项需要大概 192 字节来描述一个（ 默认 128KiB 大小的）数据块，由此可以估算一下平均每 2TiB 的数据需要 3GiB 的内存来支持 dedup 的功能。

Matt 的视频中后面讲到优化 ZFS dedup 的一些思路，大体上未来 ZFS 可以做这些优化：

1. DDT 在内存中仍然是 hashtable ，在存储介质上则换成类似 ZIL 的日志结构，让 DDT 尽量保持在内存中，并且绕过 DMU 减少写入放大。
2. 给 DDT 表项瘦身，从192字节缩减到接近64字节。
3. 当遇到内存压力时，从 DDT 中随机剔除掉引用计数为 1 的表项。被剔除的表项没有了未来参与 dedup 的可能性，但是能减轻内存压力。剔除引用计数为 1 的表项仍然可以维持数据块的归属信息（ 处理上当作是没有 dedup 的形式），但是引用计数更高的表项没法剔除。

这些优化策略目的是想让 dedup 的性能损失能让更多使用场景接受。不过因为缺乏开发者意愿， 目前这些策略还只是计划，没有实现在 ZFS 的代码中。

因为以上特点， ZFS 目前 dedup 特性的适用场景极为有限，只有在 IO 带宽、内存大小都非常充裕， 并且可以预见到很多重复的数据的时候适合。听说过的 ZFS dedup 的成功案例是，比如提供虚拟机服务的服务商，在宿主文件系统上用 ZFS 的 zvol 寄宿虚拟机的磁盘镜像，客户在虚拟机内使用其它文件系统。大部分客户可能用类似版本的操作系统， 从而宿主机整体来看有很多 dedup 的潜质。不过这种应用场景下，服务商很可能偏向选择 CephFS 这样的分布式文件系统提供虚拟机镜像存储，而不是 ZFS 这样局限在单系统上的本地文件系统。

4.2   btrfs 的 dedup

btrfs 目前没有内建的 dedup 支持，但是因为有 reflink 所以可以通过第三方工具在事后扫描文件块来实现 dedup 。这一点乍看像是某种将就之策，实际上了解了 ZFS dedup 的实现之后可以看出这个状况其实更灵活。

在 btrfs 中实现 in-band dedup 本身不算很复杂，增加一个内存中的 bloom filter 然后按情况插入 reflink 的正常思路就够了。在 btrfs kernel wiki 中有篇笔记 提到已经有了实验性的 in-band dedup 内核支持的实现。这个实现已经越来越成熟，虽然还有诸多使用限制， 不过实现正确性上问题不大，迟迟没有办法合并进主线内核的原因更多是性能上的问题。

如果 btrfs 有了 in-band dedup 这样系统性的 dedup 方案，那么不可避免地会增加文件系统中使用 reflink 的数量。这将会暴露出 backref walking 这样的基础设施中许多潜在的边角情况下的性能瓶颈。 前面解释过 backref walking 操作是个挺大开销的操作，并且开销随着快照和 reflink 的使用而爆炸式增长。直到最近的 btrfs 更新仍然在试图优化和改善现有 backref walking 的性能问题，可以预测 btrfs 的内建 dedup 支持将需要等待这方面更加成熟。