文件系统是操作系统中管理用户数据的重要模块。其中一项重要的任务就是确保用户数据的在系统突然崩溃之后，系统能够恢复出完整、一致的用户数据。本文将会分析两种流行的文件系统，Journaling File System 和 Log-structured File System是如何确保数据的一致性。本文主要参考了OSTEP的42和43章节，强烈推荐任何一位学习操作系统的同学去阅读这本教材。
什么是一致性问题
我们知道，内存的速度是远远高于磁盘，因此文件系统为了加速文件的读取，往往会使用内存页缓存一些磁盘的数据以加快文件的读写速度，而文件系统也会在适当的时机，再将脏页回写到磁盘中(即writeback操作)。这种回写操作，一般会涉及到元数据的更改(例如on-disk inode)以及文件数据的更改。一般而言，为了实现高性能，元数据的更改和文件数据的更改往往不是同步的，而是异步的。因此，如果系统突然宕机，由于它们元数据和文件数据回写的异步性，可能会引起一致性问题。
一致性问题种类
我们考虑一个简单的文件系统的on-disk结构，这个文件系统包括一个inode bitmap (8 bits，每一个bit表示一个inode)，一个data bitmap (8 bits，每一个bit表示一个data block)，一个inodes区域 (存放inode的磁盘区域，一共8个)，一个data blocks 区域 (保存文件数据的磁盘区域，一共8个)。以及一个场景: 一个进程写入一个data block到一个空文件。
如下图所示，这个操作会首先在磁盘的free space中分配一个inode (即下图的
I[v1]
，对应inode号是2，对应的inode bitmap也会被标记状态为已分配)，然后写入一个data block (即下图的
Da
，对应data blocks区域的地址是4，对应的data bitmap也会被标记状态为已分配)。当文件读数据的时候，我们是通过inode找到对应的data block，所以inode需要保存对应的data block的地址建立inode-data映射，我们需要把
Da
的地址4写入到
I[v1]
中，请注意这个隐含的关系。因为这是这个文件的第一次更新inode，所以我们将这次更新称为v1更新，所以inode用
I[v1]
表示。
如下图所示，如果我们继续往这个文件写入一个data block的数据，那么data blocks区域肯定要更新(即
Db
，对应的data blocks地址是5)，对应的data bitmap也要做第二次更新(即
B[v2]
)，inode也需要记录新写入的data block的地址(即
Db
)，因此inode也需要更新，得到
I[v2]
。
如前面介绍，为了提高性能，对应inode bitmap、data bitmap、inodes、data blocks的更新都可能是异步的，文件系统无法确保它们都同时写入。而崩溃在任何时刻都可能出现，因此可能文件系统可能会出现一致性问题。我们用第二次写入作为例子，分析有哪些一致性问题:
- 只有data block (
Db
- 只有inode (
I[v2]
Db
Db
- 只有data bitmap (
B[v2]
- inode (
I[v2]
B[v2]
Db
Db
Db
- inode (
I[v2]
Db
B[v2]
- data bitmap (
B[v2]
Db
I[v2]
接下来，我们将会探讨Journaling File System 和 Log-structured File System如何分别解决这些问题。
Journaling File System 日志文件系统
日志文件系统(Journaling File System，或者说JFS) 是一类被广泛使用的解决文件系统一致性的技术。JFS通过journaling去记录一些文件系统操作，然后再回写这些操作到磁盘的策略，实现一致性保证，使用这些技术的包括ext3/ext4，XFS等主流文件系统。Journaling的核心思想是:
在更新磁盘上的数据之前，例如更新bitmap，inode，data之前，我们先将这些操作作为日志(log)，先写入到其他位置(往往是磁盘的某个特定大小的区域)。文件系统会不断写日志(log)，而这些保存log的区域一般像一个数组一样将log组织起来，每一个数组单元就是一个log，文件系统在更新(write)磁盘的数据之前都会先写入到log中，所以我们也将journalling称为write-ahead log技术。
当系统崩溃时，文件系统恢复时就会检查日志记录，看看崩溃前的一刻哪些操作是完成的(成功写入到磁盘)，哪些没有完成，从而可以恢复文件系统的一致性。
我们使用ext3文件系统作为例子，下图是一个ext3文件系统的on-disk结构。它比我们前面讨论的简单文件系统稍微复杂点。这里每一个group相当于前面介绍的简单文件系统的on-disk结构，也是包含了data bitmap，inode bitmap，inodes，data blocks等结构。不同之处就是它在磁盘上多分配了一个journal区域，用于保存文件操作的日志。由于文件系统包括data和metadata操作，所以它们也有相应的journaling的方法，我们分别讨论。
Data Journaling
我们回到最开始介绍的例子，即需要写入
Db
，
B[v2]
，
I[v2]
到磁盘的例子。前面我们的操作是让这些三个需要写入磁盘的操作，分别写入到磁盘中。那么现在，我们可以将他们打包在一起写入log (或者说journal)，如下图所示。这里
TxB
~
TxE
表示一个log entry，箭头表示这个journal区域可能包含多个log entry，目前我们只使用一个log entry。
TxB
~
TxE
也表示一系列操作的组成的一个事务(transaction)，
TxB
是这个事务的头，包含这些操作需要写入到磁盘的位置信息(例如
I[v2]
，
B[v2]
，
Db
各自在磁盘的位置，一共三个blocks的地址)，以及一个本次事务关联的transaction identifier (TID) 。
TxE
标识事务的结束位置，也包含和
TxB
相同的TID。我们写入log的操作称为journal write。
如果这个事务被顺利写入到磁盘，那么我们可以就根据
TxB
记录的磁盘的三个blocks的位置信息，将
I[v2]
，
B[v2]
，
Db
各自写入到磁盘的位置，我们将这个操作称为checkpointing。如果这三个blocks都成功写入了磁盘，那么我们说这个文件系统被成功checkpointed，用于记录log的journal区域(即上图)也可以被释放，给其他操作使用。
讨论: 对于前面的例子，我们需要写入
TxB
，
I[v2]
，
B[v2]
，
Db
，
TxE
总共5个blocks。如果让这5个blocks一个个按顺序写入，这显然会影响性能。如果这5个blocks异步写入依然会存在一致性问题，例如
TxB
，
B[v2]
，
Db
，
TxE
成功写入到磁盘后，系统就马上崩溃，
I[v2]
，还没有写入。因此我们可以使用折衷的办法，异步写入
TxB
，
I[v2]
，
B[v2]
，
Db
，等它们都成功后，再写入
TxE
。所以我们可以将journaling分解为3个操作:
- Journal write：将
TxB
- Journal Commit：写入
TxE
- Checkpoint：将事务中的数据，分别各自回写到各自的磁盘位置中。
Recovery恢复: 我们利用上面的三个操作去描述文件系统是如何保证一致性的。
- 崩溃发生在Journal Commit完成前：那么文件系统可以丢掉之前写入的log。由于磁盘具体位置的bitmap，inodes，data blocks都没变，所以可以确保文件系统一致性。
- 崩溃发生在Journal Commit后，Checkpoint之前：那么文件系统在启动时候，可以扫描所有已经commited的log，然后针对每一个log记录操作进行replay，即recovery的过程中执行Checkpoint，将log的信息回写到磁盘对应的位置。这种操作也成为redo logging。
- 崩溃发生在Checkpoint完成后：那无所谓，都已经成功回写到磁盘了，文件系统的bitmap、inodes、data blocks也能确保一致性。
Journal是如何保存在磁盘的: 如前面所说，journal区域是磁盘一段特定空间，显然它是空间是有限的，但是我们无法确定有多少写入操作会同时发生，因此文件系统一般会采用circular log去解决这个问题，即记录journal区域中每一个log entry的生成时间，当log entry不够时，则尽快Checkpoint这个log entry，以腾出空间给新的写入操作。所以journal区域需要一个journal super block去管理这些与log entry有关的元数据信息，如下图所示。这里每一个Tx1到Tx5表示都表示一个log entry。所以出了前面介绍的Journal write，Journal Commit，Checkpoint操作以外，我们还多了一个free操作以释放log entry。
Data Journaling的开销: 经过前面的分析，我们已经得到一个完整的data journaling方案，但是这存在一个问题: 每一个data block需要写入磁盘两次 (即double write问题)，使用最开始的例子即是
Db
要先通过Journal write写入到Journal区域，再通过Checkpoint写入到磁盘，会产生大量的开销。而且一般而言，崩溃是一个比较少出现的场景，为了严格的一致性去使用data journaling也不是非常值得的。
Metadata Journaling
回顾一开始对崩溃的场景的分析，如果inode和bitmap的写入磁盘了就可以实现metadata consistent，这可以实现文件系统的一致性。一般而言，file data的写入量会远远比metadata要大(如，写入100个data block，可能只需要更新一个inode block和一个bitmap block)。所以为了解决double write问题，文件系统可以只针对metadata做journal。以确保metadata consistent，如下图所示，
Db
没有写入到log当中：
然而，如果在事务完成前之后，
Db
的磁盘写入还没完成就发生崩溃，那么inode会指向一个不确定数据的data block，因为这个事务已经完成了，文件系统重启的时候会replay这个事务。这种情况下，metadata journaling虽然确保了文件系统的一致性，但是无法确保文件数据的一致性。因此有一些文件系统，如ext3/4，的journal机制会在指定的情况下，会确保data blocks (
Db
) 先写入到磁盘，再提交metadata journal。所以我们可以将journaling再进一步分解为5个操作:
- data write：写入数据到磁盘的对应位置，等待它的完成 (也可以不等，看设定的模式)。
- Journal metadata write：将
TxB
- Journal Commit：写入
TxE
- Checkpoint metadata：将事务中的metadata的操作相关数据，分别各自回写到各自的磁盘位置中。
- free：释放journal区域的log entry。
在ext3/ext4中，这对应三种日志模式:
Journal Mode: 操作的metadata和file data都会写入到日志中然后提交，这是最慢的。
Ordered Mode: 只有metadata操作会写入到日志中，但是确保数据在日志提交前写入到磁盘中
Writeback Mode: 只有metadata操作会写入到日志中，且不确保数据在日志提交前写入。
Log-structured File System 日志结构文件系统
日志结构文件系统(Log-structured File System，或者说LFS) 是一类执行异地更新(outplace-update)策略的文件系统。无论是顺序写还是随机写，LFS都会将数据顺序地写入到新的data block中，然后再将旧的data block无效掉。这种策略可以将随机写转换为顺序写，以优化文件系统的写入性能。
我们继续使用前面的简单文件系统作为例子，但是我们目前考虑这个文件系统的写不是就地更新的，而是异地更新。例如，一开始
Db
写入到磁盘data blocks区域地址是5的位置，那么下次用户要更新
Db
这个数据时，它不会重新写到5这个位置，而是按顺序地写入到6这个位置。如果不断更新，那么就会将新更新的数据写入到7，8，9，… ，等位置。在LFS中，我们称为将目前写入磁盘的位置称为log (注意这里的含义和JFS是有不同的)，由于数据是不断顺序地写入到磁盘，而且是结构化的，所以也称为log-structured文件系统。
接下来我们考虑LFS的一致性因素。它与JFS类似，也有bitmaps，inode block，data block，除此以外还有checkpoint区域 (类似于JFS的journal区域)用于确保文件系统的一致性。LFS的checkpoint的含义和JFS不同，所以也需要注意区分。使用F2FS文件系统作为例子，可以参考这里。