局部性和快速文件系统

type

status

date

slug

summary

FFS: 磁盘意识是解决方案

快速文件系统（Fast File System , FFS），其基本思路是让文件系统的结构和分配策略具有“磁盘意识”，从而提高性能。

通过保存文件与文件系统相同的接口（相同API，包括open()、 read() 等文件系统调用）。事实上，所有现代文件系统都遵循现有的接口（从而保持与应用程序的兼容性），同时为了性能、可靠性或其他原因，改变其内部实现。

柱面组

第一步就是更改磁盘上的结构。FFS将磁盘分为一些分组，称为组面组（cylinder group,而在有些OS上，称为块组， block group）。我们想象现在有10个柱面组的磁盘：

这些分组是 FFS 用于改善性能的核心机制。通过在同一组中放置两个文件，FFS 可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道。

因此FFS需要能够在每个分组中分配文件和目录。

在一个柱面组中，每个组中都有超级快（super block）的一个副本。我们还需要记录该组的inode 和数据块是否已经分配。每组的inode位图（ib)和数据位图(db)可以实现上述需求，分别针对每组中的inode 和数据块。位图是管理文件系统中可用空间的绝佳方法，因为很容易找到大块可用空间并将其分配给文件，这可能会避免旧文件系统中空闲列表的某些碎片问题。最后，inode 和数据块区域就像之前的极简文件系统一样。像往常一样，每个柱面组的大部分都包含数据块。

如何分配文件和目录

现在我们已经有了分组结构，FFS当前必须决定如何在磁盘上放置文件和目录以及相关的元数据，以提高性能—相关的东西放在一起。

首先FFS必须决定什么是“相关的”，并将它们放在同一区块内：

FFS找到分配数量少的柱面组和大量的自由inode，并将目录数据和inode放在该分组中。

对于文件，首先 FFS 确保将文件的数据块分配到与其inode相同的组中，从而防止inode和数据之间的长时间寻道。其次它将位于同一目录中的所有文件，放在它们所在目录的柱面组中。

策略文件的局限性

为了更好地理解这些推断方法是否有意义，我们决定分析文件系统访问的一些跟踪记录，看看是否确实存在命名空间的局部性。

进程SEEK跟踪，并分析目录树中不同文件的访问差距。例如：

如果打开文件 f，然后跟踪到它重新打开（在打开任何其他文件之前），则在目录树中打开的这两个文件之间的距离为零（因为它们是同一文件）。如果打开目录 dir 中的文件 f（即 dir/f），然后在同一目录中打开文件 g（即 dir/g），则两个文件访问之间的距离为1，因为它们共享相同的目录，但不是同一个文件。

下图展示了 SEEK 跟踪中所看到的局限性，针对SEER集群中所有工作站上的所有SEER跟踪。其中的 x 轴是差异度量值，y 轴是具有该差异值的文件打开的累积百分比。

大文件的特殊性

在 FFS 中，文件放置的一般策略有一个重要的例外，它出现在大文件中。如果没有特殊的规则，大文件将填满它首先放入的块组。但是这妨碍了随后的“相关”文件放置在该组块内，因此可能破坏文件访问得到局部性。

因此，对于大文件， FFS在将一定数量的块分配到第一个块组后，将文件的下一个“大”块放在另一个块组中。然后文件的下一个块放在另一个不同得到块组中。

以下为 FFS 没有大文件时的图景：

有了大文件时，文件以如下方式分别在磁盘上：

如果在磁盘上分散文件块又会损伤性能，特别是在顺序文件访问的相对常见的情况下。我们可用通过选择大块的大小来改善这一点。如果大块大小足够大，我们大部分时间仍然花在从磁盘传输数据上，而在大块之间寻道的时间相对较少。每次开销做更多工作，从而减少开销，这个过程称为摊销（amortization），即能够弥补性能的损伤。

FFS 采用基于 inode 本身的结构方法来计算跨组分布大文件：

前 12 个直接块与 inode 放在同一组中。每个后续的间接块，以及它指向的所有块都放在不同的组中。如果块大小为 4KB，磁盘地址是 32 位，则此策略意味着文件的每 1024个块（4MB）放在单独的组中，唯一的例外是直接指针所指向的文件的前 48KB。

磁盘驱动器的趋势是传输速率相当快，因为磁盘制造商擅长将更多位填塞到同一表面。但驱动器的机械方面与寻道相关，改善空间小。随着时间的推移，机械成本变得相对昂贵，因此，为了摊销所述成本，必须在寻道之间传输更多数据。

处理小文件

当许多文件大小为 2KB 左右时，使用 4KB 块虽然利用传输数据，但空间效率差。在典型的文件系统上，这种内部碎片（internal fragmentation）可能导致大约一半的磁盘浪费

FFS 引入子块（sub-block）来解决这些问题,这些子块有512字节，文件系统可以将它们分配给文件。当创建了一个小文件（比如大小为 1KB），它将占用两个子块，因此不会浪费整个 4KB 块。随着文件的增长，文件系统将继续为其分配 512 字节的子块，直到它达到完整的 4KB 数据。此时，FFS 将找到一个 4KB 块，将子块复制到其中，并释放子块以备将来使用。

通过上述方法，文件需要大量的额外工作。FFS 又通过修改libc库来避免这种异常行为，该库将缓冲写入，然后以 4KB 块的形式将它们发送到文件系统，从而在大多数情况下完全避免子块的特殊情况。

针对性能进行优化的磁盘布局。

通过每次跳过一块（在这个例子中），在下一块经过磁头之前，FFS 有足够的时间发出请求。它能够确定特定磁盘在布局时应跳过多少块，以避免额外得到旋转。这种技术称为参数化，因为 FFS 会找出磁盘的特定性能参数，并利用它们来确定准确的交错布局方案。

这种类型的布局只能获得 50%的峰值带宽，因为必须绕过每个轨道两次才能读取每个块一次。但是现代磁盘在内部读取整个磁道并将其缓冲在内部磁盘缓存中（由于这个原因，通常称为磁道缓冲区，track buffer）。然后，在对轨道的后续读取中，磁盘就从其高速缓存中返回所需数据。因此带宽的问题可以忽略了。

小结

FFS 的引入是文件系统历史中的一个分水岭，因为它清楚地表明文件管理问题是操作系统中最有趣的问题之一，并展示了如何开始处理最重要的设备：硬盘。

将磁盘当作磁盘。

阅读推荐

“Hardware Technology Trends and Database Opportunities”David A. PattersonKeynote Lecture at the ACM SIGMOD Conference (SIGMOD ’98) June, 1998 磁盘技术趋势及其随时间变化的简单概述。

FFS: 磁盘意识是解决方案

柱面组

如何分配文件和目录

策略文件的局限性

大文件的特殊性

处理小文件

小结

阅读推荐

Uonlra

Notion 交流频道

加入社群讨论分享