檔案系統是作業系統中管理使用者資料的重要子產品。其中一項重要的任務就是確定使用者資料的在系統突然崩潰之後，系統能夠恢複出完整、一緻的使用者資料。本文将會分析兩種流行的檔案系統，Journaling File System 和 Log-structured File System是如何確定資料的一緻性。本文主要參考了OSTEP的42和43章節，強烈推薦任何一位學習作業系統的同學去閱讀這本教材。
什麼是一緻性問題
我們知道，記憶體的速度是遠遠高于磁盤，是以檔案系統為了加速檔案的讀取，往往會使用記憶體頁緩存一些磁盤的資料以加快檔案的讀寫速度，而檔案系統也會在适當的時機，再将髒頁回寫到磁盤中(即writeback操作)。這種回寫操作，一般會涉及到中繼資料的更改(例如on-disk inode)以及檔案資料的更改。一般而言，為了實作高性能，中繼資料的更改和檔案資料的更改往往不是同步的，而是異步的。是以，如果系統突然當機，由于它們中繼資料和檔案資料回寫的異步性，可能會引起一緻性問題。
一緻性問題種類
我們考慮一個簡單的檔案系統的on-disk結構，這個檔案系統包括一個inode bitmap (8 bits，每一個bit表示一個inode)，一個data bitmap (8 bits，每一個bit表示一個data block)，一個inodes區域 (存放inode的磁盤區域，一共8個)，一個data blocks 區域 (儲存檔案資料的磁盤區域，一共8個)。以及一個場景: 一個程序寫入一個data block到一個空檔案。
如下圖所示，這個操作會首先在磁盤的free space中配置設定一個inode (即下圖的
I[v1]
，對應inode号是2，對應的inode bitmap也會被标記狀态為已配置設定)，然後寫入一個data block (即下圖的
Da
，對應data blocks區域的位址是4，對應的data bitmap也會被标記狀态為已配置設定)。當檔案讀資料的時候，我們是通過inode找到對應的data block，是以inode需要儲存對應的data block的位址建立inode-data映射，我們需要把
Da
的位址4寫入到
I[v1]
中，請注意這個隐含的關系。因為這是這個檔案的第一次更新inode，是以我們将這次更新稱為v1更新，是以inode用
I[v1]
表示。
如下圖所示，如果我們繼續往這個檔案寫入一個data block的資料，那麼data blocks區域肯定要更新(即
Db
，對應的data blocks位址是5)，對應的data bitmap也要做第二次更新(即
B[v2]
)，inode也需要記錄新寫入的data block的位址(即
Db
)，是以inode也需要更新，得到
I[v2]
。
如前面介紹，為了提高性能，對應inode bitmap、data bitmap、inodes、data blocks的更新都可能是異步的，檔案系統無法確定它們都同時寫入。而崩潰在任何時刻都可能出現，是以可能檔案系統可能會出現一緻性問題。我們用第二次寫入作為例子，分析有哪些一緻性問題:
- 隻有data block (
Db
- 隻有inode (
I[v2]
Db
Db
- 隻有data bitmap (
B[v2]
- inode (
I[v2]
B[v2]
Db
Db
Db
- inode (
I[v2]
Db
B[v2]
- data bitmap (
B[v2]
Db
I[v2]
接下來，我們将會探讨Journaling File System 和 Log-structured File System如何分别解決這些問題。
Journaling File System 日志檔案系統
日志檔案系統(Journaling File System，或者說JFS) 是一類被廣泛使用的解決檔案系統一緻性的技術。JFS通過journaling去記錄一些檔案系統操作，然後再回寫這些操作到磁盤的政策，實作一緻性保證，使用這些技術的包括ext3/ext4，XFS等主流檔案系統。Journaling的核心思想是:
在更新磁盤上的資料之前，例如更新bitmap，inode，data之前，我們先将這些操作作為日志(log)，先寫入到其他位置(往往是磁盤的某個特定大小的區域)。檔案系統會不斷寫日志(log)，而這些儲存log的區域一般像一個數組一樣将log組織起來，每一個數組單元就是一個log，檔案系統在更新(write)磁盤的資料之前都會先寫入到log中，是以我們也将journalling稱為write-ahead log技術。
當系統崩潰時，檔案系統恢複時就會檢查日志記錄，看看崩潰前的一刻哪些操作是完成的(成功寫入到磁盤)，哪些沒有完成，進而可以恢複檔案系統的一緻性。
我們使用ext3檔案系統作為例子，下圖是一個ext3檔案系統的on-disk結構。它比我們前面讨論的簡單檔案系統稍微複雜點。這裡每一個group相當于前面介紹的簡單檔案系統的on-disk結構，也是包含了data bitmap，inode bitmap，inodes，data blocks等結構。不同之處就是它在磁盤上多配置設定了一個journal區域，用于儲存檔案操作的日志。由于檔案系統包括data和metadata操作，是以它們也有相應的journaling的方法，我們分别讨論。
Data Journaling
我們回到最開始介紹的例子，即需要寫入
Db
，
B[v2]
，
I[v2]
到磁盤的例子。前面我們的操作是讓這些三個需要寫入磁盤的操作，分别寫入到磁盤中。那麼現在，我們可以将他們打包在一起寫入log (或者說journal)，如下圖所示。這裡
TxB
~
TxE
表示一個log entry，箭頭表示這個journal區域可能包含多個log entry，目前我們隻使用一個log entry。
TxB
~
TxE
也表示一系列操作的組成的一個事務(transaction)，
TxB
是這個事務的頭，包含這些操作需要寫入到磁盤的位置資訊(例如
I[v2]
，
B[v2]
，
Db
各自在磁盤的位置，一共三個blocks的位址)，以及一個本次事務關聯的transaction identifier (TID) 。
TxE
辨別事務的結束位置，也包含和
TxB
相同的TID。我們寫入log的操作稱為journal write。
如果這個事務被順利寫入到磁盤，那麼我們可以就根據
TxB
記錄的磁盤的三個blocks的位置資訊，将
I[v2]
，
B[v2]
，
Db
各自寫入到磁盤的位置，我們将這個操作稱為checkpointing。如果這三個blocks都成功寫入了磁盤，那麼我們說這個檔案系統被成功checkpointed，用于記錄log的journal區域(即上圖)也可以被釋放，給其他操作使用。
讨論: 對于前面的例子，我們需要寫入
TxB
，
I[v2]
，
B[v2]
，
Db
，
TxE
總共5個blocks。如果讓這5個blocks一個個按順序寫入，這顯然會影響性能。如果這5個blocks異步寫入依然會存在一緻性問題，例如
TxB
，
B[v2]
，
Db
，
TxE
成功寫入到磁盤後，系統就馬上崩潰，
I[v2]
，還沒有寫入。是以我們可以使用折衷的辦法，異步寫入
TxB
，
I[v2]
，
B[v2]
，
Db
，等它們都成功後，再寫入
TxE
。是以我們可以将journaling分解為3個操作:
- Journal write：将
TxB
- Journal Commit：寫入
TxE
- Checkpoint：将事務中的資料，分别各自回寫到各自的磁盤位置中。
Recovery恢複: 我們利用上面的三個操作去描述檔案系統是如何保證一緻性的。
- 崩潰發生在Journal Commit完成前：那麼檔案系統可以丢掉之前寫入的log。由于磁盤具體位置的bitmap，inodes，data blocks都沒變，是以可以確定檔案系統一緻性。
- 崩潰發生在Journal Commit後，Checkpoint之前：那麼檔案系統在啟動時候，可以掃描所有已經commited的log，然後針對每一個log記錄操作進行replay，即recovery的過程中執行Checkpoint，将log的資訊回寫到磁盤對應的位置。這種操作也成為redo logging。
- 崩潰發生在Checkpoint完成後：那無所謂，都已經成功回寫到磁盤了，檔案系統的bitmap、inodes、data blocks也能確定一緻性。
Journal是如何儲存在磁盤的: 如前面所說，journal區域是磁盤一段特定空間，顯然它是空間是有限的，但是我們無法确定有多少寫入操作會同時發生，是以檔案系統一般會采用circular log去解決這個問題，即記錄journal區域中每一個log entry的生成時間，當log entry不夠時，則盡快Checkpoint這個log entry，以騰出空間給新的寫入操作。是以journal區域需要一個journal super block去管理這些與log entry有關的中繼資料資訊，如下圖所示。這裡每一個Tx1到Tx5表示都表示一個log entry。是以出了前面介紹的Journal write，Journal Commit，Checkpoint操作以外，我們還多了一個free操作以釋放log entry。
Data Journaling的開銷: 經過前面的分析，我們已經得到一個完整的data journaling方案，但是這存在一個問題: 每一個data block需要寫入磁盤兩次 (即double write問題)，使用最開始的例子即是
Db
要先通過Journal write寫入到Journal區域，再通過Checkpoint寫入到磁盤，會産生大量的開銷。而且一般而言，崩潰是一個比較少出現的場景，為了嚴格的一緻性去使用data journaling也不是非常值得的。
Metadata Journaling
回顧一開始對崩潰的場景的分析，如果inode和bitmap的寫入磁盤了就可以實作metadata consistent，這可以實作檔案系統的一緻性。一般而言，file data的寫入量會遠遠比metadata要大(如，寫入100個data block，可能隻需要更新一個inode block和一個bitmap block)。是以為了解決double write問題，檔案系統可以隻針對metadata做journal。以確定metadata consistent，如下圖所示，
Db
沒有寫入到log當中：
然而，如果在事務完成前之後，
Db
的磁盤寫入還沒完成就發生崩潰，那麼inode會指向一個不确定資料的data block，因為這個事務已經完成了，檔案系統重新開機的時候會replay這個事務。這種情況下，metadata journaling雖然確定了檔案系統的一緻性，但是無法確定檔案資料的一緻性。是以有一些檔案系統，如ext3/4，的journal機制會在指定的情況下，會確定data blocks (
Db
) 先寫入到磁盤，再送出metadata journal。是以我們可以将journaling再進一步分解為5個操作:
- data write：寫入資料到磁盤的對應位置，等待它的完成 (也可以不等，看設定的模式)。
- Journal metadata write：将
TxB
- Journal Commit：寫入
TxE
- Checkpoint metadata：将事務中的metadata的操作相關資料，分别各自回寫到各自的磁盤位置中。
- free：釋放journal區域的log entry。
在ext3/ext4中，這對應三種日志模式:
Journal Mode: 操作的metadata和file data都會寫入到日志中然後送出，這是最慢的。
Ordered Mode: 隻有metadata操作會寫入到日志中，但是確定資料在日志送出前寫入到磁盤中
Writeback Mode: 隻有metadata操作會寫入到日志中，且不確定資料在日志送出前寫入。
Log-structured File System 日志結構檔案系統
日志結構檔案系統(Log-structured File System，或者說LFS) 是一類執行異地更新(outplace-update)政策的檔案系統。無論是順序寫還是随機寫，LFS都會将資料順序地寫入到新的data block中，然後再将舊的data block無效掉。這種政策可以将随機寫轉換為順序寫，以優化檔案系統的寫入性能。
我們繼續使用前面的簡單檔案系統作為例子，但是我們目前考慮這個檔案系統的寫不是就地更新的，而是異地更新。例如，一開始
Db
寫入到磁盤data blocks區域位址是5的位置，那麼下次使用者要更新
Db
這個資料時，它不會重新寫到5這個位置，而是按順序地寫入到6這個位置。如果不斷更新，那麼就會将新更新的資料寫入到7，8，9，… ，等位置。在LFS中，我們稱為将目前寫入磁盤的位置稱為log (注意這裡的含義和JFS是有不同的)，由于資料是不斷順序地寫入到磁盤，而且是結構化的，是以也稱為log-structured檔案系統。
接下來我們考慮LFS的一緻性因素。它與JFS類似，也有bitmaps，inode block，data block，除此以外還有checkpoint區域 (類似于JFS的journal區域)用于確定檔案系統的一緻性。LFS的checkpoint的含義和JFS不同，是以也需要注意區分。使用F2FS檔案系統作為例子，可以參考這裡。