lab通关记录

MIT-6.828实验通关记录

讲课计划

记录崩溃恢复
xv6：缓慢且立即耐用
ext3：快速但不立即耐用
权衡：性能与安全

示例问题：
附加到文件
两个写：
在位图中标记块非空闲
将块 # 添加到 inode addrs[] 数组
我们想要原子性：两者兼而有之
所以我们不能一次写一个 FS

为什么要登录？
原子系统调用wrt崩溃
快速恢复（没有长达一小时的 fsck）

xv6 日志回顾
[缓存、磁盘日志、磁盘文件系统]
每个系统调用都是一个事务
系统调用更新内存中的缓存块
在系统调用结束时：
将修改后的块写入磁盘
写入块 #s 和“完成”以登录磁盘——提交点
在磁盘上的 FS 中安装修改后的块
如果我们中途崩溃，恢复可以重播日志中的所有写入
规则：在日志中提交所有写入之前不要开始 FS 写入
即全有或全无——原子
从登录磁盘上擦除“完成”
所以来自下一个 xaction 的记录块看起来没有提交

在家工作
回声嗨 > 一个
commit() 被黑客入侵以忽略其中一个写入，在 commit+install 后崩溃
和恢复被禁用
问：为什么“cat a”（崩溃后）会产生“panic: ilock: no type”？
损坏的 commit() 更新了目录条目但不是 i-node
所以 dirent 在磁盘上并包含 inode#
但 i-node 被标记为空闲 (type=0)
Q：恢复后，为什么“cat a”会产生一个空文件？
即使我们运行了“echo hi > a”？
恢复将 inode 写入正确的位置
它现在已分配，并且 dirent 有效
但是 create 和 write 是独立的系统调用和事务
echo 从未调用过 write() – 在文件创建过程中崩溃

xv6 的日志记录有什么问题？它很慢！
每次系统调用后立即提交
提交后立即写入 FS
必须这样做才能重用磁盘日志——即运行下一个系统调用
任何 commit() 期间的所有新系统调用都会阻塞
所以如果有多个进程，并发执行不会太多
每个块两次写入磁盘，一次写入日志，一次写入 FS
对于元数据块来说还不错
大文件的痛苦
所以：
这些写入是同步的——xv6 在继续之前等待每个写入完成
创建一个空文件需要 6 次同步磁盘写入——60 毫秒
所以每秒只有 10 或 20 个磁盘更新系统调用

Linux的ext3设计
将日志记录添加到文件系统所需的详细信息的案例研究
Stephen Tweedie 2000 谈话记录“EXT3，日志文件系统”
http://olstrans.sourceforge.net/release/OLS2000-ext3/OLS2000-ext3.html
ext3 向 ext2（以前的无日志文件系统）添加日志
有很多模式，我将从“日志数据”开始
日志包含元数据和文件内容块

ext3 结构：
在记忆中：
回写块缓存
每笔交易信息：
要记录的块#s 集
一组出色的“句柄”——每个系统调用一个
在磁盘上：
FS
循环日志

ext3 日志中有什么？
记录超级块：记录最早有效交易的偏移量和起始序列号
（这不是 FS 超级块；它是日志文件开头的块）
描述符块：magic、seq、块#s
数据块（如描述符所描述的）
提交块：魔术，序列
|超级：偏移+序列#| … |描述符 4|…块…|提交 4| |描述符 5|…

ext3 如何获得良好的性能？
分批
每隔几秒提交一次，而不是在每次系统调用之后
所以每个事务都包含许多系统调用
为什么批处理有助于提高性能？
1. 将固定的交易成本（描述符和数据块）摊销在许多交易上
2.“写吸收”
批处理中的许多系统调用可能会修改同一个块（i-node、bitmap、dirent）
因此一个磁盘写入许多系统调用的更新
3. 更好的并发性——减少等待前一个系统调用完成提交

注意：系统调用在安全到达磁盘之前返回
这会影响应用程序级别的崩溃恢复情况
例如，邮件服务器接收消息，写入磁盘，然后回复“OK”

ext3 允许并发事务和系统调用
可能有多个事务：
一些完全提交在磁盘日志中
一些做日志写入作为提交的一部分
一个接受新系统调用的“打开”事务

ext3 系统调用代码：
系统打开（）{
h = 开始（）
获取（h，块#）
修改缓存中的块
停止（小时）
}
开始（）：
告诉日志系统进行一组写操作，直到 stop() 原子化
日志系统必须知道未完成的系统调用集
在它们全部完成之前不能提交
如果需要，start() 可以阻止这个系统调用
得到（）：
告诉日志系统我们将修改缓存块
添加到要记录的块列表
在 xaction 提交之前阻止将块写入磁盘
停止（）：
stop() 不会不会导致提交
如果所有包含的系统调用都调用了 stop()，则事务可以提交

将事务提交到磁盘

1. 阻止新的系统调用
2. 等待正在进行的系统调用 stop()
3. 开启一个新的事务，解锁新的系统调用
4. 写入描述符以登录到带有块列表的磁盘#s
5. 将缓存中的每个块写入到登录磁盘
6. 等待所有日志写入完成

7.写提交记录

8. 现在缓存块允许进入磁盘上的家（但不是强制的）

系统调用 B 可以读取系统调用 A 的未提交结果吗？
答：rm x
B: echo > y – 重新使用 x 释放的 i-node
B 可以先提交，以便崩溃会显示异常吗？
情况 1：两者都在同一个 xaction 中——好的，两者都不是
case 2: A in T1, B in T2 – ok, ext3 按顺序提交事务
情况 3：T1 中的 B，T2 中的 A
在 T1：|–B–|
在 T2：|–A–|
B 能看到 A 没有 y 的 i 节点吗？
毕竟，A 写入的缓存与 B 读取的缓存相同
坏：T1 后崩溃可能会使用 i 节点同时保留 x 和 y
否：ext3 等待 prev xaction 中的所有系统调用完成
在让任何人进入下一次之前
因此 B（在 T1 中）在 ext3 让 A（在 T2 中）开始之前完成
所以 B 不会看到 A 的任何写入
因此：
T1：|-系统调用-|
T2：|-系统调用-|
T3：|-系统调用-|
更大的一点：
提交顺序必须与提交的顺序一致
系统调用读/写状态。
也许 ext3 在这里牺牲了一些性能以获得正确性。

T2 中的系统调用写入一个也在 T1 中写入的块是否安全？
ext3 允许 T2 在 T1 完成提交之前启动——可能需要一段时间
T1: |-syscalls-|-commitWrites-|
T2：|-syscalls-|-commitWrites-|
危险：
T1 系统调用写入块 17
T1 关闭，开始将缓存块写入日志
T2启动，一个T2系统调用也写入块17
T1 可以将 T2 修改后的第 17 块写入日志中的 T1 事务吗？
坏：不是原子性的，从那以后崩溃会留下一些但不是全部 T2 的写入提交
所以：
ext3 为 T1 提供了块缓存的私有副本，因为它在 T1 关闭时存在
T1 从缓存的这个快照提交
使用写时复制很有效
副本允许 T2 中的系统调用在 T1 提交时继续进行
要点：
正确性需要崩溃后+恢复状态，就像系统调用一样
以原子方式和顺序执行
ext3 使用各种技巧来允许一些并发

ext3 什么时候可以重用事务 T1 的日志空间？
（日志是圆形的）
一次：
T1 之前的所有事务都已在日志中释放，并且
T1的缓存块已经全部写入磁盘上的FS
自由 == 提前记录超级块的起始指针/序列

如果日志中没有足够的可用空间用于系统调用怎么办？
假设我们开始将系统调用的块添加到 T2
中途，意识到 T2 不适合磁盘
我们不能提交 T2，因为系统调用没有完成
我们也不能退出这个系统调用
无法撤消系统调用
T2 中的其他系统调用可能已读取其修改

解决方案：预订
syscall 预先声明它可能需要多少块日志空间
ext3 的 start() 会阻止系统调用，直到有足够的可用空间
可能需要提交打开的事务，然后释放旧的事务
好的，因为保留意味着所有启动的系统调用都可以完成 + 提交

表现？
rm * 在一个包含 100 个文件的目录中
xv6：超过 10 秒——每个系统调用六个同步磁盘写入
ext3：总共大约 20 毫秒
rm * 重复写入相同的目录和 inode 块
直到提交，只更新缓存的块，没有磁盘写入
然后提交几个元数据块
多久做一次提交？
记录一些块（inode，dirent）
等待磁盘说写在磁盘上
然后写提交记录
两次旋转，或总共约 20 毫秒
现代磁盘接口可以避免浪费革命

如果崩溃怎么办？
崩溃可能会中断写入最后一个 xaction 以登录磁盘
所以磁盘可能有一堆完整的 xactions，然后可能有一个部分
也可能将一些块缓存写入磁盘
但仅适用于完全提交的 xactions，而不是部分最后一个

恢复是如何工作的
1.找到日志的开始——第一个未释放的描述符
日志“超级块”包含第一笔交易的偏移量和序列号
（释放日志空间时高级）
2.找到日志的结尾
扫描直到坏魔法或不是预期的 seq #
返回上次提交记录
提交期间崩溃 -> 没有提交记录，恢复忽略
3.通过最后一个完整的xaction重播所有块，按日志顺序

如果最后一个有效日志块之后的块看起来像一个日志描述符怎么办？
也许是以前使用日志遗留下来的描述符块？
seq # 会太低
也许某些文件数据恰好看起来像一个描述符？
记录的数据块不能包含幻数！
ext3 禁止记录数据块中的幻数 -> 描述符中的标志

“有序数据”模式（到目前为止我们一直在谈论“日志数据”模式）
日志文件内容很慢，每个数据块写入两次
我们可以从日志中完全省略文件内容吗？
如果我们这样做了，我们什么时候将文件内容写入 FS？
我们可以随时写入文件内容块吗？
否：如果首先提交元数据，崩溃可能会留下文件指向
使用其他人的数据写入未写入的块
ext3“有序数据”模式：
不要将文件内容写入日志
将内容块写入磁盘 * 之前 * 提交具有新大小和块的 inode #
如果没有崩溃，就没有问题——读者会看到写入的数据
如果在提交前崩溃：
[图表：i-node和位图以及内存中的新数据，磁盘上的新数据，
但磁盘上的 i-node 和位图未更新]
块有新数据
也许不可见，因为 i-node 大小和块列表没有更新
没有元数据不一致
i-node 和空闲位图写入仍然是原子的
大多数人使用 ext3 有序模式

带有有序模式的正确性挑战：
A. rmdir, 重用块 for write() 到某个文件，
在 rmdir 或写入提交之前崩溃
恢复后，就好像 rmdir 从未发生过一样，
但目录块已被覆盖！
修复：在释放系统调用之前不能重用已释放的块
B. rmdir，提交，重用文件中的块，有序文件写入，提交，
崩溃+恢复，重放 rmdir
文件留下目录内容，例如 . 和 ..
因为不重放文件内容写入
修复：将“撤销”记录放入日志，防止给定块的日志重放
注意：由于更改块的类型（内容与元数据）而导致的两个问题
所以另一个解决方案可能是永远不要这样做

规则概要
经典的预写日志规则：
在磁盘日志中提交之前，不要将元数据块写入磁盘文件系统
在启动 T2 之前等待 T1 中的所有系统调用完成
在日志中之前不要覆盖缓冲区缓存中的块
在所有块都写入 FS 之前不要释放日志空间
订购模式：
提交前将数据块写入 FS
在提交释放系统调用之前不要重用空闲块
不要重播已撤销的系统调用

另一个极端情况：打开 fd 并取消链接
打开一个文件，然后取消链接
取消链接提交
文件已打开，因此取消链接会删除目录条目但不会释放块
碰撞
日志中没有什么有趣的东西可以重播
inode 和 blocks 不在空闲列表中，也无法通过任何名称访问
永远不会被释放！哎呀
解决方案：将inode添加到从FS超级块开始的链表中
连同删除目录一起提交
恢复查看该列表，完成删除

校验和
回想一下：在写入提交块之前，事务的日志块必须在磁盘上
ext3 在开始提交块写入之前等待磁盘说“完成”
风险：磁盘通常具有写入缓存并重新排序写入，以提高性能
有时很难关闭（磁盘位于）
人们经常出于无知而启用重新排序以加快速度
坏消息，如果磁盘在事务的其余部分之前写入提交块
解决方案：提交块包含所有数据块的校验和
恢复时：计算数据块的校验和
如果匹配提交块中的校验和：安装事务
如果不匹配：不安装交易
ext4 有日志校验和

ext3 是否修复了 xv6 日志性能问题？
同步写入磁盘日志——是的，但 5 秒窗口
微小更新 -> 整个块写入 - 也许（如果系统调用允许写入吸收）
提交后同步写入主位置 - 是
ext3/ext4 非常成功！