F2FS文件系统架构与原理分析(三) ——文件索引树

时间:2021-11-01 10:01:53

文件(Files)、索引节点(Inodes)、数据块索引(Indexing

1. 文件索引树结构

大多数现代文件系统都喜欢使用 B-trees 或类似的结构来管理索引(index)以定位文件中的 blocks。大多数文件系统中通过使用“extents”来减少文件数据块的总索引大小。F2FS 不采用 B-tree 结构管理索引,也不使用extents减少文件数据块索引的大小(虽然F2FS为每个节点(node)维护一个extent作为提示)。

2. 索引节点

管理数据位置的关键数据结构是“node”,与传统文件系统相似,F2FS 使用三种 nodeinode,直接 node,间接 nodeF2FS 分配4 KB 的空间给一个 inode,其中包括929个数据块索引指针,两个一级索引块(直接 node )指针,两个二级索引块(间接 node )指针,以及一个三级索引块(二级间接 node)指针。一个一级索引块(直接 node )包含1018个数据块指针,一个二级索引块(间接 node )包含1018个一级索引块(直接 node )指针,一个三级索引块(二级间接 node)包含1018个二级索引块(间接 node )指针。因此一个文件的最大大小是:

4 KB * (929 + 2*1018 + 2*1018*1018 + 1018*1018*1018) := 3.94 TB

3. 文件数据块索引

F2FS 使用索引树(如原始Unix文件系统和Ext3的索引树)索引数据块。Inode中包含了文件开始的一部分的数据块的地址列表,然后一些地址用于间接索引块以及二级和三级间接索引块。Ext312个直接索引地址以及三个间接索引块(一级、二级、三级)。F2FS 929个直接索引地址,2个一级间接索引块,2个二级间接索引块,1个三级间接索引块。允许寻址接近4TB的文件,也就是最大文件系统的1/4大小。

F2FS文件系统架构与原理分析(三) ——文件索引树

按大家最熟悉的Ext2Ext3的索引方式看,F2FS的索引树就是如下的结构:

F2FS文件系统架构与原理分析(三) ——文件索引树

4. 文件索引树对F2FS的意义

但是这种索引树机制有一定的代价——这也是其他文件系统抛弃这种索引方式的主要原因——但是这种方式对 LFS 却有好处。因为F2FS不使用 extents ,任意给定文件的索引树是固定的而且大小已知。这意味着,当数据块由于 cleaning 操作需要转移数据时,不可能因为可用 extens 发生改变而导致索引树变得更大(原来文件中每个 extent 很大,一个文件的索引树仅仅用少数几个 extents 就可完全表示,而新的存储部分每个可用 extent 都很小,要存储原来的文件就需要更多的 extents,导致文件的索引树变大)的情况产生——这可能会导致一种尴尬的情况产生就是 cleaning 的目的本来是要释放空间,而现在索引树变大却导致空间变小了。Logfs 文件系统也因为相同的原因,使用了许多相同的编排处理方式。

显然,所有这些需求都要求 F2FS  inode  Ext3 inode要大许多。因为Copy-on-write 不适用于小于块大小的对象,因而 F2FS 中每个 inode 占用的空间大小是一个 4 KB 的块,该 4 KB 的空间中提供了大量的空间用于索引。甚至提供空间存储(基本的)文件名,或者名字之一,以及其父节点的 inode 号,这简化了在文件系统 crash 恢复过程中近期创建的文件的恢复操作,减少了为保证文件安全需要写入的数据块的数量。

5. 加速文件查找的Extent

Inode 中包含了一个 extent,它总结了索引树的某些部分,它说明该文件的某些范围的blocks在存储上是空间连续的,并给出该范围的地址。F2FS 文件系统尝试在此处表示文件中最大的 extent,使用其加速地址查找。例如,通常情况下文件是连续写入且无任何明显的暂停,这样可能的结果是整个文件构成一个 extent,使得没有必要进入文件的索引树查找。

6. NAT解决wandering Tree问题

任何基于 Copy-on-write 技术的文件系统的一个缺点在于,无论何时要改写一个数据块,该数据块的地址就会因为数据重写到其他位置而发生改变。然后,在索引树中该块的父节点也因此必须重写到其他位置,如此往复下去直到重写操作传播到索引树的根。LFS logging 特性意味着在恢复过程中向前回滚可以重建近期对索引树的修改,因而所有这些修改不必立即写到磁盘(只是写到 log 中),但是这些修改最终还是会写到磁盘的,这就将更多的工作丢给 cleaner 去做。

这是 F2FS 为了方便而使用其底层 FTL 去处理的另一个区域。“元数据”区域("meta" area)中的内容是一个 NAT——Node Address Table(节点地址表)。这里的节点是指 inode 和间接索引块,以及用于存储扩展属性的数据块。当 inode 的地址存储在目录中,或者索引块存储在一个 inode 中或者其他的索引块中的时候,它存储的不是(存储的内容所在的)地址,而是其在 NAT 中的偏移。实际的(存储内容的)块地址是存储在 NAT 中对应的偏移处。这意味着当一个数据块被写入,仍然需要更新和修改指向该数据块的节点,但是修改该节点仅需更新对应的 NAT 项。NAT 是元数据的一部分,NAT 使用两个位置(two-location)Journaling(依靠FTL实现写聚合),因而不需要进一步的索引。

7. Inline技术支持情况

F2FS 目前不使用小文件内嵌(Inline)技术。针对这一技术的实际情况是:暂时还不支持 Inline 技术,但是很容易实现加入这一技术,并且这一技术迟早会加入到 F2FS 中。

8. 时间分辨率

很不幸,F2FS 没有足够空间存储64位的时间戳,也就是最小时间分辨率不是纳秒(ns),而是以秒(s)为时间分辨率。这可能导致2038问题,但时间戳分辨率问题应该会在未来的版本中解决。