这一章要解决什么

如何让所有的写都变成顺序写？文件系统怎样才能把所有写操作都变成顺序写？对读来说这不可能——要读的块可能在磁盘任何地方；但对写来说，文件系统总是有选择权（想写到哪儿就写到哪儿），我们要利用的正是这个选择权。

HOW TO MAKE ALL WRITES SEQUENTIAL WRITES? … For reads, this task is impossible … For writes, however, the file system always has a choice, and it is exactly this choice we hope to exploit.

上一章（崩溃一致性）我们学会了用日志（journal）保证更新的原子性；上上章（FFS）我们学会了"按局部性放置数据"。20 世纪 90 年代初，伯克利的 Ousterhout 和 Rosenblum 走得更远：干脆把整个磁盘当成一条日志，所有更新（数据和元数据）先在内存里攒成一大段，再一口气顺序写到磁盘的空闲位置，从不原地覆盖。这就是日志结构文件系统（Log-structured File System，LFS）。

他们的出发点是四个观察：

FFS：在一个块组内创建一个单块文件 = 6 次分散的小写 超级块 inode 位图 数据位图 inode 表 数据块 1 2 3 4 5 6 ① 新 inode　② inode 位图　③ 目录数据块　④ 目录 inode　⑤ 新数据块　⑥ 数据位图：磁头来回跳，每次都付寻道 + 旋转的代价 LFS：同样的更新先在内存里攒成一个段，再一次顺序写到空闲区域 D I[k] 目录块 I[dir] imap ……同一段里其他文件的更新……
图 43-A　FFS 虽然把相关块放在同一个块组，仍要 6 次小写；LFS 把它们（连同别的更新）合成一次大的顺序写。没有位图——LFS 不需要"就地找空闲块"。

核心概念速览

只追加的日志

所有更新（数据块、inode、目录、imap）都写到日志末尾的空闲位置，从不原地覆盖旧版本。

段（segment）与写缓冲

先在内存里攒满一个几 MB 的段，再一次写下去，把定位开销摊薄到可以忽略。

inode 映射（imap）

inode 号 → inode 最新磁盘地址的间接层。inode 每次都搬家，靠 imap 找到它。

检查点区域（CR）

磁盘上唯一固定位置的结构，记录各 imap 片段的地址；每隔约 30 秒才更新一次。

递归更新问题

inode 搬家若要改目录、目录又搬家……会一路改到根。imap 让目录只存 inode 号，问题消失。

段摘要块（SS）

每段开头记录每个块属于"哪个 inode 的第几块"，清理器据此判断块是否还活着。

清理（cleaning）

读入 M 个半空的段，只把活块压缩写成 N 个新段（N < M），腾出整段空闲空间。

两个 CR + 前滚（roll forward）

CR 交替写、头尾带时间戳保证原子性；重启后从检查点沿日志往后扫，找回之后写入的段。

顺序写：把一切都追加到日志末尾

先看最简单的情况：往文件里写一个数据块 D。LFS 把 D 写在磁盘地址 A0；但光写数据不够，文件的 inode 也要更新、要指向 D。于是 LFS 把 inode 紧挨着 D 写下去（图中 inode 画得和数据块一样大，实际上 inode 通常只有约 128 字节，数据块是 4KB）：

图 43-B　数据块 D 写在 A0，紧接着写它的 inode，inode 的 b[0] 指向 A0。这就是 LFS 的核心想法：所有更新顺序写到磁盘上。

光"顺序"还不够：还得"一次写很多"

假设在时刻 T 往地址 A 写了一块，过了一会儿（T+δ）再写 A+1。地址是连续的，可在这 δ 里盘片已经转过去了：第二次写要等将近一整圈（Trotation − δ）才能落到盘面上。所以要达到峰值性能，必须一次发出大量连续的写（或一次大写）。

小写、间隔着写（地址连续也没用） A T δ T+δ 发出写 A+1 A+1 刚刚转过磁头，等待 T_rotation − δ A+1 写缓冲：攒够了一次写出（一次定位，然后全速传输） 定位 A A+1 A+2 I imap …… ✓ 整段一次完成
图 43-C　"顺序"是必要条件而不是充分条件：必须把许多更新合成一次大的连续写。

为此 LFS 使用一个古老的技术：写缓冲（write buffering）。更新先记在内存里，攒够了再一次写出。LFS 一次写出的这一大块叫做段（segment）（真实系统中是几 MB）。下例把两组更新攒进一个（很小的）段：对文件 j 的 4 个块写，以及给文件 k 追加 1 个块，然后把这 7 个块一次提交：

图 43-D　一个段里的 7 个块：文件 j 的 4 个数据块 + inode j，文件 k 的 1 个数据块 + inode k，一次顺序写入。

该缓冲多少？

答案取决于磁盘：定位开销（寻道 + 旋转）相对传输速率有多大。设每次写之前的定位时间是 Tposition，峰值传输率是 Rpeak，一次写出 D MB：

Twrite = Tposition + D / Rpeak　　　(43.1)
Reffective = D / Twrite = D / (Tposition + D / Rpeak)　　　(43.2)

我们希望有效带宽达到峰值的某个比例 F（0 < F < 1，比如 0.9），即 Reffective = F × Rpeak，解出 D：

D = F × Rpeak × (Tposition + D / Rpeak)　⇒　D = F / (1 − F) × Rpeak × Tposition　　　(43.6)

原书的例子：Tposition = 10 ms，Rpeak = 100 MB/s，F = 0.9，则 D = 0.9/0.1 × 100 MB/s × 0.01 s = 9 MB。注意 F/(1−F) 这一项：F 越接近 1，它涨得越猛——这就是"最后那几个百分点最贵"。

计算器

写多少才能接近峰值带宽

改定位时间、峰值带宽和目标比例 F，看需要的缓冲量 D 以及有效带宽曲线。原书还问：95% 和 99% 需要多少？
9 MB
需要的缓冲 D
90 MB/s
有效带宽 Reff
9×
F/(1−F) 放大系数

找到 inode：inode 映射（imap）

在传统 UNIX 文件系统里找 inode 很容易：inode 放在磁盘固定位置的数组里，地址 = inode 表起始地址 + inode 号 × inode 大小。FFS 稍复杂一点——inode 表被切成块分到各个柱面组——但仍然是简单的算术。

LFS 就麻烦了：inode 被撒满了整个磁盘，而且因为从不原地覆盖，最新版本的 inode 一直在搬家。算术失效了。

解决办法是加一层间接：inode 映射（inode map，imap），输入 inode 号，输出该 inode 最新版本的磁盘地址。可以把它想成一个简单数组，每项 4 字节（一个磁盘指针）。每当 inode 被写到磁盘，imap 就更新为新位置。

"计算机科学中的所有问题都可以通过增加一层间接来解决"——当然有点夸张，但确实能解决大多数问题。虚拟内存、文件本身都是间接；imap 则是 inode 号的虚拟化，让 inode 可以随便搬家而不必改所有引用它的地方。代价是额外开销，Wheeler 补了一句："……除了间接层太多这个问题。"

imap 必须持久化（否则崩溃后找不到 inode）。放在磁盘固定位置？那每次更新文件后都要跑去固定位置写 imap，又回到了寻道地狱。LFS 的做法是：把 imap 切成片段（chunk），和其他新数据一起写进日志。于是给文件 k 追加一个数据块时，实际写下的是：

图 43-E　数据块、它的 inode、以及一片 imap 一起写出：imap 片段说"inode k 在 A1"，inode 说"数据块在 A0"。

最后一块拼图：检查点区域（CR）

imap 片段也撒在磁盘上了，那怎么找 imap？没有魔法：文件系统必须在磁盘上有一个固定且已知的起点。LFS 的这个起点叫检查点区域（checkpoint region，CR），它保存所有最新 imap 片段的地址。CR 只是定期更新（比如每 30 秒），所以不影响性能。

图 43-F　完整的指针链：CR（地址 0，固定）→ imap 片段 → inode → 数据块。真实系统有两个 CR、许多 imap 片段。

回顾：从磁盘读一个文件

  1. 挂载时先读 CR，得到所有 imap 片段的地址，把整个 imap 读进内存缓存。
  2. 给定 inode 号，在内存 imap 里查到 inode 的最新地址，读 inode。
  3. 之后与普通 UNIX 文件系统完全一样：用直接/间接/双重间接指针找数据块。

常见情况下，LFS 读文件的 I/O 次数与传统文件系统相同——imap 整个缓存在内存里，额外的工作只是一次内存查表。

目录与递归更新问题

目录在 LFS 里和经典 UNIX 一样：就是一组 (名字, inode 号) 映射。在目录 dir 中创建文件 foo 并写入数据，会在日志里（攒成段后）顺序写下：

图 43-G　创建 foo：文件数据 Dk、inode k、目录数据（含 (foo, k)）、目录 inode、一片 imap（同时记录 k 和 dir 的新位置）。

访问 foo（inode 号 k）的过程：查 imap（在内存）得到目录 dir 的 inode 在 A3 → 读目录 inode 得到目录数据在 A2 → 读目录数据得到 (foo, k) → 再查 imap 得到 inode k 在 A1 → 读数据块 A0。

imap 还顺手解决了一个严重问题：递归更新问题（recursive update problem）。任何"从不原地更新"的文件系统都会遇到它：inode 一更新就换了位置；如果目录里存的是 inode 的地址，目录就得跟着改（于是目录也搬家），目录的父目录又得改……一直改到根。

假如目录里存的是 inode 地址 ① 改 /home/remzi/foo → foo 的 inode 写到新地址 ② remzi 目录要记新地址 → 目录块搬家 ③ remzi 的 inode 要改 → 它也搬家 ④ home 目录块、home 的 inode …… ⑤ …… 一直改到根目录 LFS：目录里存 inode 号，位置交给 imap ① foo 的 inode（号 k）写到新地址 A9 ② 只改 imap[k] = A9（imap 片段随段写出） remzi 目录块：(foo, k) —— 一个字节都不用改home、根目录同样不受影响 ✓ 递归在第一层就被截断
图 43-H　递归更新问题。通过间接层，inode 的位置变化只反映在 imap 里，目录保持同样的名字→inode 号映射。

模拟器：LFS 的日志（仿 lfs.py）

下面这个模拟器按 lfs.py 的思路实现了一个迷你 LFS：地址 0 是 CR，其余地址按段排列（每行一段，8 块）。命令格式与 lfs.py -L 相同：c,/foo 创建文件，d,/dir 创建目录，w,/foo,起始块,块数 写文件，r,/foo 删除，l,/foo,/bar 建硬链接；用冒号分隔。每条命令执行完都会更新 CR（和 lfs.py 默认行为一样）。

数据块 D 目录数据块 inode I imap 片段 检查点区域 CR 段摘要 SS 虚线半透明 = 垃圾（不可达）
模拟器

写入被顺序追加到日志末尾

单步执行命令，蓝框是这一步新写的块。观察：每条命令写了哪些块、以什么顺序；哪些旧块变成了垃圾；读一个路径要经过哪些块。
0
日志中已写的块（不含 CR）
0
其中存活块
0
其中垃圾块
0
本步写入块数

新问题：垃圾回收

LFS 总是把文件的最新版本（数据 + inode）写到新位置，于是磁盘上到处散落着旧版本，我们（很不客气地）称之为垃圾（garbage）。例如文件 k 只有一个数据块 D0，我们覆盖它：

图 43-I　覆盖写：新的 D0 和新的 inode 写在 A4 附近，左边的旧 D0 和旧 inode 都成了垃圾。

如果是给文件 k 追加一个块，旧 inode 变成垃圾，但旧数据块 D0 仍被新 inode 指着，依然存活：

图 43-J　追加写：只有旧 inode 是垃圾，D0 仍是文件的一部分。

旧版本可以保留下来，让用户恢复误删、误改的文件——这叫版本化文件系统（versioning file system）。LFS 则只保留最新的存活版本，于是必须在后台定期清理（cleaning）这些旧版本，让空间可以重新写入——这是一种垃圾回收（garbage collection）。

关键在于按段清理。如果清理器只是零星地释放单个块，磁盘上会满是小空洞，LFS 再也找不到大片连续空间来顺序写，性能就崩了。所以清理器周期性地：读入 M 个旧的（部分使用的）段，找出其中的活块，把它们压缩写成 N 个新段（N < M），然后释放那 M 个旧段。

读入 M = 3 个旧段 判断存活只搬活块 写出 N = 1 个新段 旧的 3 个段整段变成空闲，可再次顺序写 （真实系统里搬家后还要重写相关 inode 和 imap）
图 43-K　清理以段为单位：M 个旧段 → N 个新段（N < M），腾出大片连续空闲空间。

这留下两个问题：机制——怎么知道段里哪个块是活的？策略——多久清理一次、清理哪些段？

机制：用段摘要块判断存活

LFS 在每个段的开头放一个段摘要块（segment summary block，SS），为段中每个数据块记录它的 inode 号 N（属于哪个文件）和偏移 T（是文件的第几块）。判断地址 A 上的块 D 是否存活：

(N, T) = SegmentSummary[A];   // 1. 从段摘要查出：A 是 inode N 的第 T 块
inode  = Read(imap[N]);       // 2. 用 imap 找到 inode N 的最新版本
if (inode[T] == A)            // 3. 最新 inode 认为第 T 块在哪？
    // block D is alive       //    正好是 A → 活
else
    // block D is garbage     //    指向别处（或文件已删）→ 死

第 3 行是关键："活"的定义就是"最新的元数据还指向我"。一个块被覆盖后，新 inode 指向新位置，旧块自然判定为死。

图 43-L　SS 记录"A0: (k, 0)"。查 imap 得到 inode k 在 A1，inode k 的 b[0] 正是 A0 → 该块存活。

LFS 还有捷径：文件被截断或删除时，LFS 增加它的版本号（version number）并记在 imap 里；段中也记录版本号。清理时先比较版本号，不一致就直接判死，省掉读 inode 的 I/O。

模拟器：段清理器

这里的磁盘每段 8 个槽位，第 0 槽是段摘要 SS，其余 7 个放块。先用预设负载把日志写出一堆垃圾，再勾选要清理的段（第二个负载里，试着比较清理"全是热文件旧版本的段"和"冷文件所在的段"各要搬多少块），单步看清理器逐块查 SS、查 imap、查 inode，决定搬还是丢；最后看它写出新段、重写 inode 与 imap、释放旧段。

模拟器

用段摘要判断存活，压缩 M 个段

段左侧显示"活块/已用块"和利用率条。注意：搬走数据块后，指向它的 inode 必须重写，于是其他段里的旧 inode 也会变成垃圾。
0
读入段数 M
0
检查的块 / 其中存活
0
清理器写出的块
0
空闲段：清理前 → 后

策略：何时清理、清理哪些段

何时比较简单：周期性地、空闲时、或者磁盘满了不得不清理时。清理哪些段更难，是许多论文的主题。原始 LFS 论文尝试区分热段（hot segment）和冷段（cold segment）：

热段：内容频繁被覆盖 冷段：内容基本稳定 → 热段先等等：死块会越来越多，将来清理时要搬的活块更少 → 冷段早点清：它的空闲空间不会自己变多
图 43-M　原论文的启发式：先清理冷段，晚清理热段。这个策略并不完美，后来的工作（如 Matthews 等人的自适应方法）做得更好。

崩溃恢复

LFS 正常运行时把写攒在内存段里，段满（或过了一段时间）就写到磁盘。这些写组织成一条日志：CR 指向日志的头段和尾段，每个段指向下一个要写的段。LFS 还会定期更新 CR。崩溃可能发生在这两类写中的任何一个时刻。

写 CR 时崩溃：两个 CR + 头尾时间戳

为了让 CR 更新是原子的，LFS 维护两个 CR，分别在磁盘两端，交替写。写 CR 时的协议：先写一个带时间戳的头部，再写 CR 主体，最后写一个同样带时间戳的尾块。如果在更新 CR 期间崩溃，头尾时间戳就会不一致；LFS 总是选择时间戳一致且最新的那个 CR。

写段时崩溃：前滚（roll forward）

CR 大约 30 秒才写一次，所以最后一个一致的快照可能已经很旧了。只读 CR 恢复的话，最后那几十秒的更新会丢失。LFS 借用数据库里前滚（roll forward）的技术：从最后一个 CR 出发，找到其中记录的日志末尾，继续往后读后续的段，看里面有没有有效的更新；有就应用到文件系统上，从而找回检查点之后写入的大部分数据和元数据（细节见 Rosenblum 的博士论文）。

头3 CR-A主体 尾1 ✗ 头尾不一致 段 S1…S3 S4 S5 S6写了一半 空闲 头2 CR-B主体 尾2 ✓ 一致且最新 CR-B 记录：检查点时日志尾在 S3 → 从 S4 开始前滚 S4 ✓ 应用S5 ✓ 应用S6 校验失败 → 停止 CR-A 正在被写成 ts=3 时断电（头=3、尾=1），于是用 CR-B（ts=2），再前滚找回 S4、S5。
图 43-N　两个 CR 交替写 + 头尾时间戳，保证总有一个完整的 CR；前滚则把检查点之后写入的完整段重新应用。
模拟器

在任意时刻拔电源，然后恢复

上排是 LFS 按时间顺序做的写操作（写段、分三步写 CR）。点任意一个按钮表示"做完这一步后崩溃"，然后单步观看恢复过程；切换是否前滚，比较丢了哪些更新。
崩溃点：
-
选用的 CR
-
前滚应用的段
-
丢失的已完成更新

总结：LFS 的遗产

LFS 引入了一种新的更新磁盘的方法：不原地覆盖文件，而是总写到磁盘的未使用部分，之后再通过清理回收旧空间。这种方法在数据库里叫影子分页（shadow paging），在文件系统里常叫写时复制（copy-on-write，COW）。

LFS 的大思路一句话就能说完，但真要做出能用的系统，必须想清楚所有棘手情况：imap 放哪、CR 如何原子更新、如何判断存活、何时清理。另一方面，当系统有根本缺陷时，想想能不能把它反过来变成有用的功能——WAFL 的快照就是范例。

先预测，再验证

（作业 Q5/Q6）在日志模拟器里分别载入"逐块写 4 次"和"一次写 4 块"两个预设。先预测：两者最终的存活块是否一样多？日志中各写了多少块？
看答案

存活块一样多：都是 8 个（根目录块、根 inode、foo 的 inode、4 个数据块、1 个 imap 片段），加上 CR。但逐块写 4 次日志里写了 19 块（11 块是垃圾），一次写 4 块只写了 13 块（5 块垃圾）。每次单块写都会多写一个 inode 和一个 imap 片段，前一次的就作废了。这正说明在内存里缓冲更新有多重要：真实 LFS 会把这 4 次写合并成一次。

（作业 Q7）对比 c,/foo:w,/foo,0,1 与 c,/foo:w,/foo,7,1。第二种情况下 inode 的 size 字段是多少？ptrs 长什么样？
看答案

两者都只写 1 个数据块、1 个 inode、1 个 imap 片段。但 w,/foo,7,1 之后 inode 的 size = 8，ptrs[0..6] 全空，只有 ptrs[7] 指向数据块——size 表示"逻辑长度（块数）"，是最大偏移 + 1，而不是真正分配的块数。中间是一个"空洞"（hole），不占磁盘空间。

（作业 Q8/Q9）预设"文件 vs 目录"和"硬链接"：c 和 d 分别写几个块？l（硬链接）写了哪些块？会分配新 inode 号吗？
看答案

c,/foo 写 4 块：新 inode、父目录的新数据块、父目录的新 inode、imap 片段。d,/bar 写 5 块：多一个新目录自己的数据块（含 . 和 ..），且父目录 inode 的 refs 加 1（子目录的 .. 指向它）。硬链接写 4 块：父目录数据块、父目录 inode、被链接文件的 inode（refs + 1）、imap 片段；不分配新 inode 号——目录里多了一个指向同一 inode 号的名字而已。

（作业 Q10）把"inode 号分配"改成"随机"，载入"作业 Q10"预设（连续创建多个文件）。imap 片段的写入有什么变化？这说明选择 inode 号为什么重要？
看答案

本模拟器每个 imap 片段覆盖 16 个 inode 号。顺序分配时新文件的 inode 号都集中在 0～15，每次创建只写 1 个 imap 片段；随机分配时新文件的 inode 号常落在另一个片段，而父目录（inode 0）在片段 0，于是一次创建要写两个 imap 片段，日志里的元数据更多。真实 LFS 中，让相关 inode 的号码聚集，就能让 imap 更新更紧凑。

在清理模拟器里用第一个负载，勾选段 2 和段 4 清理。先预测：哪些块是活的？清理结束后，段 5 的利用率会怎么变？
看答案

活的是：/a 的第 0 块（版本 v3）、/c 的第 0、1 块、最新的根目录数据块和根目录 inode，共 5 个。清理器要搬走 4 个数据/目录块，然后重写 inode 0、1、3 和 imap 片段——而 inode 1、3 与 imap 片段原本在段 5 里，于是段 5 从 5/7 降到 2/7。清理不只是"搬活块"，还会让别处的元数据作废：这就是清理的隐性成本。

在崩溃模拟器里，选"写 CR-A 主体后崩溃"。预测：恢复时用哪个 CR？不前滚会丢什么？前滚之后呢？
看答案

CR-A 的头部已写成 ts=3，尾部还是 ts=1，头尾不一致，作废；用 CR-B（ts=2）。CR-B 的检查点只包含 S1～S3，所以不前滚会丢掉 S4、S5 里的更新（/c 的创建、b=v2、a=v3、删除 /b）。前滚从 S4 开始读，S4、S5 都完整有效，全部找回，丢失为 0。

动手实验

实验 1：写缓冲到底值多少？seqbuf.c 在真实磁盘上比较三种写法：随机原地 4KB 写、顺序但每块立刻 fdatasync()、把数据攒成 16KB～8MB 的"段"再顺序写并落盘。

cd labs/43-lfs && make && ./seqbuf

示例输出（WSL2 + 虚拟磁盘，你的机器上数字会不同）：

mode                   write       total   syncs   time(s)      MB/s   ms/sync
1 rand-inplace          4 KB     2000 KB     500     0.485      4.03     0.969
2 seq-sync-each         4 KB     2000 KB     500     0.420      4.65     0.840
3 seg-buffered         16 KB    65536 KB    4096     4.945     12.94     1.207
3 seg-buffered         64 KB    65536 KB    1024     1.121     57.12     1.094
3 seg-buffered        256 KB    65536 KB     256     0.436    146.72     1.704
3 seg-buffered       1024 KB    65536 KB      64     0.301    212.95     4.696
3 seg-buffered       4096 KB    65536 KB      16     0.138    463.15     8.637
3 seg-buffered       8192 KB    65536 KB       8     0.145    442.38    18.084

怎么读：每次落盘有约 1ms 的固定开销（相当于 Tposition）。只写 4KB 就落盘，不论随机还是顺序都只有几 MB/s——"顺序但不缓冲"没用。段越大带宽越高，到 4MB 左右趋于饱和。代入式 (43.6)：Tposition≈1ms、Rpeak≈500MB/s、F=0.9 时 D≈4.5MB，与实测吻合。（虚拟磁盘底层多是 SSD，所以随机和顺序的 4KB 写差别不大；在机械盘上随机写会慢得多。）

实验 2：迷你 LFS 模拟器。lfs_mini.py 是本页模拟器的 Python 版（带段摘要块），命令格式同 lfs.py -L：

python3 lfs_mini.py -L "c,/foo:w,/foo,0,1" -c
python3 lfs_mini.py --demo-clean

示例输出（节选，确定性结果）：

[  0] live checkpoint: 12 --
[  1]      segment summary: 2:(dir,0,0) 3:(inode,0,-) 4:(imap,0) 5:(inode,1,-) 6:(dir,0,0) 7:(inode,0,-) 8:(imap,0)
...
[  9]      segment summary: 10:(data,1,0) 11:(inode,1,-) 12:(imap,0)
[ 10] live data (inode 1, off 0) v1
[ 11] live inode 1 type:reg size:1 refs:1 ptrs: 10 -- -- -- -- -- -- --
[ 12] live chunk(imap 0): 7 11 -- -- -- -- -- -- -- -- -- -- -- -- -- --

第二轮：选利用率最低、但还有活块的两个段 [2, 4] 清理
  检查 [ 22] SS=('data', 1, 0) -> 活
  检查 [ 34] SS=('data', 3, 0) -> 活
  ...
搬走 5 个活块后： S0:0/0 S1:0/0 S2:0/0 S3:0/0 S4:0/0 S5:2/7 S6:7/7 S7:1/1
文件内容（清理后应不变）： ['/a[v3,v6]', '/c[v5,v5,v7]']

该观察到：写一个块依次追加数据块 → inode → imap 片段，CR 指向最新 imap；清理前后每个文件的内容（块版本号）完全不变，但段 5 的利用率因为 inode 被重写而下降。详见 labs/43-lfs/README.md。

自测题

1. imap 已经整个缓存在内存里时，LFS 读一个文件的数据块，与 FFS 相比额外的开销主要是？
CR 只在挂载时读一次，之后整个 imap 缓存在内存。原书：常见情况下 LFS 读文件的 I/O 次数与典型文件系统相同，额外的只是在 imap 里查 inode 地址。
2. 为什么 LFS 不把 imap 放在磁盘的固定位置？
原书 43.5：放在固定位置，每次文件结构更新后都要再写一次 imap，引入更多寻道。LFS 把 imap 片段和其他新数据一起写进日志。
3. 在目录 dir 中创建文件 foo 并写入一个块，这次写出的 imap 片段需要记录哪些 inode 的新位置？
foo 的 inode 是新的，dir 的数据块变了所以 dir 的 inode 也被重写到新位置——两个都搬了家，imap 要同时记录 m[k] 和 m[dir]（图 43-G）。
4. "递归更新问题"指的是什么？
任何从不原地更新的文件系统都会遇到它。LFS 让目录只存 inode 号，位置变化只反映在 imap 中，递归被截断。
5. 清理器检查地址 A 上的数据块：SS 说它是 (inode N, 偏移 T)；imap[N] 指向的 inode 中 ptrs[T] = A'，A' ≠ A。结论是？
存活的定义就是"最新 inode 的第 T 个指针正好指向 A"。指向别处说明这是被覆盖掉的旧版本。版本号只是省 I/O 的捷径，不是必要条件。
6. 按原始 LFS 论文的启发式，热段与冷段应该如何清理？
热段里的块还在不断被覆盖，等得越久死块越多、要搬的越少；冷段的空闲空间不会自己增长，早清早受益。
7. LFS 如何发现 CR 更新到一半就崩溃了？
写 CR 的协议：头（时间戳）→ 主体 → 尾块（时间戳）。头尾不一致即不完整；LFS 选时间戳一致且最新的那个 CR。两个 CR 交替写保证总有一个完整的。
8. Tposition = 10 ms，Rpeak = 100 MB/s，想达到峰值带宽的 99%，每次至少要写多少？
D = F/(1−F) × Rpeak × Tposition = 0.99/0.01 × 100 × 0.01 = 99 MB。对比 90% 只需 9 MB、95% 需 19 MB。
9. 前滚（roll forward）解决的是什么问题？
从最后一个一致 CR 记录的日志尾开始，往后读后续的段，把其中有效的更新应用上去，找回检查点之后的大部分数据和元数据。

常见误区与小结

本章小结