Advanced Storage SystemsNTHU — Spring 2026
← Back to Crash Consistency

Crash Consistency

Niko 的 Mac Mini 又飛了

Niko 除了懂得 dream coding 以外，還會鐵頭功。上學期半夜寫 code 寫到睡著（請見黑歷史）， 這學期 Niko 故態復萌，但這次比較衰，忘了存檔，頭一歪倒在鍵盤上，整台 Mac mini 被撞飛到地板，「啪」的一聲扯斷電源以外，銀色的蘋果 logo 當場裂開。

隔天早上 Capoo 去收屍，Niko 笑稱：

老弟，安啦！你沒聽說過 3 秒定律嗎？「食物掉地上，三秒內還能吃啦！快撿起來吃！」我們家 Mac mini 比麥當勞 Big Mac 小號許多，掉地上過了一晚，應該是壞不了的。

Capoo 仍小心翼翼的把命案現場的 Mac mini 拿去 Studio A，請求檔案救援。工程師把硬碟抽出，外接到另一台電腦，掛載檔案系統，請問，工程師會看到什麼 outcome？

  1. main.c 完好無缺，dream coding 的內容都還在（editor 有 autosave，kernel 也及時 flush 完了，Niko 賺到）
  2. main.c 回到前天的版本，Niko 整晚的心血蒸發
  3. 檔案大小看起來是新的，但打開後半段是一堆亂碼
  4. 檔案大小是舊的，但硬碟上其實已經有幾 KB 的新 data block 被寫下去了，只是 ... 找不到在哪邊
  5. 工程師打開 main.c，裡面是 Niko 室友昨天刪掉的情書片段

答案是：不一定。這五種 outcome 工程師都可能遇到。取決於 Mac mini 落地那一瞬間，剛好把哪些東西寫進了 SSD 了。

一個 write() 看起來只是把 bytes 寫入硬碟，背後其實要同時更新四個獨立的 on-disk structure：data block 本身、inode（檔案大小、timestamp、block pointer）、data block bitmap、還有 directory entry（如果這是新檔案）。這四種結構不會同時寫入硬碟。Niko 的 Mac mini 落地瞬間，這四個結構可能剛好只寫完了其中任意的 subset，每一種 subset 就對應工程師可能看到的一種 outcome。

快速複習

上學期 OS 課我們學過 inode 裡面記錄了：檔案大小、UID/GID、permission bits、timestamp、還有 direct pointer + single/double/triple indirect pointer。我們知道 directory entry 把檔名對應到 inode number，以及 superblock 在 mount 時怎麼被 kernel 讀進來。dentry cache、path resolution、hard link vs. symbolic link 這些名詞你應該都不陌生。

Extent

ext2 的 block pointer 模型有一個缺點：大檔案的 metadata 佔空間。

一個 10 GB 的 4K 影片，block size 4 KB，這個檔案佔了 10 GB ÷ 4 KB，約 2.6M 個 block。ext2 用 direct / single / double / triple indirect pointer 把這些 block number 一個個列出來，光是 pointer 本身就要 2.6M×4≈10MB2.6M \times 4 \approx 10 MB 的 metadata 空間，而且讀越後面的 block 要走越多層 indirect（最多 3 層）。

ext4 改用 extent。一個 extent 在 ext4 inode 裡只佔 12 bytes，記錄：起始 block number（48 bits）、連續長度（15 bits，剩 1 bit 用來標示 uninitialized extent）、檔案內 offset（32 bits）。一個 extent 最多可以描述 2152^{15} 個連續 block，也就是 128 MB。10 GB 影片，如果 allocator 順利分配到連續區域，只需要 10 GB/128 MB=8010 \text{ GB} / 128 \text{ MB} = 80 個 extent，總共 80×12=96080 \times 12 = 960 bytes。

但 extent 有一個前提：disk 上真的有連續的空閒空間。如果硬碟嚴重 fragment，allocator 找不到大塊連續區域，一個 10 GB 檔案可能還是會被拆成幾千個小 extent。這時候 ext4 會把 extent list 組織成一棵小型的 extent tree（B+Tree 的變形），inode 裡只放 root，其他 extent node 放在 data block 裡。結構和 B+Tree 一樣。

那麼，block allocator 怎麼決定 block 要放在哪？

Allocator 與 Delayed Allocation

Allocator 的實做，最簡單版本：每 write() 100 bytes，我就立刻挑一個空閒 block 給你；下一次 write() 再 100 bytes，我再挑一個。每個 write 都是一個獨立決定。這些 block 可能散在硬碟各處。結果變成，寫一個檔案，邏輯順序連續的資料在硬碟的實體順序卻被切成很多小 extent 散佈在硬碟各處，extent tree 會變很大。其他檔案也在同時寫，大家分到的 block 互相交錯，硬碟被切得稀巴爛。我們稱之為 fragmentation

Rutgers University 的一篇有名的論文測試用 git pull 來觀察 fragmentation 對效能的影響：一個全新的 XFS 在 SSD 上 grep 大約 10 sec/GiB，但同一顆硬碟經過一萬次 git pull 之後，同樣的 grep 要 19 sec/GiB，單純因為 fragmentation，速度就慢了 1.9 倍。

Git aging workload on XFS on SSD： grep cost grows from ~10 to ~19 sec/GiB as pulls accumulate
XFS 在 SSD 上隨著 git pull 累積，grep 從 10 sec/GiB 慢到 19 sec/GiB（1.9x slowdown） （圖片來源：Conway et al.， FAST '17）

ext4 的解法叫 delayed allocation：先把 dirty page 留在 page cache 裡，不急著決定實體位置。只有當 kernel 要把 page 真正寫進硬碟的時候（通常是 30 秒後的 periodic writeback，或是你呼叫 fsync()），allocator 才一次看見「哦，這個檔案這段時間累積了 50 MB 要寫」，然後一口氣找一塊 50 MB 的連續空間，給你一個大的 extent。

藉由把「何時寫」和「寫到哪」這兩個決定分開，allocator 等到有足夠資訊才下手，extent 的長度自然就大了。

Delayed allocation 的代價是，如果在 writeback 之前斷電，那些還只在 page cache 裡的 dirty page 會蒸發。因此，當你寫很重要的資料的時候，你通常會呼叫 fsync()，強迫 kernel 立刻 flush the cache。

Metadata 與 Data 不同步的後果

現在回到最開頭那個斷電問題。為什麼可能出現五種不同結果？

假設你對一個既有的 1 MB 檔案 append 10 MB。kernel 在記憶體裡要做四件事：

  1. 把 10 MB 資料寫進 page cache（data block 的 dirty page）
  2. 在 block bitmap 裡把分配到的新 block 標成 used（bitmap dirty）
  3. 把新 block 的位址加進 inode 的 extent list（inode dirty）
  4. 把 inode 的檔案大小從 1 MB 改成 11 MB（inode dirty）

這四個步驟都只在記憶體內操作。真正把它們寫到硬碟是靠 writeback，而 writeback 沒有順序保證任何一個 subset 寫到一半斷電，你都會掉進一種不同的 outcome：

  • 只有 (2) 寫完：bitmap 說這些 block 被用了，但沒有任何 inode 指向它們，變成 orphan block，硬碟空間被浪費。
  • (1) + (2) 寫完，inode 沒更新：資料在 disk 上，但 inode 不知道，一樣找不到。
  • (3) + (4) 寫完，(1) 沒寫完：inode 指向那些新 block，檔案大小也變成 11 MB，但 block 裡還是前一個使用者刪檔後留下的內容。read() 會合法地回傳這些舊資料，產生資安漏洞。
  • (3) 寫完、(2) 沒寫：inode 指向一些 bitmap 認為「還是空的」block，下次 allocator 會把同一塊 block 分配給別的檔案，兩個檔案共用同一塊硬碟區域，資料互相覆蓋。

上面只是四種組合。實際上這四個結構落地與否共有 16 種可能，自己玩一下：

Niko 的硬碟偵探社
Niko 對 main.c append 10 MB。Mac mini 在寫一半時落地，這四個結構哪些已經寫到 SSD？點一下切換，看工程師最後會看到什麼：
BNiko 整晚做白工0/4 flushed
$ stat main.c→ 1 MB
$ cat main.c→ Niko 前天的版本
$ df→ 和 crash 前一樣
24 = 16 種組合、7 種 outcome

fsck：收拾爛攤子

Unix 有一個古老的工具叫 fsck（file system check）。mount 時 kernel 如果偵測到上次沒乾淨地 unmount，就會自動跑 fsck。它把整顆硬碟掃一遍，把每一個結構比對一遍來抓出上面提到的錯誤。例如：bitmap 說 used 卻沒人指，就釋放掉；inode 指到 bitmap 認為空的 block，那就把 bitmap 改成 used；data block 看起來有內容但沒 inode 指，放進 /lost+found/ 讓使用者自己處理。

fsck 不能解決萬事。第一，它要掃整顆硬碟，通常會頗慢。第二，它看不出上面提到的資安漏洞，inode 跟 extent 完全對得起來的話，fsck 不知道那些 block 裡的 bytes 是前任使用者的資料。

Crash Consistency

因此，「metadata 和 data 必須一起好好的寫完」這件事，是現代檔案系統設計最重要的設計之一。 我們稱之為 Crash Consistency 。

接下來的單元，我們會學習三種不同 Crash Consistency 確保方法：

  • Copy-on-Write：不原地覆蓋舊 metadata，新的 metadata 寫到新位置，最後用一個 atomic pointer swap 把 root 指過去。
  • Journaling：改動先寫到一個 append-only 的 journal，確定 journal 寫入硬碟之後，才去改真正的 metadata。crash 之後重新掃 journal 把沒做完的事補完或捨棄。
  • Log-Structured：整個 filesystem 就是一條不斷 append 的 log，metadata 和 data 都是 append，crash 後從 log 尾端往回走，來重建狀態。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

  1. Extent 模型在什麼情況下會退化？請描述一個 workload，讓 ext4 的 extent tree 退化得和 ext2 的 indirect block 差不多大。

  2. Delayed allocation 讓 extent 變長，但代價是什麼？請從「dirty page 在 page cache 裡待多久」和「使用者預期」兩個角度分析：一個文字編輯器每 30 秒自動存檔，但不呼叫 fsync()，斷電後使用者可能會很傻眼，為什麼？

  3. 假設一個 filesystem 在 crash 時，只有 block bitmap 更新寫進硬碟了，inode 和 data block 都還沒寫。重開機後 df 顯示硬碟少了幾 MB 空間，但你怎麼找都找不到對應的檔案。這是上文提到的哪一種災難？