至此我们看到，档案系统管理一组资料结构以实现预期的抽象：档案、目录，以及所有其他元资料，它们支援我们期望从档案系统获得的基本抽象。与大多数资料结构不同（例如，正在执行的程式在内存中的资料结构），档案系统资料结构必须持久（persist），即它们必须长期存在，储存在断电也能保留资料的装置上（例如硬盘或基于闪存的SSD）。

档案系统面临的一个主要挑战在于，如何在出现断电（power loss）或系统崩溃（system crash）的情况下，更新持久资料结构。具体来说，如果在更新磁盘结构的过程中，有人绊到电源线并且机器断电，会发生什么？或者操作系统遇到错误并崩溃？由于断电和崩溃，更新永续性资料结构可能非常棘手，并导致了档案系统实现中一个有趣的新问题，称为崩溃一致性问题（crash-consistency problem）。

这个问题很容易理解。想象一下，为了完成特定操作，你必须更新两个磁盘上的结构A和B。由于磁盘一次只为一个请求提供服务，因此其中一个请求将首先到达磁盘（A或B）。如果在一次写入完成后系统崩溃或断电，则磁盘上的结构将处于不一致（inconsistent）的状态。因此，我们遇到了所有档案系统需要解决的问题：

关键问题：考虑到崩溃，如何更新磁盘

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

在本文中，我们将更详细地探讨这个问题，看看档案系统克服它的一些方法。我们将首先检查较老的档案系统采用的方法，即fsck，档案系统检查程式（file system checker）。然后，我们将注意力转向另一种方法，称为日志记录（journaling，也称为预写日志，write-ahead logging），这种技术为每次写入增加一点开销，但可以更快地从崩溃或断电中恢复。我们将讨论日志的基本机制，包括Linux ext3 [T98，PAA05]（一个相对现代的日志档案系统）实现的几种不同的日志。

（此处已新增圈子卡片，请到今日头条客户端检视）欢迎加入程序员读书会，每日分享最新图书和免费赠书活动

1　一个详细的例子

为了开始对日志的调查，先看一个例子。我们需要一种工作负载（workload），它以某种方式更新磁盘结构。这里假设工作负载很简单：将单个数据块附加到原有档案。通过开启档案，呼叫lseek()将档案偏移量移动到档案末尾，然后在关闭档案之前，向档案发出单个4KB写入来完成追加。

我们还假定磁盘上使用标准的简单档案系统结构，类似于之前看到的档案系统。这个小例子包括一个inode位图（inode bitmap，只有8位，每个inode一个），一个数据位图（data bitmap，也是8位，每个资料块一个），inode（总共8个，编号为0到7，分布在4个块上），以及资料块（总共8个，编号为0～7）。以下是该档案系统的示意图：

检视图中的结构，可以看到分配了一个inode（inode号为2），它在inode位图中标记，单个分配的资料块（资料块4）也在资料中标记位图。inode表示为I [v1]，因为它是此inode的第一个版本。它将很快更新（由于上述工作负载）。

再来看看这个简化的inode。在I[v1]中，我们看到：

owner : remzi

permissions : read-write

size : 1

pointer : 4

pointer : null

在这个简化的inode中，档案的大小为1（它有一个块位于其中），第一个直接指标指向块4（档案的第一个资料块，Da），并且所有其他3个直接指标都被设定为null（表示它们未被使用）。当然，真正的inode有更多的字段。更多相关资讯，请参阅前面的章节。

向档案追加内容时，要向它新增一个新资料块，因此必须更新3个磁盘上的结构：inode（必须指向新块，并且由于追加而具有更大的大小），新资料块Db和新版本的资料位图（称之为B[v2]）表示新资料块已被分配。

因此，在系统的内存中，有3个块必须写入磁盘。更新的inode（inode版本2，或简称为I [v2]）现在看起来像这样：

owner : remzi

permissions : read-write

size : 2

pointer : 4

pointer : 5

pointer : null

更新的资料位图（B[v2]）现在看起来像这样：00001100。最后，有资料块（Db），它只是使用者放入档案的内容。

我们希望档案系统的最终磁盘映像如下所示：

要实现这种转变，档案系统必须对磁盘执行3次单独写入，分别针对inode（I[v2]），位图（B[v2]）和资料块（Db）。请注意，当用户发出write()系统呼叫时，这些写操作通常不会立即发生。脏的inode、位图和新资料先在内存（页面快取，page cache，或缓冲区快取，buffer cache）中存在一段时间。然后，当档案系统最终决定将它们写入磁盘时（比如说5s或30s），档案系统将向磁盘发出必要的写入请求。遗憾的是，可能会发生崩溃，从而干扰磁盘的这些更新。特别是，如果这些写入中的一个或两个完成后发生崩溃，而不是全部 3个，则档案系统可能处于有趣的状态。

崩溃场景

为了更好地理解这个问题，让我们看一些崩溃情景示例。想象一下，只有一次写入成功。因此有以下3种可能的结果。

只将资料块（Db）写入磁盘。在这种情况下，资料在磁盘上，但是没有指向它的inode，也没有表示块已分配的位图。因此，就好像写入从未发生过一样。从档案系统崩溃一致性的角度来看，这种情况根本不是问题[1]。只有更新的inode（I[v2]）写入了磁盘。在这种情况下，inode指向磁盘地址（5），其中Db即将写入，但Db尚未写入。因此，如果我们信任该指标，我们将从磁盘读取垃圾资料（磁盘地址5的旧内容）。此外，遇到了一个新问题，我们将它称为档案系统不一致（file-system inconsistency）。磁盘上的位图告诉我们资料块5尚未分配，但是inode说它已经分配了。档案系统资料结构中的这种不同意见，是档案系统的资料结构不一致。要使用档案系统，我们必须以某种方式解决这个问题。

只有更新后的位图（B [v2]）写入了磁盘。在这种情况下，位图指示已分配块5，但没有指向它的inode。因此档案系统再次不一致。如果不解决，这种写入将导致空间泄露（space leak），因为档案系统永远不会使用块5。在这个向磁盘写入3次的尝试中，还有3种崩溃场景。在这些情况下，两次写入成功，最后一次失败。

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指向该块。崩溃一致性问题

希望从这些崩溃场景中，你可以看到由于崩溃而导致磁盘档案系统映像可能出现的许多问题：在档案系统资料结构中可能存在不一致性。可能有空间泄露，可能将垃圾资料返回给使用者，等等。理想的做法是将档案系统从一个一致状态（在档案被追加之前），原子地（atomically）移动到另一个状态（在inode、位图和新资料块被写入磁盘之后）。遗憾的是，做到这一点不容易，因为磁盘一次只提交一次写入，而这些更新之间可能会发生崩溃或断电。我们将这个一般问题称为崩溃一致性问题（crash-consistency problem，也可以称为一致性更新问题，consistent-update problem）。

2　解决方案1：档案系统检查程式

早期的档案系统采用了一种简单的方法来处理崩溃一致性。基本上，它们决定让不一致的事情发生，然后再修复它们（重启时）。这种偷懒方法的典型例子可以在一个工具中找到：fsck[2]。fsck是一个UNIX工具，用于查询这些不一致并修复它们[M86]。在不同的系统上，存在检查和修复磁盘分割槽的类似工具。请注意，这种方法无法解决所有问题。例如，考虑上面的情况，档案系统看起来是一致的，但是inode指向垃圾资料。唯一真正的目标，是确保档案系统元资料内部一致。

工具fsck在许多阶段执行，如McKusick和Kowalski的论文[MK96]所述。它在档案系统挂载并可用之前执行（fsck假定在执行时没有其他档案系统活动正在进行）。一旦完成，磁盘上的档案系统应该是一致的，因此可以让使用者访问。

以下是fsck的基本总结。

超级块：fsck首先检查超级块是否合理，主要是进行健全性检查，例如确保档案系统大小大于分配的块数。通常，这些健全性检查的目的是找到一个可疑的（冲突的）超级块。在这种情况下，系统（或管理员）可以决定使用超级块的备用副本。空闲块：接下来，fsck扫描inode、间接块、双重间接块等，以了解当前在档案系统中分配的块。它利用这些知识生成正确版本的分配位图。因此，如果位图和inode之间存在任何不一致，则通过信任inode内的资讯来解决它。对所有inode执行相同型别的检查，确保所有看起来像在用的inode，都在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需要复杂的档案系统知识。确保这样的程式码在所有情况下都能正常工作可能具有挑战性[G+08]。然而，fsck（和类似的方法）有一个更大的、也许更根本的问题：它们太慢了。对于非常大的磁盘卷，扫描整个磁盘，以查询所有已分配的块并读取整个目录树，可能需要几分钟或几小时。随着磁盘容量的增长和RAID的普及，fsck的效能变得令人望而却步（尽管最近取得了进展[M+13]）。

在更高的层面上，fsck的基本前提似乎有点不合理。考虑上面的示例，其中只有3个块写入磁盘。扫描整个磁盘，仅修复更新 3 个块期间出现的问题，这是非常昂贵的。这种情况类似于将你的钥匙放在卧室的地板上，然后从地下室开始，搜遍每个房间，执行“搜寻整个房子找钥匙”的恢复算法。它有效，但很浪费。因此，随着磁盘（和RAID）的增长，研究人员和从业者开始寻找其他解决方案。