LFS：The Design and Implementation of a Log-Structured File System（论文笔记）

论文：The Design and Implementation of a Log-Structured File System（Rosenblum, Ousterhout，SOSP 1991 / 1992 扩展版）

LFS（Log-Structured File System）的经典点在于：它把文件系统写入路径重构成“只追加”的日志，把随机写压缩成顺序写，换取更高的写带宽；同时用 cleaner（清理/压缩） 在后台回收空间。它也是“日志结构 + 后台合并”这一类系统设计（LSM、现代对象存储、某些 copy-on-write FS）的源头之一。

本文的工程化关注点：

• 写优化到底解决了什么瓶颈：为什么小文件写在传统 FFS 上会被放大？
• 代价在哪里：cleaning 的读写放大、尾延迟抖动来自哪里？
• 关键机制：segment、segment summary、inode map、checkpoint、cleaner 策略。

全文不使用 Mermaid，图用 ASCII 画法，保证构建稳定。

1. 传统文件系统的写放大：小更新为何慢

典型的“就地更新（in-place update）”文件系统（如 FFS）在小写场景会遇到系统性放大：

• 数据块写：写数据本身；
• 元数据写：inode 更新、间接块更新、位图更新、目录项更新；
• 同步语义：为了崩溃一致性，元数据写可能需要强制落盘或依赖日志/排序。

于是一个“写 4KB 文件”的动作，可能触发多次随机写。磁盘在随机写下的带宽远低于顺序写，最终表现为吞吐不稳定、延迟拉长。

LFS 的一句话动机：既然随机写慢，那就把写变成顺序追加。

2. LFS 的核心抽象：把磁盘当成循环日志

2.1 Segment：日志的物理组织

• Segment：磁盘上顺序追加的“大块”，例如 512KB/1MB/几MB。
• 写入时把数据块与元数据块打包成一个 segment，顺序落盘。

Disk as a log:

  +--------------------------------------------------------------+
  | seg0 | seg1 | seg2 | seg3 | ... | segK | free ...            |
  +--------------------------------------------------------------+
                          ^
                          |
                        tail (append point)

2.2 写路径：数据与元数据一起顺序写

简化写流程：

write(file, offset, data):
  1) allocate new blocks in the log
  2) write new data blocks to log tail
  3) write updated inode (and indirect blocks) to log tail
  4) update inode map (in-memory), later flushed as part of log

关键点：不修改旧位置的块，而是写新版本，并通过映射把“最新位置”指向新块。

3. 关键元数据：inode map 与 checkpoint

3.1 inode map（imap）：inode 编号到磁盘地址

传统 FS：inode 固定位置（inode table）。

LFS：inode 随日志移动，固定位置消失；需要 imap 维护：

imap[inode_number] -> disk_address_of_latest_inode

为了让 imap 自身不成为随机写热点：

• imap 也被切成块（imap blocks）
• imap blocks 作为日志的一部分顺序写入
• 内存中维护最新版本，周期性落盘

3.2 checkpoint：崩溃恢复入口

磁盘上保留一个（或两个交替）checkpoint region，记录：

• 最新 checkpoint 时间点的 imap blocks 地址
• log tail 的位置等关键信息

Checkpoint region:
  - pointer to imap block #0
  - pointer to imap block #1
  - ...
  - log tail position

崩溃恢复时：

1) 读 checkpoint region 得到 imap 的入口 2) 从 log tail 附近扫描 segment summary，找到 checkpoint 之后的新写入，重建内存状态

4. Segment Summary：为什么需要“每段摘要”

因为日志里混杂了数据块、inode、imap block 等，清理与恢复需要知道“每个块是什么、属于谁、对应文件哪个偏移”。

所以每个 segment 带一个 summary：

Segment:
  [segment summary][block1][block2]...[blockN]

summary entry:
  - type: data / inode / imap / ...
  - inode number
  - file block number (for data)
  - version / timestamp (optional)

它承担两类职责：

• recovery：扫描 segment 时快速识别有效块；
• cleaning：判断块是否仍是“最新版本”，还是已被更新淘汰。

5. Cleaning（清理/压缩）：LFS 的代价与灵魂

5.1 为什么一定需要 cleaner

日志只追加会把旧版本留在盘上；随着写入推进，空间会耗尽。要回收空间，需要识别“过期块”，把仍然有效的块搬走，释放整段空间。

这和 LSM 的 compaction 本质类似：后台合并 + 回收旧版本。

5.2 Cleaner 的基本流程

clean():
  1) select victim segments (old segments to clean)
  2) read victim segments sequentially
  3) for each block in segment:
       if block is still live (latest):
          copy it to the log tail (write new segment)
       else:
          drop it
  4) mark victim segments as free

5.3 “live 判断”怎么做：版本验证

对于某个数据块（inode=i，file_block=b，addr=A）：

• 通过 imap 找到最新 inode 地址
• 读 inode，得到 file_block b 的最新数据块地址 A’
• 若 A == A’，则该块仍 live；否则已过期

这一步看似会引入随机读；工程上会做批量化/缓存/把验证信息放在 summary 中降低成本。

6. Segment 选择策略：利用率与年龄

Cleaner 不是随便挑段；挑得不好会导致：

• 搬运活数据太多 → 写放大过大
• cleaning 跟不上前台写 → tail 逼近 head，系统抖动

论文里常见的启发式：结合 segment utilization（活数据比例）与 age（冷热）。

直觉：

• 低利用率段：可回收空间多，搬运少，性价比高。
• 冷数据段：不容易再被覆盖，搬运一次后可长时间不动，减少二次搬运。

可以用“成本/收益”类指标排序（示意）：

benefit ~= (1 - utilization) * segment_size
cost    ~= utilization * segment_size + read_cost
pick segments with high benefit/cost

7. LFS 的性能画像：什么时候快，什么时候抖

7.1 快的场景

• 小文件创建/追加写：把大量随机元数据写变成顺序日志写；
• 高写入并发：顺序带宽更容易吃满；
• 元数据密集：目录操作、fsync 频繁（假设 checkpoint 与写合并得当）。

7.2 抖的场景（cleaning 主导）

当系统进入“cleaning-heavy”状态：

• 前台写产生新日志
• 后台 cleaning 产生更多写（搬运 live data）

若 live data 比例高（例如覆盖率低、数据很冷），cleaning 的写放大可能接近或超过 2x、3x，导致：

• 写带宽被 cleaner 吞掉
• 前台延迟抬升，甚至出现 stall（没有足够干净 segment）

工程上往往需要：

• 给 cleaner 设置带宽上限/低优先级
• 预留足够 free segments（类似 LSM 预留空间）
• 做冷热分离（把冷数据聚集到少数段）

8. 崩溃一致性与恢复：checkpoint + roll-forward

LFS 的一致性设计偏“数据库式”：

• checkpoint 提供一个一致性快照点
• 崩溃后从 checkpoint 向前扫描日志（roll-forward）恢复到最新状态

恢复路径示意：

boot:
  1) read checkpoint region -> imap roots + log tail
  2) scan forward from last checkpoint to tail
  3) apply segment summary entries to rebuild latest mappings

工程提醒：

• checkpoint 刷盘频率是性能与恢复时间的权衡；
• checkpoint 需要双写或校验，避免自身损坏导致无法启动；
• scan 的上界取决于“checkpoint 之后写入量”，会影响重启时长。

9. 与现代系统的对应关系

LFS 的思想在很多系统里以不同形式出现：

• LSM-Tree：memtable + WAL + SST + compaction，本质是“日志结构 + 后台合并”
• Copy-on-Write FS（ZFS/btrfs）：写新块 + 指针更新；通过事务组/树结构维护一致性
• 对象存储/块存储：append-only + GC/compaction 的组合常见

差异在于：

• LFS 的地址空间是“文件系统块”，元数据组织与 POSIX 语义绑定；
• LSM 的 key-space 更适合做“版本淘汰”与“范围合并”；
• CoW FS 更强调树结构一致性与快照/克隆语义。

10. 工程实践清单（面向实现/运维）

10.1 设计层面的 checklist

• segment size 与写聚合策略：是否能稳定吃到顺序带宽？
• cleaner 策略：是否能在最坏情况下跟上写入？
• free segment 水位：何时触发 backpressure？
• checkpoint 频率：恢复时间是否可接受？

10.2 观测指标

• log 写入带宽、尾部推进速度
• cleaner 读带宽、写带宽、搬运率（live bytes copied / bytes cleaned）
• segment utilization 分布（冷热是否集中）
• stall 次数/时长（因无干净 segment）
• 重启恢复扫描时间

11. 小结

LFS 解决了“随机小写吞吐不稳定”的根问题：把写路径改为顺序追加；同时把代价转移到后台 cleaner。它的经典性来自于：

• 清晰的系统重构：数据 + 元数据一起日志化；
• 一套完整的恢复机制：checkpoint + roll-forward；
• 对 cleaning 代价的正面讨论：利用率/年龄驱动的选择策略。

工程视角下，LFS 的关键风险点也同样明确：cleaning 写放大 + 尾延迟抖动。这在后续几十年的存储系统里不断重演，成为“日志结构类系统”的长期主题。