FSCK和日志

1 崩溃一致性

正如我们到目前为止所看到的，文件系统管理一组数据结构来实现预期的抽象：文件、目录以及支持我们期望从文件系统获得的基本抽象所需的所有其他元数据。与大多数数据结构（例如，在正在运行的程序的内存中找到的数据结构）不同，文件系统数据结构必须持久存在，即它们必须长期存在，存储在即使断电也能保留数据的设备上（例如硬盘或基于闪存的 SSD）。

文件系统面临的一项主要挑战是如何在断电或系统崩溃的情况下更新持久数据结构。具体来说，如果在更新磁盘结构的过程中，有人被电源线绊倒并且机器断电，会发生什么情况？或者操作系统遇到bug而崩溃？由于断电和崩溃，更新持久数据结构可能非常棘手，并导致文件系统实现中出现一个新的有趣问题，称为崩溃一致性问题。

这个问题很容易理解。想象一下，您必须更新两个磁盘上的结构 A 和 B，才能完成特定操作。由于磁盘一次仅服务一个请求，因此这些请求之一将首先到达磁盘（A 或 B）。如果系统在一次写入完成后崩溃或断电，磁盘上的结构将处于不一致的状态。因此，我们有一个所有文件系统都需要解决的关键问题：

如何在崩溃的情况下更新磁盘？系统可能会崩溃或在任意两次写入之间断电，因此磁盘上的状态可能只会部分更新。崩溃后，系统启动并希望再次挂载文件系统（以便访问文件等）。鉴于崩溃可能在任意时间点发生，我们如何确保文件系统将磁盘映像保持在合理的状态？

在本章中，我们将更详细地描述这个问题，并了解文件系统用来克服它的一些方法。我们将首先检查旧文件系统所采用的方法，称为 fsck 或文件系统检查器。然后，我们将注意力转向另一种方法，称为日志记录（也称为预写日志记录），这种技术会为每次写入增加一点开销，但可以更快地从崩溃或断电中恢复。我们将讨论日志记录的基本机制，包括 Linux ext3（一种相对现代的日志文件系统）实现的几种不同风格的日志记录。

2 详细示例

2.1 基本介绍

为了开始我们对日志的研究，让我们来看一个例子。我们需要使用以某种方式更新磁盘结构的工作负载。假设工作负载很简单：向现有文件追加一个数据块。追加的方法是打开文件，调用 lseek() 将文件偏移量移动到文件末尾，然后在关闭文件之前向文件写入一个 4KB 的数据块。

我们还假设磁盘上使用的是标准的简单文件系统结构，类似于我们以前见过的文件系统。这个小例子包括一个 inode 位图（只有 8 位，每个 inode 一个）、一个数据位图（也是 8 位，每个数据块一个）、inodes（共 8 个，编号 0 至 7，分布在 4 个块中）和数据块（共 8 个，编号 0 至 7）。下面是该文件系统的示意图：

观察图片中的结构，可以看到一个已分配的 inode（inode number 2）和一个已分配的数据块（数据块 4），前者已在 inode 位图中标记，后者也在数据位图中标记。该 inode 被标记为 I[v1]，因为它是该 inode 的第一个版本；它将很快被更新（由于上述工作负载）。让我们也来看看这个简化的 inode 内部。在 I[v1] 中，我们可以看到：

1
2
3
4
5
6
7

owner 		: remzi
permissions : read-write
size 		: 1
pointer 	: 4
pointer 	: null
pointer 	: null
pointer 	: null

在这个简化的 inode 中，文件的size为 1（分配了一个块），第一个直接指针指向块 4（文件的第一个数据块 Da），所有其他三个直接指针都设置为 null （表明它们没有被使用）。当然，真正的inode还有更多的字段。

当我们追加到文件时，我们向其中添加一个新的数据块，因此必须更新三个磁盘结构：inode（必须指向新块并记录由于追加而产生的新的较大大小）、新的数据块Db，以及新版本的数据位图（称为B[v2]）来指示新的数据块已经被分配。

因此，在系统内存中，我们必须将三个块写入磁盘。更新后的索引节点（inode版本 2，简称 I[v2]）现在如下所示：

为实现这一转换，文件系统必须向磁盘执行三次单独的写入操作，分别写入 inode (I[v2])、bitmap (B[v2]) 和数据块 (Db)。请注意，这些写入通常不会在用户发出 write() 系统调用时立即发生；相反，脏的 inode、位图和新数据会先在主内存（页面缓存或缓冲区缓存）中停留一段时间；然后，当文件系统最终决定将它们写入磁盘时（比如 5 秒或 30 秒后），文件系统会向磁盘发出必要的写入请求。

不幸的是，崩溃可能会发生，从而干扰对磁盘的更新。特别是，如果在写入其中一个或两个而不是全部三个之后发生崩溃，文件系统可能会处于一种奇怪的状态。

2.2 崩溃场景

为了更好地理解这个问题，让我们看一些崩溃场景的例子。想象一下只有一次写入成功；因此存在三种可能的结果，我们在此列出：

• 仅将数据块 (Db) 写入磁盘。

  在这种情况下，数据就在磁盘上，但没有指向它的 inode，也没有位图显示该数据块已分配。因此，写入就好像从未发生过一样。从文件系统崩溃一致性的角度来看，这种情况根本不是问题。

• 只有更新的 inode（I[v2]）被写入磁盘。

  在这种情况下，inode 指向 Db 即将被写入的磁盘地址 (5)，但 Db 尚未被写入。因此，如果我们相信该指针，就会从磁盘读取垃圾数据（磁盘地址 5 的旧内容）。

  此外，我们还遇到了一个新问题，我们称之为文件系统不一致。磁盘位图告诉我们，数据块 5 尚未分配，但 inode 却说它已经分配。位图和 inode 之间的不一致是文件系统数据结构的不一致；要使用文件系统，我们必须以某种方式解决这个问题。

• 只有更新后的位图（B[v2]）被写入磁盘。

  在这种情况下，位图显示块 5 已分配，但却没有指向它的 inode。因此，文件系统再次出现不一致；如果不加以解决，这次写入将导致空间泄漏，因为文件系统永远不会使用块 5。

在尝试向磁盘写入三个数据块的过程中，还有三种崩溃情况。在这些情况中，两次写入成功，最后一次写入失败：

• inode (I[v2]) 和 bitmap (B[v2]) 被写入磁盘，但数据 (Db) 未被写入。

  在这种情况下，文件系统元数据是完全一致的：inode 有一个指向块 5 的指针，位图显示 5 正在使用中，因此从文件系统元数据的角度看一切正常。但有一个问题：5 中又出现了垃圾。

• 写入了 inode (I[v2]) 和数据块 (Db)，但没有写入位图 (B[v2])。在这种情况下，我们的 inode 指向了磁盘上的正确数据，但 inode 和旧版本的位图 (B1) 之间再次出现不一致。因此，我们再次需要在使用文件系统前解决这个问题。

• 位图 (B[v2]) 和数据块 (Db) 被写入，但 inode (I[v2]) 却没有被写入。在这种情况下，我们又遇到了 inode 和数据位图不一致的问题。然而，尽管块已被写入，位图也显示了它的使用情况，我们却不知道它属于哪个文件，因为没有 inode 指向该文件。

2.3 崩溃一致性问题

希望从这些崩溃场景中，你能看到磁盘上的文件系统映像因崩溃而可能出现的诸多问题：文件系统数据结构不一致；空间泄漏；向用户返回垃圾数据等等。理想情况下，我们希望将文件系统从一种一致的状态（例如，在文件被附加之前）原子地移动到另一种一致的状态（例如，在将 inode、位图和新数据块写入磁盘之后）。遗憾的是，我们无法轻易做到这一点，因为磁盘每次只提交一次写入，而在这些更新之间可能会发生崩溃或断电。我们将这一普遍问题称为崩溃一致性问题（也可称为一致性更新问题）。

3 解决方案#1：文件系统检查器

早期的文件系统采用一种简单的方法来解决崩溃一致性问题。基本上，它们决定任由不一致性发生，然后稍后（重启时）再修复它们。fsck就是这种懒惰方法的典型例子，它是一种 UNIX 工具，用于查找和修复此类不一致性；不同系统上也有类似的工具用于检查和修复磁盘分区。需要注意的是，这种方法并不能解决所有问题；例如，考虑上述文件系统看起来一致，但 inode 指向垃圾数据的情况。唯一真正的目标是确保文件系统元数据的内部一致性。

正如 McKusick 和 Kowalski 的论文所总结的，fsck 工具的运行分为几个阶段。它在文件系统挂载和可用之前运行（fsck 假设运行时没有其他文件系统活动）；一旦完成，磁盘上的文件系统应该是一致的，因此可以让用户访问。以下是 fsck 工作的基本概要：

• 超级块：fsck 首先检查超级块看起来是否合理，主要是进行健全性检查，如确保文件系统大小大于已分配的块数。这些健全性检查的目的通常是发现可疑（损坏）的超级块；在这种情况下，系统（或管理员）可能会决定使用超级块的替代副本。
• 空闲块：接下来，fsck 会扫描 inodes、间接块、双间接块等，以了解文件系统中当前分配的块。它利用这些知识生成正确版本的分配位图；因此，如果位图和 inodes 之间有任何不一致，可以通过信任 inodes 中的信息来解决。对所有 inodes 执行相同类型的检查，确保所有看起来正在使用的 inodes 都在 inode 位图中标记为正在使用。
• Inode状态：检查每个 inode 是否损坏或存在其他问题。例如，fsck 会确保每个已分配的 inode 都有一个有效的类型字段（如常规文件、目录、符号链接等）。如果 inode 字段存在不易修复的问题，该 inode 就会被视为可疑，并被 fsck 清除；inode 位图也会相应更新。
• Inode 链接：fsck 还会验证每个已分配 inode 的链接计数。链接计数表示包含对该特定文件的引用（即链接）的不同目录的数量。为了验证链接计数，fsck 会从根目录开始扫描整个目录树，并为文件系统中的每个文件和目录建立自己的链接计数。如果新计算的链接数与某个 inode 中的链接数不匹配，就必须采取纠正措施，通常是修复 inode 中的链接数。如果发现一个已分配的 inode，但没有目录指向它，它就会被移到lost+found目录</。
• 重复：fsck 还会检查重复指针，即两个不同的 inode 指向同一块的情况。如果其中一个 inode 明显有问题，可能会被清除。或者，可以复制指向的块，从而根据需要给每个 inode 提供自己的副本。
• 坏块：在扫描所有指针列表时，还会对坏块指针进行检查。如果一个指针明显指向超出其有效范围的内容，例如，它的地址指向的块大于分区大小，那么这个指针就被认为是 “坏的”。在这种情况下，fsck 不会做任何太聪明的事情；它只是从 inode 或间接块中删除（清除）指针。
• 目录检查：fsck 无法理解用户文件的内容；但目录中包含文件系统本身创建的特定格式化信息。因此，fsck 会对每个目录的内容执行额外的完整性检查，确保". “和”.. “是第一个条目，目录条目中引用的每个 inode 都已分配，并确保在整个层次结构中，没有任何目录被链接超过一次。

如你所见，构建一个有效的 fsck 需要复杂的文件系统知识；要确保这样一段代码在所有情况下都能正确运行，是一项挑战。然而，fsck（以及类似方法）还有一个更大、也许更根本的问题：它们太慢了。在磁盘容量非常大的情况下，扫描整个磁盘以找到所有已分配块并读取整个目录树可能需要数分钟或数小时。随着磁盘容量的增加和 RAID 的普及，fsck 的性能变得令人望而却步。

从更高层次来看，fsck 的基本前提似乎有点不合理。想想我们上面的例子，只有三个数据块被写入磁盘；要扫描整个磁盘来修复在更新三个数据块时出现的问题，成本高得惊人。这种情况就好比你把钥匙掉在卧室的地板上，然后开始搜索整个房子的钥匙恢复算法，从地下室开始，逐个房间搜索。这样做虽然有效，但会造成浪费。因此，随着磁盘（和 RAID）的发展，研究人员和从业人员开始寻找其他解决方案。

4 解决方案#2：日志（或预写日志）

4.1 基本介绍

解决一致性更新问题的最流行的解决方案可能是从数据库管理系统领域窃取的一个想法。这种被称为预写日志的想法正是为了解决此类问题而发明的。在文件系统中，由于历史原因，我们通常将其称为预写日志记录。第一个做到这一点的文件系统是 Cedar，尽管许多现代文件系统都使用这个想法，包括 Linux ext3 和 ext4、reiserfs、IBM 的 JFS、SGI 的 XFS 和 Windows NTFS。

基本思路如下：更新磁盘时，在覆盖现有的结构之前，首先写下一个小注释（磁盘上其他某个众所周知的位置）描述您将要执行的操作。写这个注释是“预写”部分，我们将其写入我们组织为“日志”的结构中；因此，预写日志记录。

通过将注释写入磁盘，您可以保证如果在更新（覆盖）正在更新的结构期间发生崩溃，您可以返回并查看您所做的注释并重试；因此，您将确切地知道崩溃后要修复什么（以及如何修复），而不必扫描整个磁盘。根据设计，日志记录会在更新期间增加一些工作量，从而大大减少恢复期间所需的工作量。

现在我们将描述 Linux ext3（一种流行的日志文件系统）如何将日志合并到文件系统中。大多数磁盘结构与 Linux ext2 相同，例如，磁盘分为块组，每个块组包含 inode 位图、数据位图、inode 和数据块。新的关键结构是日志本身，它占用分区内或其他设备上的一些少量空间。因此，ext2 文件系统（没有日志）如下所示：

假设日志放置在同一个文件系统映像中（尽管有时它放置在单独的设备上，或者作为文件系统中的文件），带有日志的 ext3 文件系统如下所示：

真正的区别只是日志的存在，当然还有它的使用方式。

4.2 数据日志

让我们看一个简单的例子来了解数据日志的工作原理。数据日志是 Linux ext3 文件系统的一种模式，本文的大部分讨论都是基于这种模式。

假设我们再次进行典型更新，希望将 inode (I[v2])、位图 (B[v2]) 和数据块 (Db) 再次写入磁盘。在将它们写入最终磁盘位置之前，我们首先要将它们写入日志（又称日记）。这就是日志中的内容：

可以看到，我们在这里写入了 5 个块。事务开始（TxB）告诉我们这次更新的信息，包括文件系统待更新的信息（例如，块 I[v2]、B[v2]和 Db 的最终地址），以及某种事务标识符（TID）。中间三个块只包含块本身的确切内容；这被称为物理日志，因为我们将更新的确切物理内容写入日志（另一种想法是逻辑日志，将更新的逻辑表述更紧凑地写入日志，例如 “此更新希望将数据块 Db 附加到文件 X”，这有点复杂，但可以节省日志空间，也许还能提高性能）。最后一个数据块（TxE）是该事务结束的标记，也包含 TID。

一旦事务安全地存储在磁盘上，我们就可以覆盖文件系统中的旧结构；这个过程称为检查点。因此，为了对文件系统进行检查点（即使其与日志中的待定更新保持同步），我们按照上述方式将I[v2]、B[v2] 和 Db 写入到它们的磁盘位置；如果这些写入成功完成，我们就对文件系统进行了检查点，基本上就完成了。因此，我们的初始操作序列为：

1. 写日志：将事务写入日志，包括事务开始块、所有待处理的数据和元数据更新以及事务结束块；等待这些写入完成。
2. 检查点：将待处理的元数据和数据更新写入文件系统中的最终位置。

在我们的示例中，我们首先将 TxB、I[v2]、B[v2]、Db 和 TxE 写入日志。当这些写入完成后，我们将通过检查点 I[v2]、B[v2] 和 Db 到它们在磁盘上的最终位置来完成更新。

当写入日志期间发生崩溃时，事情会变得有点棘手。在这里，我们尝试将事务中的一组块（例如，TxB、I[v2]、B[v2]、Db、TxE）写入磁盘。一种简单的方法是一次发出每一个，等待每一个完成，然后发出下一个。然而，这很慢。理想情况下，我们希望一次发出所有五个块写入，因为这会将五个写入转换为单个顺序写入，从而速度更快。然而，这是不安全的，原因如下：给定如此大的写入，磁盘内部可能会执行调度并以任何顺序完成大写入的小片段。因此，磁盘内部可以 (1) 写入 TxB、I[v2]、B[v2] 和 TxE，并且仅在稍后 (2) 写入 Db。不幸的是，如果磁盘在 (1) 和 (2) 之间断电，磁盘上的结果如下：

强制写入磁盘

现代文件系统在强制两次磁盘写入之间保持顺序时需要额外的预防措施。过去，简单地等待第一次写入完成再进行第二次写入就足够了。然而，由于写入缓存的使用增加，这种方法不再有效。启用写入缓存后，磁盘可能会在将数据放置在内存缓存中后通知操作系统写入已完成，而不是立即将数据写入磁盘。这使得无法保证先前的写入在后续写入之前到达磁盘。

为了解决这个问题，一种解决方案是禁用写缓存，但这会影响性能。另一种现代方法是明确发出写屏障，确保在屏障之前发出的所有写入在屏障之后发出的任何写入之前到达磁盘。然而，最近的研究表明，一些磁盘制造商为了提高性能，可能会忽略写屏障请求，这可能导致错误操作。

为什么会有这个问题？这个事务看起来是一个有效的事务（它有一个开始和结束，序列号匹配）。此外，文件系统无法查看第四个数据块并知道它是错误的；毕竟，它是任意的用户数据。因此，如果系统现在重启并运行恢复，它就会重放此事务，并无知地将垃圾数据块”?? “的内容复制到 Db 应该存放的位置。这对文件中的任意用户数据来说是很糟糕的；如果发生在文件系统的关键部分，如超级块上，情况就更糟了，可能导致文件系统无法挂载。

优化日志写入

文件系统首先要写出事务开始块和事务内容；只有在这些写入完成后，文件系统才能将事务结束块发送到磁盘，这样写入日志的效率特别低，通常会产生额外的旋转（因为磁盘通常需要等待正确的扇区旋转到磁头下方才能进行写入操作）。

Linux ext4中则提供了这样一个方法：将事务写入日志时，在开始和结束块中包含日志内容的校验和。这样做使文件系统能够一次写入整个事务，而不会产生等待；如果在恢复期间，文件系统发现事务中计算的校验和与存储的校验和不匹配，则可以断定事务写入期间发生了崩溃，从而丢弃文件系统更新。因此，通过对写入协议和恢复系统进行小的调整，文件系统可以实现更快的常见情况性能；最重要的是，系统稍微更可靠，因为从日志中读取的任何内容现在都受到校验和的保护。

为避免这一问题，文件系统分两步进行事务写入。首先，文件系统将除 TxE 块外的所有块写入日志，并一次性完成这些写入操作。当这些写入完成后，日志将显示如下内容：

这些写入完成后，文件系统会发出 TxE 块的写入，从而使日志处于最终安全状态：

这个过程的一个重要方面是磁盘提供的原子性保证。事实证明，磁盘保证任何 512 字节的写入要么发生要么不发生（绝不会写一半）；因此，要确保 TxE 的写入是原子性的，就应该把它变成一个单一的 512 字节块。因此，我们目前更新文件系统的协议分为三个阶段：

1. 日志写入：将事务内容（包括 TxB、元数据和数据）写入日志；等待写入完成。
2. 日志提交：将事务提交块（包含 TxE）写入日志；等待写入完成；事务即被提交。
3. 检查点：将更新内容（元数据和数据）写入磁盘上的最终位置。

4.3 恢复

现在让我们了解文件系统如何使用日志的内容从崩溃中恢复。在此更新序列期间随时可能发生崩溃。

• 如果崩溃发生在事务安全写入日志之前（即，在上面的步骤 2 完成之前），那么我们的工作就很简单：只需跳过挂起的更新。
• 如果崩溃发生在事务提交到日志之后、检查点完成之前，文件系统可以按如下方式恢复更新。当系统启动时，文件系统恢复过程将扫描日志并查找已提交到磁盘的事务；因此，这些事务会被重放（按顺序），文件系统再次尝试将事务中的块写出到它们在磁盘上的最终位置。这种形式的日志记录是最简单的形式之一，称为重做日志。通过恢复日志中已提交的事务，文件系统确保磁盘上的结构是一致的，因此可以通过挂载文件系统并为新请求做好准备来继续进行。

请注意，在检查点期间的任何时候发生崩溃都是正常的，即使在对块的最终位置的一些更新已经完成之后也是如此。在最坏的情况下，其中一些更新只是在恢复期间再次执行。由于恢复是一种罕见的操作（仅在意外系统崩溃后发生），因此无需担心一些冗余写入。

4.4 批处理日志更新

您可能已经注意到，基本协议可能会增加大量额外的磁盘流量。例如，假设我们在同一目录中连续创建两个文件，分别称为 file1 和 file2。要创建一个文件，必须更新许多磁盘结构，至少包括：inode 位图（分配新的 inode）、文件新创建的 inode、包含新目录条目的的父目录的数据块和父目录 inode（现在有新的修改时间）。通过日志记录，我们在逻辑上将所有这些信息提交到我们创建的两个文件的日志中；因为这些文件位于同一目录中，并且假设它们甚至在同一 inode 块中具有 inode，这意味着如果我们不小心，我们最终将一遍又一遍地写入这些相同的块，即相同的目录数据块和 inode 可能会被重复写入，造成了额外的磁盘流量和性能开销。。

为了解决这个问题，某些文件系统不会一次将每个更新提交到磁盘（例如，Linux ext3）；相反，我们可以将所有更新缓冲到全局事务中。在上面的例子中，当创建两个文件时，文件系统只是将内存中的 inode 位图、文件的 inode、目录数据和目录 inode 标记为脏，并将它们添加到形成当前事务的块列表中。当最终将这些块写入磁盘时（例如，5 秒超时后），将提交包含上述所有更新的单个全局事务。因此，通过缓冲更新，文件系统在许多情况下可以避免过多的磁盘写入流量。

4.5 限制日志大小

因此，我们已经达成了更新磁盘上文件系统结构的基本协议。文件系统在内存中缓冲更新一段时间；当最终写入磁盘时，文件系统首先仔细地将事务的详细信息写入日志（也称为预写日志）；事务完成后，文件系统将这些块检查点到它们在磁盘上的最终位置。

然而，日志的大小是有限的。如果我们继续向其中添加事务（如下图所示），它很快就会填满。你认为接下来会发生什么？

日志满时会出现两个问题：

• 第一个问题比较简单，但不那么关键：日志越大，恢复所需的时间就越长，因为恢复过程必须（按顺序）重放日志中的所有事务才能恢复。
• 第二个问题更为严重：当日志已满（或接近满）时，就无法再向磁盘提交任何事务，从而使文件系统变得 “不那么有用”（即无用）。

为了解决这些问题，日志文件系统将日志视为循环数据结构，不断重复使用；这就是日志有时被称为循环日志的原因。为此，文件系统必须在检查点之后的一段时间内采取行动。具体来说，一旦事务被检查点化，文件系统就应释放日志中占用的空间，允许日志空间被重复使用。实现这一目的的方法有很多，例如，你可以简单地在日志超级块中标记日志中最旧和最新的非检查点事务，其他所有空间都是空闲的。下面是一个图表说明：

在日志超级块（不要与主文件系统超级块混淆）中，日志系统记录足够的信息以了解哪些事务尚未设置检查点，从而减少恢复时间并允许以循环方式重复使用日志。因此，我们在基本协议中添加了另一个步骤：

1. 日志写入：将事务内容（包含 TxB 和更新内容）写入日志，等待这些写入完成。
2. 日志提交：将事务提交块（包含TxE）写入日志，等待写入完成，事务现已提交。
3. 检查点：将更新内容写入文件系统中的最终位置。
4. 释放：一段时间后，通过更新日志超级块在日志中将事务标记为已释放。

这样我们就有了最终的数据日志协议。但仍然存在一个问题：我们将每个数据块写入磁盘两次，这是一个沉重的成本，特别是对于像系统崩溃这样罕见的情况。

4.6 元数据日志

尽管现在恢复速度很快（扫描日志并重放一些事务，而不是扫描整个磁盘），但文件系统的正常操作比我们期望的要慢。特别是，对于每次写入磁盘，我们现在也首先写入日志，从而使写入流量加倍；在顺序写入工作负载期间，这种加倍尤其令人痛苦，现在该工作负载将以驱动器峰值写入带宽的一半进行。此外，在写入日志和写入主文件系统之间，存在成本高昂的查找，这显着增加了某些工作负载的开销。

由于将每个数据块写入磁盘两次的成本很高，因此人们尝试了一些不同的方法来提高性能。例如，我们上面描述的日志模式通常称为数据日志（如在 Linux ext3 中），因为它记录所有用户数据（除了文件系统的元数据）。一种更简单（也更常见）的日志形式有时称为有序日志（或只是元数据日志），它几乎相同，只是用户数据不写入日志。因此，当执行与上述相同的更新时，以下信息将被写入日志：

之前写入日志的数据块 Db 将被写入文件系统本身，避免了额外的写入；考虑到磁盘的大部分 I/O 流量都是数据，不重复写入数据大大减少了日志的 I/O 负载。不过，这一修改确实提出了一个有趣的问题：我们应该在什么时候将数据块写入磁盘？

为了更好地理解这个问题，我们再来看看追加文件的例子。更新由三个数据块组成：I[v2]、B[v2] 和 Db。前两个块都是元数据，会被记录下来，然后进行检查点处理；后一个块只会被写入文件系统一次。我们应该何时将 Db 写入磁盘？这重要吗？

事实证明，对于纯元数据日志，数据写入的顺序确实很重要。例如，如果我们在事务（包含 I[v2] 和 B[v2]）完成后将 Db 写入磁盘，会怎样？不幸的是，这种方法存在一个问题：文件系统是一致的，但 I[v2] 最终可能指向垃圾数据。具体来说，考虑 I[v2] 和 B[v2] 已被写入，但 Db 未被写入磁盘的情况。这时文件系统会尝试恢复。由于 Db 不在日志中，文件系统将重放对 I[v2] 和 B[v2] 的写入，并生成一个一致的文件系统（从文件系统元数据的角度来看）。但是，I[v2] 将指向垃圾数据，即 Db 所在槽中的任何数据。

为了确保这种情况不会发生，一些文件系统（如 Linux ext3）会在将相关元数据写入磁盘之前，先将数据块（常规文件）写入磁盘。

具体来说，协议如下：

1. 数据写入：将数据写入最终位置，等待完成（等待是可选的，详见下文）。
2. 日志元数据写入：将起始块和元数据写入日志，等待写入完成。
3. 日志提交：将事务提交块（包含 TxE）写入日志，等待写入完成，事务（包括数据）现已提交。
4. 检查点元数据：将元数据更新内容写入文件系统中的最终位置。
5. 释放：之后，在日志超级块中标记事务释放。

通过强制先写入数据，文件系统可以保证指针永远不会指向垃圾文件。事实上，"先写被指向对象，再写指向该对象的对象 “这一规则是崩溃一致性的核心，其他崩溃一致性方案也进一步利用了这一规则（详见下文）。

在大多数系统中，元数据日志（类似于 ext3 的有序日志）比完整数据日志更受欢迎。例如，Windows NTFS 和 SGI 的 XFS 都使用某种形式的元数据日志。 Linux ext3 允许您选择数据、有序或无序模式（在无序模式下，可以随时写入数据）。所有这些模式都保持元数据一致；它们的数据语义各不相同。

最后，请注意，如上述协议所示，在向日志发出写入（步骤 2）之前强制完成数据写入（步骤 1）并不是正确性所必需的。具体来说，最好同时对数据、事务开始块和日志元数据进行写入；唯一真正的要求是步骤 1 和 2 在发布日志提交块（步骤 3）之前完成。

4.7 棘手的情况：块重用

有一些有趣的情况会让日志记录变得更加棘手，因此值得讨论。其中许多情况都与块重用有关；正如Stephen Tweedie（ext3 的主要幕后推手之一）所说：

“整个系统最可怕的部分是什么？是删除文件。与删除有关的一切都令人毛骨悚然。所有与删除有关的事情……都会让你做噩梦，因为如果块被删除，然后重新分配，会发生什么？

Tweedie给出的具体例子如下。假设你正在使用某种形式的元数据日志（因此文件的数据块没有日志）。假设有一个名为 foo 的目录。用户向 foo 添加条目（比如创建文件），因此 foo 的内容（因为目录被视为元数据）被写入日志；假设 foo 目录数据的位置是块 1000。日志内容如下

此时，用户删除目录中的所有内容以及目录本身，从而释放块 1000 以供重复使用。最后，用户创建一个新文件（例如 foobar），最终会重用曾经属于 foo 的相同块（1000）。 foobar 的 inode 及其数据都提交到磁盘；但请注意，由于正在使用元数据日志，因此只有 foobar 的 inode 会提交到日志；文件 foobar 中块 1000 中新写入的数据未记录。

现在假设发生了崩溃，并且所有这些信息仍在日志中。在重放期间，恢复过程只是重放日志中的所有内容，包括块 1000 中目录数据的写入；因此，重访会用旧目录内容覆盖当前文件 foobar 的用户数据！显然这不是一个正确的恢复操作，并且当用户读取文件 foobar 时肯定会感到惊讶。

对于这个问题有多种解决方案。例如，人们可以永远不会重用块，直到从日志中检查到删除所述块为止。 Linux ext3 所做的是向日志添加一种新类型的记录，称为撤销记录。在上述情况下，删除目录将导致撤销记录写入日志。重放日志时，系统首先扫描此类撤销记录；任何此类撤销的数据都不会被重放，从而避免了上述问题。

4.8 总结日记：时间轴

在结束对日志的讨论之前，我们用时间轴总结一下我们讨论过的协议。上图显示了记录数据和元数据时的协议，而下图显示了只记录元数据时的协议。

在每个图中，时间都是向下递增的，图中的每一行都显示了可以发出或可能完成写入的逻辑时间。例如，在数据日志协议（第一张图）中，事务开始块（TxB）的写入和事务内容的写入在逻辑上可以同时发出，因此可以按任意顺序完成；但事务结束块（TxE）的写入必须在前述写入完成后才能发出。同样，在事务结束块提交之前，也不能开始对数据和元数据块进行检查点写入。水平虚线表示必须遵守写入排序要求的位置。

元数据日志协议也有类似的时间轴。请注意，数据写入在逻辑上可以与事务开始和日志内容的写入同时发出，但必须在事务结束发出前发出并完成。

最后要注意的是，时间轴中标记的每次写入的完成时间是任意的。在实际系统中，完成时间由 I/O 子系统决定，它可能会重新安排写入顺序以提高性能。我们对排序的唯一保证是协议正确性所必须执行的（如图中的水平虚线所示）。

5 解决方案#3：其他方法

到目前为止，我们已经描述了保持文件系统元数据一致性的两种方法：

• 基于 fsck 的惰性方法
• 日志记录的更主动的方法。

然而，这些并不是唯一的两种方法。 Ganger 和 Patt 提出了一种这样的方法，称为软更新。这种方法仔细地对文件系统的所有写入进行排序，以确保磁盘上的结构永远不会处于不一致的状态。例如，通过在指向它的inode之前将一个指向的数据块写入磁盘，我们可以确保该inode永远不会指向垃圾；对于文件系统的所有结构都可以导出类似的规则。然而，实施软更新可能是一个挑战；虽然上述日志层可以在对确切文件系统结构相对较少的了解的情况下实现，但软更新需要对每个文件系统数据结构的复杂了解，从而给系统增加了相当多的复杂性。

另一种方法称为写时复制（COW），并在许多流行的文件系统中使用，包括 Sun 的 ZFS。此技术永远不会覆盖原位的文件或目录；相反，它将新的更新放置到磁盘上以前未使用的位置。完成多次更新后，COW 文件系统会翻转文件系统的根结构以包含指向新更新的结构的指针。

COW 技术的一个重要优点是它使得保持文件系统的一致性变得更加简单。由于原始数据没有被直接修改，因此不需要复杂的同步或回滚机制来维护一致性，而是通过简单地修改指向新数据的指针来实现。

另一种方法是名为基于反向指针的一致性（backpointer-based consistency, BBC）的技术中，写入之间不强制执行任何顺序。为了实现一致性，系统中的每个块都添加了一个额外的反向指针；例如，每个数据块都有对其所属inode的引用。当访问文件时，文件系统可以通过检查前向指针（例如，inode 或直接块中的地址）是否指向引用它的块来确定文件是否一致。如果是这样，则所有内容都必须已安全到达磁盘，因此文件是一致的；如果不是，则文件不一致，并返回错误。通过向文件系统添加反向指针，可以获得一种新形式的惰性崩溃一致性。

最后，还有一种减少日志协议等待磁盘写入完成的次数的技术。这种新方法被称为乐观崩溃一致性，通过使用事务校验和的通用形式向磁盘发出尽可能多的写入，并包含一些其他技术来检测出现的不一致情况。对于某些工作负载，这些乐观技术可以将性能提高一个数量级。然而，要真正正常运行，需要稍微不同的磁盘接口。