RFC-0136：Fxf

RFC-0136：Fxfs
狀態	已接受
區域	儲存空間
說明	新版 Fuchsia 檔案系統的概要總覽。
Gerrit 變更	588001
作者	csuter@google.com jfsulliv@google.com
審查人員	abarth@google.com brettw@google.com palmer@google.com
提交日期 (年-月-日)	2021-09-30
審查日期 (年-月-日)	2021-10-13

摘要

Fxfs 是 Fuchsia 的新檔案系統，由儲存空間團隊開發。這項提案概述了 Fxfs 的動機和高階設計決策。

提振精神

Fuchsia 現有的可變動檔案系統 Minfs 有些限制，因此難以新增我們想加入的功能，也難以達成效能目標。我們正在開發 Fxfs，希望取代 Minfs 來達成這些目標。

有些功能幾乎是必要條件，例如：

• 完整支援讀取/寫入 mmap
• 支援擴充屬性
• 嚴格執行配額
• 檔案系統通知 (特別是 inotify 支援)
• 檔案鎖定 (特別是 flock 支援)

我們最終可能還需要其他功能：

• 內建加密功能：可針對個別檔案加密
• 快照支援
• 檔案副本
• 支援多個音量
• 支援壓縮

我們的目標是達到與其他作業系統相當的檔案系統效能。在所有考量因素中，這項最難達成，也最需要投入心力。

所有檔案系統都必須考量以下基本檔案系統目標：

• 寫入放大率越低越好，這樣才能盡量減少快閃記憶體耗損。
• 有效率地使用空間，例如盡量減少小型檔案的浪費。
• 輕鬆遷移。

為達成這些目標，許多工作會在儲存堆疊和核心的其他位置完成，因此本文不會涵蓋這些工作；這份 RFC 僅著重於檔案系統實作項目 Fxfs。

Fxfs 非常適合在快閃儲存裝置上執行，但設計上並未排除在旋轉儲存裝置上使用，我們預期 Fxfs 在旋轉儲存裝置上也能順利執行。

利害關係人

協助人員：

審查人員：abarth@google.com、brettw@google.com、palmer@google.com

已諮詢：

我們已諮詢 Fuchsia 安全團隊，瞭解加密相關問題。

社交：

Local Storage 團隊已對 Fxfs 進行詳細的設計審查。

設計

記錄結構化合併樹

如要瞭解記錄結構化合併 (LSM) 樹狀結構，請參閱 Wikipedia。Fxfs 使用 LSM 樹狀結構提供持續性鍵/值資料結構，供 Fxfs 內部使用。

LSM 樹狀結構提供一些吸引人的屬性：

• 寫入裝置的圖層不可變更，也就是說：
  • 存取這些圖層時，不需要鎖定。
  • 限制特定類別的錯誤，如果圖層未經過修改，損毀的機率就會降低。
  • 可能更容易偵錯問題：如果圖層沒有變更，活動零件就會減少。
  • 這樣可簡化壓縮作業，並在背景套用更積極的壓縮方式，以節省空間。
• 系統會以批次形式依序寫入突變，而非逐一寫入，這對快閃儲存空間來說是較理想的寫入模式，可減少寫入放大，並避免不必要的清除週期。這種寫入模式也適用於旋轉儲存裝置。
• 快照支援比其他支援更容易中斷。
• 允許將寫入作業所需的工作延後至閒置時間 (許多裝置都有相當長的閒置時間)。這表示裝置閒置時可以執行壓縮作業，在最方便的時間進行。
• 壓縮作業可在背景執行，讓您有更多時間處理重要事項。
• 重寫中繼資料是經過充分練習的完整檔案系統作業，可簡化格式遷移作業。壓縮期間可以寫出完全不同的層格式。

但也有一些缺點：

• 空間管理更加困難：所有作業 (包括刪除) 都需要中繼資料空間，因此必須謹慎預留空間。請注意，支援快照的其他檔案系統也會發生這個問題，因此不只 LSM 樹狀結構會出現這種情況。
• 如果圖層數量龐大，讀取速度會較慢。我們可以採取一些緩解措施，例如使用 Bloom 篩選器，而壓縮作業會合併圖層，進而降低這項成本。

值得注意的是，即使選擇 LSM 樹狀結構，如果發現混合式方法可行，仍可選擇使用可變動的持續性層格式。

Fxfs 的 LSM 樹狀結構實作 API 需要合併函式，該函式會決定記錄的合併方式。

Fxfs 的記憶體內層是由有效率且適合並行的資料結構 (目前為跳躍串列) 所代表。

物件儲存庫

Fxfs 由物件儲存庫階層組成。物件儲存空間提供類似檔案的 API，以物件 ID (64 位元不帶正負號的整數) 做為鍵。系統支援簡單的命名空間功能 (即目錄支援或類似功能)，但並非必要；您可以使用物件儲存空間，並只使用物件 ID 參照物件。物件儲存空間會將中繼資料保留在持續性鍵值資料結構 (LSM 樹狀結構) 中。中繼資料包含一般檔案資訊，例如物件大小和對應至裝置位移的範圍。

Fxfs 的 LSM 樹狀結構會使用物件儲存空間來儲存其持續性層，這會產生循環依附元件：物件儲存空間會使用 LSM 樹狀結構來儲存中繼資料，而 LSM 樹狀結構則會使用物件儲存空間來儲存持續性層。如要解決這個問題，物件儲存空間會以階層方式排列：

1. 根上層商店

   根父項物件儲存空間僅由記憶體中的 LSM 樹狀結構支援，因此不依附於物件儲存空間。

   根父項商店只包含根商店的圖層檔案和日誌檔案 (稍後會討論)。請注意，LSM 樹狀結構只包含中繼資料 (例如範圍資訊)，且只有該資訊會永久駐留在記憶體中。

2. Root Store

   根存放區會使用根父項存放區來儲存其永久層檔案。

   根存放區包含支援檔案系統的所有其他物件，例如分配器和超級區塊使用的物件。

3. 子商店

   子商店會使用根商店儲存其永久層檔案。儲存使用者資料。子商店數量不限，但只能使用根商店做為上層商店，因此階層最多只能有三層。請注意，如有需要，我們可以支援更深層的物件商店階層。

物件

• 物件是由 64 位元不帶正負號的整數所識別，該整數在物件儲存的商店中是唯一的，因此如要在檔案系統中唯一識別物件，您必須指定商店。

• 0 為保留值，用於表示無效的物件 ID。

• 物件支援多個屬性，並以 64 位元屬性 ID 編列索引，該 ID 在物件內是專屬的。屬性具有類似檔案的 API，可讀取和寫入屬性內任意偏移位置的任意數量資料。一開始，Fxfs 只會公開物件的單一屬性存取權 (即檔案內容)。日後可能會使用其他屬性來支援擴充屬性。屬性可以稀疏。

• 寫入物件的模式有兩種：寫入時複製模式 (與 Minfs 相同) 和覆寫模式。在寫入時複製模式下，任何寫入已分配區塊的作業都會涉及寫入新分配的區塊、更新中繼資料以指向新區塊，然後釋放舊區塊。覆寫模式會覆寫現有區塊，因此不需要更新相同的中繼資料。大多數物件都會使用寫入時複製模式寫入，而這也是一開始唯一向外部使用者公開的模式。

日誌

Fxfs 的日誌有兩個用途：

1. 這項功能支援交易，可對多個檔案系統物件自動套用變更。
2. 在電源中斷時快速保存變更。如果沒有這項操作，記憶體層排清前不會有任何變更，但基於效能和寫入放大原因，最好盡可能延遲這項操作 (視記憶體限制而定)。

所有對記憶體內資料結構的變動都必須經過記錄檔。與 Minfs 的日誌不同，這個日誌是邏輯日誌，而非實體日誌。這大幅減少了日誌佔用的空間量，因為插入記錄可以用幾個位元組表示，而 Minfs 內資料結構的變更可能涉及多個區塊。

請注意，Fxfs 的日誌 (如 Minfs) 不會包含資料。不過，Fxfs 的日誌確實包含以 COW 模式寫入資料的檢查碼，而且 Fxfs 會在日誌重播期間驗證這些檢查碼，以檢查自上次已知裝置排清以來寫入的資料，這表示 Fxfs 可以偵測到 COW 寫入作業中斷，並將檔案內容還原至上次完整寫入的版本。Minfs 沒有這項資料總和檢查碼功能。

日誌會以單一檔案的形式存在，並持續擴充。變更會串流至檔案。樹狀結構壓縮後，日誌檔案開頭的範圍可以釋放，也就是說，日誌會含有稀疏前置字元。所有物件的大小都是 64 位元，而我們需要支援的寫入速率表示在我們的生命週期內，包裝不會是問題。為避免裝置任意重新排序寫入作業，系統會在每 4 KiB 區塊的結尾放置檢查碼。重播時，如果日誌中第一個區塊的總和檢查碼不符，重播就會結束。一個區塊的檢查碼會做為下一個區塊的種子，防止系統不慎接受用於不同位移的區塊，或是先前 Fxfs 執行個體的殘餘區塊。

重播日誌時，如何得知超級區塊未涵蓋的日誌檔案範圍，是一項挑戰。如要解決這個問題，日誌會使用覆寫模式運作，並預先分配範圍。重播期間，系統會使用日誌串流中的任何範圍，讀取日誌檔案中的後續偏移。

超級區塊

Fxfs 的超級區塊不只是區塊，但用途與傳統超級區塊類似，因此使用相同名稱。超級區塊會以物件的形式存在於根物件存放區。與其他物件不同，這些物件的第一個範圍會放置在裝置上的固定位置 (其他物件的位置則不受限制)。超級區塊的第一部分包含序列化結構，其中包含與其他檔案系統類似的資訊 (例如區塊大小、重要物件的物件編號等)。之後，超級區塊會包含根父項物件儲存空間中的所有記錄 (在寫入超級區塊時)。超級區塊的寫入方式與日誌相同：每個 4 KiB 區塊的結尾都有檢查碼。

有兩個超級區塊。掛接期間，系統會選擇序號最新的超級區塊。

掛接檔案系統的步驟如下：

1. 讀取具有最新序號的超級區塊。
2. 將日誌中的所有異動套用至記憶體內層。
3. 讀取圖層資訊，並初始化 LSM 樹狀結構的持續性圖層。

分配器

分配器會使用 LSM 樹狀結構儲存參照計數範圍 (這可有效視為持續儲存 <device-range> => <reference-count>)。Fxfs 一開始只支援一個參照計數，但日後可能會支援檔案複製或範圍共用，進而產生超過一個的參照計數。

目錄

物件儲存空間支援目錄，方法是儲存以下形式的記錄： <object-id><child-name> => <child-object-id><child-type>。這項資訊會記錄在用於其他物件中繼資料的相同樹狀結構中。

壓縮

一開始，壓縮作業會因需要釋出日誌空間而啟動。系統一開始會選擇合理的政策，並視需要調整；無論我們採取什麼做法，都不會與格式綁定，因此很容易變更。

檔案名稱編碼

Fxfs 用於檔案名稱的具體編碼目前尚未指定，但我們注意到，編碼選擇至少會與 UTF-8 相容，這是用於 FIDL 字串和 Rust 字串的編碼。Fxfs 區分大小寫，且不會執行正規化。如果發生相容性問題，可能需要變更這項設定。

檔案系統限制

• 檔案大小上限為 2^63 個位元組 (64 位元帶正負號整數的最大值)。在內部，Fxfs 最多可表示 2^64 位元組的檔案大小，但現有的檔案系統 API 會限制這個大小 (例如已簽署的 off_t 型別)。
• 目錄大小沒有特定限制，但實際上會受到磁碟大小和 inode 計數的限制。
• 每個磁碟區大約可有 2^64 個 inode。實際上，這項限制更可能取決於磁碟大小。
• Fxfs 大約可支援 2^64 個磁碟區。實際上，這項限制更可能受到磁碟大小和其他資源 (例如載入卷宗時的記憶體) 的影響。
• Fxfs 支援奈秒精細度的時間戳記，並以 2^64 位元秒和 2^32 位元奈秒表示，可代表 UNIX 指定期間的時間戳記，直到遙遠的未來。

Fsck

Fxfs 具有 fsck 的基本實作項目，可驗證分配情形和物件參照計數。我們會在不久的將來擴大 fsck 的涵蓋範圍。

Minfs

Minfs 的部分限制會影響 Fxfs 的設計選擇：

• 支援多執行緒。Minfs 是單一執行緒，回溯新增多執行緒支援的難度，遠高於在開始時實作。Fxfs 是多執行緒。
• Minfs 使用實體日誌，雖然簡單，但會造成大量的寫入放大。Fxfs 使用邏輯日誌。
• Minfs 對目錄大小和 inode 計數設有硬性限制。Fxfs 的限制主要取決於磁碟大小。
• 由於所有變更都必須回溯相容，且遷移作業必須經過仔細考量，因此演進 Minfs 的格式並不容易。Fxfs 仍需要遷移作業，但由於壓縮作業會觸發中繼資料的完整重寫作業，因此部分格式變更較為簡單。

實作

Fxfs 的原型設計已進行一段時間，樹狀結構內已有該設計 (//src/storage/fxfs)，且可選擇使用該設計取代 Minfs。目前 Minfs 仍是預設的可變動檔案系統。變更預設值的決定不在本 RFC 的範圍內。

語言

Fxfs 使用 Rust。我們認為 Rust 具有一些優勢：

• 記憶體安全：減少當機和安全問題，特別是在多個執行緒同時運作時。
• 良好的非同步支援：檔案系統可受益於高度平行處理，而 Rust 的非同步支援功能可大幅簡化這項作業，比其他語言更輕鬆。

效能

我們採用 Fxfs 的動機之一，是為了提升可變動檔案系統的效能。我們用來評估效能的基準是獨立開發而成。這些基準的確切性質不在本 RFC 的討論範圍內。

回溯相容性

Fxfs 最初會做為 Minfs 的替代方案，但支援有限 (不適合用於正式環境)，用於從 Minfs 遷移。

我們可能會在日後支援更完善的遷移作業。

安全性考量

Fxfs 最初可搭配 Zxcrypt 使用，進行磁碟區層級的加密 (就像 Minfs 一樣)，因此這方面應該不會有太大變化。Fxfs 是以 Rust 開發，理論上應可降低部分安全風險。

Fxfs 內建加密功能需要全面考量安全性，這超出本 RFC 的範圍。

隱私權注意事項

不適用

測試

Fxfs 使用的全面性檔案系統測試套件與 Minfs 相同。在適當情況下，還會有 Fxfs 專用的單元和整合測試。

說明文件

Fxfs 應可與 Minfs 互換，因此不需要額外的外部文件；我們的 API 不會變更。這份 RFC 本身就是主要構件，用於記錄 Fxfs 的高階設計。

缺點、替代方案和未知事項

開發新的檔案系統是一項重大工程。我們已實作功能和效能接近 Minfs 的原型，但 Fxfs 仍有進步空間，才能投入正式環境。

在啟動這項專案前，我們考慮過其他策略，例如移植現有的開放原始碼檔案系統，或是使用現有檔案系統的設計。考量因素包括：

• Fuchsia 的檔案系統介面與其他作業系統大不相同，因此移植作業並不容易。
• 部分現有的開放原始碼檔案系統有授權障礙。
• 程式碼集與大多數 Fuchsia 程式碼集不一致，且未來也不會一致 (C++ 不常見，測試做法也不同)。
• 選擇現有設計會對格式演進造成一些限制；為支援新功能需求而進行的格式變更，可能會導致格式分叉，以及/或因將變更向上推送而產生額外負擔。
• 我們需要執行的許多效能工作實際上並非在檔案系統實作中，因此無論如何，開發新的檔案系統可能都不在達成效能目標的關鍵路徑上。
• 現有檔案系統會附上演進歷程記錄。重新實作現有設計通常需要挑選要支援的功能集，因此相容性有限。
• 逐步變更 Minfs 以達到所需狀態，可能需要較長時間，因為我們很可能需要支援遷移作業。

因此，我們選擇支援外部對 F2fs 移植作業的貢獻，目標是讓 Fuchsia 能夠順利使用多種不同的檔案系統。

既有技術和參考資料

LSM 樹狀結構並非新技術，且廣泛用於各種應用程式，但較小規模檔案系統的使用範例有限。

如要瞭解 Fxfs 設計的其他層面，例如邏輯日誌格式和多卷宗支援，請參閱其他檔案系統。