InfiniFS論文解讀

在前期分析BeeGFS的中繼資料實作思路的文章中有提到，BeeGFS的中繼資料具有很好的負載均衡和本地化性能，但也存在一些不足，正好看了一篇FAST2022上的論文<<InfiniFS:An Efficent Metadata Service for Large-Scale Distribuited Filesytems>>， 在論文中對近根熱點、路徑尋址等方面提供了相應的解決方式，論文解析如下，供大家參考。

InfiniFS的系統結構

InfiniFS是一個分布式中繼資料系統，希望用一個單一的命名空間滿足整個資料中心的檔案管理需求，包括如下幾個元件：

用戶端（Client）: 使用者态實作的相容POSIX标準的檔案系統接口。

中繼資料服務（Metadata Server）：分布式中繼資料叢集，用于管理檔案系統目錄樹。

重命名協調器（Rename Coordinator）：中心化的重命名協調器，用于處理目錄的重命名及設定目錄權限的操作

核心技術

現代資料中心通常包含數十億甚至數百億的檔案，用一個超大規模的檔案系統來管理這些檔案，将對中繼資料服務帶來巨大的挑戰。

• 首先，随着目錄樹的擴充以及工作負載變得多樣，在目錄樹分區方面，同時取得優秀的中繼資料本地化能力和優秀的負載均衡能力将面臨挑戰。
• 第二，在超大規模檔案系統中随着檔案目錄深度的增加，路徑解析延遲可能會很高。
• 最後，由于超大規模的檔案系統通常有大量的用戶端在并發的操作，維護用戶端緩存的一緻性所帶來的的開銷将變得難以承受。

為了解決上述的挑戰，InfiniFS采用如下的三個關鍵設計來解決目錄樹分布及中繼資料通路性能問題。

通路-内容中繼資料分離

拆分目錄中繼資料、本地化及分組

首先，将目錄中繼資料拆分為通路中繼資料（access metadata）和内容中繼資料（content metadata），通路中繼資料用來描述目錄自身，包括：目錄名、目錄ID、目錄權限，内容中繼資料用來表示目錄的子目錄及檔案，包含：子目錄和檔案中繼資料、時間戳；通路中繼資料可以了解為很少變化的中繼資料，内容中繼資料是變化相對頻繁的中繼資料，

如下圖（b）。接着，将兩部分中繼資料進行負載分布，政策為：目錄的通路中繼資料與其父目錄分組放置，目錄的内容中繼資料與其下檔案中繼資料分組放置，以目錄ID為鍵進行一緻性Hash，将分組分布到不同的中繼資料服務上，如下圖（c）。注：○目錄中繼資料，□檔案中繼資料；◐通路中繼資料，◑内容中繼資料。

中繼資料存儲

使用KV引擎作中繼資料分區的後端存儲，中繼資料索引表結構如下，包含：目錄通路中繼資料，目錄内容中繼資料以及檔案中繼資料三種Key-Value索引對表。如上圖（a），假定（目錄/，A，C 的ID分别為0，1，2），解析路徑 /A/C/f1的過程如下：

1. 通過<0,A>擷取A的通路中繼資料，得到A的ID=1
2. 通過<1,C>擷取C的通路中繼資料，得到C的ID=2
3. 通過<2>擷取C的内容中繼資料，接着通過<2,f1>獲得檔案中繼資料

   

推斷式目錄解析

基于一緻性Hash算法，以<父目錄ID，目錄名，命名版本>為鍵，為每個目錄生成一個可預測的ID，InfiniFS設計了一種推斷式的路徑解析機制實作目錄樹的并行周遊，可以縮短中繼資料通路延遲。

可預測的目錄ID

1）建立目錄。Hash函數以目錄的"出生"元組<父目錄id，目錄名，命名版本>為鍵生成目錄ID。如下圖（a）

2）重命名目錄。隻有目錄的通路中繼資料需要修改，其内容中繼資料及目錄ID保持不變（是以該目錄下的所有"孩子"都不需要修改）；父目錄包含一個重命名清單（RL）記錄其下子目錄的重命名記錄（記錄它離家的孩子），格式為<目錄名，命名版本>，目錄首次重命名時會添加記錄到RL，而目錄自身包含一個後備指針（BP）記錄其重命名記錄（記錄它親爹是誰），格式為<父目錄ID，命名版本>，通過RL來決定目錄的命名版本。

如下圖（b），注：當一個目錄再次重命名時，隻有目錄的通路中繼資料會修改，其内容中繼資料、BP以及（親生）父目錄的RL都不會修改；當删除一個重命名目錄（如：B）的（親生）父目錄（如：A）時，（親生）父目錄的通路中繼資料及内容中繼資料都會被删除，但是RL會保留直到重命名目錄被删除（如：B）

3）删除目錄。删除一個重命名目錄時，會同時删除其（親生）父目錄RL上的記錄，這樣再次建立相同名字的目錄時命名版本重置為0，如下圖（c）

并行路徑解析

根據可預測的目錄ID，用戶端通過如下的步驟實作并行路徑解析：

1. 推斷目錄ID。client根據查找路徑/子路徑的根來推斷中間目錄的ID，首先通過命名版本為0的“出生”元組來計算路徑上所有目錄的目錄ID，然後發起查找。
2. 并行查找。client并行的查找請求，檢查通路權限以及比較推斷的ID和中繼資料服務上儲存的ID，如果不一緻則将正确的ID傳回給client。
3. 重複上述的1）和2）直到完成路徑解析。

如下圖（a），一個網絡RRT完成路徑解析；如下圖（b），重命名後 h（2，x，0） ≠ 12 = h（1，x，0），2個網絡RRT完成路徑解析

優化的中繼資料緩存

InfiniFS将目錄通路中繼資料緩存在用戶端的記憶體中以緩解近根熱點

緩存資料的組織

InfiniFS用戶端隻緩存目錄的通路中繼資料，緩存命中将消除發往中繼資料服務的近根查找請求，避免近根熱點以及確定路徑查找解析的擴充性。如下圖，InfiniFS按照檔案系統目錄樹在組織緩存項，并将葉子節點組織為LRU連結清單。

緩存延遲失效

在目錄重命名或者修改目錄權限後，很多緩存項将會過期，在上述情況下立即，對所有相關用戶端進行緩存失效實操上是不太可行的，首先因為用戶端（中繼資料）關系很難維護，其次用戶端可能會很多且遠遠多餘中繼資料服務數。

延遲失效機制，通過将失效消息廣播給中繼資料服務來解決該問題（中繼資料服務的數量遠遠少于用戶端數），這樣每個中繼資料服務在處理用戶端請求時能夠延遲确認過期緩存，如下圖（b）

1. client并不知道緩存已過期，在進行路徑解析時還會繼續使用緩存項，每個用戶端都有一個版本号，通過它來判斷緩存是否因為重命名而更新了。client與中繼資料服務互動時會帶上路徑及該版本号。
2. 中繼資料服務通過比較請求路徑與失效清單中的路徑來确認狀态（隻需要比較失效清單中請求版本号與最新版本号之間的條目）。如果路徑合法，請求将被處理并傳回成功
3. 中繼資料服務發現路徑不合法，會拒絕處理請求并新的路徑及版本傳回給用戶端

特别地，目錄重命名操作，會由中心化的重命名協調器來處理，以避免目錄的孤兒循環，協調器會将重命名消息廣播給中繼資料服務，如下圖（a）

1. 重命名請求發給協調器，由其檢測該重命名操作是否與其他正在進行的重命名操作有沖突，檢查通過将會給改重命名請求賦予一個遞增的版本号
2. 鎖定目标目錄（直到重命名完成），并行地向中繼資料服務廣播重命名消息，等待應答
3. 将目錄的通路中繼資料從源中繼資料服務移到目标中繼資料服務，如果是首次重命名，則更新父目錄的RL以及目錄自身的BP

   

   論文中，對跨目錄的重命名的一緻性問題，也進行了特别的說明

一緻性

重命名協調器維護一個重命名圖，用于跟蹤進行中的重命名操作的源和目标路徑。

循環孤兒

并發的目錄重命名可能導緻循環孤兒，這會導緻資料丢失，如下圖（a）是一棵正常的檔案系統目錄樹，

如下圖（b）和（c），C1想要将E重命名為C的子目錄（/D/E -> /A/B/C/），而C2想要将B重命名為F的子目錄（/A/B->/D/E/F/），兩個用戶端的重命名操作的是完全獨立的，它們并行執行将導緻産生循環孤兒子樹，破壞檔案系統樹。

中繼資料事務

InfiniFS中的中繼資料操作可以歸為3類：

1. 單中繼資料服務操作。如：目錄的readdir，檔案的create/delete/open/close/stat/set_permission。這些操作隻需要單個中繼資料服務參與，通過本地的KV引擎來保障一緻性
2. 兩個中繼資料服務的操作。如：目錄的mkdir/rmdir/statdir，檔案的rename。這些操作需要兩個中繼資料服務參與，通過兩階段送出協定來保證一緻性
3. 目錄重命名。通常目錄重命名和修改目錄權限的操作頻率不高，這兩類操作有重命名協調器負責處理

論文解讀到此，各位讀者也可以通過文章開頭的連結閱讀論文原文。