1本章要解决什么

前两章（第 40、41 章）里，文件系统的一次操作（比如给文件追加一块）要修改好几个磁盘结构：inode、位图、数据块…… 可磁盘一次只处理一个请求，这些写必然有先有后。如果恰好在两次写之间断电，磁盘上就会留下"改了一半"的结构——这就是崩溃一致性问题（crash-consistency problem），也叫一致性更新问题（consistent-update problem）。

本章介绍三条路：老派的文件系统检查程序 fsck（先让它乱，重启时再全盘修）、现代主流的日志（journaling，即预写日志 write-ahead logging）（先在别处记下"我要做什么"，再动手）， 以及软更新、写时复制、反向指针等其他方案。下一章的日志结构文件系统（LFS）把"写时复制"推到极致；第 45 章的校验和则会再次出现在日志里。

2核心概念速览

3一个具体例子：给文件追加一块

工作负载很简单：打开一个已有文件，lseek() 到末尾，写入一个 4KB 块，关闭。文件系统也很小： inode 位图 8 位、数据位图 8 位、8 个 inode（编号 0–7，占 4 个块）、8 个数据块（编号 0–7）。现在只有 2 号 inode 被分配，它的唯一一个数据块是 4 号块 Da。

于是内存里有三个脏块要写回磁盘：新 inode I[v2]、新数据位图 B[v2]（00001100）、新数据块 Db。 它们通常不会在 write() 时立即写盘，而是先在页缓存（page cache / buffer cache）里待上 5 秒或 30 秒，之后文件系统才发出三个写请求。 问题是：三个写之间的任何时刻都可能断电。

4六种崩溃场景

三个写里"只成功了一个"有 3 种情况，"成功了两个"又有 3 种。原书逐一分析了它们：

我们真正想要的是原子地（atomically）把文件系统从一个一致状态（追加前）移动到另一个一致状态（追加后）。但磁盘一次只提交一个写，崩溃可能发生在任意两次写之间，所以做不到"天然原子"。下面的模拟器让你亲手制造每一种崩溃。

5方案一：文件系统检查程序 fsck

早期文件系统的做法很"懒"：允许不一致发生，重启时再修。典型代表是 UNIX 工具 fsck（读作 "eff-ess-see-kay"、"eff-ess-check"……）。 它在文件系统挂载之前运行（假设此时没有其他文件系统活动），完成后磁盘上的元数据应当重新自洽。注意它的目标只是元数据内部一致： 像"inode 和位图都更新了、但数据块是垃圾"这种情况，它根本看不出来。

按 McKusick 和 Kowalski 的论文，fsck 分几个阶段：

fsck 的根本问题是太慢：磁盘越来越大、RAID 越来越普及，扫描整个卷找出所有已分配块、读完整棵目录树可能要几分钟甚至几小时。 而且前提本身就有点不讲理——只为了三个块的更新，就把整块盘扫一遍。原书的比喻：钥匙掉在卧室地板上，你却从地下室开始把整栋房子搜一遍。能找到，但很浪费。

6方案二：日志（预写日志）

最流行的解法借自数据库领域的预写日志（write-ahead logging），文件系统里出于历史原因叫日志（journaling）。 第一个这么做的文件系统是 Cedar；今天的 Linux ext3/ext4、reiserfs、IBM JFS、SGI XFS、Windows NTFS 都用它。

基本想法：在原地覆盖之前，先在磁盘上一个众所周知的位置写一条小"笔记"，描述你将要做什么。写笔记是"预写（write ahead）"，笔记组织成"日志（log）"。 崩溃发生在覆盖过程中也不怕——回头看笔记，照着再做一遍即可；不必扫描整个磁盘。日志在更新时多做一点事，换来恢复时少做很多事。

数据日志（data journaling）

还是那个追加：要写 I[v2]、B[v2]、Db。数据日志（ext3 的一种模式）先把它们写进日志，形成一个事务（transaction）：

把块的原样内容写进日志叫物理日志（physical logging）；另一种逻辑日志（logical logging）只记"本次要把数据块 Db 追加到文件 X"，更紧凑、可能更快，但更复杂。 事务安全落盘后，再把 I[v2]、B[v2]、Db 写到它们的最终位置，这叫加检查点（checkpointing）。于是最初的协议是两步：① 日志写入，② 检查点。

顺序问题：能不能五块一起写？

一块一块地写、每写一块等它完成，太慢。理想情况是五个写一次性发出，变成一次顺序写。但这不安全：面对一个大写请求，磁盘内部可能调度，以任意顺序完成其中的小块。 比如磁盘先写完 TxB、I[v2]、B[v2]、TxE，之后才写 Db——如果恰好在这中间断电：

解决办法：分两步发出。先一次性发出除 TxE 以外的所有块；等它们全部完成后，再发出 TxE。 磁盘保证任何 512 字节的写要么完整发生、要么完全没发生（不会写一半），所以把 TxE 做成一个 512 字节的块，它的写入就是原子的。协议变成三步：

1. 日志写入（Journal write）：把事务内容（TxB、元数据、数据）写入日志，等待完成。
2. 日志提交（Journal commit）：写入提交块 TxE，等待完成；此时事务称为已提交（committed）。
3. 检查点（Checkpoint）：把更新的内容（元数据和数据）写到它们在磁盘上的最终位置。

恢复（Recovery）

崩溃可能发生在这串写的任意时刻：

• 在事务安全写入日志之前（第 2 步完成前）崩溃：很简单，这次挂起的更新直接跳过。
• 事务已提交、检查点未完成时崩溃：重启后恢复程序扫描日志，找出已提交的事务，按顺序重放（replay），再次把块写到最终位置。这种最简单的日志形式叫重做日志（redo logging）。
• 检查点进行到一半崩溃也没关系：最坏情况就是某些块在恢复时被再写一遍。恢复很少发生，几次多余的写不足为虑。

批量更新日志（Batching log updates）

在同一目录里连续创建 file1、file2：每次创建都要改 inode 位图、新文件的 inode、父目录的数据块（多了一个目录项）、父目录的 inode（修改时间变了）。 如果每次创建各自提交一个事务，同样这几个块会被反复写进日志。ext3 等文件系统的做法是把所有更新缓冲进一个全局事务（global transaction）： 在内存里把这些块标脏、加进当前事务的块列表，等到该写盘时（比如 5 秒超时）一次提交。这样就避免了大量多余的写流量。

让日志有限：循环日志

日志空间有限。一直往里追加事务会出两个问题：日志越长，恢复要重放的东西越多；更严重的是日志满了以后，再也提交不了新事务，文件系统就没法用了。 所以日志被当作循环（circular）数据结构反复使用：事务检查点完成后，释放它在日志里占的空间。一种办法是在日志超级块（journal superblock）（不要和文件系统超级块混淆）里记录最老和最新的尚未检查点的事务，其余空间都是空闲的。

加上释放这一步，数据日志的最终协议是四步：

1. Journal write：把事务内容（TxB 和更新内容）写进日志，等待完成。
2. Journal commit：写提交块 TxE，等待完成；事务提交。
3. Checkpoint：把更新内容写到文件系统中的最终位置。
4. Free：之后某个时刻，更新日志超级块，把该事务标记为空闲。

7元数据日志（有序日志）

数据日志恢复很快，但平时太慢：每个数据块都要写两遍（日志一遍、最终位置一遍），顺序写负载只能跑到磁盘峰值带宽的一半；日志和主文件系统之间还要来回寻道。 更简单、更常见的是有序日志（ordered journaling），也叫元数据日志（metadata journaling）：用户数据不进日志，日志里只有

那 Db 什么时候写？顺序很关键。如果在事务（I[v2]、B[v2]）提交之后才写 Db，而 Db 没来得及落盘就崩溃：恢复程序重放 I[v2] 和 B[v2]， 元数据是一致的，但 I[v2] 指向垃圾——Db 不在日志里，谁也救不回来。所以 ext3 等系统先写数据块，再写相关元数据：

1. Data write：把数据写到最终位置，等待完成（等待是可选的，见下）。
2. Journal metadata write：把 TxB 和元数据写进日志，等待完成。
3. Journal commit：写提交块 TxE，等待完成；事务（包括数据）提交。
4. Checkpoint metadata：把元数据写到最终位置。
5. Free：之后在日志超级块里标记事务空闲。

强制先写数据，就能保证指针永远不会指向垃圾。"先写被指向的对象，再写指向它的对象"是崩溃一致性的核心规则。 另外，第 1 步不必在第 2 步之前完成：数据、TxB、日志元数据可以同时发出，唯一的要求是第 1、2 步都在第 3 步（发出 TxE）之前完成。

实践中元数据日志比完整的数据日志更流行：Windows NTFS、SGI XFS 都用某种元数据日志；Linux ext3 可选 data、ordered、unordered（数据任何时候都可以写）三种模式。 这几种模式都保证元数据一致，区别只在用户数据的语义。

时间线（原书 Figure 42.1 / 42.2）

时间向下增长，每一行是某个写可以被发出（issue）或可能完成（complete）的逻辑时刻；虚线是必须遵守写顺序的地方。同一段里的写可以任意顺序完成。

注意：图中每个写的完成时刻是任意画的，真实系统里由 I/O 子系统决定，它可能为了性能重排写。我们唯一能依赖的顺序保证，就是协议正确性所要求的那些（虚线）。

8日志模拟器：随时拔电源

下面把两张时间线变成可以"拔电源"的模拟器。每一步是一次写的发出或完成（落盘）；同一批发出的写，磁盘可以按任意顺序完成（改"完成顺序种子"就会重排，种子 0 是原书时间线上的顺序）。 按下"⚡ 拔电源"后，已发出但没完成的写全部丢失，恢复程序扫描日志、决定重放还是丢弃，然后判断文件系统落在什么状态。拔电源保持按下时继续单步，可以逐个检查每个崩溃点。

9棘手情况：块复用与撤销记录

ext3 的主要作者 Stephen Tweedie 说过："整个系统里最可怕的部分是什么？……是删除文件。与删除有关的一切都很麻烦……你会做噩梦，梦见块被删除后又被重新分配。"

他举的例子（使用元数据日志，数据块不进日志）：目录 foo 的数据在块 1000。用户在 foo 里创建了一个文件，由于目录内容算元数据，foo 的目录块被写进了日志。 接着用户删除 foo 里的一切和 foo 本身，块 1000 被释放；然后创建新文件 bar，恰好复用了块 1000。bar 的 inode 进了日志，但 bar 的数据是普通用户数据，不进日志，直接写到块 1000。 此时崩溃，日志里这些事务都还在：重放时会把旧的 foo 目录内容写到块 1000——bar 的用户数据被旧目录内容覆盖了！

解决办法有好几种。比如：在块的删除被检查点移出日志之前，干脆不复用这些块。Linux ext3 的做法是在日志里加一种新记录——撤销记录（revoke record）： 删除目录时往日志写一条撤销记录；重放时先扫描所有撤销记录，被撤销的数据永远不会被重放。

10方案三：其他方法

11先预测再验证

12动手实验：在磁盘镜像上拔电源

cd labs/42-crash-consistency && make
./journal crashtest          # 4 种协议 × 每个崩溃点
./journal show nobarrier 4   # 看一个崩溃点：崩溃后/恢复后的整个镜像
./journal fsyncbench         # write / fdatasync / fsync / 原子 rename 的开销

== 无日志（原地写 I、B、Db）：共 3 次块写 ==
  写序列：I[v2] → B[v2] → Db
  崩溃于第 1个写之后 I[v2]      | 恢复：日志中没有事务 → 什么都不做
                           结果：不一致 + inode 指向垃圾
  崩溃于第 2个写之后 B[v2]      | 恢复：日志中没有事务 → 什么都不做
                           结果：元数据一致，但 inode 指向垃圾！

== 数据日志（data journaling）：共 9 次块写 ==
  写序列：J:TxB → J:I[v2] → J:B[v2] → J:Db → J:TxE → I[v2] → B[v2] → Db → JSB:free
  崩溃于第 4个写之后 J:Db       | 恢复：有 TxB 无匹配 TxE（未提交）→ 丢弃事务
                           结果：旧状态（一致；追加丢失）
  崩溃于第 5个写之后 J:TxE      | 恢复：发现已提交事务 → 重放（replay）
                           结果：新状态（一致，追加成功）

== 数据日志但不等屏障（磁盘把 TxE 排在 Db 前）：共 9 次块写 ==
  写序列：J:TxB → J:I[v2] → J:B[v2] → J:TxE → J:Db → I[v2] → B[v2] → Db → JSB:free
  崩溃于第 4个写之后 J:TxE      | 恢复：发现已提交事务 → 重放（replay）
                           结果：元数据一致，但 inode 指向垃圾！

== 有序元数据日志（ordered）：共 8 次块写 ==
  写序列：Db → J:TxB → J:I[v2] → J:B[v2] → J:TxE → I[v2] → B[v2] → JSB:free
  崩溃于第 1个写之后 Db         | 恢复：日志中没有事务 → 什么都不做
                           结果：旧状态（一致；Db 写了但没人指向，追加丢失）

$ ./journal show nobarrier 4     （恢复后的镜像，节选）
  [ 4] J3  GARBAGE(old block 4)        ← 日志里 Db 的槽还是旧垃圾
  [ 5] J4  TXE tid=1                   ← 但 TxE 已经落盘
  [ 7] I   INODE size=2 ptr=4,5,-1,-1
  [13] D5  GARBAGE(old block 4)        ← 重放把垃圾拷到了块 5
--- 检查：元数据一致，但 inode 指向垃圾！

$ ./journal fsyncbench
  write()                  200 次 4KB 追加：平均      6.8 us/次
  write() + fdatasync()    200 次 4KB 追加：平均   5021.0 us/次
  write() + fsync()        200 次 4KB 追加：平均   6078.9 us/次
  原子更新（tmp+fsync+rename+fsync目录）100 次：平均  13312.2 us/次
  config.txt 最终内容：version=99

13自测题

14常见误区与小结