MIT 6.1810 · 第 18 课 · rtm

崩溃恢复

断电后文件系统还能用吗？本节课探讨崩溃恢复问题及其解决方案——预写日志（Write-Ahead Logging）。

问题：崩溃恢复

什么是崩溃恢复？

1. 进程创建文件、目录等
2. 然后断电
3. 重启后，文件系统还能用吗？

具体例子

操作	崩溃风险
创建文件	inode 已分配但目录项未写入 → inode 泄漏
写入数据	inode 指向未分配的块 → 读取垃圾数据
删除文件 (unlink)	目录项指向已释放的 inode → 灾难性后果

我们希望达到什么目标？

1. 文件系统内部不变量保持——没有块既在空闲列表中又在文件中
2. 除最后几个操作外，所有操作都被保留——昨天的数据保留，正在写的可能丢失
3. 没有顺序异常——如果程序先写 result 再写 status，不能出现 status 存在但 result 不存在

解决方案：预写日志 (Write-Ahead Logging)

基本思想

1. 将要做的所有写入记录到日志中
2. 在磁盘上写入"完成"标记（提交点）
3. 然后执行实际的 FS 写入（安装）
4. 崩溃+恢复时：如果日志有"完成"，重放日志；否则忽略

预写日志规则

为什么这个规则有效？

• 一旦安装了第一个写入，就必须完成事务的所有其他写入（保证原子性）
• 崩溃后，其他写入必须在日志中仍然可用

xv6 日志实现

日志表示

┌─────────────┐     ┌──────────────┐     ┌─────────────┐
│  缓冲缓存    │     │  磁盘 FS 树   │     │  磁盘日志    │
│  (buffer    │     │  (实际文件    │     │  (事务记录   │
│   cache)    │     │   系统)       │     │  + 提交点)   │
└─────────────┘     └──────────────┘     └─────────────┘

提交流程

1. 写入时：将块号添加到内存数组，数据保留在缓冲缓存中（固定）
2. 提交时：
• 将缓冲区写入磁盘日志
• 等待磁盘完成写入（同步）
• 写入日志头扇区（块号 + 非零的 "n"）
3. 提交后：将块安装到 FS 中的实际位置，解除固定，将 "n" 写零

日志头中的 "n" 值

• 非零 = 已提交：日志内容有效，是完整事务
• 零 = 未提交：可能不完整，恢复时应忽略日志
• 写入非零 "n" 是提交点

示例：创建文件

$ echo > x
log_write 34   // ialloc
log_write 34   // iupdate
log_write 47   // writei (目录项)
log_write 33   // iupdate (目录 inode)
log_write 34   // iupdate (itrunc)
// 提交前没有磁盘写入！
bwrite 3       // 写入日志块 (x 的 inode)
bwrite 4       // 写入日志块 (目录块)
bwrite 5       // 写入日志块 (目录 inode)
bwrite 2       // 提交（写入日志头）
bwrite 34      // 安装 inode
bwrite 47      // 安装目录内容
bwrite 33      // 更新目录 inode
bwrite 2       // 标记日志为空
// 同一块的多次写入合并为一次
// 每个块写两次：日志 + 安装

崩溃场景分析

崩溃时机	后果
提交前	日志头 n=0，恢复时忽略日志，操作未发生
提交期间	提交点是单个扇区写入，原子的；要么提交要么不提交
安装期间	恢复时重放日志，完成安装
恢复期间	再次重放日志（幂等）——只要没有其他活动介入就没问题

代码结构

sys_open()                     // sysfile.c
  → begin_op() / end_op()      // 标记事务边界
  → create()
      → ialloc()               // 分配 inode
          → log_write()        // 记录到日志
      → iupdate()              // 更新 inode
      → dirlink()              // 创建目录项
          → writei()
              → iupdate()
  → itrunc()
      → iupdate()

begin_op()                      // log.c
  → 检查日志是否正在提交
  → 检查写入是否能容纳在日志中

log_write()                     // log.c
  → 添加扇区号到内存数组
  → bpin() 固定缓冲区

end_op()                        // log.c
  → 如果没有未完成操作，提交

commit()                        // log.c
  → 将更新的块从缓存复制到磁盘日志
  → 在磁盘日志头中记录扇区号和 "done"
  → 安装写入（从磁盘日志复制到磁盘 FS）
  → bunpin() 解除固定
  → 擦除日志中的 "done"

挑战与 xv6 解决方案

挑战 1：防止写回缓存

挑战 2：系统调用数据必须能容纳在日志中

• 计算每个系统调用写入的块数上界
• 将大操作拆分为多个事务（如大文件写入）

挑战 3：允许并发系统调用

• 允许多个调用的写入在日志中
• 提交时写入所有
• 但不能写入仍在事务中的调用的数据

挑战 4：块可能在事务中被多次写入

解决方案：日志只影响内存中的缓存块，安装只在没有进行中的事务时发生 → 写入吸收 (write absorption)优化

挑战 5：孤儿文件/目录

解决方案：ireclaim 在重启时检查孤儿文件

挑战 6：进程何时知道其写入在磁盘上？

典型方案：sync() 系统调用——仅在所有脏块写入磁盘后返回

xv6 日志：优缺点

优点	缺点
预写日志保证正确性	每个块写两次（日志 + 安装）
日志自然批量化写入，磁盘吞吐量好	即使只修改几个字节也记录整个块
支持并发	同步写入日志块（可以批量化）
	不适合操作超出日志容量的情况

要点总结

测验

延伸阅读

• xv6 手册
• Linux ext3/ext4 文件系统日志实现