ostep阅读笔记：单机fs的崩溃一致性(chapter42-44)
chapter 42 崩溃一致性
以一个传统的结构(linux ext2)为例子
一个磁盘group
inode bitmap | data bitmap | inode block | data block
磁盘映像
super | group0 | group1 | …
想要给一个文件追加一个block，需要改inode block, data bitmap 和 data block 3处
设想中途断电，硬件原子性在磁盘上是不好做的，所以可能在三个写入之中发生任意个写入落盘的情况
断电时已经修改的数据和后果的对应:
- inode block， 元数据不一致，指向垃圾数据
- data bitmap，元数据不一致，空间泄露
- data block， 没关系
- inode block + data bitmap， 文件是乱码，问题不大
- inode block + data block，元数据不一致
- data bitmap + data block， 元数据不一致，空间泄露
早期文件系统：fsck，让不一致发生，重启时修复，只确保元数据一致
- 检查super block（发现系统大小小于分配块数等不健全的情况，可以考虑启用super block的备用副本来防止super block自身损坏）
- 空闲块：inode, 间接块，以inode为参考， 修改inode bitmap达到一致, 所有看起来在用的inode都会有bitmap标记
- inode状态：如果inode的字段不合法，认为不易修复，删掉这个inode
- inode链接：扫描整个目录树，重新计算引用计数，如果找到已经分配的inode但没有目录引用，放到lost+found
- 重复和坏块，清除不正确的指针
- 目录检查：确保无环，目录中每个inode已分配等
磁盘清理工具：重排inode的data block来减少碎片
fsck 存在的一个问题：很复杂
fsck 最关键的问题：太慢了！
另外的方法：WAL
Linux ext34, Windows NTFS 采用的方法: 加上journal block
super | **journal** | group0 | group1 | …
journal中条目的形式：
TxB | inode | bitmap | data | TxE (物理日志，也有逻辑日志的做法，可能提高性能，节省空间)
checkpoint： 成功写入journal之后，就是一个checkpoint
先写WAL, 再写文件系统元数据，最后落盘data
问题：写日志的时候崩溃？
问题发生在，一条日志（以物理为例）可能太大，以至于不能被原子写入（常态）
- 日志内的数据可以被磁盘调度为小块乱序写入
- 写入的部分错误难以检查，例如在写入data段的时候出错，但其他部分正确（但也可以checksum? 这就是ext4的一项重要更新，通过在TxB和TxE之中包含checksum来加快写入速度）
- 磁盘的写缓冲，早期OS强制写入顺序就是通过关中断实现的: 写A，关中断，写B；有缓冲的状态下，写入缓冲就会返回。还要保证顺序的话，一种是禁用写缓冲，更现代的方法是写屏障（有趣的是一些磁盘产商忽略了写屏障，即使存在错误的风险，“快速几乎总是打败慢速，即使快速是错的”）
- 所以早期的方案是这样的，先写除了TxE之外的所有块，这部分出错这个事务就是未提交的，会被重置；然后第二步再写TxE, 磁盘保证写512字节的block的原子性，因而TxE是原子的。流程称为日志写入，日志提交，加检查点
此时，恢复仅仅是重放（replay）
批处理：
和TLB缓存很像，fs可以为了性能将磁盘写入合并批处理，在内存之中标记dirty
日志长度有限：循环，checkpoint之后前面的日志可以释放掉再重新写入
物理日志严重的写放大：元数据日志（linux ext3的另一个mode, windows NTFS），WAL之中不保存data段，只保存inode, inode bitmap，block bitmap等元数据修改。此时需要先写data, 来避免指向垃圾数据
- 这样的“强制 先写入被指向的对象，再写入指针”是崩溃一致性的核心
棘手的问题：块复用，感觉有点绕，总之是删除+文件夹这种递归结构+只记录元数据+重用得到了一些不好的结果，linux ext3的解决方法是删除也有revoke日志
其他崩溃一致性的解法：
- COW
- 反向指针，在被引用块里面添加引用块的引用（惰性崩溃一致性）
- 软更新，排序所有写入，复杂
- 乐观崩溃一致，例如校验和的方案
ZFS使用COW和日志
chapter43 LFS 日志文件系统
很像LSM，同样是为了利用磁盘的顺序写，同时只做顺序写，读时读最新版本，GC回收旧版本数据
LFS将每次文件系统的更新都顺序写入（data, inode），并以写缓冲实现批量写的性能提高，带来一个问题是不知道inode在哪里了
因而引入了一个中间层imap，记录inode, addr的对，imap需要保证持久，每次写入inode时,imap进行更新
imap放在哪里？如果在固定段，由于它更新的频繁性，所以需要非常多的磁盘寻道，不可接受
所以把imap和inode一起，写到更新后面
那去哪里找imap呢？（有点像 一级一级的索引，现在要找索引入口）
在磁盘的固定处维护检查点区域CR, CR指向最新imap，而CR的性能可以通过降低更新频率，例如每30s定时更新来解决，inode的更新全放到imap了
imap还解决了递归更新的问题
读取的时候有内存缓存，直接读里面的imap就行
怎么做GC? 在data block的开头有对inode块的反向引用+自身在inode中偏移量T，称为segment summary block
所以data → segment → 查最新的imap得到inode addr → inode[T] == data ? alive : dead
更简单的空间换时间的方法，在imap里面记录版本号，在segment里面也记录版本号
清理哪些段？一种粗略的方法是冷热分离
经常覆盖内容的段是热段，尽可能保留；反之冷段可以早清
崩溃恢复
- 写CR崩溃：1. 给cr做一个副本 2.更新cr时，通过 时间戳 + CR + 时间戳的方式，检测更新的一致性，时间戳是原子的
- 其他崩溃：CR后的数据丢了，假设CR是30s, 那不超过30s, 当然可以在CR里面包含更多信息，从而在最后一个检查点之后，尽量找到日志的结尾，并尽可能恢复有效的段，称为前滚 roll forward
LFS的思想在ZFS, Linux btrfs等有所体现，通过快照来得到fs的版本化
chapter 44 检测错误
磁盘错误：“有声的” 和“无声的”
- 前者例如意外的不可读，数据位反转，可以被ECC修复或检错的，总之会被磁盘发现
- 后者如写歪了
前者的解决方法是各种方式的RAID
后者的解决方法是校验和，xor, add, fletcher, crc
像“写歪了”（addr x写到y， 磁盘A写到B）这种如何检测？在校验和之中加入块 的磁盘和扇区号这样的物理标识符
还有一个特殊的情况是写入丢失，解决方法有写入后检验，或者在inode上加校验和（这样inode + data block全写丢了才会发现不了）
何时检测：定时，磁盘的位是会衰退的