日志结构文件系统的追加布局

inode编号稳定，位置可以改变 ​

若目录直接指向inode所在设备块，inode每移动一次都要改目录；目录自己的inode又可能移动，修改会向上蔓延。imap把“对象叫什么”和“这一版对象在哪里”分开：文件编号F没有变，目录无需因普通数据覆盖而变化，只需更新 imap[F]。

追加的数据也不是一份稍后必须搬回固定地址的临时副本。在本页模型里，最新数据就留在追加的位置，通过新映射提供正常读取；旧位置变为可回收候选。预写日志理路预写日志Write-ahead logging · WAL规定数据页落盘与提交确认前必须先持久化相应日志，使崩溃后的撤销和重做拥有可靠依据。主要记录恢复所需信息，LSM树理路LSM树：有序段、压实与读路径Log-structured merge tree · LSM tree · SSTable compaction · Memtable以带序号更新实现字典，完整追踪memtable、不可变有序段、tombstone、Bloom过滤和安全发布压实结果的条件。则按键组织多层有序表，三者虽然都会顺序写入，定位对象与回收任务仍不同。

连续的小写入还需要批量 ​

地址相邻，不保证每个小请求都达到大块顺序传输效率。机械盘上，若每批都付一次定位开销 $t$，传输 $D$ 字节、传输速率为 $R$，这一批的平均速率是 $D/(t+D/R)$。假定 $t=0.01$ 秒、$R=100$ MB/s，要达到90 MB/s，解得 $D=9$ MB；这里MB统一按十进制计。

这个算式只展示批量怎样摊薄固定开销，不包含排队、缓存命中、清理或确认延迟。把更新等待到一整段满了可能提高吞吐，也会让同步请求等得更久；实现可以提前写出部分段，不能用未刷出的缓存内容冒充持久成功。

修改文件第二块，追加三份记录 ​

重置DISK-32：检查点位于块0，内容指向imap块4；imap4[F]=3，块3是F的inode，长度512字节，数据块映射为 [1,2]。文件第一块位于设备1，第二块位于设备2。

现在覆盖第二块，文件长度不变。预留的新区域是8、9、10：块8写新数据，块9写新inode，其映射为 [1,8]，块10写新imap，其F项为9。第一块1未修改，继续共享于这两个尚在过渡中的版本。

新版本中的字节300满足 $300=1\times 256+44$，沿0→10→9找到第二块8，从它的偏移44读取。若把文件编号F当成设备块号，或跳过imap仍读取旧inode3，就不会得到这条新映射。

把根先写了会发生什么 ​

若先让检查点0持久地指向10，而新imap10尚未持久，恢复入口直接指向未完成对象。即使10已经写好，inode9或数据8未持久也会在后续一层断开。单独保证每一块不撕裂，不能保证它们形成同一完整版本；依赖对象先持久、入口后发布的顺序不可省略。

在正确顺序下，旧块2、3、4只有在新根已发布且旧读者不再使用它们后，才可回收。块1仍由新inode引用，不能随着旧inode一起释放。如果加入历史快照，还必须保留所有快照根可达的块，不能仅按最新根判废。

周期检查点需要额外恢复机制 ​

本例每次持久提交都更新检查点，故恢复只读检查点，不承诺找回未发布尾部。真实LFS可以降低检查点频率，再从最近检查点之后扫描有效日志记录，执行roll-forward；这需要识别完整记录、处理文件与目录一致性等额外规则。不能一方面隔很久才更新检查点，另一方面仍仅用本例四层读取就声称所有已确认更新都可恢复。

真实检查点也可能大于一次原子写单位，需要双检查点及完整性判定等机制。本页把这一问题明确收进“256字节检查点原子”的假设；若设备不提供该原子单位，就要更换发布协议，而非继续引用本例证明。

追加解决写入形状，也制造回收工作 ​

成功发布后，新数据、inode和imap位于追加区域，旧版本留下空洞。如果每次只标出孤立旧块，空闲空间可能不足以形成下一次大段写入。段清理理路日志段清理与写放大LFS segment cleaning · 段清理 · Cleaning write amplification按当前映射判定日志段中的活块，先复制并持久发布新地址再回收旧段，逐项核算净释放空间、数据写放大和含读取的清理成本。需要把仍活的块搬走、更新引用，才能整段回收，并为复制付出额外I/O。

读取性能也不由“写得顺序”自动保证。连续文件块可能在多次覆盖后散落于多个段，imap和inode还会增加定位层次；缓存、数据聚集和清理时的布局选择会影响读取。本页的数值终点是正确定位与掉电版本选择，不是某种现实工作负载的性能结论。

迁移练习：如果这次是追加第三块而非覆盖第二块，新inode应指向 [1,2,8]、长度768。块2仍然活着，只有旧inode和imap可能过期。这能检验读者是否根据可达关系判活，而不是把“上一段里的东西”一律当作垃圾。