第 43 章 日志结构文件系统

第 43 章 日志结构文件系统

设计动机

20 世纪 90 年代初，Rosenblum 和 Ousterhout 提出了日志结构文件系统 (LFS)，其设计基于以下观察：

• 内存容量增长：更大的内存能缓存更多数据，读请求多被缓存拦截，文件系统性能越来越取决于写性能。
• 顺序与随机 I/O 差距拉大：磁盘传输带宽持续提升，但寻道和旋转延迟下降缓慢。顺序访问磁盘能获得巨大的性能优势。
• 现有系统表现不佳：FFS 在创建单块文件时会产生大量零碎写（如分配 Inode、更新位图、目录和数据块），引发多次寻道，远低于峰值带宽。
• 缺乏 RAID 感知：现有文件系统未针对 RAID-4/5 的小写问题（单块逻辑写引发 4 次物理 I/O）进行优化。

核心机制：顺序写与缓冲

LFS 的核心思想是将所有更新（包括数据和元数据）转化为顺序写。

仅按顺序向磁盘发出写请求不足以保证高效，因为两次独立写操作之间的磁盘旋转会导致延迟。LFS 采用写缓冲 (Write Buffering) 技术，在内存中积攒大量更新，形成一个大型的段 (Segment)，随后将整个段一次性顺序写入磁盘的空闲位置。LFS 从不原地覆盖现有数据。

缓冲大小计算

为了摊销每次写入的定位开销，LFS 需要计算合理的缓冲量。假设磁盘定位时间为 $T_{position}$，峰值传输率为 $R_{peak}$，每次写入的数据量为 $D$。

写入耗时 $T_{write}$ 为： $T_{write}=T_{position}+\frac{D}{R_{peak}}$

有效写入速率 $R_{effective}$ 为： $R_{effective}=\frac{D}{T_{write}}=\frac{D}{T_{position}+\frac{D}{R_{peak}}}$

若期望有效速率达到峰值速率的比例 $F$（如 0.9），即 $R_{effective}=F\times R_{peak}$，解得缓冲量 $D$ 为： $D=\frac{F}{1-F}\times R_{peak}\times T_{position}$

例如，定位时间 10 ms，峰值速率 100 MB/s，期望达到 90% 峰值速率 ($F=0.9$)，则需缓冲 9 MB 数据。

索引与查找

LFS 将 Inode 散布在磁盘各处，且由于从不覆盖旧数据，最新版 Inode 的位置不断移动。

Inode Map

LFS 引入了Inode Map (imap) 作为间接层，将 Inode 编号映射到最新版本的磁盘物理地址。imap 自身也需要持久化。为避免额外的寻道开销，LFS 将 imap 切分为块，并与新写入的数据块、Inode 放在同一个段中一并追加到磁盘。

核心思想：引入间接层

计算机科学中的许多问题都可以通过引入间接层来解决。LFS 的 Inode Map 就是对 Inode 编号的虚拟化，它允许底层结构自由移动而无需修改上层引用。

检查点区域

为了在磁盘上找到分散的 imap 块，LFS 在磁盘固定位置（通常是起始处）维护了检查点区域 (Checkpoint Region, CR)。CR 包含指向最新 imap 块的指针。

CR 定期（如每 30 秒）更新一次以降低性能损耗。读取文件时，LFS 首先读取 CR，将全量 imap 缓存至内存，随后即可通过 imap 快速定位任何 Inode。

目录与递归更新问题

LFS 的目录结构与传统 UNIX 相同，存储 (文件名称, Inode 编号) 映射。

在从不原地更新的文件系统中，修改文件会导致 Inode 位置变化。如果不加处理，包含该文件的目录也必须更新指向，进而引发父目录更新，最终波及整个文件系统树，这被称为递归更新问题 (Recursive Update Problem)。

LFS 通过 imap 巧妙避免了该问题。Inode 位置变化只更新 imap，目录中存储的 Inode 编号保持不变。

垃圾回收

LFS 持续将新版本写入新位置，导致磁盘上散落着大量旧版本结构（垃圾）。LFS 必须定期清理，回收空间供后续写入使用。

段清理机制

为了避免清理后磁盘空间碎片化，LFS 清理器以段为单位运行：读取 $M$ 个旧段，提取其中的存活块，将其压缩写入 $N$ 个新段 ($N<M$)，最后释放原有的 $M$ 个段。

为了判断块是否存活，LFS 在每个段的头部增加了段摘要块 (Segment Summary Block)，记录段内每个数据块所属的 Inode 编号 $N$ 和逻辑偏移量 $T$。 存活检测逻辑如下：

1. 从段摘要中读取 $(N,T)$。
2. 查询 imap 获取 Inode $N$ 的最新地址并读取该 Inode。
3. 检查 Inode 中偏移量 $T$ 指向的物理地址是否等于当前块的地址。若相等则存活，否则为垃圾。

LFS 还通过在 imap 和段中记录版本号来加速比对，避免多余的磁盘读取。

清理策略

LFS 采用热度隔离策略决定清理时机：

• 热段 (Hot Segment)：内容被频繁覆盖。策略是延迟清理，等待其中更多块自然变为垃圾，从而提高清理效率。
• 冷段 (Cold Segment)：内容相对稳定，仅含少量死块。策略是尽早清理以回收空间。

崩溃恢复

LFS 采用日志结构，必须处理写入段或更新 CR 时发生的崩溃。

• CR 更新崩溃：LFS 在磁盘两端维护两个 CR，交替更新。更新时严格遵循顺序：先写头部（含时间戳），再写主体，最后写尾部（含相同时间戳）。若崩溃导致时间戳不一致，LFS 会回退使用另一个时间戳一致的旧 CR。
• 日志前滚 (Roll Forward)：由于 CR 仅定期更新，崩溃会丢失最近几十秒的进度。LFS 从最新 CR 指向的日志末尾开始，向后扫描后续段，提取有效更新以重建文件系统状态，尽可能挽救数据。