LFS 1991 — 把整个磁盘当日志写

是什么

LFS（Log-Structured File System，日志结构文件系统）是 1991 年 Mendel Rosenblum 和 John Ousterhout 在 Berkeley 的 Sprite 项目里提出的一种文件系统设计——把整块磁盘当一条只追加的大日志来写，从来不”原地修改”任何块。

日常类比：

传统文件系统（ffs-1984 / ext / NTFS）像家里的活页本——改第 3 页就翻开第 3 页，用橡皮擦掉再写新字
LFS 像写日记——永远在最后一页接着写”3 月 5 日：我把第 3 页那段话改成 X”。原文不动，新版本接在末尾

写文件从”找位置 + 覆盖”两步变成”只追加”一步。这就是 LFS 把小文件写吞吐打到接近磁盘带宽极限的根本原因。

为什么重要

不理解 LFS，你解释不了下面这些事：

为什么 lsm-tree-1996 / RocksDB / clickhouse 会出现——它们就是 LFS 思想从文件系统挪到数据库引擎
为什么 SSD 内部的 FTL（Flash Translation Layer）也是 log-structured——闪存”原地改”会写放大，FTL 把所有写变追加
为什么 ZFS / btrfs / WAFL（NetApp）有”copy-on-write”——它们是 LFS 的现代化变体
为什么 1991 年这篇论文影响力远远超过同年的其他 SOSP 文章——它把”硬件越来越偏向顺序写”这个趋势看透了

LFS 是系统设计史上第一次正面把”未来 CPU 和内存会让磁盘读变得不重要、写才是瓶颈”作为前提来重做整套文件系统的工作。

核心要点

LFS 由三块拼起来：

只追加写（append-only）

新写入永远落在磁盘的”日志末尾”。不存在”找文件原来在哪、覆盖那个块”这一步。所有写都变成大块顺序写——磁头几乎不动，吞吐量直奔磁盘带宽上限。

段（segment）+ 段清理（cleaner）

磁盘被切成几 MB 一个的”段”。日志写满当前段，就跳到下一个空段继续写。久了磁盘会塞满”过期数据混着活数据”的段——LFS 跑一个后台清理器，扫几个半空的段，把里面活的块拷贝到新段，原段整段释放。类比：日记本写满，把每一页的”还在用的句子”剪贴到新本子，旧本子整本扔掉。

inode map（inode 也在日志里漂）

传统文件系统里 inode 表在固定位置。LFS 里 inode 也是只追加写——每次改文件，新 inode 写在日志末尾。怎么找到当前最新的 inode？再加一张小小的 imap（inode map）记录”inode N 当前在日志哪个偏移”，imap 本身也只追加写，再用一个固定位置的 checkpoint 区指向最新 imap。

三层”间接表”嵌套，每层都是 log-structured。这就是 LFS 的全部魔法。

实践案例

案例 1：写一个文件走什么路径

write("foo.txt", data)
  ↓
新数据块追加到日志末尾
  ↓
新 inode 追加到日志末尾（指向上一步的数据块）
  ↓
新 imap 块追加到日志末尾（更新 inode N 的位置）
  ↓
checkpoint 偶尔（每 30 秒）原地更新一次，指向最新 imap

写一个 4KB 文件可能产生 12KB 日志写——但都是顺序写，磁头不动。FFS 同样的操作要做 4-5 次寻道（inode、目录、bitmap、数据块各一次）。

案例 2：读一个文件走什么路径

read("foo.txt")
  ↓
查 checkpoint → 找到最新 imap 位置
  ↓
读 imap → 找到 inode N 当前在日志哪个偏移
  ↓
读 inode → 拿到数据块指针
  ↓
读数据块

读比 FFS 多一跳（imap 这层间接），但 imap 通常被缓存在内存里——Sprite 实测读性能和 FFS 持平甚至略好。

案例 3：段清理选哪些段

清理器面对的是经济学问题：每个段有”利用率 u”（活数据占比）。清理 u=0.1 的段，搬 10% 数据出去就回收一整个段——划算。清理 u=0.9 的段不划算。论文给了”代价/收益”公式：

benefit / cost = (1 - u) * age / (1 + u)

age 是段最后修改时间——老段更可能稳定，回收后空闲时间长。这个公式是论文的灵魂——它把”什么时候清理”从直觉变成可计算。

直觉解释：

u 小（活数据少）→ 1-u 大 → 收益高
age 大（段已稳定很久）→ 搬完后能空闲很久 → 收益高
1+u 在分母 → u 越大成本越高（要搬的越多）

踩过的坑

清理器开销：写工作负载下清理器持续在后台跑，吃 CPU 和 IO 带宽，前台写延迟尖刺。后续 lsm-tree-1996 的 Compaction 抖动是同一个问题换皮
小文件随机更新场景：BSD 团队 1995 年的论文反驳，说 LFS 在”老化磁盘 + 高利用率”下清理器吃掉所有收益。这个争论持续了 10 年
崩溃恢复看似简单实则脆：理论上”重放日志末尾”就能恢复，但 imap 更新和 checkpoint 不原子时会丢——Sprite 用 roll-forward + 校验和才稳住
磁盘满时雪崩：利用率 95%+ 时清理器找不到划算段，前台写被堵成蜗牛——所有 LFS 风格系统都有这个隐藏死亡螺旋
目录 trace 和 find 慢：所有元数据都漂在日志里，全盘扫元数据需要顺着 imap 跳一堆点。后续 BSD-LFS 加了 ifile 缓存才把这个补上

适用 vs 不适用场景

适用：

写多读少、小文件密集（日志、缓存、消息队列）
SSD/NVMe 等闪存介质（“原地改”代价大，顺序写是天生优势）
需要快照 / 时间机器功能（旧版本天然保留在日志里）—— ZFS / btrfs 直接拿这个特性当卖点

不适用：

读密集、文件极大、几乎不修改（视频归档）—— 多一跳 imap 没意义
磁盘长期 90%+ 占用（清理器死亡螺旋）
严格实时系统（清理抖动让延迟不可预测）

历史小故事（可跳过）

1980s 末：Ousterhout 在 Berkeley 带 Sprite 操作系统项目，发现 ffs-1984 改进的极限在于”小写入仍是随机写”——磁盘吞吐被卡死在 5-10%
1989-1990：博士生 Mendel Rosenblum 提出”反正内存越来越大，读会被缓存吃掉，那就只优化写”，写出 Sprite-LFS 原型
1991：SOSP 论文发表。当年最佳论文。Rosenblum 后来成为 Stanford 教授，又和 Diane Greene 一起创办 VMware
1995：Seltzer 等人在 USENIX 发反驳论文（“File System Logging vs. Clustering”），引发学界十年辩论
2000s：NetApp WAFL、ZFS、btrfs 把 LFS 思想变种成 copy-on-write 商用化；闪存 SSD 的 FTL 内部全是 log-structured
2006-至今：lsm-tree-1996 概念被 Google bigtable、LevelDB、RocksDB、cassandra 推到 NoSQL 主流，本质是把 LFS 从文件系统层挪到 KV 层

学到什么

看清硬件演化方向，比优化当前瓶颈重要——LFS 押的是”内存变大、读会被缓存吃掉”，30 年后真的发生
不可变 + 后台合并 是工程切割复杂度的通用招式，从 LFS → LSM → Git 对象模型 → 函数式 GC 都是一脉
理论 → 工业 → 反扑 → 再融合，一个好想法要经历 20 年才能定型。LFS 1991 → SSD 普及 2010s 才完全验证
公式化决策 > 凭直觉——段清理 cost/benefit 公式让”什么时候做”成为可调可证的工程问题
顺序写 vs 随机写的差距是物理铁律——这条原理从 1991 LFS 到 2026 NVMe 都没变，只是放大了几个数量级

关联

ffs-1984 —— FFS 把磁盘几何写进文件系统；LFS 把它彻底反过来：完全无视几何，只管追加
lsm-tree-1996 —— LSM-Tree 是 LFS 思想从文件系统层挪到数据库 KV 层的直系后裔
bigtable —— 第一个工业级把 LSM/LFS 思想做到 PB 级的系统
leveldb —— Google 把 LFS 思想抽成 500 行 C++ 库
unix-1974 —— Unix 文件系统原始设计，LFS 与之同源但走完全相反的路

反向链接

btrfs-2013 —— Btrfs — Linux 上”写时复制 B-tree”的工业级文件系统
clickhouse —— ClickHouse — 列式 OLAP 数据库
disco-1997 —— Disco — 让没改过的商用 OS 在 64 核大机器上一起跑
frangipani-1997 —— Frangipani — 把分布式文件系统盖在共享虚拟磁盘上
lsm-tree-1996 —— LSM-Tree 1996 — 写优化存储引擎
soft-updates-1999 —— Soft Updates — 不写 journal 也能保证文件系统元数据一致
xen-2003 —— Xen 2003 — 让操作系统配合虚拟化，性能直接接近原生
zfs-2003 —— ZFS — 把磁盘当成水池，每滴水都贴标签