编程语言研究书库
操作系统导论(OSTEP)

崩溃一致性与日志结构文件系统 — 断电那一刻,盘上状态怎么救

17 崩溃一致性与日志结构文件系统 — 断电那一刻,盘上状态怎么救

1. 这一章讲什么

上一章留的尾巴现在兑现:文件系统「迟早」要把缓存里的脏块写盘, 而磁盘一次只承诺一块的原子写——「改两个地方」的操作永远有 中途断电的缝。本章先把这个问题的全部形状摆出来(三种目标块、 六种事故),然后讲两代解法:老派的 fsck(事后修)和现代主流的 日志(事先记账);最后讲 LFS——一个把「顺序写」信仰推到极致、 顺手把崩溃恢复变得平凡的设计。

2. 顶层全景

  问题:一次 append = 写 3 块(inode 新指针 + 数据块 + 数据位图),
        断电可能落在任何一步之间 → 6 种事故
        (垃圾数据/空间泄漏/位图不一致/指向空块……)
        │
  解法一:fsck —— 允许坏,重启后全盘扫描修
        问题:盘越大越慢(TB 级 = 小时级);只修元数据一致性,不修用户数据
        │
  解法二:日志(journaling / write-ahead logging)
        先记账:TxB [块块块] TxE → 提交后再写到最终位置(checkpoint)
        崩溃恢复 = 重放日志尾部,不扫全盘
        变体:数据日志(写两遍,稳但慢) vs 有序/元数据日志(数据不写日志,
              但必须先于元数据落盘:「被指者先于指人者」)
        │
  极致:LFS —— 从不覆写,永远顺序写
        段缓冲 + 一次大写 → 带宽贴峰值
        代价1:inode 到处跑 → inode 映射(imap)+ 检查点区(CR)两层间接
        代价2:旧版本成垃圾 → 分段垃圾回收(热段晚清、冷段早清)
        意外收获:崩溃恢复几乎免费(指针永远指向已写好的数据)

图说:三代解法,一代比一代「把顺序写信仰贯彻得彻底」。

3. 核心原理

3.1 主线例子:一次 append,六种死法

书里的教学场景,数字照抄1:玩具文件系统有 8 inode、8 数据块, inode 2 属于某文件,size=1,指针指向数据块 4(Da)。 现在 append 一块:内存里备好三块待写——

  • I[v2]:size=2,新指针指向块 5;
  • B[v2]:数据位图,从 00001000 变 00001100(块 5 标记已分);
  • Db:新数据块。

目标终态三者齐全;但磁盘一次落一块,断电有 6 种落点(1 成功 2 失败 的组合有 3 种,2 成功 1 失败的组合也有 3 种)2:

落盘情况后果
只落了 Db无害:没人指向它、位图也说它空闲,当作没写过
只落了 I[v2]读垃圾:指针指向块 5,那里还是旧数据;位图与 inode 不一致
只落了 B[v2]空间泄漏:位图说块 5 已分,没有 inode 用它,永远闲置
I[v2]+B[v2],没落 Db元数据自洽但指向垃圾——fsck 也救不了用户数据
I[v2]+Db,没落 B[v2]位图与 inode 不一致,需修复
B[v2]+Db,没落 I[v2]不一致,且不知道该块属于谁

图说:六种里只有第一种侥幸没事。问题的正式名字: 崩溃一致性(=一致更新问题)——想把盘上状态从一个一致点 原子地搬到下一个一致点,但硬件只给一块一块的写3。

3.2 老解法:fsck 及其荒唐

早期文件系统的态度:允许坏,重启再修。fsck 在挂载前跑, 分阶段:超级块健全性检查 → 扫全部 inode/间接块重建位图 (以 inode 为准)→ 逐个 inode 查字段、核对链接数 (自己重算一遍,对不上就改;发现无人引用的 inode 塞进 lost+found) → 查重复指针、越界指针 → 目录检查(. 和 .. 是否在前、引用是否合法)4。

两个根本问题:一是慢——为修三个块的事扫全盘,书里原话: 「好比钥匙掉在卧室,却从地下室开始搜遍全屋」;盘越大越不可行5。 二是能力有限——它只求元数据内部自洽,「inode 指向垃圾」这类 对用户真实伤害最大的场景,它管不着6。

3.3 现代解法:日志(预写日志)

思想借自数据库:覆写原处之前,先在盘上知名位置留一条笔记 (写前 = write-ahead;笔记按序排 = log)7。 ext3 的布局 = ext2 全套 + 一个日志区8。

数据日志的完整协议(照抄书里的三步)9:

  日志:  TxB | I[v2] | B[v2] | Db | TxE      ← TxB/TxE 带同一事务号 TID
  1. Journal write :整笔写进日志,等完成
  2. Journal commit:写 TxE 块,等完成 ──「已提交」
  3. Checkpoint    :把三块写到它们的最终位置

三个工程细节,每个都堵一个洞:

  • 为什么不能五块一起发? 磁盘内部会重排:可能 TxE 先于 Db 落盘, 断电后日志看起来「完整」(有头有尾号也对),恢复时就把垃圾块 当数据重放。所以 TxE 最后单独写,且利用「512 字节写必原子」 的硬件承诺10。ext4 的改进:TxB/TxE 带校验和, 整笔一把写、恢复时校验和不符就丢弃——一次写省一次旋转延迟, 威斯康星的一个小改动随 Android 进了亿万台设备11。
  • 恢复:崩在提交前——丢弃,当没发生;崩在提交后——重放 (redo)日志里已提交的事务,把块再写一遍(幂等,写两遍无害)12。
  • 日志 finite:当日志写满?循环日志:checkpoint 完成后在 日志超级块里标记释放,空间复用;恢复只需从头扫到第一个 未 checkpoint 的事务13。

元数据日志(有序日志)——治「每块写两遍」的贵14: 用户数据不进日志(大多数 I/O 是数据,省一半流量), 日志只记 TxB I[v2] B[v2] TxE。但引出一个顺序问题: inode 先落盘、数据后落盘,崩溃后恢复出的文件系统元数据一致、 内容却是垃圾。所以铁律是:

被指者先于指人者:数据块先写,元数据(带指针的)后写。15

ext3 的有序模式、NTFS、XFS 都是这个家族;差别只在数据语义的强弱 (ext3 还提供 data 模式全日志、unordered 模式)。「先数据后元数据」 这条铁律不止于日志——软更新、copy-on-write 等其它崩溃一致性 方案的核心也是它16。

块复用的坑:删除文件再分配块时,新数据若先于「块被重新分配」 的元数据落盘,崩溃后元数据可能把老数据当新数据。ext3 的 Stephen Tweedie 的原话:「整个系统里最难看的部分?删除。 跟删除有关的一切都毛骨悚然」17。

3.4 LFS:把顺序写信仰推到底

动机(90 年代初 Berkeley,Rosenblum 与 Ousterhout): 内存越来越大 → 缓存吃掉读 → 盘流量几乎全是写; 而随机写比顺序写慢几十倍;老文件系统还不懂 RAID 的小写问题。 理想:把所有写都变成顺序写18。

基本机制:更新(数据 + inode + 一切)先在内存攒成段 (segment,几 MB);段满了,一次连续写到盘上空白处。 永不覆写19。光「顺序」不够——隔一会儿写一块,盘转走了还得 等旋转;必须攒够量。攒多少?书里的账:定位时间 10ms、峰值 100MB/s、要 90% 效率 → D = 9MB;要 99% 得约 99MB (公式 D = F/(1−F) × Rpeak × Tposition)20。

新问题一:inode 找不到了(从不覆写 ⇒ 最新 inode 永远在搬家)。 解法:一层间接——inode 映射(imap):inode 号 → 最新版本 磁盘地址;imap 的碎片就写在数据旁边,随段一起落盘21。 新问题二:imap 又散了?再固定一个检查点区(CR): 盘开头,指向所有 imap 碎片;每 30 秒左右更新一次。 读文件 = CR → imap(缓存进内存)→ inode → 数据, 常规读的 I/O 次数和普通文件系统一样22。 递归更新问题也顺带解决:目录里存的永远是 inode 号, inode 搬家的变化全部吸收在 imap 里,目录本身不动23。

新问题三:垃圾。旧版本散落全盘。段摘要块(segment summary) 记每块的 (inode 号, 偏移);判活:查 imap 里该 inode 的当前指针 是否还指向这块24。回收策略:冷段(内容稳定)早清、 热段(反复覆写)晚清——等它自己死更多25。

崩溃恢复是 LFS 的隐藏彩蛋:CR 双副本交替写(时间戳成对校验), 崩溃后回滚到上一个一致的 CR;由于指针只指向已写完的数据, 重放的需求几乎不存在26。今天 LFS 的思想活在闪存盘(本库 18 章: 闪存本来就「先擦后写、从不覆写」)、ZFS/BTRFS 的 COW 设计里。

4. 作者的判断与证据

书里给了证据的判断:

  • 六种崩溃场景的穷举有完整图解;
  • fsck 各阶段引 McKusick-Kowalski 论文,慢的问题引 TB 级测量的文献5;
  • 日志协议每步的「为什么」(TxE 单写、校验和、循环复用、数据先写) 都给了具体的失败场景作为证据101115;
  • LFS 的缓冲量公式与热冷段策略引原始论文 [RO91][MR+97]2025。

作者的判断(立场):

  • 「细节重要」提示被显式立碑:大意容易懂,能跑的系统全是细节27。
  • 对 fsck 的判词(搜全屋找钥匙)是全书最锋利的比喻之一。

5. 边界与局限

  • 元数据日志保证元数据一致,用户数据最多回滚到旧版本 (刚写的内容丢失)——「文件系统一致性 ≠ 你的数据安全」, fsync 与掉电丢数据的争吵都源于此。
  • 写屏障会被某些磁盘无视(书里引 [C+13,R+11] 的研究)—— 协议层正确不等于设备层诚实,这是全章最阴暗的一行注脚28。
  • LFS 在纯 HDD 时代未统治市场:垃圾回收的写放大与读性能问题 在「盘半满 + 随机写」工作负载下会恶化;闪存时代思想借尸还魂, 但 FTL 的磨损均衡把「冷段早清」这类策略的复杂度收进了设备。

6. 可带走的

  1. 「改两个地方」+ 「硬件一次只原子一块」= 崩溃一致性问题。 认出这个形状,数据库、配置系统、双写一致性都是它。
  2. 先记账,后动账:日志把「恢复」从扫全盘变成重放尾巴。 更新时多付一点,恢复时省一大笔——这个交换在一切日志系统里成立。
  3. 被指者先于指人者——指针类更新的写序铁律。
  4. 事务的原子性靠「提交块」兑现:TxE 要单独、要原子(512B)、 最好带校验和。
  5. 一层间接解决定位问题(LFS 的 imap),再固定一个锚点解决 间接自身的定位(CR)——两层结构是「永动数据」的通用答案。
  6. LFS 的崩溃恢复近乎免费,因为它从不让指针指向「还没写完」的数据—— 不变式设计往往顺手把最难的问题消掉。

7. 原文地图

主题原书章原文位置
问题定义(一致更新问题)42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:170(搜「Crash Consistency Problem」)
三块的 append 例子42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:41(搜「Detailed Example」)
六种崩溃场景42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:114(搜「Crash Scenarios」)
fsck 各阶段42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:187(搜「fsck」)
「搜全屋找钥匙」42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:263(搜「keys」)
日志基本思想(写前日志)42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:272(搜「write-ahead」)
数据日志三步协议42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:314(搜「Data Journaling」)
TxE 为何最后单写42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:380(搜「TxB」)
校验和优化(ext4)42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:404(搜「checksum」)
恢复 = 重放42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:453(搜「Recovery」)
循环日志42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:498(搜「finite」)
元数据日志与「先数据后元数据」42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:555(搜「Metadata Journaling」)与:596(搜「first」)
Tweedie 谈删除之难42. Crash Consistency: FSCK and Journalingtext/44-ch42-42-crash-consistency-fsck-and-journaling.txt:631(搜「hideous」)
LFS 动机43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:7(搜「memories are growing」)
段缓冲与一次顺序写43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:113(搜「segment」)
缓冲量公式(9MB 例)43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:138(搜「How Much To Buffer」)
inode map 与一层间接43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:209(搜「indirection」)
检查点区43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:262(搜「checkpoint region」)
递归更新问题43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:334(搜「recursive update」)
垃圾回收与段摘要43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:350(搜「Garbage Collection」)与:422(搜「segment summary」)
热段冷段策略43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:475(搜「hot」)
CR 双副本与崩溃恢复43. Log-structured File Systemstext/45-ch43-43-log-structured-file-systems.txt:489(搜「Crash Recovery」)

Footnotes

  1. 出处:「42. Crash Consistency: FSCK and Journaling」第 41–113 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:64,搜「I[v1]」)。I[v1] 的内容:size=1,指针指向块 4。 ↩

  2. 出处:「42. Crash Consistency: FSCK and Journaling」第 114–169 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:114,搜「Crash Scenarios」)。 ↩

  3. 出处:「42. Crash Consistency: FSCK and Journaling」第 170–181 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:170,搜「Crash Consistency Problem」)。 ↩

  4. 出处:「42. Crash Consistency: FSCK and Journaling」第 183–260 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:193,搜「phases」)。 ↩

  5. 出处:「42. Crash Consistency: FSCK and Journaling」第 253–270 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:263,搜「keys」)。 ↩ ↩2

  6. 出处:「42. Crash Consistency: FSCK and Journaling」第 185–192 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:190,搜「can't fix」)。 ↩

  7. 出处:「42. Crash Consistency: FSCK and Journaling」第 272–291 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:273,搜「most popular」)。 ↩

  8. 出处:「42. Crash Consistency: FSCK and Journaling」第 292–309 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:306,搜「Journal」)。 ↩

  9. 出处:「42. Crash Consistency: FSCK and Journaling」第 314–348 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:324,搜「TxB」)。 ↩

  10. 出处:「42. Crash Consistency: FSCK and Journaling」第 349–451 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:436,搜「512-byte」)。原文:磁盘保证 512 字节写要么发生要么不发生。 ↩ ↩2

  11. 出处:「42. Crash Consistency: FSCK and Journaling」第 397–418 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:402,搜「Prabhakaran」)。校验和思路被 Linux ext4 采纳。 ↩ ↩2

  12. 出处:「42. Crash Consistency: FSCK and Journaling」第 453–470 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:453,搜「Recovery」)。原文:崩溃在提交前跳过;提交后重放(redo)。 ↩

  13. 出处:「42. Crash Consistency: FSCK and Journaling」第 498–549 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:518,搜「circular」)。 ↩

  14. 出处:「42. Crash Consistency: FSCK and Journaling」第 555–573 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:559,搜「doubling」)。 ↩

  15. 出处:「42. Crash Consistency: FSCK and Journaling」第 589–612 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:597,搜「write data blocks」)。原文:ext3 先写数据块再写相关元数据。 ↩ ↩2

  16. 出处:「42. Crash Consistency: FSCK and Journaling」第 609–612 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:610,搜「pointed-to」)。 ↩

  17. 出处:「42. Crash Consistency: FSCK and Journaling」第 627–634 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:631,搜「hideous」)。 ↩

  18. 出处:「43. Log-structured File Systems」第 1–63 段(text/45-ch43-43-log-structured-file-systems.txt:31,搜「not RAID-aware」)。 ↩

  19. 出处:「43. Log-structured File Systems」第 44–136 段(text/45-ch43-43-log-structured-file-systems.txt:53,搜「never over」)。 ↩

  20. 出处:「43. Log-structured File Systems」第 138–187 段(text/45-ch43-43-log-structured-file-systems.txt:185,搜「9 MB」)。D = F/(1−F) × Rpeak × Tposition;F=0.9、100MB/s、10ms → 9MB。 ↩ ↩2

  21. 出处:「43. Log-structured File Systems」第 189–259 段(text/45-ch43-43-log-structured-file-systems.txt:209,搜「inode map」)。 ↩

  22. 出处:「43. Log-structured File Systems」第 262–302 段(text/45-ch43-43-log-structured-file-systems.txt:268,搜「checkpoint region」)。 ↩

  23. 出处:「43. Log-structured File Systems」第 333–346 段(text/45-ch43-43-log-structured-file-systems.txt:334,搜「recursive update」)。 ↩

  24. 出处:「43. Log-structured File Systems」第 422–466 段(text/45-ch43-43-log-structured-file-systems.txt:429,搜「segment summary」)。 ↩

  25. 出处:「43. Log-structured File Systems」第 468–488 段(text/45-ch43-43-log-structured-file-systems.txt:475,搜「hot」)。 ↩ ↩2

  26. 出处:「43. Log-structured File Systems」第 489–530 段(text/45-ch43-43-log-structured-file-systems.txt:503,搜「two CRs」)。 ↩

  27. 出处:「43. Log-structured File Systems」第 35–42 段(text/45-ch43-43-log-structured-file-systems.txt:35,搜「DETAILS MATTER」)。 ↩

  28. 出处:「42. Crash Consistency: FSCK and Journaling」第 356–376 段(text/44-ch42-42-crash-consistency-fsck-and-journaling.txt:363,搜「write buffering」)。原文:写缓存让「完成」变假,现代系统用写屏障;而有厂商无视写屏障。 ↩

文件、目录与文件系统实现 — 从 open() 到 inode 的访问路径

Previous Page

闪存盘与数据完整性 — 新硬件的新脾气,和「盘会说谎」的应对

Next Page

On this page

17 崩溃一致性与日志结构文件系统 — 断电那一刻,盘上状态怎么救1. 这一章讲什么2. 顶层全景3. 核心原理3.1 主线例子:一次 append,六种死法3.2 老解法:fsck 及其荒唐3.3 现代解法:日志(预写日志)3.4 LFS:把顺序写信仰推到底4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes