Home [论文阅读] F2FS: A New Filesystem for Flash Storage
Post
Cancel

[论文阅读] F2FS: A New Filesystem for Flash Storage

Posted 2023/09/29
By Caturra
17 min read

前言

首先F2FS也不算新文件系统，迄今已超过10年了，但不妨碍它在闪存设备领域的流行

然后我其实没怎么看论文，而是听作者的演讲，也没人规定论文一定要看文字对吧

背景：为什么需要F2FS

主要是随机写对flash设备不利。随机写的性能低于顺序写是常识了，但还有一个原因是影响设备寿命，这是由flash的物理特性决定的弊端，需要FTL完成写前擦除操作，随机写就是放大弊端

进一步的考虑就是要做一个面向顺序写（具有磨损均衡特性）的文件系统，而这就是F2FS

设计思路与主要特性

  • Flash-friendly on-disk layout
  • Cost-effective index structure
  • Multi-head logging
  • Adaptive logging
  • fysnc() acceleration with roll-forward recovery

Layout

怎样才算是闪存友好的硬盘布局？

layout

作者给的答案是按上图一样布局就是友好的：它考虑了闪存感知（flash awareness）和低清理成本（clean cost reduction）

闪存感知指的是文件系统匹配闪存物理特性：

  • superblock metadata存放在一起（且是头部），以提高局部性和并行性
  • main area的起始地址对齐与zone大小，这是考虑了FTL的工作特征
  • 以section为单位的文件系统GC

清理成本降低则是使用Multi-head logging实现冷热数据分离，见图中Hot / Warm / Cold

另外补充一些硬盘布局的说明，以下部分来自kernel文档：

  • F2FS将整个分卷都划分为若干segment，每一个segment都是2MB大小
  • F2FS按三级划分：section包含若干segment，zone包含若干section，但默认是1:1:1关系
  • F2FS按功能划分6个area：从super block到main如图所示
  • 如上面所说，main area按zone对齐，同时check point按segment对齐
  • 除了super block以外，其它的area都具有多个segment

这6个area存储以下信息：

  • Superblock：基本的分区信息以及F2FS的默认参数。它具有2个备份以避免文件系统崩溃
  • CP：文件系统信息，NAT/SIT的bitmap，orphan inode，以及active segment的summary entry
  • SIT：segment信息，比如valid block数目，（main area的）block对应的valid bitmap
  • NAT：映射main area中所有node block的地址
  • SSA：summary entry，这里指的是main area中block对应的归属关系（parent node / offset等）
  • Main area：文件和目录信息，以及它们的索引信息

这里有个问题：为什么需要三级划分（zone-section-segment）？我个人理解是zone的引入是考虑FTL识别冷热数据的辅助单位（见下方Multi-head logging章节）；而section则是一个文件系统GC时选用的单位（performs “cleaning” in the unit of section. …identify a victim selection，见下方Cleaning章节）；而segment是基本管理单元（allocates storage blocks in the unit of segments），这可能是出于F2FS仍作为块设备文件系统的适配；这三种的单位的大小选值都需要考虑FTL硬件特征

Index structure

作者通过对比LFS来体现F2FS的索引效率优势

lfs-index-structure LFS

f2fs-index-structure F2FS

* SB = super block
* CP = check point

作者指出，LFS有2个问题：

  • Update propagation（Wandering tree）：即使只想更新一个block，内部也需要更新更多的intermediate block（见红色⚡标记）
  • One big log：不管什么东西都走到同一个log里面，不区分block的特征

f2fs-multi-head

而F2FS则分别解决这两个问题：

  • 使用NAT（node address table）来处理wandering tree：通过一个大表来直接将node block id翻译到物理地址，避免访问indirect pointer block。在上图的场景中，不需更新inode和indirect pointer block（因为indirect pointer block记录node id，而direct pointer block记录block address）
  • 使用multi-head log来替代one big log：见上表，按类型和温度分为6种log。区分node和data是因为node的更新频率更高于data；两种类型在内部也细分不同的温度，一些准则是direct比indirect热、dentry比user file热

Multi-head logging?

上面已经提了Multi-head logging的冷热分离思路，而作者在8:06对multiple log仍有补充，但我听不清楚作者的具体表态，似乎是在讨论这种冷热分离对于硬件层面FTL的关联：即使有multiple log，但是FTL mapping并不能得知这种关系，即使F2FS冷热分离，到最后FTL mapping仍然是混在同一个erase block中存放的，这种node block和data block混在一块的现象称为zone-blind allocation。作者假定F2FS是zone-based mapping，FTL会将不同的log放到不同的区域。我认为这里的意思是分离数据的粒度是要按zone来划分的，这样才能避免FTL mapping后导致混到一块

Cleaning

GC加速的诀窍是section按照FTL GC单位的大小进行对齐。简单来说就是避免文件系统与FTL层面的不一致，其实也没啥好说的，文件系统会做GC清理数据，但是FTL可能会保留，不对齐的话就是两个层面互不搭配造成性能浪费

cleaning

具体流程如图，清理是可以前台（高效贪心）执行，也可以后台（成本最优）执行：

  • 贪心和最优指的是找出victim section的算法策略
  • 贪心算法尝试找出含最少数目valid block的section，通过控制迁移block成本以减少前台延迟
  • 最优算法除了像贪心一样考虑利用率以外，还需要参考section的「老化」程度（age）。SIT会记录last modified的时间点，而这个时间的平均值就是一个section的「年纪」

Adaptive logging

而清理会在老化（高占用、多碎片）时花费更多的时间，为了降低成本引入了adaptive logging。具体来说，就是在不同的场合下使用不同的写策略：

  • 当文件系统只剩5%的free section时，使用threaded logging
  • 否则使用append logging
  • 对于node，不管空间大小总是使用append logging

threaded logging是重新使用已经写过的segment，因此是随机写行为，但并不需要清理操作；而append虽然是顺序写行为，但是空间不足时仍需清理，此时会是更严重的随机写行为。这也是为什么使用动态写策略的原因

Recovery

recovery

* SPO = Sudden Power Off

F2FS使用check point来实现文件系统的一致性，避免宕机导致文件系统损坏。当调用sync()、umount()或者前台GC时，F2FS会触发check point

简单来说，check point就是一种shadow copy（不被用户感知的备份），其备份会交替放置于CP area的#1和#0部分，check point内容包含NAT/SIT journaling，避免直接写入NAT/SIT block。提供了必要的信息后，要执行recovery就是获取最新的check point，然后回滚（roll-back recovery）到对应的时间点

roll forward

虽然使用check point来实现fsync()是一种可行的思路，但是成本是相当的高。为了减少fsync()的执行成本，F2FS还引入了前滚（roll-forward recovery）操作来替代check point的回滚操作。它的思路是只更新对应的direct node block和data block（其中direct node block打上FSYNC标记）。在执行recovery时，则通过标记好的block来重做一遍写操作

Benchmark

benchmark部分主要对标ext4，粗略的负载结论如下：

  • 按设备来看，SATA SSD有2.5倍提升，PCIe SSD有1.8倍提升
  • 按应用来看，SQLite有2倍提升，iozone有3.1倍提升

但这些数据距离现在年代差异较大，参考价值不高（你也可以在这里得到较新的民间数据）。这几年按前司的经验来看，移动设备不同场合下与ext4互有胜负

另外作者在演讲中也暗示了，F2FS这么厉害是因为它很懂FTL的特征（甚至能用某种stream interface控制FTL的行为）。为什么懂呢？因为作者是三星员工，而测试设备的FTL就是三星自己造的，能不懂吗。这也意味着你放到其它厂商不同固件的设备，不一定能达到上面跑分这么夸张的差距

总结就是，即使你用了看似开源且一模一样的代码，自研与非自研之间，实则存在着一堵高墙

References

FAST ‘15 - F2FS: A New File System for Flash Storage - YouTube

This post is licensed under CC BY 4.0 by the author.
Contents