| RFC-0136：Fxfs | |
|---|---|
| 狀態 | 已接受 |
| 區域 |
|
| 說明 | 全新 Fuchsia 檔案系統的概略總覽。 |
| Gerrit 變更 | |
| 作者 | |
| 審查人員 | |
| 提交日期 (年-月-日) | 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 安全性團隊，以便瞭解加密相關問題。
社會化：
本機儲存空間團隊已針對 Fxfs 進行詳細的設計審查。
設計
記錄結構化合併樹
如要瞭解記錄結構化合併 (LSM) 樹狀結構的概略說明，請參閱 維基百科。Fxfs 使用 LSM 樹狀結構，提供 Fxfs 內使用的持續性鍵/值資料結構。
LSM 樹狀結構提供一些吸引人的特性：
- 寫入裝置的圖層不可變更，也就是說：
- 存取這些圖層時，不需要鎖定。
- 限制特定類別的錯誤。如果未修改圖層，則較不容易發生圖層損毀的情況。
- 可能更容易偵錯問題：如果圖層沒有變更，則可減少移動的部分。
- 這麼做比較容易支援壓縮，而且在背景中可套用更積極的壓縮方式來節省空間。
- 變異會以批次方式依序寫出，而非分批寫出，這是針對快閃儲存空間的較佳寫入模式，可減少寫入放大效應，並避免不必要的擦除週期。這種寫入模式也適合旋轉式儲存裝置。
- 快照支援功能比其他方式更容易失效。
- 允許將寫入作業延後至閒置時間 (許多裝置都有相當長的閒置時間)。這在實際上代表的是，當裝置未使用時，系統就能執行壓縮作業，這也是最方便的時機。
- 壓縮作業可在背景執行，讓您有更多時間處理更重要的事。
- 重寫中繼資料是經過充分實作的完整檔案系統作業，可讓格式遷移作業更輕鬆。在壓縮期間，可以寫出完全不同的圖層格式。
但這麼做也有缺點：
- 空間管理更加困難：所有作業都需要中繼資料空間，即使是刪除作業也是如此，因此必須謹慎保留空間。請注意，其他支援快照的檔案系統也會發生這個問題，因此並非 LSM 樹狀結構專屬。
- 在有大量圖層的情況下，讀取速度會變慢。我們可以採用一些緩解措施，例如布隆篩選器，而壓縮功能則會透過合併圖層來降低這項成本。
值得一提的是，即使選擇使用 LSM 樹狀結構，如果我們發現混合方法較為合理，仍可選擇使用可變動的持久層格式。
Fxfs LSM 樹狀結構實作的 API 需要合併函式，用於指定記錄的合併方式。
Fxfs 的記憶體內層是由高效率、支援並行的資料結構 (目前為跳過清單) 所代表。
物件儲存庫
Fxfs 由物件儲存庫階層組成。物件儲存庫會提供以物件 ID 做為索引的類似檔案 API，此 ID 為 64 位元不帶正負號整數。雖然系統支援簡單的命名空間功能 (例如目錄支援或類似功能)，但這並非必要；您可以使用物件儲存空間，並只使用物件 ID 參照物件。物件儲存庫會將中繼資料儲存在持久的鍵/值資料結構 (LSM 樹狀結構) 中。中繼資料包含一般檔案資訊，例如物件大小和對應至裝置偏移的範圍。
Fxfs 的 LSM 樹狀結構會使用物件儲存空間來儲存其持續性層，這會產生循環依附：物件儲存空間會使用 LSM 樹狀結構來儲存中繼資料，然後 LSM 樹狀結構會使用物件儲存空間來儲存其持續性層。為解決這個問題，物件儲存空間會以階層方式排列：
根父項存放區
根父項物件儲存庫由僅限記憶體的 LSM 樹狀結構支援，因此不會對物件儲存庫產生依附性。
根目錄父項儲存庫只包含根目錄儲存庫的層級檔案和日誌檔案 (稍後會討論)。請注意，LSM 樹狀結構只包含中繼資料 (例如範圍資訊)，而且只有這類資訊會永久駐留在記憶體中。
Root Store
根儲存庫會使用根父儲存庫來儲存其永久層檔案。
根儲存庫包含所有其他物件，用於支援檔案系統，例如分配器和超級區塊使用的物件。
子商店
子商店會使用根商店來儲存其持續性層檔案。儲存使用者資料。子商店可以有很多，但只能使用根目錄商店做為父項，因此階層會限制在三個層級。請注意，我們可視需要支援更深層的物件儲存層級。
物件
物件會透過 64 位元未簽署整數進行識別，該整數在儲存物件所在的儲存空間中是唯一的，因此如要唯一識別檔案系統中的物件，您必須指定儲存空間。
0 是保留值，用於表示無效的物件 ID。
物件支援多個屬性，並以 64 位元屬性 ID 做為索引，此 ID 在物件中是唯一的。屬性具有類似檔案的 API，可在屬性內以任意偏移量讀取及寫入任意數量。一開始，Fxfs 只會公開物件 (即檔案內容) 的單一屬性存取權。日後，可能會使用其他屬性來支援擴充屬性。屬性可以是稀疏的。
寫入物件的模式有兩種：寫入時複製模式 (與 Minfs 相同) 和覆寫模式。在使用寫入時複製模式時，任何對已分配區塊的寫入作業都會涉及寫入新分配的區塊、更新中繼資料以指向新區塊，然後釋放舊區塊。覆寫模式會覆寫現有區塊，因此不需要更新相同的中繼資料。大多數物件都會使用寫入時複製模式進行寫入，且這是一開始向外部使用者公開的唯一模式。
日誌
Fxfs 的日誌有兩個用途：
- 它支援交易：能夠將變異應用於多個檔案系統物件。
- 在電力中斷的情況下，快速保存變更。如未執行此操作，則在記憶體層刷出之前，不會有任何變更會保留，但基於效能和寫入放大問題，建議盡可能延遲這項操作 (視記憶體限制而定)。
記憶體內資料結構的所有變異都必須經過日誌。與 Minfs 的日誌不同，日誌是邏輯日誌，而非實體日誌。這項功能可大幅減少日誌所需的空間量，插入記錄可用幾個位元組表示，而 Minfs 中資料結構的變更可能涉及多個區塊。
請注意，Fxfs 的記錄 (例如 Minfs) 不含資料。不過，Fxfs 的記錄檔確實會在以 COW 模式寫入的資料中加入總和檢查碼，並在記錄檔重播期間驗證自上次已知裝置清除後寫入的資料，這表示 Fxfs 可以偵測到 COW 寫入作業中斷的情況，並將檔案內容還原為上次完整寫入的版本。Minfs 沒有這項資料檢查和總和檢查功能。
日誌是以單一不斷增加的檔案形式存在。變異會串流至檔案。樹狀結構經過壓縮後，系統可以釋放日誌檔案開頭的範圍，這表示日誌會有稀疏的前置字串。所有物件都具有 64 位元大小，而我們需要支援的寫入率意味著在生命週期中，我們不必擔心包裝問題。為因應裝置可自由重新排序寫入作業的事實，系統會在每個 4 KiB 區塊的結尾放置總和檢查碼。在重播時，重播作業會在日誌中第一個檢查和不相符的檢查碼結束。一個區塊的總和檢查碼會用來做為下一個區塊的種子，以防誤將用於不同偏移的區塊或先前 Fxfs 例項的遺留區塊誤當成有效區塊。
重播日誌時，要知道超級區塊未涵蓋的日誌檔案範圍，這項作業相當困難。為解決這個問題，日誌會使用覆寫模式的作業，並預先配置區域。重播期間，日誌串流中的任何邊界都會用於讀取日誌檔案中的後續偏移量。
超級區塊
Fxfs 的超級區塊不僅是區塊，而且與傳統超級區塊的用途相似，因此使用相同的名稱。超級區塊會以物件的形式存在於根物件儲存庫中。與其他物件不同的是，其第一個邊界會放在裝置上的固定位置 (所有其他物件都沒有位置限制)。超級區塊的第一部分包含序列化結構，其中包含與其他檔案系統類似的資訊 (例如區塊大小、重要物件的物件編號等)。之後，超級區塊會包含根父項物件儲存庫 (在超級區塊寫入時) 中的所有記錄。超級區塊的寫入方式與日誌相同：每個 4 KiB 區塊的結尾都有檢查和修復碼。
有兩個超級區塊。在掛載期間，系統會選擇具有最新序號的超級區塊。
掛接檔案系統的程序包括：
- 讀取含有最新序號的超級區塊。
- 將日誌中的所有異動事件套用至記憶體層。
- 讀取圖層資訊，並初始化 LSM 樹狀圖持久層。
Allocator
配置器會使用 LSM 樹狀結構來儲存參照計數區塊 (這可有效地視為持續儲存 <device-range> => <reference-count>)。一開始，Fxfs 只支援一個參照計數，但日後，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
我們在設計 Fxfs 時，會參考 Minfs 的部分限制：
- 支援多執行緒。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 設計方面，例如邏輯日誌格式和多卷支援，都可以在其他檔案系統中找到。