L13：崩溃恢复，日志记录

lab通关记录

MIT-6.828实验通关记录

课程总览

问题：崩溃恢复
崩溃导致磁盘文件系统不一致
解决方案：
日志记录

Ps：这是最后一次 xv6 讲座
下周我们将转向论文

为什么要崩溃恢复

什么是崩溃恢复？
你正在编写文件系统
然后停电
你重启
你的文件系统还能用吗？

问题：
多步操作时崩溃
可能会违反 FS 不变量
重启后：
坏：由于损坏的 FS 再次崩溃
更糟糕的是：没有崩溃，但读取/写入不正确的数据

例子：

目录项

create:
   新建目录项
   分配一个inode
   突然断电:你的目录指向了一个free的inode  -- disaster!
     突然又断电了, 或许那时候inode因为其他文件的创建被分配
   突然断电: inode 并不是free但是不能使用 -- 不是很糟糕
 write:
   inode addrs[] and len
   使用了间接 block
   block content
   block free bitmap
   突然断电: inode 指向一个free的block -- disaster!
   突然断电: block 并不是free但是不能使用 -- 不是很糟糕
 unlink:
   block free bitmaps
   free inode
   清除目录项

我们能希望结果是什么？
重新启动并运行恢复代码后
1.保持FS内部不变量
例如，空闲列表和文件中都没有块

2. 除了最后几个操作之外的所有操作都保存在磁盘上
   例如，我昨天写的数据被保留了
   但也许不是我在崩溃时写的数据
   所以用户可能需要检查最后几个操作

3.无事物异常
 echo 99 > 结果；echo done > state

正确性和性能经常发生冲突
磁盘写入很慢！
安全 => 尽快写入磁盘
速度 => 不写入磁盘（批处理、回写缓存、按轨道排序）

崩溃恢复是一个反复出现的问题
出现在所有存储系统中，例如数据库
多年来，很多工作都进入了解决方案
许多巧妙的性能/正确性权衡

日志解决方案

最流行的解决方案：日志记录
目标：原子系统调用wrt崩溃
目标：快速恢复（没有长达一小时的 fsck）

将分两步介绍日志
第一个xv6的日志，只提供安全和快速恢复
然后是Linux EXT3，正常运行也很快（查看本文件夹下的论文和另一节课笔记）

日志背后的基本思想
你想要原子性：所有系统调用的写入，或者没有
让我们将原子操作称为“事务”

1.记录所有写入系统调用在磁盘上的日志（日志）
2.然后在磁盘上记录“完成”（提交）
3.然后做 FS 磁盘写入（安装）
日志的记录为什么能够在崩溃后恢复起作用？因为日志记录了应该改动的地方，而这比磁盘写入快很多，或许这跟git的commit hash原理相近？

关于崩溃+恢复：
！！如果在日志中“完成”，则重播日志中的所有写入
如果没有“完成”，则忽略日志
这是一个可写的日志

预写日志规则
写日志直到“完成”标志后，再真正写文件入磁盘

为什么是这种规则？
一旦我们安装了一个写入磁盘文件的文件，
我们必须做所有交易的其他
写——所以事务是原子的。我们有
为第一次安装后的崩溃做好准备
写入，因此其他写入必须仍然可用
崩溃后——在日志中。

日志是魔法
复杂可变数据结构的崩溃恢复通常很难
日志记录通常可以在现有存储系统上分层
并且它与高性能兼容（下周的主题）

挑战：防止从缓存写回
系统调用可以安全地更新 cached 块，
但是块不能写入FS
直到事务提交（write back回写）
棘手，因为例如缓存可能会耗尽空间，
并试图按顺序逐出一些条目
读取和缓存其他数据。
考虑创建示例：
将脏 inode 写入日志
将目录块写入日志
驱逐脏的 inode
解决方案：
确保缓冲区缓存足够大
在缓冲区缓存中固定脏块
提交后，取消锁定块

xv6 日志表示

[图表：

​ 缓冲区缓存，内存日志块#数组，
​ 磁盘上的 FS 树、磁盘上的日志头和块

]

写入：

在写入时将 blockno 添加到内存数组
将数据本身保存在缓冲区缓存中
提交时：
1.将缓冲区写入磁盘上的日志
等待磁盘完成写入（“同步”）
2.将日志头扇区写入磁盘
块号
非零“n”
提交后：
将日志中记录的文件块（写入）到它们在 FS 中的主位置
在磁盘上的日志标题中将零写入“n”

磁盘日志头中的“n”值表示提交
非零 == 已提交，日志内容有效并且是一个完整的事务
零 == 未提交，可能不完整，恢复应忽略日志
写入非零“n”是“提交点”

挑战：系统的调用数据必须适合日志
计算每个系统调用写入的块数的上限
设置日志大小 >= 上限
将一些系统调用分解成几个事务

挑战：允许并发系统调用
必须允许来自多个调用的写入记录在日志中
提交时必须将它们全部写入
但是不能从仍在事务中的调用中写入数据

xv6 解决方案

如果数据可能不适合日志，则不允许启动新的系统调用
必须等待当前调用完成并提交
当进行中的调用数量降为零时（规定了并发调用数？）
提交
释放日志空间
唤醒等待的调用

挑战：一个区块可能在一个交易中被多次写入
写入仅影响内存中的缓存块
所以一个缓存块可能会反映多个未提交的事务
但只有在没有进行中的事务时才会安装
所以安装的块只反映提交的事务
有利于性能：“写吸收”

带有块号的 xv6 磁盘布局
2：日志头
32：索引节点
58：位图
63：内容块

让我们看一个例子。
我修改了 bwrite() 来打印低级磁盘写入，
即在事务提交期间发生的磁盘写入。

$ echo a > x
 // create
 bwrite 3   inode, 35
 bwrite 4   directory content, 63
 bwrite 2   commit (block #s and n)
 bwrite 35  install inode
 bwrite 63  install directory content
 bwrite 2   mark log "empty"
 // write
 bwrite 3
 bwrite 4
 bwrite 5
 bwrite 2
 bwrite 58   bitmap
 bwrite 533  x
 bwrite 35   inode (file size)
 bwrite 2
 // write
 bwrite 3
 bwrite 4
 bwrite 2
 bwrite 533  \n
 bwrite 35   inode
 bwrite 2

让我们看看第二个事务，一个 write()
第一个文件.c:syswrite
计算在日志满之前我们可以写多少块
在一个事务中写入那么多块

结合 fs.c:writei
begin_op（）
bmap() – 可以写位图，间接块
bread（）
修改bp->data
Log_write（）
iupdate()——写入inode
end_op（）

log.c 中的 begin_op()：
需要指明哪组写入必须是原子的！
需要检查日志是否正在提交
需要检查我们的写入是否适合日志的其余部分
日志写（）：
将扇区 # 添加到内存数组
设置 B_DIRTY，这样 bio.c 就不会驱逐它
结束操作（）：
如果没有未完成的操作，则提交
commit（）：
将更新的块从缓存复制到登录磁盘
在磁盘日志标头中记录扇区 #s 和“完成”
安装写入——从磁盘日志复制到磁盘文件系统
ide.c 将清除写入块的 B_DIRTY — 现在它可以被驱逐
从日志中删除“完成”

如果我们在交易过程中崩溃了会发生什么？

内存丢失，只剩下崩溃时的磁盘
在使用 FS 之前，内核在引导期间调用 recovery_from_log()
如果日志标题块显示“完成”：
将块从日志复制到磁盘上的实际位置
磁盘日志中有什么？
提交前崩溃
提交期间崩溃——提交点？
install_trans() 期间崩溃
重启后崩溃，而在recover_from_log()
注意：可以多次重放日志！因为我们的恢复是幂等的
只要没有其他活动干预

注意 xv6 假设磁盘是故障停止的
它要么正确写入，要么不写入（通过log的完成标志进行决定）
即可能由于电源故障而无法进行最后一次写入
因此：
没有部分写入（每个扇区写入都是原子的）
没有疯狂的写作
没有扇区衰减（没有读取错误）
没有读取错误的扇区

xv6 的日志设计有什么好处？
由于预写日志的正确性
良好的磁盘吞吐量：日志自然批量写入
但数据磁盘块被写入两次
并发

xv6 的日志记录有什么问题？
效率不高：
每个块被写入两次（日志和实际写入）
即使只修改了几个字节，也会记录整个块
同步写入每个日志块
可以批量写入，只能同步写入头
日志写入和安装写入是立即的
我们可以假设两者都可能是懒惰的，为了更多的写作吸收（意思是先记录，后一起写入）
！！但还是要先写日志
不适合日志的操作有问题
在截断文件时取消链接可能会弄脏许多块（意思是如果我删除文件，相关的文件块部分或许只是在日志上反馈，实际的块没有直接释放）

Donate