要實現上面的操作，文件系統必須對磁碟執行三個單獨的寫操作，一個是inode(i[v2])，一個是點陣圖(B[v2])，另一個是數據塊(DB)。注意，當用戶發出write()系統調用時，這些寫入通常不會立即發生；相反，髒的inode、點陣圖和新數據將首先在主內存中停留一段時間；然後，當文件系統最終決定將它們寫入磁碟時(例如5秒或30秒後)，文件系統將向磁碟發出必要的寫入請求。不幸的是在這個時間段內可能會發生崩潰。特別是，如果崩潰發生在這幾個寫操作之間,那麼文件系統可能會處於一種奇怪的狀態。

為了更好地理解這個問題，讓我們看看一些崩潰的具體場景。假設只有一次寫入成功；因此有三種可能的結果，我們在這裡列出：

1.只將數據塊(DB)寫入磁碟。在這種情況下，數據在磁碟上，但是沒有inode指向它，也沒有顯示塊被分配的點陣圖信息。因此，看起來像是從未發生過寫入一樣。

2.只將inode(i[v2])寫入磁碟。在這種情況下，inode指向即將寫入DB的磁碟地址(5)，但DB尚未寫入其中。因此，如果我們信任該指針，我們將從磁碟讀取到的是垃圾數據。此外，還有一個新的問題，稱之為文件系統的一致性問題.磁碟上的點陣圖告訴我們數據塊5沒有被分配，但是inode說它已經分配了。點陣圖和inode之間的分歧導致文件系統的數據結構不一致；因此我們必須以某種方式解決這個問題(下面將詳細介紹)。

3.只將更新後的點陣圖(B[v2])寫入磁碟。在這種情況下，點陣圖指示塊5已經被分配，但沒有指向它的inode。因此，文件系統再次不一致；如果未解決，第5塊永遠不會被文件系統使用。

在試圖將三個塊寫入磁碟的嘗試中，還有另外三種崩潰可能。在這些情況下，會有2個寫入成功：

1.inode(i[v2])和點陣圖(B[v2])被寫入磁碟，數據並沒有寫入。在這種情況下，文件系統元數據是完全一致的：inode有一個指向塊5的指針，點陣圖表示5在使用中，因此從文件系統元數據的角度來看，一切看起來都正常。但是有一個問題：5裡面又是垃圾數據。

2.inode(i[v2])和數據塊(DB)寫入了，但沒有寫入點陣圖(B[v2])。在這種情況下，我們有指向磁碟上正確數據的inode，但是inode和點陣圖(B1)的舊版本之間有不一致之處。因此，在使用文件系統之前，我們需要解決這個問題。

3.點陣圖(B[v2])和數據塊(DB)寫入，inode(i[v2])沒有寫入。在這種情況下，我們再次在inode和數據點陣圖之間出現了不一致。所以即使塊是寫入的，並且點陣圖顯示了它的使用情況，我們也不知道它屬於哪個文件，因為沒有inode指向該文件。

可以看到由於崩潰導致文件系統出現了許多可能發生的問題。理想情況下，我們要做的是將文件系統從一個一致的狀態原子地移動到另一個狀態。不幸的是，我們無法輕鬆地做到這一點，因為磁碟同一時間只能完成一次寫操作，並且在這些更新之間隨時可能會發生崩潰或斷電。

解決方案一：fsck

早期文件系統採取了簡單的方法來解決一致性問題。基本的策略是讓不一致的事情發生然後再修正他們（當重新啟動時）。這種方法的一個典型例子是執行FSCK2這個工具：。fsck是一個用於查找這種不一致並修復它們的UNIX工具。請注意，這種方法無法修復所有問題；例如，文件系統看起來一致，但inode指向垃圾數據。以下是fsck的基本概要：

1.超級塊(Superblock)：fsck首先檢查超級塊是否合理，主要進行健全性檢查，例如確保文件系統大小大於已分配的塊的數量。通常這些健全性檢查的目標是尋找有問題的超級塊；在這種情況下，系統（或管理員）可以決定使用超級塊的替代副本。

2.自由塊(Free blocks)：下一步，fsck掃描inode，間接塊，雙間接塊等。知道哪些塊已經被分配。使用這個數據生成正確版本的點陣圖；因此，如果點陣圖和inode之間存在任何不一致，將信任inodes內的信息。

3.inode狀態：檢查每個inode是否存在損壞或其他問題。例如，fsck確保每個已分配的inode有效類型欄位有分配（例如，常規文件、目錄、符號鏈接等).如果存在不容易確定的inode欄位的問題，inode被認為是可疑的，並被fsck清除；inode點陣圖相應地更新。

4.inode鏈接:fsck還驗證每個已分配inode的鏈接計數。鏈路計數表示指向該特定文件的引用數量。要驗證鏈路計數，fsck掃描整個目錄樹，從根目錄開始，並建立文件系統中每個文件和目錄的鏈接計數。如果新計算的計數和找到的計數之間不匹配，必須採取糾正措施，通常是修改inode中的引用計數值。如果發現了已分配的inode,但是沒有目錄引用它，它將被移動到lost+found的目錄。

5.重複：在掃描所有指針時，還會執行對錯誤塊指針的檢查。如果指針明顯地指向它的有效範圍之外的地方，那麼指針就被認為是「壞」的，例如，指針指向的地址大於分區大小的塊。在這種情況下，fsck不做任何太智能的事情；它只是從inode或間接塊中移除(清除)指針。

6.目錄檢查：fsck不了解用戶的文件內容；但是，目錄保存著由文件系統本身創建的特定格式的信息。因此，fsck對每個目錄的內容執行額外的完整性檢查，確保"."還有「..」是第一個條目，在目錄條目中引用的每個inode都被分配，並確保在整個層次結構中沒有任何目錄被鏈接到不止一次。

正如你所看到的，構建一個工作的fsck需要了解文件系統的複雜知識；確保這樣的代碼在所有情況下都能正確工作是很有挑戰性的。然而，fsck(和類似的方法)有一個更大、也許更根本的問題：它們太慢了。掃描整個磁碟以找到所有分配的塊，並讀取整個目錄樹可能需要許多分鐘甚至小時。fsck的性能隨著磁碟容量的增長和RAID的普及而變得令人望而卻步。在更高的層面上，fsck的基本前提似乎有點不合理。考慮上面的示例，其中只向磁碟寫入了三個塊；但是卻需要掃描整個磁碟來修復。這種情況類似於把你的鑰匙丟在你卧室的地板上，然後用一種搜索整棟房子的恢復演算法。因此，隨著磁碟(RAID)的增加，人們開始尋找其他解決方案。

解決方案二：日誌記錄型文件系統

對於一致性的問題，最流行的解決方案是從資料庫管理系統中學習的一個想法。在文件系統中，由於歷史原因，我們通常稱為journaling。第一個這樣做的文件系統是Cedar，許多現代文件系統都使用這種思想，包括Linux ext3和ext4、ReiserFS、IBM的JFS、SGI的XFS和WindowsNTFS。基本思想如下。

當更新磁碟時，在覆蓋數據結構之前，首先寫日誌(在磁碟上的某個地方)，先將日誌寫入磁碟，可以確保如果正在更新數據的期間發生崩潰，可以回過頭來查看所做的日誌，然後再試一次；因此，你將知道在崩潰後修復什麼(以及如何修復)，而不必掃描整個磁碟。我們現在以Linux ext3為例子，來看看如何將日誌合併到文件系統中。ext3大多數磁碟上的結構與Linux ext2相同，例如，磁碟被劃分為組，每個組包含一個inode點陣圖、數據點陣圖、inode和數據塊。新的核心結構是日誌本身。ext 2文件系統(沒有日誌記錄)如下所示：

假設日誌被放置在同一個文件系統映像中(雖然有時被放置在單獨的設備上，或者作為文件系統中的文件)，帶有日誌的ext3文件系統如下所示：

真正的區別只是日誌記錄部分的存在，當然還包括它是如何使用的。

讓我們看一個簡單的例子來了解日誌是如何工作的。假設我們希望再次將inode(i[v2])、點陣圖(B[v2])和數據塊(DB)寫入磁碟。在將它們寫入最終磁碟位置之前，我們首先將它們寫入日誌。這將是日誌中的內容：

你可以看到我們在這裡寫了五個塊。事務開始(TxB)，需要更新到文件系統的內容(例如，塊I[v2]、B[v2]和DB)，以及事務標識符(transaction identifier，TID)。中間三個塊包含了本次更新的實際內容；這種日誌被稱為物理日誌，因為我們將更新的確切物理內容放在日誌中。(另一種方式是邏輯日誌，是在日誌中放置更緊湊的邏輯表示，例如，「此更新希望將數據塊DB附加到文件X」，這有點複雜，但可以節省日誌中的空間，並可能提高性能)。最終塊(TxE)是此事務結束的標記，並且還將包含TID。一旦事務安全地更新在磁碟上，我們就可以覆蓋文件系統中的舊數據，這個過程稱為檢查點（checkpointing）。因此，我們操作的順序是：

1.日誌寫入：將事務寫入日誌，包括一個transaction-BEGIN塊、所有待寫入的數據和元數據以及一個Transaction-end塊；然後等待這些寫入完成。

2.檢查點： 將掛起的元數據和數據寫入文件系統中它們的最終位置。

在我們的示例中，我們首先將TxB、I[v2]、B[v2]、DB和TxE寫入日誌。當這些寫入完成時，我們將通過檢查點來完成對I[v2]、B[v2]和DB的寫入。但是當崩潰發生在寫日記的時候，事情又會變得複雜。比如為了加快寫這些日誌的速度，會將這5塊的信息作為一個i/o請求去進行操作，至於寫的順序那就要看具體的調度實現了，有可能出現先寫TxB、I[v2]、B[v2]和TxE，然後寫DB的情況，如果在這2個步驟之間斷電了，那麼就會出現下面這種情況的日誌。當重啟機器恢復日誌的時候，讀到的數據就會是垃圾數據了。

這種問題解決方法是分兩步發出事務寫入的請求。首先，將除TxE塊之外的所有塊寫入日誌，並且同時發出這些寫入。 當這些寫入完成後，日誌將類似於這樣：

當這些寫入完成後，文件系統發出TxE塊的寫入，從而使日誌處於最後的安全狀態：

此過程的一個重要支撐是磁碟提供的原子性保證。磁碟保證任何512位元組的寫入都是原子性的。因此，為了確保TxE的寫入是原子的，應該將它變成一個512位元組的塊。到這裡，當前更新文件系統的協議分為如下三個階段：

1.日誌寫入：將事務的內容(包括TxB、元數據和數據)寫入日誌；等待這些寫入完成。

2.日誌提交：將事務提交塊(包含TxE)寫入日誌；等待寫入完成

3.檢查點： 將更新的內容(元數據和數據)寫入它們對應的最終磁碟位置。

崩潰恢復

現在讓我們了解文件系統如何使用日誌的內容從崩潰中恢復。如果崩潰發生在事務安全地寫入日誌之前(即在上面的步驟2完成之前)，那麼我們的工作很簡單：不對數據進行更新。

如果崩潰發生在事務提交到日誌之後，但在檢查點完成之前，文件系統可以恢復更新。當系統啟動時，文件系統恢復程序將掃描日誌並查找已提交到磁碟的事務；文件系統再次嘗試將事務中的塊寫入其最終的磁碟位置。我們現在這種形式的日誌記錄是最簡單的形式之一，稱為redo logging。通過恢復日誌中提交的事務，文件系統確保了磁碟上的結構是一致的。

你可能已經注意到，基本協議可能會增加許多額外的磁碟通信量。例如，假設我們在同一目錄中創建了兩個文件，名為file 1和file 2。要創建一個文件，必須更新多個磁碟上的結構，最少包括：inode點陣圖，新創建的inode，包含新目錄條目的父目錄的數據塊，以及父目錄inode(需要更新修改時間)。這2個文件的創建動作，我們會寫2塊日誌信息。因為這些文件位於同一個目錄中，並且假設它們的inode信息甚至在同一個inode塊中，所以我們最終可能會多次訪問相同的塊。

為了解決這個問題，一些文件系統不是有了更新就向磁碟提交的(例如Linux ext3)；相反，可以將所有更新緩衝到一個全局事務中。在上面的示例中，當創建兩個文件時，文件系統只是將需要更新的數據添加到當前事務的塊列表中。當最終將這些塊寫入磁碟時(例如，5秒後)，將提交包含上述所有更新的單個全局事務。因此，在許多情況下，通過緩衝，文件系統可以避免過多地與磁碟通信。

上面的協議已經可以滿足我們最基本的要求了。但是，日誌只有有限的大小。如果我們不斷把事務添加進去（如本圖所示），日誌空間將很快填滿。

當日誌滿時會出現兩個問題。第一個比較簡單，但不太關鍵：日誌越大，恢復所用的時間就越長，因為恢復過程必須重新執行日誌中的所有事務(為了恢復)。第二個問題則嚴重得多：當日誌已滿(或接近滿)時，無法將更多事務提交到磁碟，會導致文件系統「不可用」。

為了解決這些問題，日誌文件系統將日誌空間視為循環的數據結構，反覆使用它；這就是為什麼日誌有時被稱為循環日誌的原因。要做到這一點，文件系統必須在檢查點之後的某個時間採取特定的操作。具體來說，一旦事務完成了檢查點，文件系統應該釋放它在日誌中佔用的空間，從而允許重用日誌空間。實現的方法有很多種；例如，可以在日誌超級塊中標記日誌中最古老和最新的非檢查點事務；這樣其他空間都是空閑的。下面是對應的描述：

在日誌超級塊中(不要與主文件系統超級塊混淆)，有足夠的信息知道哪些事務尚未被檢查，從而縮短了恢復時間，並允許循環地重用日誌。因此，我們的基本協議中又增加了一個步驟：

1.日誌寫入：將事務的內容(包含TxB和更新的內容)寫入日誌；等待這些寫入完成。

2.日誌提交：將事務提交塊(包含TxE)寫入日誌；等待寫入完成；事務現在已提交。

3.檢查點：將更新的內容寫入文件系統中的最終位置。

4.釋放：一段時間後，通過更新日誌超級塊來標記日誌中的事務。

我們現在有了最終的日誌記錄協議。但是仍然存在一個問題：我們需要將每個數據塊寫兩次到磁碟，這是一個巨大的消耗，特別是對於像系統崩潰這樣罕見的場景而這麼做。你能想出一種更高效的方法嗎？

元數據日誌

雖然現在恢復很快(掃描日誌然後重新執行幾個事務，而不是掃描整個磁碟)，但文件系統的常規操作將比我們希望的要慢。特別是，對於每一次磁碟寫入，我們要將所有的數據都先寫入日誌，從而使寫入流量加倍。此外，在寫入日誌和寫入主文件系統之間，存在一個代價高昂的查找，這也會帶來明顯的開銷。

由於將每個數據塊兩次寫入磁碟的成本高，人們嘗試了一些不同的事情，以加快性能。例如，在linux ex3中，日誌中不會寫入用戶數據，寫入的日誌信息如下：

那麼我們什麼時候寫入數據塊呢？

答案就是將數據塊先寫入。對於這種方式，我們現在的整體步驟變為了如下幾步：

1.數據寫入：將數據寫入最終位置；等待完成(等待是可選的；詳見下文)。

2.日誌元數據寫入：將BEGIN塊和元數據寫入日誌；等待寫入完成。

3.日誌提交：將事務提交塊(包含TxE)寫入日誌；等待寫入完成；完後後事務(包括數據)就表示已經提交了。

4.檢查點元數據：將元數據的內容寫入文件系統中的最終位置。

5.釋放：稍後，在日誌超級塊中標記事務。

對於步驟一，其實可以和步驟2一起寫入，因為我們最終是根據步驟三的完成情況來判斷這個事務的日誌數據是否完整，所以1，2同時進行是可以的。

在結束日誌記錄的討論之前，我們總結下討論過的協議，並給出了每個協議的執行時間表。圖42.1顯示了同時記錄數據和元數據時的協議，而圖42.2則顯示了只記錄元數據時的協議。在每個圖形中，時間向下增長，圖中的每一行顯示發出或可能完成寫入的邏輯時間。例如，圖42.1中，事務開始塊(TxB)的寫入和事務的內容可以在邏輯上同時發出，因此可以按任何順序完成；但是，在寫完之前，不能發出對事務結束塊(TxE)的寫入。水平虛線顯示必須遵守的順序。

元數據日誌記錄協議顯示了類似的時間線。請注意，數據和事務內容可以同時發起；但是，必須在事務結束TXE之前完成數據寫入。在實際系統中，完成時間由I/O系統決定，系統也可以重新排序寫入的順序以提高性能。

推薦閱讀：