揭開F2FS與FTL“剪不斷理還亂”的“愛恨交織”

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

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

FTL的地址映射方式

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

圖1 SAST映射數(shù)據(jù)搬移示例

日志結(jié)構(gòu)文件系統(tǒng)

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

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

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

空間布局和索引結(jié)構(gòu)

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

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

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

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

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

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

段摘要區(qū)Segment Summary Area (SSA)主區(qū)域所有數(shù)據(jù)塊的所有者信息（即反向索引），包括：父inode號和內(nèi)部偏移。SSA表項(xiàng)可用于搬移有效塊前查找其父親索引節(jié)點(diǎn)編號,

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

由于NAT的存在，數(shù)據(jù)和各級索引節(jié)點(diǎn)之間的“滾雪球效應(yīng)”被打破。如下圖所示：當(dāng)文件數(shù)據(jù)更新時，我們只需更新其直接索引塊和NAT對應(yīng)表項(xiàng)即可。其他間接索引塊不會受到影響。

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

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

垃圾回收和塊分配

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

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

F2FS展望

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

圖8 F2FS作者Jaegeuk Kim

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

參考文獻(xiàn)：

[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/