到目前为止，我们已经看到，文件系统管理一组数据结构来实现预期的抽象：文件、目录以及支持我们对文件系统预期的基本抽象所需的所有其他元数据。 与大多数数据结构（例如，在运行程序的内存中发现的数据结构）不同，文件系统数据结构必须**持久存在（persist）**，即它们必须长期存在，存储在即使断电仍能保留数据的设备上（例如硬盘或基于闪存的 SSD）。<br />文件系统面临的一个主要挑战是如何在**断电（power loss）或系统崩溃（system crash）**的情况下更新持久数据结构。 具体来说，如果就在更新磁盘结构的过程中，有人被电源线绊倒并且机器断电，会发生什么情况？ 还是操作系统遇到错误而崩溃？ 由于断电和崩溃，更新持久数据结构可能非常棘手，并导致文件系统实现中一个新的有趣的问题，称为**崩溃一致性问题（crash-consistency problem）**。<br />这个问题很容易理解。 假设您必须更新两个磁盘结构 A 和 B，才能完成特定操作。 由于磁盘一次仅处理一个请求，因此其中一个请求将首先到达磁盘（A 或 B）。 如果在一次写入完成后系统崩溃或断电，则磁盘结构将处于**不一致的（inconsistent）**状态。 因此，我们有一个所有文件系统都需要解决的问题：
关键的问题：考虑到崩溃，如何更新磁盘 系统可能会在任何两次写入之间崩溃或断电，因此磁盘状态可能只会部分更新。 崩溃后，系统启动并希望再次挂载文件系统（以便访问文件等）。 鉴于崩溃可能发生在任意时间点，我们如何确保文件系统将磁盘映像保持在合理的状态？
在本章中，我们将更详细地描述这个问题，并看看文件系统用来克服它的一些方法。 我们将首先检查旧文件系统采用的方法，称为 **fsck 或文件系统检查器（ fsck or the file system checker）**。 然后我们将注意力转向另一种方法，称为**日志记录（journaling，也称为预写日志（write-ahead logging））**，**这种技术会为每次写入增加一点开销，但可以更快地从崩溃或断电中恢复。** 我们将讨论日志的基本机制，包括 Linux ext3 [T98,PAA05]（一种相对现代的日志文件系统）实现的几种不同风格的日志。
42.1 一个详细的例子 A Detailed Example
为了开始我们对日记的研究，让我们看一个例子。 我们需要使用以某种方式更新磁盘结构的工作负载（workload）。 这里假设工作负载很简单：将单个数据块追加（append）到现有文件。 追加是通过打开文件，调用 lseek() 将文件偏移量移动到文件末尾，然后在关闭文件之前向文件发出单个 4KB 写入来完成的。
我们还假设我们在磁盘上使用标准的简单文件系统结构，类似于我们之前看到的文件系统。 这个小例子包括一个 inode 位图（inode bitmap，只有 8 位，每个 inode 一个），一个数据位图（data bitmap，也是 8 位，每个数据块一个），inode（总共 8 个，编号为 0 到 7，分布在四个块中），以及 数据块（共 8 个，编号为 0 到 7）。这是该文件系统的示意图：
如果查看图中的结构，可以看到分配了单个inode（inode编号2），在inode位图中标记，而单个分配的数据块（数据块4），也在数据位图中标记。 inode 表示为 I[v1]，因为它是这个 inode 的第一个版本； 它将很快更新（由于上述工作负载）。
让我们也来看看这个简化的 inode。 在 I[v1] 内部，我们看到：
在这个简化的inode中，文件的大小为1（它分配了一个块），第一个直接指针指向块4（文件的第一个数据块，Da），其他三个直接指针都设置为空 （表示它们未被使用）。 当然，真正的 inode 有更多的字段（fields）； 有关详细信息，请参阅前面的章节。
当我们追加到文件时，我们正在向它添加一个新的数据块，因此必须更新三个磁盘结构：inode（必须指向新块并记录由于追加而导致的新的更大的大小）、 新数据块 Db，以及新版本的数据位图（称为 B[v2]），表示新数据块已被分配。
因此，在系统的内存中，我们必须将三个块写入磁盘。 更新后的 inode（inode 版本 2，或简称 I[v2]）现在看起来像这样：
更新后的数据位图 (B[v2]) 现在看起来像这样：00001100。最后是数据块 (Db)，它只是填充了用户放入文件中的任何内容。 也许是偷来的音乐？
我们希望文件系统的最终磁盘映像如下所示 :
为了实现这种转换，文件系统必须对磁盘执行三个单独的写入，每个写入 inode (I[v2])、bitmap (B[v2]) 和 data block (Db)。 请注意，这些写入通常不会在用户发出 write() 系统调用时立即发生； 相反，脏的 inode、位图和新数据将首先在主内存中（在页面缓存（page cache）或缓冲区缓存（buffer cache）中）停留一段时间； 然后，当文件系统最终决定将它们写入磁盘时（比如 5 秒或 30 秒后），文件系统将向磁盘发出必要的写入请求。 不幸的是，可能会发生崩溃，从而干扰对磁盘的这些更新。 特别是，如果在这些写入中的一两个（但不是所有三个）发生后发生崩溃，则文件系统可能会处于一种有趣的状态。
崩溃场景 Crash Scenarios
为了更好地理解这个问题，让我们看一些示例崩溃场景。 想象一下只有一次写入成功； 因此存在三种可能的结果，我们在此列出：
只是将数据块 (Db) 写入磁盘。 在这种情况下，数据在磁盘上，但没有指向它的 inode，也没有位图甚至表明块已分配。 因此，就好像写入从未发生过一样。 从文件系统崩溃一致性的角度来看，这种情况根本不是问题。
然而，对于刚刚丢失了一些数据的用户来说，这可能是一个问题!
仅将更新的 inode (I[v2]) 写入磁盘。 在这种情况下，inode 指向 Db 将要写入的磁盘地址 (5)，但 Db 尚未写入那里。 因此，如果我们信任该指针，我们将从磁盘读取垃圾数据（garbage，磁盘地址 5 的旧内容）。此外，我们还有一个新问题，我们称之为文件系统不一致（file-system inconsistency）。 磁盘上的位图告诉我们数据块 5 尚未分配，但 inode 表示已分配。 bitmap和inode的不一致是文件系统的数据结构不一致； 要使用文件系统，我们必须以某种方式解决这个问题（更多内容见下文）。
- 只是将更新的位图 (B[v2]) 写入磁盘。 在这种情况下，位图指示块 5 已分配，但没有指向它的 inode。 这样文件系统又不一致了； 如果不解决，此写入将导致空间泄漏（space leak），因为文件系统永远不会使用块 5。
在尝试将三个块写入磁盘时，还有另外三个崩溃场景。 在这些情况下，两次写入成功，最后一次失败：
- inode (I[v2]) 和位图 (B[v2]) 写入磁盘，但不写入数据 (Db)。 在这种情况下，文件系统元数据是完全一致的：inode 有一个指向块 5 的指针，位图表明 5 正在使用中，因此从文件系统元数据的角度来看，一切都正常。 但是有一个问题：5 里面又出现了垃圾。
- 写入inode (I[v2]) 和数据块 (Db)，但不写入位图 (B[v2])。 在这种情况下，我们有 inode 指向磁盘上的正确数据，但在 inode 和旧版本的位图 (B1) 之间再次存在不一致。 因此，我们再次需要在使用文件系统之前解决问题。
位图 (B[v2]) 和数据块 (Db) 被写入，但不写入 inode (I[v2])。 在这种情况下，我们再次遇到 inode 和数据位图之间的不一致。 但是，即使块已写入并且位图指示其用途，我们也不知道它属于哪个文件，因为没有 inode 指向该文件。
崩溃一致性问题 The Crash Consistency Problem
希望从这些崩溃场景中，您可以看到由于崩溃而导致我们的磁盘文件系统映像可能出现的许多问题：我们可能存在文件系统数据结构的不一致； 我们可能会有空间泄漏； 我们可以将垃圾数据返回给用户； 等等。 理想情况下，我们想要做的是将文件系统从一个一致的状态（例如，在文件被附加到之前）以原子方式（atomically，例如，在 inode、位图和新数据块写入磁盘之后）移动到另一个状态。 不幸的是，我们不能轻易做到这一点，因为磁盘一次只提交一次写入，并且在这些更新之间可能会发生崩溃或断电。 我们称这个普遍问题为崩溃一致性问题（crash-consistency problem，我们也可以称其为一致性更新问题（consistent-update problem））。
42.2 解决方案1：文件系统检查器 Solution #1: The File System Checker
早期的文件系统采用了一种简单的方法来实现崩溃一致性。 基本上，他们决定让不一致发生，然后在稍后（重新启动时）修复它们。 在执行此操作的工具中可以找到这种惰性方法的一个经典示例：fsck。 fsck 是一个 UNIX 工具，用于查找此类不一致并修复它们 [MK96]； 在不同的系统上存在用于检查和修复磁盘分区的类似工具。 请注意，这种方法不能解决所有问题； 例如，考虑上述文件系统看起来一致但 inode 指向垃圾数据的情况。 唯一真正的目标是确保文件系统元数据在内部是一致的。
fsck：发音为“eff-ess-see-kay”、“eff-ess-check”，或者，如果您不喜欢该工具，则发音为“eff-suck”。 是的，严肃的专业人士使用这个词。
工具 fsck 在多个阶段运行，如 McKusick 和 Kowalski 的论文 [MK96] 中所述。 它在文件系统被挂载并可用之前运行（fsck 假设在它运行时没有其他文件系统活动正在进行）； 一旦完成，磁盘上的文件系统应该是一致的，从而可以被用户访问。
以下是 fsck 功能的基本摘要：超级块（Superblock）：fsck 首先检查超级块是否合理，主要是做健全性检查，例如确保文件系统大小大于已分配的块数。 通常这些健全性检查的目标是找到一个可疑的（损坏的）超级块； 在这种情况下，系统（或管理员）可能会决定使用超级块的备用副本。
- 空闲块（Free blocks）：接下来，fsck 扫描 inode、间接块、双重间接块等，以了解当前文件系统内分配了哪些块。 它使用这些知识来生成分配位图的正确版本； 因此，如果位图和 inode 之间存在任何不一致，则通过信任 inode 内的信息来解决。 对所有 inode 执行相同类型的检查，确保所有看起来像是正在使用的inode在inode位图中都被标记为正在使用的inode。
- inode 状态（Inode state）：检查每个 inode 是否存在损坏或其他问题。 例如，fsck 确保每个分配的 inode 都有一个有效的类型字段（例如，常规文件、目录、符号链接等）。 如果inode字段有问题不易修复，则认为inode有问题，由fsck清除； inode 位图也相应更新。
- inode 链接（Inode links）：fsck 还会验证每个分配的 inode 的链接数。 您可能还记得，链接计数表示包含对该特定文件的引用（即链接）的不同目录的数量。 为了验证链接数，fsck 从根目录开始扫描整个目录树，并为文件系统中的每个文件和目录构建自己的链接数。 如果新计算的计数与 inode 中发现的计数不匹配，则必须采取纠正措施，通常是通过修复 inode 内的计数。 如果发现分配的 inode 但没有目录引用它，则将其移动到 lost+found 目录。
- 重复（Duplicates）：fsck 还会检查重复的指针，即两个不同的 inode 引用同一个块的情况。 如果一个 inode 明显坏了，它可能会被清除。 或者，可以复制指向的块，从而根据需要为每个 inode 提供自己的副本。
- 坏块（Bad blocks）：在扫描所有指针的列表时，还会执行对坏块指针的检查。 如果一个指针明显指向其有效范围之外的某些内容，则该指针被认为是“坏的”，例如，它的地址指向一个大于分区大小的块。 在这种情况下，fsck 不能做任何太聪明的事情； 它只是从 inode 或间接块等中删除（清除）指针。
- 目录检查（Directory checks）：fsck 不了解用户文件的内容； 但是，目录包含由文件系统本身创建的特定格式的信息。 因此，fsck 对每个目录的内容执行额外的完整性检查，确保“.” 和“..”是第一个条目，在目录条目中引用的每个inode都被分配，并确保在整个层次结构中没有目录被链接超过一次。
如您所见，构建一个有效的 fsck 需要复杂的文件系统知识； 确保这样一段代码在所有情况下都能正常工作可能具有挑战性 [G+08]。 然而，fsck（和类似的方法）有一个更大的，也许是更根本的问题：它们太慢了。 对于非常大的磁盘容量，扫描整个磁盘以找到所有分配的块并读取整个目录树可能需要几分钟或几小时。 随着磁盘容量的增加和 RAID 的普及，fsck 的性能变得令人望而却步（尽管最近取得了进展 [M+13]）。
在更高的层次上，fsck 的基本前提似乎有点不合理。 考虑我们上面的例子，其中只有三个块被写入磁盘； 扫描整个磁盘以修复在仅更新三个块期间出现的问题的成本非常高。 这种情况类似于将您的钥匙丢在卧室的地板上，然后开始搜索整个房子以获取钥匙（search-the-entire-house-for-keys）恢复算法，从地下室开始，并在每个房间中搜索。 它有效，但很浪费。 因此，随着磁盘（和 RAID）的增长，研究人员和从业人员开始寻找其他解决方案。
42.3 解决方案2：日志（或预写日志） Solution #2: Journaling (or Write-Ahead Logging)
一致更新问题最流行的解决方案可能是从数据库管理系统的世界中窃取的一个想法。 这个想法被称为预写日志（write-ahead logging），正是为了解决这类问题而发明的。 在文件系统中，由于历史原因，我们通常称为预写日志记录（write-ahead logging journaling）。 第一个这样做的文件系统是 Cedar [H87]，尽管许多现代文件系统都使用了这个想法，包括 Linux ext3 和 ext4、reiserfs、IBM 的 JFS、SGI 的 XFS 和 Windows NTFS。
基本思想如下。 更新磁盘时，在适当地覆盖结构之前，首先写下一个小便条（磁盘上的其他位置，在众所周知的位置）描述您将要执行的操作。 写这个小便条是“预写（write ahead）”部分，我们把它写到一个我们组织为“日志（log）”的结构中； 因此，预写日志（write-ahead logging）。
通过将便条写入磁盘，您可以保证如果在更新（覆盖）您将更新的结构期间发生崩溃，您可以返回并查看您所做的注释并重试； 因此，您将确切知道崩溃后要修复什么（以及如何修复），而不必扫描整个磁盘。 根据设计，日志因此在更新期间增加了一些工作，以大大减少恢复期间所需的工作量。
我们现在将描述 Linux ext3（一种流行的日志文件系统）如何将日志合并到文件系统中。 大多数磁盘结构与Linux ext2相同，例如，磁盘分为块组，每个块组包含一个inode位图，数据位图，inodes和数据块。 新的关键结构是日志本身，它在分区内或其他设备上占用少量空间。 因此，ext2 文件系统（无日志）如下所示：
假设日志放置在同一个文件系统映像中（尽管有时它放置在单独的设备上，或者作为文件系统中的文件），带有日志的 ext3 文件系统如下所示：
真正的区别只是日志的存在，当然还有它的使用方式。
数据日志 Data Journaling
让我们看一个简单的例子来理解数据日志（data journaling）是如何工作的。 数据日志可用作 Linux ext3 文件系统的一种模式，本文的大部分讨论都基于该模式。
假设我们再次进行典型更新，我们希望将 inode (I[v2])、位图 (B[v2]) 和数据块 (Db) 写入磁盘。 在将它们写入最终磁盘位置之前，我们现在首先将它们写入日志（log，也称为日志journal）。 这就是日志中的样子：
你可以看到我们在这里写了五个块。 事务开始 (TxB) 告诉我们有关此更新的信息，包括有关文件系统挂起的更新的信息（例如，块 I[v2]、B[v2] 和 Db 的最终地址）以及某种事务标识符 (transaction identifier，TID)。 中间的三个块只包含块本身的确切内容； 这被称为物理日志记录（physical logging），因为我们将更新的确切物理内容放在日志中（另一种想法，逻辑日志记录（logical logging），将更新的更紧凑的逻辑表示放在日志中，例如，“此更新希望将数据块 Db 附加到文件 X”，这有点复杂，但可以节省日志空间并可能提高性能）。 最后一个区块 (TxE) 是该事务结束的标志，也将包含 TID。
一旦这个事务安全地在磁盘上，我们就准备好覆盖文件系统中的旧结构； 这个过程称为 checkpointing（译者注：让我想起了游戏中的checkpoint，一般是存档点）。 因此，为了 checkpoint 文件系统（即，使其与日志中的挂起更新保持同步），我们将写入 I[v2]、B[v2] 和 Db 发布到它们的磁盘位置，如上所示； 如果这些写入成功完成，我们就成功地 checkpointed 文件系统。 因此，我们的初始操作序列：
- 日志写入（Journal write）：将事务写入日志，包括事务开始（transaction-begin）块、所有未决数据和元数据更新以及事务结束（transaction-end）块； 等待这些写入完成。
- Checkpoint : 将挂起的元数据和数据更新写入文件系统中的最终位置。
在我们的示例中，我们首先将 TxB、I[v2]、B[v2]、Db 和 TxE 写入日志。 当这些写入完成时，我们将通过 checkpointing I[v2]、B[v2] 和 Db 到它们在磁盘上的最终位置来完成更新。
当写入日志期间发生崩溃时，事情会变得有点棘手。 在这里，我们试图将事务中的一组块（例如，TxB、I[v2]、B[v2]、Db、TxE）写入磁盘。 一种简单的方法是一次发布一个，等待每个完成，然后发布下一个。 然而，这是缓慢的。 理想情况下，我们希望一次发出所有五个块写入，因为这会将五个写入变成单个连续写入，从而更快。 但是，这是不安全的，原因如下：对于这么大的写入，磁盘内部可能会进行调度并以任意顺序完成大型写入中的小块。 因此，磁盘内部可能 (1) 写入 TxB、I[v2]、B[v2] 和 TxE，然后才 (2) 写入 Db。 不幸的是，如果磁盘在 (1) 和 (2) 之间断电，这就是磁盘上的结果：
为什么这是个问题？ 好吧，事务看起来像一个有效的事务（它有一个开始和一个结尾，并带有匹配的序列号）。 此外，文件系统无法查看第四个块并知道它是错误的； 毕竟，它是任意的用户数据。 因此，如果系统现在重新启动并运行恢复，它将重新发送此事务，并无知地将垃圾块“??”的内容复制到 Db 应该存在的位置。 这对文件中的任意用户数据不利； 如果它发生在文件系统的关键部分（例如超级块）上，则情况会更糟，这可能会使文件系统无法挂载。
Aside：强制写入磁盘 为了在两次磁盘写入之间强制排序，现代文件系统必须采取一些额外的预防措施。 在过去，强制在 A 和 B 两个写入之间进行排序很容易：只需将 A 写入磁盘，等待写入完成后磁盘中断操作系统，然后发出 B 写入。 由于磁盘中使用写入缓存的增加，事情变得稍微复杂一些。 启用写入缓冲（有时称为立即报告（immediate reporting））后，磁盘将在仅将其放置在磁盘的内存缓存中且尚未到达磁盘时通知操作系统写入已完成。 如果操作系统随后发出后续写入，则不能保证在先前写入之后到达磁盘； 因此不保证写入之间的顺序。 一种解决方案是禁用写缓冲。 然而，更现代的系统会采取额外的预防措施并发出明确的写入屏障（write barriers）； 当它完成时，这样的屏障保证在屏障之前发出的所有写入将在屏障之后发出的任何写入之前到达磁盘。 所有这些机制都需要非常信任磁盘的正确操作。 不幸的是，最近的研究表明，一些磁盘制造商为了提供“更高性能”的磁盘，明确忽略写屏障请求，从而使磁盘看起来运行得更快，但存在错误操作的风险 [C+13, R+11 ]。 正如卡汉所说，即使快速是错误的，快速几乎总是胜过慢速。
为避免此问题，文件系统分两步发出事务性写入。 首先，它将除 TxE 块之外的所有块写入日志，同时发出这些写入。 当这些写入完成时，日志将如下所示（再次假设我们的追加工作工作负载）：<br /><br />当这些写操作完成时，文件系统发出对TxE块的写操作，从而使日志处于最终的安全状态:<br /><br />这个过程的一个重要方面是磁盘提供的原子性保证（atomicity guarantee）。 事实证明，磁盘保证任何 512 字节的写入要么发生要么不发生（并且永远不会被写入一半）；** 因此，为了确保 TxE 的写入是原子的，应该将其设为一个 512 字节的块。** 因此，我们当前更新文件系统的协议，其三个阶段中的每一个都标记为：
- 日志写入（Journal write）：将事务的内容（包括TxB、元数据、数据）写入日志； 等待这些写入完成（译者注：将内存中的事务写入磁盘中的日志）。
- 日志提交（Journal commit）：将事务提交块（包含TxE）写入日志； 等待写入完成； 事务被称为已提交（committed）。
- Checkpoint：将更新的内容（元数据和数据）写入其最终的磁盘位置。
Aside：优化日志写 您可能已经注意到写入日志的效率特别低。 即文件系统首先要写出事务开始块和事务的内容； 只有在这些写入完成后，文件系统才能将事务结束块发送到磁盘。 如果您考虑磁盘的工作方式，性能影响很明显：通常会产生额外的旋转（想想为什么）。 我们以前的一位研究生 Vijayan Prabhakaran 有一个简单的想法来解决这个问题 [P+05]。 将事务写入日志时，请在开始和结束块中包含日志内容的校验和（checksum）。 这样做可以使文件系统一次写入整个事务，而无需等待； 如果在恢复期间，文件系统发现计算的校验和与事务中存储的校验和不匹配，则可以断定在事务写入期间发生崩溃，从而丢弃文件系统更新。 因此，通过对写入协议和恢复系统的小幅调整，文件系统可以实现更快的普通情况性能； 最重要的是，系统稍微更可靠，因为从日志中读取的任何内容现在都受到校验和的保护。 这个简单的修复很有吸引力，引起了 Linux 文件系统开发人员的注意，然后他们将它合并到下一代 Linux 文件系统中，称为（你猜对了！）Linux ext4（译者注：这就是大佬级研究生吗？）。 它现在在全球数百万台机器上运行，包括 Android 手持平台。 因此，每次在许多基于 Linux 的系统上写入磁盘时，在威斯康星州开发的少量代码都会使您的系统更快、更可靠。
恢复 Recovery
现在让我们了解文件系统如何使用日志的内容从崩溃中恢复（recover）。在一个更新序列期间，任何时候都可能发生崩溃。如果崩溃发生在事务安全写入日志之前（即，在上面的第 2 步完成之前），那么我们的工作很简单：挂起的更新被简单地跳过。如果崩溃发生在事务提交到日志之后，但在 checkpoint 完成之前，文件系统可以按如下方式恢复（recover）更新。系统启动时，文件系统恢复进程会扫描日志，寻找已经提交到磁盘的事务；这些事务因此被重新执行（replayed）（按顺序），文件系统再次尝试将事务中的块写出到它们最终的磁盘位置。这种日志形式是最简单的形式之一，称为重做日志（redo logging）。通过恢复日志中提交的事务，文件系统确保磁盘结构一致，因此可以通过挂载文件系统并为新请求做好准备来继续进行。
请注意，即使在对块的最终位置的某些更新已经完成之后，在 checkpoint 期间的任何时候发生崩溃也是正常的。 在最坏的情况下，其中一些更新只是在恢复期间再次执行。 由于恢复是一种罕见的操作（仅在意外系统崩溃后发生），因此无需担心一些冗余写入。
除非您担心一切，那我们无法帮助您。 别再担心了，这是不健康的！ 但现在你可能担心过度担心。
批处理日志更新 Batching Log Updates
您可能已经注意到基本协议可能会增加大量额外的磁盘流量。 例如，假设我们在同一目录中连续创建两个文件，分别称为 file1 和 file2。 要创建一个文件，必须更新一些磁盘结构，至少包括：inode 位图（分配新的 inode）、文件的新创建的 inode、包含新目录条目的父目录的数据块，以及父目录 inode（现在有一个新的修改时间）。 通过日志，我们在逻辑上将所有这些信息提交给我们创建的两个文件中的每一个的日志； 因为这些文件在同一个目录中，并且假设它们甚至在同一个 inode 块中有 inode，这意味着如果我们不小心，我们最终会一遍又一遍地写这些相同的块。
为了解决这个问题，一些文件系统不会一次提交一个更新到磁盘（例如，Linux ext3）； 相反，可以将所有更新缓冲到一个全局事务（global transaction）中。 在我们上面的例子中，当创建这两个文件时，文件系统只是将内存中的 inode 位图、文件的 inode、目录数据和目录 inode 标记为脏，并将它们添加到构成当前事务的块列表中（the list of blocks that form the current transaction）。 当最终需要将这些块写入磁盘时（例如，在 5 秒超时后），将提交包含上述所有更新的单个全局事务。 因此，通过缓冲更新，文件系统可以在许多情况下避免过多的磁盘写入流量。
使日志有限 Making The Log Finite
因此，我们得出了一个用于更新磁盘上文件系统结构的基本协议。 文件系统在内存中缓冲更新一段时间； 当最终写入磁盘时，文件系统首先小心地将事务的详细信息写入日志（也称为预写日志（write-ahead log））； 事务完成后，文件系统将这些块 checkpoints 到它们在磁盘上的最终位置。
但是，日志的大小是有限的。 如果我们不断向其添加事务（transactions）（如图所示），它很快就会被填满。 你认为会发生什么？
当日志变满时会出现两个问题。 第一个更简单，但不太重要：日志越大，恢复所需的时间就越长，因为恢复过程必须重新执行日志中的所有事务（按顺序）才能恢复。 第二个更重要的问题是：当日志已满（或接近满）时，无法将更多事务提交到磁盘，从而使文件系统“无用”（即无用）。
为了解决这些问题，日志文件系统将日志视为一个循环数据结构，反复重用； 这就是日志有时被称为循环日志（circular log）的原因。 为此，文件系统必须在 checkpoint 之后的某个时间采取行动。 具体来说，一旦一个事务被 checkpointed，文件系统应该释放它在日志中占用的空间，允许日志空间被重用。 有很多方法可以达到这个目的； 例如，您可以简单地在日志超级块中标记日志中最旧和最新的没有 checkpointed 的事务； 所有其他空间都是空闲的。 这是一个图形描述：
在日志超级块（不要与主文件系统超级块混淆）中，日志系统记录了足够的信息以了解哪些事务尚未被 checkpointed，从而减少恢复时间并以循环方式重用日志 . 因此，我们在我们的基本协议中添加了另一个步骤：
- 日志写入（Journal write）：将事务的内容（包括TxB、元数据、数据）写入日志； 等待这些写入完成（译者注：将内存中的事务写入磁盘中的日志）。
- 日志提交（Journal commit）：将事务提交块（包含TxE）写入日志； 等待写入完成； 事务被称为已提交（committed）。
- Checkpoint：将更新的内容写入文件系统中的最终位置。
- 释放（Free）：一段时间后，通过更新日志超级块在日志中标记事务释放。
因此，我们有了最终的数据日志协议。 但是仍然存在一个问题：我们将每个数据块写入磁盘两次，这是一个沉重的代价，尤其是对于像系统崩溃这样罕见的事情。 你能想出一种方法来保持一致性而不写两次数据吗？
元数据日志 Metadata Journaling
尽管现在恢复速度很快（扫描日志并重新执行（replaying）一些事务而不是扫描整个磁盘），但文件系统的正常操作比我们希望的要慢。 特别是，对于每次写入磁盘，我们现在也首先写入日志，从而使写入流量增加一倍； 在连续写入工作负载期间，这种加倍尤其痛苦，现在将以驱动器峰值写入带宽的一半进行。 此外，在写入日志和写入主文件系统之间，存在代价高昂的寻道，这会明显增加某些工作负载的开销。
由于将每个数据块写入磁盘两次的成本很高，人们尝试了一些不同的方法来提高性能。 例如，我们上面描述的日志模式通常称为数据日志（data journaling，如在 Linux ext3 中），因为它记录所有用户数据（除了文件系统的元数据）。 一种更简单（也更常见）的日志形式有时称为顺序日志（ordered journaling，或元数据日志（metadata journaling）），它几乎相同，只是用户数据不会写入日志。 因此，当执行与上述相同的更新时，以下信息将写入日志：
先前写入日志的数据块 Db 将改为适当地写入文件系统，避免额外写入； 考虑到磁盘的大多数 I/O 流量是数据，不写两次数据会大大减少日志的 I/O 负载。 不过，修改确实提出了一个有趣的问题：我们应该什么时候将数据块写入磁盘？
让我们再次考虑我们的文件追加示例，以更好地理解问题。 更新由三个块组成：I[v2]、B[v2] 和 Db。 前两个都是元数据，会被记录然后 checkpointed； 后者只会写入文件系统一次。 我们什么时候应该将 Db 写入磁盘？ 有关系吗？
事实证明，数据写入的顺序对于只有元数据的日志很重要。 例如，如果我们在事务（包含 I[v2] 和 B[v2]）完成后将 Db 写入磁盘会怎样？ 不幸的是，这种方法有一个问题：文件系统是一致的，但 I[v2] 可能最终指向垃圾数据。 具体来说，请考虑写入 I[v2] 和 B[v2] 但 Db 未将其写入磁盘的情况。 然后文件系统将尝试恢复。 因为 Db 不在日志中，文件系统会重新执行对 I[v2] 和 B[v2] 的写入，并产生一致的文件系统（从文件系统元数据的角度来看）。 但是， I[v2] 将指向垃圾数据，即 Db 所指向的插槽中的任何内容。
为了确保不会出现这种情况，一些文件系统（例如 Linux ext3）会先将（常规文件的）数据块写入磁盘，然后再将相关元数据写入磁盘。 具体来说，协议如下：
- 数据写入（Data write）：将数据写入最终位置； 等待完成（等待是可选的；详情见下文）。
- 日志元数据写入（Journal metadata write）：将开始块和元数据写入日志； 等待写入完成。
- 日志提交（Journal commit）：将事务提交块（包含TxE）写入日志； 等待写入完成； 事务（包括数据）现在已提交（committed）。
- Checkpoint 元数据（Checkpoint metadata）：将元数据更新的内容写入它们在文件系统中的最终位置。
- 释放（Free）：稍后，在日志超级块中将事务标记为空闲。
通过强制先写入数据，文件系统可以保证指针永远不会指向垃圾。 事实上，这种“在指向它的对象之前写入指向对象”的规则是崩溃一致性的核心，并且被其他崩溃一致性方案 [GP94] 进一步利用（详见下文）。
在大多数系统中，元数据日志（metadata journaling，类似于 ext3 的有序日志（ordered journaling））比全数据日志（full data journaling）更受欢迎。 例如，Windows NTFS 和 SGI 的 XFS 都使用某种形式的元数据日志。 Linux ext3 为您提供了选择数据、有序或无序（data, ordered, or unordered）模式的选项（在无序模式下，可以随时写入数据）。 所有这些模式都保持元数据一致； 它们的数据语义各不相同。
最后，请注意，在向日志（步骤 2）发出写入之前强制数据写入完成（步骤 1）并不是正确性所必需的，如上面的协议所示。 具体来说，并发写入数据、事务开始块和日志元数据是可以的； 唯一真正的要求是步骤 1 和 2 在发布日志提交块（步骤 3）之前完成。
棘手的情况：块重用 Tricky Case: Block Reuse
有一些有趣的极端案例（corner cases）使日志变得更加棘手，因此值得讨论。 其中一些围绕块重用； 正如 Stephen Tweedie（ext3 背后的主要推动者之一）所说：
“整个系统最可怕的地方是什么？ …它正在删除文件。 与删除有关的一切都是吓人的。 一切都与删除有关……如果块被删除然后重新分配会发生什么，你会做噩梦。” [T00]
Tweedie 给出的特定示例如下。 假设您正在使用某种形式的元数据日志记录（因此文件的数据块没有被记录）。 假设您有一个名为 foo 的目录。 用户向 foo 添加一个条目（比如通过创建一个文件），因此 foo 的内容（因为目录被视为元数据）被写入日志； 假设 foo 目录数据的位置是块 1000。因此日志包含如下内容：
此时，用户删除目录中的所有内容和目录本身，释放块 1000 以供重用。 最后，用户创建一个新文件（比如 bar），它最终会重用曾经属于 foo 的同一个块（1000）。 bar 的 inode 被提交到磁盘，它的数据也是如此； 但是请注意，由于正在使用元数据日志记录，因此只有 bar 的 inode 提交给日志； 不记录文件 bar 中块 1000 中新写入的数据。
现在假设发生了崩溃并且所有这些信息仍在日志中。 在重新执行期间，恢复过程简单地重新执行日志中的所有内容，包括块1000中目录数据的写入； 因此，重新执行（replay）会用旧目录内容覆盖当前文件 bar 的用户数据！ 显然，这不是一个正确的恢复操作，而且在读取文件 bar 时肯定会给用户带来惊喜。
这个问题有多种解决方案。 例如，人们可以永远不要重用块，直到将所述块被 checkpointed 从日志中删除。 Linux ext3 所做的是向日志添加一种新类型的记录，称为撤销（revoke）记录。 在上述情况下，删除目录会导致将撤销记录写入日志。 重新执行日志时，系统首先扫描此类撤销记录； 任何此类撤销的数据都不会重新执行，从而避免了上述问题。
总结日志：一个时间表 Wrapping Up Journaling: A Timeline
在结束我们对日记的讨论之前，我们总结了我们讨论过的协议，并用时间表描述了它们中的每一个。 图 42.1 显示了记录数据和元数据时的协议，而图 42.2 显示了仅记录元数据时的协议。
Figure 42.1: Data Journaling Timeline
Figure 42.2: Metadata Journaling Timeline
在每幅图中，时间向下增加，图中的每一行表示可以发出或可能完成写入的逻辑时间。 例如，在数据日志协议（图42.1）中，事务开始块（TxB）的写入和事务的内容在逻辑上可以同时发出，因此可以以任意顺序完成； 然而，在上述之前的写入完成之前，不得发出对事务结束块 (TxE) 的写入。 类似地，在事务结束块提交之前，checkpointing 写入数据和元数据块不能开始。 水平虚线显示必须遵守写入顺序要求的地方。
元数据日志协议显示了类似的时间线。 请注意，数据写入在逻辑上可以在写入事务开始和日志内容的同时发出； 但是，它必须在事务结束发出之前发出并完成。
最后，请注意，时间线中为每个写入标记的完成时间是任意的。 在实际系统中，完成时间由 I/O 子系统决定，它可能会重新排序写入以提高性能。 我们所拥有的关于排序的唯一保证是那些必须为协议正确性而强制执行的保证（并通过图中的水平虚线显示）。
42.4
解决方案3：其他方法 Solution #3: Other Approaches
到目前为止，我们已经描述了保持文件系统元数据一致的两种选择：一种基于 fsck 的惰性方法，以及一种称为日志记录的更主动方法。 然而，这并不是仅有的两种方法。 Ganger 和 Patt 引入了一种称为软更新（Soft Updates） [GP94] 的方法。 这种方法仔细地对所有对文件系统的写入进行排序，以确保磁盘结构永远不会处于不一致的状态。 例如，通过在指向它的inode之前将指向的数据块写入磁盘，我们可以确保inode永远不会指向垃圾； 可以为文件系统的所有结构导出类似的规则。 然而，实施软更新可能是一个挑战； 虽然上述日志层可以在对确切文件系统结构的了解相对较少的情况下实现，但软更新需要每个文件系统数据结构的复杂知识，因此给系统增加了相当多的复杂性。
另一种方法称为写时复制（是的，copy-on-write，COW），并用于许多流行的文件系统，包括 Sun 的 ZFS [B07]。 这种技术永远不会覆盖原地的文件或目录； 相反，它会将新的更新放置到磁盘上以前未使用的位置。 在完成多次更新后，COW 文件系统翻转文件系统的根结构以包含指向新更新结构的指针。 这样做可以使文件系统保持一致。 在以后的章节中讨论日志结构文件系统 (log-structured file system，LFS) 时，我们将更多地了解这种技术； LFS 是 COW 的早期示例。
另一种方法是我们刚刚在威斯康星州开发的方法。 在这种称为基于反向指针的一致性（backpointer-based consistency，BBC）的技术中，写入之间不强制执行排序。 为了实现一致性，系统中的每个块都添加了一个额外的后向指针； 例如，每个数据块都有一个对它所属的 inode 的引用。 在访问文件时，文件系统可以通过检查前向指针（例如 inode 或直接块中的地址）是否指向反向引用它的块来确定文件是否一致。 如果是这样，一切都必须安全地到达磁盘，因此文件是一致的； 如果不是，则文件不一致，并返回错误。 通过向文件系统添加反向指针，可以获得一种新形式的惰性崩溃一致性 [C+12]。
最后，我们还探索了减少日志协议必须等待磁盘写入完成的次数的技术。 这种名为乐观崩溃一致性（optimistic crash consistency） [C+13] 的新方法通过使用事务校验和（transaction
checksum）的通用形式 [P+05] 向磁盘发出尽可能多的写入，并包括一些其他技术来检测出现的不一致。 对于某些工作负载，这些乐观技术可以将性能提高一个数量级。 然而，要真正运行良好，需要稍微不同的磁盘接口 [C+13]。
42.5
总结 Summary 我们已经介绍了崩溃一致性问题，并讨论了解决这个问题的各种方法。 构建文件系统检查器的旧方法有效，但可能太慢而无法在现代系统上恢复。 因此，许多文件系统现在使用日志。 日志将恢复时间从 O（磁盘容量大小）减少到 O（日志大小），从而大大加快了崩溃和重启后的恢复速度。 出于这个原因，许多现代文件系统使用日志。 我们还看到日志可以有多种不同的形式； 最常用的是有序元数据日志，它减少了日志的流量，同时仍然为文件系统元数据和用户数据保留了合理的一致性保证。 最后，对用户数据的强有力保证可能是最重要的事情之一； 奇怪的是，正如最近的研究表明，该领域仍在进行中 [P+14]。
References
[B07] “ZFS: The Last Word in File Systems” by Jeff Bonwick and Bill Moore.
ZFS使用写时复制和日志写入，实际上，在某些情况下，将日志写入磁盘的性能会更好。
[C+12] “Consistency Without Ordering” by Vijay Chidambaram, Tushar Sharma, Andrea C.
Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. FAST ’12, San Jose, California.
我们最近的一篇关于基于反向指针的崩溃一致性的新形式的论文。 阅读它以了解令人兴奋的细节！
[C+13] “Optimistic Crash Consistency” by Vijay Chidambaram, Thanu S. Pillai, Andrea C.
Arpaci-Dusseau, Remzi H. Arpaci-Dusseau . SOSP ’13, Nemacolin Woodlands Resort, PA,
November 2013.
我们的工作更乐观，性能更高的日志协议。对于经常调用fsync()的工作负载，性能可以大大提高。
[GP94] “Metadata Update Performance in File Systems” by Gregory R. Ganger and Yale N.
Patt. OSDI ’94.
一篇关于使用仔细的写入顺序作为实现一致性的主要方法的聪明论文。 后来在基于 BSD 的系统中实现。
[G+08] “SQCK: A Declarative File System Checker” by Haryadi S. Gunawi, Abhishek Rajimwale, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. OSDI ’08, San Diego, California.
我们自己的论文是关于使用 SQL 查询构建文件系统检查器的一种新的更好的方法。 我们还展示了现有检查器的一些问题，发现了许多错误和奇怪的行为，这是 fsck 复杂性的直接结果。
[H87] “Reimplementing the Cedar File System Using Logging and Group Commit” by Robert Hagmann. SOSP ’87, Austin, Texas, November 1987.
第一个工作(我们知道的)是将预写日志记录(又称日志记录)应用到文件系统。
[M+13] “ffsck: The Fast File System Checker” by Ao Ma, Chris Dragga, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. FAST ’13, San Jose, California, February 2013.
我们最近的一篇论文详细介绍了如何使 fsck 速度提高一个数量级。 一些想法已经被纳入 BSD 文件系统检查器 [MK96] 并在今天部署。
[MK96] “Fsck – The UNIX File System Check Program” by Marshall Kirk McKusick and T. J.
Kowalski. Revised in 1996.
描述第一个全面的文件系统检查工具，同名的 fsck。 由为您带来 FFS 的一些人撰写。
[MJLF84] “A Fast File System for UNIX” by Marshall K. McKusick, William N. Joy, Sam J.
Leffler, Robert S. Fabry. ACM Transactions on Computing Systems, Volume 2:3, August 1984.
你对 FFS 已经足够了解了吧？ 不过算了，重要的论文再参考一下也行。
[P+14] “All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent
Applications” by Thanumalayan Sankaranarayana Pillai, Vijay Chidambaram, Ramnatthan
Alagappan, Samer Al-Kiswany, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. OSDI
’14, Broomfield, Colorado, October 2014.
一篇论文，我们研究文件系统在崩溃后保证什么，并表明应用程序期望不同的东西，从而导致各种有趣的问题。
[P+05] “IRON File Systems” by Vijayan Prabhakaran, Lakshmi N. Bairavasundaram, Nitin
Agrawal, Haryadi S. Gunawi, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. SOSP
’05, Brighton, England, October 2005.
一篇论文主要侧重于研究文件系统如何对磁盘故障做出反应。 最后，我们引入了一个事务校验和来加速日志记录，最终被 Linux ext4 采用。
[PAA05] “Analysis and Evolution of Journaling File Systems” by Vijayan Prabhakaran, Andrea
C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. USENIX ’05, Anaheim, California, April 2005.
我们写的一篇早期论文分析了日志文件系统是如何工作的。
[R+11] “Coerced Cache Eviction and Discreet-Mode Journaling” by Abhishek Rajimwale, Vijay
Chidambaram, Deepak Ramamurthi, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau.
DSN ’11, Hong Kong, China, June 2011.
我们自己的论文关于磁盘缓冲写入内存缓存而不是强制它们写入磁盘的问题，即使明确告知不要这样做！ 我们解决这个问题的方法是：如果你想让 A 在 B 之前写入磁盘，首先写入 A，然后向磁盘发送大量“虚拟”写入，希望导致 A 被强制写入磁盘以在缓存中为它们腾出空间。 一个简洁但不切实际的解决方案。
[T98] “Journaling the Linux ext2fs File System” by Stephen C. Tweedie. The Fourth Annual
Linux Expo, May 1998.
Tweedie 在为 Linux ext2 文件系统添加日志方面做了很多繁重的工作。 结果，毫不奇怪，被称为 ext3。 一些不错的设计决策包括对向后兼容性的高度关注，例如，您可以将日志文件添加到现有的 ext2 文件系统，然后将其挂载为 ext3 文件系统。
[T00] “EXT3, Journaling Filesystem” by Stephen Tweedie. Talk at the Ottawa Linux Symposium, July 2000.
Tweedie 在 ext3 上的谈话记录。
[T01] “The Linux ext2 File System” by Theodore Ts’o, June, 2001.
基于 FFS 中的想法的简单 Linux 文件系统。 有一段时间它被大量使用； 现在它真的只是在内核中作为一个简单的文件系统的例子。
Homework (Simulation)
本节介绍 fsck.py，这是一个简单的模拟器，可用于更好地了解如何检测（并可能修复）文件系统损坏。 有关如何运行模拟器的详细信息，请参阅相关的 README。
Questions
- 首先，运行 fsck.py -D; 此标志关闭任何损坏，因此您可以使用它来生成随机文件系统，并查看您是否可以确定其中有哪些文件和目录。 所以，继续做吧！ 使用 -p 标志来查看您是否正确。 通过将种子 (-s) 设置为不同的值（如 1、2 和 3），为一些不同的随机生成的文件系统尝试此操作。
- 现在，让我们介绍一个损坏。 运行 fsck.py -S 1 开始。 你能看出引入了什么不一致吗？ 您将如何在真正的文件系统修复工具中修复它？ 使用 -c 来检查您是否正确。
- 将种子改为-S 3 或-S 19； 你看到哪个不一致？ 使用 -c 检查您的答案。 这两种情况有什么不同？
- 将种子改为-S 5； 你看到哪个不一致？ 以自动方式解决这个问题有多难？ 使用 -c 检查您的答案。 然后，引入与-S 38 类似的不一致； 这更难/可能检测到吗？ 最后，使用 -S 642; 这种不一致是否可以检测到？ 如果是这样，您将如何修复文件系统？
- 将种子改为-S 6 或-S 13； 你看到哪个不一致？ 使用 -c 检查您的答案。 这两种情况有什么区别？ 遇到这种情况，修复工具应该怎么做？
- 将种子改为-S 9； 你看到哪个不一致？ 使用 -c 检查您的答案。 在这种情况下，检查和修复工具应该信任哪条信息？
- 将种子改为-S 15； 你看到哪个不一致？ 使用 -c 检查您的答案。 在这种情况下，修复工具可以做什么？ 如果无法修复，会丢失多少数据？
- 将种子改为-S 10； 你看到哪个不一致？ 使用 -c 检查您的答案。 这里的文件系统结构是否有冗余可以帮助修复？
- 将种子更改为 -S 16 和 -S 20； 你看到哪个不一致？ 使用 -c 检查您的答案。 修复工具应该如何修复问题？
若有收获，就点个赞吧
0 人点赞
