系統(tǒng)可能在任何兩次寫入之間崩潰或斷電，崩潰后，如何更新磁盤

本文截選自《操作系統(tǒng)導(dǎo)論》第42章

崩潰一致性：FSCK和日志

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

文件系統(tǒng)面臨的一個主要挑戰(zhàn)在于，如何在出現(xiàn)斷電（power loss）或系統(tǒng)崩潰（system crash）的情況下，更新持久數(shù)據(jù)結(jié)構(gòu)。具體來說，如果在更新磁盤結(jié)構(gòu)的過程中，有人絆到電源線并且機器斷電，會發(fā)生什么？或者操作系統(tǒng)遇到錯誤并崩潰？由于斷電和崩潰，更新持久性數(shù)據(jù)結(jié)構(gòu)可能非常棘手，并導(dǎo)致了文件系統(tǒng)實現(xiàn)中一個有趣的新問題，稱為崩潰一致性問題（crash-consistency problem）。

這個問題很容易理解。想象一下，為了完成特定操作，你必須更新兩個磁盤上的結(jié)構(gòu)A和B。由于磁盤一次只為一個請求提供服務(wù)，因此其中一個請求將首先到達磁盤（A或B）。如果在一次寫入完成后系統(tǒng)崩潰或斷電，則磁盤上的結(jié)構(gòu)將處于不一致（inconsistent）的狀態(tài)。因此，我們遇到了所有文件系統(tǒng)需要解決的問題：

關(guān)鍵問題：考慮到崩潰，如何更新磁盤

系統(tǒng)可能在任何兩次寫入之間崩潰或斷電，因此磁盤上狀態(tài)可能僅部分地更新。崩潰后，系統(tǒng)啟動并希望再次掛載文件系統(tǒng)（以便訪問文件等）。鑒于崩潰可能發(fā)生在任意時間點，如何確保文件系統(tǒng)將磁盤上的映像保持在合理的狀態(tài)？

在本章中，我們將更詳細地探討這個問題，看看文件系統(tǒng)克服它的一些方法。我們將首先檢查較老的文件系統(tǒng)采用的方法，即fsck，文件系統(tǒng)檢查程序（file system checker）。然后，我們將注意力轉(zhuǎn)向另一種方法，稱為日志記錄（journaling，也稱為預(yù)寫日志，write-ahead logging），這種技術(shù)為每次寫入增加一點開銷，但可以更快地從崩潰或斷電中恢復(fù)。我們將討論日志的基本機制，包括Linux ext3 [T98，PAA05]（一個相對現(xiàn)代的日志文件系統(tǒng)）實現(xiàn)的幾種不同的日志。

1　一個詳細的例子

為了開始對日志的調(diào)查，先看一個例子。我們需要一種工作負載（workload），它以某種方式更新磁盤結(jié)構(gòu)。這里假設(shè)工作負載很簡單：將單個數(shù)據(jù)塊附加到原有文件。通過打開文件，調(diào)用lseek()將文件偏移量移動到文件末尾，然后在關(guān)閉文件之前，向文件發(fā)出單個4KB寫入來完成追加。

我們還假定磁盤上使用標(biāo)準(zhǔn)的簡單文件系統(tǒng)結(jié)構(gòu)，類似于之前看到的文件系統(tǒng)。這個小例子包括一個inode位圖（inode bitmap，只有8位，每個inode一個），一個數(shù)據(jù)位圖（data bitmap，也是8位，每個數(shù)據(jù)塊一個），inode（總共8個，編號為0到7，分布在4個塊上），以及數(shù)據(jù)塊（總共8個，編號為0～7）。以下是該文件系統(tǒng)的示意圖：

查看圖中的結(jié)構(gòu)，可以看到分配了一個inode（inode號為2），它在inode位圖中標(biāo)記，單個分配的數(shù)據(jù)塊（數(shù)據(jù)塊4）也在數(shù)據(jù)中標(biāo)記位圖。inode表示為I [v1]，因為它是此inode的第一個版本。它將很快更新（由于上述工作負載）。

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

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

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

因此，在系統(tǒng)的內(nèi)存中，有3個塊必須寫入磁盤。更新的inode（inode版本2，或簡稱為I [v2]）現(xiàn)在看起來像這樣：

更新的數(shù)據(jù)位圖（B[v2]）現(xiàn)在看起來像這樣：00001100。最后，有數(shù)據(jù)塊（Db），它只是用戶放入文件的內(nèi)容。

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

要實現(xiàn)這種轉(zhuǎn)變，文件系統(tǒng)必須對磁盤執(zhí)行3次單獨寫入，分別針對inode（I[v2]），位圖（B[v2]）和數(shù)據(jù)塊（Db）。請注意，當(dāng)用戶發(fā)出write()系統(tǒng)調(diào)用時，這些寫操作通常不會立即發(fā)生。臟的inode、位圖和新數(shù)據(jù)先在內(nèi)存（頁面緩存，page cache，或緩沖區(qū)緩存，buffer cache）中存在一段時間。然后，當(dāng)文件系統(tǒng)最終決定將它們寫入磁盤時（比如說5s或30s），文件系統(tǒng)將向磁盤發(fā)出必要的寫入請求。遺憾的是，可能會發(fā)生崩潰，從而干擾磁盤的這些更新。特別是，如果這些寫入中的一個或兩個完成后發(fā)生崩潰，而不是全部 3個，則文件系統(tǒng)可能處于有趣的狀態(tài)。

崩潰場景

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

只將數(shù)據(jù)塊（Db）寫入磁盤。在這種情況下，數(shù)據(jù)在磁盤上，但是沒有指向它的inode，也沒有表示塊已分配的位圖。因此，就好像寫入從未發(fā)生過一樣。從文件系統(tǒng)崩潰一致性的角度來看，這種情況根本不是問題[1]。

只有更新的inode（I[v2]）寫入了磁盤。在這種情況下，inode指向磁盤地址（5），其中Db即將寫入，但Db尚未寫入。因此，如果我們信任該指針，我們將從磁盤讀取垃圾數(shù)據(jù)（磁盤地址5的舊內(nèi)容）。

此外，遇到了一個新問題，我們將它稱為文件系統(tǒng)不一致（file-system inconsistency）。磁盤上的位圖告訴我們數(shù)據(jù)塊5尚未分配，但是inode說它已經(jīng)分配了。文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)中的這種不同意見，是文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)不一致。要使用文件系統(tǒng)，我們必須以某種方式解決這個問題。

只有更新后的位圖（B [v2]）寫入了磁盤。在這種情況下，位圖指示已分配塊5，但沒有指向它的inode。因此文件系統(tǒng)再次不一致。如果不解決，這種寫入將導(dǎo)致空間泄露（space leak），因為文件系統(tǒng)永遠不會使用塊5。

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

inode（I[v2]）和位圖（B[v2]）寫入了磁盤，但沒有寫入數(shù)據(jù)（Db）。在這種情況下，文件系統(tǒng)元數(shù)據(jù)是完全一致的：inode有一個指向塊5的指針，位圖指示5正在使用，因此從文件系統(tǒng)的元數(shù)據(jù)的角度來看，一切看起來都很正常。但是有一個問題：5中又是垃圾。

寫入了inode（I[v2]）和數(shù)據(jù)塊（Db），但沒有寫入位圖（B[v2]）。在這種情況下，inode指向了磁盤上的正確數(shù)據(jù)，但同樣在inode和位圖（B1）的舊版本之間存在不一致。因此，我們在使用文件系統(tǒng)之前，又需要解決問題。

寫入了位圖（B[v2]）和數(shù)據(jù)塊（Db），但沒有寫入inode（I[v2]）。在這種情況下，inode和數(shù)據(jù)位圖之間再次存在不一致。但是，即使寫入塊并且位圖指示其使用，我們也不知道它屬于哪個文件，因為沒有inode指向該塊。

崩潰一致性問題

希望從這些崩潰場景中，你可以看到由于崩潰而導(dǎo)致磁盤文件系統(tǒng)映像可能出現(xiàn)的許多問題：在文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)中可能存在不一致性。可能有空間泄露，可能將垃圾數(shù)據(jù)返回給用戶，等等。理想的做法是將文件系統(tǒng)從一個一致狀態(tài)（在文件被追加之前），原子地（atomically）移動到另一個狀態(tài)（在inode、位圖和新數(shù)據(jù)塊被寫入磁盤之后）。遺憾的是，做到這一點不容易，因為磁盤一次只提交一次寫入，而這些更新之間可能會發(fā)生崩潰或斷電。我們將這個一般問題稱為崩潰一致性問題（crash-consistency problem，也可以稱為一致性更新問題，consistent-update problem）。

2　解決方案1：文件系統(tǒng)檢查程序

早期的文件系統(tǒng)采用了一種簡單的方法來處理崩潰一致性。基本上，它們決定讓不一致的事情發(fā)生，然后再修復(fù)它們（重啟時）。這種偷懶方法的典型例子可以在一個工具中找到：fsck[2]。fsck是一個UNIX工具，用于查找這些不一致并修復(fù)它們[M86]。在不同的系統(tǒng)上，存在檢查和修復(fù)磁盤分區(qū)的類似工具。請注意，這種方法無法解決所有問題。例如，考慮上面的情況，文件系統(tǒng)看起來是一致的，但是inode指向垃圾數(shù)據(jù)。唯一真正的目標(biāo)，是確保文件系統(tǒng)元數(shù)據(jù)內(nèi)部一致。

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

以下是fsck的基本總結(jié)。

超級塊：fsck首先檢查超級塊是否合理，主要是進行健全性檢查，例如確保文件系統(tǒng)大小大于分配的塊數(shù)。通常，這些健全性檢查的目的是找到一個可疑的（沖突的）超級塊。在這種情況下，系統(tǒng)（或管理員）可以決定使用超級塊的備用副本。

空閑塊：接下來，fsck掃描inode、間接塊、雙重間接塊等，以了解當(dāng)前在文件系統(tǒng)中分配的塊。它利用這些知識生成正確版本的分配位圖。因此，如果位圖和inode之間存在任何不一致，則通過信任inode內(nèi)的信息來解決它。對所有inode執(zhí)行相同類型的檢查，確保所有看起來像在用的inode，都在inode位圖中有標(biāo)記。

inode狀態(tài)：檢查每個inode是否存在損壞或其他問題。例如，fsck確保每個分配的inode具有有效的類型字段（即常規(guī)文件、目錄、符號鏈接等）。如果inode字段存在問題，不易修復(fù)，則inode被認為是可疑的，并被fsck清除，inode位圖相應(yīng)地更新。

inode鏈接：fsck還會驗證每個已分配的inode的鏈接數(shù)。你可能還記得，鏈接計數(shù)表示包含此特定文件的引用（即鏈接）的不同目錄的數(shù)量。為了驗證鏈接計數(shù)，fsck從根目錄開始掃描整個目錄樹，并為文件系統(tǒng)中的每個文件和目錄構(gòu)建自己的鏈接計數(shù)。如果新計算的計數(shù)與inode中找到的計數(shù)不匹配，則必須采取糾正措施，通常是修復(fù)inode中的計數(shù)。如果發(fā)現(xiàn)已分配的inode但沒有目錄引用它，則會將其移動到lost + found目錄。

重復(fù)：fsck還檢查重復(fù)指針，即兩個不同的inode引用同一個塊的情況。如果一個inode明顯不好，可能會被清除。或者，可以復(fù)制指向的塊，從而根據(jù)需要為每個inode提供其自己的副本。

壞塊：在掃描所有指針列表時，還會檢查壞塊指針。如果指針顯然指向超出其有效范圍的某個指針，則該指針被認為是“壞的”，例如，它的地址指向大于分區(qū)大小的塊。在這種情況下，fsck不能做任何太聰明的事情。它只是從inode或間接塊中刪除（清除）該指針。

目錄檢查：fsck不了解用戶文件的內(nèi)容。但是，目錄包含由文件系統(tǒng)本身創(chuàng)建的特定格式的信息。因此，fsck對每個目錄的內(nèi)容執(zhí)行額外的完整性檢查，確保“.”和“..”是前面的條目，目錄條目中引用的每個inode都已分配，并確保整個層次結(jié)構(gòu)中沒有目錄的引用超過一次。

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

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

3　解決方案2：日志（或預(yù)寫日志）

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

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

通過將注釋寫入磁盤，可以保證在更新（覆寫）正在更新的結(jié)構(gòu)期間發(fā)生崩潰時，能夠返回并查看你所做的注記，然后重試。因此，你會在崩潰后準(zhǔn)確知道要修復(fù)的內(nèi)容（以及如何修復(fù)它），而不必掃描整個磁盤。因此，通過設(shè)計，日志功能在更新期間增加了一些工作量，從而大大減少了恢復(fù)期間所需的工作量。

我們現(xiàn)在將描述Linux ext3（一種流行的日志文件系統(tǒng)）如何將日志記錄到文件系統(tǒng)中。大多數(shù)磁盤上的結(jié)構(gòu)與Linux ext2相同，例如，磁盤被分成塊組，每個塊組都有一個inode和數(shù)據(jù)位圖以及inode和數(shù)據(jù)塊。新的關(guān)鍵結(jié)構(gòu)是日志本身，它占用分區(qū)內(nèi)或其他設(shè)備上的少量空間。因此，ext2文件系統(tǒng)（沒有日志）看起來像這樣：

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

真正的區(qū)別只是日志的存在，當(dāng)然，還有它的使用方式。

數(shù)據(jù)日志

看一個簡單的例子，來理解數(shù)據(jù)日志（data journaling）的工作原理。數(shù)據(jù)日志作為Linux ext3文件系統(tǒng)的一種模式提供，本討論的大部分內(nèi)容都來自于此。

假設(shè)再次進行標(biāo)準(zhǔn)的更新，我們再次希望將inode（I[v2]）、位圖（B[v2]）和數(shù)據(jù)塊（Db）寫入磁盤。在將它們寫入最終磁盤位置之前，現(xiàn)在先將它們寫入日志。這就是日志中的樣子：

你可以看到，這里寫了5個塊。事務(wù)開始（TxB）告訴我們有關(guān)此更新的信息，包括對文件系統(tǒng)即將進行的更新的相關(guān)信息（例如，塊I[v2]、B[v2]和Db的最終地址），以及某種事務(wù)標(biāo)識符（transaction identifier，TID）。中間的3個塊只包含塊本身的確切內(nèi)容，這被稱為物理日志（physical logging），因為我們將更新的確切物理內(nèi)容放在日志中（另一種想法，邏輯日志（logical logging），在日志中放置更緊湊的更新邏輯表示，例如，“這次更新希望將數(shù)據(jù)塊Db追加到文件X”，這有點復(fù)雜，但可以節(jié)省日志中的空間，并可能提高性能）。最后一個塊（TxE）是該事務(wù)結(jié)束的標(biāo)記，也會包含TID。

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

1．日志寫入：將事務(wù)（包括事務(wù)開始塊，所有即將寫入的數(shù)據(jù)和元數(shù)據(jù)更新以及事務(wù)結(jié)束塊）寫入日志，等待這些寫入完成。

2．加檢查點：將待處理的元數(shù)據(jù)和數(shù)據(jù)更新寫入文件系統(tǒng)中的最終位置。

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

在寫入日志期間發(fā)生崩潰時，事情變得有點棘手。在這里，我們試圖將事務(wù)中的這些塊（即TxB、I[v2]、B[v2]、Db、TxE）寫入磁盤。一種簡單的方法是一次發(fā)出一個，等待每個完成，然后發(fā)出下一個。但是，這很慢。理想情況下，我們希望一次發(fā)出所有 5 個塊寫入，因為這會將 5 個寫入轉(zhuǎn)換為單個順序?qū)懭耄虼烁臁Ｈ欢捎谝韵略颍@是不安全的：給定如此大的寫入，磁盤內(nèi)部可以執(zhí)行調(diào)度并以任何順序完成大批寫入的小塊。因此，磁盤內(nèi)部可以（1）寫入TxB、I[v2]、B[v2]和TxE，然后才寫入Db。遺憾的是，如果磁盤在（1）和（2）之間斷電，那么磁盤上會變成：

補充：強制寫入磁盤

為了在兩次磁盤寫入之間強制執(zhí)行順序，現(xiàn)代文件系統(tǒng)必須采取一些額外的預(yù)防措施。在過去，強制在兩個寫入A和B之間進行順序很簡單：只需向磁盤發(fā)出A寫入，等待磁盤在寫入完成時中斷OS，然后發(fā)出寫入B。

由于磁盤中寫入緩存的使用增加，事情變得有點復(fù)雜了。啟用寫入緩沖后（有時稱為立即報告，immediate reporting），如果磁盤已經(jīng)放入磁盤的內(nèi)存緩存中、但尚未到達磁盤，磁盤就會通知操作系統(tǒng)寫入完成。如果操作系統(tǒng)隨后發(fā)出后續(xù)寫入，則無法保證它在先前寫入之后到達磁盤。因此，不再保證寫入之間的順序。一種解決方案是禁用寫緩沖。然而，更現(xiàn)代的系統(tǒng)采取額外的預(yù)防措施，發(fā)出明確的寫入屏障（write barrier）。這樣的屏障，當(dāng)它完成時，能確保在屏障之前發(fā)出的所有寫入，先于在屏障之后發(fā)出的所有寫入到達磁盤。

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

為什么這是個問題？好吧，事務(wù)看起來像一個有效的事務(wù)（它有一個匹配序列號的開頭和結(jié)尾）。此外，文件系統(tǒng)無法查看第四個塊并知道它是錯誤的。畢竟，它是任意的用戶數(shù)據(jù)。因此，如果系統(tǒng)現(xiàn)在重新啟動并運行恢復(fù)，它將重放此事務(wù)，并無知地將垃圾塊“??”的內(nèi)容復(fù)制到Db應(yīng)該存在的位置。這對文件中的任意用戶數(shù)據(jù)不利。如果它發(fā)生在文件系統(tǒng)的關(guān)鍵部分上，例如超級塊，可能會導(dǎo)致文件系統(tǒng)無法掛裝，那就更糟了。

補充：優(yōu)化日志寫入

你可能已經(jīng)注意到，寫入日志的效率特別低。也就是說，文件系統(tǒng)首先必須寫出事務(wù)開始塊和事務(wù)的內(nèi)容。只有在這些寫入完成后，文件系統(tǒng)才能將事務(wù)結(jié)束塊發(fā)送到磁盤。如果你考慮磁盤的工作方式，性能影響很明顯：通常會產(chǎn)生額外的旋轉(zhuǎn)（請考慮原因）。

我們以前的一個研究生Vijayan Prabhakaran，用一個簡單的想法解決了這個問題[P+05]。將事務(wù)寫入日志時，在開始和結(jié)束塊中包含日志內(nèi)容的校驗和。這樣做可以使文件系統(tǒng)立即寫入整個事務(wù)，而不會產(chǎn)生等待。如果在恢復(fù)期間，文件系統(tǒng)發(fā)現(xiàn)計算的校驗和與事務(wù)中存儲的校驗和不匹配，則可以斷定在寫入事務(wù)期間發(fā)生了崩潰，從而丟棄了文件系統(tǒng)更新。因此，通過寫入?yún)f(xié)議和恢復(fù)系統(tǒng)中的小調(diào)整，文件系統(tǒng)可以實現(xiàn)更快的通用情況性能。最重要的是，系統(tǒng)更可靠了，因為來自日志的任何讀取現(xiàn)在都受到校驗和的保護。

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

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

當(dāng)這些寫入完成時，文件系統(tǒng)會發(fā)出TxE塊的寫入，從而使日志處于最終的安全狀態(tài)：

此過程的一個重要方面是磁盤提供的原子性保證。事實證明，磁盤保證任何512字節(jié)寫入都會發(fā)生或不發(fā)生（永遠不會半寫）。因此，為了確保TxE的寫入是原子的，應(yīng)該使它成為一個512字節(jié)的塊。因此，我們當(dāng)前更新文件系統(tǒng)的協(xié)議如下，3個階段中的每一個都標(biāo)上了名稱。

1．日志寫入：將事務(wù)的內(nèi)容（包括TxB、元數(shù)據(jù)和數(shù)據(jù)）寫入日志，等待這些寫入完成。

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

3．加檢查點：將更新內(nèi)容（元數(shù)據(jù)和數(shù)據(jù)）寫入其最終的磁盤位置。

恢復(fù)

現(xiàn)在來了解文件系統(tǒng)如何利用日志內(nèi)容從崩潰中恢復(fù)（recover）。在這個更新序列期間，任何時候都可能發(fā)生崩潰。如果崩潰發(fā)生在事務(wù)被安全地寫入日志之前（在上面的步驟2完成之前），那么我們的工作很簡單：簡單地跳過待執(zhí)行的更新。如果在事務(wù)已提交到日志之后但在加檢查點完成之前發(fā)生崩潰，則文件系統(tǒng)可以按如下方式恢復(fù)（recover）更新。系統(tǒng)引導(dǎo)時，文件系統(tǒng)恢復(fù)過程將掃描日志，并查找已提交到磁盤的事務(wù)。然后，這些事務(wù)被重放（replayed，按順序），文件系統(tǒng)再次嘗試將事務(wù)中的塊寫入它們最終的磁盤位置。這種形式的日志是最簡單的形式之一，稱為重做日志（redo logging）。通過在日志中恢復(fù)已提交的事務(wù)，文件系統(tǒng)確保磁盤上的結(jié)構(gòu)是一致的，因此可以繼續(xù)工作，掛載文件系統(tǒng)并為新請求做好準(zhǔn)備。

請注意，即使在某些更新寫入塊的最終位置之后，在加檢查點期間的任何時刻發(fā)生崩潰，都沒問題。在最壞的情況下，其中一些更新只是在恢復(fù)期間再次執(zhí)行。因為恢復(fù)是一種罕見的操作（僅在系統(tǒng)意外崩潰之后發(fā)生），所以幾次冗余寫入無須擔(dān)心[3]。

批處理日志更新

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

為了解決這個問題，一些文件系統(tǒng)不會一次一個地向磁盤提交每個更新（例如，Linux ext3）。與此不同，可以將所有更新緩沖到全局事務(wù)中。在上面的示例中，當(dāng)創(chuàng)建兩個文件時，文件系統(tǒng)只將內(nèi)存中的inode位圖、文件的inode、目錄數(shù)據(jù)和目錄inode標(biāo)記為臟，并將它們添加到塊列表中，形成當(dāng)前的事務(wù)。當(dāng)最后應(yīng)該將這些塊寫入磁盤時（例如，在超時5s之后），會提交包含上述所有更新的單個全局事務(wù)。因此，通過緩沖更新，文件系統(tǒng)在許多情況下可以避免對磁盤的過多的寫入流量。

本文截選自《操作系統(tǒng)導(dǎo)論》

操作系統(tǒng)導(dǎo)論

譯者：王海鵬

美國知名操作系統(tǒng)教材

緊緊圍繞操作系統(tǒng)的三大主題元素:虛擬化 并發(fā)和持久性進行講解

豆瓣原版評分９.７

本書具有以下特色：

● 主題突出，緊緊圍繞操作系統(tǒng)的三大主題元素——虛擬化、并發(fā)和持久性。

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

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

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

● 提供作業(yè)、模擬和項目等眾多學(xué)習(xí)方式，鼓勵讀者動手實踐。

● 為教師提供教學(xué)輔助資源。

本文轉(zhuǎn)載自異步社區(qū)。

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。