6.1810 2024 第14讲：崩溃恢复，日志记录

本讲计划

• 问题：崩溃恢复
  • 崩溃导致磁盘上的文件系统不一致
• 解决方案：
  • 预写式日志 (write-ahead logging)

为什么需要崩溃恢复

什么是崩溃恢复？

• 你正在写入文件系统
• 然后电源故障
• 你重启
• 你的文件系统还能用吗？

问题所在：

• 多步骤操作期间发生崩溃
• 可能导致文件系统的不变性被破坏
• 重启后：
  • 坏情况：由于文件系统损坏再次崩溃
  • 更坏的情况：没有崩溃，但读/写了不正确的数据

示例：

• 创建文件 (create):

  $ echo hi > x
  // 上一讲的创建文件跟踪记录:
  bwrite: block 33 by ialloc   // 在 inode 块 33 中分配 inode
  bwrite: block 33 by iupdate  // 更新 inode (例如，设置 nlink)
  bwrite: block 46 by writei   // 写入目录条目，通过 dirlink() 添加 "x"
  bwrite: block 32 by iupdate  // 更新目录 inode，因为 inode 可能已更改

  • 在 iupdate 和 writei 之间崩溃
    • 分配了文件 inode
    • 崩溃：inode 不是空闲的但也没被使用 —— 还不是太糟
  • 如果文件系统先写了 46 和 32，然后才写 33
    • 如果在 32 和 33 之间崩溃，那么目录项指向一个空闲的 inode —— 这是灾难！
    • 再次崩溃，或者更糟的是，如果该 inode 被分配给其他东西

• 写入文件 (write):

  • inode 的 addrs[] 和 len
  • 间接块
  • 块内容
  • 块空闲位图
  • 崩溃：inode 引用了一个空闲块 —— 灾难！
  • 崩溃：块不是空闲的但也没被使用 —— 还不是太糟

• 删除文件 (unlink):

  • 块空闲位图
  • 空闲 inode
  • 删除目录项

我们能期望什么？

• 在重启并运行恢复代码后
  1. 文件系统的内部不变性得到维护
     • 例如，没有块同时在空闲列表和文件中
  2. 除了最后几个操作外，所有操作都保留在磁盘上
     • 例如，我昨天写的数据被保留了
     • 但也许我在崩溃时正在写的数据没有
     • 所以用户可能需要检查最后几个操作
  3. 没有顺序异常
     • echo 99 > result ; echo done > status

正确性与性能常常冲突

• 磁盘写入很慢！
• 安全性 => 尽快写入磁盘
• 速度 => 不要写入磁盘 (批量处理, 写回缓存, 按磁道排序等)

崩溃恢复是一个反复出现的问题

• 出现在所有存储系统中，例如数据库
• 多年来，人们在解决方案上投入了大量工作
• 许多巧妙的性能/正确性权衡

日志解决方案

最流行的解决方案：日志记录 (logging / journaling)

• 目标：相对于崩溃，系统调用是原子的
• 目标：快速恢复 (不需要长达一小时的 fsck)

我们将分两步介绍日志记录

• 首先是 xv6 的日志，它只提供安全性和快速恢复
• 然后是 Linux EXT3，它在正常操作中也很快

日志记录的基本思想

• 你想要原子性：一个系统调用的所有写入，要么全部发生，要么全部不发生
  • 让我们称一个原子操作为“事务”
• 在磁盘上的日志中记录系统调用将要做的所有写入 (log)
• 然后在磁盘上记录“完成” (commit)
• 然后执行文件系统的磁盘写入 (install)
• 在崩溃+恢复时：
  • 如果日志中有“完成”标记，则重放日志中的所有写入
  • 如果没有“完成”标记，则忽略日志
• 这就是 预写式日志 (WRITE-AHEAD LOG)

预写式日志规则

• 在一个事务的所有写入都记录在磁盘上的日志中，并且日志中的写入被标记为已提交之前，不要将该事务的任何写入安装到磁盘上。

为什么有这条规则？

• 一旦我们将一次写入安装到磁盘上的文件系统，我们就必须完成该事务的所有其他写入 —— 这样事务才是原子的。我们必须为第一次安装写入后可能发生的崩溃做好准备，所以其他写入在崩溃后必须仍然可用 —— 在日志中。

日志记录是神奇的

• 复杂可变数据结构的崩溃恢复通常很难
• 日志记录通常可以分层应用在现有的存储系统上
• 并且它与高性能兼容 (下一讲的主题)

xv6 日志记录概述

xv6 日志表示

• [图：缓冲区缓存，内存中的日志块编号数组，磁盘上的文件系统树，磁盘上的日志头和日志块]
• 写入时，将块号添加到内存中的数组
• 将数据本身保留在缓冲区缓存中 (固定/pin)
• 提交时 (on commit)：
  • 将缓冲区写入磁盘上的日志
  • 等待 磁盘完成写入 (“同步”)
  • 将日志头扇区写入磁盘
    • 包含块号
    • 非零的 "n"
• 提交后 (after commit)：
  • 将日志中的块安装 (写入) 到它们在文件系统中的最终位置
  • 解除固定 (unpin) 块
  • 将磁盘上日志头中的 "n" 写为零

磁盘上日志头中的 "n" 值表示提交

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

xv6 磁盘布局与块号

• 2: 日志头
• 3: 日志记录的块
• 32: inodes
• 45: 位图
• 46: 内容块

让我们看一个例子。

• 我修改了 bwrite() 来打印底层的磁盘写入，即在事务提交期间发生的磁盘写入。

$ echo a > x

// create
bwrite 3    // inode, 33
bwrite 4    // directory content, 46
bwrite 5    // directory inode, 32
bwrite 2    // commit (block #s and n)
bwrite 33   // install inode for x
bwrite 46   // install directory content
bwrite 32   // install dir inode
bwrite 2    // mark log "empty"
// write
bwrite 3
bwrite 4
bwrite 5
bwrite 2
bwrite 45   // bitmap
bwrite 595  // a  (注意: bzero 被吸收了)
bwrite 33   // inode (file size)
bwrite 2
// write
bwrite 3
bwrite 4
bwrite 2
bwrite 595  // \n
bwrite 33   // inode
bwrite 2

让我们看看第二个事务，一个 write()

• 首先 file.c:syswrite

  • 计算在日志满之前我们可以写多少个块
  • 在一个事务中写入那么多块

• 结合 fs.c:writei

  • begin_op()
    • bmap() -- 可以写入位图，间接块
      • log_write 来 bzero 新块
    • bread()
    • 修改 bp->data
    • log_write()
      • 吸收 bzero
    • iupdate() -- 写入 inode
  • end_op()

• log.c 中的 begin_op():

  • 需要指明哪一组写入必须是原子的！
  • 需要检查日志是否正在提交
  • 需要检查我们的写入是否能装入日志的剩余空间

• log_write():

  • 将扇区号添加到内存中的数组
  • bpin() 将块固定在缓冲区缓存中，这样 bio.c 就不会驱逐它

• end_op():

  • 如果没有未完成的操作，则提交

• commit():

  • 将更新的块从缓存复制到磁盘上的日志
  • 在磁盘上的日志头中记录扇区号和“完成”标记
  • 安装写入 —— 从磁盘上的日志复制到磁盘上的文件系统
    • bunpin() 将从缓存中解除固定 —— 现在它可以被驱逐了
  • 从日志中擦除“完成”标记

如果在事务期间崩溃会发生什么？

• 内存丢失，只剩下崩溃时的磁盘状态
• 内核在启动期间，在使用文件系统之前调用 recover_from_log()
  • 如果日志头块显示“完成”：
    • 将块从日志复制到磁盘上的真实位置
• 磁盘上的日志里有什么？
  • 提交前崩溃
  • 提交期间崩溃 —— 提交点？
  • install_trans() 期间崩溃
  • 重启后，在 recover_from_log() 中崩溃
• 注意：多次重放日志是可以的！
  • 只要没有其他活动介入

注意 xv6 假设磁盘是“故障-停止”(fail-stop)的

• 它要么正确地完成写入，要么不写入
  • 例如，由于电源故障，它可能无法完成最后一次写入
• 因此：
  • 没有部分写入 (每个扇区的写入是原子的)
  • 没有乱写
  • 扇区不会衰减 (没有读取错误)
  • 不会读到错误的扇区

挑战

挑战：防止从缓存写回

• 系统调用可以安全地更新一个缓存的块，
  • 但在事务提交之前，该块不能被写入文件系统
• 这很棘手，因为例如缓存可能会空间不足，
  • 并试图驱逐一些条目以便
  • 读取和缓存其他数据。
• 考虑创建文件的例子：
  • 将脏的 inode 写入日志
  • 将目录块写入日志
  • 驱逐脏的 inode
  • 提交
• xv6 解决方案：
  • 确保缓冲区缓存足够大
  • 将脏块固定在缓冲区缓存中
  • 提交后，解除固定块

挑战：系统调用的数据必须能装入日志

• xv6 解决方案：
  • 计算每个系统调用写入的块数的上限
    • 设置日志大小 >= 上限
  • 将一些系统调用分解成几个事务
    • 例如，大的 write()
    • 因此：大的 write() 不是原子的
      • 但崩溃会留下一个正确的写入前前缀

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

• 必须允许来自多个调用的写入在日志中
• 提交时必须全部写入它们
• 但是不能写入仍在事务中的调用的数据

xv6 解决方案

• 如果新系统调用的数据可能无法装入日志，则不允许其开始
  • 必须等待当前调用完成并在日志中留出足够空间
  • 或者，等待并发调用提交，从而释放日志
• 当进行中的调用数量降至零时
  • 提交
  • 释放日志空间
  • 唤醒等待的调用

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

• log_write() 只影响内存中的缓存块
• 所以一个缓存块可能反映了多个未提交的事务
• 但安装只在没有进行中的事务时发生
  • 所以安装的块只反映已提交的事务
• 对性能有好处：“写入吸收” (write absorption)

总结

xv6 的日志设计有什么好处？

• 由于预写式日志，正确性得到保证
• 良好的磁盘吞吐量：日志自然地批量处理写入
  • 但数据磁盘块被写入两次
• 并发性

xv6 的日志记录有什么问题？

• 效率不是很高：
  • 每个块都被写入两次 (日志和安装)
  • 即使只修改了几个字节，也记录整个块
  • 同步写入每个日志块
    • 可以将它们作为一批写入，只同步写入头部
  • 日志写入和安装写入都是“急切的” (eager)
    • 两者都可以是“懒惰的” (lazy)，以获得更多的写入吸收
    • 但仍必须先写入日志
• 对无法装入日志的操作处理有困难
  • unlink 在截断文件时可能会弄脏许多块