第 3 章 - 其他文件系统 (Other File Systems)

Be 文件系统只是众多文件系统中的一个例子。每种操作系统都有自己原生的文件系统，各自提供了一些有趣的功能组合。本节将介绍若干在历史上具有代表性的文件系统（如 BSD FFS）、传统的现代文件系统（Linux ext2）、Macintosh 的 HFS，以及其他更先进的当前文件系统（Windows NT 的 NTFS 以及 SGI Irix 的 XFS）。

3.1 BSD FFS

大多数当前的文件系统至少部分都可以追溯到 FFS，因此在讨论文件系统时，不提及它就不算完整。BSD FFS（或简称 FFS）在性能和可靠性上超越了之前的 Unix 文件系统，并在近十年内成为健壮性和速度的标杆。FFS 的核心包括：一个超级块（superblock）、一个块位图（block bitmap）、一个 inode 位图（inode bitmap）以及一组预分配的 inode。这一设计理念至今仍构成了许多文件系统的基础。

FFS 第一个也是最简单的性能改进技术，是使用更大的文件系统块（block）大小。FFS 采用任意不小于 4096 字节的 2 的幂作为块大小。仅此一项，就使其性能较先前文件系统翻了一番（McKusick，第196页）。其中的道理很简单：连续的磁盘读取带宽远高于为读取文件的不同块而频繁寻道的带宽。无需多言，连续读写磁盘块始终是访问磁盘的最快方式，这种优势在可预见的未来仍难以超越。

当然，块越大也意味着空间浪费更严重：一个仅有 1 字节的文件也会占用整整一个块。McKusick 报道说，在使用 4096 字节块的文件系统上，存储约 775 MB 文件时，有高达 45.6% 的空间开销（即额外浪费了 353 MB）来保存这些文件。FFS 的解决方案是在块内管理碎片（fragment），最小可细分到 512 字节，通常为 1024 字节。FFS 通过块位图记录所有碎片的状态，而不仅仅是整块，从而既能为大文件保留大块以提升性能，又能避免小文件的大量空间浪费。

FFS 进一步通过最小化磁头移动来提升性能。磁盘驱动器的寻道时间非常可观；通过合理组织磁盘上数据布局，文件系统可以减少寻道开销。为此，FFS 引入了“柱面组”（cylinder group）的概念。利用磁盘的几何结构（磁头数、磁道数、柱面数以及每个磁道的扇区数），物理上将同一柱面上的所有磁道组成一个柱面组（见图3-1）。本质上，柱面组相当于磁盘的一个“竖切片”，在同一柱面组内读取连续块仅需切换磁头，这一电气操作速度远快于机械移动磁头。

在利用柱面组的局部性方面，FFS 还将文件系统的各类元数据按柱面组分散存放。例如，不是在磁盘起始位置放置一个大型位图，而是将块位图、inode 位图和预分配的 inode 都分散到各个柱面组中。同时，FFS 尽量将文件数据分配在靠近其 inode 的位置，以减少读取元数据与访问文件内容之间的长距离寻道。为了均匀地将数据分布到磁盘上，FFS 也会将新创建的目录放置在不同的柱面组中。

对于当时的磁盘驱动器而言，将数据组织到柱面组中大有裨益。但现代磁盘已将物理几何细节隐藏在驱动器控制器中，文件系统难以直接利用这些信息。而驱动器控制器本身反而能更有效、更精准地完成 FFS 曾经负责的工作。柱面组的管理职责已经从文件系统转移到磁盘驱动器。

FFS 的另一主要目标是通过精心排序元数据的写入来提高文件系统的可靠性。对元数据更新进行有序写入，使得一致性检查程序（fsck）在崩溃时能够更容易地恢复。如果 fsck 发现不一致的数据，就能根据现有内容推断出崩溃发生时系统的操作意图，进而纠正错误。通常情况下，FFS 的 fsck 能将文件系统恢复到一致状态。该恢复过程需要对文件系统做多达五次的检查与修复，时间开销取决于文件系统的大小和文件数量。

除了写入顺序之外，FFS 还要求所有元数据写入都必须同步完成。例如删除文件时，对目录的更新必须立即写入磁盘，而不能缓存在内存中。同步写元数据可保证：凡是修改元数据的调用一旦返回，就意味着磁盘上的数据确实已被更改。但元数据写入通常是少量的、分散的单块写操作，并几乎不具备连续性，将文件系统可支持的最大 I/O 操作数限制在磁盘多次单块写入速度之下，这是对性能的巨大制约。

总体而言，FFS 在当时为 Unix 文件系统带来了前所未有的性能和可靠性提升。通过利用柱面组的局部性，在上世纪八十年代中期的硬件条件下取得了显著的性能增益；而精心排序、同步写入元数据，则在崩溃恢复方面提供了强有力的保障。尽管现代磁盘和新一代文件系统在性能和可靠性上均已超越 FFS，但它曾一度奠定了 Unix 文件系统设计的标准。

3.2 Linux ext2

Linux ext2 文件系统是对经典 Unix 文件系统的一种惊人快速的实现。ext2 支持的唯一非标准特性是访问控制列表（ACL）。它通过放宽一致性模型，并依赖一个非常复杂的文件系统检查程序来修复崩溃造成的损坏，从而获得卓越的速度。

Linux ext2 与 FFS 在很多方面都非常相似，尽管它并不使用柱面组来划分磁盘分配，而是依赖驱动器自身进行重映射。ext2 仅将磁盘划分为若干固定大小的块组，每个块组都像一个迷你文件系统，拥有完整的超级块、块位图、inode 位图和 inode 表。这样，即便磁盘的大部分区域无法访问，文件系统一致性检查程序仍能在各个块组内恢复文件。

ext2 与 FFS 的主要区别在于，ext2 对文件系统的一致性及文件系统调用完成时操作是否已真正写入磁盘不作任何保证。实际上，ext2 将几乎所有操作都缓存在内存中，只有在需要刷新缓冲区时才写入磁盘。这使其在性能基准测试中（尤其是完全驻留于内存的测试）表现极为出色；在某些测试中甚至可能无需向磁盘写入任何数据，其性能仅受制于内核进行 memcpy() 的速度。这种模型与 FFS 严格的同步写入形成鲜明对比。ext2 所做的权衡十分明确：在 Linux 系统中，重启事件很少，保证系统在其余 99.99% 的时间里高速运行，比因同步写入而降低性能更为划算。

当然，这种一致性模型也并非没有缺陷，对某些应用可能完全不合适。由于 ext2 不保证操作的执行顺序和刷新时机，存在（虽不大）“后续修改已写入磁盘，而早先操作尚未写入”的可能。虽然文件系统一致性检查可以确保文件系统的整体一致性，但操作顺序的随意性可能导致应用行为异常，甚至因文件系统修改顺序不一致而崩溃。

尽管上述风险听起来严重，但在实际使用中此类情况极为罕见。通常情况下，ext2 的速度比传统基于 FFS 的文件系统快一个数量级。

3.3 Macintosh HFS

HFS 于 1984 年诞生，与此之前的任何文件系统都截然不同。我们讨论 HFS，正因为它是最早一批为图形用户界面设计的文件系统之一（这在其某些数据结构设计中可见端倪）。

几乎没有哪一点能让 HFS 与传统文件系统相似。它没有 inode 表，也没有显式的目录，记录文件所属数据块的方法也十分特殊。HFS 中唯一与现存系统类似的，大概只有用于标记块已分配或空闲的块位图。

HFS 大量利用 B* 树来存储文件系统结构。HFS 的两个主要数据结构是“目录项文件”（catalog file）和“扩展溢出文件”（extent overflow file）。目录项文件保存四类条目：目录记录（directory records）、目录线程（directory threads）、文件记录（file records）和文件线程（file threads）。

每个文件或目录都关联两种文件系统条目：记录（record）和线程（thread）。线程部分存储该项的名称及其所属目录；记录部分存储常规信息，如最后修改时间、如何访问文件数据等。除此之外，HFS 还在每个文件的记录中存储 GUI 所需的额外信息，包括在图形界面浏览时图标的显示位置——这种将 GUI 信息直接保存在文件记录中的做法在当时极为罕见。

目录项文件将卷上所有文件和目录的引用集中存放在一个整体结构中，并以编码方式体现了文件系统的层次结构；与传统文件系统中每个目录单独存储不同，HFS 中的目录内容通过目录线程条目在同一个 B* 树中串联。查找条目的关键字由父目录 ID 与项名称组合而成；每个文件记录都含有其父目录 ID，从而在逻辑上紧密关联文件与其所在目录。

由于目录项文件保存了所有文件和目录的信息，访问它必须串行化；任何创建或修改文件的操作都必须锁定目录项文件，阻止其他线程甚至进行只读访问，其访问模式只能是“单写多读”（single-writer/multi-reader），这在多线程文件 I/O 场景下是一个严重瓶颈。

HFS 在引入之初还提出了“资源分叉”（resource fork）和“数据分叉”（data fork）同属于一个文件的概念。这一创新在当时极为罕见，却为 GUI 系统提供了必要功能——通过这种双流（“分叉”）模型，可将图标、程序资源及其他元数据干净地存储在文件内部。

要访问 HFS 文件的任一分叉中的数据，需通过“extent map”——即分配映射。HFS 在目录项文件中的文件记录里存储了三条 extent（区段）信息；若同一文件的 extent 超出这三条，则额外信息保存在扩展溢出文件中。用于查找的关键字包括文件 ID、extent 在文件中的位置及所查找的分叉类型。与目录项文件相似，扩展溢出文件同样将所有文件的所有 extent 集中存储，从而再次迫使对其访问采用“单写多读”策略，进一步加剧多线程访问时的竞争。

此外，HFS 对卷容量还有一项严重限制：每个卷最多只能包含 65 536 个块，因主目录块（master directory block）仅用 2 字节来存储块数。这一限制迫使 HFS 在较大磁盘（如 1 GB 及以上）上采用非常大的块尺寸——32 KB 甚至更大，以弥补总块数的不足，但这对小文件来说浪费极大。教训十分明确：设计数据结构时务必留有足够的字段以适应将来的扩展。事后看来，主目录块中还有许多冗余字段，本可拿出额外 2 字节来扩充“块数”字段。

后来对 HFS 的一次重要修订——HFS+，消除了原 HFS 的诸如卷最大块数限制等部分缺陷，但在基本结构上仅作了极少改动。HFS+ 随 Mac OS 8.1 首次发布，这距 HFS 问世已有约 14 年。

尽管存在诸多严重局限，HFS 在发布之初依然开辟了新境界：它是首个能直接支持完整图形环境的文件系统。其最严重的局限在于高度单线程化，以及将所有文件和目录信息集中存储在单一的目录项文件中；将所有 extent 信息放在同一文件内、将卷块数限制为 65 536 也带来了可扩展性瓶颈。HFS 的资源分叉与数据分叉为文件及其元数据的存储提供了新思路；它奠定了图形界面文件系统的设计标准，但在性能与可扩展性等关键方面已难以满足现代需求。

3.4 Irix XFS

SGI 公司的 Irix 操作系统（Unix 的一个分支）提供了一个非常先进的文件系统——XFS。XFS 支持日志记录（journaling）、64 位文件以及高度并行操作。推动 XFS 开发的一大动力是对超大规模文件系统的需求——数十到数百 GB 的在线存储、数百万个文件以及跨越数十 GB 的超大文件。XFS 是为“大型机”而生的文件系统。

虽然 XFS 支持所有传统的文件系统抽象，但它在实现这些抽象时却大相径庭。XFS 在管理空闲磁盘空间、i-node、文件数据和目录内容方面，均有别于常见的直观实现。

如前所述，管理空闲磁盘块最常见的方法是使用每块对应一位的位图。XFS 则用一对 B+ 树来管理空闲空间。XFS 将磁盘分成若干称为“分配组”（allocation group）的较大块，每个分配组维护两棵 B+ 树：一棵按起始块号排序，一棵按长度（连续空闲块数）排序。该方案既可根据与已分配区域的邻近性查找可用空间，也可根据需用大小查找，从而高效地为文件分配合适的空间。唯一潜在的缺点是，两棵 B+ 树都保存相同信息的不同视图，若二者不同步就会产生不一致，但由于 XFS 支持日志记录，这类问题通常能被避免。

XFS 也不预分配 i-node，不像传统 Unix 文件系统那样使用固定大小的 i-node 表。相反，每个分配组按需分配存放 i-node 的磁盘块，并将 i-node 的位置记录在本组的一棵 B+ 树中——这一组织方式颇为罕见。其好处显而易见：不浪费为未使用文件分配的空间，且文件数量无上限；但查询 i-node 时需通过 B+ 树查找，而非表格索引，故查找开销比常数时间要高。

XFS 使用 extent（区段）映射来管理文件所占块。一个区段映射由起始块号和长度（块数）组成。与用直接、一级间接、二级间接、三级间接块管理固定大小块不同，XFS 再次采用 B+ 树——树的索引键是区段所对应的文件内偏移。借助 B+ 树，XFS 可使用可变大小的区段；代价是实现更复杂，但好处是少量映射即可覆盖文件的大块区域。XFS 单个区段便能映射多达两百万块。

XFS 还利用 B+ 树存储目录内容。传统文件系统将目录条目线性存储，当目录条目数增至数百或数千时，线性查找效率急剧下降；而 XFS 按名称排序条目，查找单个文件时效率极高，可轻松应对上数十万条目的目录。

最后，XFS 在并行 I/O 支持上也表现卓越。SGI 的高端硬件常常高度并行，某些机型可扩展至 1024 个处理器。XFS 实现了细粒度锁定：允许单写多读访问缓存中的文件，多 CPU 可并发 memcpy() 数据；在大型磁盘阵列上，多读模式可将多个请求同时排入磁盘控制器队列。XFS 甚至支持多写访问，但需采用绕过缓存的特殊访问模式。

总之，XFS 对传统文件系统实现作出了大胆革新，以复杂性换取性能提升，其成果无疑证明了这些设计选择的价值。

3.5 Windows NT 的 NTFS

Windows NT 文件系统（NTFS）是一种支持日志记录（journaling）和 64 位文件的文件系统，并内建对属性（attributes）的支持。NTFS 还在文件系统层面提供了文件压缩功能，并与其他 Windows NT 服务协同工作，以实现高可靠性和可恢复性。微软开发 NTFS，是为了支持 Windows NT 并克服当时（约 1990 年）现有文件系统的局限。

主文件表（Master File Table）与文件

NTFS 的核心数据结构是主文件表（MFT）。MFT 包含了文件系统中所有文件的 i-node（在 NTFS 术语中称为“文件记录”）。正如稍后将述，MFT 本身即作为一个文件存在，可根据需要动态增长。MFT 中的每个条目对应一个文件，存储了访问该文件所需的所有信息。每个文件记录的大小可为 1、2 或 4 KB，由文件系统初始化时确定。

NTFS 的 i-node（文件记录）将文件的所有信息组织为一系列“属性”（attribute）。其中一些属性（如时间戳）是必需且始终存在的；另一些属性（如文件名）也是必需的，但可能有多个实例（例如 NTFS 文件名的截断 MS-DOS 版本）。还有部分属性仅在 i-node 中存放属性头，并通过指针引用其实际数据。

当一个文件的属性过多，单个 i-node 无法容纳时，会在该 i-node 中添加一个“属性列表”属性，该属性记录另一个 MFT 条目的编号，后者保存额外的属性。如此一来，文件可拥有理论上不受限的属性列表。NTFS 将文件和属性数据统称为“属性流”（attribute streams）。对于文件所占用的磁盘区段（extent），NTFS 以 extent 形式记录：每个 extent 由起始块号和长度（块数）组成。Extent 方法虽紧凑，但查找文件中某一位置时，需遍历整个 extent 列表以定位对应区段。关于 NTFS 是否还同时采用间接块来访问大型文件，目前公开资料甚少，尚无定论。

文件系统元数据（File System Metadata）

NTFS 在存储和组织元数据结构方面有一套优雅的方案：所有文件系统的数据结构，包括 MFT 本身，都作为普通文件存放，且均有对应 MFT 条目。MFT 的前九个条目固定如下：

• MFT 自身
• MFT 的部分副本（Partial MFT copy）
• 日志文件（Log file）
• 卷文件（Volume file）
• 属性定义文件（Attribute definition file）
• 根目录（Root directory）
• 位图文件（Bitmap file）
• 引导文件（Boot file）
• 坏簇文件（Bad cluster file）

此外，NTFS 在 MFT 中还预留了八个条目，以备将来可能新增的系统文件使用。每个条目都是一个常规文件，具备文件的全部属性。

通过将所有元数据作为文件存储，NTFS 能让这些结构动态增长。例如，卷位图文件可根据需要扩大，从而直接支持卷的在线扩容——只需增加存储空间并让位图文件增长即可。与之类似的系统还有 IBM 的 JFS。

卷文件（Volume file）存储了卷名称及其他全局信息；日志文件以文件形式保存，使其也能按需增长（可提高文件系统吞吐，但在崩溃时可能丢失更多未提交数据）。属性定义文件是一个小型维护文件，列出了本卷支持的属性类型、是否可索引及是否可在恢复时重建。

在这些保留的系统文件中，仅引导文件必须位于磁盘的固定位置，以便计算机的启动 ROM 能方便地加载并执行它。NTFS 格式化时会预留该固定位置，并在引导文件中记录 MFT 的位置。

目录（Directories）

NTFS 中的目录存储在 B+ 树中，条目按字母顺序排序。目录条目除了文件名，还保存文件参考号（i-node 编号）、文件大小和最后修改时间。NTFS 的一个特殊之处在于，它不仅在 i-node 中保存文件大小和修改时间，也在目录条目中重复存储这些信息。这使得使用 MS-DOS 的 dir 命令列出目录时极为快速，但也带来数据冗余、可能不同步的问题。而且 Windows NT GUI 在显示文件图标、位置等时通常还需读取 i-node，因此该做法的实际性能优势存疑。

日志记录与日志文件服务（Journaling and the Log File Service）

NTFS 的日志记录由日志文件服务（Log File Service）实现，文件系统本身不直接承担日志逻辑。日志记录涉及文件系统、日志文件服务和缓存管理器三方协作，以确保事务正确记录，并在系统故障时可回放。

NTFS 采用预写式日志（write-ahead logging）：先将计划变更写入日志，再将实际的文件系统块写入缓存。以下操作会在日志中生成记录：

• 创建文件（Creating a file）
• 删除文件（Deleting a file）
• 更改文件大小（Changing the size of a file）
• 设置文件信息（Setting file information）
• 重命名文件（Renaming a file）

NTFS 通过向日志文件中写入条目来通知日志文件服务即将进行的更新。当一个事务完成后，NTFS 会写入一个检查点记录，以表明该事务不再有未记录的更新。日志文件服务以循环方式使用日志文件，对 NTFS 呈现出“无限”日志的假象。为了防止日志覆盖仍需保留的重要信息，如果日志即将写满，日志文件服务会向 NTFS 返回“日志已满”（log file full）错误。NTFS 收到此错误后，会引发异常、重新调度该操作，并请求缓存管理器将未写入的数据块刷写到磁盘。通过强制刷新缓存，NTFS 可将属于未完成事务的块写入磁盘，从而让这些事务得以完成，并释放出日志空间。此“日志已满”错误对用户程序透明，仅作为内部机制提示需刷新缓存以腾出日志空间。

当必须刷新日志时，NTFS 首先锁定所有打开的文件（以阻止进一步的 I/O 操作），然后调用缓存管理器将所有未写入的块写入磁盘。这可能会在任意且不可预测的时刻中断重要的 I/O 操作，用户会感觉系统短暂“卡住”片刻，然后恢复正常运行。在某些场景下，这种行为可能无法接受。

如果卷在运行中发生崩溃，下次访问该卷时，NTFS 会回放日志以修复可能出现的损坏。回放日志时，NTFS 首先扫描日志以定位最后一个检查点记录的位置，然后从该位置逆向回放更新记录，直至回到文件系统最后一个已知的正常状态。此过程最多只需数秒，且不受磁盘容量大小的影响。

数据压缩 (Data Compression)

NTFS 还支持对文件进行透明的数据压缩以节省空间。NTFS 提供两种压缩方式。第一种方法针对文件中大片空洞（全零填充）区域，仅在元数据中记录这些区块的位置，而不实际写入零；这种技术称为稀疏文件（sparse files），在 Unix 文件系统中也很常见。对于需要在磁盘上存储大型稀疏矩阵的科学计算应用而言，稀疏文件是一项重大优化。

第二种方法则是一种较为传统（但未公开文档）的压缩技术。在此模式下，NTFS 将文件切分为每组 16 个文件系统块的小区段，对每个区段单独压缩；若压缩后数据未至少节省一个块，则该区段仍以未压缩方式存储。对文件按区段分别压缩，使得压缩算法可针对文件的不同部分采用不同策略。

在实践中，由于 CPU 的速度远超磁盘 I/O，NTFS 访问压缩文件与未压缩文件的性能差异较小。但若配备高速 RAID 子系统，情况可能会大不相同。

将压缩功能集成到文件系统层面（而非对整个卷统一压缩）允许用户或程序根据对文件内容的高级认知，选择性地压缩特定文件。虽然这需要更多的配置与管理成本，却具有两个优点：不会影响其他文件的 I/O 性能，且被选中的文件最能从压缩中受益。

NTFS 小结 (NTFS Summary)

NTFS 是一款功能先进的现代文件系统，支持文件属性（attributes）、64 位文件和卷大小、日志记录以及数据压缩。其唯一区别表现平平的方面是文件属性尚无法被索引或查询。总体而言，NTFS 是一个设计精良、特性丰富的文件系统，非常适合 Windows NT 的目标市场。

3.6 总结 (Summary)

本章简要介绍了五种现有文件系统家族中的代表成员：开创现代文件系统先河的 BSD FFS；速度惊人却安全性较低的 ext2；为图形界面而生的独特 HFS；面向大型存储阵列的强悍 XFS；以及功能全面、深度集成于 Windows NT 的 NTFS。每种文件系统各具特色，满足不同场景需求。了解它们的设计理念与特性，有助于在设计新文件系统时做出更合适的选择。