《操作系统导论》第 43 章：日志结构文件系统 (LFS) - 深度知识架构

1. 核心矛盾 (The Crucial Problem)

随着系统内存（缓存）越来越大，读取操作大部分被缓存消化，磁盘 I/O 流量越来越以写入为主；而在机械磁盘上，随机写入的性能远远落后于顺序写入。操作系统如何将所有离散的、随机的写入操作，全部转换为最高效的顺序写入，从而逼近磁盘物理性能的理论极限？

2. 核心概念 (Core Concepts)

• 日志结构文件系统 (Log-structured File System, LFS)：
  • 定义：一种从不覆盖旧数据（异地更新，Out-of-place Write），而是始终将所有数据和元数据作为日志（Log）顺序追加写入到磁盘空闲区域的文件系统。
  • 角色：写入性能的“巅峰造极者”。它彻底打破了传统文件系统把磁盘当作随机访问内存的思维定势。
• 段 (Segment)：
  • 定义：LFS 用来在内存中缓冲待写入数据的大型块结构（通常是几 MB 大小）。
  • 角色：顺序写入的“载体”。通过将多次零碎写入打包进一个段，一次性顺序写盘，完美摊销了磁盘极高的定位延迟。
• inode 映射 (inode map, imap)：
  • 定义：一种记录“inode 号”到“其最新物理磁盘地址”的映射数据结构。
  • 角色：动态寻址的“GPS”。因为 LFS 从不覆盖旧数据，每次更新 inode 都会写到磁盘新位置，imap 使得系统能时刻追踪到 inode 四处“流浪”的最新位置。
• 检查点区域 (Checkpoint Region, CR)：
  • 定义：位于磁盘开头等固定且已知位置的结构，包含指向最新 imap 块的指针。
  • 角色：整个文件系统引导的“锚点”。通过读取它，系统才能顺藤摸瓜找到 imap，进而找到所有文件。
• 垃圾收集 (Garbage Collection) / 清理 (Cleaning)：
  • 定义：由于 LFS 只追加不覆盖，磁盘上会留下大量文件的旧版本（死块）。后台程序定期读取这些旧段，保留活跃数据（活块）写入新段，并释放旧段。
  • 角色：空间回收的“清洁工”，是保证 LFS 能够持续运转的关键机制。
• 段摘要块 (Segment Summary Block, SS)：
  • 定义：位于每个段头部的元数据块，记录了该段中每个数据块归属于哪个文件（inode 号）以及文件的哪个逻辑偏移量。
  • 角色：判定数据死活的“反向索引鉴定器”。

3. 逻辑演进 (Logical Evolution)

为了让机械磁盘飞速旋转出最纯粹的顺序吞吐，LFS 的设计者经历了一场精彩绝伦的推演：

• 最初的直觉方案（简单的顺序写入）：只要我们把所有的文件数据、目录、inode 统统按顺序追加到磁盘上就可以了。
  • 遇到的问题 1：如果只是一次追加一点点数据，两次写入间隙磁盘已经旋转，下次写入依然需要昂贵的旋转等待延迟。
• 演进方案 1（引入段缓冲）：引入段 (Segment)。在内存中积攒大量更新，等段满了以后，再执行一次漫长的顺序传输，将整个大段写入磁盘。
  • 遇到的问题 2：在传统 FFS 中，根据 inode 号通过简单的数学公式就能算出它在磁盘的固定物理位置。但在 LFS 中，inode 每次被修改都会写到段的最末尾，满磁盘乱跑。系统怎么找到文件？
• 演进方案 2（引入间接层 imap）：引入 inode 映射 (imap)。它记录每个 inode 当前所在的最新的物理磁盘地址。只要查 imap，就能找到乱跑的 inode。
  • 遇到的问题 3：imap 本身也会被修改，也会被追加写入到磁盘的新位置！我们怎么找到漂泊不定的 imap？
• 演进方案 3（引入固定的 CR）：在磁盘开头的固定物理位置设立检查点区域 (CR)。CR 包含指向最新 imap 片段的指针，而且定期原地更新。这样文件系统就有了启动的根基。
  • 遇到的问题 4（终极挑战）：磁盘终究会满。不停追加写入产生了大量废弃的、旧版本的“死块”，导致新数据无处可写。
• 最终成熟方案（垃圾收集与死活判定）：引入清理器。通过读取段中的段摘要块 (SS) 获得某块数据属于“文件 K 的块 N”。然后去查文件 K 最新的 inode：如果 inode 里的块 N 指针依然指向现在的物理地址，说明它是“活的”，将其搬运到新段保留；如果地址不同，说明该块已被更新的数据取代，它是“死的”，可以直接丢弃。最后整体回收该旧段。

4. 机制与策略 (Mechanisms vs. Policies)

• 底层的“实现手段”（机制 - Mechanisms）：
  • 死活快速判定机制：除了通过 SS 和 imap 进行长链路的反向查证外，LFS 还引入了版本号（Version Number）机制。文件被截断或更新时增加版本号，清理时只要对比磁盘段上的版本号和 imap 里的版本号，就能极速判断数据死活。
  • 双 CR 崩溃恢复机制：为了防止在原地覆写 CR 时发生断电导致系统损毁，LFS 维护了两个 CR（分别在磁盘两端），交替写入并附带时间戳。崩溃重启时，系统只要挑出时间戳最新且一致的那个 CR 即可恢复系统。
• 上层的“决策逻辑”（策略 - Policies）：
  • 清理策略（何时清理，清理谁）：由于清理的代价很高，系统需要策略抉择。通常的做法是把段分为“热段”（频繁被覆盖的段）和“冷段”（很少变动的段）。策略研究表明：应该尽快清理冷段，而延迟清理热段（因为等一等热段中会有更多的块自己变成死块，清理效率更高）。

5. 设计折衷 (Design Trade-offs)

• 牺牲“数据读取时的物理局部性”，换取“极致的写入性能”：这是 LFS 最疯狂的折衷。在 LFS 中，如果一个文件是陆续随着时间更新的，它的各个数据块会被打散在各个时间点的不同段中。这使得顺序读取文件的性能可能会退化。LFS 团队赌定“随着内存增大，读取大部分会被缓存命中”，所以哪怕牺牲了一定程度上的磁盘读取局部性，为了极致的写入性能也是值得的。
• 牺牲“后台 CPU 和 磁盘 I/O 资源”，换取“前端写操作的无阻碍”：为了维持 LFS 永远有空闲的新段可以写，后台必须不断运行垃圾回收。这种清理操作消耗了可观的计算和磁盘带宽，在极端满载情况下甚至可能引起系统性能断崖式下跌。

6. 关键洞察 (Key Insights)

• 计算机科学中的所有问题都可以通过一个间接层 (Level of Indirection) 来解决：由于 LFS 打破了传统 inode 固定位置分配的硬编码寻址方式，转而采用动态追加写入，直接导致系统找不到数据。LFS 巧妙地通过增加 imap 这个间接层，完成了从“固定物理地址计算”到“动态逻辑查找”的跨越，赋予了底层存储结构自由移动的终极能力。
• 细节至关重要 (Details Matter)：不要只把“把所有写入转为顺序写入”当成一句空泛的口号。真正让 LFS 成为经典的，是支持它运转的那些精密细节：为了解决寻找 inode 的问题发明了 imap，为了解决清理判断发明了段摘要块，为了应对崩溃发明了双重检查点。仅仅把握大致思路是极其危险的一知半解。
• 批处理 (Batching/Buffering) 掩盖高昂延迟：就像处理中断和网络包一样，在面对昂贵的物理延迟（如磁盘旋转和寻道）时，将零散操作在内存中缓冲收集，打包为极其庞大的“段”进行一次性下发，永远是突破硬件吞吐瓶颈的制胜法宝。

导师的下一步建议： 我们现在已经领略了如何通过 LFS 这个精巧的设计，将糟糕的随机写入逆转为飞速的顺序写入（顺便提一句，这套日志化思想现在正是绝大多数闪存固态硬盘 (SSD) 内部 FTL 层工作的核心原理！）。

但是，无论是 FFS 还是 LFS，如果这块辛辛苦苦转动的机械磁盘最终出现了不可恢复的扇区错误（Latent-Sector Errors），甚至是写错位置了，数据该怎么办呢？

MOC · 下一章：Ch44 数据完整性