技術文章 » 檔案系統考古 3：1994

檔案系統考古 3：1994

2023-06-26 15:00:32

在 1994 年，論文《XFS 檔案系統的可延伸性》發表了。自 1984 年以來，計算機的發展速度變得更快，儲存容量也增加了。值得注意的是，在這個時期出現了更多配備多個 CPU 的計算機，並且儲存容量已經達到了 TB 級別。對於這些裝置，僅僅對 4.3BSD 快速檔案系統（或 SGI IRIX 中稱為 EFS 的修改版本）進行改進已不再足夠。（點選此處

SGI 的基準測試中採用的計算機擁有大型背板和多個控制器（其中一項基準測試採用了一個具有 20 個 SCSI 控制器的裝置），大量的磁碟（上百塊硬碟機）以及多個 CPU（12個 CPU 插槽）和大量記憶體（最高1GB）。

SGI 是一家制造高效能運算機（HPC）和圖形工作站的企業。在 20 世紀 80 年代和 90 年代，SGI 是計算機圖形和視覺化領域的先驅和領導者。在進行基準測試時，SGI 會使用一系列具有特定設定的計算機裝置，並進行效能測試和比較，以評估其系統的效能和能力。

然而，SGI 在 2009 年申請破產保護，並在 2016 年以「Silicon Graphics International」為名重組，繼續致力於提供高效能運算和資料分析解決方案。SGI 在計算機發展史上留下了重要的足跡，並對計算機圖形和視覺化領域產生了深遠的影響。

當前所需的檔案系統處理能力已經超出了 FFS（Fast Filling System），檔案的大小也超過了 FFS 可以的處理能力，目錄中的檔案數量增大導致查詢時間過長，像分配點陣圖（allocation bitmaps）這樣的中央資料結構無法進行有效的擴充套件，並且全域性鎖在多個 CPU 的情況下會造成低效的檔案系統並行存取。於是，SGI 決定設計一個完全不同的檔案系統。

此外，整個 Unix 社群也面臨著來自 David Cutler 和 Helen Custer 的挑戰，他們開發了 Windows NT 4.0 的開發者。通過 Windows NT 4.0 中的 NTFS，他們展示了從頭開始設計系統的可能性。

新要求

XFS 檔案系統充滿了創新思想，與傳統的 Unix 檔案系統設計有很大的不同。其中的新特性包括：

  • 通過以下方式實現並行性：

    • 分配區域
    • Inode 鎖分離
    • 大規模並行 I/O 請求、DMA 和零拷貝 I/O 功能

  • 通過以下概念，提高存取的可延伸性：

    • B+樹：一種平衡的多路搜尋樹，可以有效地儲存和檢索大量的資料；
    • extent：一種用來描述連續的磁碟塊的資料結構，由（起始塊，長度）兩個欄位組成2；
    • 將「檔案寫入」和「檔案在磁碟上的佈局」分離，以便通過使用延遲分配和預分配來實現連續的檔案。

extent（區段）表示檔案在磁碟上連續的一段資料塊。每個 extent 由一個起始位置（start）和一個長度（length）描述符組成，用於指定檔案在磁碟上的物理儲存位置。通過使用 extent，檔案系統可以實現動態增長的 I/O 大小，從而提高吞吐量。extent 的概念還可以與延遲分配和預分配相結合，以優化檔案的佈局，使得檔案在磁碟上可以連續儲存。這種連續儲存可以減少磁碟定址的開銷，提高檔案讀寫的效率。

  • 引入預寫紀錄檔（write-ahead log）以記錄後設資料更改：
    • 非同步記錄紀錄檔以實現寫入合併
    • 利用紀錄檔進行恢復，使恢復時間與正在處理的資料量成比例，而不是與檔案系統的大小成比例。

XFS 是為了滿足這些特性而開發的，實現這些特性後就可以在視訊編輯、視訊服務和科學計算等領域充分發揮大型 SGI 裝置的效能。

一個不使用紀錄檔結構的紀錄檔檔案系統

在約同一時期，John K. Ousterhout 提出了一個問題：「為什麼作業系統的速度沒有跟上硬體的發展速度？」 Ousterhout 開始在實驗性的 Sprite 作業系統中探索基於紀錄檔的檔案系統的想法。

Sprite 是一種早期的分散式作業系統，最早由John K. Ousterhout 和 Kenneth L. Dickey）於1984年在加州大學伯克利分校開發。Sprite 的設計目標是提供高度可靠的分散式環境，支援在網路上連線的多臺計算機之間進行共同作業和通訊。它在學術界和研究領域具有一定影響力，為後續分散式作業系統的發展奠定了基礎。

基於紀錄檔的檔案系統是一個非常激進的想法，我們在後續的文章中會討論。儘管它們在時間上比 XFS 早一點，但這個概念的引入具有重要的意義。最初它們並不實用，因為它們需要不同的硬體提供更多的磁碟尋道。紀錄檔結構化檔案系統的理念必須變得更加精細才能產生實際影響，我們將在本系列的後續部分中討論它們。

IRIX 的處境

IRIX 是 Silicon Graphics Inc.（SGI）開發的作業系統，用於其工作站和伺服器產品線。它是基於Unix System V 的變種，幷包含了許多 SGI 獨有的功能和優化，以適應其高效能運算和圖形處理需求。IRIX 在1988年首次釋出，併成為 SGI 工作站的主要作業系統，為許多科學、工程和創意領域的應用提供了強大的計算和圖形處理能力。

IRIX 最初使用 EFS（Extent File System）作為其檔案系統，它是 BSD FFS 的一個改進版本，使用了 extents 來描述檔案的連續磁碟塊。它受到 8 GB 檔案系統大小限制，2 GB 檔案大小限制，以及無法充分利用硬體 I/O 頻寬的影響，這讓許多購買了這些昂貴機器的客戶感到不滿。後來，SGI 開發了 XFS 檔案系統來取代 EFS，並在 IRIX 5.3 版本中引入了 XFS3。XFS 是一種高效能的 64 位紀錄檔檔案系統，支援大容量儲存、快速恢復和高階管理功能。

視訊播放和資料庫社群對檔案系統提出了新的需求：需要支援數百 TB 的磁碟空間、數百 MB/s 的 I/O 頻寬以及許多並行的 I/O 請求，以便能夠充分利用硬體資源，同時確保不會出現 CPU 資源瓶頸。

「XFS檔案系統的可延伸性」這篇論文主要展示了它的功能，對其實現和設計決策進行了簡要討論，也沒有提供詳盡的基準測試。

功能特性

大容量檔案系統

XFS 支援大容量檔案系統。之前的檔案系統使用 32 位的指標來指向磁碟塊。塊的大小是 8 KB ，使用 32 位的塊指標，檔案系統的上限是 32 TB。

當使用 64 位的塊指標會導致許多資料結構的大小變成 8 位元組的倍數，這樣的操作會造成一些些浪費。

為了提高並行性（參見下文），XFS引入了「分配組」（Allocation Groups，簡稱AG）的概念，其大小總是小於 4GB。分配組（AG）擁有本地範例，這些範例具備檔案系統資料結構，例如，inode 對映或空閒塊跟蹤。這些本地範例可以獨立進行加鎖，從而允許在不同的分配組中進行並行操作。

分配組（AG）還有助於減小指標的大小：一般組內編號可以用 32 位指標表達。事實上，一個 4GB 的分配組可以容納最多 1M 個塊的塊，因為每個塊的最小大小為 4K。組內單個最大的 extent 可以用 40 位（5位元組）來表示（位置和大小各佔 20 位）。

檔案和檔案系統最大值為 8 EB（2^63-1）。

頻寬和並行

XFS 的設計目標之一就是並行操作。1994 年是 20 MB/s SCSI 控制器的時代，SGI 構建了能夠容納多個控制器和多個驅動器的大型電腦箱。基準測試參照了具有 480 MB/s 總頻寬的計算機，其檔案 I/O 效能超過 370 MB/s，無需進行任何調整，包括所有開銷。這對於當時的日常使用來說是相當令人印象深刻的。

XFS 通過使用大塊（4 KB或8 KB塊大小）和extents 概念來實現這一點。

Extent 和二元樹

在 XFS 中，「extent」 是一個核心概念，它通常是一個包含兩個欄位的元組（起始塊和長度）。將檔案塊對映到磁碟塊（「bmap」）時，「extent」 則包含三個元素，即一個三元組（偏移量，長度，起始塊）。由於分配組（AG）存在上限值，可以用一系列 4 位元組的 extent 來描述連續的多達 2M 個資料塊，這比 BSD FFS 之前的方法更為高效。

extent 也使 XFS 能夠進行大規模 I/O 請求。源於它們描述了連續的塊區域，這樣可以輕鬆建立讀取或寫入多個塊的請求。預設情況下，它使用 64 KB 的記憶體緩衝區進行 I/O 操作，除非有特殊規定使用更大的記憶體緩衝區。

XFS 通過條帶化（striping）來管理底層磁碟結構，並支援同時處理 2 或 3 個並行的 IO 請求。它會檢查反壓（backpressure），也就是檢查應用程式是否實際上在讀取資料。如果是的化，檔案系統會發出額外的讀取請求，以保持預設情況下最多 3 個請求同時進行，這樣可以一次處理 192KB 的資料。

extent 組被組織成一個線性的列表，但這會導致擴充套件性問題。因此，XFS 使用 B+ 樹來處理多個索引塊的情況，如果只有一個索引塊時，則退化為線性列表。

B+ 樹是一種樹狀資料結構，用於組織和管理 extent 組。它允許在大規模的 extent 組集合中高效地進行搜尋、插入和刪除操作。B+樹結構能夠有效地處理大量的 extent 組，並且具有較好的擴充套件性和效能。

通常，元組是根據其第一個值進行索引，但對於某些結構（如空閒列表），會保留多個索引：通過 startblock 索引進行接近性的空間索引是有用的，但也按 length 索引來適配正確的可用空間。

去掉每個檔案的寫鎖

Posix鎖定記憶體中的 inode 以保證原子寫入。這確保了任何兩個大型多塊寫操作總是按順序進行。

XFS還去掉了記憶體中的 inode 鎖：Posix 要求對於大型、重疊的多塊寫操作進行完全有序的處理。當它們重疊時，不能出現從寫操作 A 和寫操作 B 交替出現的塊混亂現象。

在大多數核心中，預設設定是在記憶體中的 inode 上放置一個檔案全域性鎖，以此確保每個 inode 只能有一個寫入者。資料庫的開發者對此非常不滿，因為它將任何單個檔案的寫並行性限制為 1。這也是為什麼 Oracle 建議將表空間分成多個檔案來實現並行性，每個檔案的大小不超過 1GB。

在 O_DIRECT 模式下，XFS 消除了這個鎖，並允許原子、並行的寫操作，資料庫開發者對此非常認同。

動態 inode 和空閒空間跟蹤優化

對於大型檔案系統，你永遠無法預知：應用程式是需要大量的 inode 來儲存許多小檔案，還是少量的大檔案。此外，inode 和檔案資料塊之間的距離是多少也沒有一個確定的答案。

對於第一個問題沒有一個好的答案，而對於第二個問題，答案是「讓它們儘可能接近」。因此，XFS 根據需要動態建立 inode，每次建立 64 個 inode 的塊。

對於較大的 inode，即 256 位元組的 inode（相比於 BSD FFS 的 128 位元組和傳統 Unix 的64位元組），XFS 使用的策略是，僅在需要時建立 inode，並將它們放置在檔案的開頭附近來進行補償。這樣可以釋放大量的磁碟空間。在具有固定 inode 計數的傳統 Unix 檔案系統中，高達3-4%的磁碟空間可能被預先分配的inode 所佔用。即使在使用了柱面組（cylinder groups），inode 與第一個資料塊之間仍然存在相當大的距離。

由於 inode 可以存在於磁碟上的任何位置，而不僅僅是超級塊後面，因此需要對 inode 進行跟蹤。XFS 通過每個分配組（AG）使用一棵 B+ 樹來實現這一點。該樹以起始塊為索引，在每個塊中記錄每個 inode 塊是否可用或正在使用。inode 本身並不儲存在樹中，而是儲存在靠近檔案資料的塊中。

類似地，空閒空間以塊為單位進行跟蹤，並在每個分配組（AG）的樹中進行兩次索引：起始塊和長度索引。

預寫式紀錄檔

系統崩潰後要恢復一個大型檔案系統可能會很慢。恢復時間與檔案系統的大小和檔案數量成正比，這是因為系統基本上必須掃描整個檔案系統並重建目錄樹，以確保資料的一致性。對於 XFS 來說，檔案系統更加脆弱，因為它提供了可變數量的 inode，並且在磁碟上分散地非連續儲存。恢復它們將會有很大的開銷。

使用後設資料的預寫式紀錄檔（write-ahead logging），可以在大部分情況下可以避免這個問題。使得恢復時間與紀錄檔的大小成正比，即與崩潰時正在處理的資料量成正比。

紀錄檔中包含了紀錄檔條目，每個條目包括一個描述符頭和所有更改過的後設資料結構的完整映象：包括 inode、目錄塊、空閒 extent 樹塊、inode 分配樹塊、分配組塊和超級塊。由於完整映象儲存在塊中，因此恢復過程非常簡單：只需將這些新的、更改過的映象複製到它們原本應該在的位置上，而無需瞭解它所更改的結構型別。

作者對紀錄檔非常信任：因此 XFS 最初沒有 fsck （檔案系統一致性檢查）程式。然而，事實證明這種設定過於樂觀了，因此現在有了 xfs_repair 程式。

後設資料更新效能

XFS 會記錄後設資料更新，這意味著它們需要被寫入檔案系統紀錄檔中。預設情況下，該紀錄檔會放置在檔案系統中。但也可以選擇將紀錄檔提取出來，放置在其他媒介上，例如快閃記憶體儲存或帶有電池備份的記憶體。

如果可能的話，對紀錄檔的寫入是非同步進行的，但是對於提供 NFS 服務的分割區來說，這種寫入只能是同步的。非同步寫入允許進行寫入批次處理，從而加快速度。但NFS伺服器從加速的紀錄檔儲存中獲益很多。

由於所有後設資料更新都需要被記錄在紀錄檔中，因此在進行大量後設資料操作時，可能會導致紀錄檔被洪水般的後設資料更新所佔滿。例如，執行 rm -rf /usr/src/linux 這樣的操作就不會特別快，因為後設資料更新流最終會導致紀錄檔溢位。而且，由於 XFS 中的其他所有操作都是基於分配組（AG）並行進行的，因此紀錄檔是可能引起資源競爭的唯一來源。

大檔案和稀疏檔案

在 FFS（Unix File System）中，檔案通過傳統的動態陣列（dynamic array）進行對映，該陣列包括直接塊（direct blocks）和最多三級的間接塊（indirect blocks）。在64位元檔案大小的情況下，這種方式就變得很笨拙：會需要超過三級的間接塊，同時會需要大量的資料塊。由於大量的資料塊的存在，塊編號基本上形成了一個遞增的數位列表。這不僅會增加管理的複雜性，也會增大儲存塊編號的空間開銷。FFS（以及 EFS）需要在每個塊被分配到檔案系統緩衝池（filesystem buffer pool）時就確定它們在磁碟上的位置。可以看到，FFS 實際上沒有嘗試在磁碟上連續佈局檔案，而是單獨放置每個塊。XFS 用 extents 取代了這個動態陣列。

在檔案放置對映（file placement maps）中，這些對映的 extents 是三元組（塊偏移量，長度，磁碟塊）。這些 extents 被儲存在 inode 本身中，直到溢位。然後，XFS 開始在 inode 中建立一個由對映 extents 組成的B+樹，通過邏輯塊號（logical block number）來索引對映 extents ，以便進行快速查詢。

在可以進行連續分配的前提下，這種資料結構允許將大量的塊（最多2M個塊）壓縮為一個單獨的描述符。因此，即使是大型檔案，也可以在非常少的 extents 中儲存，最理想的情況是每個分配組（AG）只需一個 extent。

實現連續佈局：延遲分配和預分配

XFS 引入了一個新概念：延遲分配，它可以在檔案系統緩衝池中分配虛擬 extent。這些預留的 extent 是用來存放還未寫入的資料塊，它們在磁碟上還沒有確定的物理位置。當進行重新整理操作時，這些 extent 會被填充實際的資料，然後按照連續的方式進行佈局，並以大塊方式進行線性寫入。這樣的設計可以提高寫入操作的效率。

這對檔案系統緩衝區的工作方式產生了根本性的改變。以前，通過使用（裝置，物理塊號）可以標識緩衝區快取中的塊，以防止重複分配緩衝區。然而，當將 XFS 移植到Linux時，如果在普通緩衝區不使用此類標識，最初 Linux 核心無法適應。因此 XFS 需要一個單獨的緩衝區快取。隨著移植工作的進行，這個問題後來得到了解決。

為了確保檔案可以在單個 extent 中進行儲存空間分配而不會出現碎片化，當開啟檔案時，XFS 會積極為其預分配儲存空間。預分配的磁碟空間量是根據檔案系統中的可用空間而確定的，預設情況下可能會預分配相當大的空間。

在網際網路上，有很多 XFS 使用者問到他們的磁碟空間在哪裡，答案是「在 /var/log 的開啟檔案控制程式碼中。此外，檢視手冊頁中關於 allocsize= 的部分，以及 /proc/sys/fs/xfs/speculative_prealloc_lifetime 。

區域性性

在提高「區域性性」方面，XFS 並不太依賴分配組（AG）來實現。分配組主要用於並行處理。相反，XFS 更多地通過在目錄和當前檔案的現有塊周圍放置檔案來優化資料的區域性性。唯一的例外是「新目錄」，這些新目錄會被放置在不同的分配組中，遠離它們的父目錄。

在大檔案中，如果需要分配新的 extent，也就是為新的資料塊分配空間時，根據論文中提到的規定，「首先靠近 inode ，然後靠近附近的塊」。這樣的設定方式使得 inode 放置在靠近檔案開頭的地方，並將後來新增的塊放置在已有塊的附近。

大目錄

在傳統的 Unix 檔案系統和 BSD FFS 中，目錄名稱查詢是線性操作。對於任何型別的路徑名到 inode 的轉換，大目錄會明顯減慢這一過程。

XFS 選擇了被廣泛使用的 B+ 樹作為目錄的資料結構。然而，由於鍵（檔名）是可變長度的結構，與其他檔案系統中的樹實現完全不同。XFS 的作者不喜歡這種情況，因此對檔名進行了雜湊處理，將其轉換為一個固定長度的 4 位元組名稱雜湊值。然後，將一個或多個目錄條目以（名稱，inode）對的形式儲存在 B+ 樹的值中。通過這種方式，XFS 能夠高效地管理目錄，並在需要時快速查詢和存取特定的檔案。這種雜湊處理方式允許 XFS 在 B+ 樹結構中使用固定長度的鍵，而不需要關注鍵的實際長度。

在這方面進行了一些討論，作者們發現短鍵可以讓每個塊儲存許多條目，從而形成寬樹，進而實現更快的查詢速度。他們自豪地宣稱：「我們可以擁有數百萬條目的目錄」，這在以前的 Unix 檔案系統中是難以想象的。

大量的程式碼

在 1994 年的 XFS 基準測試中，XFS 顯示出良好的線性擴充套件表現，能夠很好地利用硬體資源。它在 多核的大型電腦器上表現良好。

XFS 是一個大型檔案系統。Linux 的 ext2 有 5,000 行核心程式碼（和大約10倍這個數量的使用者空間程式碼）。而 XFS 有 50,000 行核心程式碼，這還不包括 IRIX 卷管理器 XLV（在Linux中，XFS 移植使用的是 LVM2）。

XFS 在 1999 年 5 月以 GNU GPL 許可協定釋出，並從 2001 年開始移植到 Linux 核心。截至 2014 年，它在大多數 Linux 發行版中得到支援，RHEL（Red Hat Enterprise Linux）將其作為預設檔案系統。

筆者認為，XFS 是具有最佳擴充套件性、最佳並行能力和修改時間最一致的檔案系統，這使得它成為任何型別的資料庫使用的首選檔案系統。它消除了一些全域性鎖，這些鎖會影響大型檔案系統的並行使用和效能，並且使用了具有 O(log(n)) 擴充套件性的 B+ 樹結構，而之前使用的演演算法擴充套件性都比較差。使用 extent 還允許動態增加 I/O 大小，有利於提高吞吐量，並與延遲分配的新穎思想一起促進將檔案在磁碟上連續地放置或儲存。

如有幫助的話歡迎關注我們專案 Juicedata/JuiceFS 喲！ (0ᴗ0✿)