21. The Design and Implementation of a Log-Structured File System

Design for File Systems of the 1990’s

文件系统的设计受到两种力量驱动:

技术 (Technology): 提供基本的硬件能力与性能边界;
工作负载 (Workload): 决定系统需要高效完成的操作类型;

本节总结了 1990 年代的技术变迁及其对文件系统设计的影响, 并说明为何当时的传统文件系统难以适应这些变化, 从而引出了 Sprite LFS(Log-Structured File System) 的设计动机;

2.1 技术背景 (Technology)

1. 处理器 (Processors)

CPU 性能以近乎指数级速度提升, 并将持续很长一段时间;
这种提升迫使系统中其他组件(如磁盘, 内存)也必须加快, 否则系统整体性能会"失衡";

2. 磁盘 (Disks)

磁盘技术的主要改进集中在 成本与容量, 而非性能;
磁盘性能包含两个部分:
- 传输带宽 (transfer bandwidth): 可通过磁盘阵列或并行磁头提升;
- 访问时间 (access time): 受机械结构限制, 几乎无法显著改善;
因此, 如果应用产生大量小的随机 I/O(带有频繁寻道), 即使 CPU 提升, 也难以获得速度提升;

3. 主存 (Main Memory)

内存容量呈指数增长, 现代系统可缓存更多文件数据;
对文件系统行为的两大影响:
1. 更多读请求被缓存吸收 $\rightarrow$ 磁盘 I/O 越来越以"写"为主;
2. 缓存也可作为写缓冲 (write buffer) $\rightarrow$ $\to$ 能将多个修改块合并为一次大规模顺序写, 极大提高效率;
  - 缺点: 若系统崩溃, 缓存中未写入的数据会丢失;
  - 可选方案: 使用非易失性内存(NVRAM)缓解;

2.2 工作负载 (Workloads)

1. 办公与工程应用 (Office & Engineering Workloads)

典型特征: 大量小文件访问(平均仅几 KB);
小文件导致大量随机磁盘 I/O;
文件创建/删除时间常被元数据(metadata)更新主导(如 inode, 目录项);

2. 大文件访问 (Large Sequential Workloads)

典型于超级计算环境 (supercomputing);
顺序访问大文件的性能主要受 I/O 带宽和内存子系统限制, 而非文件系统布局;
LFS 主要针对小文件优化, 但其机制同样适用于大文件;

2.3 现有文件系统的问题 (Problems with Existing File Systems)

问题一: 磁盘数据分散, 导致大量小访问 (Too Many Small, Random Accesses)

以 Unix FFS 为例:
- 虽能使单个文件顺序存放, 但不同文件之间分散;
- 文件内容, inode, 目录项被分离存储;
- 创建一个新文件至少需要 5 次独立磁盘 I/O(且每次都需 seek):
  1. 文件 inode 写入(两次)
  2. 文件数据块
  3. 目录数据块
  4. 目录 inode
- 小文件写入效率极低, 仅利用不到 5–10% 的磁盘带宽, 其余时间花在寻道上;

问题二: 同步写入 (Synchronous Writes)

许多元数据更新(inode, 目录)必须 同步写入 (synchronous write):
- 应用程序必须等待磁盘写入完成;
- 阻塞应用性能, 无法充分利用高速 CPU;
- 也使写缓冲 (write buffering) 无法发挥作用;
网络文件系统(如 NFS)甚至引入了更多同步操作, 虽然简化了崩溃恢复, 却严重降低写入性能;

Log-Structured File Systems

本节介绍 日志结构文件系统(Log-Structured File System, LFS) 的核心思想与实现方法;
LFS 的目标是通过顺序写入来显著提升写性能, 并保持与传统文件系统相当的读取性能;

核心思想 (Fundamental Idea)

“A log-structured file system improves write performance by buffering changes in memory and writing them sequentially to disk.”

1. 背景动机

传统文件系统(如 Unix FFS)在更新文件时需多次随机写:
- 文件数据, inode, 目录项等都分散在磁盘不同位置;
- 每次写操作都需要寻道 (seek), 导致带宽浪费;

2. LFS 的方法

将所有修改(data + metadata)先缓存在内存中;
定期 一次性顺序写入磁盘(即写成一个连续的日志段 log segment);
写入内容包括:
- 文件数据块 (file data blocks)
- 文件属性 (inodes)
- 索引块 (index / indirect blocks)
- 目录 (directories)
- 以及几乎所有文件系统管理信息 (metadata)

3. 效果

将大量小的同步随机写 $\rightarrow$ 合并为单次大的异步顺序写;
可利用几乎 100% 的磁盘原始带宽;
写性能提升约一个数量级;
崩溃恢复更快: 只需检查日志尾部;

设计挑战 (Two Key Issues)

LFS 的设计虽概念简单, 但要发挥潜力需解决两个关键问题:

文件读取与定位 — 如何从日志中快速找到文件内容?
(见 Section 3.1)
空闲空间管理 — 日志写满后如何回收空间?
(见 Sections 3.2–3.6)

Sprite LFS 通过一系列日志化数据结构解决这两个问题, 如下表所示;

文件定位与读取 (3.1 File Location and Reading)

1. 问题背景

“Log-structured” 乍看像必须顺序扫描日志才能找到文件;
但这会导致读性能极差;
Sprite LFS 的目标: 读性能必须与 Unix FFS 一样甚至更好;

2. 核心设计思想

LFS 在日志中同样保存了索引结构, 以支持随机访问读取:

每个文件有 inode:
- 存储文件属性(类型, 权限, 修改时间等);
- 记录前 10 个数据块的地址;
- 若文件更大, inode 会指向一个或多个 间接索引块 (indirect blocks);
这些结构在 LFS 中仍然存在, 只是被写入日志;

3. inode map 的作用

在 Unix FFS 中: inode 的位置固定, 可通过公式计算;
在 LFS 中: inode 随每次写入移动, 因此其位置是动态的;
inode map 维护每个 inode 的最新日志位置;
- 被划分为若干块, 也写入日志;
- 最新位置由固定的 checkpoint region 指向;
- 其活跃部分常驻内存, 因此查找几乎无需磁盘访问;

4. 文件读取流程

根据文件号(file ID)查询 inode map;
得到该文件 inode 在日志中的位置;
读取 inode;
从 inode 中查出数据块地址(直接或通过间接块);
读取文件内容;

$\rightarrow$ 一旦 inode 被找到, 读取的 I/O 次数与 Unix FFS 相同;

Free Space Management & Cleaning (Segments $\rightarrow$ Policies $\rightarrow$ Cost-Benefit $\rightarrow$ Evidence)

本组小节讲解 LFS 如何维持"大块连续空闲区" 以保证顺序写入始终高效:
从 按段管理 (segments) $\rightarrow$ 段清理机制 (cleaning) $\rightarrow$ 清理策略 (policies) $\rightarrow$ 写入代价模型 (write cost) $\rightarrow$ 仿真证据 (simulations) $\rightarrow$ 段使用表 (segment usage table);

3.2 Segments: 以"段"为单位的空闲空间管理

设计目标

目标: 始终维持 大块连续空闲区 用于新写入;
难点: 日志推进到磁盘末尾后, 删除/覆盖会把空闲空间打散成许多小碎片;

两种思路

Threading (穿插写)
- 保留 live 数据不动, 新的日志 thread fragmentations 继续写;
- 问题: 空闲空间高度碎片化 $\rightarrow$ 难以进行大块顺序写 $\rightarrow$ 性能退化到传统FS;
Copying(复制整理)
- 将活数据复制到一起 (compact/压实), 留下连续大空闲区;
- 问题: 复制成本高, 尤其对long-live cold data, 循环日志会反复移动它们;

Sprite LFS 的折中

将磁盘划分为固定大小的大块: segments(段), 每段从头到尾顺序写;
要重写一个段, 必须先把其中所有活数据复制出去(cleaning);
段级 threading: 如果能将冷数据聚集到若干段, 这些段可长期跳过, 避免反复复制;
段大小选择: 使整段读/写时间 ≫ 一次寻道时间 $\rightarrow$ $\to$ 无论访问顺序如何, 整段操作均接近满带宽;
- Sprite LFS: 512 KB 或 1 MB;

3.3 段清理机制(Segment Cleaning Mechanism)

三步走

读入若干段到内存;
识别活数据(live blocks);
写回活数据到更少的"干净段"(clean segments), 并将已读段标记为"干净";

如何识别活数据?

每段内包含 segment summary block(段摘要块), 记录:
- 段内每个条目的文件号 + 文件内偏移(或其它标识);
- 允许一个段中有多个 summary(当一次日志写未填满整段时);
判断活/死:
- 知道"块属于哪个文件, 哪个偏移"后, 对照该文件的 inode / indirect block:
  - 指针仍指向此块 $\rightarrow$ Live; 否则 $\rightarrow$ Dead;
- 优化: inode map 中为每个文件维护 版本号(删除或截断为零时+1);
  段摘要中记录的 (inode#, version) 与 inode map 当前版本不匹配 $\rightarrow$ 直接视为 Dead, 无需访问 inode;

结果

无需 free-block list 或 bitmap: 节省空间与实现复杂度; 也简化崩溃恢复;

3.4 段清理策略(Policies)

四个关键策略问题:

何时清理?(后台低优先级, 夜间, 或接近耗尽时触发)
- Sprite LFS: 干净段数低于阈值开始清理; 清理到另一个较高阈值停止;
一次清理多少段?(影响可重组的机会)
清理哪些段?(核心)
如何分组回写活块? (按目录增强读局部性; 或按"修改时间"排序 (age sort) 聚集同龄块)

实践中 (3) 清理哪些段 与 (4) 如何分组 对性能影响最大;

写入代价模型(Write Cost Model)

定义: write cost = 写入每个新数据字节引发的平均磁盘繁忙时间(包含清理开销), 以"无开销, 满带宽顺序写"的时间为 1.0 基准;
大段LFS中 seek/旋转延迟可忽略, 写代价由 清理段的"利用率 u" 决定;
设清理时读取 N 段, 每段利用率 u $\in$ [0,1):
- 读入: N 段
- 写回活数据: N * u 段
- 写入新数据: N * (1 - u) 段
- 生成的可用空段: N * (1 - u)

[
\text{write cost}
= \frac{\text{读入 + 写回活 + 写入新}}{\text{写入新}}
= \frac{N + N u + N (1-u)}{N (1-u)}
= \frac{2}{1-u}
]

极端: 若清理段没有活数据(u=0) $\rightarrow$ write cost = 1.0(理想);
参考: 传统 Unix FFS 小文件场景仅能利用 5–10% 带宽 $\rightarrow$ write cost $\approx$ 10–20;
即使改进(日志化, 延迟写, 调度)也约 25% $\rightarrow$ write cost $\approx$ 4;

结论: 若要优于现有 FFS, 清理段的 u < 0.8; 要优于"改进版 FFS", u < 0.5;

注意: 这里的 u 指"被清理的那些段的利用率", 不是磁盘全局利用率;
因此清理器应尽量挑选 低 u 段, 并通过策略让"可清理段"整体呈现低利用率;

3.5 仿真结果(Simulations)

模型与访问模式

模拟固定数量的 4KB 文件, 整体磁盘占用固定; 持续随机覆盖写某个文件;
两种模式:
- Uniform: 每个文件被选到的概率相等;
- Hot-and-cold: 10% 文件是 hot(被选概率 90%), 90% 文件是 cold(被选概率 10%);组内均匀;

两个关键现象

仅用贪心 (Greedy)(总清理最低利用率的段)+ Uniform:
- 由于段利用率存在自然方差, 被清理段的平均 u 低于全局占用率 $\rightarrow$ write cost 优于公式粗估;
有局部性 (Hot-and-cold) + 贪心 + 按年龄分组回写(age sort):
- 令人意外: 性能更差(越强的局部性, 越差);
- 原因: 冷段利用率下降缓慢, 长时间徘徊在清理阈值附近, 占用大量可用块 $\rightarrow$ 平均被清理段的利用率升高;

关键洞见: 需要区分"热段 vs 冷段"

冷段一旦被清理, 释放的空闲块能"保持很久"(高时间价值);
热段清理后, 空闲很快又被碎片"拿回去"(低时间价值);
因此应把选择段的依据改为"收益/代价"而非"谁最空";

Cost-Benefit 策略(核心公式)

收益: 释放的空间 $\times$ 空间"可保持"的时间
- 释放空间: (1 - u)
- 可保持时间: 用"段内最年轻块的年龄"近似(越老越稳定)
代价: 读一段 + 写回活数据: (1 + u)
指标: $\frac{\text{Benefit}}{\text{Cost}} = \frac{(1-u)\times \text{age}}{1+u}$
效果:
- 形成双峰分布: 大多数段接近满, 少数段接近空;
  绝大多数被清理的段是 低 u 的热段(约 15%), 冷段即使在 u$\approx$75% 也只偶尔清理;
- 相比贪心, write cost 降低可达 ~50%, 即使在较高的全局磁盘占用下仍优于最好的 FFS 方案;
- 局部性越强, Cost-Benefit 效果越好;

该策略最终被集成到 Sprite LFS, 并在真实系统中表现优于仿真预期;

3.6 Segment Usage Table(段使用表)

为支持 Cost-Benefit, 需要维护每段的两个指标:

live bytes: 段内仍然活的数据字节数;
age 指标: 段内最年轻块的"最近修改时间"(作为稳定性的近似);

维护与存储

段写入时初始化; 当文件删除或块被覆盖, live bytes 递减;
若计数降为 0 $\rightarrow$ 该段可直接重用(无需清理);
段使用表以块的形式写入日志, 其位置由 checkpoint region 记录;

补充

为按年龄排序, 段摘要记录"最年轻块"的年龄;
目前 Sprite LFS 以"文件级"修改时间近似块级时间(大文件的局部修改会有误差),
计划将来在摘要中记录块级修改时间;

4 Crash Recovery

LFS 的恢复核心是: 知道"最后写在哪里" $\rightarrow$ 只需处理日志尾部;
Sprite LFS 采用双路径恢复: Checkpoints(一致快照) + Roll-forward(向前回放未入快照的数据);

4.0 背景问题 (Why Recovery Is Easier in LFS)

传统 Unix FS: 崩溃后无法定位最后修改位置 $\rightarrow$ 必须全盘扫描元数据(fsck), 耗时可达数十分钟, 且磁盘越大越慢;
LFS: 最后的修改必在日志尾部 $\rightarrow$ 只需检查最近写入的段即可, 理论上可快速恢复;
Sprite LFS 与数据库/日志型 FS 类似, 采用:
(1) Checkpoints 定义一致状态; (2) Roll-forward 恢复 checkpoint 之后写入的数据;

4.1 Checkpoints(一致快照)

定义

Checkpoint: 日志中的一个点, 表示"此处之前文件系统的结构完整且一致";

两阶段写入流程

先将所有修改写入日志: 文件数据, 间接块, inodes, inode map, segment usage table;
再把 checkpoint region 写到磁盘固定位置:
- 内容: inode map 各块地址, segment usage table 各块地址, 当前时间, 最后写入段指针;

双 checkpoint 区域(抗崩溃)

磁盘上有两个 checkpoint region, 交替使用;
时间戳在最后一个块, 若崩溃于 checkpoint 写入过程中, 时间不会更新;
重启时读取两个区域, 选择时间更新更近的一个;

启动流程

引导时读取 checkpoint region $\rightarrow$ 初始化内存中的 inode map, segment usage table 等;

周期与开销权衡

周期性 checkpoint + 在 unmount/shutdown 时写入;
间隔长: 常态开销低, 但恢复时需要更多 roll-forward;
间隔短: 恢复快, 但常态开销高;
Sprite LFS 示例采用 30s(偏短); 也可按写入数据量阈值触发以平衡开销与恢复时间上限;

4.2 Roll-forward(向前回放)

目标与基本思路

仅用 checkpoint 可"秒恢复", 但会丢失 checkpoint 之后的数据;
Roll-forward: 从最后 checkpoint 之后写入的段向前扫描, 尽可能纳入最新数据;

利用段摘要(segment summary)

根据 segment summary block 识别最近写入内容:
- 若发现新 inode: 更新内存中的 inode map 使其指向新副本(自动纳入对应数据块);
- 若只发现数据块而无对应新 inode: 视为该文件新版本不完整 $\rightarrow$ 忽略这些块(避免引入不一致);

同步 segment usage 统计

checkpoint 之后写入的段: 使用率初始为 0, 需要根据 roll-forward 结果更新"活数据量";
更早的段: 还需根据新 inode 表明的删除/覆盖操作递减其活数据量;

目录一致性(directory vs. inode)

每个 inode 维护目录引用计数(计数为 0 $\rightarrow$ $\to$ 文件删除);崩溃可能导致:
- inode 的新计数已写入, 但目录块未写; 或反之;
解决方案: Directory Operation Log(目录操作日志):
- 每次目录变更都在日志中输出一条操作记录(create/link/rename/unlink), 包含:
  - 操作码, 目录位置(目录 inode 号 + 目录内偏移), 目录项内容(名称 + i-number), 新引用计数;
- 保证: 该操作日志先于相应的目录块或 inode 持久化到日志中;

Roll-forward 的修补动作

回放目录操作日志, 若发现"日志有操作, 但目录块/inode 未都写入"的情况:
- 补齐目录项和/或更新 inode 引用计数, 使之一致;
回放结束后, 将变更过的目录, inode, inode map, segment usage table 追加写入日志;
写入新的 checkpoint 以固化恢复后的状态;

唯一无法完成的操作: 创建了新文件但inode 从未写入(只有目录项变化);
这种情况下, 删除该目录项以恢复一致性;
(顺带好处: 实现了原子 rename)

与 checkpoint 的同步

要求每次 checkpoint 都与目录操作日志保持一致性;
因此在写 checkpoint 时需要暂时阻止目录修改, 以保证快照自洽;