Lecture 23–24: 文件系统崩溃恢复（File System Crash Recovery）
Lecture 23–24: 文件系统崩溃恢复（File System Crash Recovery）
概述
崩溃恢复对操作系统其余部分很简单（重启即清零），但对文件系统是生死攸关的：用户期望磁盘上的信息在崩溃后依然存在。本讲梳理三大方案：崩溃后修复（fsck）、有序写入（ordered writes）、预写日志（write-ahead logging / journaling）——最后者是现代 ext4/NTFS 与 Assign8 的核心。
核心概念与系统机制图解
崩溃恢复为什么难
- 数据丢失：延迟写意味着最近约 30 秒的修改可能还在内存（块缓存）里没上盘。
- 不一致（Inconsistency）：一次修改往往涉及多个块（如加块到文件 = 更新空闲位图 + 更新 inode），磁盘无法原子地完成多块写；崩溃可能落在中间：
- 空闲位图已更新但 inode 还没指向新块 → 块泄漏（块既不在任何文件里也不在空闲表中）；
- 新目录项已写但 inode 链接数未更新 → 计数与目录不一致。
- 块缓存可能重排写入顺序。
方案 1：崩溃后修复——fsck（file system check）
启动时运行 fsck:
1. 检查"干净位(clean bit)": 上次正常关机 → 跳过
2. 否则全盘扫描元数据: inode、间接块、空闲位图、目录
3. 找出不一致并修复
典型不一致与修复:
● 块既在 inode 又在空闲位图 → 从空闲位图移除(防双重分配)
● inode 链接数与目录项不符 → 修正计数
● 同一块属于两个 inode(先删A后建B, 延迟写乱序) → 随机选一个归属/复制块/两边都删
● inode 计数>0 但不在任何目录 → 放入 /lost+found 目录
- fsck 的局限：
- 恢复一致性但不保证不丢信息（恢复后系统可能仍不可用，如高层目录损坏）；
- 安全问题：块可能在崩溃中从密码文件迁移到别处；
- 太慢：现代大磁盘不可接受——5TB 全盘顺序读约 8 小时，随机读 10% 需数周。
方案 2：有序写入（Ordered Writes）
- 思想：规定写盘顺序，把”不一致”换成”较轻的泄漏”。
- 例子：给文件加一块，按此顺序写：
i. 先写空闲位图块(标记新块已分配) ii. 再写 inode(指向新块) 崩溃分析: ● 只写完 i → 位图说空闲、inode 没指 → 无问题 ● 写完 i 和 ii → 一致 ● 写完 i 没写 ii → 块"泄漏"(既不在文件也不空闲) —— 比不一致轻, 可后台 fsck 回收 结论: 绝不出现"同一块同时在空闲表和 inode 中"(双重分配) - 通用原则：指针指向的数据要先初始化好；重用资源前先清掉旧指针。
- 代价：简单的有序写 = 同步写（write-through），拖慢文件操作；改进版在块缓存中记录依赖关系（写 inode 前先写位图块），避免同步写，但依赖环需强制写打破——实现微妙。
方案 3：预写日志（Write-Ahead Logging / Journaling）
- 思想（数据库界老方法）：先把”这次操作要改什么”追加写进一个日志文件，再执行实际的块更新（顺序随意）。
操作: 给 inode 862 加块 99421 (索引93) 步骤: 1. 写日志: "加块99421到inode862第93块" (append-only, 顺序写无寻道) 2. 执行实际块更新(任意顺序) 3. 事务完成后可截断日志 崩溃恢复: 重放日志, 完成所有未完成更新 保证: 一旦操作开始, 最终必然完成 - 日志条目的两种形式：
- 逻辑操作：
把块 99421 加到 inode 862 的第 93 项； - 物理补丁：
把块 6159972 偏移 324 处的 4 字节改为 9942； - 条目必须幂等（idempotent）——重放多次结果相同（恢复过程本身也可能崩溃）。
- 逻辑操作：
- 一致性组（事务，transaction）：一次逻辑操作可能含多个日志条目；要么全部生效、要么全不生效。用”事务开始/结束”标记日志分组（Assign8 的做法）；只处理完整的事务。
- 检查点（checkpoint）与日志截断：日志无限增长恢复会变慢；定期记录”日志头位置 + 冲刷所有脏块”，之后截断日志。
- 记多少？ 通常只记录元数据（空闲位图、inode、间接块）；记录全部文件数据太贵。
日志方案评价
| 优点 | 缺点 | | :— | :— | | 恢复快（只重放日志） | 每次元数据操作前要同步写日志 | | 消除不一致 | 延迟写仍可能丢失最近数据（需 fsync） | | 日志顺序写、无寻道 | 磁盘自身故障仍需复制/备份 | | 元数据可用延迟写（有日志兜底） | — |
- 延迟日志写：日志条目只需在”相关块写盘之前”落盘（不需要同步写）——把耐久性（durability）与一致性（consistency）分离。
- 结论（Lecture 23）：性能、耐久、一致性三者不可兼得——必须决定想从哪些故障中恢复。
代码示例与系统调用解说
示例：重放日志恢复一致性（Assign8 的核心，约 10–15 行）
// 伪代码: 崩溃后重放 write-ahead log
// log 中的每条记录是 "物理补丁" 或 "分配/释放标记", 按事务分组
void recover(std::vector<LogEntry>& log) {
for (const auto& txn : groupByTransaction(log)) {
if (!txn.complete) continue; // 不完整的组(崩溃中断)直接跳过
for (const auto& entry : txn.entries) {
switch (entry.kind) {
case PATCH: // 覆盖磁盘块中若干字节
writeBlock(entry.block, entry.offset, entry.data);
break;
case MARK_FREE: // 把块标为空闲(更新位图)
freemap.set(entry.block, FREE);
break;
case MARK_ALLOCATED:
freemap.set(entry.block, ALLOCATED);
break;
}
}
}
}
【代码做了什么？】 按事务分组扫描日志：只重放完整事务（崩溃发生在事务中间则整组丢弃，保证原子性），对每条记录执行补丁或位图更新。
【系统机制透视】
- 幂等性：重放可能被再次崩溃打断、再次重放——补丁必须”重复应用结果相同”（覆盖写天然幂等）。
- 日志先于数据：若先改数据块再写日志，崩溃后日志里没有记录可重放——所以必须”写前日志”（write-ahead）。
- 与 Assign8 的衔接：作业里你用 FUSE 挂载 V6 文件系统，给所有元数据更新加日志，崩溃后用上面的逻辑恢复——你会亲身体会”10–15 行代码背后是整套一致性理论”。
关键要点
- 崩溃恢复难在：延迟写丢数据 + 多块更新不一致 + 缓存重排写序。
- fsck：全盘扫描修复，保证一致性但慢、可能丢信息——大磁盘不可接受。
- 有序写入：用写序把”不一致”换成”泄漏”，但同步写拖慢性能。
- 预写日志：先记日志后改数据、事务原子性、幂等条目、检查点截断——现代文件系统（ext4/NTFS）的标准答案。
- 性能 / 耐久 / 一致性三者不可兼得，必须明确故障模型。
常见陷阱与注意事项
- 日志写与数据写顺序颠倒：必须先日志后数据，否则崩溃无法恢复。
- 日志条目非幂等：重放两次产生不同结果（如”分配计数++”）。
- 重放不完整事务：必须整组跳过，否则破坏事务原子性。
- 忘记 fsync 关键数据：延迟写 + 崩溃 = 数据丢失。
- 日志无限增长：不设检查点，恢复时间越来越长。
思考题
- 问题：为什么”块既在 inode 里又在空闲位图里”比”块泄漏”更严重？
- 答案：前者是双重分配——两个文件可能共享同一块，写入会互相覆盖、数据损坏且难修复；后者只是少了一块可用空间（泄漏），数据完好、可通过后台回收。
- 问题：预写日志如何保证”操作要么全部生效要么全不生效”？
- 答案：用事务标记把相关日志条目组成一致性组；恢复时只重放完整的事务，不完整事务（崩溃中断）整组丢弃。配合”先写日志再改数据”，就能保证已提交操作最终完成。
- 问题：为什么日志条目必须幂等？
- 答案：恢复过程本身可能再次崩溃，日志可能被重放多次；只有幂等条目（重复应用结果不变）才能保证多次重放与一次重放效果一致。