F2FS文件系统架构与原理分析(四)——F2FS的目录结构与目录哈希

1目录（Directories）

LFS(Log-structured File System) 实际上对目录布局没有强加任何特殊的要求，因而访问 F2FS 文件系统的目录等同于访问其他文件系统的目录。目录的主要目的是提供更快速的文件名查找，为每个可使用 telldir() 报告的文件名提供稳定的地址。

原始的 Unix 文件系统支持256字节的文件名长度，使用与 Ext2 相同的目录机制——在布满目录项的文件中顺序遍历查找文件名。这种方法简单有效，但是对于大目录的扩展性不好。

多数现在主流文件系统如 Ext3，XFS 和 Btrfs 使用多种机制（包括 B-tree），有时通过哈希索引文件名。B-tree 的一个问题是节点（nodes）需要切分，这导致一些目录项在文件中频繁移动，这给 telldir() 提供文件名对应的稳定地址带来了额外的挑战。这大概就是 telldir() 经常被认为是不太好的接口的主要原因。

1.1 目录结构

一个目录项占据11 Bytes，也就是包含以下属性：

(1)    – hash     文件名的哈希值

(2)    – ino       inode 号

(3)    – len       文件名长度

(4)    – type     文件类型，如目录，符号链接，等等

一个目录项 block 包含214个目录项槽位(slot)和文件名，其中用一个 bitmap 表示每个目录项是否有效，1个目录项块占用 4 KB，结构如下：

Dentry block(4 Kb) = bitmap(27bytes) + Reserved(3bytes) + Dentries(11*214bytes) + filename(8*214bytes)

1.2 目录哈希

F2FS 使用一些连续搜索和哈希方法提供一个简单的搜索机制，合理高效，简单实现提供稳定的 telldir() 的地址。F2FS 文件系统的大多数的哈希算法代码都是参考 Ext3，但是删除（忽略）了使用每个目录作为seed。F2FS 的 seed 使用一个秘密的随机数，以确保满足使用的哈希值在每个目录中都不同，因而是不可预测的。使用这样的 seed 可以给哈希冲突提供保护。虽然哈希冲突在现实中是不可避免的，但使用这种方式可以很容易避免这种冲突，这种删除(忽略) 使用每个目录作为seed 带来的效果很意外。

很容易想到目录结构是一系列的哈希表连续地存储在一个文件中，每个哈希表具有一组相当大的 buckets。查找过程从第一个哈希表到下一个哈希表，在每一个阶段对合适的bucket 执行线性查找，直到找到文件名或者查找到最后的那个哈希表。在查找过程中，在合适的 bucket 中的任意空闲空间都会被记录，以防需要创建文件名的时候用到。

F2FS 对目录结构实现了多级哈希表，每一级都有一个使用专用数字的哈希 bucket 的哈希表，如下所示。注意，“A(2B)”表示一个哈希 bucket 包含两个数据块。

----------------------

A : bucket    哈希bucket

B : block     数据块

N : MAX_DIR_HASH_DEPTH   最大目录哈希层级

----------------------

level #0:   A(2B)

level #1:   A(2B) - A(2B)

level #2:   A(2B) - A(2B) - A(2B) - A(2B)

     .       .       .       .       .

level #N/2:  A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)

     .        .       .       .       .

level #N:   A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B)

 

所有的哈希表按如下方式组织：第一个哈希表恰好有1个 bucket，大小是两个数据块，因而对于最开始的少数几百个目录项，使用简单的线性搜索。第二个哈希表有2个 bucket，第三个哈希表有4个 bucket，第四个哈希表有8个 bucket，然后是16 个 bucket，……，直到第31个哈希表有大约10亿（2^30）个 bucket，每个 bucket 都是两个数据块大小。从第32个哈希表开始，都与第31个哈希表一样，但是不同的是每个 bucket 的大小是四个数据块。哈希表中 block 个数与 buckets 个数的确定方法是：

F2FS 在目录中查找文件名时，首先计算文件名的哈希值，然后在 level #0 中扫描哈希值查找包含文件名和文件的 inode 的目录项。如果没有找到，F2FS 在 level #1 中扫描下一个哈希表，用这种方式，F2FS 以递增的方式扫描每个 level 的哈希表（如果上一 level 中没有查找到结果），在每个 level 中，F2FS 仅需要扫描一个bucket，而该 bucket 的号是由文件名的哈希值与该 level 中的 buckets 个数的相除取余得到的。也就是每个 level 中需要扫描的一个 bucket 由下式确定的，查找复杂度是 0：

bucket number to scan in level #n = (hash value) % (# of buckets in level #)

所以哈希表的最终结果就是需要线性搜索几百个目录项，如果目录项很大的话，需要通过几个数据块的搜索。搜索长度仅随着目录文件中目录项的个数对数级增长，所以容易扩展。这种搜索当然比完全的线性搜索算法要好，但是看起来好像比实际需要做的工作更多。但是它保证了每次加入或删除一个文件名的时候仅需要更新一个数据块，因为目录项没有移动，目录项在文件中的偏移对于 telldir() 来说就是一个稳定的地址，这是非常有意义的特性。

在创建文件的情况下，F2FS 在哈希表的buckets 中找到该创建文件名对应的空的连续的槽位(slots)（这一句的原文是：F2FS finds empty consecutive slots that cover the file name）。F2FS 自哈希表的 level #0 到level #N 从哈希表中给搜索该空闲的槽位，与查找文件系统中已有文件的查找操作一样。