F2FS (Flash Friendly File System) 是專門針對SSD、eMMC、UFS等閃存設備設計的文件系統。由三星工程師Jaegeuk Kim于2012年10月發布到Linux社區，并于2012年12月進入Linux 3.8 內核主線。和UBIFS、JFFS2等文件系統不同，F2FS并不直接面向裸NAND閃存設計，而是和其他通用文件系統一樣基于塊設備層接口實現。既然如此，為什么說F2FS是針對SSD、EMMC、UFS等閃存設備設計呢？另一方面SSD、eMMC、UFS等擁有FTL（Flash Translation Layer）的閃存存儲已經對外提供了通用塊設備接口，是否真的需要針對性地設計一個文件系統呢？F2FS的“Flash Friendly”體現在哪些方面呢？請跟隨本文對F2FS的設計實現做詳細拆解，揭開F2FS與FTL“剪不斷理還亂”的“愛恨交織”。

F2FS繼承了日志結構文件系統的衣缽，使用異地更新的數據寫入方式化隨機為順序。同時改善了日志結構文件系統的一些已知問題，如滾雪球效應和高清理開銷。而FTL為了對上隱藏NAND閃存無法覆蓋寫的特性（先擦后寫），其內部實現也采用了類似的日志結構寫入方式。從軟件模塊化設計的角度看，兩個層次的相近冗余設計似乎并不合理。然而存在即合理，F2FS實際上是摸準了FTL的軟肋：那就是由于缺少上層（系統層、應用層）信息，FTL并不能很好的實現冷熱分離、做到高效垃圾回收、減少寫放大。同時FTL承載了太多目標：地址映射、磨損均衡、壞塊管理等等，以及一些器件廠商無法言說的原因導致將FTL上移到軟件層或是提供地址映射表等接口困難重重。因此即使擁有FTL，SSD、eMMC、UFS等設備也是需要一個針對性設計的文件系統來實現性能和壽命的優化。
F2FS雖然基于通用塊設備層接口實現，但并不像通用文件系統一樣無差別的對待機械磁盤和閃存盤，在設計上是”flash-awared”。根據閃存內部結構和閃存管理機制(FTL)，F2FS可通過多個參數配置磁盤布局、選擇分配和回收單元大小從而適配不同實現的閃存存儲設備。為方便理解F2FS，我們先簡單介紹下FTL的地址映射方式和日志結構文件系統，然后從空間布局和索引結構入手建立F2FS的基本概念，進而深入到冷熱分離、垃圾回收、塊分配等細節中去。

FTL的地址映射方式

FTL(Flash Translation Layer)的本職工作是完成Host端邏輯地址到Flash側物理地址的映射。需要地址映射的原因是閃存只能異地更新，為了對上支持數據塊原地更新則需要通過地址轉換實現。由于閃存先擦后寫、擦寫有次數限制（壽命）、使用過程中會不斷出現壞塊（塊壽命不同）等特性，FTL還需具備垃圾回收、磨損均衡、壞塊管理等十八般武藝。閃存內部的基本存儲單位是Page（4KB）,N個Page組成一個Block。這里主要介紹下邏輯地址LPN（Logical Page Number）到物理地址PPN（Physical Page Number）的映射方式：
塊級映射：將塊映射地址分為兩部分：塊地址和塊內偏移。映射表只保存塊的映射關系，塊內偏移直接對應。映射表比較小，需要內存（RAM）少。但無法很好的處理隨機寫，容易產生頻繁的有效數據搬移和塊擦除操作。
頁級映射：映射表維護每個頁的映射關系，這種方式靈活，能有效減少數據搬移。缺點是映射表很大（每個表項內容為PPN以4字節計算，128GB的閃存存儲需要128GB/4KB*4B=128MB大小的內存保存映射表），約占存儲容量的千分之一。
混合映射：主要思路是針對頻繁更新的數據采用頁級映射，很少更新的數據采用塊級映射。其中采用Log Structed思想的混合映射將存儲分為數據塊（Data Block）和日志塊（Log Block）。數據塊用于存儲數據，采用塊級映射，日志塊用于存儲對于數據塊更新后的數據，采用頁級映射。混合映射是低端SSD、eMMC、UFS廣泛采用的映射方式。根據日志塊和數據塊的對應關系又可以分為全相關映射（FAST）、塊相關映射（BAST）、組相關映射（SAST）等等。下圖是SAST映射的一個示例：2個日志塊對應4個數據塊，當日志塊用完時需要通過搬移有效數據回收日志塊。對于順序寫場景，最好情況下日志塊對應位置記錄了數據塊的更新，則可以無需搬移數據，直接將日志塊作為新的數據塊，數據塊進行擦除操作作為新的日志塊。對于大量隨機寫場景，則需要將日志塊和數據塊中的有效數據搬移到空閑塊的對應位置作為新的數據塊，然后擦除原日志塊和數據塊。

圖1 SAST映射數據搬移示例

日志結構文件系統

日志結構文件系統,Log Structured File System（注意：不是Journaling File System。Journaling File System是指在磁盤特定區域記錄所有寫入動作以便在需要時回溯和恢復，如：EXT4）思想的提出非常早，可以追溯到1992年時任UC Berkeley計算機系教授的John Ousterhout和他的學生Mendel Rosenblum發表的論文“The Design and Implementation of a Log-Structured File System”。John Ousterhout還是強大的Tcl語言（Tool Command Language，讀：tickle，不是家電品牌哦）的發明者，就是下圖這位白眉老爺爺。

圖2 Tcl、LFS作者John Ousterhout
日志結構文件系統將所有的更改以日志式的結構連續的寫入磁盤，以此加速文件寫入和崩潰恢復。日志中包含索引信息，文件可以被高效的讀出。為了快速的寫入需要保留大塊的空閑區域，可以將日志分成多個固定大小的連續空間——段（segment），在空閑區域不足時通過在碎片化的段中搬移有效數據回收新的連續空間。文章中還介紹了基于日志結構文件系統理念實現的Sprite LFS，較當時的UNIX文件系統FFS在小文件隨機寫上性能提升一個數量級。即使去除垃圾回收的開銷，仍可以利用70%的磁盤帶寬。日志結構文件系統如此優秀的寫入性能不是沒有代價的，如何高效的進行垃圾回收保持較高的寫入性能特別是剩余空間較少、碎片化嚴重后的性能一直是眾多日志結構文件系統致力于解決的問題。
下圖展示了一個日志結構文件系統基本的索引結構和空間布局，以及數據更新方式。超級塊Super Block（SB）自不必說，用于保存文件系統的基礎信息。檢查點Checkpoint（CP）則是指文件系統某一時點所有文件系統有效數據、索引結構一致完整的記錄。創建檢查點通常分兩步：1.落盤所有文件數據、索引、inode表、段使用情況表，2.在固定的檢查點區記錄所有有效的inode表和段使用情況表地址以及時間戳等。為了應對檢查點過程中的系統崩潰，實際有兩個檢查點區交替更新。由于時間戳是檢查點最后更新的內容，每次重啟后只需選擇最新的檢查點區即可保證有效性。在恢復到檢查點后，還可根據日志記錄繼續前向恢復（roll-forward）數據。F2FS就針對單個文件的fsync實現了前向恢復能力，fsync時只需落盤文件數據和其直接索引。
除了超級塊和檢查點是保存在固定位置的，其他元數據和數據都是異地更新的日志。以更新一個文件的內容為例：先寫入文件數據內容，再更新各級索引塊，最后還要更新Inode Map。這種更新數據帶來的索引數據更新問題被形象的稱為“滾雪球效應”（英文語境中為：Wandering Tree），這也是日志結構文件系統的另一大問題。

圖3日志結構文件系統索引結構和數據更新示意圖
接下來的部分，我們先看F2FS如何在空間布局和索引結構上解決“滾雪球”效應，再看基于空間布局的冷熱分離和垃圾回收算法如何減少回收代價以及塊分配策略對碎片化后寫性能的改善。

空間布局和索引結構

F2FS的空間布局在設計上試圖匹配閃存存儲內部的組織和管理方式。如下圖所示，整個存儲空間被化分為固定大小的Segment。Segment是F2FS空間管理的基本單元，也確定了文件系統元數據的初始布局。一定數量連續的Segment組成Section,一定數量連續的Section組成Zone。Section和Zone是F2FS日志寫入和清理的重要單元，通過配置合適的Section大小可以極大地減少FTL層面垃圾回收的開銷。

圖4 F2FS空間布局
整個存儲空間被劃分為6個區域：

超級塊（SB）包含基本分區信息和F2FS在格式化分區時確定不可更改的參數

檢查點（CP）保存文件系統狀態，有效NAT/SIT（見下文說明）集合的位圖，孤兒inode列表（文件被刪除時尚有引用無法立即釋放時需被計入此列表，以便再次掛載時釋放）和當前活躍段的所有者信息。和其他日志結構文件系統一樣，F2FS檢查點時某一給定時點一致的文件系統狀態集合——可用于系統崩潰或掉電后的數據恢復。F2FS的兩個檢查點各占一個Segment，和前述不同的是，F2FS通過檢查點頭尾兩個數據塊中的version信息判斷檢查點是否有效。

段信息表Segment Information Table（SIT）包含主區域（Main Area，見下文說明）中每個段的有效塊數和標記塊是否有效的位圖。SIT主要用于回收過程中選擇需要搬移的段和識別段中有效數據。

索引節點地址表Node Address Table（NAT）用于定位所有主區域的索引節點塊（包括：inode節點、直接索引節點、間接索引節點）地址。即NAT中存放的是inode或各類索引node的實際存放地址。

段摘要區Segment Summary Area (SSA)主區域所有數據塊的所有者信息（即反向索引），包括：父inode號和內部偏移。SSA表項可用于搬移有效塊前查找其父親索引節點編號,

主區域 Main Area由4KB大小的數據塊組成，每個塊被分配用于存儲數據（文件或目錄內容）和索引（inode或數據塊索引）。一定數量的連續塊組成Segment，進而組成Section和Zone（如前所述）。一個Segment要么存儲數據，要么存儲索引，據此可將Segment劃分為數據段和索引段。

由于NAT的存在，數據和各級索引節點之間的“滾雪球效應”被打破。如下圖所示：當文件數據更新時，我們只需更新其直接索引塊和NAT對應表項即可。其他間接索引塊不會受到影響。

圖5 F2FS索引結構
這里通過一個文件查找的小例子展示F2FS是如何工作的，假設要查找 “/dir/file”大致步驟如下：1）從NAT中獲取根目錄“/”的地址并讀取,2）在根目錄的數據塊中查詢目錄項“dir”對應的inode號，3）通過NAT獲取inode號對應的地址，4）讀取“dir”的inode塊，5）在目錄“dir”的數據塊中查詢目錄項“file”的inode號，然后重復類似3）和4）步的操作獲取“file”的inode塊。然后即可對該文件進行所需的操作，如下圖所示文件數據可由inode中的文件索引獲取。F2FS的inode多級索引結構類似EXT3，并沒有EXT4的extent結構。這也是日志結構文件系統的普遍選擇，因為考慮到垃圾回收過程對inode內部索引的改變，固定層次的索引可以避免extent區間范圍變化導致索引存儲空間變大的尷尬問題。F2FS最多有3級間接索引，單文件大小最大可達約3.94TB。因為數據塊地址采用4字節存儲，F2FS可支持的最大分區大小是16TB。從目前使用場景看，這不會成為明顯限制。另外，F2FS支持inline data（數據直接存儲在inode中），小文件大小最大可達約3.4KB，在Android大量小文件場景中對存取空間占用和性能有一定優化。

圖6 F2FS的inode索引結構
為了減少垃圾回收的開銷，F2FS采用了多日志頭的記錄方式實現冷熱數據分離。如下表所示，將數據區劃分為多個不同冷熱程度的Zone。如：目錄文件的inode和直接索引更新頻繁計入熱節點區，多媒體文件數據和回收中被搬移的數據計入冷數據區。冷熱分離的目的是使得各個區域數據更新的頻率接近，存儲空間中各個Section/Zone的有效塊數量呈binomial分布（即：冷數據大多數保持有效因而無需搬移，熱數據大多數更新后處于無效狀態只需少量搬移）。目前F2FS的冷熱分離還較為簡單，結合應用場景有很大的優化空間。
表1 F2FS不同類型數據冷熱劃分

垃圾回收和塊分配

F2FS的垃圾回收Garbage Collection（GC）分為前臺GC和后臺GC。當沒有足夠空閑Section時會觸發前臺GC，內核線程也會定期執行后臺GC嘗試清理。另外F2FS也會預留少量空間，保證GC在任何情況下都有足夠空間存放搬移數據。GC過程分三步：1）搬移目標選擇，兩個著名的選擇算法分別是貪心和成本最優（cost-benefit）。貪心算法挑選有效塊最少的Section，一般用于前臺GC以減少對IO的阻塞時間。Cost-benefit算法主要用于后臺GC，綜合了有效塊數和Section中段的年齡（由SIT中Segment的更新時間計算）。該算法的主要思想是識別出冷數據進行搬移，熱數據可能再接下來一段時間被更新無需搬移，這也是進行動態冷熱分離的又一次機會。2）識別有效塊并搬移，從SIT中可以獲取所有有效塊，然后在SSA中可以檢索其父親節點塊信息。對于后臺GC，F2FS并不會立即產生遷移塊的I/O，而只是將相關數據塊讀入頁緩存并標記為臟頁交由后臺回寫進程處理。這個方式既能減少對其他I/O的影響，也有聚合、消除小的分散寫的作用。3） 后續處理，遷移后的Section被標記為“預釋放”狀態，當下一個檢查點完成中Section才真正變為空閑可被使用。因為檢查點完成之前掉電后會恢復到前一個檢查點，在前一個檢查點中該Section還包含有效數據。
當空閑空間不足時，F2FS也不是“一根筋”的繼續保持日志寫的方式（Normal Logging）。直接向碎片化的Segment中的無效塊寫入數據是日志結構文件系統的另一個日志策略（Threaded Logging），又被稱為SSR（Slack Space Recycling）。SSR雖然變成了隨機寫，但避免了被前臺GC阻塞。同時通過以貪心方式選擇做SSR的Section，寫入位置仍然有一定的連續性。

圖6 F2FS的垃圾回收和空間分配

F2FS展望

F2FS從問世至今曾不被看好，某乎歷史上有很多對各個手機廠商在F2FS上謎一樣操作的疑問，如：“為什么三星發布的f2fs文件系統而自己的旗艦機都不使用這一文件系統？”，“F2FS文件系統既然被華為證實很好用，其他廠商為何不跟進？”。如今這些疑問都可畫上句號，谷歌2018年在自家的Pixel 3手機上使用F2FS并推薦Android Go項目（低內存和存儲容量配置的入門級設備）使用F2FS以改善器件壽命，三星在2019年自家旗艦上已經開始使用F2FS，目前很多手機廠商也都紛紛開始使用F2FS。
回首F2FS發展歷程（放個馬后炮），所有玩家的選擇都是從商業利益出發：文件系統需要多年打磨才能達到穩定商用的程度，三星發布F2FS時深知這一點，通過開源借助社區力量補齊F2FS短板不可謂不“老謀深算”。華為“正面剛”則是希望借助新技術打造品牌競爭力，F2FS之外還有方舟編譯器、EROFS等等。何況還有F2FS作者Jaegeuk Kim坐鎮，就是下圖中這位大兄弟。其實從Jaegeuk Kim的工作履歷（三星->摩托羅拉->華為->谷歌）也可以看出F2FS不斷前進的路線，他不遺余力的面向Android平臺推廣也起到了相當程度的助力——F2FS多年來不斷完善補齊特性，由于沒有歷史包袱大刀闊斧地針對Android平臺優化。如：原子寫特性提升SQLite數據庫性能（DELETE等模式），優化discard下發機制和策略減少卡頓等。

圖8 F2FS作者Jaegeuk Kim

展望F2FS的未來，可以看到社區的新特性（如：online resize，冷數據壓縮等）在不斷推出，且都能帶來Android用戶體驗的優化，而其成熟度和穩定性也在不斷提升。應用場景上，Android之外，疊瓦式磁記錄盤SMR（Shingled Magnetic Recording）有望成為F2FS的又一用武之地。SMR由于磁盤設計上盤片磁道部分重疊部分存儲空間只能順序寫，F2FS作為日志結構文件系統已有相應方案能很好的支持這類Zoned Block Device。限于篇幅，本文不再一一展開分析。

參考文獻：

[1] Lee et. al, F2FS: A New File System for Flash Storage, FAST ‘15

[2] Rosenblum et. al, The Design and Implementation of a Log-Structured File System, SOSP ‘92

[3] Jaegeuk Kim, Flash-Friendly File System (F2FS), Korea Linux Forum(KLF) 2012

[4] SMR介紹，https://zonedstorage.io/getting-started/smr-disk/