文件系统可靠性

数据备份

1. FS要求
   • FS给用户提供持久化的数据存储
   • 文件一直要保存完好，除非用户显式删除它们
2. 威胁一：设备损坏
   • 磁盘块损坏
   • Superblock损坏：整个FS丢失
   • bitmap、inode table损坏：无法管理空间和inode
   • 数据块损坏：目录、文件、间址块都无法读写

备份与恢复

1. 物理备份与恢复：设备级
   • 将磁盘块逐一拷贝到另一个磁盘上（备份盘）
   • 全复制：原始盘与备份盘在物理上一模一样
   • 增量备份：只拷贝发生变化的块，与上次备份相比
   • 例如：使用dd进行磁盘备份
2. 逻辑备份与恢复：文件系统级
   • 遍历文件系统目录树，从根目录开始
   • 把指定的目录和文件拷贝到备份磁盘
   • 在备份过程中验证文件系统结构
   • 恢复时可以将指定的文件或目录树恢复出来
   • 也有两种方式
     • 全备份：备份整个文件系统
     • 增量备份：只备份发生变化的文件/目录

物理备份 vs 逻辑备份

1. 物理备份
   • 忽略文件和文件系统结构，处理过程简洁，备份性能高
   • 文件修改时只用备份修改的数据块，不用备份整个文件
   • 不受文件系统限制
2. 逻辑备份
   • 备份文件时，文件块可能分散在磁盘上，备份性能受影响
   • 文件修改时需要备份整个文件
   • 受文件系统限制，按文件粒度备份，保证完整性

宕机一致性保证

1. 威胁二：宕机或掉电
   • 硬件掉电
   • 软件bugs导致宕机：驱动或文件系统bug
   • 导致文件缓存中的脏数据没有写回磁盘：目录块、inode 、间址块、数据块
2. 挑战
   • 宕机可能发生在任意时刻
   • 在性能与可靠性之间进行取舍
     • 宕机使得内存中的数据全部丢失
     • 缓存越多的数据 -> 性能越好
     • 缓存越多的数据 -> 宕机时丢失的数据越多
   • 一个文件写操作往往修改多个块
     • 磁盘只能保证原子写一个扇区
     • 如何保证修改多个块的原子性？

宕机的影响

1. 创建文件：在当前目录 /home/xj 下创建文件 testfile
   • 需写回4个块，在磁盘不同位置
     • inode bitmap
     • 文件inode
     • 目录块：含目录项<"testfile", ino>
     • 目录inode：修改size，mtime等
   • 宕机时，没有全部写回 -> FS不一致
     • 写回顺序可能是任意的
     • 目录块没写回：有inode，没目录项
     • 文件inode没写回：有目录项，没inode
2. 写文件：在 /home/xj/testfile 末尾写入一个数据块（Append）
   • 需写回3个块，在磁盘的不同位置
     • 文件inode：修改size，mtime等
     • data-block bitmap
     • 数据块本身
   • 宕机时，没有全部写回 -> FS不一致 & 数据与元数据不一致
     • 写回顺序可能是任意的
     • FS不一致：文件inode 和 data-block bitmap 中有一个没写回
     • 数据与元数据不一致：文件inode 和 数据块没有都写回
3. 写回方案一：先写元数据、后写数据（同上例）
   • 路径解析"/home/xj/testfile" || 宕机 -> 数据与元数据一致
   • 分配数据块，写bitmap || 宕机 -> 数据与元数据一致（FS不一致，有垃圾块）
   • 写inode（直接指针、大小等） || 宕机 -> 数据与元数据不一致
   • 写数据块 || 宕机 -> 数据与元数据一致

先写元数据，宕机后可能出现数据与元数据不一致

4. 写回方案二：先写数据、后写元数据（同上例）
   • 路径解析"/home/xj/testfile" || 宕机 -> 数据与元数据一致
   • 分配数据块，写bitmap || 宕机 -> 数据与元数据一致（FS不一致，有垃圾块）
   • 写数据块 || 宕机 -> 数据与元数据一致
   • 写inode（直接指针、大小等） || 宕机 -> 数据与元数据一致

先写数据，宕机后可能i-node指向旧版本，但数据与元数据是一致的

宕机一致性保证

宕机一致性的分类

1. FS一致性
   • 文件系统自身的数据结构（称为FS元数据）一致
     • Superblock,bitmap(inode和data)，inode，目录项
     • 可能导致FS不一致：修改多个元数据的操作
       • 创建/删除文件、创建/删除目录、重命名、硬链接、符号链接、...
       • 写文件
2. 数据与元数据一致性
   • 文件元数据（inode和间址块）和文件块一致
   • 数据与元数据不一致：写文件
3. 数据一致性
   • 一次写多个数据块
   • 数据不一致：写文件
4. 宕机一致性保证
   • 一个操作包含多个修改：要么全部写到磁盘，要么都没写到磁盘

宕机一致性的总结

1. 通用方法：按自底向上顺序进行修改（Ordered Write）
   • 文件的数据块 -> 文件的inode -> 目录的数据块 -> 目录的inode
     • 写回所有的数据块（有文件缓存）
     • 修改文件的inode，并把它写回磁盘
     • 修改目录块（目录项），并把它写回磁盘
     • 修改目录的inode，并把它写回磁盘
     • 沿路径向上，直到无修改的目录
2. 不足
   • 宕机后仍然可能产生垃圾块（FS不一致），也可能有目录和文件不一致（文件修改了，目录没有改）
   • FS不一致可以通过运行一致性检查工具（例如fsck）清理垃圾块
3. 理想情况
   • 保证一致性的修改，而且不留下垃圾块
   • 三个一致性保证

fsck：Unix FS一致性检查工具

1. 检查并试图恢复FS的一致性
   • 不能解决所有问题，比如数据与元数据不一致
2. 检查Superblock
   • 如果fs size < 已分配块，认为它损坏，切换到另一个 Superblock 副本
3. 检查块位图
   • 重构已使用块信息：扫描磁盘上所有的 inode 和间址块
4. 检查 inode 位图
   • 重构已使用 inode 信息：扫描磁盘上所有目录的目录项
5. 检查 inode
   • 通过 type 域的值（普通文件，目录，符号链接）来判断 inode 是否损坏
   • 如果损坏，则清除该 inode 及它对应的 bitmap 位
6. 检查 nlink 域
   • 遍历 FS 的整个目录树，重新计算每个文件的链接数（即指向它的目录项个数）
   • 没有目录项指向的 inode ，放到 lost+found 目录下
7. 检查数据块冲突
   • 是否有两个(或更多)的 inode 指向同一数据块
   • 如果有 inode 损坏，则清理 inode，否则把该数据块复制一份
8. 检查数据块指针
   • 指针是否越界(> 磁盘分区大小)
   • 删除该指针
9. 不足
   • 恢复时间与 FS 大小成正比
     • 即使只修复几个块，也需要扫描整个磁盘和遍历 FS 目录树
     • 会导致丢数据：inode 损坏、数据块或间址块损坏

事务和日志文件系统

事务：一组操作，需要具有原子性 —— 要么所有操作都成功完成，要么一个操作也不曾执行过

事务的应用 —— Write-Ahead Log（写前日志）

1. 写前日志
   • 在实际进行写操作前，先把写操作记日志
   • 记录日志时使用事务
2. 前提
   • 日志中记录的所有修改必须是幂等的
   • 每个事务有唯一的编号 TID
   • 必须有办法确认写磁盘完成
     • TxB 和 日志记录可以同时发给磁盘，TxE最后发送，使用 Write Barrier
     • 使用 fsync 保证写盘完成

具体步骤

1. Begin Transaction（开始事务）
   • 开始一条日志项，写一个日志开始标记 TxB，标明一个事务开始
2. 事务中的修改
   • 所有修改都写日志
   • 事务日志中需要标明事务编号 TID
3. Commit（提交事务）
   • 写一个日志结束标记 TxE，标明一个事务成功完成
4. Checkpoint（检查点）
   • Commit 之后，把该事务中的修改全部写到磁盘上
5. 清除日志
   • Checkpoint 写完后，清除相应的日志项

宕机恢复（Replay）

1. 宕机后扫描写前日志中的日志项，对于每条日志项
   • 如果磁盘上只有日志开始标记 TxB，没有结束日志 TxE，则什么也不做
   • 如果日志项是完整的（同时有 TxB 和 TxE），则按日志重做（Redo Log），然后再清除日志
2. 前提假设
   • 写到磁盘上的日志数据都是正确的
   • 宕机后没有磁盘损坏

日志文件系统（Journaling File System）

1. 用写前日志来记录所有写操作

   • 创建/删除文件、创建/删除目录、重命名、硬链接、符号链接...
   • 写文件

2. 第一个日志文件系统：Cedar FS[1987]

3. 很多商用文件系统都使用写前日志：NTFS、JFS、XFS、Linux ex2/3/4...

4. 宕机恢复

   • 按日志重做一遍
   • 简单、高效
     • 恢复时间与日志大小成正比
   • 日志必须是等幂的

日志文件系统：数据日志（data journaling）

1. 记录所有修改的日志：数据 & 元数据
2. 例如：在一个文件末尾追加一个数据块
   • 修改文件的inode，修改bitmap，写数据块
3. 流程
   • 写日志：TxB、inode日志、bitmap日志、数据块日志
   • 提交日志 commit：写 TxE
   • Checkpoint：实际修改磁盘上的inode、bitmap、数据块
   • 清除日志
4. 日志开销
   • 所有数据块写两次磁盘

日志文件系统：元数据日志（metadata journaling）

1. 只记录元数据的修改的日志
2. 例如：在一个文件末尾追加一个数据块
   • 修改文件的inode，修改bitmap，写数据块
3. 流程
   • 写数据块
   • 写日志：TxB、inode日志、bitmap日志
   • 提交日志 commit：写 TxE
   • Checkpoint：实际修改磁盘上的inode、bitmap
   • 清除日志
4. 日志开销
   • 只有元数据写两次磁盘，所有数据块只写一次磁盘

日志文件系统总结

1. 性能问题
   • 增加额外的写磁盘开销：每个日志都要同步写磁盘（fsync）
   • 写放大
     • 即使只修改一个块中少量内容（十几字节），也需要写日志
     • Bitmap中一个bit修改，也要对bitmap block写日志
2. 改进办法
   • 批量写日志：以牺牲可靠性换取性能
     • 宕机仍然可能丢数据，但不会损坏FS一致性
     • 例如，再同一个目录下创建和写入多个文件
   • 用 NVRAM 来保存日志，实现快速同步写
3. 可靠性
   • 无法应对硬件故障，比如磁盘扇区坏
4. 日志管理
   • 需要多大的日志？
     • 日志只在宕机恢复时需要
     • 日志过小，很快占满日志空间，无法接受新日志
     • 日志过大，导致恢复时间长
   • 方法
     • 顺序地、Append-only 写，循环使用日志空间（Circular Log）
     • 定期做 checkpoint ：把缓存里的修改内容刷回磁盘
     • checkpoint 之后，可以释放日志所占空间

日志结构文件系统（LFS —— Log-Structured File System）

1. 思想
   • 想写日志那样顺序地写磁盘
2. 具体机制
   • 每次写文件块写到新位置（日志末尾）：out-of-place update（vs in-place update）
   • 不需要 bitmap 来管理空闲空间
   • 文件块采用多级索引（同FFS）：文件块位置记录在 inode中
   • 每次写文件采用一致性修改：先写文件块，再写inode
3. 大粒度顺序写
   • 起因：小粒度写不能发挥磁盘带宽
   • Segment：大粒度的内存 buffer
     • 缓存多个写，一次把整个 Segment 写回磁盘
     • 写回时仍然遵循 先写文件块，再写inode 的原则

读inode

1. UFS 和 FFS
   • 通过ino来计算出inode的位置
2. LFS
   • 每次写文件块，都要写 inode
   • 每次会写到新的位置，即一个文件的 inode 在磁盘没有固定位置

imap

1. 记录 ino->inode 磁盘地址，只记录最新的inode地址
2. 怎么存
   • 磁盘上的固定位置
   • 每次写文件，都要修改 imap
   • 写日志与写imap需要长距离寻道，性能比 FFS 还差
3. LFS的改进方法
   • imap块随文件块和i-node一起写到日志中
   • CR(Change Region)：记录每个imap块的最新磁盘地址
   • CR位于磁盘上固定位置：有两个CR，分别位于磁盘的头和尾

关于目录：目录采用与文件一样的方式来写

读文件

1. 假设 LFS 刚挂载，内存里什么也没有
   • 先读 CR，把 CR 缓存在内存，以后就不用读了
   • 根据 ino ，知道它所在的磁盘块
   • 查 CR 得到 imp 块的磁盘地址
   • 读 imap 块，得到 ino 对应的 inode 的磁盘地址
   • 读 inode，查文件块索引，得到文件块的磁盘地址
   • 读文件块

修改文件

1. 修改 /home/os/foo 的第一块
   • 原来的数据块变为无效 -> 垃圾
2. 在 /home/os/foo 末尾追加写一块
   • 原来的inode变为无效 -> 垃圾

垃圾回收

1. 原理
   • 后台进程cleaner周期性地检查一定数量的segment
   • 把每个segment中的活块拷贝到新的segment中
     • 如何判断活块？
       • segment summary block
         • 记录每个数据块的ino和文件内偏移
         • 位于 segment 的头部
       • 通过查segment summary block、imap和文件索引可以得到当前块的地址
   • M个segment的活块占据N个新的segment
2. 何时回收
   • 周期性回收
   • 空闲时：无访问或访问少
   • 磁盘快满的时候
3. 回收什么样的segment
   • 热segment：块频繁被重写
   • 冷segment：部分死块、部分稳定块（不重写）
   • 优先回收冷segment，推迟回收热segment（直至该segment里的数据块都被重写过）

宕机恢复

1. LFS的最新修改在日志末尾
2. CR记录第一个 segment 和最后一个 segment 的磁盘地址
   • 每个segment指向下一个segment
3. CR更新
   • 写CR的第一个块，带时间戳
   • 写CR本身内容
   • 写CR最后一个块，带时间戳
   • 周期性地将CR刷盘（30s）
   • 两个CR（磁盘头和尾）交替写，减少CR更新时宕机的影响
4. CR一致性保证
   • 第一个块和最后一个块的时间戳一致
5. 恢复方式
   • 使用最后一次且一致的 Checkpoint Region
     • 时间戳最新的 & 完整的CR
     • 可以获得最后一次 Checkpoint 时的 CR 内容，包括 imap 等数据结构的地址
   • CR 周期性刷盘，此时 CR 内容可能已过时，即最后一次 Checkpoint 后的磁盘写没有被恢复
   • 恢复优化（回滚）
     • 使用最后一次修改的 CR（不一定是一致的）重构最新的文件修改
       • 根据 CR 找到日志末尾（有记录），检查后续写的 segment
       • 将其中有效的更新恢复到文件系统，例如，将 segment summary block 中记录的 inode 更新到 imap 中
   • 恢复快
     • 无需fsck，无需扫描磁盘
     • 秒级 vs 小时级