F2FS

F2FS（Flash-Friendly File System）是一種快閃記憶體檔案系統，主要由金載極（김재극）在三星集團研發，適合Linux內核使用。

此檔案系統起初是為了NAND快閃記憶體的存儲設備設計（諸如固態硬碟、eMMC和SD卡），這些設備廣泛存在於自行動裝置至伺服器領域。

三星應用了日誌結構檔案系統的概念，使它更適合用於儲存設備。

## 特性

- 多頭日誌（Multi-head logging）
- 對目錄項的多層哈希表
- 靜態/動態冷熱數據分離
- 自適應記錄方案
- 可配置操作單元
- 雙檢查點
- 回滾和前滾恢復
- Heap-style塊分配
- TRIM/FITRIM支持
- 聯機的文件系統/文件碎片整理
- 內聯xattrs/數據/目錄
- 脫機filesystem check（檢查和修復不一致）)
- 線性一致性
- 文件系統級加密
- 脫機調整大小
- 內部定期數據刷新
- 範圍緩存

## 設計

### 磁碟上布局

F2FS將整個卷分成多個段（segment），每個段固定為2 MB。一個節（section）由連續的段組成，一個區（zone）由一組節組成。默認情況下，節與區被設置為相同的大小，但使用者可以用`mkfs`輕鬆修改大小。

F2FS將整個卷劃分為六個區域，除了超級塊（superblock）以外的所有區都由多個段組成，如下所述。

超級塊（Superblock，SB）：超級塊位於分區起始處，共有兩個副本以避免文件系統損壞。它包含基本的分區資訊和一些默認的F2FS參數。

檢查點（Checkpoint，CP）：檢查點包含文件系統資訊，有效NAT/SIT集的位圖，孤立inode列表，以及當前活動段的摘要條目。

段信息表（SIT）：段信息表包含主區域塊的有效塊數量和有效位圖。

節點地址表（NAT）：節點資訊表主區域節點塊的地址表。

段摘要區（SSA）：段摘要區包含的條目包含主區域數據和節點塊的所有者資訊。

主區域（Main Area）：主區域包含文件和目錄數據及其索引（indices）。

為了避免文件系統與快閃記憶體之間的對齊錯誤，F2FS將CP的起始塊地址與段大小對齊。它還通過在SSA區域中預留一些段來將「主區」起始塊地址與區的大小對齊。

### 元數據結構

F2FS使用檢查點方案來維護文件系統的完整性。在掛載時，F2FS首先嘗試掃描CP區域來查找最後的有效檢查點數據。為了縮短掃描時間，F2FS只使用CP的兩個副本。其中一個總是指示最後的有效數據，這被稱為影子副本機制。除了CP之外，NAT和SIT也使用影子副本機制。為了保證文件系統的一致性，每個CP指向的NAT和SIT副本都是有效的。

### 索引結構

關鍵的數據結構是「節點」。與傳統的文件結構類似，F2FS有三種類型的節點：inode，直接節點，間接節點。F2FS將4 KB分配給一個inode塊，其中包含923個數據塊索引（data block indices），兩個直接節點指針，兩個間接節點指針，以及一個double間接節點指針，如下所述。一個直接節點塊包含1018個數據塊索引，而間接節點塊包含1018個節點塊索引。因此，一個inode塊（即一個文件）涵蓋：

```
4&nbsp;KB × (923 + 2×1018 + 2×1018<sup>2</sup> + 1018<sup>3</sup>) = 3.94&nbsp;TB
```

注意，所有節點塊都經NAT映射，因此每個節點的位置都經NAT轉換。為了緩解漫遊樹問題，F2FS能夠切斷葉數據寫入引起的節點更新傳播。

### 目錄結構

一個目錄條目（dentry）占用11個字節，由以下屬性組成。

hash｜文件名的散列值

ino｜Inode號碼

len｜文件名長度

type｜文件類型，如目錄、符號連結等。

一個目錄條目塊由214個目錄條目槽及文件名組成。有一個位圖用於記錄每個目錄條目是否有效。一個目錄條目塊占用4 KB，結構如下：

```
目录条目块 (4 K) = 位图 (27 字节) + 保留 (3 字节) +
                      目录项 (11 * 214 字节) + 文件名 (8 * 214 字节)
```

F2FS為目錄結構實現了多級散列表，每一級有一個包含專用散列桶數的散列表，如下所示。「A(2B)」表示桶包含2個數據塊。

項：A表示桶（bucket）

B表示塊（block）

N表示目錄散列最大深度（MAX_DIR_HASH_DEPTH）

```
level #0    A(2B)
level #1    A(2B) - A(2B)
level #2    A(2B) - A(2B) - A(2B) - A(2B)
    ...
level #N/2  A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)
    ...
level #N    A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B)
```

當F2FS在一個目錄中找一個文件名時，首先計算出該文件名的散列值，然後F2FS掃描級別#0的散列表一查找由文件名及其inode編號組成的目錄條目。如果未找到，F2FS繼續查找級別#1的散列表。F2FS通過此方法逐級掃描由1至N的每層散列表。在每一層中，F2FS只需掃描由以下等式確定的一個桶（bucket），因此展現出 O(log(# of files)) 的複雜度。

```
 级别#n中要扫描的桶（bucket）数 = (散列值) % (级别#n中的桶数)
```

在創建文件時，F2FS找到一個能涵蓋文件名的空的連續槽。F2FS以同樣的方式由1至N查找各級散列表中的空槽。

### 默認的塊分配

在運行時，F2FS在「主要區域：」內管理六個活動日誌：熱/暖/冷節點和熱/暖/冷數據。

熱節點｜包含直接的目錄節點塊。

暖節點｜包含除熱節點塊以外的直接節點塊。

冷節點｜包含間接節點塊。

熱數據｜包含目錄條目塊。

暖數據｜包含除冷熱數據塊以外的數據塊。

冷數據｜包含多媒體數據或遷移的數據塊。

基於日誌的文件系統（LFS）有兩種空閒空間管理方案：穿插記錄（threaded log）與複製並壓縮（copy-and-compaction）。後者也稱為清理（cleaning），很適合有良好順序寫入性能的設備，因為空閒空間總用於寫入新數據。但它會在發生高利用率時遭遇「清理」的開銷。穿插記錄則受到隨機寫入性能的影響，但沒有「清理」過程。F2FS採用混合方案，默認採用「複製並壓縮」，但根據文件系統的狀態將策略動態變更為「穿插記錄」方案。

為使F2FS與基於快閃記憶體的存儲保持一致，F2FS以一個節（section）為單位分配一個段（segment）。F2FS預期節的大小與FTL中的垃圾收集單元大小相同。為考慮FTL中的映射粒度，F2FS將活動日誌的每個節分配給儘可能多的不同區域。FTL可以根據其映射粒度將活動日誌數據寫入一個分配單元。

### 清理流程

F2FS在需要時和後台閒置時進行清理。按需清理在沒有足夠的空閒分段（segments）服務VFS調用時觸發。後台清理器由一個內核線程執行，在系統空閒時觸發清理作業。

F2FS支持兩種受者選擇策略：貪婪、成本效益演算法。在貪婪演算法中，F2FS選擇有最小有效塊數的受者段。在成本效益演算法中，F2FS根據段的年齡和有效塊數量選擇受者段，以解決貪婪演算法中存在的日誌塊抖動問題。F2FS使用貪婪演算法進行按需清理，後台清理器則使用成本效益演算法。

為識別受者段中的數據是否有效，F2FS管理了一個位圖，其中用一個位元表示一個塊的有效性，覆蓋主區域所有塊的位元流組成了該位圖。

## 基本資料

- 開發者：三星電子、摩托羅拉移動和華為
- 全稱：Flash-Friendly File System
- 發布：2012-12-20
- 發布：Linux內核 3.8
- 目錄內容：多級哈希表
- 文件分配：位圖（可用空間）、表
- 最大文件尺寸：3.94TB
- 最大文件數量：取決於卷大小
- 最長文件名：255位元組
- 最大卷容量：16TB
- 日期記錄：修改 (mtime), 屬性修改 (ctime), 訪問 (atime)
- 日期解析度：1 ns
- 屬性：POSIX、擴展屬性
- 文件系統權限：POSIX、ACL
- 透明壓縮：否
- 透明加密：是
- 作業系統：Linux