快速文件系统（FFS）是一种用于UNIX操作系统的文件系统，最初由Marshall Kirk McKusick和William N. Joy在1984年开发。它是BSD操作系统中最常用的文件系统之一，也被许多其他UNIX操作系统所采用。
FFS的设计目标是提高文件系统的性能和可靠性。它使用了一些高级技术，如柔性块分配（Flexible Block Allocation，FBA）和多级索引（Multi-Level Indexing），以提高文件系统的性能和可靠性。FFS还支持快速文件系统快照（Fast File System Snapshot），可以在不影响文件系统性能的情况下创建文件系统的快照。
历史原因
在早期的UNIX系统中，UNIX“魔法师”Ken Thompson编写了第一个文件系统。我们称之为“老UNIX文件系统”，它非常简单，基本上，它的数据结构在磁盘上看起来像这样：
超级块(S)包含有关整个文件系统的信息：卷的大小、有多少inode、指向空闲列表块的头部的指针等等。磁盘的inode区域包含文件系统的所有inode。最后，大部分磁盘都被数据块占用。
这个老文件系统通的好处在于它很简单，支持文件系统试图提供的基本抽象：文件和目录层次结构。与过去笨拙的基于记录的存储系统相比，这个易于使用的系统真正向前迈出了一步。与早期系统提供的更简单的单层次层次结构相比，目录层次是真正的进步。
问题：性能不佳
这个老文件系统最大的问题是：性能很糟糕。更具Kirk McKusick和他在伯克利的同事的测量，性能开始就不行，随着时间的推移变得更糟，指导文件系统仅提供总磁盘带宽的2%！
主要问题是老UNIX文件系统将磁盘当成随机存取的内存。数据遍布各处，而不考虑保存数据的介质是磁盘的事实，因此具有实实在在的、昂贵的定位成本。例如，文件的数据块离其inode非常远，因此当读取inode后再读取文件的数据块时，就会导致昂贵的寻道，这种操作场景式很常见的。
更糟糕的是，文件系统最终会变得非常碎片化(fragmented)，因为空闲空间没有得到精心管理。空闲列表最终会指向遍布磁盘的一堆块，并且随着文件的分配，它们只会占用下一个空闲块。结果是访问一个连续文件时，需啊在磁盘上来回访问，从而大大降低了性能。
如下，假设以下数据块区域包含4个文件(A、B、C和D)，每个文件大小为两个块：
如果将B和D删除，则生成的布局为：
如你所见，可用空间被分成两块构建的两大块，而不是很好的连续4块。假设我们现在希望分配一个大小为4块的文件E:
你可以看到会发生什么：E被分散在磁盘上，因此，在访问E时，无法从磁盘获得峰值(顺序读写)性能。你首先读取E1和E2，然后寻道，再读取E3和E4。这个碎片问题一直发生在老UNIX文件系统中，并且会影响性能。这个问题正是磁盘碎片整理工具要解决的。它们将重新组织磁盘数据以连续放置文件，并未空闲空间成为一个或几个连续的区域，移动数据，然后重写inode等以反映变化。
另一个问题：原始块大小太小(512字节)。因此，从磁盘传输数据本质上是低效的。较小的块是好的，因为他们可以最大限度地减少内存碎片(internal fragmentation，块内的浪费)，但是由于每个块可能需要一个定位开销来访问它，因此传输不佳。
同时我们也发现了，在早期的计算机系统中，磁盘通常被视为一个简单的块设备，文件系统的设计往往只考虑了逻辑上的文件组织和管理，而没有考虑磁盘的物理结构和读写特性。这种设计方式可能会导致文件系统的性能和可靠性问题。我们可以总结如下问题。
关键问题：如何组织磁盘数据以提高性能
如何组织文件系统数据结构以提高性能？在这些数据结构之上，需要那些类型的分配策略？如何让文件系统具有“磁盘意识”？
FFS：磁盘意识是解决方案
为了解决上述老文件系统的问题，伯克利的一个小组决定建立一个更好的、更快的文件系统，他们聪明地称之为快速文件系统(Fast File System，FFS)。思路是让文件系统的结构和分配策略具有“磁盘意识”，从而提高性能。
FFS的设计理念是将磁盘视为磁盘，而不是将其视为一个简单的块设备。这意味着FFS的设计考虑了磁盘的物理结构和读写特性。这种设计方式为后来的文件系统设计提供了重要的借鉴和启示，现代的文件系统也都采用了类似的设计理念，将磁盘视为磁盘，以便更好地管理磁盘的读写操作，提高文件系统的性能和可靠性。
因此，FFS进入了文件系统研究的新时代。通过保持与文件系统相同的接口(相同的API，包括open()、read()、write()、close()和其它文件系统调用)，但改变内部实现，作者为新文件系统的构建铺平了道路，这方面的工作今天人在继续。事实上，所有的现代文件系统都遵循现有的接口(从而保持与应用程序的兼容性)，同时为了性能、可靠性或其它原因，改变其内部实现。
祖师结构：柱面组
第一步是更改磁盘上的结构。FFS将磁盘划分为一些分组，称为柱面组(cylinder group, 而一些现代文件系统，如Linux ext2和ext3，就称它们为块组，即block group)。因此，我们可以想象一个具有10个柱面组的磁盘：
这些分组是FFS用于改善性能的核心机制。每个柱面组包含一些扇区，可以存储文件和目录等数据，通过在同一组中放置两个文件，FFS可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道。
因此，FFS需要能够在每个组中分配文件和目录。每个组看起来像是这样：
我们现在描述一个柱面组的构成。出于可靠性原因，每个组中都有超级块(super block)的一个副本(例如，如果一个被损坏或划伤，你仍然可以通过使用其中一个副本来挂载和访问文件系统)。
在每个组中，我们需要记录组的inode和数据块是否已分配。每组的inode位图(inode bitmap, ib)和数据位图(data bitmap, db)起到了这个作用，分别针对每组的inode和数据块。位图是管理文件系统中可用空间的绝佳方法，因为很容易找到大块可用空间并将其分配给文件，这可能会避免就文件系统中空闲列表的某些碎片问题。
最后，inode和数据块区域就像之前的极简文件系统一样。像往常一样，每个柱面组大部分都包含数据块。
补充：FFS 文件创建
例如，考虑在创建文件时必须更新哪些数据结构。对于这个例子，假设用户创建了一个新文件/foo/bar.txt，并且该文件长度为一个块(4KB)。该文件是新的，因此需要一个新的inode。因此，inode 位图和新分配的 inode 都将写入磁盘。该文件中还包含数据，因此也必须分配。因此(最终)将数据位图和数据块写入磁盘。因此，会对当前柱面组进行至少 4 次写入(回想一下，在写入发生之前，这些写入可以在存储器中缓冲一段时间)。
但这并不是全部！特别是，在创建新文件时，我们还必须将文件放在文件系统层次结构中。因此，必须更新目录。具体来说，必须更新父目录 foo，以添加 bar.txt 的条目。 此更新可能放入 foo 现有的数据块，或者需要分配新块(包括关联的数据位图)。还必须更新 foo 的 inode，以反映目录的新长度以及更新时间字段(例如最后修改时间)。
总的来说，创建一个新文件需要做很多工作！也许下次你这样做，你应该更加心怀感激，或者至少感到惊讶，一切都运作良好。
策略：如何分配文件和目录
有了这个分组结构，FFS现在必须决定，如何在磁盘上放置文件和目录以及相关的元数据，以提高性能。基本的守则很简单：相关的东西放一起(以此类推，无关的东西分开放)。
因为，FFS首先要确定，该如何定义什么是“相关的”，并将它们置于同一个区块组内。相反，不相关的东西应该放在不同的块组中，为实现这一目标，FFS使用了一些简单的放置推断方法。
对于文件，FFS做两件事。首先，它确保(在一般情况下)将文件的数据块分配到其inode相同的组中，从而防止inode数据之间的长时间寻道(如在老文件系统中)。其次，它将位于同一目录中的所有文件，放在它们所在目录的柱面组中。因此，如果用户创建了4个文件，
/dir1/1.txt、/dir1/2.txt、/dir1/3.txt 和/dir99/4.txt，FFS会尝试将前3个放在一起(同一组)，与第四个远离(它在另外某个组中)应该注意的是，这些推断方法并非基于对文件系统流量的广泛研究，或任何特别细致的研究。相反，它们建立在良好的老式常识基础之上(这不就是CS代表的吗？)。目录中的文件通常一起访问(想象编译一堆文件然后将它们链接到单个可执行文件中)。因为它们确保了相关文件的寻道时间很短，FFS通常会提高性能。
测量文件的局部性
为了更好地理解这些推断方法是否有意义，我们决定分析文件系统访问的一些跟踪记录，看看是否确实存在命名空间的局部性。出于某种原因，文献中似乎没有对这个主题进行过很好的研究。
具体来说，我们进行了SEER跟踪，并分析了目录树中不同文件的的访问有多“遥远”。例如，如果打开文件f，然后跟踪到它重新打开(在打开任何其它文件之前)，则在目录树中打开的这两个文件之间的距离为零(因为它们是同一个文件)。如果打开目录dir中的文件f(即dir/f)，然后在同一目录中打开文件g(即dir/g)，则两个文件访问之间的距离为1，因为它们共享相同的目录，但不是同一个文件。换句话说，我们的距离度量标准衡量为了找到两个文件的共同祖先，必须在目录树上走多远。它们在树上越靠近，度量值越低。
下图展示了SEER跟踪中看到的局部性，针对SEER集群中所有工作站上的所有SEER跟踪。其中的x轴是差异度量值，y轴是具有该差异值得文件打开的累计百分比。具体来说，对于SEER跟踪(图中标记为“跟踪”)，你可以看到大约7%的文件访问是先前打开的文件，并且近40%的文件访问是相同的文件或同一目录中的文件(即0和1的差异值)。因此，FFS的局部性假设似乎有意义(至少对于这些跟踪)
有趣的是，另外25%左右的文件访问是距离为2的文件。当用户以多级方式构造一组相关目录，并不断在它们之间跳转时，就会发生这种类型的局部性。例如，如果用户有一个src目录，并将目标文件(.o文件)构建到obj目录中，并且这两个目录都是主proj目录的子目录，则常见访问模式是proj/src/foo.c后跟着proj/obj/foo.o。这两个访问之间的距离时2，因为proj是共同的祖先。FFS在其策略中没有考虑这种类型的局部性，因此在这种访问之间会发生更多的寻道。
为了进行比较，我们还展示了“随机”跟踪的局部性。我们以随机的顺序，从原有的SEER跟踪中选择文件，计算这些随机顺序访问之间的距离度量值。但是，因为最终每个文件共享一个共同的祖先(即根)，总会有一些局部性，因此跟踪可以作为比较点。
大文件例外
在FFS中，文件放置的一般策略有一个重要的例外，它出现在大文件中。如果不对大文件使用不同的规则，大文件将填满它首先放入的块组(也可能填满其它组)。以这种方式填充块组是不符合需要的，因为它妨碍了随后的“相关”文件放置在该块内，因此可能破坏文件访问的局部性。
因此，对于大文件，FFS执行以下操作。在将一定的块分配到第一个块组(例如，12个块，或inode中可用的直接指针的数量)之后，FFS将文件的下一个“大”块(即第一个间接块指向的那些部分)放在另一个块组中(可能因为它的利用率低而选择)。然后，文件的下一个块放入在另一个不同的块组中，依此类推。
让我们看一些图片，更好地理解这个策略。如果没有大文件例外，单个大文件会将其所有块放入磁盘的一部分。我们使用一个包含10个块的文件的小例子，来直观地说明该行为。
以下是FFS没有大文件例外的时的图景：
有了大文件例外，我们可能会看到像这样的情形，文件以大块的形式分布在磁盘上：
聪明的你可能会注意到，在磁盘上分散文件块会损害性能，特别是在顺序文件访问的相对常见的情况下(例如，当用户或应用程序按顺序读取块0~9时)。你想的是对的！确实会。我们可以通过仔细选择大块大小，来改善这一点。
具体来说，如果大块大小足够大，我们大部分时间仍然花在从磁盘传输数据上，而在大块之间寻道的时间相对较少。每次开销做更多工作，从而减少开销，这个过程称为摊销(amortization)，它是计算机系统中的常用技术。
举个例子：假设磁盘的平均定位时间(即寻道和旋转)是10ms。进一步假设磁盘以40MB/s的速率传输数据。如果我们的目标是花费一半的时间来寻找数据块，一半的时间传输数据(从而达到峰值磁盘性能的50%)，那么需要每10ms定位开销导致10ms的传输数据。所以问题就变成了：为了在传输中花费10ms，大块必须有多大？简单，只需要计算一下，特别是我们在磁盘章节中提到的量纲分析：
基本上，这个等式是说：如果你以40MB/s的速度传输数据，每次寻找时只需传输409.6KB，就能花费一半的时间寻找，一半的时间传输。同样，你可以计算达到90%峰值带宽的块大小(结果大约为3.69MB)，甚至达到99%的峰值带宽(40.6MB！)。正如你所看到的，越接近峰值，这些块就越大，如下图：
多级索引
但是，FFS没有使用这种类型的计算来跨组分布大文件。相反，它采用了一种简单的方法，这种方法称为多级索引(multi-level indexing)，基于inode本身的结构。前12个直接块与inode放在同一组中。如果块大小位4KB，磁盘地址是32位，则此策略意味着文件的每1024个块(4MB)放在单独的组中，唯一的例外是直接指针所指向的文件的前48KB。
我们应该注意到，磁盘驱动器的趋势是传输速率非常快，因为磁盘制造商擅长将更多位填塞到同一表面。但驱动器的机械方面与寻道相关(磁盘臂速度和旋转速度)，改善相当缓慢。这意味着随着时间的推移，机械成本变得相对昂贵，因此，为了摊销所述成本，你必须在寻道之间传输更多数据。
关于FFS的其它特性
FFS还引入了其它创新。特别是，设计人员非常担心存放小文件。事实证明，当时许多文件大小为2KB左右，使用4KB块虽然有利于传输数据，但空间效率却不太好。因此在典型的文件系统上，这种内部碎片(internal fragmenttaion)可能导致大约一半的磁盘浪费。
柔性快分配
FFS设计人员采用很简单的方案解决了这个问题。在FFS文件系统中，柔性块分配(Flexible Block Allocation，FBA)技术引入了子块（sub-block），这些字块有512字节，文件系统可以将它们分配给文件。文件系统可以将它们分配给文件。这样可以避免小文件占用整个块的情况，提高磁盘空间的利用率。
因此，如果你创建了一个小文件(比如大小位1KB)，它会占用两个子块(一个为512字节)，因此不会浪费整个4KB块。随着这个文件的增长，文件系统将继续为其分配512字节的子块，直到它达到完整的4KB数据。此时，FFS将找到一个4KB块，将子块复制到其中，并释放子块以备将来使用。
你可能会觉得这个过程效率很低，文件系统要做很多额外的工作(特别是执行复制的大量额外I/O)。你又对了！因此，FFS通常通过修改libc库来缓冲写入，并以4KB的形式将它们发送到文件系统，从而在大多数情况下完全避免了子块的特殊情况。从而在大多数情况下完全避免了子块的特殊情况。
标准与参数化放置
FFS引入了第二个巧妙方法，是针对性能进行优化的磁盘布局。那时候(在SCSI和其它更现代的设备接口之前)，磁盘不太复杂，需要主机CPU以更加亲力亲为的方式来控制它们的操作。当文件放在磁盘的连续扇区上时，FFS可能在某些情况下遇到问题。
如右图所示，在顺序读取时，可能会有问题。FFS首先发出一个请求，读取块0(图左)。当读取完成时，FFS向块1发出读取，但此时为时已晚：块1已经在磁头下方旋转，那么可能要等待一个完整的旋转延迟，才能读取到块1.
FFS使用不同的布局解决了这个问题，如图右所示。将连续的块间隔开，在下一个块经过磁头之前，FFS有足够的时间发出请求。实际上，FFS足够聪明，能够确定特定磁盘在布局时应跳过多少块，以避免额外的旋转。这种技术称为标准与参数化（Standard and Parameterized Placement)，因为FFS会找出磁盘的特定性能参数，并利用它们来确定准确的交错布局方案。
你可能会觉得，这个方案不是很好。因为这个布局方案只能获得50%的峰值带宽，因为你必须绕过每个轨道两次才能读取每个块一次。幸运的是，现代磁盘已经不存在这个问题，主要原因是：现代磁盘的传输速度比当时已经有很大的提升。另外它们可以在内部读取整个磁道并将其缓冲在内部磁盘缓存中(由于这个原因，通常称为磁道缓冲区，track buffer)。然后，在对磁道的后续读取中，磁道就从其高速缓存中返回所需的数据，而不需要再次读取了。因此，文件系统不再需要担心这些令人难以置信的低级细节。如果设计的当，抽象和更高级别的接口可能是一件好事。
FFS还增加了另一些可用性改进。FFS是允许长文件名的第一个文件系统之一，因此在文件系统中实现了更具有表现力的名称，而不是传统的固定大小方法(例如，8个字符)。此外，引入了符号链接的新概念。正如上一章讨论的那样，硬链接的局限性在于它们都不能指向目录(因为害怕引入文件系统层次结构中的循环)，并且它们只能只想同一卷内的文件(即inode号必须仍然有意义)。符号链接允许用户为操作系统上的任何其他文件或目录创建“别名”，因此更加灵活。FFS还引入了一个原子rename()操作，用于重命名文件。除了基本技术之外，可用性也让FFS拥有更强大的用户群。
提示：让系统可用
FFS 最基本的经验可能在于，它不仅引入了磁盘意识布局(这是个好主意)，还添加了许多功能， 这些功能让系统的可用性更好。长文件名、符号链接和原子化的重命名操作都改善了系统的可用性。虽 然很难写一篇研究论文(想象一下，试着读一篇 14 页的论文，名为《符号链接:硬链接长期失散的表 兄》)，但这些小功能让 FFS 更可用，从而可能增加了人们采用它的机会。让系统可用通常与深层技术创 新一样重要，或者更重要。
FFS 的引入是文件系统历史中的一个分水岭，因为它清楚地表明文件管理问题是操作系统中最有趣的问题之一，并展示了如何开始处理最重要的设备：硬盘。从那时起，人们开发了数百个新的文件系统，但是现在仍有许多文件系统从FFS中获得提示(例如，Linux ext2和ext3 是明显的知识传承)。当然，所有现代系统都要感谢 FFS 的主要经验：将磁盘当作磁盘。