每个操作系统都有配套的文件系统，分别提供了不同的特性。本章简单的介绍一些的文件系统，比如具有很高历史地位的BSD FFS，传统而流行的Linux Ext2，Macintosh HFS，还有高级的Window NTFS和SGI Irix的XFS。

     从历史角度，文件系统就是一种管理持久存储介质的方法。大多数文件系统的基础都是简单的目录和文件多级结构。这种设计虽然简单，但是却可以有许多实现。可能最精髓的实现就是BSD FFS（Berkeley Software Distribution Fast File System）了。

    3.1 BSD FFS

    大部分现代文件系统的祖先都能追溯到FFS，所以对文件系统的完整介绍不可能忽略它。BSD FFS在原有Unix文件系统的基础上改进了性能和可靠性，于是在后来的几乎10年内都是文件系统健壮性和速度的标准。在它的框架里，有一个超级块，一个块位图，一个i-node位图，和一些预分配的i-node数组。这种设计可在许多现代文件系统里找到。

     FFS对Unix文件系统的第一个改进是块大小。FFS使用任何大于或等于4096的2的幂作为块的字节大小。仅这一个改进就使性能提高了一倍，原因很简单：相比搜寻和读取多个块，对磁盘的连续读取能达到更高的带宽。对磁盘的连续读写毫无疑问是最快的方式，即使未来也是如此。

    大的块也会有代价：磁盘空间的浪费。实际上，McKusick的报告说，在一个块大小为4096字节的文件系统了，总共775MB的文件会导致45.6%的额外空间浪费，即除了文件本身数据占用的空间外，文件系统还需要353MB的空间来“管理”这些文件。FFS通过把块分片（fragments）来克服这个问题。片（fragment）最小可以为512字节，一般是1024字节。FFS通过块位图来管理片，这样块位图不仅需要记录所有块的状态，还要记录所有片的状态。分片策略允许FFS为大文件采用较大的块，而又不会因为小文件浪费太多的空间。

    FFS的第二个改进是减少磁盘头的移动。显然磁盘头频繁从一个地方移动到另一个地方是非常耗时的。通过仔细的安排数据在磁盘上的位置和结构，文件系统能尽量减少磁头的寻道时间。为此，FFS引入了柱面组（cylinder groups）的概念，深入到磁盘的物理结构（磁头的个数，磁道（tracks），柱面（cylinders）及每个磁道上的扇区（sectors）数）来提高性能。物理上，一个柱面组就是所有磁头对应的同一位置的磁道上的所有块，本质上，柱面组就是磁盘的一个垂直切片。这个改进能提升性能的原因是，读取多个块的数据只需切换不同的磁头。而磁头的切换是一个电子操作，比其他物理操作（比如移动磁头）要快得多。

     FFS使用柱面组的局域性来组织磁盘上的数据。比如，很多文件系统把连续的位图块放在整个磁盘的开始部分，但FFS把它们分散到每个柱面组里。i-node的位图和预分配i-node的位图也有类似处理。FFS还试图把文件的数据放在i-node的附近，减少读取文件元数据和实际内容之间的寻道时间。为了让数据在磁盘里均匀散布，FFS还把新目录放到不同的柱面组里。

    在设计FFS的时候，采用柱面组是一个很好的方案。但是现代的磁盘隐藏了太多的物理结构，导致FFS这样的文件系统不再有预期的作用。现代的磁盘驱动已经把FFS做的大部分事情都做过了，而且做得更好更精确，因为磁盘驱动程序拥有磁盘的所有信息。柱面组是一个好想法，但是现在由磁盘驱动程序来管理，而不是文件系统了。

    除了仔细安排文件系统元数据的写顺序，FFS还强制所有元数据写操作要同步完成。比如删除文件时，对应目录的更新必须直接写入磁盘，不通过内存缓冲。同步元数据写操作能保证，只要写操作返回，那么元数据一定已经写到了磁盘上。但是，需要写的元数据往往只占用单个块，并分布在不同的位置，于是文件系统的I/O操作速度上限就被这些单个块的写操作拖了后腿，因为这种方式是最慢的磁盘写方式。

    在二十世纪80年代，FFS通过引入柱面组的概念，提供了Unix文件系统没有的高性能和高可靠性。但现在的磁盘驱动彻底隐藏了这些细节，于是FFS不再有当初的辉煌。而FFS仔细的安排元数据的写顺序，以及强制性的同步写，反而成为了更大的性能瓶颈。虽然现在FFS已不再是Unix文件系统里最快和最安全的了，但它永远是一个标准。

    3.2 Linux ext2

    Linux Ext2文件系统是在传统Unix文件系统基础上实现的一个高效版本，它支持的唯一“非标准”特性是访问控制列表（access control lists）。Ext2通过放松对系统一致性的要求，来达到极高的性能，同时使用非常复杂的文件系统检测程序来发现和修复文件系统的损坏。

    Ext2和FFS非常相似，但它没有使用柱面组的概念，而是让驱动程序自己完成这些映射。Ext2文件系统把整个磁盘划分成几个固定大小的块组（block groups），每一个块组都像是一个微型的文件系统，拥有完整的超级块，块位图，i-node位图和i-node列表。这样即使在大部分磁盘都损坏的情况下，文件系统检测程序仍然可以恢复部分文件。

     Ext2和FFS最大的不同是，Ext2从不保证文件系统的一致性，也不保证写操作返回后，数据一定已经在磁盘上。实际上，Ext2的所有操作都是在内存缓冲区里完成的，除非实在需要把数据刷到磁盘上了，这使Ext2的测试性能非常引人注目。在有些测试里，由于根本没有向磁盘写过任何数据，Ext2的性能完全取决于操作系统能多快的进行memcpy()。

    这种模型和FFS采用的强制同步写模型形成了鲜明的对比。Ext2的哲学很明显：在Linux世界里，重启是极其稀有的事情，所以使系统在99.9%的时间里拥有高性能，比任何事情都重要。

当然，如果这种哲学是完全正确的话，所有的文件系统都会这么做了。Ext2的模型并不是完美无暇，对于有些应用程序甚至是完全不适用的。由于Ext2不保证文件修改操作被刷写到磁盘上的顺序，所以有可能（虽然可能性有点小）后来的修改被先写到磁盘。虽然文件系统检测程序能保证整个Ext2系统的一致性，但是这个无序性漏洞会使应用程序疑惑，甚至因为文件状态的不一致而崩溃。

    上面的描述听起来可怕，实际中却很少碰到。通常，Ext2文件系统比基于FFS的其他文件系统能快上10倍。

    3.3 Macintosh HFS

    HFS诞生于1984，并且和所有先前的文件系统都不同。我介绍它的原因是，它是第一个从设计上支持图形用户界面的文件系统，我们在它的许多数据结构的设计里都能看到这一点。

基本上，HFS没有哪一点像传统文件系统。它没有i-node列表，没有显而易见的目录，并且记录文件块的方式也很奇怪。唯一能在HFS里找到的相似点是，它也有一个块位图，记录哪些块空闲，哪些块已分配。

    HFS广泛的使用B*树来存储文件系统结构。它有2个主要的数据结构，编目文件（catalog file）和扩展溢出文件（Extent Overflow File）。编目文件里存储4种对象：目录记录（directory records），目录线索（directory threads），文件记录（file records），文件线索（file threads）。

    每个文件或目录都有2个结构与之关联：记录（record）和线索（thread）。线索对象存储文件的名字和所属的目录。记录对象存储文件的普通信息，比如3个时间戳，文件数据等。除此之外，文件系统还存储了每个文件的GUI信息。当在GUI下浏览文件系统时，需要知道如何显示每个文件的图标，以及显示的位置。在当时，直接在文件记录里存储这些信息是不寻常的。

编目文件（catalog file）采用一种紧致的结构存储指向卷内所有文件和目录的引用，它对文件系统的层次结构进行了编码，不像传统文件系统那样直接的分开存储每个目录的内容。通过编目（catalog），单个目录下的内容被线索记录（thread records）收集（threaded）到一起。

    编目文件里，搜索的关键字是父目录的ID和对象自己的名字。于是在HFS里，每个文件和它的父目录有很强的联系，因为每个文件记录都包含了父目录的ID

    编目文件的结构非常复杂，因为它要记录所有文件和目录的信息，同时也导致整个文件系统必须顺序访问（serialization）——这对于多线程的文件I/O操作非常不理想。在HFS里，任何创建文件、修改文件的操作都需要锁住编目文件，别的线程即使只读访问它都不行。编目文件的访问必须是单写者/多读者模式。

    HFS为每个文件引入了资源分支（resource fork）和数据分支（data fork）的概念，这在当时是个难得的进步，为GUI系统提供了必需的功能抽象。把这2种数据流（streams，或者叫“分支（fork）”）概念区分开来，使得一个文件的其他信息，比如图标、程序资源或其他元数据，可以直接存储在文件里。

    存储在资源或数据分支里的文件数据可以通过扩展映射（extent maps）来访问。HFS编目文件的每个文件记录可以存储3个扩展，扩展溢出文件（Extent Overflow File）存储余下的文件扩展，搜索的关键字是文件ID编码，扩展的索引，和所在的分支。与编目文件一样，扩展溢出文件存储了所有文件的扩展，再次导致了文件系统只能顺序访问。这给多线程程序访问文件系统带来了很大的局限。

    HFS还有另一个严重的局限：每个卷的块数最多只能是65536。主目录块（master directory block）只使用2字节来存储卷内的块个数。这个局限使HFS不得不使用更大的块，比如在1GB的磁盘上，HFS使用32K的块也不少见，导致了相当的磁盘浪费。这里的教训很明显：让你设计的数据结构更持久。回想当初，主目录块里包含了许多无关紧要的字段，完全可以腾出2个字节给“块个数”字段。

    HFS后来的一个版本，HFS+，去掉了原来的一些限制，比如块的个数，但是对HFS内部结构却改动很少。HFS发布14年后，HFS+终于在Mac OS 8.1上开始服役了。

    尽管HFS有诸多局限，但它开辟了文件系统的一个新典范，即直接支持图形化环境。HFS最大的局限在于，它只支持单线程，以及所有文件和目录的信息都存储在一个文件里，即编目文件（catalog file）。把所有文件的扩展信息存储在一个文件里（扩展溢出文件）和限制块个数为65536一下，也是HFS的严重局限。但是，资源和数据分支的概念，提供了一种全新的存储文件和元数据的方案。HFS为支持GUI的文件系统设定了一个标准，但是它在其他许多关键的领域，比如性能和扩展性，有着很大的缺陷。

    3.4 Irix XFS

    Irix操作系统是SGI开发的一个Unix系统变种，并提供了一个非常成熟的文件系统，叫做XFS。XFS支持日志（journaling），64-bit文件，和高并行的操作。开发XFS的一个主要动力是支持非常大的文件系统——拥有成百上千GB的在线存储，百万的文件，和上GB的文件。XFS是文件系统里的“钢铁巨人”。

    虽然XFS支持文件系统的所有传统抽象，但是却在实现方式上另辟蹊径。XFS完全没有采用传统文件系统的实现方式，无论是空闲磁盘空间的管理，i-node，文件数据，还是目录内容。

    大家都知道，管理磁盘空闲块最直接的方法是使用位图，每个bit表示一个块。XFS却使用一对B+树来管理。XFS把磁盘分成许多分配组（allocation groups，与FFS的柱面组有点相似），每个分配组里都有一对B+树记录组内的空闲空间，其中一个按照空闲空间的起始块号排序，另一个按照空闲空间的长度排序。这样文件系统就既可以根据已分配空间的位置来申请新空间，也可以根据需要的空间大小来申请新空间。显然这种组织方式能为给定文件找到更合适的空闲块，唯一可能的缺点是2个B+树维护了同样数据的不同形式。如果由于某种原因，致使它们之间的同步失效，那么这2个B+树就会不一致，导致不可预料的后果。不过由于XFS是带日志的文件系统，一般情况下，不会发生这种事情。

    XFS与传统Unix文件系统不同的另一点是，它不预分配i-node节点。XFS的i-node列表并不是固定大小的，而是每个分配组（allocation group）根据自己的需要临时分配。XFS在每个分配组里使用B+树来存储i-node的位置——这是一种非常少见的架构。优点很明显：没有浪费预分配空间，也没有文件系统的文件数限制。但缺点也是显然的：如果i-node节点列表是固定大小的，查找就是一个常数复杂度的操作；而XFS里却要查找B+树。

    XFS使用扩展映射（extent maps）来管理文件的块。扩展映射包括一个起始块索引和块的个数。XFS不是使用列表简单的列出直接、间接或双间接的块，而是再次使用了B+树，并且这次的关键字是块内数据在整个文件中的位置。

    采用B+树使XFS能使用变长的扩展空间（extents），而代价是实现上的复杂性。XFS能使用一个扩展映射包含2百万个文件块。

    XFS使用B+树存储目录的内容，在当时也是一个与传统文件系统不同的地方。传统的文件系统把目录的内容存储于线性结构里，所以导致对象太多时性能严重下降。XFS再次使用了B+树，把对象的名字作为关键字，方便了文件的查找，即使是包含成百上千个文件的目录也非常高效。

    XFS技压群雄的最后一个领域是并行I/O的支持。SGI的许多高端硬件都是高并行度的，甚至有些机器的处理器有1024个之多，所以支持细粒度锁（fine-grained locking）是必不可少的。虽然许多文件系统允许同一文件打开多次，但内部却对i-node进行了加锁，阻止了真正的并行访问。XFS去掉了这个限制，允许单写者/多读者访问同一文件。对于在内存缓冲区里的文件，多个CPU可以同时复制文件数据。对于大型磁盘阵列系统，多读者访问使多个请求能排队等候磁盘控制器的处理。XFS还支持多个写者访问同一文件，不过需要用户使用一种特殊的访问模式绕过文件缓冲。

    XFS给传统文件系统注入了新的血液，它没有采用“标准方案”，而是用更复杂的实现，换取更高的性能。XFS的高性能和高复杂度总是一个引人注目的争论话题。

译自《Practical File System Design》Chapter 3。