今天继续与大家分享系列文章“50 years in filesystems”由 KRISTIAN KÖHNTOPP 撰写。
1994 年，文件系统的第三个十年，SGI XFS 诞生了。XFS 在处理大容量和高负载存储环境中表现出色。直到今天，XFS 仍然是一个活跃、被广泛采用的文件系统。
在 1994 年，论文《XFS 文件系统的可扩展性》发表了。自 1984 年以来，计算机的发展速度变得更快，存储容量也增加了。值得注意的是，在这个时期出现了更多配备多个 CPU 的计算机，并且存储容量已经达到了 TB 级别。对于这些设备，仅仅对 4.3BSD 快速文件系统（或 SGI IRIX 中称为 EFS 的修改版本）进行改进已不再足够。（点击此处回顾 BSD Fast Filling System）
SGI 的基准测试中采用的计算机拥有大型背板和多个控制器（其中一项基准测试采用了一个具有 20 个 SCSI 控制器的设备），大量的磁盘（上百块硬盘驱动器）以及多个 CPU（12个 CPU 插槽）和大量内存（最高1GB）。
SGI 是一家制造高性能计算机（HPC）和图形工作站的企业。在 20 世纪 80 年代和 90 年代，SGI 是计算机图形和可视化领域的先驱和领导者。在进行基准测试时，SGI 会使用一系列具有特定配置的计算机设备，并进行性能测试和比较，以评估其系统的性能和能力。
然而，SGI 在 2009 年申请破产保护，并在 2016 年以“Silicon Graphics International”为名重组，继续致力于提供高性能计算和数据分析解决方案。SGI 在计算机发展史上留下了重要的足迹，并对计算机图形和可视化领域产生了深远的影响。
IRIX 6.5 Desktop from https://en.wikipedia.org/wiki/IRIX
当前所需的文件系统处理能力已经超出了 FFS（Fast Filling System），文件的大小也超过了 FFS 可以的处理能力，目录中的文件数量增大导致查找时间过长，像分配位图（allocation bitmaps）这样的中央数据结构无法进行有效的扩展，并且全局锁在多个 CPU 的情况下会造成低效的文件系统并发访问。于是，SGI 决定设计一个完全不同的文件系统。
此外，整个 Unix 社区也面临着来自 David Cutler 和 Helen Custer 的挑战，他们开发了 Windows NT 4.0 的开发者。通过 Windows NT 4.0 中的 NTFS，他们展示了从头开始设计系统的可能性。
新要求
XFS 文件系统充满了创新思想，与传统的 Unix 文件系统设计有很大的不同。其中的新特性包括：
- 通过以下方式实现并发性：
- 分配区域
- Inode 锁分离
- 大规模并行 I/O 请求、DMA 和零拷贝 I/O 功能
- 通过以下概念，提高访问的可扩展性：
- B+树：一种平衡的多路搜索树，可以有效地存储和检索大量的数据；
- extent：一种用来描述连续的磁盘块的数据结构，由（起始块，长度）两个字段组成 2；
- 将“文件写入”和“文件在磁盘上的布局”分离，以便通过使用延迟分配和预分配来实现连续的文件。
extent（区段）表示文件在磁盘上连续的一段数据块。每个 extent 由一个起始位置（start）和一个长度（length）描述符组成，用于指定文件在磁盘上的物理存储位置。通过使用 extent，文件系统可以实现动态增长的 I/O 大小，从而提高吞吐量。extent 的概念还可以与延迟分配和预分配相结合，以优化文件的布局，使得文件在磁盘上可以连续存储。这种连续存储可以减少磁盘寻址的开销，提高文件读写的效率。
- 引入预写日志（write-ahead log）以记录元数据更改：
- 异步记录日志以实现写入合并
- 利用日志进行恢复，使恢复时间与正在处理的数据量成比例，而不是与文件系统的大小成比例。
XFS 是为了满足这些特性而开发的，实现这些特性后就可以在视频编辑、视频服务和科学计算等领域充分发挥大型 SGI 设备的性能。
一个不使用日志结构的日志文件系统
在约同一时期，John K. Ousterhout 提出了一个问题：“为什么操作系统的速度没有跟上硬件的发展速度？” Ousterhout 开始在实验性的 Sprite 操作系统中探索基于日志的文件系统的想法。
Sprite 是一种早期的分布式操作系统，最早由John K. Ousterhout 和 Kenneth L. Dickey）于1984年在加州大学伯克利分校开发。Sprite 的设计目标是提供高度可靠的分布式环境，支持在网络上连接的多台计算机之间进行协作和通信。它在学术界和研究领域具有一定影响力，为后续分布式操作系统的发展奠定了基础。
基于日志的文件系统是一个非常激进的想法，我们在后续的文章中会讨论。尽管它们在时间上比 XFS 早一点，但这个概念的引入具有重要的意义。最初它们并不实用，因为它们需要不同的硬件提供更多的磁盘寻道。日志结构化文件系统的理念必须变得更加精细才能产生实际影响，我们将在本系列的后续部分中讨论它们。
IRIX 的处境
IRIX 是 Silicon Graphics Inc.（SGI）开发的操作系统，用于其工作站和服务器产品线。它是基于Unix System V 的变种，并包含了许多 SGI 独有的功能和优化，以适应其高性能计算和图形处理需求。IRIX 在1988年首次发布，并成为 SGI 工作站的主要操作系统，为许多科学、工程和创意领域的应用提供了强大的计算和图形处理能力。
IRIX 最初使用 EFS（Extent File System）作为其文件系统，它是 BSD FFS 的一个改进版本，使用了 extents 来描述文件的连续磁盘块。它受到 8 GB 文件系统大小限制，2 GB 文件大小限制，以及无法充分利用硬件 I/O 带宽的影响，这让许多购买了这些昂贵机器的客户感到不满。后来，SGI 开发了 XFS 文件系统来取代 EFS，并在 IRIX 5.3 版本中引入了 XFS3。XFS 是一种高性能的 64 位日志文件系统，支持大容量存储、快速恢复和高级管理功能。
视频播放和数据库社区对文件系统提出了新的需求：需要支持数百 TB 的磁盘空间、数百 MB/s 的 I/O 带宽以及许多并行的 I/O 请求，以便能够充分利用硬件资源，同时确保不会出现 CPU 资源瓶颈。
“XFS文件系统的可扩展性”这篇论文主要展示了它的功能，对其实现和设计决策进行了简要讨论，也没有提供详尽的基准测试。
功能特性
大容量文件系统
XFS 支持大容量文件系统。之前的文件系统使用 32 位的指针来指向磁盘块。块的大小是 8 KB ，使用 32 位的块指针，文件系统的上限是 32 TB。
当使用 64 位的块指针会导致许多数据结构的大小变成 8 字节的倍数，这样的操作会造成一些些浪费。
为了提高并发性（参见下文），XFS引入了“分配组”（Allocation Groups，简称AG）的概念，其大小总是小于 4GB。分配组（AG）拥有本地实例，这些实例具备文件系统数据结构，例如，inode 映射或空闲块跟踪。这些本地实例可以独立进行加锁，从而允许在不同的分配组中进行并发操作。
分配组（AG）还有助于减小指针的大小：一般组内编号可以用 32 位指针表达。事实上，一个 4GB 的分配组可以容纳最多 1M 个块的块，因为每个块的最小大小为 4K。组内单个最大的 extent 可以用 40 位（5字节）来表示（位置和大小各占 20 位）。
文件和文件系统最大值为 8 EB（2^63-1）。
带宽和并发
XFS 的设计目标之一就是并发操作。1994 年是 20 MB/s SCSI 控制器的时代，SGI 构建了能够容纳多个控制器和多个驱动器的大型机箱。基准测试引用了具有 480 MB/s 总带宽的计算机，其文件 I/O 性能超过 370 MB/s，无需进行任何调整，包括所有开销。这对于当时的日常使用来说是相当令人印象深刻的。
XFS 通过使用大块（4 KB或8 KB块大小）和extents 概念来实现这一点。
Extent 和二叉树
在 XFS 中，“extent” 是一个核心概念，它通常是一个包含两个字段的元组（起始块和长度）。将文件块映射到磁盘块（“bmap”）时，“extent” 则包含三个元素，即一个三元组（偏移量，长度，起始块）。由于分配组（AG）存在上限值，可以用一系列 4 字节的 extent 来描述连续的多达 2M 个数据块，这比 BSD FFS 之前的方法更为高效。
extent 也使 XFS 能够进行大规模 I/O 请求。源于它们描述了连续的块区域，这样可以轻松创建读取或写入多个块的请求。默认情况下，它使用 64 KB 的内存缓冲区进行 I/O 操作，除非有特殊规定使用更大的内存缓冲区。
XFS 通过条带化（striping）来管理底层磁盘结构，并支持同时处理 2 或 3 个并发的 IO 请求。它会检查反压（backpressure），也就是检查应用程序是否实际上在读取数据。如果是的化，文件系统会发出额外的读取请求，以保持默认情况下最多 3 个请求同时进行，这样可以一次处理 192KB 的数据。
extent 组被组织成一个线性的列表，但这会导致扩展性问题。因此，XFS 使用 B+ 树来处理多个索引块的情况，如果只有一个索引块时，则退化为线性列表。
B+ 树是一种树状数据结构，用于组织和管理 extent 组。它允许在大规模的 extent 组集合中高效地进行搜索、插入和删除操作。B+树结构能够有效地处理大量的 extent 组，并且具有较好的扩展性和性能。
通常，元组是根据其第一个值进行索引，但对于某些结构（如空闲列表），会保留多个索引：通过 startblock 索引进行接近性的空间索引是有用的，但也按 length 索引来适配正确的可用空间。
去掉每个文件的写锁
Posix锁定内存中的 inode 以保证原子写入。这确保了任何两个大型多块写操作总是按顺序进行。
XFS还去掉了内存中的 inode 锁：Posix 要求对于大型、重叠的多块写操作进行完全有序的处理。当它们重叠时，不能出现从写操作 A 和写操作 B 交替出现的块混乱现象。
在大多数内核中，默认设置是在内存中的 inode 上放置一个文件全局锁，以此确保每个 inode 只能有一个写入者。数据库的开发者对此非常不满，因为它将任何单个文件的写并发性限制为 1。这也是为什么 Oracle 建议将表空间分成多个文件来实现并发性，每个文件的大小不超过 1GB。
在 O_DIRECT 模式下，XFS 消除了这个锁，并允许原子、并发的写操作，数据库开发者对此非常认同。
动态 inode 和空闲空间跟踪优化
对于大型文件系统，你永远无法预知：应用程序是需要大量的 inode 来存储许多小文件，还是少量的大文件。此外，inode 和文件数据块之间的距离是多少也没有一个确定的答案。
对于第一个问题没有一个好的答案，而对于第二个问题，答案是“让它们尽可能接近”。因此，XFS 根据需要动态创建 inode，每次创建 64 个 inode 的块。
对于较大的 inode，即 256 字节的 inode（相比于 BSD FFS 的 128 字节和传统 Unix 的64字节），XFS 使用的策略是，仅在需要时创建 inode，并将它们放置在文件的开头附近来进行补偿。这样可以释放大量的磁盘空间。在具有固定 inode 计数的传统 Unix 文件系统中，高达3-4%的磁盘空间可能被预先分配的inode 所占用。即使在使用了柱面组（cylinder groups），inode 与第一个数据块之间仍然存在相当大的距离。
由于 inode 可以存在于磁盘上的任何位置，而不仅仅是超级块后面，因此需要对 inode 进行跟踪。XFS 通过每个分配组（AG）使用一棵 B+ 树来实现这一点。该树以起始块为索引，在每个块中记录每个 inode 块是否可用或正在使用。inode 本身并不保存在树中，而是保存在靠近文件数据的块中。
类似地，空闲空间以块为单位进行跟踪，并在每个分配组（AG）的树中进行两次索引：起始块和长度索引。
预写式日志
系统崩溃后要恢复一个大型文件系统可能会很慢。恢复时间与文件系统的大小和文件数量成正比，这是因为系统基本上必须扫描整个文件系统并重建目录树，以确保数据的一致性。对于 XFS 来说，文件系统更加脆弱，因为它提供了可变数量的 inode，并且在磁盘上分散地非连续存储。恢复它们将会有很大的开销。
使用元数据的预写式日志（write-ahead logging），可以在大部分情况下可以避免这个问题。使得恢复时间与日志的大小成正比，即与崩溃时正在处理的数据量成正比。
日志中包含了日志条目，每个条目包括一个描述符头和所有更改过的元数据结构的完整镜像：包括 inode、目录块、空闲 extent 树块、inode 分配树块、分配组块和超级块。由于完整镜像存储在块中，因此恢复过程非常简单：只需将这些新的、更改过的镜像复制到它们原本应该在的位置上，而无需了解它所更改的结构类型。
作者对日志非常信任：因此 XFS 最初没有 fsck （文件系统一致性检查）程序。然而，事实证明这种设置过于乐观了，因此现在有了 xfs_repair 程序。
元数据更新性能
XFS 会记录元数据更新，这意味着它们需要被写入文件系统日志中。默认情况下，该日志会放置在文件系统中。但也可以选择将日志提取出来，放置在其他介质上，例如闪存存储或带有电池备份的内存。
如果可能的话，对日志的写入是异步进行的，但是对于提供 NFS 服务的分区来说，这种写入只能是同步的。异步写入允许进行写入批处理，从而加快速度。但NFS服务器从加速的日志存储中获益很多。
由于所有元数据更新都需要被记录在日志中，因此在进行大量元数据操作时，可能会导致日志被洪水般的元数据更新所占满。例如，执行 rm -rf /usr/src/linux 这样的操作就不会特别快，因为元数据更新流最终会导致日志溢出。而且，由于XFS中的其他所有操作都是基于分配组（AG）并行进行的，因此日志是可能引起资源竞争的唯一来源。
大文件和稀疏文件
在 FFS（Unix File System）中，文件通过传统的动态数组（dynamic array）进行映射，该数组包括直接块（direct blocks）和最多三级的间接块（indirect blocks）。在64位文件大小的情况下，这种方式就变得很笨拙：会需要超过三级的间接块，同时会需要大量的数据块。由于大量的数据块的存在，块编号基本上形成了一个递增的数字列表。这不仅会增加管理的复杂性，也会增大存储块编号的空间开销。FFS（以及 EFS）需要在每个块被分配到文件系统缓冲池（filesystem buffer pool）时就确定它们在磁盘上的位置。可以看到，FFS 实际上没有尝试在磁盘上连续布局文件，而是单独放置每个块。XFS 用 extents 取代了这个动态数组。
在文件放置映射（file placement maps）中，这些映射的 extents 是三元组（块偏移量，长度，磁盘块）。这些 extents 被存储在 inode 本身中，直到溢出。然后，XFS 开始在 inode 中创建一个由映射 extents 组成的B+树，通过逻辑块号（logical block number）来索引映射 extents ，以便进行快速查找。
在可以进行连续分配的前提下，这种数据结构允许将大量的块（最多2M个块）压缩为一个单独的描述符。因此，即使是大型文件，也可以在非常少的 extents 中存储，最理想的情况是每个分配组（AG）只需一个 extent。
实现连续布局：延迟分配和预分配
XFS 引入了一个新概念：延迟分配，它可以在文件系统缓冲池中分配虚拟 extent。这些预留的 extent 是用来存放还未写入的数据块，它们在磁盘上还没有确定的物理位置。当进行刷新操作时，这些 extent 会被填充实际的数据，然后按照连续的方式进行布局，并以大块方式进行线性写入。这样的设计可以提高写入操作的效率。
这对文件系统缓冲区的工作方式产生了根本性的改变。以前，通过使用（设备，物理块号）可以标识缓冲区缓存中的块，以防止重复分配缓冲区。然而，当将 XFS 移植到Linux时，如果在普通缓冲区不使用此类标识，最初 Linux 内核无法适应。因此 XFS 需要一个单独的缓冲区缓存。随着移植工作的进行，这个问题后来得到了解决。
为了确保文件可以在单个 extent 中进行存储空间分配而不会出现碎片化，当打开文件时，XFS 会积极为其预分配存储空间。预分配的磁盘空间量是根据文件系统中的可用空间而确定的，默认情况下可能会预分配相当大的空间。
在互联网上，有很多 XFS 用户问到他们的磁盘空间在哪里，答案是“在 /var/log 的打开文件句柄中。此外，查看手册页中关于 allocsize= 的部分，以及 /proc/sys/fs/xfs/speculative_prealloc_lifetime 。
局部性
在提高“局部性”方面，XFS 并不太依赖分配组（AG）来实现。分配组主要用于并发处理。相反，XFS 更多地通过在目录和当前文件的现有块周围放置文件来优化数据的局部性。唯一的例外是“新目录”，这些新目录会被放置在不同的分配组中，远离它们的父目录。
在大文件中，如果需要分配新的 extent，也就是为新的数据块分配空间时，根据论文中提到的规定，“首先靠近 inode ，然后靠近附近的块”。这样的设置方式使得 inode 放置在靠近文件开头的地方，并将后来添加的块放置在已有块的附近。
大目录
在传统的 Unix 文件系统和 BSD FFS 中，目录名称查找是线性操作。对于任何类型的路径名到 inode 的转换，大目录会明显减慢这一过程。
XFS 选择了被广泛使用的 B+ 树作为目录的数据结构。然而，由于键（文件名）是可变长度的结构，与其他文件系统中的树实现完全不同。XFS 的作者不喜欢这种情况，因此对文件名进行了哈希处理，将其转换为一个固定长度的 4 字节名称哈希值。然后，将一个或多个目录条目以（名称，inode）对的形式存储在 B+ 树的值中。通过这种方式，XFS 能够高效地管理目录，并在需要时快速查找和访问特定的文件。这种哈希处理方式允许 XFS 在 B+ 树结构中使用固定长度的键，而不需要关注键的实际长度。
在这方面进行了一些讨论，作者们发现短键可以让每个块存储许多条目，从而形成宽树，进而实现更快的查找速度。他们自豪地宣称：“我们可以拥有数百万条目的目录”，这在以前的 Unix 文件系统中是难以想象的。
大量的代码
在 1994 年的 XFS 基准测试中，XFS 显示出良好的线性扩展表现，能够很好地利用硬件资源。它在 多核的大型机器上表现良好。
XFS 是一个大型文件系统。Linux 的 ext2 有 5,000 行内核代码（和大约10倍这个数量的用户空间代码）。而 XFS 有 50,000 行内核代码，这还不包括 IRIX 卷管理器 XLV（在Linux中，XFS 移植使用的是 LVM2）。
XFS 在 1999 年 5 月以 GNU GPL 许可协议发布，并从 2001 年开始移植到 Linux 内核。截至 2014 年，它在大多数 Linux 发行版中得到支持，RHEL（Red Hat Enterprise Linux）将其作为默认文件系统。
笔者认为，XFS 是具有最佳扩展性、最佳并发能力和修改时间最一致的文件系统，这使得它成为任何类型的数据库使用的首选文件系统。它消除了一些全局锁，这些锁会影响大型文件系统的并发使用和性能，并且使用了具有 O(log(n)) 扩展性的 B+ 树结构，而之前使用的算法扩展性都比较差。使用 extent 还允许动态增加 I/O 大小，有利于提高吞吐量，并与延迟分配的新颖思想一起促进将文件在磁盘上连续地放置或存储。
