was successfully added to your cart.

        當文件文件系統在整理磁碟結構(如FSCK)時、或是一般使用讀寫狀況下操作時遇到錯誤、崩潰、突然斷電,會發生什麼情況?
        這些情形發生時都有機會讓系統可能會在任何兩次寫入之間崩潰或斷電,因此磁碟狀態可能只會部分更新。進而導致再次掛載文件系統時的資料不一致,鑑於崩潰可能發生在任何時間點,我們如何確保文件系統將磁碟image保持在合理的狀態?以及
崩潰一致性又是怎麼發生的?最後我們要怎麼解決?

        本篇中,會詳細地描述崩潰一致性(Crash Consistency)這個問題,並且逐步地從基礎的文件系統問題到複雜的解決步驟一一講解用來克服的方法。

原文出處:
http://pages.cs.wisc.edu/~remzi/OSTEP/file-journaling.pdf

 

        我們將從傳統檢查文件系統的方法(稱為fsck或文件系統檢查程序)開始。 然後,我們使用另外一種稱為日誌(journaling,也稱為預寫式日誌記錄)的方法,這種方法會為每次寫入增加一點loadhead,但可以更快地從崩潰或功耗中恢復。
        我們也將討論日誌的基本機制,包括Linux ext3 [T98,PAA05](一種相對現代的日誌文件系統)實現的幾種不同類型的日誌記錄。

一、崩潰一致性:
        為了啟動我們對日誌的調查,我們來看一個例子。 我們需要使用以某種方式更新磁碟結構的workload。 這裡假設工作量很簡單:將單個data block附加到現有文件。 通過打開文件,調用lseek()將文件偏移量移至文件末尾,然後在關閉文件之前向文件發出單個4KB寫入來完成附加操作。
        我們假設在磁碟上使用標準的簡單文件系統結構,類似於我們以前見過的文件系統。 這個例子包括:

  • inode bitmap(只有8位,每個inode)
  • data bitmap(也是8位,每個data block一個)
  • inode(共8個,編號為0到7,分佈在四個block中)
  • Data blocks (共8個,編號為0到7)。
    以下是這個文件系統的圖表:

         如果查看圖中的結構,可以看到在inodebitmap中標記了一個inode(inode編號2)和一個分配的數據塊(數據塊4),這些數據塊也標記在數據中bitmap。 inode表示為I [v1],因為它是此inode的第一個版本; 它將很快更新(由於上述工作量)。
讓我們來看看這個簡化的inode。 在我[v1]的內部,我們看到:

         在這個簡化的inode中,文件的大小是1(它有一個block),第一個pointer指向block 4(文件的第一個Data Blocks),而其他三個pointer 為空(表示它們未被使用)。 當然,真正的inode有更多的domain。

       當我們追加文件時,我們正在為它添加一個新的Data block,因此必須更新三個磁碟結構:

  • inode(必須指向新block)
  • 新Data Blocks Db
  • 新版本的data bitmap(稱之為B[v2])

        以指示新Data Blocks已被分配。
       因此,在系統的memory中,我們有三個塊,必須寫入磁碟。 更新的inode(inode版本2,簡稱I [v2])現在看起來像這樣:

更新後的資料bitmap(B[v2])現在看起來像這樣:00001100.最後,有Data Blocks(Db),它只是填充了使用者放入任何內容的文件。也許是竊聽音樂?
我們想要的是文件系統的最終磁盤image如下所示:

為了實現這種轉換,文件系統必須對磁碟執行三次獨立寫入操作,每次對inode(I [v2]),bitmap(B [v2])和數據塊(Db)執行一次寫入。 請注意,當用戶發出write()系統調用時,這些寫操作通常不會立即發生; 相反,骯髒的內存,bitmap和新數據將首先駐留在主內存中(在頁面緩存或緩衝區緩存中)一段時間; 那麼,當文件系統最終決定將它們寫入磁碟(例如5秒或30秒之後)時,文件系統將向磁碟發出必要的寫入請求。 不幸的是,可能會發生崩潰,從而乾擾磁碟的這些更新。 尤其是,如果在發生一次或兩次寫入之後發生崩潰,但不是全部三次,則文件系統可能會處於滑稽狀態。

崩潰情景
為了更好地理解這個問題,我們來看看一些崩潰情景的例子。 想像一下,只有一次寫入成功; 因此有三種可能的結果,我們在此列出:

○只是將數據塊(Db)寫入磁碟。在這種情況下,數據在磁碟上,但沒有inode指向它,並且沒有bitmap甚至說分配了該塊。因此,就好像書寫從未發生過一樣。從這個角度來看,這種情況根本不是問題
文件系統崩潰一致性1。
o只更新的inode(I [v2])寫入磁碟。在這種情況下,inode指向Db即將寫入的磁碟地址(5),但Db尚未寫入該地址。因此,如果我們相信指針,我們將從磁碟讀取垃圾數據(磁碟地址5的舊內容)。
此外,我們有一個新問題,我們稱之為文件系統不一致。磁碟上的bitmap告訴我們數據塊5沒有被分配,但inode說它有。bitmap和inode之間的不一致是文件系統數據結構的不一致;要使用文件系統,我們必須以某種方式解決這個問題(更多關於下面的內容)。
o只更新bitmap(B [v2])寫入磁碟。在這種情況下,bitmap指示塊5已分配,但沒有指向它的inode。因此文件系統再次不一致;如果沒有解決,這個寫入將導致空間洩漏,因為塊5將永遠不會被文件系統使用。

在嘗試將三個塊寫入磁碟時,還有三個崩潰場景。在這些情況下,兩次寫入成功,最後一次寫入失敗:

o inode(I [v2])和bitmap(B [v2])寫入磁碟,但不寫入數據(Db)。在這種情況下,文件系統元數據是完全一致的:inode具有指向塊5的指針,bitmap指示5正在使用,因此從文件系統元數據的角度看,一切看起來都不錯。但是有一個問題:5又有垃圾。
o寫入inode(I [v2])和數據塊(Db),但不寫入bitmap(B [v2])。在這種情況下,我們將inode指向磁碟上正確的數據,但是在舊版本的bitmap(B1)之間再次出現不一致。因此,我們再次需要在使用文件系統之前解決問題。
o寫入bitmap(B [v2])和數據塊(Db),但不寫入inode(I [v2])。在這種情況下,我們再次在inode和數據bitmap之間存在不一致。但是,即使塊已寫入並且bitmap指示其用法,我們也不知道它屬於哪個文件,因為沒有inode指向該文件。

崩潰一致性問題
從這些崩潰場景中,您可以看到我們的磁碟文件系統映像因崩潰而可能發生的許多問題:我們可能在文件系統數據結構中存在不一致; 我們可以有空間洩漏; 我們可以將垃圾數據返回給用戶; 等等。 我們希望理想的做法是將文件系統從一個一致的狀態(例如,在文件附加到另一個狀態之前)移動到另一個狀態(例如,inode,bitmap和新的數據塊已經寫入磁碟之後)。 不幸的是,我們無法輕易做到這一點,因為磁碟一次只提交一次寫入,並且在這些更新之間可能會發生崩潰或斷電。 我們稱這個一般問題為崩潰一致性問題(我們也稱之為一致性更新問題)。

解決方案#1:文件系統檢查工具
早期的文件系統採用了一種簡單的方法來確保崩潰一致基本上,他們決定讓不一致發生,然後在重新啟動時修復它們。這種懶惰方法的典型例子是在一個工具中找到的:fsck2。 fsck是用於查找這種不一致的UNIX工具,維修和修理它們;類似的工具來檢查和修復磁碟
分區存在於不同的系統上。請注意,這種方法無法解決所有問題;例如,考慮以上情況,文件系統看起來一致但inode指向垃圾數據。唯一真正的目標是確保文件系統元數據內部一致。
正如McKusick和Kowalski的論文[MK96]所總結的那樣,fsck工具分幾個階段運行。它在文件系統安裝並可用之前運行(fsck假定運行時沒有其他文件系統活動正在進行);一旦完成,磁碟上的文件系統應該是一致的,因此可以被用戶訪問。
以下是fsck所做的一個基本總結:

o超級塊:fsck首先檢查超級塊是否看起來合理,主要是進行完整性檢查,例如確保文件系統大小大於分配的塊數。 通常這些理智檢查的目標是找到一個可疑(腐敗)超級塊; 在這種情況下,系統(或管理員)可能會決定使用超級塊的備用副本。
o空閒塊:接下來,fsck掃描inode,間接塊,雙重間接塊等,以了解當前在文件系統內分配了哪些塊。 它使用這些知識來生成正確版本的分配bitmap; 因此,如果bitmap和inode之間存在任何不一致,則通過信任inode內的信息來解決。 對所有inode執行相同類型的檢查,確保inodebitmap中所有類似inode的inode都被標記為inode。

o Inode狀態:檢查每個inode是否存在損壞或其他問題。例如,fsck確保每個分配的inode都有一個有效的類型字段(例如,常規文件,目錄,符號鏈接等)。如果inode字段出現問題並不容易修復,則inode將被視為可疑並由fsck清除; inodebitmap會相應更新。
o Inode鏈接:fsck還會驗證每個分配的鏈接的鏈接數量。您可能還記得,鏈接計數表示包含對該特定文件的引用(即鏈接)的不同目錄的數量。為了驗證鏈接數量,fsck從根目錄開始掃描整個目錄樹,並為文件系統中的每個文件和目錄構建自己的鏈接計數。如果新計算的計數與inode內發現的計數不匹配,則必須採取糾正措施,通常通過將計數固定在inode中。如果發現分配的inode但沒有目錄引用它,它將移動到lost + found目錄。
o重複:fsck還檢查重複的指針,即,其中的情況
兩個不同的inode指向同一個塊。如果一個inode顯然不好,它可能會被清除。或者,可以復制指向的塊,從而根據需要為每個inode提供自己的副本。
○壞塊:在掃描所有指針列表時,還執行壞塊指針的檢查。如果指針明顯指向超出其有效範圍的某個指針,則該指針被認為是“不好的”,例如,它的地址指的是大於分區大小的塊。在這種情況下,fsck不能做任何太聰明的事情;它只是從inode或間接塊中刪除(清除)指針。
o目錄檢查:fsck不理解用戶文件的內容;但是,目錄保存由文件系統本身創建的專門格式化的信息。因此,fsck會對每個目錄的內容執行額外的完整性檢查,確保“。”和“..”是第一個條目,分配目錄條目中引用的每個inode都是分配的,並確保沒有目錄在整個層次結構中鏈接多次。

正如你所看到的,構建一個工作fsck需要復雜的文件系統知識;確保這樣一段代碼在所有情況下都能正確工作,這可能是具有挑戰性的[G + 08]。然而,fsck(以及類似的方法)有一個更大或許更根本的問題:它們太慢了。使用非常大的磁碟捲時,掃描整個磁碟以查找所有分配的塊並讀取整個目錄樹可能需要幾分鐘或幾小時。隨著磁碟容量的增長以及RAID越來越流行,fsck的性能變得越來越差,儘管最近取得了進展[M + 13])。在更高層次上,fsck的基本前提似乎只是一點點不合理。考慮我們上面的例子,其中只有三個塊被寫入磁碟;掃描整個磁碟以解決僅更新三個塊時出現的問題非常昂貴。這種情況類似於將鑰匙放在臥室的地板上,然後通過開始搜索整個房子的密鑰恢復算法,從地下室開始,在每個房間里工作。 它的工作原理很浪費。 因此,隨著磁碟(和RAID)的增長,研究人員和從業者開始尋找其他解決方案。

解決方案2:日誌文件系統(或預寫日誌文件系統)
可能是一致性更新問題最流行的解決方案是從數據庫管理系統的世界竊取一個想法。這個想法被稱為預寫式日誌記錄,是為了解決這類問題而發明的。在文件系統中,出於歷史原因,我們通常會調用預寫式日誌記錄。第一個文件系統是Cedar [H87],儘管許多現代文件系統都使用這個想法,包括Linux ext3和ext4,reiserfs,IBM的JFS,SGI的XFS和Windows NTFS。
基本思路如下。在更新磁碟時,在覆蓋已有的結構之前,先寫下一個小記錄(磁碟上的其他位置,位於眾所周知的位置),描述您將要執行的操作。編寫本說明是“提前寫入”部分,並將其寫入我們組織為“日誌”的結構;因此,預寫日誌。
通過將註釋寫入磁碟,您可以保證,如果在更新(覆蓋)更新結構期間發生崩潰,則可以返回並查看所做的註釋並重試;因此,在崩潰之後,您將確切知道要修復哪些內容(以及如何修復它),而不必掃描整個磁碟。通過設計,日誌記錄在更新期間添加了一些工作,可以大大減少恢復過程中所需的工作量。
現在我們將描述一個流行的日誌文件系統Linux ext3如何將日誌整合到文件系統中。大多數磁碟上的結構與Linux ext2相同,例如,磁碟分為塊組,每個塊組都有一個inode和數據bitmap以及inode和數據塊。新的關鍵結構是日誌本身,它佔用了分區內或其他設備上的少量空間。因此,一個ext2文件系統(沒有日誌)看起來像這樣:

假設日誌放置在同一個文件系統映像中(儘管有時它放置在單獨的設備上,或作為文件系統中的文件),帶日誌的ext3文件系統如下所示:

真正的區別就在於期刊的存在,當然還有它的使用方式。

數據日誌
我們來看一個簡單的例子來理解數據日記如何工作。 數據日誌可作為Linux ext3文件系統的一種模式提供,大部分討論都基於這種模式。
假設我們再次有我們的規範更新,我們希望將inode(I [v2]),bitmap(B [v2])和數據塊(Db)再次寫入磁碟。 在將它們寫入其最終磁碟位置之前,我們現在首先將它們寫入日誌(a.k.a.日誌)。 這就是日誌中的樣子:

你可以看到我們在這裡寫了五個block。TxB Header block告訴我們關於此更新的信息,包括關於文件系統的掛起更新的信息(例如,塊I [v2],B [v2]和Db的最終地址)以及某種事務標識符(TID)。中間的三個塊只包含塊本身的確切內容;這就是所謂的物理日誌記錄,因為我們在日誌中放置了更新的確切物理內容(另一種想法,邏輯日誌記錄,在日誌中提供了更新的更新邏輯表示,例如,“此更新希望將數據塊Db附加到文件X“,這稍微複雜一些,但可以節省日誌中的空間並可能提高性能)。最後的塊(TxE)是該事務結束的標記,並且還包含TID。
一旦這個事務安全地在磁碟上,我們就可以覆蓋文件系統中的舊結構;這個過程被稱為檢查點。因此,為了檢查文件系統(即,使其與日誌中的更新更新一致),我們向其磁碟位置寫入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)寫入磁碟。一個簡單的方法是每次發行一個,等待每個完成,然後發布下一個。但是,這很慢。理想情況下,我們希望發布。

ASIDE:強制寫入磁碟
為了強制在兩個磁碟寫入之間進行排序,現代文件系統必須採取一些額外的預防措施。在過去,強制在兩次寫入之間進行排序,A和B很容易:只需向磁碟寫入A,等待寫入完成後磁碟中斷OS,然後再寫入B.
由於磁碟內寫入緩存的使用增加,事情變得稍微複雜一些。啟用寫入緩衝(有時稱為即時報告)時,當磁碟放置在磁碟的內存高速緩存中且尚未到達磁碟時,磁碟將通知操作系統寫入已完成。如果操作系統隨後發出後續寫入,則不能保證在之前的寫入之後到達磁碟;因此寫入之間的順序不會被保留。一種解決方法是禁用寫入緩衝。但是,更現代化的系統需要額外的預防措施並提出明確的書寫障礙;這種障礙在完成時會保證在屏障之前發出的所有寫入將在屏障之後發出的任何寫入之前到達磁碟。
所有這些機器都需要對磁碟的正確操作有很大的信任。不幸的是,最近的研究表明,一些磁碟製造商為了提供“更高性能”的磁碟,顯然忽略了寫屏障請求,從而使磁碟看起來運行得更快,但存在操作不正確的風險[C + 13,R +11。正如卡漢所說,即使齋戒是錯誤的,齋戒幾乎總能擊敗緩慢。

所有五個塊寫入,因為這會將五個寫入轉換為單個順序寫入,並因此更快。 但是,這是不安全的,因為以下原因:給予這麼大的寫入,磁碟內部可以執行調度並以任何順序完成大寫的小部分。 因此,磁碟內部可能(1)寫入TxB,I [v2],B [v2]和TxE,並且僅在稍後
(2)寫Db。 不幸的是,如果磁碟在(1)和(2)之間斷電,這就是磁碟上的結果:

為什麼這是個問題? 那麼,這個事務看起來像一個有效的交易(它有一個開始和結束的序列號)。 此外,文件系統無法查看第四個塊並知道它是錯誤的; 畢竟,這是任意的用戶數據。 因此,如果系統現在重新啟動並運行恢復,它將重放此事務,並無意複製垃圾塊’??’的內容。 到Db應該居住的地點。 這對於文件中的任意用戶數據是不利的; 如果它發生在一個重要的文件系統上,比如超級塊,它可能會導致文件系統無法掛載,那麼情況會更糟糕。

ASIDE:優化日誌寫入
您可能已經註意到寫入日誌的特別低效率。也就是說,文件系統首先必須寫出事務開始塊和事務的內容;只有在這些寫入完成後,文件系統才能將事務結束塊發送到磁碟。如果您考慮磁碟的工作方式,性能影響很明顯:通常會發生額外的旋轉(想想為什麼)。
我們以前的研究生之一Vijayan Prabhakaran有一個簡單的想法來解決這個問題[P + 05]。在向日記帳寫入交易時,將日記帳內容的校驗和包括在開始和結束欄中。這樣做可以使文件系統立即寫入整個事務,而不會發生等待;如果在恢復期間,文件系統在計算的校驗和與事務中存儲的校驗和之間看到不匹配,則可以斷定在寫入事務期間發生崩潰並因此丟棄文件系統更新。因此,通過在寫入協議和恢復系統中進行小小的調整,文件系統可以實現更快的常見性能;最重要的是,系統稍微更可靠,因為從日誌中讀取的任何數據現在都受到校驗和的保護。
這個簡單的修復很有吸引力,可以獲得Linux文件系統開發人員的注意,後者然後將其整合到下一代Linux ext4 文件系統中。它現在在全球發行數百萬台機器,包括Android手持平台。因此,每當您在許多基於Linux的系統上寫入磁碟時,都會發現一些小小的代碼

為避免此問題,文件系統分兩步發出性寫入。 首先,它將除TxE塊之外的所有塊寫入日誌,並一次發出這些寫入。 當這些寫入完成時,日誌將看起來像這樣(假設我們再次追加工作負載):

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

這個過程的一個重要方面是磁碟提供的原子性保證。 事實證明,該磁碟保證任何512字節

寫或者會發生或者不發生(並且永遠不會被寫成一半); 因此,為了確保TxE的寫入是原子的,應該使其成為單個512字節的塊。 因此,我們目前的協議來更新文件系統,其三個階段分別標記為:

1.日誌寫入:將事務的內容(包括TxB,元數據和數據)寫入日誌; 等待這些寫入完成。
2.日誌提交:將事務提交塊(包含TxE)寫入日誌; 等待寫入完成; 交易據說是承諾的。
3.檢查點:將更新內容(元數據和數據)寫入其最終的磁碟位置。

恢復
現在我們來了解文件系統如何使用日記的內容從崩潰中恢復。在這一系列更新過程中,任何時候都可能發生崩潰。如果在將事務安全寫入日誌之前發生崩潰(即,在上述步驟2完成之前),那麼我們的工作很簡單:掛起的更新只需跳過即可。如果在事務已經提交到日誌之後,但在檢查點完成之前發生崩潰,則文件系統可以按如下方式恢復更新。系統引導時,文件系統恢復進程將掃描日誌並查找已提交給磁碟的事務;這些事務因此被重放(依次),文件系統再次嘗試將事務中的塊寫出到其最終的磁碟位置。這種記錄形式是最簡單的形式之一,被稱為重做日誌記錄。通過恢復日誌中的已提交事務,文件系統確保磁碟上的結構是一致的,因此可以通過掛載文件系統並為新請求自行準備進行。
請注意,即使在塊的最終位置的某些更新已完成後,在檢查指向期間的任何時候發生崩潰也是可以的。在最壞的情況下,這些更新中的一部分在恢復過程中會再次執行。由於恢復是一種罕見的操作(只發生在意外的系統崩潰之後),因此需要進行一些冗餘的寫操作

批處理日誌更新
您可能已經註意到基本協議可能會增加大量額外的磁碟流量。例如,假設我們在同一個目錄中創建了兩行文件,名為file1和file2。要創建一個文件,必須更新多個磁碟結構,最低限度包括:inodebitmap(分配新的inode),新創建的文件inode,

包含新目錄條目的父目錄的數據塊以及父目錄inode(現在有一個新的修改時間)。使用日誌功能,我們在邏輯上將所有這些信息提交給我們的兩個文件創作中的每一個;因為這些文件位於同一個目錄中,並且假設他們甚至在同一個inode塊中有inode,這意味著如果我們不小心,我們最終會反複寫入這些相同的塊。
為了解決這個問題,一些文件系統不會每次更新一個磁碟(例如Linux ext3)。相反,可以將所有更新緩衝到全局事務中。在我們上面的例子中,當創建兩個文件時,文件系統將內存inodebitmap,文件的inode,目錄數據和目錄inode標記為臟,並將它們添加到組成當前塊的列表交易。當最終時間將這些塊寫入磁碟時(例如,在5秒超時後),這個單個全局事務將被提交,其中包含上述所有更新。因此,通過緩衝更新,文件系統在很多情況下可以避免過多的磁碟寫入流量。

使日誌有限
因此,我們已經達成了更新文件系統磁碟結構的基本協議。文件系統在內存中緩存更新一段時間;當最後一次寫入磁碟時,文件系統首先仔細地將交易的細節寫到日誌(a.k.a.預先寫好的日誌)中;事務完成後,文件系統會將這些塊檢查到磁碟上的最終位置。
但是,日誌的大小是有限的。如果我們不斷向它添加交易(如本圖所示),它將很快填滿。那麼你認為會發生什麼?

日誌變滿時出現兩個問題。 第一種方法比較簡單,但不太重要:日誌越大,恢復時間就越長,因為恢復過程必須重播日誌中的所有事務(按順序)才能恢復。 第二個問題更為嚴重:當日誌滿(或接近滿)時,不能再向磁碟提交進一步的事務,從而使文件系統“不夠用”(即無用)。
為了解決這些問題,日誌文件系統將日誌視為循環數據結構,反復重複使用日誌; 這就是為什麼期刊有時被稱為循環日誌。 為此,文件系統必須在檢查點後一段時間採取行動。 具體來說,一旦一個事務處於檢查點,文件系統應該釋放它在日誌中佔用的空間,從而允許重用日誌空間。 有很多方法可以達到這個目的; 例如,你可以簡單地標記日誌超級塊中日誌中最舊和最新的非檢查點事務; 所有其他空間都是免費的。 這是一個圖形描述:

在日誌超級塊中(不要與主文件系統超級塊混淆),日誌系統記錄足夠的信息以知道哪些事務尚未被檢查點,從而減少了恢復時間,並且可以重新使用日誌以循環方式。因此我們在基本協議中增加了另一個步驟:

1.日誌寫入:將事務的內容(包含TxB和更新內容)寫入日誌;等待這些寫入完成。
2.日誌提交:將事務提交塊(包含TxE)寫入日誌;等待寫入完成;交易現在承諾。
3.檢查點:將更新的內容寫入文件系統中的最終位置。
4.免費:一段時間後,通過更新日記帳超級塊,在日記中免費標記交易。

因此,我們有我們的最終數據日記協議。但是仍然存在一個問題:我們將每個數據塊寫入磁碟兩次,這是一項沉重的代價,特別是對於像系統崩潰那樣罕見的事情。你能想出一種保持一致性的方法,而不用兩次寫入數據嗎?

元數據日記
雖然現在恢復速度很快(掃描日誌並重播一些事務而不是掃描整個磁碟),但是文件系統的正常運行速度比我們想要的要慢。特別是,對於每次寫入磁碟,我們現在也首先寫入日誌,從而使寫入流量翻倍;在連續寫入工作負載期間,這種加倍是特別痛苦的,現在將以驅動器峰值寫入帶寬的一半進行。此外,在寫入日誌和寫入主文件系統之間,存在代價高昂的尋找,這為一些工作負載增加了明顯的開銷。
由於將每個數據塊寫入磁碟兩次的成本很高,為了加速性能,人們嘗試了一些不同的方法。例如,我們上面描述的日誌模式通常被稱為數據日誌(如在Linux ext3中),因為它記錄了所有用戶數據(除了文件系統的元數據之外)。一種更簡單(也是更常見)的日誌形式有時被稱為有序日誌(或僅僅是元數據)日誌),除了用戶數據沒有寫入日誌以外,它幾乎是一樣的。 因此,當執行與上述相同的更新時,以下信息將被寫入日誌中:

先前寫入日誌的數據塊Db將改為寫入文件系統,避免額外寫入;考慮到大多數磁碟的I / O流量都是數據,而不是兩次寫入數據會大大減少日誌的I / O負載。然而,修改引發了一個有趣的問題:我們應該在什麼時候將數據塊寫入磁碟?
讓我們再次考慮一個文件的示例附件,以更好地理解問題。更新由三個塊組成:I [v2],B [v2]和Db。前兩個都是元數據,將被記錄,然後檢查指出;後者只會被寫入一次文件系統。我們應該什麼時候將Db寫入磁碟?有關係嗎?
事實證明,數據寫入的順序對於僅用於元數據的日誌記錄很重要。例如,如果我們在交易(包含I [v2]和B [v2])完成後將Db寫入磁碟會怎樣?不幸的是,這個方法有一個問題:文件系統是一致的,但是我[v2]最終可能指向垃圾數據。具體來說,考慮寫入I [v2]和B [v2]但Db沒有將其寫入磁碟的情況。文件系統然後會嘗試恢復。由於Db不在日誌中,因此文件系統將重放寫入I [v2]和B [v2],並生成一致的文件系統(從文件系統元數據的角度來看)。然而,I [v2]將指向垃圾數據,即在Db所在的插槽中的任何位置。
為確保不會出現這種情況,有些文件系統(例如Linux ext3)會在將相關元數據寫入磁碟之前,先將(常規文件的)數據塊寫入磁碟。具體來說,協議如下:
1.數據寫入:將數據寫入最終位置;等待完成(等待是可選的;詳情見下文)。
2.日記元數據寫入:將開始塊和元數據寫入日誌;等待寫入完成。
3.日誌提交:將事務提交塊(包含TxE)寫入日誌;等待寫入完成;交易(包括數據)現在已經提交。
4.檢查點元數據:將元數據更新的內容寫入文件系統中的最終位置。
5.免費:稍後,在日記超級塊中標記交易免費。
通過先強制數據寫入,文件系統可以保證指針永遠不會指向垃圾。事實上,“在指向它的對象之前寫入指向的對象”這一規則是崩潰一致性的核心,甚至可以通過其他崩潰一致性方案[GP94](詳見下文)進一步加以利用。

在大多數係統中,元數據日記(類似於ext3的有序日記)比全數據日記更受歡迎。例如,Windows NTFS和SGI的XFS都使用某種形式的元數據日記。 Linux ext3提供了選擇數據,有序或無序模式的選項(無序模式下,數據可以隨時寫入)。所有這些模式保持元數據一致;它們在數據的語義上有所不同。
最後,請注意,正如上面的協議所述,強制數據寫入完成(步驟1)在寫入日誌(步驟2)之前不需要正確性。具體來說,將數據寫入以及事務開始塊和元數據發布給日誌將會很好;唯一真正的要求是在發布日誌提交塊之前完成步驟1和步驟2(步驟3)。

整蠱案例:阻止重用
有一些有趣的角落案例使得日記更加棘手,因此值得討論。其中有許多是圍繞著塊重用;正如Stephen Tweedie(ext3背後的主要力量之一)所說:
“整個系統的可怕部分是什麼?……它正在刪除文件,所有與刪除有關的東西都很毛茸茸,所有與刪除有關的事情……如果塊被刪除然後重新分配,發生的事情都會發生惡夢。 [T00]
Tweedie給出的具體例子如下。假設您正在使用某種形式的元數據日記(因此文件的數據塊未被記錄)。假設您有一個名為foo的目錄。用戶向foo添加一個條目(比如通過創建一個文件),因此foo的內容(因為目錄被認為是元數據)被寫入日誌;假設foo目錄數據的位置是塊1000.日誌因此包含如下所示的內容:

此時,用戶刪除目錄中的所有內容以及目錄本身,釋放塊1000以供重用。 最後,用戶創建一個新文件(比如foobar),這個文件最終重用了曾經屬於foo的同一塊(1000)。 foobar的inode和它的數據一樣,都是致力於磁碟的; 但是,請注意,因為元數據日記正在使用中,所以只有foobar的inode被委託給期刊; foobar文件中塊1000中新寫入的數據不記錄。

現在假設發生崩潰並且所有這些信息仍在日誌中。在重放期間,恢復過程只是重放日誌中的所有內容,包括在塊1000中寫入目錄數據;重播因此用舊目錄內容覆蓋當前文件foobar的用戶數據!顯然,這不是一個正確的恢復操作,當讀用foobar文件時用戶會感到驚訝。
這個問題有很多解決方案。人們可以,
足夠的,從不重複塊,直到刪除所述塊被檢查點排除在日誌之外。 Linux ext3所做的是向日誌中添加一種新的記錄類型,稱為撤銷記錄。在上面的情況下,刪除目錄會導致將撤銷記錄寫入日誌。回放日誌時,系統首先掃描這些回收記錄;任何這樣的撤銷數據都不會重播,從而避免了上述問題。

總結日記:時間軸
在結束我們關於日誌的討論之前,我們總結了我們討論過的協議,並用時間線描述了它們中的每一個。圖42.1顯示了記錄數據和元數據時的協議,而圖42.2顯示了僅記錄元數據時的協議。
在每個圖中,時間向下增加,圖中的每一行顯示寫入可以發出或可能完成的邏輯時間。例如,在數據日誌記錄協議(圖42.1)中,事務開始塊(TxB)的寫入和交易的內容可以在邏輯上同時發布,因此可以按任意順序完成;然而,寫入事務結束塊(TxE)必須等到前面的寫入完成後才能發出。同樣,直到事務結束塊已經提交,才能開始對數據和元數據塊的檢查指向寫操作。水平虛線表示必須遵守寫入順序的要求。
針對元數據日記協議顯示類似的時間線。請注意,數據寫入在邏輯上可以與寫入同時發出。

到交易開始和期刊的內容; 但是,它必須在交易結束前發布並完成。
最後,請注意在時間軸中為每個寫入標記的完成時間是任意的。 在真實係統中,完成時間由I / O子系統決定,它可能會重新排序寫入以提高性能。 關於命令我們有的唯一保證是必須為協議正確執行的那些(並且通過圖中的水平虛線顯示)。

解決方案3:其他方法
到目前為止,我們已經描述了兩種保持文件系統元數據一致的選擇:基於fsck的懶惰方法和稱為日誌的更為主動的方法。但是,這不是唯一的兩種方法。 Ganger和Patt引入了一種稱為Soft Updates [GP94]的方法。這種方法仔細排列了對文件系統的所有寫入操作,以確保磁碟上的結構永遠不會處於不一致的狀態。例如,通過在指向它的inode之前寫入指向數據塊的磁碟,我們可以確保inode從不指向垃圾;可以為文件系統的所有結構導出類似的規則。然而,實施軟件更新可能是一個挑戰。儘管上述日誌層可以在相對較少的文件系統結構知識的情況下實現,但軟件更新需要每個文件系統數據結構的複雜知識,並因此增加了系統的相當複雜度。
另一種方法稱為copy-on-write(yes,COW),並在許多流行的文件系統中使用,包括Sun的ZFS [B07]。這項技術不會覆蓋文件或目錄;相反,它將新的更新置於磁碟上以前未使用的位置。許多更新完成後,COW文件系統會翻轉文件系統的根結構,以包含指向新更新結構的指針。這樣做可以使文件系統保持一致。當我們在未來的章節中討論日誌結構文件系統(LFS)時,我們將更多地學習這種技術; LFS是COW的早期例子。

另一種方法是我們剛剛在威斯康辛州開發的方法。在這種名為基於反向指示器的一致性(或BBC)的技術中,不會在寫入之間執行排序。為了實現一致性,系統中的每個塊都會添加一個額外的返回指針;例如,每個數據塊都具有對其所屬的inode的引用。當訪問文件時,文件系統可以通過檢查前向指針(例如inode或直接塊中的地址)是否指向返回給它的塊來確定文件是否一致。如果是這樣,一切都必須安全地到達磁碟,因此文件是一致的;如果不是,則文件不一致,並返回錯誤。通過向文件系統添加回指針,可以獲得一種新的惰性崩潰一致性[C + 12]。
最後,我們還探討了減少日誌協議等待磁碟寫入完成的次數的技術。題為樂觀的崩潰一致性[C + 13],這種新方法盡可能多地向磁碟寫入數據,並使用事務校驗和的一般形式[P + 05]以及其他一些技術來檢測不一致情況他們出現了。對於一些工作負載,這些樂觀的技術可以將性能提高一個數量級。但是,為了真正正常工作,需要稍微不同的磁碟接口[C + 13]。

摘要
我們介紹了崩潰一致性的問題,並討論了解決這個問題的各種方法。構建文件系統檢查程序的較早方法有效,但在現代系統上恢復可能過於緩慢。因此,現在很多文件系統都使用日記功能。日誌記錄可將恢復時間從O(磁碟大小)縮短到O(日誌大小),從而在崩潰和重新啟動後大幅加快恢復速度。出於這個原因,許多現代文件系統使用日誌。我們也看到日記可以有很多不同的形式。最常用的是有序的元數據日誌,它可以減少到日誌的流量,同時仍然保持對文件系統元數據和用戶數據的合理一致性保證。