Locality and The Fast File System

"old UNIX file system" looked like this:

super block（S）: contains information about the entire file system
inode region: contains all the inodes for the file system
data region: contains user data

1. The Problem: Poor Performance

The problem: performance was terrible. The file system was delivering only 2% of overall disk bandwidth.

The main issue was that the old UNIX file system treated the disk like it was a random-access memory. For example, the data blocks of a file were often very far away from its inodes, thus inducing an expensive seek whenever one first read the inode and then the data blocks of a file.

Worse, the file system would end up getting quite fragmented, as the free space was not carefully managed.

when accessing E, you don't get peak (sequential) performance from the disk.

One other problem: the original block size was too small (512 bytes). 对于每个块而言，太小有利于减少块内部碎片化，但是不利于传输，块太小导致定位查找开销增加。

故关键问题为：如何组织磁盘数据去提升性能？

2. FFS：Disk Awareness Is The Solution

Fast File System（FFS）：简而言之，就是保持以前文件系统的原有接口（相同的APIs，包含open()、read()、write()、close()和其他的文件系统调用接口）但是改变内部实现。

3. Organizing Structure: The Cylinder Group

第一步就是改变磁盘结构。FFS将磁盘分成多个柱面组（cylinder groups）。单个圆柱体是硬盘驱动器不同表面上的一组磁道，这些磁道距驱动器中心的距离相同。

如下所示，显示了具有6个盘片的驱动器的四个最外轨道，以及一个由三个圆柱组成的圆柱组：

现代文件系统会导出块的逻辑地址空间，故无法为文件系统导出足够的信息，无法真正了解是否正在使用特定的柱面。

文件系统将驱动器组织成块组（block groups），每个块组为磁盘连续的空间。如下所示：每8个块分成一组

如果文件系统把两个文件放到同一个组，那么接连获取两个文件不会造成很长的寻道时间。

FFS里单个圆柱组如下所示：

FFS保留了超级块（S）的副本，故当一个超级快失效后，还有其他块可用；FFS需要追踪组中哪个索引节点和数据块已经被使用。

4. Policies: How To Allocate Files and Directories

为了提升性能，FFS在磁盘中放置文件、目录和相关元数据的原理非常简单：保持相关内容在一起（keep related stuff together）。为了达到这个目的，FFS利用了一些简单的布局试探法。

首先是目录的放置：找到分配的目录数量少和大量的空闲索引节点的柱面组，然后将目录数组和索引节点放入该组中。

对于文件：首先确保将文件的数据块与索引节点分配在同一组中，确保查找时间最小；然后将所有文件放在其所在目录的柱面组中的同一目录中。