crash recovery

崩溃恢复

这里的Crash safety并不是一个通用的解决方案，我们关心的是包含了多个步骤的文件系统操作过程中发生的故障。

崩溃成因与创建写入文件

• 断电
• 内核崩溃

磁盘是持久性存储设备，但是对一个fs操作可能包含多个对磁盘的操作，如果这个过程被打断则 fs 可能会处于错误的状态

例如，创建一个文件需要以下步骤：

x在根目录下

如果在图示位置断电，这意味着我们分配了一个 inode，但是它不处于任何目录中——我们永远丢失了这个inode，无法从任何目录找到他

如果先设置目录再标记inode已分配，则有可能导致重新分配一个已分配的inode

文件系统有一个属性：每一个磁盘block要么是空闲的，要么是只属于一个文件

下一个部分：写入文件

bitmap中分配数据块–写入hi–更新inode：size 与 data addr

在图示的位置发生崩溃则会丢失一个数据块。同样的，调整操作的顺序不会让情况变得更好

我们需要让这一系列操作是一个原子性的操作，即一个事务

logging 概述

XV6的实现非常简单，几乎是最简单的实现logging的方法。但是即使是这么基本的logging实现，也包含了一些微妙的问题，例如性能

logging 思想来源于数据库，它有一些属性：

• 保证一个事务操作的原子性
• 支持快恢复，不需要大量的操作才能恢复一个文件系统
• 原则上来说，它可以非常的高效，尽管我们在XV6中看到的实现不是很高效

基本思想是，在写入磁盘时，并不会直接把数据写入目标块，而是写入log块，并记录它应该写入的目标块号

• commit op：在未来某个时间，事务的一些列操作写入完毕，我们 commit 这个事务
  • 需要一个地方存储记录，与commit事务的个数
• install log：然后，根据记录将数据从log复制到目标块
• clean log：全部完成后即可删除原来的log文件

在文件系统恢复时，如果commit的事务个数大于0，则会 reinstall log & clean

• 任何commit前的操作都不会被执行
• commit 时所有log写入完毕，更新header。算不算commit成功就看header中的数字有没有改为非0（事务操作的个数）
• commit、install 之间，install期间，install、clean 之间被打断则会reinstall——这保证了一个事务的原子性

恢复期间不能进行额外的磁盘操作

install log是幂等操作，进行多次操作也会产生同样的结果

下节课我们会看到更加复杂的logging协议，所有的这些协议都遵循了write ahead rule

write ahead rule的含义是，你需要先将所有的block写入到log中，之后才能实际的更新文件系统block

log blocks

log 块分为两个部分：header+log data，header中存放了log的commit record，它包含：

• n：事务对应的Block数
• bni：log data block 对应的实际块号

当文件系统在运行时，在内存中也有header block的一份缓存

log_write

每个文件系统操作，都有 begin_op 和 end_op 分别表示事务的开始和结束，在end_op中，我们会将数据写入到log中，然后写入 log header / commit record

在end_op之前，磁盘并不会有实际的改变

任何一个文件系统调用的begin_op和end_op之间的写操作总是会在修改缓存块后，走到 log_write 修改 log header

文件系统中的所有bwrite都需要被log_write替换

这里先获取 log header 的锁，然后更新log header

• 如果log已经被记录了，则不需要做任何事
• 否则，增加该事务的块计数，并记录实际应写入的块号

这里会通过调用bpin函数将block 45固定在block cache中，我们稍后会介绍为什么要这么做

end_op

直接跳到正常且简单情况的代码：

首先调用了 commit：

• commit 首先调用 write_log，把缓存中的 目标缓存块 写入到log块中、以及将缓存中的 log header 写入到磁盘中

  • write_log 首先读出 log header，然后将缓存块写入log

• 然后调用 write_head，将log header写入磁盘

  • write_head 首先读出 log header，然后将n和block号拷贝进去，最后写入磁盘
  • 如果在 bwrite 前系统崩溃，则 commit 失败
  • 在之后发生，则数据已经落盘，commit 成功，可以恢复

    所以 write_head 中的 bwrite 是 commit point，在这之后文件系统崩溃才可恢复

• 然后是 install_trans：

  • 读取log block和目标block，写入目标缓存block，落盘

• install结束之后，会将log header中的n设置为0，再将log header写回到磁盘中

崩溃恢复流程

在第一个用户进程启动前会初始化文件系统，并调用 initlog，initlog 会调用 recover_from_log

recover_from_log 读取 log header，然后 reinstall log、清空n并更新 log header

如果我们在install_trans函数中又crash了，也不会有问题，因为之后再重启时，XV6会再次调用initlog函数，再调用recover_from_log来重新install log。如果我们在commit之前crash了多次，在最终成功commit时，log可能会install多次。

bwrite：写入磁盘

log_write只是更新log header缓存，并不能代表实际写磁盘的记录

• 3、4、5 属于 log data block
• 然后更新 log header
• 33，46，32 即 intall 上面的 345 的log data
• 然后clean log
• 然后就是上面的流程的重复：
  • 345写入log data
  • 2更新log header
  • 45、595、33 install log
  • 2 clean log

这里立刻可以想到的一个问题是，通过观察这些记录，这是一个很有效的实现吗？很明显不是的，因为数据被写了两次。如果我写一个大文件，我需要在磁盘中将这个大文件写两次。所以这必然不是一个高性能的实现，为了实现Crash safety我们将原本的性能降低了一倍。当你们去读ext3论文时，你们应该时刻思考如何避免这里的性能降低一倍的问题。

fs 的三个挑战

cache eviction：pin/unpin

假设在 intall log 过程中，我们install了block 45，此时缓存满了，假设我们决定撤回45，于是写入到block45中。这就破坏了 write ahead rule，即先写入log再更新fs块

所以buffer cache不能撤回任何还位于log的block，前面的 log_write 调用 bpin 增加block的引用计数即在防止块被撤回，在事务中的块都写入fs块后，unpin 这些block

fs 操作必须适配 log 大小

在XV6中，总共有30个log block，如果一个事务需要写入更多的块，则意味着一部分块必须直接写入fs，这违反了 write ahead rule

为什么XV6的log大小是30？因为30比任何一个文件系统操作涉及的写操作数都大，Robert和我看了一下所有的文件系统操作，发现都远小于30，所以就将XV6的log大小设为30。

其解决方案是，将写操作分解为多个小一些的写操作，因此 整个写操作不是原子的，但这对于 write 是ok的，我们只需要保证对于 fs 操作，log 放得下即可

block在落盘之前需要在cache中pin住，所以buffer cache的尺寸也要大于log的尺寸。

并发文件系统调用

太多的并发的执行的transaction的数据量可能突破log data的大小，我们需要限制并发fs操作的个数：

如果有太多正在进行的文件系统操作，我们会通过sleep停止当前文件系统操作的运行，并等待所有其他所有的文件系统操作都执行完并commit之后再唤醒。这里的其他所有文件系统操作都会一起commit。有的时候这被称为group commit，因为这里将多个操作像一个大的transaction一样提交了，这里的多个操作要么全部发生了，要么全部没有发生。

学生提问：前面说到cache size至少要跟log size一样大，如果它们一样大的话，并且log pin了30个block，其他操作就不能再进行了，因为buffer中没有额外的空间了。

Frans教授：如果buffer cache中没有空间了，XV6会直接panic。这并不理想，实际上有点恐怖。所以我们在挑选buffer cache size的时候希望用一个不太可能导致这里问题的数字。这里为什么不能直接返回错误，而是要panic？因为很多文件系统操作都是多个步骤的操作，假设我们执行了两个write操作，但是第三个write操作找不到可用的cache空间，那么第三个操作无法完成，我们不能就直接返回错误，因为我们可能已经更新了一个目录的某个部分，为了保证文件系统的正确性，我们需要撤回之前的更新。所以如果log pin了30个block，并且buffer cache没有额外的空间了，会直接panic。当然这种情况不太会发生，只有一些极端情况才会发生。

begin_op

1. 如果log正在commit过程中，那么就等到log提交完成，
   • 不能在install log的过程中写log
2. 如果当前操作是允许并发的操作个数的后一个，那么当前操作可能会超过log区域的大小，也需要sleep
3. 如果当前操作可以继续执行，需要将log的outstanding字段加1，最后再退出函数并执行文件系统操作。

end_op

1. 在最开始首先会对log的outstanding字段减1，因为一个transaction正在结束
2. 其次检查committing状态，当前不可能在committing状态，所以如果是的话会触发panic；
3. 如果当前操作是整个并发操作的最后一个的话，接下来立刻就会执行commit
4. 否则，我们需要唤醒在begin_op中sleep的操作，让它们检查是不是能运行。