基于 NAND 的闪存设备被广泛地用在各种设备中，闪存具有先擦后写固有的限制，并且擦写寿命是有限的。通常将多个闪存芯片连接到一个控制器，这个控制器解决了闪存芯片的限制，提供了与传统块设备相同的外部接口。eMMC 和 SSD 等大多数闪存设备都采用了这种方案，与传统的磁盘相比，闪存设备没有机械装置，因此具有更低的访问延迟、更低的能耗、低噪声、抗摔等优点。
然而，在某些特殊的使用环境下，闪存芯片的缺点被显现出来。例如，频繁的随机写操作会使 SSD 产生内部碎片，导致性能下降一个数量级。产生性能下降的原因是，随机写操作使得闪存内部的数据页需要拷贝到其它位置，再进行擦除，因此也导致了设备寿命的显著下降。随机写的 I/O 模式在资源有限的设备上尤其常见，因为文件系统需要频繁触发 fsync 将内存缓冲区写回外存，而写回数据块的地址通常是随机的。因此，文件系统应该针对闪存设备这种特殊的 I/O 性质进行设计，以充分发挥闪存的性能。
日志式文件系统的结构可以缓解随机写模式的问题，但是它们没有考虑闪存设备的特性，在性能和寿命上不是最优的。因此，传统的针对硬盘的文件系统设计策略不能充分利用和优化闪存设备的使用。一些专门为闪存设备设计的文件系统通常采用日志式文件系统的结构，加入了一些对闪存特性的考虑，例如，将文件系统的数据块大小与闪存内部数据块大小对齐，并且将冷热数据分离存储等，这些文件系统在闪存设备上表现出了更好的性能。
本文主要根据 F2FS 的设计，介绍了闪存文件系统常见的几个设计要点。
闪存文件系统
日志式文件系统将所有的写操作组合成顺序的日志式结构写入外存，因此可以解决闪存随机写性能低下的问题。但是 LFS 的段清理操作对性能产生严重的影响，并且会降低闪存的寿命，因此针对 LFS 的改进都会考虑如何有效降低段清理的代价。另外，LFS 采用的传统的索引块文件结构会导致索引递归更新的问题，被称为“wandering tree problem”。大多数闪存文件系统都采用日志式文件系统的结构，并综合考虑闪存的 I/O 特性进行设计，本节主要讨论了闪存文件系统的设计要点，并概述了 F2FS 文件系统的组织结构。
日志式结构
文件系统的一个基本功能是为文件块分配一个逻辑数据块 LBA，文件系统对逻辑块的分配大致可以分为两种策略：原地更新（in-place-update）的策略和非覆盖（no-overwrite）的策略。采用原地更新的文件系统，例如，FAT32 和 ext4，将一个脏的文件块写回到它对应的逻辑块地址，就是说该逻辑块始终与这个文件块保持关联。因此，由底层闪存 FTL 的机制处理来处理写回同一个闪存块的冲突，这样就会导致出现之前提到的随机写的问题，严重影响闪存的性能。CFDC 是一种基于闪存的缓冲区管理方法，它在 LRU 基础上将缓冲区数据块按地址进行聚类，使得写回的数据具有更好的局部性，从而提高了闪存的性能。
与此同时，一些采用非覆盖策略的文件系统，例如日志式文件系统，将脏的文件块写入到新的逻辑块。因为没有写入相同块的冲突，每次文件块更新，FTL 收到的请求都是写入新的逻辑块。在文件系统层面，将原来的逻辑块标记为 dirty，之后进行统一的回收。
之前我们提到，在写请求大小是 SSD 组合块大小的倍数时，随机写可以达到与顺序写相同的吞吐量。为了利用这个重要的性质，闪存文件系统通常都采用日志式的结构，将文件层面的随机写转换为逻辑块地址层面的顺序写。因为每次都写入新的逻辑地址，SSD 并不会回收文件块原本对应的物理块，因此在写的过程中不会产生性能的下降。
存储布局
F2FS 的数据布局根据底层的闪存性质进行组织和管理，如图所示，F2FS 将整个卷划分为固定大小的段（segments），段是文件系统管理的基本单元。每个节（section）由连续的段组成，而一个区域（zone）是一些 section 的集合。F2FS 在若干个 zone 中以 segment 为单位分配存储块，并以 section 为单位进行回收。这些单元与底层的 FTL 操作单元进行对齐，以避免不必要的数据拷贝。F2FS 将整个空间划分为六个区域：
- Superblock（SB）存储了 F2FS 基本的分区信息和默认的参数，这些数据在格式化时被写入，并且通常不会改变。
- Checkpoint（CP）记录了文件系统的状态、位图、孤立的 inode 列表等信息。这些信息用于维持文件系统的一致性，并且可以在突然断电后进行恢复。
- Segment Information Table（SIT）包含了每个 segment 的信息，例如，可用的块数、数据块状态的位图等。在回收过程中，选取牺牲块和确定可用块的过程都需要 SIT 中记录的信息。
- Node Address Table（NAT）记录每个 node 块在主区域中的物理位置，维护了一个从 node 编号到物理地址的映射表。
- Segment Summary Area（SSA）存储主区域中每个块的信息，例如该块的 inode 节点编号等。在回收过程中，迁移可用数据块后要根据 SSA 的信息更新该数据块的父节点。
- Main Area 由 4KB 的块组成，数据块被分为两种类型，node block 和 data block。node 块包含 inode 或者数据块的索引，而数据块包含实际的目录或文件数据。一个 section 不会同时存储索引块和数据块。
文件结构
FLFS 将更新的数据和索引块写入新的空闲区域。如果一个叶数据块被更新了（重新写入其他位置），它的直接索引块也要被更新，更新的直接索引块同样被写入新的位置，这就导致它的间接索引块也被更新，这种递归的更新产生了一连串的写操作，这就是所谓的 wandering tree 问题。
为了解决这个问题，通常的做法是切断间接索引块和直接索引块之间的直接关联。F2FS 维护了一个 NAT 表，每个 node 块具有一个唯一的编号，NAT 表记录了每个 node 编号的实际物理地址。因此每个 inode 和间接索引中不再直接存储子索引块的物理地址，而是存储 node 的编号，这种称为基于指针的文件索引结构能很好地避免递归更新的问题，如图所示。在传统的 LFS 中，如果一个叶数据块更新，它的直接和间接索引块都会递归更新，而在 F2FS 中，只需要更新一个直接索引块以及该索引块的 NAT 表项，因为间接索引块中存储的是这个直接索引块的 node 编号，因为直接索引块的编号没有更改，所以间接索引块不需要更新。
每个文件的 inode 块包含了该文件数据块的直接指针以及索引块的指针，F2FS 支持内联数据，可以将小的数据直接存储在 inode 块中，减少了空间的需求并提升 I/O 性能。
冷热数据分离
在日志式文件系统中，当没有足够的空闲空间时，就会触发 cleaning 操作，将 section 中存活的数据拷贝出去，再按整个 section 进行擦除。因为 cleaning 过程涉及到读写存活数据块的操作，这成为日志式文件系统的一个主要延迟。
通常文件系统中的数据块具有不同的使用频率，当一个 section 中混合了不同频率数据时，就会增加回收代价。因为冷数据的更新频率比较低，那在 cleaning 进程开始时，冷数据很可能还是存活的，因此需要将这些冷数据迁移到新的位置。如果热数据和冷数据被分配在不同的 section 中，那热度较高的 section 中的数据块可能很快就失效了，同时热度较低的 section 中可能大多数块还是存活的。这样的结果就是，大多数的 section 是几乎是全满的或者全空的，可以很容易找到几乎全空的 section 进行清除，大大降低了需要迁移的数据量。
F2FS 维护了六个写操作的队列用于区分不同冷热程度的数据，并分别为 node 和 data 定义了三种级别的热度：hot、warm 和 cold，总结如表 1 所示。直接索引块比间接索引块定义的热度更高，因为我们认为直接索引块会更频繁的更新。间接索引块存储 node 编号，只有在一个 node 节点添加或删除时才会更新间接索引块，否则只需要更新 NAT 。目录的直接索引块和数据块与正常文件块的访问模式有明显的差别，因此它的热度被定义为 hot。如果一个数据块满足如下三个条件之一，那它的热度被定义为 cold：
- 在 cleaning 阶段被迁移的数据块：因为它们在之前的周期里存活了更长的时间，因此我们认为这些数据块在不久的将来还会继续存活。
- 用户标记为 cold 的数据块：F2FS 支持对文件设置扩展属性，允许用户将文件热度标记为 cold。
- 多媒体文件数据：多媒体文件块通常具有只读的性质，因此文件系统可以利用文件的扩展属性区分多媒体文件。
而在 SFS 文件系统中，数据块的热度不是固定不变的，文件系统统计每个文件块的使用频率，并定义了一个关于文件块频率的函数，该函数用于计算文件块的热度值。因为计算的热度是连续值的形式，因此首先要确定如何根据热度值进行分组的标准，分组的方式对区分冷热数据具有决定性的影响。一般有两种常见的划分方式，等深划分将整个区间换分为相等大小的子区间，而等宽划分使得每个分组内具有相同个数的数据块。
利用闪存设备的并行性，可以将多路数据同时写入，闪存文件系统可以维护多个写操作的队列，分别对应于不同的数据热度，在为写操作分配逻辑块时，根据它们的属性划分到对应的队列中。在每个写操作队列中，如果块数不能填满一个 segment，那这个队列需要等待之后的写操作加进来，直到填充满一个 segment，并按 segment 写回闪存。
空间回收
回收进程用于回收分散的和无效的块，从而保证有足够的空白区域为之后的写操作服务。因为回收操作在底层存储容量不足时不断发生，因此，限制回收操作的执行代价对日志式文件系统的性能尤其重要。在 F2FS 中以 section 为单位进行回收操作，并将回收分为两种不同的方式，前台和后台。前台回收进程只在空间不足时触发，而后台回收进程由系统定时启动执行。回收进程分为三个步骤进行：首先根据策略选取要被回收的 section，然后确定 section 中依然存活的数据，并将这些数据迁移到空白的位置，最后进行闪存块擦除操作。
回收进程首先要在非空的 section 中选择一个要被擦除的 section，称为 victim section。日志式文件系统有两种经典的策略：贪心策略和最优代价策略。贪心策略选取具有最少存活数据块的 section 作为牺牲者，即希望用最少的代价回收尽量多的空间。直观上，贪心策略可以最小化可用块的迁移代价。F2FS 中采用贪心法作为前台回收的策略，为了尽可能地减少可见的延迟。
然而，贪心策略在回收过程中没有考虑数据块的热度信息。经验上，冷数据在它失效之前会保持更长的时间，而热数据在很短的时间内就会失效，稍等片刻再进行回收就可以不用迁移数据。最优代价策略综合考虑了 section 的存活块数和年龄，section 的年龄由其中每个 segment 的年龄取平均值，segment 的年龄纪录在 SIT 中。最优代价策略根据年龄信息进一步区分了冷热数据，可以获得更好的性能，但值得注意的是，因为需要计算每个 section 的年龄，因此最优代价策略比贪心策略更加耗时。F2FS 采用了最优代价策略作为后台回收的方式。
选取被回收的 section 后，需要根据 SIT 表中的信息确定其中的存活块，并将这些存活块根据它们的属性添加到对应的写操作队列。如果一个队列中的数据量不足以填充 segment，写操作会被推迟，那这些没有被写回的存活页会产生丢失的风险。SFS 的做法是维护迁移块的记录，如果这些块没有被写回，那原始的数据块就不执行擦除操作。
写回策略
LFS 介绍了两种数据写回方式，normal logging 方法中，将数据转换为顺序的流写入空白的区域。即使用户提交了大量的随机写请求，这个过程也会将它们转换为顺序写的模式，前提是由足够的空闲空间。由于这种策略总是将数据写入空白区域，因此当空闲空间不足时将面临着严重的回收代价。而 threaded logging 方法将数据块写回到脏的 segment 的空洞中（淘汰的块），由 FTL 层处理相同地址的冲突，这种策略不需要额外的回收代价，但是会触发 SSD 的随机写的问题。
F2FS 同时采用了这两种写回策略，并根据文件系统的状态动态地切换两种策略。具体的设定一个阈值，如果可用空间小于这个阈值（通常是 5%），写回策略由 normal logging 切换为 threaded logging，因此可以避免严重的回收代价。
考虑 threaded logging 的随机写问题，日志式文件系统可以将数据写入任意的空洞，因此如果这些空洞的局部性比较好，就可以减轻随机写的代价。就是说应该在填满整个 segment 的空洞后再寻找其他脏的 segment，这样就保证了很好的局部性，而在原地写回的文件系统中就无法完成这样的操作。因此，F2FS 可以在维护代价过高的情况下放弃顺序写回方式而平滑地切换到 threaded logging 策略。
