Crash Consistency: FSCK and Journaling
這篇是閱讀 Operating Systems: Three Easy Pieces 的Crash Consistency: FSCK and Journaling 的心得。
不管是 HDD 或 Flash-based SSD，都無法提供 atomic write。對 file system 來說，更新檔案的時候，包含 meta data 和 data 的更新。如果在寫入的過程裡斷電或 OS crash，file system 要如何保證重開機後，資料能回到一致的狀態呢？
這裡以 Linux file system 的術語來討論。假設的 file system 使用的資料如下：
inode bitmap 和 data bitmap 表示 inode/data block 是否有資料。上圖一格在硬碟裡是一個 block。也就是用一個 block 存 inode bitmap、一個 block 存 data bitmap、4 個 block 存 8 個 inode，最後是 8 個 data block。inode 內存owner、可否讀寫、檔案大小、指向 data block 的 pointer 等。
假設我們附加新資料到檔案裡，這個動作需要作三次事：
- 更新 inode
- 增加 data block
- 更新 data bitmap
更新後的結構如下：
三者沒有同時完成的話，資料會處於不一致的狀態。比方說有更新 inode 卻沒更新 data block，檔案內會有錯誤的資料 (garbage)；有更新 data bitmap 卻沒更新 inodes，會有 space leak。
解法一：fsck (File System Checker)
早期 file system 的解法 (e.g., Linux ext2) 是事後檢查資料不一致的部份，然後修正它。比方說發現 data bitmap 標示已使用 Db 但沒有 inodes 指向 Db，就修正 data bitmap 為未使用 Db；發現有些檔案不存在任何目錄裡 (目錄的 inodes 壞了)，將這些檔案搬到 lost+found 目錄下。
這作法有些問題：
- 要掃完整個 partition，太慢了。
- 無法處理資料不正確的問題 (inode 指向 garbage)。
解法二：Journaling (aka Write-Ahead Logging)
這個作法普遍用在今日在使用的 file system，像是 Linux ext3 和 ext4 和 Windows 的 NTFS。
基本想法很簡單：先寫入硬碟「準備更新什麼」(journaling)，再開始更新。如果發生 crash，重開機後可以依 journal 重作一次。也就是說，每次寫入的時候增加一些成本，換得 crash 後可以在很短的時間內還原到資料一致的狀態 (而且不會有 garbage data)。
下圖是 ext3 的示意圖，其中的 Journal 是 ext2 所沒有的，除此之外，兩者差不多。
回到上面說的例子：附加資料到檔案結尾。寫入的 journal 像是這樣：
- TxB / TxE：transaction begin / end
- I[v2]：inode v2
- B[v2]：bitmap v2
- Db：新增的 data block
這裡是用 physical logging，也就是 log 內的資料和之後更新的資料一模一樣，也可以用 logical logging：記錄要作什麼事，會比較省空間。不過從軟體開發的觀點來看，physical logging 的實作比較簡單，有錯比較好修正。
雖說 journal 看起來很可靠，但每次寫入資料都要寫兩次，效率有點差。改善的方式有：
- 減少產生 journal 的量，也就是 buffer 一串更新，再放入同一個 transaction。比方說短時間內一個目錄內新增兩個檔案，會放在同一個 transaction 內，這樣只會有一份新的 inode 和一份新的 bitmap。
- journal 只存 meta data。相較於 data，meta data 並不大。Btw，包含 data block 的 journal 稱為 data journaling，不包含的稱為 metadata journaling 或 ordered journaling。ext3 可選擇不同的模式。
Journal 本身也會占空間，所以需要清掉已執行的 journal (可以固定一段時間後再作）。我們可以用 circular buffer 存 journal，然後記住目前有效的範圍。如下圖所示，Tx1 ~ Tx5 是目前有效 (未執行) 的 journal：
綜合以上，使用 data journaling 的執行步驟如下：
- Journal write：寫入 journal 的資料，包含 TxB, inode, bitmap, data block。
- Journal commit：寫入 TxE (後述)。
- Checkpoint：寫入資料到它們真正的位置。
- Free：標示 journal 已執行完畢。
Timeline 示意圖：
使用 metadata journaling 的執行步驟如下：
- Data write：data 沒有在 journal 內，所以可以先寫入。只要在 journal commit 前完成即可，和下一步之間沒有強制的執行順序。
- Journal metadata write
- Journal commit
- Checkpoint metadata
- Free
Timeline 示意圖：
為什麼 Journal commit 要特別拆開一步呢？因為硬碟為了提升效能，也會 buffer 一串寫入，再自己排程一起完成。所以 journal commit 作的事就是插入「write barrier」再寫入 TxE，這樣會要求硬碟先完成 barrier 前的操作才能作之後的操作。不過依作者所言，有些家硬碟為了更好的效能，會忽略 write barrier，這….感覺還滿危險的，但沒遇到也不會知道，遇到資料有問題也很判斷是物件損壞、driver bug 還是 file system bug 吧。
ext4 針對 journal 寫入的最佳化
為了寫入 TxE，file system 需要等前面的寫入完成，才會開始寫 TxE。以 HDD 來說，這樣要等硬碟多轉一次。作者很自豪的說他之前的碩士生改善了這點，吸引了 Linux file system 開發者的注意，而一同完成在 ext4 裡。
之所以要將 TxE 分開寫入，是希望 crash 後可以從有無 TxE 判斷是寫入 journal 時還是寫完 journal 才 crash。換個想法，transaction 的資料內包含 transaction 整體資料的 checksum，也可以用 checksum 判斷 transaction 的資料是否正確。如果 checksum 不符，表示在寫入 transaction 時就 crash 了。這樣就可以一次寫入整個 transaction 到硬碟。
其它解法
作者最後列了一些其中作法，其中一個是用 copy-on-write，也就是只附加更新資料，不更改原本的資料。概念和 data journaling 有點像，只不過「journal」本身就是最終資料了。Sun 的 ZFS 是一個例子。關於 copy-on-write 的細節，見 Log-structured File System。
