目錄

日誌結構的文件系統

技術的改變會給當前的文件系統帶來壓力。這種情況下，CPU 會變得越來越快，磁盤會變得越來越大並且越來越便宜（但不會越來越快）。內存容量也是以指數級增長。但是磁盤的尋道時間（除了固態盤，因爲固態盤沒有尋道時間）並沒有獲得提高。

這些因素結合起來意味着許多系統文件中出現性能瓶頸。爲此，Berkeley 設計了一種全新的文件系統，試圖緩解這個問題，這個文件系統就是日誌結構文件系統（Log-structured File System，LFS）。

日誌結構文件系統由 Rosenblum和 Ousterhout於 90 年代初引入，旨在解決以下問題：

• 不斷增長的系統內存
• 順序 I/O 性能勝過隨機 I/O 性能
• 現有低效率的文件系統
• 文件系統不支持 RAID（虛擬化）

另一方面，當時的文件系統不論是 UNIX 還是 FFS，都有大量的隨機讀寫（在 FFS 中創建一個新文件至少需要 5 次隨機寫），因此成爲整個系統的性能瓶頸。同時因爲 Page cache 的存在，隨機讀不是主要問題，隨着越來越大的內存，大部分的讀操作都能被 cache，因此 LFS 主要要解決的是減少對硬盤的隨機寫操作。

在這種設計中，inode 甚至具有與 UNIX 中相同的結構，但是現在它們分散在整個日誌中，而不是位於磁盤上的固定位置。所以，inode 很難定位。爲了能夠找到 inode ，維護了一個由 inode 索引的 inode map（inode 映射）。表項 i 指向磁盤中的第 i 個 inode 。這個映射保存在磁盤中，但是也保存在緩存中，因此，使用最頻繁的部分大部分時間都在內存中。

到目前爲止，所有寫入最初都緩存在內存中，並且追加在日誌末尾，所有緩存的寫入都定期在單個段中寫入磁盤。所以，現在打開文件也就意味着用映射定位文件的索引節點。一旦 inode 被定位後，磁盤塊的地址就能夠被找到。所有這些塊本身都將位於日誌中某處的分段中。

• 日誌結構文件系統主要使用四種數據結構：Inode、Inode Map、Segment、Segment Usage Table：
  

真實情況下的磁盤容量是有限的，所以最終日誌會佔滿整個磁盤空間，這種情況下就會出現沒有新的磁盤塊被寫入到日誌中。幸運的是，許多現有段可能具有不再需要的塊。例如，如果一個文件被覆蓋了，那麼它的 inode 將被指向新的塊，但是舊的磁盤塊仍在先前寫入的段中佔據着空間。

爲了處理這個問題，LFS 有一個清理（Clean）線程，它會循環掃描日誌並對日誌進行壓縮。首先，通過查看日誌中第一部分的信息來查看其中存在哪些索引節點和文件。它會檢查當前 inode 的映射來查看 inode 是否在當前塊中，是否仍在被使用。如果不是，該信息將被丟棄。如果仍然在使用，那麼 inode 和塊就會進入內存等待寫回到下一個段中。然後原來的段被標記爲空閒，以便日誌可以用來存放新的數據。用這種方法，清理線程遍歷日誌，從後面移走舊的段，然後將有效的數據放入內存等待寫到下一個段中。由此一來整個磁盤會形成一個大的環形緩衝區，寫線程將新的段寫在前面，而清理線程則清理後面的段。

日誌文件系統

雖然日誌結構系統的設計很優雅，但是由於它們和現有的文件系統不相匹配，因此還沒有廣泛使用。不過，從日誌文件結構系統衍生出來一種新的日誌系統，叫做日誌文件系統，它會記錄系統下一步將要做什麼的日誌。

微軟的 NTFS 文件系統、Linux 的 ext3 就採用了這樣的思路。OS X 將日誌系統作爲可供選項。爲了看清它是如何工作的，我們下面討論一個例子，比如 移除文件 ，這個操作在 UNIX 中需要三個步驟完成：

1. 在目錄中刪除文件
2. 釋放 inode 到空閒 inode 池
3. 將所有磁盤塊歸還給空閒磁盤池

在 Windows 中，也存在類似的步驟。不存在系統崩潰時，這些步驟的執行順序不會帶來問題。但是一旦系統崩潰，就會帶來問題。假如在第一步完成後系統崩潰。inode 和文件塊將不會被任何文件獲得，也不會再分配；它們只存在於廢物池中的某個地方，並因此減少了可利用的資源。如果崩潰發生在第二步後，那麼只有磁盤塊會丟失。日誌文件系統保留磁盤寫入期間對文件系統所做的更改的日誌或日誌，該日誌可用於快速重建可能由於系統崩潰或斷電等事件而發生的損壞。

一般文件系統崩潰後必須運行 fsck（文件系統一致性檢查）實用程序。

爲了讓日誌能夠正確工作，被寫入的日誌操作必須是冪等的（idempotent），它意味着只要有必要，它們就可以重複執行很多次，並不會帶來破壞。像操作 更新位表並標記 inode k 或者塊 n 是空閒的 可以重複執行任意次。同樣地，查找一個目錄並且刪除所有叫 foobar 的項也是冪等的。相反，把從 inode k 新釋放的塊加入空閒表的末端不是冪等的，因爲它們可能已經被釋放並存放在那裏了。

爲了增加可靠性，一個文件系統可以引入數據庫中原子事務（atomic transaction）的概念。使用這個概念，一組動作可以被界定在開始事務和結束事務操作之間。這樣，文件系統就會知道它必須完成所有的動作，要麼就一個不做。