至此我們看到，文件系統管理一組數據結構以實現預期的抽象：文件、目錄，以及所有其他元數據，它們支持我們期望從文件系統獲得的基本抽象。與大多數數據結構不同（例如，正在運行的程序在内存中的數據結構），文件系統數據結構必須持久（persist），即它們必須長期存在，存儲在斷電也能保留數據的設備上（例如硬盤或基于閃存的SSD）。

文件系統面臨的一個主要挑戰在于，如何在出現斷電（power loss）或系統崩潰（system crash）的情況下，更新持久數據結構。具體來說，如果在更新磁盤結構的過程中，有人絆到電源線并且機器斷電，會發生什麼？或者操作系統遇到錯誤并崩潰？由于斷電和崩潰，更新持久性數據結構可能非常棘手，并導緻了文件系統實現中一個有趣的新問題，稱為崩潰一緻性問題（crash-consistency problem）。

這個問題很容易理解。想象一下，為了完成特定操作，你必須更新兩個磁盤上的結構A和B。由于磁盤一次隻為一個請求提供服務，因此其中一個請求将首先到達磁盤（A或B）。如果在一次寫入完成後系統崩潰或斷電，則磁盤上的結構将處于不一緻（inconsistent）的狀态。因此，我們遇到了所有文件系統需要解決的問題：

關鍵問題：考慮到崩潰，如何更新磁盤

查看圖中的結構，可以看到分配了一個inode（inode号為2），它在inode位圖中标記，單個分配的數據塊（數據塊4）也在數據中标記位圖。inode表示為I [v1]，因為它是此inode的第一個版本。它将很快更新（由于上述工作負載）。

再來看看這個簡化的inode。在I[v1]中，我們看到：

owner : remzi permissions : read-write size : 1 pointer : 4 pointer : null pointer : null pointer : null

在這個簡化的inode中，文件的大小為1（它有一個塊位于其中），第一個直接指針指向塊4（文件的第一個數據塊，Da），并且所有其他3個直接指針都被設置為null（表示它們未被使用）。當然，真正的inode有更多的字段。更多相關信息，請參閱前面的章節。

向文件追加内容時，要向它添加一個新數據塊，因此必須更新3個磁盤上的結構：inode（必須指向新塊，并且由于追加而具有更大的大小），新數據塊Db和新版本的數據位圖（稱之為B[v2]）表示新數據塊已被分配。

因此，在系統的内存中，有3個塊必須寫入磁盤。更新的inode（inode版本2，或簡稱為I [v2]）現在看起來像這樣：

owner : remzi permissions : read-write size : 2 pointer : 4 pointer : 5 pointer : null pointer : null

更新的數據位圖（B[v2]）現在看起來像這樣：00001100。最後，有數據塊（Db），它隻是用戶放入文件的内容。

我們希望文件系統的最終磁盤映像如下所示：

要實現這種轉變，文件系統必須對磁盤執行3次單獨寫入，分别針對inode（I[v2]），位圖（B[v2]）和數據塊（Db）。請注意，當用戶發出write()系統調用時，這些寫操作通常不會立即發生。髒的inode、位圖和新數據先在内存（頁面緩存，page cache，或緩沖區緩存，buffer cache）中存在一段時間。然後，當文件系統最終決定将它們寫入磁盤時（比如說5s或30s），文件系統将向磁盤發出必要的寫入請求。遺憾的是，可能會發生崩潰，從而幹擾磁盤的這些更新。特别是，如果這些寫入中的一個或兩個完成後發生崩潰，而不是全部 3個，則文件系統可能處于有趣的狀态。

崩潰場景

為了更好地理解這個問題，讓我們看一些崩潰情景示例。想象一下，隻有一次寫入成功。因此有以下3種可能的結果。

• 隻将數據塊（Db）寫入磁盤。在這種情況下，數據在磁盤上，但是沒有指向它的inode，也沒有表示塊已分配的位圖。因此，就好像寫入從未發生過一樣。從文件系統崩潰一緻性的角度來看，這種情況根本不是問題[1]。
• 隻有更新的inode（I[v2]）寫入了磁盤。在這種情況下，inode指向磁盤地址（5），其中Db即将寫入，但Db尚未寫入。因此，如果我們信任該指針，我們将從磁盤讀取垃圾數據（磁盤地址5的舊内容）。

此外，遇到了一個新問題，我們将它稱為文件系統不一緻（file-system inconsistency）。磁盤上的位圖告訴我們數據塊5尚未分配，但是inode說它已經分配了。文件系統數據結構中的這種不同意見，是文件系統的數據結構不一緻。要使用文件系統，我們必須以某種方式解決這個問題。

• 隻有更新後的位圖（B [v2]）寫入了磁盤。在這種情況下，位圖指示已分配塊5，但沒有指向它的inode。因此文件系統再次不一緻。如果不解決，這種寫入将導緻空間洩露（space leak），因為文件系統永遠不會使用塊5。

在這個向磁盤寫入3次的嘗試中，還有3種崩潰場景。在這些情況下，兩次寫入成功，最後一次失敗。

• inode（I[v2]）和位圖（B[v2]）寫入了磁盤，但沒有寫入數據（Db）。在這種情況下，文件系統元數據是完全一緻的：inode有一個指向塊5的指針，位圖指示5正在使用，因此從文件系統的元數據的角度來看，一切看起來都很正常。但是有一個問題：5中又是垃圾。
• 寫入了inode（I[v2]）和數據塊（Db），但沒有寫入位圖（B[v2]）。在這種情況下，inode指向了磁盤上的正确數據，但同樣在inode和位圖（B1）的舊版本之間存在不一緻。因此，我們在使用文件系統之前，又需要解決問題。
• 寫入了位圖（B[v2]）和數據塊（Db），但沒有寫入inode（I[v2]）。在這種情況下，inode和數據位圖之間再次存在不一緻。但是，即使寫入塊并且位圖指示其使用，我們也不知道它屬于哪個文件，因為沒有inode指向該塊。

崩潰一緻性問題

希望從這些崩潰場景中，你可以看到由于崩潰而導緻磁盤文件系統映像可能出現的許多問題：在文件系統數據結構中可能存在不一緻性。可能有空間洩露，可能将垃圾數據返回給用戶，等等。理想的做法是将文件系統從一個一緻狀态（在文件被追加之前），原子地（atomically）移動到另一個狀态（在inode、位圖和新數據塊被寫入磁盤之後）。遺憾的是，做到這一點不容易，因為磁盤一次隻提交一次寫入，而這些更新之間可能會發生崩潰或斷電。我們将這個一般問題稱為崩潰一緻性問題（crash-consistency problem，也可以稱為一緻性更新問題，consistent-update problem）。

2　解決方案1：文件系統檢查程序

早期的文件系統采用了一種簡單的方法來處理崩潰一緻性。基本上，它們決定讓不一緻的事情發生，然後再修複它們（重啟時）。這種偷懶方法的典型例子可以在一個工具中找到：fsck[2]。fsck是一個UNIX工具，用于查找這些不一緻并修複它們[M86]。在不同的系統上，存在檢查和修複磁盤分區的類似工具。請注意，這種方法無法解決所有問題。例如，考慮上面的情況，文件系統看起來是一緻的，但是inode指向垃圾數據。唯一真正的目标，是确保文件系統元數據内部一緻。

工具fsck在許多階段運行，如McKusick和Kowalski的論文[MK96]所述。它在文件系統挂載并可用之前運行（fsck假定在運行時沒有其他文件系統活動正在進行）。一旦完成，磁盤上的文件系統應該是一緻的，因此可以讓用戶訪問。

以下是fsck的基本總結。

• 超級塊：fsck首先檢查超級塊是否合理，主要是進行健全性檢查，例如确保文件系統大小大于分配的塊數。通常，這些健全性檢查的目的是找到一個可疑的（沖突的）超級塊。在這種情況下，系統（或管理員）可以決定使用超級塊的備用副本。
• 空閑塊：接下來，fsck掃描inode、間接塊、雙重間接塊等，以了解當前在文件系統中分配的塊。它利用這些知識生成正确版本的分配位圖。因此，如果位圖和inode之間存在任何不一緻，則通過信任inode内的信息來解決它。對所有inode執行相同類型的檢查，确保所有看起來像在用的inode，都在inode位圖中有标記。
• inode狀态：檢查每個inode是否存在損壞或其他問題。例如，fsck确保每個分配的inode具有有效的類型字段（即常規文件、目錄、符号鍊接等）。如果inode字段存在問題，不易修複，則inode被認為是可疑的，并被fsck清除，inode位圖相應地更新。
• inode鍊接：fsck還會驗證每個已分配的inode的鍊接數。你可能還記得，鍊接計數表示包含此特定文件的引用（即鍊接）的不同目錄的數量。為了驗證鍊接計數，fsck從根目錄開始掃描整個目錄樹，并為文件系統中的每個文件和目錄構建自己的鍊接計數。如果新計算的計數與inode中找到的計數不匹配，則必須采取糾正措施，通常是修複inode中的計數。如果發現已分配的inode但沒有目錄引用它，則會将其移動到lost found目錄。
• 重複：fsck還檢查重複指針，即兩個不同的inode引用同一個塊的情況。如果一個inode明顯不好，可能會被清除。或者，可以複制指向的塊，從而根據需要為每個inode提供其自己的副本。
• 壞塊：在掃描所有指針列表時，還會檢查壞塊指針。如果指針顯然指向超出其有效範圍的某個指針，則該指針被認為是“壞的”，例如，它的地址指向大于分區大小的塊。在這種情況下，fsck不能做任何太聰明的事情。它隻是從inode或間接塊中删除（清除）該指針。
• 目錄檢查：fsck不了解用戶文件的内容。但是，目錄包含由文件系統本身創建的特定格式的信息。因此，fsck對每個目錄的内容執行額外的完整性檢查，确保“.”和“..”是前面的條目，目錄條目中引用的每個inode都已分配，并确保整個層次結構中沒有目錄的引用超過一次。

如你所見，構建有效工作的fsck需要複雜的文件系統知識。确保這樣的代碼在所有情況下都能正常工作可能具有挑戰性[G 08]。然而，fsck（和類似的方法）有一個更大的、也許更根本的問題：它們太慢了。對于非常大的磁盤卷，掃描整個磁盤，以查找所有已分配的塊并讀取整個目錄樹，可能需要幾分鐘或幾小時。随着磁盤容量的增長和RAID的普及，fsck的性能變得令人望而卻步（盡管最近取得了進展[M 13]）。

在更高的層面上，fsck的基本前提似乎有點不合理。考慮上面的示例，其中隻有3個塊寫入磁盤。掃描整個磁盤，僅修複更新 3 個塊期間出現的問題，這是非常昂貴的。這種情況類似于将你的鑰匙放在卧室的地闆上，然後從地下室開始，搜遍每個房間，執行“搜索整個房子找鑰匙”的恢複算法。它有效，但很浪費。因此，随着磁盤（和RAID）的增長，研究人員和從業者開始尋找其他解決方案。

3　解決方案2：日志（或預寫日志）

對于一緻更新問題，最流行的解決方案可能是從數據庫管理系統的世界中借鑒的一個想法。這種名為預寫日志（write-ahead logging）的想法，是為了解決這類問題而發明的。在文件系統中，出于曆史原因，我們通常将預寫日志稱為日志（journaling）。第一個實現它的文件系統是Cedar [H87]，但許多現代文件系統都使用這個想法，包括Linux ext3和ext4、reiserfs、IBM的JFS、SGI的XFS和Windows NTFS。

基本思路如下。更新磁盤時，在覆寫結構之前，首先寫下一點小注記（在磁盤上的其他地方，在一個衆所周知的位置），描述你将要做的事情。寫下這個注記就是“預寫”部分，我們把它寫入一個結構，并組織成“日志”。因此，就有了預寫日志。

通過将注釋寫入磁盤，可以保證在更新（覆寫）正在更新的結構期間發生崩潰時，能夠返回并查看你所做的注記，然後重試。因此，你會在崩潰後準确知道要修複的内容（以及如何修複它），而不必掃描整個磁盤。因此，通過設計，日志功能在更新期間增加了一些工作量，從而大大減少了恢複期間所需的工作量。

我們現在将描述Linux ext3（一種流行的日志文件系統）如何将日志記錄到文件系統中。大多數磁盤上的結構與Linux ext2相同，例如，磁盤被分成塊組，每個塊組都有一個inode和數據位圖以及inode和數據塊。新的關鍵結構是日志本身，它占用分區内或其他設備上的少量空間。因此，ext2文件系統（沒有日志）看起來像這樣：

假設日志放在同一個文件系統映像中（雖然有時将它放在單獨的設備上，或作為文件系統中的文件），帶有日志的ext3文件系統如下所示：

真正的區别隻是日志的存在，當然，還有它的使用方式。

數據日志

看一個簡單的例子，來理解數據日志（data journaling）的工作原理。數據日志作為Linux ext3文件系統的一種模式提供，本讨論的大部分内容都來自于此。

假設再次進行标準的更新，我們再次希望将inode（I[v2]）、位圖（B[v2]）和數據塊（Db）寫入磁盤。在将它們寫入最終磁盤位置之前，現在先将它們寫入日志。這就是日志中的樣子：

你可以看到，這裡寫了5個塊。事務開始（TxB）告訴我們有關此更新的信息，包括對文件系統即将進行的更新的相關信息（例如，塊I[v2]、B[v2]和Db的最終地址），以及某種事務标識符（transaction identifier，TID）。中間的3個塊隻包含塊本身的确切内容，這被稱為物理日志（physical logging），因為我們将更新的确切物理内容放在日志中（另一種想法，邏輯日志（logical logging），在日志中放置更緊湊的更新邏輯表示，例如，“這次更新希望将數據塊Db追加到文件X”，這有點複雜，但可以節省日志中的空間，并可能提高性能）。最後一個塊（TxE）是該事務結束的标記，也會包含TID。

一旦這個事務安全地存在于磁盤上，我們就可以覆寫文件系統中的舊結構了。這個過程稱為加檢查點（checkpointing）。因此，為了對文件系統加檢查點（checkpoint，即讓它與日志中即将進行的更新一緻），我們将I[v2]、B[v2]和Db寫入其磁盤位置，如上所示。如果這些寫入成功完成，我們已成功地為文件系統加上了檢查點，基本上完成了。因此，我們的初始操作順序如下。

1．日志寫入：将事務（包括事務開始塊，所有即将寫入的數據和元數據更新以及事務結束塊）寫入日志，等待這些寫入完成。

2．加檢查點：将待處理的元數據和數據更新寫入文件系統中的最終位置。

在我們的例子中，先将TxB、I[v2]、B[v2]、Db和TxE寫入日志。這些寫入完成後，我們将加檢查點，将I[v2]、B[v2]和Db寫入磁盤上的最終位置，完成更新。

在寫入日志期間發生崩潰時，事情變得有點棘手。在這裡，我們試圖将事務中的這些塊（即TxB、I[v2]、B[v2]、Db、TxE）寫入磁盤。一種簡單的方法是一次發出一個，等待每個完成，然後發出下一個。但是，這很慢。理想情況下，我們希望一次發出所有 5 個塊寫入，因為這會将 5 個寫入轉換為單個順序寫入，因此更快。然而，由于以下原因，這是不安全的：給定如此大的寫入，磁盤内部可以執行調度并以任何順序完成大批寫入的小塊。因此，磁盤内部可以（1）寫入TxB、I[v2]、B[v2]和TxE，然後才寫入Db。遺憾的是，如果磁盤在（1）和（2）之間斷電，那麼磁盤上會變成：

補充：強制寫入磁盤

為了在兩次磁盤寫入之間強制執行順序，現代文件系統必須采取一些額外的預防措施。在過去，強制在兩個寫入A和B之間進行順序很簡單：隻需向磁盤發出A寫入，等待磁盤在寫入完成時中斷OS，然後發出寫入B。

由于磁盤中寫入緩存的使用增加，事情變得有點複雜了。啟用寫入緩沖後（有時稱為立即報告，immediate reporting），如果磁盤已經放入磁盤的内存緩存中、但尚未到達磁盤，磁盤就會通知操作系統寫入完成。如果操作系統随後發出後續寫入，則無法保證它在先前寫入之後到達磁盤。因此，不再保證寫入之間的順序。一種解決方案是禁用寫緩沖。然而，更現代的系統采取額外的預防措施，發出明确的寫入屏障（write barrier）。這樣的屏障，當它完成時，能确保在屏障之前發出的所有寫入，先于在屏障之後發出的所有寫入到達磁盤。

所有這些機制都需要對磁盤的正确操作有很大的信任。遺憾的是，最近的研究表明，為了提供“性能更高”的磁盤，一些磁盤制造商顯然忽略了寫屏障請求，從而使磁盤看起來運行速度更快，但存在操作錯誤的風險[C 13, R 11]。正如Kahan所說，快速幾乎總是打敗慢速，即使快速是錯的。

為什麼這是個問題？好吧，事務看起來像一個有效的事務（它有一個匹配序列号的開頭和結尾）。此外，文件系統無法查看第四個塊并知道它是錯誤的。畢竟，它是任意的用戶數據。因此，如果系統現在重新啟動并運行恢複，它将重放此事務，并無知地将垃圾塊“??”的内容複制到Db應該存在的位置。這對文件中的任意用戶數據不利。如果它發生在文件系統的關鍵部分上，例如超級塊，可能會導緻文件系統無法挂裝，那就更糟了。

補充：優化日志寫入

你可能已經注意到，寫入日志的效率特别低。也就是說，文件系統首先必須寫出事務開始塊和事務的内容。隻有在這些寫入完成後，文件系統才能将事務結束塊發送到磁盤。如果你考慮磁盤的工作方式，性能影響很明顯：通常會産生額外的旋轉（請考慮原因）。

我們以前的一個研究生Vijayan Prabhakaran，用一個簡單的想法解決了這個問題[P 05]。将事務寫入日志時，在開始和結束塊中包含日志内容的校驗和。這樣做可以使文件系統立即寫入整個事務，而不會産生等待。如果在恢複期間，文件系統發現計算的校驗和與事務中存儲的校驗和不匹配，則可以斷定在寫入事務期間發生了崩潰，從而丢棄了文件系統更新。因此，通過寫入協議和恢複系統中的小調整，文件系統可以實現更快的通用情況性能。最重要的是，系統更可靠了，因為來自日志的任何讀取現在都受到校驗和的保護。

這個簡單的修複很吸引人，足以引起Linux文件系統開發人員的注意。他們後來将它合并到下一代Linux文件系統中，稱為Linux ext4（你猜對了！）。它現在可以在全球數百萬台機器上運行，包括Android手持平台。因此，每次在許多基于Linux的系統上寫入磁盤時，威斯康星大學開發的一些代碼都會使你的系統更快、更可靠。

為避免該問題，文件系統分兩步發出事務寫入。首先，它将除TxE塊之外的所有塊寫入日志，同時發出這些寫入。當這些寫入完成時，日志将看起來像這樣（假設又是文件追加的工作負載）：

當這些寫入完成時，文件系統會發出TxE塊的寫入，從而使日志處于最終的安全狀态：

此過程的一個重要方面是磁盤提供的原子性保證。事實證明，磁盤保證任何512字節寫入都會發生或不發生（永遠不會半寫）。因此，為了确保TxE的寫入是原子的，應該使它成為一個512字節的塊。因此，我們當前更新文件系統的協議如下，3個階段中的每一個都标上了名稱。

1．日志寫入：将事務的内容（包括TxB、元數據和數據）寫入日志，等待這些寫入完成。

2．日志提交：将事務提交塊（包括TxE）寫入日志，等待寫完成，事務被認為已提交（committed）。

3．加檢查點：将更新内容（元數據和數據）寫入其最終的磁盤位置。

恢複

現在來了解文件系統如何利用日志内容從崩潰中恢複（recover）。在這個更新序列期間，任何時候都可能發生崩潰。如果崩潰發生在事務被安全地寫入日志之前（在上面的步驟2完成之前），那麼我們的工作很簡單：簡單地跳過待執行的更新。如果在事務已提交到日志之後但在加檢查點完成之前發生崩潰，則文件系統可以按如下方式恢複（recover）更新。系統引導時，文件系統恢複過程将掃描日志，并查找已提交到磁盤的事務。然後，這些事務被重放（replayed，按順序），文件系統再次嘗試将事務中的塊寫入它們最終的磁盤位置。這種形式的日志是最簡單的形式之一，稱為重做日志（redo logging）。通過在日志中恢複已提交的事務，文件系統确保磁盤上的結構是一緻的，因此可以繼續工作，挂載文件系統并為新請求做好準備。

請注意，即使在某些更新寫入塊的最終位置之後，在加檢查點期間的任何時刻發生崩潰，都沒問題。在最壞的情況下，其中一些更新隻是在恢複期間再次執行。因為恢複是一種罕見的操作（僅在系統意外崩潰之後發生），所以幾次冗餘寫入無須擔心[3]。

批處理日志更新

你可能已經注意到，基本協議可能會增加大量額外的磁盤流量。例如，假設我們在同一目錄中連續創建兩個文件，稱為file1和file2。要創建一個文件，必須更新許多磁盤上的結構，至少包括：inode位圖（分配新的inode），新創建的文件inode，包含新文件目錄條目的父目錄的數據塊，以及父目錄的inode（現在有一個新的修改時間）。通過日志，我們将所有這些信息邏輯地提交給我們的兩個文件創建的日志。因為文件在同一個目錄中，我們假設在同一個inode塊中都有inode，這意味着如果不小心，我們最終會一遍又一遍地寫入這些相同的塊。

為了解決這個問題，一些文件系統不會一次一個地向磁盤提交每個更新（例如，Linux ext3）。與此不同，可以将所有更新緩沖到全局事務中。在上面的示例中，當創建兩個文件時，文件系統隻将内存中的inode位圖、文件的inode、目錄數據和目錄inode标記為髒，并将它們添加到塊列表中，形成當前的事務。當最後應該将這些塊寫入磁盤時（例如，在超時5s之後），會提交包含上述所有更新的單個全局事務。因此，通過緩沖更新，文件系統在許多情況下可以避免對磁盤的過多的寫入流量。

本文截選自《操作系統導論》

操作系統導論

作者：[美] 雷姆茲·H.阿帕希杜塞爾（ Remzi H. Arpaci-Dusseau）， [美]安德莉亞·C.阿帕希杜塞爾（Andrea C. Arpaci-Dusseau）

譯者：王海鵬

• 美國知名操作系統教材
• 緊緊圍繞操作系統的三大主題元素:虛拟化 并發和持久性進行講解
• 豆瓣原版評分９.７

本書圍繞虛拟化、并發和持久性這三個主要概念展開，介紹了所有現代系統的主要組件（包括調度、虛拟内存管理、磁盤和I/O子系統、文件系統）。全書共50章，分為3個部分，分别講述虛拟化、并發和持久性的相關内容。作者以對話形式引入所介紹的主題概念，行文诙諧幽默卻又鞭辟入裡，力求幫助讀者理解操作系統中虛拟化、并發和持久性的原理。

本書内容全面，并給出了真實可運行的代碼（而非僞代碼），還提供了相應的練習，很适合高等院校相關專業的教師開展教學和高校學生進行自學。

本書具有以下特色：

● 主題突出，緊緊圍繞操作系統的三大主題元素——虛拟化、并發和持久性。

● 以對話的方式引入背景，提出問題，進而闡釋原理，啟發動手實踐。

● 包含衆多“補充”和“提示”，拓展讀者知識面，增加趣味性。

● 使用真實代碼而不是僞代碼，讓讀者更加深入透徹地了解操作系統。

● 提供作業、模拟和項目等衆多學習方式，鼓勵讀者動手實踐。

● 為教師提供教學輔助資源。

,