至此我们看到，文件系统管理一组数据结构以实现预期的抽象：文件、目录，以及所有其它元数据，它们支持我们期望从文件系统获得的基本抽象。与大多数数据结构不同(例如，正在运行的程序在内存中的数据结构)，文件系统数据结构必须持久(persist)化，即它们必须长期存在，存储在断电也能保留数据的设备上(例如硬盘或基于闪存的SSD)。
因此，文件系统面临的挑战在于：如何在出现断电(power loss)或系统崩溃(system cresh)的情况下，依旧能更新持久数据结构。具体来说，如果在更新磁盘结构的过程中，有人绊倒电源线并且机器断电，会发生什么？或者操作系统遇到了错误导致崩溃？断电和崩溃，文件系统更新持久性数据结构会变得非常棘手，并导致了文件系统实现中一个有趣的新问题，称为崩溃一致性问题(crash-consistency problem)。
这个问题很容易理解。想象一下，为了完成特定操作，你必须更新磁盘上的结构A和B。由于磁盘一次性只能为一个请求提供服务，因此这两个请求肯定会存在先后的情况。如果在一次写入完成后系统崩溃或断电，那么磁盘上的结构将处于不一致(inconsistent)的状态。因此，我们遇到了所有文件系统都会面临的问题：
关键问题：考虑崩溃的情况，如何更新磁盘
系统可能在任何两次写入之间发生崩溃或断电，因此磁盘上状态可能仅部分地更新。崩溃后，系统重新启动并希望再次挂载文件系统(以便访问文件等)。鉴于崩溃可能在任意时间点发生，如何确保文件系统将磁盘上的映像(磁盘上的存储状态)保持在合理的状态？
在本章中，我们将更详细探讨这个问题，看看文件系统客服它的一些方法。我们将首先检查较老的文件系统采用的方法，即fsck，文件系统检查程序(file system checker)。然后，我们将注意力转向另一种方法，称为日志记录(journaling，也称为预写日志，write-ahead logging)，这种技术为每次写入增加一点开销，但可以更快地从崩溃或断电中回复。我们将讨论日志的基本机制，包括Linux ext3(相对现代的日志文件系统)实现的几种不同的日志。
一个详细的例子
为了开始对日志的调查，先看一个例子。我们需要一种工作负载(workload)，它以某种方式更新磁盘结构。这里假设工作负载很简单：将单个数据块附加到原有文件。通过打开文件，调用lseek()将文件偏移量移动到文件末尾，然后在关闭文件之前，向文件发出单个4KB写入来完成追加。
我们先回忆一下
inode： 在inode块中。文件的数据结构，如大小，直接指针等
inode 位图： inode空闲列表
data 位图：data块空闲列表
我们还假定磁盘上使用标准的简单文件系统结构，类似于之前看到的文件系统。这个小例子包括一个inode位图(inode bitmap，只有8位，每个inode一个)，一个数据位图(data bitmap，也是8位，每个数据块一个)，inode块(总共8个，编号为0-7，分布在4个块上)，以及数据块(总共8个，编号为0-7)。以下是该文件的示意图：
查看图中的接口，我们目前有一个文件，它的inode号是2，并且在inode位图中标记，其对应的数据块4也在数据位图(00001000)中标记。当前的inode表示为I[v1]，因为它是此inode的第一个版本。一会我们将对它进行更新。
我们来看看这个inode 的简化信息。在I[v1]中，我们看到：
我们从这个inode信息中可以看到，文件的大小为1(它有一个块)，第一个直接指针指向了块4(文件的第一个数据块，Da)，并且所有其它3个直接指针都被设置为null(表示它们未被使用)。当然，真正的inode有更多的字段，在之前的章节我们有讨论。
当我们想这个文件追加内容时，要向它添加一个新的数据块，因此必须更新3个磁盘上的结构
inode：直接指针需要多增加一个，同时size也会增加
新数据块Db：新的数据块
新数据位图：数据位图也需要更新，将对应的数据块标记为已使用
因此，在系统的内存中，有3个块必须要写入磁盘。更新的inode(inode版本2，或简称I[v2])，现在的inode看起来像这样：
数据位图先看起来像这样：00001100。
最后，还有数据块，它只是用户放入文件的内容。
我们希望文件系统的最终磁盘状态如下所示：
我们直到，如果想让磁盘的状态达到图上那样，文件系统需要对磁盘执行3次单独写入，分别针对inode，位图和数据块。还记得我们上一章学习的内容吗，当用户发出write()系统调用是，这些写操作通常不会立即发生。脏的inode、位图和新数据先在内存(页面缓存，page cache，或缓冲区缓存，buffer cache)中存在一段时间。然后，当文件系统最终决定将它们写入磁盘时(比如说5s或30s)，文件系统将向磁盘发出必要的写入请求。遗憾的是，在写入的过程中，是有可能发生崩溃的，从而干扰磁盘的这些更新。特别是，如果这些写入中的一个或两个完成后突然发生崩溃，而不是3个，此时文件系统可能处于有趣的状态。
崩溃场景
为了更好地理解这个问题，让我们看一些崩溃的场景示例。因为我们一共有3次写入，所有组合排列的话，一共有6种情况。
只有数据块写入磁盘：
在这种情况下，数据在磁盘上，但是inode没有指向它，数据位图也没有将其标记为已使用。所以，看起来就像没有发生过写入一样。从文件系统崩溃一致性的角度来看，这种情况根本不是问题。
只有inode(I[v2])写入了磁盘：
这种情况下，inode指向磁盘地址5，其中数据块还未写入。如果我们信任这个inode的指针，则可能会从磁盘地址5中读取出垃圾数据(磁盘地址5的旧内容)。
这种情况被称为文件系统不一致(file-system inconsistency)。inode中说磁盘5中有数据，但是数据位图说它没有被占用。文件系统数据结构的这种不同意见，是文件系统的数据结构不一致。
只有更新后的数据位图写入了磁盘：
在这种情况下爱，数据位图标记数据块5已经被使用，但是没有inode指向它。因此文件系统再次不一致。如果不解决，这种写入将导致空间泄露(space leak)，因为空间系统不会再去使用数据块5
还有3中崩溃场景。在这种情况下，两次写入成功，最后一次写入失败。
inode和数据位图写入了磁盘，但是数据块没有被写入：
在这种情况下，文件系统元数据(inode和数据位图)是完全一致的：inode有一个指向数据块5的指针，数据位图表示数据块5已被使用，因此从文件的元数据角度来看，一切看起来都很正常。但依旧有一个问题：数据块5中又是垃圾
inode和数据块写入了磁盘，但数据位图没有写入：
在这种情况下，inode指向了正确的磁盘数据，可数据位图没有将其标记为已使用。inode和数据位图出现了不一致的情况。
数据位图和数据块写入了磁盘，但inode没有写入：
在这种情况下，数据块和数据位图都写入了，数据位图也将该数据块标记为已使用，但我们不知道它属于哪个文件，inode和数据位图再次出现了不一致的情况。
崩溃一致性问题
希望从这些崩溃场景中，你可以看到由于崩溃而导致磁盘文件系统状态可能出现的许多问题：在文件系统数据结构中可能存在不一致性。可能有空间泄露，可能将垃圾数据返回给用户，等等。理想的做法是将文件系统从一个一致状态(在文件被追加之前)，原子地(atomically)移动到另一个状态(在inode、位图和新数据块被写入磁盘之后)。遗憾的是，做到这一点并不容易，因此磁盘一次只提交一次写入，而这些更新之间可能会发生崩溃或断电。我们可以将这个一般问题称为崩溃一致性问题(crash-consistency problem，也可以称为一致性更新问题，consistent-update problem)
解决方案1：文件系统检查程序
早期的文件系统采用了一种简单的方法来处理崩溃一致性。基本上，它们决定让不一致的事情发生，然后再修复它们(重启时)。这种偷懒方法的典型例子可以在一个工具中找到：fsch。fsck是一个UNIX工具。请注意，这种方法无法解决所有问题。例如，考虑上面的情况，文件系统看起来是一致的(inode和数据位图是一致的，但是数据块还未写入)，但是inode指向垃圾数据。
工具fsck在许多阶段运行，如McKusick和Kowalski的论文所述。它在文件系哦天哪挂载并可用之前运行(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需要复杂的文件系统知识。确保这样的代码在所有情况下都能正常工作可能具有挑战性。然而，fsck(和类似的方法)有一个更大的、也许更根本的问题：它们太慢了。对于非常大的磁盘卷，扫描整个磁盘，以查找所有已分配的块并读取整个目录树，可能需要几分钟或几小时。随着磁盘容量的增长和RAID的普及，fsck的性能变得令人望而却步(尽管最近取得了进展)。
在更高的层面上，fsck的基本前提似乎有些不合理。考虑上面的示例，其中只有3个块写入磁盘。扫描整个磁盘，仅修复更新3个块区间开始的问题，这是非常昂贵的。这种情况类似于将你的钥匙放到卧室的地板上，然后从地下室开始，搜遍每个房间，执行“搜索整个房子找钥匙”的恢复算法。它有效，但很低效。因此，随着磁盘(和RAID)的增长，研究人员和从业者开始寻找其它解决方案。
解决方案2：预写日志
对于一致性更新问题，最流行的解决方式是从数据库管理系统的世界中借鉴的一个想法。这种名为预写日志(write-ahead logging)，就是为了解决这类问题而发明的。
为什么文件系统的预写日志借鉴的是数据库，而不是RAID的？
实际上，文件系统的预写日志和RAID的预写日志都是为了解决数据一致性问题而设计的，它们的实现方式也有很多相似之处。但是，文件系统的预写日志最初确实是从数据库管理系统中借鉴的，原因如下：
- 数据库管理系统中的预写日志是最早被广泛应用的。在数据库管理系统中，数据的一致性和可靠性是至关重要的，因此需要一种可靠的机制来确保数据的一致性和可靠性。预写日志就是为了解决这个问题而被发明的。
- 文件系统的预写日志最初是在1980年代末期和1990年代初期被引入的。当时，文件系统的设计者们开始意识到，文件系统的可靠性和性能也需要一种可靠的机制来确保。因此，他们开始借鉴数据库管理系统中的预写日志的思想，将其应用到文件系统中。
- 在实现预写日志的过程中，文件系统的设计者们也借鉴了RAID中的一些思想和技术。例如，文件系统的预写日志和RAID的预写日志都需要使用缓存来提高性能，都需要使用校验和来确保数据的完整性，都需要使用日志来记录磁盘操作等等。
因此，虽然文件系统的预写日志和RAID的预写日志都是为了解决数据一致性问题而设计的，但文件系统的预写日志最初确实是从数据库管理系统中借鉴的。
文件系统的设计者们当然也会考虑RAID中的预写日志，但是需要注意的是，RAID和文件系统的设计目标是不同的。RAID的设计目标是提高数据的可靠性和性能，而文件系统的设计目标是提供一种可靠的机制来管理文件和目录，并确保数据的一致性和可靠性。因此，文件系统的设计者们需要考虑的问题更加复杂，需要解决的问题也更加多样化。
此外，预写日志最初是在数据库管理系统中被广泛应用的，因为在数据库中，数据的一致性和可靠性是至关重要的。因此，预写日志在数据库中的应用得到了广泛的认可和应用。当文件系统的设计者们开始意识到文件系统的可靠性和性能也需要一种可靠的机制来确保时，他们自然而然地想到了从数据库管理系统中借鉴预写日志的思想。
最后，需要注意的是，文件系统的预写日志和RAID的预写日志虽然有很多相似之处，但是它们的实现方式也有很多不同之处。因此，文件系统的设计者们需要根据文件系统的特点和需求来选择最适合的实现方式，而不是盲目地借鉴其他系统的实现方式。
在文件系统中，处于历史原因，我们通常将预写日志称为日志(journaling)。第一个实现它的文件系统是Cedar，但许多现代化文件系统都使用相同的想法，包括Linux ext3和ext4、reiserfs、IBM的JFS、SGI的XFS和Windows NTF。
基本思如如下。更新磁盘时，在覆写结构之前，首先写下一点小标记/日志记录(在磁盘上的其它地方，在一个从所周知的位置)，描述你想做的事情。写下这个标记就是“预写”部分，我们把它写入一个结构，并组织成“日志”。因此，就有了预写日志。
通过将日志记录写入到磁盘中的某个位置，可以保证在更新文件数据结构时突然发生崩溃，能够返回并查看你所做的记录，然后重试。因此，你会在崩溃后准确知道要修复的内容(以及日和修复它)，而不必扫描整个磁盘。因此，通过设计，日志功能在更新期间增加了一些工作量，从而大大减少了恢复期间所需的工作量。
我们现在将描述Linux etx3(一种流行的日志文件系统)如果将日志记录到文件系统中。大多数磁盘上的结构与Linux etx2相同，例如，磁盘被分成块组，每个块组都有一个inode和数据位图以及inode和数据块。新的关键结构是日志本身，它占用分区内或其它设备上的少量空间。因此，ext2文件系统(没有日志)看起来像这样：
假设日志放在同一个文件系统映像中(虽然有时将它放在单独的设备上，或作为文件系统中的文件)，带有日志的etx3文件系统如下所示：
真正的区别只是日志的存在，当然，还有它的使用方式。
数据日志
看一个简单的例子，来理解数据日志(data journaling)的工作原理。数据日志作为Linux ext3文件系统的一种模式提供，本讨论的大部分内容都来自于此。
假设再次进行标准的更新，我们再次希望将inode(I[V2])、数据位图(B[v2])和数据块(Db)写入磁盘。在将它们写入最终磁盘位置之前，现在先将它们写入日志。这就是日志中的样子：
你可以看到，这里有5个块，其中是3个写入，另外两个是事务相关的，事务开始(TxB)会记录我们有关此更新的信息，包括对文件系统即将进行的更新的相关信息(例如，块I[v2]、B[v2]和Db的最终地址)，以及某种事务标识符(transaction identifier, TID)。中间的3个块只包含块本身的确切内容，这被称为物理日志(physical logging)，因为我们将更新的确切物理内容放在日志中(另一种想法，逻辑日志(logical logging)，在日志中放置更紧凑的更新逻辑表示，例如，“这次更新希望将数据库Db追加到文件X”，这有点复杂，但可以节省日志中的空间，并可能提高性能)。最后一块(TxE)是该事务结束的标记，也会包含TID。
一旦这个事务日志安全地存在磁盘上，我们就可以去覆写文件系统中的旧结构了。这个过程称为加检查点(checkpointing)。因此，为了对文件系统加检查点(checkpoint，即让它与日志中即将进行的更新一致)，我们将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)写入磁盘。一种简单的方法是依次发出一个，等待每个完成，然后发出下一个。但是，这很慢。理想情况下，我们希望依次发出所有5个块细入，因为这会将5个写入转换为单个顺序写入，因此更快。然而，由于以下原因，这是不安全的：给定如此大的写入，磁盘内部可以执行调度并以任何顺序完成大批写入的小块。因此，磁盘内部的写入顺序可能发生错乱，如先写入 TxB、I[v2]、B[v2](①)和 TxE(②)，然后才写入 Db。如果在①和②的过程中发生了断电，那么磁盘上会变成：
为什么这是个问题？好吧，这个事务看起来像是一个有效的事务(TxB和TxE都有)。但是文件系统无法查看第四个块，也不知道它发生了错误。毕竟，它是任意的用户数据(垃圾数据)。因此，如果系统现在重启并运行恢复，它会重放此事务，并将垃圾块“??”的内容复制到Db应该存在的位置。这个问题很严重。如果这发生在文件系统的关键部分上，例如超级块，可能会导致文件系统无法挂载，那就更糟了。
为了避免该问题，文件系统分两步发出事务写入。首先，它将TxE块(事务结束)之外的所有块写入日志，同时发出这些写入。当这些写入完成时，日志看起来如下这样(假设又是文件追加的工作负载)：
当前面的这些写入完成时，文件系统会发出TxE块的写入，从而使日志处于最终的安全状态：
这个过程的一个重要方面是磁盘提供的原子性保证。事实证明，磁盘保证任何512字节写入都会发生或不发生(永远不会半写)。因此，为了确保TxE的写入是原子的，应该使它成为一个单独的512字节的块。因此，我们当前更新文件系统的协议如下，3个阶段中每一个都标上了名称。
1. 日志写入：将事务的内容(包括TxB、元数据和数据)写入日志，等待这些写入完成。
2. 日志提交：将事务提交块(包括TxE)写入日志，等待写完成，事务被认为已提交(committed)。
3. 加检查点：将更新内容(元数据和数据)写入其最终的磁盘位置。
补充：强制写入磁盘
如果想要在两次磁盘写入保证顺序，现代文件系统必须采取一些额外的预防措施。
在以前，强制在两个写入 A 和 B 之间进行顺序很简单: 只需向磁盘发出 A 写入，等待磁盘在写入完成时中断 OS， 然后发出写入 B。
但是因为磁盘有写入缓存(有时称为立即报告， immediate reporting)的功能，它让这件事情变得复杂起来了，如果写入缓冲被启用，然后磁盘将数据放到磁盘的内存缓存中、但此时它还没有实际的写入到磁盘，磁盘会告诉操作系统 写入完成。
如果操作系统随后又发出了后续的写入，那么可能这两次写入没有办法保证先后顺序。
d
由于磁盘中写入缓存的使用增加，事情变得有点复杂了。启用写入缓冲后(有时称为立即报告， immediate reporting)，如果磁盘已经放入磁盘的内存缓存中、但尚未到达磁盘，磁盘就会通知操作系统 写入完成。如果操作系统随后发出后续写入，则无法保证它在先前写入之后到达磁盘。因此，不再保证写入之间的顺序。一种解决方案是禁用写缓冲。然而，更现代的系统采取额外的预防措施，发出明确的写入屏障(write barrier)。这样的屏障，当它完成时，能确保在屏障之前发出的所有写入，先于在屏障之后发出的所有写入到达磁盘。
所有这些机制都需要对磁盘的正确操作有很大的信任。遗憾的是，最近的研究表明，为了提供“性能更高”的磁盘，一些磁盘制造商显然忽略了写屏障请求，从而使磁盘看起来运行速度更快，但存在操作错误的风险[C+13, R+11]。正如 Kahan 所说，快速几乎总是打败慢速，即使快速是错的。
补充：优化日志写入
你可能已经注意到，写入日志的效率特别低。也就是说，文件系统首先必须写出事务开始块和事务的内容。只有在这些写入完成后，文件系统才能将事务结束块发送到磁盘。如果你考虑磁盘的工作方式， 性能影响很明显:通常会产生额外的旋转(请考虑原因)。
我们以前的一个研究生 Vijayan Prabhakaran，用一个简单的想法解决了这个问题[P+05]。将事务写入日志时，在开始和结束块中包含日志内容的校验和。这样做可以使文件系统立即写入整个事务，而不会产生等待。如果在恢复期间，文件系统发现计算的校验和与事务中存储的校验和不匹配，则可以断定在写入事务期间发生了崩溃，从而丢弃了文件系统更新。因此，通过写入协议和恢复系统中的小调整， 文件系统可以实现更快的通用情况性能。最重要的是，系统更可靠了，因为来自日志的任何读取现在都受到校验和的保护。
这个简单的修复很吸引人，足以引起 Linux 文件系统开发人员的注意。他们后来将它合并到下一代 Linux 文件系统中，称为 Linux ext4(你猜对了!)。它现在可以在全球数百万台机器上运行，包括 Android 手持平台。因此，每次在许多基于 Linux 的系统上写入磁盘时，威斯康星大学开发的一些代码都会使你的系统更快、更可靠。
恢复
现在来了解文件系统如何使用日志的内容来从崩溃中恢复(recover)。在这个更新序列期间，任何时候都可能发生崩溃。如果崩溃发生在事务被安全地写入到日志之前(在上面的步骤②完成之前)，那么我们可以很简单的处理：简单地跳过待执行的更新(即不去处理这种情况，这可能会导致文件系统的一些数据丢失或不一致)。
如果在事务已经提交，但在加检查点完成之前发生崩溃，则文件系统可以按如下方式恢复(recover)更新。系统引导时，文件系统恢复过程将扫描日志，并查找已提交到磁盘的事务。然后，这些事务被重放(replayed，按顺序)，文件系统再次尝试将事务中的块写入它们最终的磁盘位置。
这种形式的日志是最简单的形式之一，称为重放日志(redo logging)。通过在日志中恢复已提交的事务，文件系统确保磁盘上的结构是一致的，因此可以继续工作，挂载文件系统并为新请求做好准备。
请注意，即使在某些更新写入块的最终位置之后，然后在加检查点期间发生崩溃，都是没有问题的。在最坏的情况下，其中一些更新只是在回复期间再次执行。因为回复是一种罕见的操作(仅在系统意外崩溃之后发生)，所以几次冗余写入无须过分担心。
批处理日志更新
你可能已经注意到，基本协议可能会增加大量额外的磁盘流量。例如，假设我们在同一目录中连续创建两个文件，file1和file2。我们知道，要创建一个文件，必须更新磁盘上的很多结构，至少包括：inode位图(分配新的inode)，数据位图，新创建文件的inode，包含新文件目录条目的父目录的数据块，以及父目录的inode(现在有一个新的修改时间)。通过日志，我们将所有这些信息逻辑地写到日志中(包含两个创建文件的日志)。因为文件在同一个目录中，我们假设在同一个inode块中都有inode，这意味着如果不小心，我们最终会一遍又一遍地写入这些相同的块。
为了避免这种情况，一些文件系统不会一次一个地向磁盘提交每个更新(例如，Linux etx3)。与此不同，可能将所有更新缓冲到全局事务中。在上面的示例中，当创建两个文件时，文件系统只讲内存中的inode位图、文件的inode、目录数据和目录inode标记为脏，并将它们添加到块列表中，形成当前的事务。当最后应该将这些块写入磁盘时(例如，在超时5s之后)，会提交包含上述所有更新的单个全局事务。因此，通过缓冲更新，文件系统在许多情况下可以避免对磁盘的过多的写入流量。
使日志有限
我们已经了解到更新文件系统磁盘结构的基本协议。文件系统缓冲内存中的更新一段时间。最后写入磁盘，文件系统首先仔细地将事务的详细信息写入日志(即预先日志)。在事务完成后，文件系统会加检查点，将这些块写入磁盘上的最终位置。
但是，日志的大小是有限的。如果不断向它添加事务(如下所示)，它将很快填满。你觉得这会发生什么？
日志满时会出现两个问题，日志文件系统将日志视为循环数据结构，一遍又一遍地重复使用。这就是为什么日志有时候被称为循环日志(circular log)，这意味着当日志文件达到一定大小时，它会从头开始重新写入，覆盖之前的日志记录。这种循环的方式可以确保日志文件不会无限增长，同时也可以保证日志记录的连续性。
为此，文件系统必须在加检查点之后的某个时间执行操作。具体来说，一旦事务被加检查点，文件系统应释放它在日志中占用的空间，允许重用日志空间。有很多方法可以达到这个目的。例如，你只需在日志超级块(journal superblock)中标记日志中最旧和最新的事务。所有其它空间都是空闲的。以下是这种机制的图形描述：
在日志超级块(不要与主文件系统的超级块混淆)中，日志系统记录了足够的信息，以了解哪些事务尚未加检查点，从而减少了恢复时间，并允许以循环的方式重新使用日志。因此，我们在基本协议中添加了另一个步骤。
1. 日志写入：将事务的内容(包括TxB和更新内容)写入日志,等待这些写入完成。
2. 日志提交：将事务提交块(包括TxE)写入日志，等待写完成，事务被任务已提交(committed)
3. 加检查点：将更新内容写入其最终的磁盘位置。
4. 释放：一段时间后，通过更新日志超级块，在日志中标记该事务为空闲。
通过以上方式，我们得到了最终的数据日志协议。但这样仍然存在一个问题：我们将每个数据块写入磁盘两次(第一次将日志写入到磁盘中，第二次才实际写入到对应的数据块中)，这个成本很高，特别是它是为了解决系统崩溃这样发生频率很少的事情。你能找出一种方法来保持数据一致性，而且不需要往磁盘写入两次的方案吗？
解决方案：元数据日志(有序日志)
刚刚我们提到，我们需要将数据块往磁盘写入两次，尽管现在恢复很快(扫描日志并重放一些事务而不是扫描整个磁盘)，但文件系统的正常操作比我们想要的要慢。特别是，对于每次写入磁盘，需要先写入日志，这导致写入的流量加杯。在顺序写入工作负载期间，这种加倍尤为痛苦，这会导致驱动器峰值写入的带宽只能获得一半。此外，在写入日志和写入主文件系统之间，存在代价高昂的寻道(还记得我们之前学习的寻道时间吗)，这为某些工作负载增加了显著的开销。
由于将数据块写入磁盘的成本很高，人们为了提高性能，尝试了一些不同的东西。例如，我们上面描述的日志模式通常称为数据日志(data journaling，如在Linux ext3中)，因为它在日志中记录了所有用户的数据(除了文件系统的元数据之外)。
还有一种更简单(也更常见)的日志形式称为有序日志(ordered journaling，或称为元数据日志，metadata journaling)，它几乎和数据日志相同，只是用户数据不会写入到日志。因此，在执行上述相同的更新时，以下信息将写入日志：
你会注意到，其中缺少了数据块Db，在之前的日志中，是会将Db也写入到日志中的。在有序日志中，为了避免额外写入，考虑到磁盘的大多数I/O流量是数据。因此，如果能够避免数据块两次写入将会大大减少日志的I/O负载。然而，这个修改需要先解决一个问题：那我们该何时将数据块写入磁盘？
我们再来考虑一下文件追加的例子，以更好地理解问题。更新包含3个块：I[v2]、B[v2]和 Db。前两个都是元数据，将被记录，然后加检查点。后者(Db)只会向文件系统写入一次。什么时候应该把Db写入磁盘？这有什么关系？
事实证明，数据写入的顺序对于仅元数据日志很重要。例如，如果我们在事务(包含I[v2]和B[v2])完成之后将Db写入磁盘如何？如果使用这个方式，会存在一个问题：文件系统是一致的，但是I[v2]指向了垃圾数据。具体来说，可能I[v2]和B[v2]已经写入到磁盘，但是Db没有写入磁盘。然后文件系统将尝试恢复。由于 Db 不在日志中，因此文件系统将重放对 I[v2]和 B[v2]的写入，并生成一致的文件系统(从文件系统元数据的角度来看)。但是， I[v2]将指向垃圾数据，即指向 Db 中的任何数据。
为了确保不会出现这个情况，在将相关元数据写入磁盘之前，一些文件系统(例如，Linux etx3)先将数据块(常规文件)写入磁盘。具体来说，协议有以下几个。
1. 数据写入：将数据写入最终位置，等待完成(等待是可选的(即文件系统也可以立即返回，不等待数据块实际写入完成)，详见下文)。
2. 日志元数据写入：将开始块和元数据写入到日志，等待写入完成。
3. 日志提交：将事务提交块(包括TxE)写入日志，等待写完成，现在认为事务(包括数据)已提交(committed)。
4. 加检查点元数据：将元数据更新的内容写入到文件系统的最终位置。
5. 释放：稍后，在日志超级块中将事务标记为空闲。
通过强制先写入数据，文件系统可以保证指针永远不会指向垃圾。实际上，这个”先写入被指对象(数据块)，再写入指针对象(元数据)“的规则是崩溃一致性的核心，这种方式也叫做”写后日志“，并且被其它崩溃一致性进一步利用。
在大多数系统中，元数据日志(类似ext3的有序日志)比数据日志更受欢迎。例如，Windows NTFS和SGI的XFS都使用无序的元数据日志。Linux ext3为你提供了选择数据、有序或无序模式的选项(在无序模式下，可以随时写入数据)。所有这些模式都保持元数据一致，它们的数据语义各不相同。
最后，请注意，在发出写入日志(步骤2，写入元数据时)是可以不等待数据块实际写入，就如上面协议所示。具体来说，可以在发出数据块写入后，文件系统可以立即返回，而不必等待数据块被写入磁盘。但是，在执行到步骤3时需要确保步骤1和步骤2都已经实际的完成。
棘手的情况：块复用
在某些特殊情况下会让日志变得棘手，因此值得讨论。其中一些与块复用有关。正如Stephen Tweedie(etx3 背后的主要开发者之一)所说：
“整个系统的可怕部分是什么？...…是删除文件。与删除有关的一切都令人毛骨悚然。与删除有关的一切……如果块被删除然后重新分配，你会做噩梦”
Tweedie给出的具体例子如下。假设你正在使用某种形式的元数据日志(因此不记录文件的数据块)。假设你有一个名为foo的目录。用户想foo添加一个条目(例如通过创建文件的数据块)。因此foo的内容(因为目录被认为是元数据)被写入日志。假设foo目录数据的位置是块1000。因此日志包含如下内容：
如果此时用户删除目录中的所有内容以及目录本身，这样块1000可以重新使用。接着，用户创建了一个新文件(如foobar)，它复用了之前属于foo的相同块(1000)。foobar的inode提交了磁盘，其数据也是如此。但是，请注意，因为正在使用元数据日志，所以在日志中只会有foobar的inode记录，文件foobar的实际数据不会出现在日志中。
现在假设发生了崩溃，所有这些信息仍然在日志中。在重放期间，恢复过程简单地重 放日志中的所有内容，包括在块 1000 中写入目录数据。因此，重放会用旧目录内容覆盖当 前文件 foobar 的用户数据!显然，这不是一个正确的恢复操作，当然，在阅读文件 foobar 时，用户会感到惊讶。
关于书上描述的这个问题，我没有理解到。 因为在元数据日志中，会先将数据块写入到实际的磁盘地址，然后再写入元数据到日志中。因为在发生崩溃的时候，此时数据块应该已经是正确的数据块了(foobar)，然后再将元数据写入到日志中。此时就算发生崩溃，在随后的重放期间，它取到旧数据去恢复，这个旧数据也是正确的数据了(foobar)，所以我认为书上描述的问题应该不成立吧
这个问题有一些解决方案。例如，可以永远不再重复使用块，直到所述块的删除加上检 查点，从日志中清除。Linux ext3 的做法是将新类型的记录添加到日志中，称为撤销(revoke) 记录。在上面的情况中，删除目录将导致撤销记录被写入日志。在重放日志时，系统首先扫 描这样的重新记录。任何此类被撤销的数据都不会被重放，从而避免了上述问题。
总结日志：时间线
在结束对日志的讨论之前，我们总结一下讨论过的协议，用时间线来描述每个协议。表1展示了日志数据和元数据时的协议，表2展示了仅记录元数据时的协议。
在每个表中，事件向下增加，表中的每一行显示可以发出或可能完成写入的逻辑时间。例如，在数据日志协议中，事务开始块(TxB)的写入和事务的内容可以在逻辑上同时发出，因此可以按任何顺序完成。但是，在上述写入完成之前，不得发出对事务结束块(TxE)的写入。同样，在事务结束块(TxE)提交之前，写入数据和元数据块的加检查点无法开始。水平虚线表示必须遵守的写入顺序要求。
对元数据日志协议也显示了类似的时间线。请注意，在逻辑上，数据写入可以与对事务开始的写入和日志的内容一起发出。但是，必须在事务结束发出之前并完成。
最后，请注意，时间线每次写入标记的完成时间是任意的。在实际系统中，完成时间有I/O子系统确定，I/O子系统可能会重新排序写入以提高性能。对于顺序的唯一保证，是那些必须强制执行，才能保证协议正确性的顺序。
解决方案3：其它方法
到目前为止，我们已经描述了保持文件系统元数据一致性的两个可选方法：基于fsch的偷懒方法，以及称为日志的更活跃的方法。但是，并不是只有这两种方法。Ganger和Patt引入了一种称为软更新的方法。这种方法仔细地对文件系统的所有写入排序，以确保磁盘上的结构永远不会处于不一致的状态。例如，通过先写入指向的数据块，再写入指向它的inode，可以确保inode永远不会指向垃圾。对文件小系统的所有结构可以导出类似的规则。然而，实现软更新可能是一个挑战。上述日志层的实现只需要具体文件系统结构的较少知识，但软更新需要每个文件系统数据结构的复杂知识，因此给系统增加了相当大的复杂性。
另一种方法称为写时复制(Copy-On-Write，COW)，并且在许多流行的文件系统中使用，包括Sun的ZFS。这种技术永远不会覆写文件或目录。相反，它会对磁盘上以前未使用的位置进行新的更新。在完成许多更新后，COW文件系统会翻转文件系统的根结构，以包含指向刚更新结构的指针。这样做可以使文件系统保持一致。在将来的章节中讨论日志结构文件系统(LFS)时，我们将学习更多关于这种技术的知识。LFS是COW的早起范例。
另一种方法时我们刚刚在威斯康星大学开发的方法。这种技术名为基于反向指针的一致性(Backpointer-Based Consistency，BBC)，它在写入之间不强制执行排序。为了实现一致性，系统中的每个块都会添加一个额外的反向指针。例如，每个数据块都引用它所属的inode。访问文件时，文件系统可以检查正向指针(inode或直接块中的地址)是否指向引用它的块，从而确定文件是否一致，并返回错误。通过向文件系统添加反向指针，可以获得一种新形式的惰性崩溃一致性。
最后，我们海滩锁了减少日志协议等待磁盘写入完成的次数的技术。这种新方法名为乐观崩溃一致性(optimistic crash consistency)，尽可能多地向磁盘发出写入，并利用事务校验和(transaction checksum)的一般形式，以及其它一些技术来检测不一致，如果出现不一致的话。对于某些工作负载，这些乐观技术可以将性能提高一个数量级。但是，要真正运行良好，需要稍微不同的磁盘接口。