文件系统五十年：1984年的文件系统发展

50 Years in Filesystems: 1984

Source | HN Comments

1984年，BSD Unix的快速文件系统（FFS）问世，解决了传统Unix文件系统在吞吐量、分配和局部性方面的不足。FFS基于柱面组优化磁盘布局，将元数据和数据更紧密结合，并引入大块、小片段和尾部打包等技术。它还改进了inode编号、文件名长度、符号链接、rename系统调用和配额等。FFS显著提升了性能，但仍是非日志文件系统，存在目录条目搜索效率低等问题。Linux的ext2文件系统借鉴了FFS的设计。

@isotopp@infosec.exchange image Kristian Köhntopp - 2023年5月6日 a featured image

这是系列文章的第二部分。第一部分是“1974 ”。

进步有时很难看到，特别是当你参与其中或者亲身经历过的时候。通常，如果你比较现代的教育材料和所讨论的问题与旧的材料，就更容易看到进步。然后寻找推动变革的研究论文和来源。

在 Linux（以及一般的 Unix）中，这很容易。

1984年——BSD快速文件系统

最初的 Unix 文件系统运行良好，但也有大量明显的缺点。BSD Unix 致力于解决这些问题，这在 Leffler、McKusick 等人所著的“The Design and Implementation of the 4.3BSD UNIX Operating System ”一书中有所记载。

更简洁但也更学术的讨论可以在 1984 年的经典论文A Fast File System for UNIX 中找到，该论文列出了 Marshall McKusick、Bill Joy（当时在 Sun）、Samuel Leffler（当时在 LucasFilm）和 Robert Fabry 作为作者。该论文承诺重新实现 Unix 文件系统，以实现更高的吞吐量、更好的分配和更好的引用局部性。

硬件

现在是 1984 年。4.3BSD 的目标计算机是桌面和机柜工作站。这些机器具有 32 位数据寄存器和 32 位地址寄存器。

外部数据和地址总线大小各不相同：早期的 68k CPU 具有较小的总线，但在 1984 年，Motorola 68020 首次亮相。它是第一个提供具有完整 32 位宽度的总线的 68k，预算约为芯片上的 20 万个晶体管。后来，68030 集成了 MMU（以前是一个单独的芯片），而 68040 也集成了 FPU（同样是以前是一个单独的芯片）。

早期的 Sun 工作站，Sun-3 系列，采用了这些 CPU。但是 Sun 从实验性的 Berkeley RISC 系统中获取了设计，并在 1986 年发布了带有 SPARC 架构 RISC 芯片的 Sun-4 系列。SPARC 架构并非没有妥协，但非常可行，并且一直持续开发到 Oracle 收购 Sun 之后，Oracle 随后杀死了 SPARC，后来还杀死了 Itanium CPU 架构。

Curt Schimmel 讨论了 SPARC 在 MMU、寄存器和内存访问设计中所做的权衡，以及为什么它们有意义。请参阅 UNIX Systems for Modern Architectures 。

在此期间，在 1985 年，MIPS 架构首次亮相，这是另一个 RISC CPU 架构系列。它也从完全 32 位的系统类型开始，并在 SGI 工作站中得到应用。

HP 还有另一种 RISC 类型的 CPU，PA-RISC，这是他们“Spectrum”研究计划的成果，于 1986 年上市（后来被 Intel 失败的 Itanium 所取代）。

系统先驱 DEC 本身拥有 VAX，这是一款带有 CISC CPU 的 32 位机柜计算机，自 1977 年以来就存在。直到 1992 年，他们才采用 RISC，但随后完全采用 64 位 Alpha AXP (“DEC Alpha”) 架构。虽然有趣，但这并没有持续多久：随着 1998 年出售给 Compaq，CPU 停止生产，IP 于 2001 年出售给 Intel。

一般来说，1984 年的工作站类型系统的内存容量在较低的两位数 MB 范围内，并且以两位数的 MHz 系统时钟运行。

4.3BSD 的快速文件系统

传统文件系统的缺点

32 位的 VAX 系统被用于典型的 1980 年代工作站工作，包括图像处理或 VLSI 芯片设计等。在这些系统上，最初的 Unix 文件系统在跟上文件大小、I/O 速度和简单文件数量方面显示出结构性问题。此外，微小的 512 字节 I/O 大小大大降低了磁盘子系统的性能。

该论文提到了文件系统元数据在文件系统前端与文件系统后端实际数据的严格分离。

一个 150 MB 的传统 UNIX 文件系统由 4 MB 的 inode 组成，后面跟着 146 MB 的数据。这种组织将 inode 信息与数据隔离；因此，访问文件通常需要从文件的 inode 到其数据的长寻道。单个目录中的文件通常不会在 4 MB 的 inode 中分配连续的槽，导致在对目录中多个文件的 inode 执行操作时，访问许多非连续的 inode 块。

这定义了 BSD FFS 的一个主要目标：更好的文件系统布局，将元数据和数据更紧密地结合在一起，将单个目录中的文件更紧密地存储在一起，并防止文件碎片化成只能低效加载的小片段。

碎片：最初，创建了四个文件，每个文件使用 2 个块。然后删除文件 B 和 D。然后，三块大小的文件 E 回收了可用空间，该文件存储在非相邻的块中。这会导致小的磁盘寻道和缓慢的 I/O。

另一个既定目标是增加磁盘块大小。更大的磁盘块通过两种方式提高吞吐量：

更大的磁盘块提供更大的 I/O 单元，因此在单个 I/O 操作中传输更多数据。
更大的磁盘块还允许文件系统在间接块中存储更多的文件指针，从而大大减少了间接块的访问次数。如果间接块未缓存在文件系统缓冲区缓存中，这主要是一个问题。

该论文引用了已经经过少量优化的传统 Unix 文件系统的吞吐量约为理论最大值的 4%，这是非常糟糕的。这主要归因于碎片、文件中相邻块的非连续存储。早在 1976 年就提出的碎片整理被认为是一个不可行的想法而被放弃。作者的目标是找到一种首先合理放置文件的解决方案。

BSD FFS 创新

Cylinder Groups 和理解 CHS

BSD FFS 了解硬盘的物理布局，包括柱面、磁头和扇区 (CHS)。它将磁盘划分为柱面组，即所有磁盘磁头的相邻磁道。

当磁盘旋转时，各种磁盘磁头像梳子一样伸入盘片堆栈中。每个磁头在磁盘上标记一个磁道，该磁道由控制器硬件细分为物理磁盘块。所有磁头标记的所有磁道共同形成一个柱面。柱面组是一组连续的柱面。（图片：OSTEP ，第 3 页）

每个柱面组都成为传统 Unix 文件系统的迷你版本，其中包含超级块的副本、其自己的本地 inode 区域以及本地 inode 和块使用位图。位图的使用也是新颖的，因为它们取代了传统文件系统中使用的空闲列表。由于文件系统具有有关 CHS 布局的信息，因此它还确保超级块并非总是放置在每个副本的同一盘片上，从而尝试使文件系统更好地防止硬盘故障。

题外话：RAID 和 Berkeley 的其他努力

RAID 论文几年后才发表，但根据 Katz 的说法也是在 Berkeley 开发的，在同一时间段内，即 1983/1984 年。

Katz 还提到，当时 Stonebraker 也在，从事 Ingres（Postgres 的前身）的工作，并指出他对低提交延迟的需求推动了通过 FFS 和后来的 RAID 改进磁盘带宽的尝试。然而，我们今天所知的 RAID 分类法的认真工作直到 1987 年才开始。

许多初创公司和存储公司都将 RAID 论文用作其开发的基础，其中包括 NetApp 和 EMC（通过 Data General 的 Clariion 磁盘阵列）

BSD FFS 不仅了解磁盘的 CHS 几何形状，还了解处理器速度和磁盘旋转速度。这使其可以配置并将交错因子记录在超级块中，以优化磁盘 I/O 吞吐量。

硬盘连续旋转，但 CPU 需要时间来设置下一次传输。在此期间，磁头可能已经移动到下一个块开始边界之后，现在系统需要等待一个完整的旋转才能写入。使用适当的交错因子，相邻编号的块不会相邻地存储在磁盘上，而是将其他块交错在中间。这使 CPU 有足够的时间来思考和设置下一个块传输。

CPU 速度越快，所需的交错因子越低。

一旦硬盘以集成控制器出售，开始谎报其 CHS 几何形状，并最终随着线性块地址 (LBA) 的接管，所有这些优化都相对较快地变得无关紧要。但在 10 到 15 年的时间里，这提供了不错的性能优势。

大块、小片段和尾部打包

在内部，FFS 使用至少 4 KB 大小的逻辑块。任何具有至少 4 KB 块大小的东西都可以创建大小为 4 GB 的文件，最多具有两个级别的间接寻址。

大块可以加快 I/O 速度，但它们也会带来存储开销，因为文件的大小会以块的大小增长。由于 FFS 中的逻辑块由多个物理块组成，因此 FFS 引入了片段的概念来公开较小的内部物理块。通过尾部打包，多个文件的末尾可以一起存储在同一个逻辑块中，仅使用尽可能多的物理块。

需要额外的逻辑来防止缓慢增长的文件经历逐个片段增长和不断重新布局的阶段。为了克服这个问题，空间被预先分配给完整的逻辑块，并且尾部打包仅在文件关闭时取消预分配时才会发生。

长寻道布局策略

BSD FFS 引入了许多布局策略，这些策略控制着新目录、新文件的放置以及大型文件的处理。全局策略主要关注选择合适的柱面组来放置数据，而本地策略则处理柱面组内的放置。

新的文件系统布局具有柱面组。每个柱面组都有自己的 inode 表，以及用于 inode 和块的空闲空间位图。文件系统的目标是防止碎片。

当然，在某些情况下这是不可能的：例如，如果一个柱面组的大小为 512 MB，并且要写入一个大于 512 MB 的文件，它将使用该柱面组中的一个 inode，但所有可用的空闲块都将消失。如果要将第二个文件放置到此柱面组中，可以使用该 inode，但该文件的数据块需要放置在其他地方——这是不可取的。

最好强制进行长寻道，即从一个柱面组切换到下一个柱面组，用于大型文件。文件系统可以从每兆字节的文件大小强制执行这样的长寻道中获利。这将均匀地从一个柱面组到下一个柱面组使用空闲块，同时在每个柱面组中为其他文件留下一些空闲块。

当然，这会故意对文件进行碎片整理，但也要确保碎片足够大，以便允许大型文件 I/O。只有当碎片太小而无法有效读取时，碎片整理（文件中块的非相邻放置）才真正是一个性能问题。

目录布局策略

同一目录中的文件经常一起使用。将同一目录中的所有文件一起放置在同一柱面组中很有用。

当然，完成此操作后，还需要将不同的目录放入不同的柱面组中，以确保均匀使用可用的文件系统空间。这意味着一个 shell 脚本，例如

#! /usr/bin/bash
for i in $(seq -w 1 10)
do
 touch file$i
 mkdir dir$i
done

将创建十个名为 fileXX 的文件，这些文件都将放置在与当前目录相同的柱面组中。

它还将创建当前目录的十个子目录，名为 dirXX。如果可能，它们中的每一个都将放置在不同的柱面组中。FFS 将选择具有高于平均数量的空闲 inode 且其中已存在的目录数量最少的柱面组。

柱面组中 inode 的实际选择是“下一个可用”，非常简单。但这没有问题，因为整个柱面组 inode 表适合 8-16 个块。

对于数据块的放置，会投入大量精力来寻找旋转最佳块，给定此机器所需的交错因子。

BSD FFS 需要始终在文件系统中提供一些可用空间。如果文件系统填充超过 90%，则其许多算法会退化为传统文件系统的性能。

其他更改和改进

BSD FFS 还删除了传统文件系统附带的几个限制。

长 Inode 编号和块地址

例如，Inode 编号现在是 32 位数字。这会将每个文件系统可能的文件数从 64 K 增加到 4 G。inode 的大小增加了一倍：现在强制为 128 字节大小（带有 20 个未使用的字节）。此外，磁盘块地址现在是 4 个字节。在 4 KB 的块大小下，这足以容纳 4 G 个块，或者最大 16 TB 的文件系统大小。文件长度记录在一个 quad 中，允许超过 4 G 的单个文件大小。

Inodes 现在包含 12 个直接块和三种类型的间接块。在 4 KB 的块大小下，这对于每个间接块来说都很好，为 1024 个块地址，从而导致每个文件 12 + 1024 + 1024^2 + 1024^3 = 1074791436 个块，或者略高于 4 TB 的最大文件大小。

Unix 用户 ID 和组 ID 仍然限制为一个短，限制了每个系统的用户和组的数量为 64 K。

即使 inode 中的时间类型仍然限制为 4 个字节，也已为 8 字节的时间戳预先分配了空间。

长文件名

传统的文件系统具有固定 16 字节长度的目录槽，其中 2 个字节用于 inode 编号，14 个字节用于文件名。

BSD FFS 定义了一个更复杂的目录条目结构。单个条目包含一个 4 字节的 inode 编号、一个 2 字节的记录长度和一个 2 字节的名称长度，然后是实际的文件名。每个路径名组件的文件名限制为 255 字节，并且目录条目的长度向上舍入到下一个 4 字节边界。

目录本质上仍然是一个链表，并且在大型目录中搜索名称的速度很慢。

现在，在目录中搜索可用空间变得更加复杂：要创建一个新的目录条目，我们现在需要从头开始搜索目录，尝试在当前结构中找到一个足够大的间隙，以容纳我们要创建的名称。如果找不到，则将新名称附加到末尾，从而增加目录的大小。

目录中的可用空间永远不会通过压缩来回收，只有在新名称恰好适合时才最终重新使用。

符号链接（Symlinks）

传统的文件系统允许一个文件具有多个名称，使用 link() 系统调用和硬链接机制。硬链接的数量有限（一个 short，因此为 64 K 个名称）。

它们可能会意外丢失，例如，通过使用某些编辑器保存硬链接的文件。如果编辑器确实将文件写入为 filename.new，然后取消链接旧的 filename 并将新文件移动到位，则该文件的硬链接性质将被修改。

硬链接还会多次引用文件的原始 inode，因此它们不能跨越文件系统边界。

BSD 引入了一种新的文件类型（l，符号链接），并在链接的文件中放置一个“替换文件名”，该文件名确定链接目标位置。它可以是绝对名称或相对名称（相对于符号链接文件的位置）。

这会创建一个“软”链接或“符号链接”。尝试访问符号链接将使用替换文件名启动 namei() 中文件名的重新解释，从而导致尝试的 open() 系统调用被重定向到链接目标位置。

由于重定向发生在 namei() 中，它可以遍历文件系统边界，因此新的链接类型不受单个文件系统限制。它也不计入任何链接计数限制。

Rename 系统调用

BSD 引入了 rename() 系统调用，该调用以前需要使用对 unlink() 和 link() 的调用作为库函数来实现。由于这使用了多个系统调用，因此该操作不是原子的：它会受到部分执行的影响，并且由于它是一个多步骤过程，因此会受到恶意干扰。

配额（Quotas）

BSD 还引入了文件系统使用配额的概念：这些是对用户或组可以使用的文件数量和磁盘空间量的软限制和硬限制。

为了以有用的方式实现它们，必须修改文件系统的行为：

现在，将文件的所有者更改为远离自己是一种特权操作。如果没有这样做，则可以创建一个仅供自己访问的目录，然后将其中的所有文件赠送给另一个用户。然后，这些文件将计入该用户的配额。
同样，现在也不可能将文件的组成员身份更改为任何组。相反，只能使用来自用户组集的组。
最后，新目录和文件从其父目录继承其组，而不是从用户的用户组继承。这样，项目目录将包含计入项目配额的文件，而不是用户的用户组配额。

建议性锁定（Advisory Locking）

建议性文件锁定已在 4.2BSD 中引入。为此，已实现新的 flock() 系统调用。

锁可以是共享的（读取锁）或互斥的（写入锁）。
它们始终应用于整个文件，而不应用于字节范围。
不会尝试死锁检测。
它们与文件描述符相关联。因此，当进程死亡时，其文件句柄会自动关闭，这也会自动释放所有持有的锁。这非常强大，直到 dup() 和 fork() 发挥作用。

Posix 后来试图在此基础上进行改进，引入了第二个完全不同的锁系统，使用 fcntl()。这在不同的方面存在缺陷，但可以进行字节范围操作，并且它实现了一些基本的死锁检测。

实现这两个系统的内核（例如 Linux）现在有两种不同的、不兼容的文件锁定实现，它们彼此不了解。

本文对此进行了更多讨论，并提供了示例程序。

性能

作者在他们的论文中指出了以下优点：

ls 和 ls -l 速度很快，因为单个目录中文件的 inode 位于同一柱面组中。因此，读取和列出目录的寻道次数和寻道距离都非常低（除了子目录，它们肯定离得很远）。他们测量了没有子目录的目录的 8 倍加速。
根据所使用的控制器硬件，理论最大带宽的利用率从传统文件系统中的 3% 提高到 22% 甚至 47%。作者对结果感到非常自豪，因为这些结果是在具有真实用户生产数据布局的实际生产系统上实现的，而不是在合成基准布局上实现的。吞吐量在文件系统的生命周期内是稳定的，因为它的文件群发生了变化。

这解决了改进的主要驱动因素：更好的吞吐量和随着时间的推移性能不会降低的稳定布局。

此外，还进行了一些生活质量增强，从而可以在组中更舒适地工作，并释放新功能。

虽然 Linux 不包含任何 BSD 代码，但 ext2 文件系统几乎是 BSD FFS 的实现盲重写，适用于 Linux，重新创建了文献中描述的功能，而没有使用任何 BSD 代码。

BSD FFS 和 Linux ext2 仍然是非日志文件系统，在崩溃后需要进行文件系统检查。它们也不能很好地处理具有许多条目的目录，并且只能稍微好地处理深层目录层次结构。需要进行其他更改才能启用真正的大型文件系统，以便跟上不断增长的存储大小。

此外，仍然存在一些更隐蔽的限制：文件系统代码中的几个地方都受到锁的保护，这使得在高并发系统上扩展某些操作变得困难。

SGI 的 XFS 将在十年后的 1994 年解决这些问题。