F2FS文件系統論文解讀

• F2FS
• • F2FS 輪廓
  • Design and Implementation of F2FS
  • • Block、Segment、Section and Zone
    • • 整體布局
      • 文件結構（file inode structure）
      • 目錄結構（Directory Structure）
      • 多級頭部日志（Multi-Head Logging）
      • Cleaning
      • Adaptive Logging
      • Checkpoint And Recovery

最近在做文件系統方面的工作，就把這幾天的工作貼上來吧。
參考文獻：
1. F2FS origin paper
2. F2FS slides
3. F2FS presentation
4. F2FS versus JFFS
5. UBIFS
6. UBIFS DOC

F2FS

F2FS 輪廓

首先需要明白F2FS與JFFS之間的區別。事實上，二者沒有可比性。因為F2FS把Flash設備看作塊設備，利用FTL（Flash Translation Layer）技術；而JFFS是直接由Flash的特點設計而來。

這里有一個很有趣的問題。

在JFFS2的presentation中，作者認為利用FTL是一個很爛的選擇。

這里值得一提的是，F2FS的誕生在2012年左右，而JFFS2在2001年左右就已經誕生。

下面是F2FS versus JFFS中的兩條回復：

It is designed for flash devices that expose themselves as block devices (like SSDs) and not for raw flash devices as jffs2 … so they aren’t really comparable.

And JFFS2 works really badly on file systems which sizes are in GBs as it AFAIK keeps the whole fs structure in RAM. From scalability point of view, UBIFS would be more reasonable comparison.

也許在進一步深入F2FS之前還應該去閱讀UBIFS。

The big difference between JFFS2 and UBIFS is that UBIFS stores the index on flash whereas JFFS2 stores the index only in main memory, rebuilding it when the file system is mounted.

點到為止，還有更多的工作需要完成，翻譯工作將在后續進行。

從Presentation來看，F2FS主要特點是：

Multi-Head Log，基于特殊FTL，該FTL能夠根據規則翻譯物理地址（zone 2 zone mapping）。根據后面的QA環節可以直到，這種FTL是由三星自研的。

冷熱數據分區。其規則是：Node比Data熱，在Node中，目錄文件下的Direct Node為Hot、File文件下的Direct Node為Warm、Indirect Node為Cold；Data中，Dirent為Hot、普通Data Block為Warm、被回收的、用戶指定的、多媒體數據文件等為Cold。

NAT。減少更新傳播（update propagation），所有Node通過NAT（Node Address Table） 翻譯

適應性追加Log機制（Adaptive Logging）。

(1).Append Logging 。在垃圾清理（cleaning）的時候，隨機讀順序寫；

(2).Threaded Logging。不需要垃圾清理，覆寫dirty Segments中的不可用Block，這導致隨機寫;

Rollback機制，在Presentation中沒有搞懂，還需閱讀論文。

Design and Implementation of F2FS

關于性能評估部分不需要做很深的研究，我們只需要知道它好就行了。不過F2FS適用于Nand Flash，但是也許我們同樣可從它的設計中取出一些精華。

Block、Segment、Section and Zone

F2FS把整個卷分成固定大小的Segment，Segment是F2FS進行管理的基本單位。

其中，若干Block構成Segment；若干Segment構成Section；若干Section構成Zone；

在Presentation中，我們可以看到：

Block大小一般為4KB；

Segment大小一般為2MB，也就是512個Block；

Section大小是n個Segment；

Zone大小是m個Section；

整體布局

• SuperBlock（SB）： SB具有F2FS文件系統的基本分區信息和一些默認參數，這些是在文件系統格式化的時候給出的，是不可更改的。

• Checkpoint（CP）：CP維護了文件系統的狀態、有效NAT/SIT集合的位圖、孤兒節點（Orphan inode）列表以及當前被激活的Segments的入口（Entries）。一個有效的”檢查點包“應該保存給定時間（given point of time）的F2FS狀態——用于掉電恢復。CP區域用兩個Segment保存了兩個檢查點包（#0和#1）：一個用于保存最近穩定的版本，另一個用于保存一個中間（過時的）版本；

• Segment Information Table（SIT）：SIT包含了每一個Segment的信息，例如：Segment中有效的Block數量以及在Main Area中的Block的位圖。另外，在垃圾清理階段（Cleaning），SIT中的信息還被用于選擇受害Segment（Victim Segment） 并識別其中的有效塊。

• Node Address Table（NAT）：NAT是一個Block地址映射表，用于定位所有在Main Area中的”Node Blocks“；

• Segment Summary Area（SSA）：SSA保存了“Summary Entries”，該Summary Entries 記錄了Main Area中所有Block的歸屬信息，例如：父Inode號以及它在其中的偏移 node/data offsets。在垃圾清理過程中，在遷移有效塊之前，這些“Entries”將被用于識別父node節點；

• Main Area（MA）：MA被大小為4KB的Block填充。每一個Block有兩種大的類型：node類型或data類型。一個Node Block包含了inode或Data Blocks索引，而一個Data Block包含了dirent或用戶數據。注意，一個Section并不同時存儲Node Blocks和Data Blocks

下面舉一個例子。

假設我們要查詢文件“/dir/file”

F2FS的查找步驟如下：

發現路徑開始為“/”，則從NAT中尋找Root inode對應的地址，然后讀取地址對應的Node Block，獲得Root inode；

在Root inode下，F2FS在它的Data Block中尋找名字為dir的dirent，通過dirent可以獲取對應的inode num；

接著，F2FS通過NAT將inode num轉化為物理地址，并通過讀取該物理地址對應的Node Block，獲取名字為dir的inode；

在dir inode中，與步驟2一樣，找到file對應的dirent，然后獲取其inode num，然后重復步驟3，最終獲得file inode；

真實的文件數據可在Main Area中獲取，接下來要說明文件的結構。

文件結構（file inode structure）

傳統的LFS利用inode map 將inode num翻譯為物理地址。相比而言，F2F2利用node結構，將inode map拓展到可以翻譯更多的索引塊上。每一個Node Block都有一個唯一標識符Node ID。通過這個Node ID，NAT可以為所有的Node Block提供它們相應的物理地址。一個Node Block有三種類型：inode、direct和indirect node。inode block包括了文件的元數據，例如文件名、inode num、文件大小、訪問時間、修改時間等；direct node block包含了Data Block的地址，而indirect node block則包含的是可以定位其他Node Block的Node ID。

也就是說，F2FS的indirect node的內容并不直接是另一個direct或者indirect node的物理地址，而是它們的邏輯ID。通過NAT表，我們可以將這個ID翻譯為它們對應的物理地址，這樣的好處是解決了Wandering Tree的問題。

在傳統的LFS中，如果一個位于葉子的Data Block被更新了，由于LFS的追加寫機制，那么它的direct和indirect指針Block都會被遞歸地更新，然后是指向direct或者indirect的inode也會被更新，接著是相應的inode map會被更新，最后是CP區域會被更新，見下圖。

但是F2FS僅僅更新一個direct node block和它對應的NAT入口，這有效解決了Wandering Tree的問題。

可以預見，Single-indirect、Double-indirect以及Triple-indirect 部分也都保存的Node ID。

目錄結構（Directory Structure）

在F2FS中，一個4KB大小的dentry block由幾個部分組成：bitmap以及兩個成對的slot和name數組。其中，slot包含了一個文件名的hash值，inode num，文件名長度以及文件類型（例如：普通文件、目錄文件以及符號鏈接）。一個目錄文件構建了一個多級哈希表來更有效地管理dentries。具體操作見wiki百科。

個人理解是：相當于每一個dentry block中的name的hash值都相同，可將多個block看作一個hash桶。因為在wiki百科中提到：

In the case of file creation, F2FS finds empty consecutive slots that cover the file name. F2FS searches the empty slots in the hash tables of whole levels from 1 to N in the same way as the lookup operation.

也就是說，在創建文件的時候，先會根據尋找算法 一樣的算法去插入一條dentry。

多級頭部日志（Multi-Head Logging）

不像LFS只有一個大的log區域，F2FS維護了六個主要的log區域來最大化冷熱數據分區效應。F2FS靜態地為Node Block和Data Block定義了3個數據溫度級別——hot、warm以及cold，如下表所示。

因為Direct Node Block更新更加頻繁，因此，它比Indirect Node Block更熱，反觀Indirect Node Block，它包含Node ID，并且僅僅只在一個Node Block被添加或者刪除時才會去追加寫更新。Direct Node Block和存儲Dentries的Data Block都被視為熱Block。其中，具有以下特點的Data Block被認為是冷Block：

• 被Cleaning過程移動的Data Block： 既然它們已經在Cleaning里被保留下來了，那么他們在不遠的將來也同樣不會被修改；
• 被用戶定義的Cold Data Block： F2FS允許用戶添加這個參數；
• 多媒體文件： 多媒體文件大都表現為”寫一次，只讀“模式。F2FS通過文件后綴名來識別這些文件。

F2FS默認開啟6個Log區域。同樣也支持2、4個Log區域。當6個區域都被激活時，6個區域對應上表的6種溫度級別的Block；當4個區域被激活時，F2FS將Cold和Warm Log區域合并在一起。如果只有2個Log區域，那么F2FS將一個區域分配給Node Block，一個區域分配給Data Block。

F2FS提供了一種Zone可定制FTL兼容方法，能夠間接減輕GC開銷。具體原理不太清楚，大概類似下圖的Zone-aware Allocation：

F2FS maps active logs to different zones to separate them in the FTL.

冷熱數據分離的原因？

是讓性能更好？對WL應該沒有什么幫助！

參考這篇文章On the Necessity of Hot and Cold Data Identification to Reduce the Write Amplification in Flash-based SSDs的結論：

In this paper we compare the performance of such a write approach with write approaches that do rely on data identification using both mean field models and simulation experiments. The main finding is that the added gain of identifying hot and cold data is quite limited, especially as the hot data gets hotter. Moreover, the write approaches relying on hot and cold data identification may even become inferior if either the fraction of data labeled hot is not ideally chosen or if the probability of having false positives or negatives when identifying data is substantial (e.g. 5%).

是了，這符合我的想法。
但是，導師告訴我
冷熱分離，一方面是性能，另外對磨損均衡還是有作用的，熱數據可以挪一挪，這很重要

Cleaning

在F2FS種，Cleaning是以Section為單位完成的。F2FS的Cleaning發生在Foreground 和Background 。Foreground Cleaning只在沒有足夠多的空閑Section時才發生，而Background Cleaning是由內核線程階段性的喚醒來完成。一個Cleaning包含3個步驟：

Victim Selection：主要有兩種方式，其一為Greedy——選擇具有最少有效塊的Section作為Victim Section，F2FS將Greedy方式作為Foreground Cleaning以最小化前端應用的延遲。另外，F2FS保留了5%的存儲空間，這足以夠Cleaning進程進來移動Block；第二種方式是cost-benefit，F2FS將其作為Background Cleaning方法，這種方法不僅僅根據Section的使用情況，還根據它的年齡來選擇Victim Section。F2FS利用SIT里記錄的信息來推測Section的年齡，一般是計算Section中所有Segment的平均年齡（F2FS infers the age of a section by averaging the age of segments in the section）。有了cost-benefit方法，F2FS就有了分別冷熱數據的另一種方法。

Valid block identification and migration：在進行完Victim Selection之后，F2FS必須驗證Section中Block的有效性。F2FS在SIT中為每一個Segment都維護了一個有效位圖（validity bitmap），一旦通過Section中的所有bitmap找到了該Section中所有Segment中所有的有效Block，F2FS就能夠從SSA中獲取這些Block的父Node Block。接著，F2FS就能夠將有效的Block全部遷移（migrate） 到log的其他空閑區域中。

這里有一個問題，到底移到哪一個log區域中呢？有整整6個Log區域呀，這該怎么權衡呢？

呵呵，應該只在Log Area也就是單一Zone里面移動吧……

是嗎？好像不是？

對于Background Cleaning，F2FS并不會引起移動有效塊的I/O。相反，F2FS將有效塊裝載到Page Cache中，然后將它們標記為Dirty。接下來，F2FS就將他們留在Page Cache中，等待內核工作進程將他們Flush到存儲器中。這種模式被稱為Lazy Migration，它不止減輕了對前臺應用I/O的影響，同時允許小的寫入（Small Write） 被合并起來。Background Cleaning在常規I/O或者Foreground Cleaning時不會工作。

Post-cleaning process：當所有有效塊都被遷移后，那個Victiom Section就會被標記為Pre-Free。當Checkpoint生成后，這個Section才變成一個Free Section，等待被重新分配。這個機制的原因是：如果一個Pre-Free Section在Checkpoint生成前就被當作空閑塊使用，那么當掉電時，文件系統可能會丟失在上一個Checkpoint時的數據。（因為Pre-Free Section已經被覆寫了。Brilliant！）

Adaptive Logging

The original LFS introduced two logging policies, normal logging and threaded logging. In the normal logging, blocks are written to clean segments, yielding strictly sequential writes. Even if users submit many random write requests, this process transforms them to sequential writes as long as there exists enough free logging space. As the free space shrinks to nil, however, this policy starts to suffer high cleaning overheads, resulting in a serious performance drop (quantified to be over 90% under harsh conditions, see Section 3.2.5). On the other hand, threaded logging writes blocks to holes (invalidated, obsolete space) in existing dirty segments. This policy requires no cleaning operations, but triggers random writes and may degrade performance as a result.

F2FS implements both policies and switches between them dynamically according to the file system status. Specifically, if there are more than k clean sections, where k is a pre-defined threshold, normal logging is initiated. Otherwise, threaded logging is activated. k is set to 5% of total sections by default and can be configured.

簡單來說，設定一個閾值，當空閑塊大于這個閾值時，F2FS啟用基于Append Logging的Cleaning回收機制，當空閑塊小于這個閾值時，如果再調用Cleaning，那么寫入效率會變得非常低下，于是直接采用Threaded Logging——直接寫到臟Segment的空閑Block中，就不采用Cleaning操作了。

Checkpoint And Recovery

無論何時，F2FS需要維護一個持續狀態事件：例如sync、umount以及Foreground Cleaning時，F2FS都會觸發一個檢查點，具體流程如下：

所有在Page Cache中的Dirty Node和Dentry Block被Flush；

F2FS暫停基本寫系統調用，例如：create、unlink以及mkdir；

文件系統的元數據、NAT、SIT以及SSA被寫入Flash特定區域；

F2FS向CP Area寫入Checkpoint包，包括了以下信息：

• Header and Footer： 分別被寫入包的開頭和結尾。F2FS在Header和Footer中維護版本號，該版本號在創建檢查點時遞增。在文件系統裝載時，版本號可以從兩個Checkpoint包中曲分最新的穩定包；
• NAT and SIT bitmaps：NAT和SIT bitmaps指明構成當前包的NAT和SIT的Block的集合；
• NAT and SIT journals： 包含了一小部分最近修改的NAT與SIT Entries，用于避免經常性的NAT和SIT更新；
• Summary blocks of active segments： 由內存中的SSA Block組成，這些內存中的SSA Block將來會被Flush到Flash的SSA Area中；
• Orphan Blocks： 保存孤兒節點信息。如果一個inode在它被關閉之前刪除了，例如：當兩個進程同時打開一個文件，然后其中一個進程刪除了這個文件，那么此時這個文件就被標記為孤兒節點，在突然斷電后，F2FS就可以成功恢復它；

回滾恢復（Roll-Back Recovery）

在突然掉電后，F2FS回滾到最近Checkpoint上。F2FS維護了兩個Checkpoint包，如果一個Checkpoint包的Header和Footer和另一個相同，則F2FS認為該Checkpoint包是有效的，否則，它會被丟棄。

同樣，F2FS同樣管理了兩組NAT和SIT的塊集合，由每個Checkpoint包的NAT和SIT bitmaps區分。當在更新檢查點時寫NAT或者SIT block時，F2FS將交替寫這兩組集合，然后將bitmap指向被最新的集合。

如果只有很少的NAT或者SIT Entries被經常更新，則F2FS將多次寫入4KB大小的NAT或者SIT Block。為了減輕負擔，F2FS在Checkpoint包中實現了NAT and SIT journal，這項技術減少了I/O的數量，以及更新檢查點的延遲。

在文件系統掛載恢復階段，F2FS通過Header和Footer搜索有效的Checkpoint 包。如果所有Checkpoint 包都有效，F2FS就選擇最新的一個包。一旦選擇了最近有效的包，F2FS將檢查是否存在孤兒節點。如果存在，F2FS將剪除這些孤兒節點指向的所有Data Block，然后將這些孤兒節點Free掉。接下來，F2FS在Roll-Forward Recovery成功完成后，通過指向NAT和SIT Blocks的bitmaps來開啟文件系統服務。

前滾恢復（Roll-Forward Recovery，類似強制刷新吧，不是很懂。。。感覺是針對數據庫的？？？Mayday Mayday /(ㄒoㄒ)/~~）

類似數據庫的應用時常向文件寫入小型數據并執行fsync來保證數據的持續性。一個支持fsync的簡單的方法可能是：觸發更新檢查點然后通過Roll-Back模型來恢復數據。然而，這個方法的性能十分低下，因為更新檢查點將導致所有無關的Node、Dentry Block都被寫入數據庫文件。

F2FS實現了一個高效的前滾恢復機制來提升fsync性能。關鍵思想是只寫Data Block以及這些Data Block的Direct Node Block，而不寫其他Node 或者F2FS元數據Block。為了在回滾到穩定的Checkpoint時選擇性地找到Data Block，F2FS在Direct Node Block中保留了一些特殊的標志位。

總結

以上是生活随笔為你收集整理的F2FS文件系统论文解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。