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

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

前言

首先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