3.4 日志结构化文件系统——只追加，不覆盖
你有一个永远不会改错字的打字机
想象一个场景：你有一台老式打字机。不是你爷爷那种——这是一台“只追加、不倒退“的打字机。你只能往前打字。你不能退格。你不能涂改液。你不能把纸抽出来反过来写背面。
你打错了一个字怎么办？
你按下回车，在新的一行写上更正。旧的那行就留在那里——成为一段历史的见证，一段永远不需要被删除的程序记录。
这就是日志结构化文件系统（Log-Structured File System, LFS）的核心思想：你永远只追加，不覆盖。旧的数据不删除——它们自然死亡（被后续的垃圾回收清理）。
这个思想，诞生于1992年Mendel Rosenblum和John Ousterhout的那篇著名论文《The Design and Implementation of a Log-Structured File System》。这篇论文最初是为了解决磁盘的“小写放大“问题——磁盘上大量的小同步写造成的寻道开销。但他们发现，这种设计天然地和Flash的物理特性完美契合。
1992年的洞察：为什么磁盘讨厌小写入
在1992年，磁盘的性能瓶颈是寻道时间。一次随机寻道大约需要10毫秒。如果你每秒要写100次日志——每次都更新一个inode（索引节点）和一个数据块——那就是每秒200次随机寻道，大约2秒的纯寻道延迟。磁盘的吞吐量崩溃。
Rosenblum和Ousterhout的观察是：“如果我们不是把inode和数据块分散在磁盘的各个位置上，而是把所有写入都追加到一个连续的日志流的末尾——那磁盘的写头就永远不需要移动。它只需要待在一个地方，持续写。”
磁盘上的原地更新 vs 日志追加
=======================
原地更新（传统FS，如Unix FFS）:
磁盘布局:
┌──────┬──────┬──────┬──────┬──────┬──────┐
│inode1│inode2│块A │块B │块C │块D │
└──────┴──────┴──────┴──────┴──────┴──────┘
↑ ↑ ↑ ↑ ↑ ↑
每次修改inode或数据块，磁头都要移动到对应位置
寻道延迟 ≈ 写延迟的 100 倍
日志追加（LFS）:
磁盘布局:
┌──────────────────────────────────────────┐
│ inode1 │块A│inode2│块B│inode1│块A'│inode3│块C│ ... → 日志流 → │
└──────────────────────────────────────────┘
↑ 磁头一直待在这里，不断追加写
不需要寻道！写入速度 = 磁盘顺序写入速度
但这里有一个核心问题：如果数据块A被追加了新的版本（块A’），旧版本（块A）怎么办？
答案：旧的块A变成“垃圾“，等待回收。
LFS 的版本演进
=======================
首次写入:
日志: ...[inode1: version=1, 指向块A]...[块A: 内容="Hello"]...
修改文件:
日志: ...[inode1: version=2, 指向块A']...[块A': 内容="World"]...
旧块A的状态: [块A: 内容="Hello"] ← 仍然在磁盘上，但被标记为垃圾
没有任何inode指向它了
GC 之后:
旧块A被回收（擦除或重新分配），空间还给系统。
这个设计在磁盘上的性能提升是惊人的。在当时的测试中，LFS的写吞吐量达到了Unix FFS的10倍以上（对于小文件写入负载）。
但Rosenblum和Ousterhout没有想到的是：他们的设计，在30年后，成了Flash文件系统的天然范本。
为什么日志结构化天然适合Flash
把LFS的每一条设计选择和Flash的物理约束逐条对齐：
LFS 设计选择 → Flash 物理契合
=======================
1. 只追加，不覆盖
LFS: 所有写入都追加到日志末尾
Flash: 编程只能1→0，原地覆盖是不可能的
契合度: ★★★★★ 完全吻合
2. 旧版本自然保留
LFS: 旧的数据块没有被删除，它们变成垃圾等待GC
Flash: 旧数据块在擦除之前保留着，可以提供掉电恢复
契合度: ★★★★★ 完美利用Flash的Copy-on-Write特性
3. 垃圾回收（GC）
LFS: 定期扫描日志，将有效数据（最新版本）移到日志尾部
Flash: 必须GC来回收无效块，为写入腾出空间
契合度: ★★★★★ 都是空间回收的必需机制
4. 顺序写入
LFS: 日志流=顺序写入流
Flash: NAND的顺序写入比随机写入快（页面编程流水线）
契合度: ★★★★ 顺序写入有性能优势
5. 无原地修改
LFS: 不存在"修改一个inode"的概念，每次都创建新的
Flash: 不存在"原地修改"，每次都是Copy-on-Write
契合度: ★★★★★ 概念完全一致
6. 版本快照
LFS: 每次checkpoint都是一次快照
Flash: 旧数据天然保留，掉电后可以回滚到上一个checkpoint
契合度: ★★★★★ 天然支持掉电恢复
LFS的设计哲学和Flash的物理约束之间，不是“适配“，是“命中注定“。
这不是巧合。这是物理约束决定了数据结构，而数据结构反过来验证了物理约束的合理性。Flash的三原罪（写前擦除、单向编程、有限寿命）把文件系统设计推向了日志结构化，而日志结构化恰好是应对这些原罪的最优解。
LFS的核心数据结构
具体看看LFS的数据结构。在KnotFS里，你会在很多地方看到这些结构的影子。
1. 超级块（Superblock）
LFS Superblock = KnotFS Superblock 的直系祖先
=======================
LFS:
两个超级块副本，分别位于磁盘的两端
┌──────────┐ ┌──────────┐
│ SB 副本 1 │ │ SB 副本 2 │
│ (磁盘头部) │ ... 日志段 ... │ (磁盘尾部) │
└──────────┘ └──────────┘
每个超级块包含：
- 日志尾部的起始位置（tail pointer）
- 段使用表（segment usage table）的起始位置
- inode映射表的起始位置（imap）
- 时间戳和序列号
KnotFS:
两个超级块副本，位于块0和块1
┌──────────┐ ┌──────────┐
│ SB0 (块0) │ │ SB1 (块1) │
└──────────┘ └──────────┘
每个超级块包含：
- sequence_number（决定哪个是有效的）
- 文件表的位置信息
- 空闲位图的起点
- magic number 和 CRC
2. Inode映射表（Imap）
LFS Imap → KnotFS File Table
=======================
LFS:
imap是一个紧凑的数组：imap[inode_number] → 日志中该inode的最新位置
每次inode被更新（放到日志末尾），imap也要更新
imap自身也以日志追加的方式存储
KnotFS:
文件表嵌入在Superblock中（nodes[8]），双副本由SB双槽位保证
nodes[x] → {文件名, 起始块号, 大小, 属性}
每次文件修改，通过Compact重写整个SB来持久化文件表
3. 段（Segment）和段清洁器（Segment Cleaner）
LFS Segment → KnotFS GC Block
=======================
LFS:
磁盘被划分为固定大小的段（segment），通常512KB-1MB
segment cleaner = 垃圾回收器
┌────── Segment 1 ────────┐ ┌────── Segment 2 ────────┐
│[有效│垃圾│有效│垃圾│有效]│ │[有效│有效│有效│有效│有效]│
│ 50% 50% │ │ 90% 10% │
└─────────────────────────┘ └─────────────────────────┘
选择Segment 1进行清理（垃圾最多）
读出有效数据 → 追加到日志尾部 → Segment 1被清空 → 可重用
KnotFS:
每个块（Block）就是一个"段"
gc_recycle() 选择垃圾最多的块
搬迁有效数据到新块 → 擦除旧块 → 旧块回到空闲池
日志结构化的“元数据洪水“
但LFS有一个著名的工程代价：元数据洪泛（Metadata Flood）。
因为一切都是日志追加，任何修改——哪怕只是改动一个inode的时间戳——都需要在日志末尾追加一条记录。也就是说：
修改一个inode的时间戳:
Unix FFS:
1. 读inode块
2. 修改其中的时间戳字段（8字节）
3. 原地写回同一个扇区
物理I/O: 1次读 + 1次写
LFS:
1. 读入旧inode
2. 在内存中修改时间戳
3. 将修改后的inode（整个128字节左右）追加到日志尾部
4. 更新imap → 追加一条imap记录到日志尾部
5. 标记旧inode为垃圾
物理I/O: 1次读 + 2次追加写 + 增加2条垃圾记录
LFS的写放大在元数据层面比传统FS更高。这个“元数据洪泛“在磁盘上被顺序写入的性能优势摊平了——但在Flash上，你同时有了磨损的问题。
这就是为什么KnotFS在LFS的基础上做了裁剪：SB Log的每一条记录只有8字节（tag+blk+val+crc32）。 它不记录“inode被修改成了什么“——它只记录“哪个块被标记为used/free“。文件表的修改不走日志——文件表嵌入在SB Header中，通过Compact一次性持久化。这种设计把“追加一整个inode“变成了“追加几个字节+定期Compact“。
KnotFS 的元数据 compact log
=======================
LFS 做法:
修改inode字段 → 追加整个inode(128B) + imap条目(16B) → 144B
KnotFS 做法:
修改free_map → 追加一条 SB Log 记录(8B)
修改文件表 → 累积在内存中，Compact时一次性写入新SB
Compact log 的优势:
- 一个4KB块可以塞下 ~400条 SB Log 记录
- 日志记录极小，减少了磨损
这是KnotFS对LFS的一个关键优化——但不是对LFS的否定，而是对LFS的充实。
LFS的Checkpoint机制：一条线的两头
LFS的另一个重要贡献是Checkpoint（检查点）机制。
因为所有写入是追加的，你总可以找到“上一次完整写入的状态“。如果在写入过程中掉电，你只需要回滚到上一个checkpoint即可。
LFS Checkpoint = KnotFS 的双槽位Compact 的祖先
=======================
Checkpoint N (有效):
┌─────────────────────────────────┐
│ Superblock → imap → inodes → data│
└─────────────────────────────────┘
↓ 开始写入新数据
┌─────────────────────────────────┐
│ 新inode │ 新data │ 新imap │ ... │ ← 追加到日志尾部
└─────────────────────────────────┘
↓ 掉电！！
日志尾部不完整 —— 但没关系
重新mount时：读到Checkpoint N的信息
从Checkpoint N的位置开始扫描日志
发现不完整的记录 → 丢弃 → Checkpoint N成为恢复点
Checkpoint N+1 永远只在"所有数据都安全落地"时才被写出来。
KnotFS里的双槽位Compact——把内存中的完整状态（文件表+free_map+wear[]）写入备用SB槽位，写入成功后切换活跃指针——本质上就是LFS Checkpoint的缩减版：Checkpoint写的是完整的inode映射表，Compact写的是完整的SB Header（内嵌文件表）。
一篇论文和一百二十八个Flash块
1992年，Rosenblum和Ousterhout在斯坦福的SUN工作站上写LFS时，他们面对的是300MB SCSI硬盘、16MB内存、每秒几百次随机I/O的性能瓶颈。
2026年，你在Cortex-R5核心上设计KnotFS，面对的是512KB NOR Flash、64KB SRAM、实时调度器的确定性要求。
硬件差了三个数量级。但核心问题完全一样：
1992 LFS → 2026 KnotFS
=======================
LFS 面对的: KnotFS 面对的:
磁盘寻道延迟(10ms) Flash擦除延迟(200ms)
小写放大(随机寻道代价) 小写放大(擦除-重写代价)
需要顺序写入提升吞吐 必须异地更新才能活
GC浪费磁盘带宽 GC浪费Flash P/E寿命
Checkpoint防崩溃 双槽位Compact防掉电
分段管理(512KB-1MB) 按块管理(4KB)
同构的问题，在不同的尺度上，产生了同构的解决思路。
这就是为什么你需要读LFS论文、理解LFS思想——不是因为它“先进“，而是因为它揭示了一个更本质的工程规律：当一个存储介质不允许原地修改时，日志结构化是唯一正确的数据结构选择。
为什么KnotFS是“日志结构化“而不只是“Copy-on-Write“
有一个微妙的区分需要说清：Copy-on-Write和日志结构化不是同一件事。
Copy-on-Write是一块一块的。你有一棵数据树，你修改一个叶子节点，你把修改过程一路向上传播到根节点——每一层都分配新块（CoW），旧的保留为垃圾。
日志结构化是一条流。你在日志末尾不断追加新的记录——不管它是一个数据块、一个inode、还是一个目录项。所有东西都是日志流上的一个条目。
CoW vs Log-Structured
=======================
CoW（如 Btrfs, ZFS）:
块0: [A] → 修改A → 块0: [A 旧]
块N: [A'新]
修改只影响"被修改的块所在的树路径"
引用计数管理：当旧的树路径上所有节点都失去引用时，它们被回收
Log-Structured（如 LFS, KnotFS）:
日志: [条目1│条目2│条目3│条目4│...] → 修改条目2 → 追加条目2'到末尾
所有修改都追加到日志尾部
有效版本永远在"日志尾部"方向
垃圾是日志里被后面的记录覆盖了的前面记录
KnotFS采用了混合策略：
- 元数据（Superblock）：日志结构化 + Compact。 SB Log 是 LFS 日志流的微缩版——free_map 的增量变化以 8 字节 log 记录追加。文件表嵌入在 SB Header 中，通过 Compact 持久化。
- 数据块：Copy-on-Write。 文件数据存在独立的数据块中，修改时分配新块、复制旧数据+修改、标记旧块为垃圾。这更接近Btrfs的CoW而非LFS的纯日志。
KnotFS 的混合架构
======================
元数据层（Log-Structured + Compact）:
┌──────────────┐ ┌──────────────┐
│ SB0 SB Log│ │ SB1 SB Log│
│ nodes[8] │ │ nodes[8] │
│ [rec1][rec2] │ │ [空日志区] │
│ [... │ │ │
└──────────────┘ └──────────────┘
追加写入 追加写入
数据层（Copy-on-Write）:
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐
│ 块3 │ │ 块5 │ │ 块8 │ │ 块12 │
│ 文件1 │ │ 文件1 │ │ 文件2 │ │ 文件1 │ ← 旧的
│ (旧) │ │ (旧) │ │ (旧) │ │ (新CoW) │
└────────┘ └────────┘ └────────┘ └────────┘
垃圾 垃圾 垃圾 有效
为什么要这样分层？因为元数据很“小“（几字节一条记录），适合紧凑日志；数据块很“大“（4KB一块），做CoW更自然。两者用同样的垃圾回收机制（遍历有效块、搬迁到新块、擦除旧块）统一管理。
下集预告
LFS给Flash文件系统提供了理论基础。但在真实世界——在2026年的嵌入式开发中——你不是从零开始的。已经有一批Flash文件系统在不同领域服役：LittleFS在ARM Mbed上运行、SPIFFS在ESP32上运行、YAFFS和JFFS2在Linux上跑了二十年、F2FS在Android手机上服务了几亿设备。
下一节，我们铺开一张地图——给你看一遍这个“嵌入式Flash文件系统“的全家福。看看它们各自的设计哲学、数据结构和生死抉择。也看看为什么KnotFS不在这张地图上跟它们竞争，而是走一条完全不同的路。
悬念留给：你猜LittleFS为了节省RAM，怎么做了一个整个文件系统在一棵“链式元数据对“上的设计？两棵四层级的元数据树，在4KB RAM的微控制器上，怎么装下32MB Flash的全套文件系统？