在本章中，我们将介绍一个简单的文件系统实现，称为** vsfs (Very simple file system)**。该文件系统是典型UNIX文件系统的简化版本，因此可以引入一些基本的磁盘结构、访问方法和各种策略，您可以在今天的许多文件系统中找到这些内容。<br />文件系统是纯软件； **与我们开发的 CPU 和内存虚拟化不同，我们不会添加硬件功能来使文件系统的某些方面更好地工作（尽管我们会注意设备特性以确保文件系统运行良好）**。 由于我们在构建文件系统方面具有极大的灵活性，因此构建了许多不同的文件系统，从 AFS（ Andrew File System，安德鲁文件系统）[H+88] 到 ZFS（Sun 的 Zettabyte File System）[B07]。 所有这些文件系统都有不同的数据结构，并且在某些方面做得比同行更好或更差。 因此，我们将通过案例研究来学习文件系统：首先，本章中的一个简单文件系统 (vsfs) 介绍了大多数概念，然后对实际文件系统进行了一系列研究，以了解它们在实践中有何不同。
关键的问题：如何实现一个简单的文件系统 我们如何构建一个简单的文件系统?磁盘上需要什么结构?他们需要追踪什么?如何访问它们?
40.1 思考方式 The Way To Think
要考虑文件系统，我们通常建议考虑它们的两个不同方面;如果您理解了这两个方面，就可能理解文件系统基本上是如何工作的。
首先是文件系统的数据结构（data structures）。换句话说，文件系统利用什么类型的磁盘结构来组织它的数据和元数据?我们将看到的第一个文件系统(包括下面的vsfs)使用简单的结构，如块数组或其他对象，而更复杂的文件系统，如 SGI 的 XFS，使用更复杂的基于树的结构 [S+96]。
文件系统的第二个方面是它的访问方法（access methods）。它如何将进程发出的调用（例如 open()、read()、write() 等）映射到其结构上？ 在执行特定系统调用期间读取哪些结构？ 写了哪些？ 所有这些步骤的执行效率如何？
如果您理解了文件系统的数据结构和访问方法，您就开发了一个很好的关于它如何真正工作的思维模型，这是系统思维的一个关键部分。当我们深入研究我们的第一个实现时，试着培养你的思维模型。
Aside：文件系统的思维模型 正如我们之前讨论过的，思维模型是你在学习系统时真正想要养成的东西。 对于文件系统，您的思维模型最终应该包括以下问题的答案：什么磁盘结构存储文件系统的数据和元数据？ 当一个进程打开一个文件时会发生什么？ 在读取或写入期间访问哪些磁盘结构？ 通过研究和改进您的思维模型，您可以对正在发生的事情有一个抽象的理解，而不仅仅是试图理解某些文件系统代码的细节（当然，这也很有用！）。
40.2 整体结构 Overall Organization
我们现在开发 vsfs 文件系统的数据结构的整体磁盘组织。 我们需要做的第一件事是将磁盘分成块（blocks）； 简单的文件系统只使用一种块大小，这正是我们在这里要做的。 让我们选择一个常用的大小为 4 KB。
因此，我们对构建文件系统的磁盘分区的看法很简单：一系列块，每个块的大小为 4 KB。 这些块在大小为 N 4 KB 块的分区中从 0 到 N - 1 寻址。 假设我们有一个非常小的磁盘，只有 64 个块：
现在，让我们考虑一下构建文件系统需要在这些块中存储什么。当然，首先想到的是用户数据。事实上，任何文件系统中的大部分空间都是(也应该是)用户数据。我们把用于存储用户数据的磁盘区域称为数据区域（data region），为了简单起见，为这些块保留磁盘的固定部分，比如磁盘上64块中的最后56块:
正如我们在上一章（一点点）了解到的那样，文件系统必须跟踪有关每个文件的信息。 此信息是元数据（metadata）的关键部分，它跟踪诸如哪些数据块（在数据区域中）构成文件、文件的大小、其所有者和访问权限、访问和修改时间以及其他类似类型的信息等内容。 为了存储这些信息，文件系统通常有一个称为 inode 的结构（我们将在下面阅读有关 inode 的更多信息）。
为了容纳 inode，我们还需要在磁盘上为它们保留一些空间。 我们将磁盘的这一部分称为 inode 表，它仅包含磁盘上的 inode 数组。 因此，我们的磁盘映像现在看起来像这张图片，假设我们将 64 个块中的 5 个用于 inode（在图中用 I 表示）：
这里我们应该注意，inode 通常没有那么大，例如 128 或 256 字节。 假设每个 inode 有 256 个字节，一个 4 KB 的块可以容纳 16 个 inode，我们上面的文件系统总共包含 80 个 inode。 在我们的简单文件系统中，建立在一个 64 块的小分区上，这个数字代表我们文件系统中可以拥有的最大文件数； 但是，请注意，构建在更大磁盘上的相同文件系统可以简单地分配更大的 inode 表，从而容纳更多文件。
到目前为止，我们的文件系统有数据块(D)和 inodes (I)，但仍然缺少一些东西。正如您可能已经猜到的，仍然需要的一个主要组件是跟踪 inodes 或数据块是空闲的还是已分配的。因此，这种分配结构（allocation structures）是任何文件系统中必不可少的元素。
当然，许多分配跟踪方法都是可行的。例如，我们可以使用指向第一个空闲块的空闲链表（free list），然后该空闲块又指向下一个空闲块，以此类推。相反，我们选择一种简单而流行的结构，称为位图（bitmap），一个用于数据区域(数据位图（data bitmap）)，一个用于inode表(inode位图（inode bitmap）)。位图是一个简单的结构:每个位用来指示对应的对象/块是空闲的(0)还是在使用的(1)。这样我们就有了新的磁盘布局，包括一个inode位图(i)和一个数据位图(d):
您可能会注意到，对这些位图使用整个4KB的块有点过分;这样的位图可以跟踪是否分配了32K对象，但我们只有80个节点和56个数据块。然而，为了简单起见，我们只对每个位图使用一个完整的4KB块。
细心的读者（即仍然醒着的读者）可能已经注意到，在我们非常简单的文件系统的磁盘结构设计中还剩下一个块。 我们为超级块（superblock）保留它，在下图中用 S 表示。 超级块包含有关此特定文件系统的信息，例如包括文件系统中有多少 inode 和数据块（在本例中分别为 80 和 56），inode 表从何处开始（块 3），等等。 它还可能包含某种用于标识文件系统类型（在本例中为 vsfs）的幻数（magic number）。
因此，当挂载文件系统时，操作系统将首先读取超级块，以初始化各种参数，然后将卷（volume）附加到文件系统树。当访问卷中的文件时，系统将确切地知道在哪里查找所需的磁盘结构。
40.3 文件结构：Inode File Organization: The Inode
文件系统最重要的磁盘结构之一是 inode； 几乎所有的文件系统都有类似的结构。 名称 inode 是 index node 的缩写，在 UNIX [RT74] 和可能更早的系统中给它的历史名称，使用这个名称是因为这些节点最初排列在一个数组中，并且在访问特定 inode 时索引到该数组中。
Aside：数据结构——索引节点（THE INODE） inode 是许多文件系统中使用的通用名称，用于描述保存给定文件元数据的结构，例如其长度、权限及其组成块的位置。 这个名字至少可以追溯到 UNIX（如果不是更早的系统，可能还可以追溯到 Multics）； 它是 index node 的缩写，因为 inode 编号用于索引磁盘上的 inode 数组，以便找到该编号的 inode。 正如我们将看到的，inode 的设计是文件系统设计的关键部分之一。 大多数现代系统对于它们跟踪的每个文件都有某种类似的结构，但可能将它们称为不同的东西（例如 dnodes、fnodes 等）。
**每个 inode 都由一个数字（称为 i-number）隐式引用，我们之前将其称为文件的低级名称（low-level name）**。 在 vsfs（和其他简单的文件系统）中，给定一个 i-number，您应该能够直接计算出相应 inode 在磁盘上的位置。 比如上面vsfs的inode表：20KB大小（5个4KB块），因此由80个inode组成（假设每个inode为256字节）； 进一步假设 inode 区域从 12KB 开始（即超级块从 0KB 开始，inode 位图在地址 4KB，数据位图在 8KB，因此 inode 表紧随其后）。 因此，在 vsfs 中，我们在文件系统分区的开头（在特写视图中）具有以下布局：<br /><br />为了读取第32个inode，文件系统首先计算到inode区域的偏移量(或8192)，加上磁盘上inode表的起始地址(inodeStartAddr = 12KB)，从而到达所需 inode 块的正确字节地址上：20KB。 回想一下，磁盘不是字节可寻址的，而是由大量可寻址扇区组成，通常为 512 字节。 因此，为了获取包含 inode 32 的 inode 块，文件系统将读取扇区  或 40，以获取所需的 inode 块。 更一般地，inode块的扇区地址 sector 可以计算如下：
blk = (inumber * sizeof(inode_t)) / blockSize;sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;
在每个 inode 中几乎包含您需要的关于文件的所有信息：它的类型（例如，常规文件、目录等）、它的大小、分配给它的块数、保护信息（例如谁拥有该文件、 以及谁可以访问它），一些时间信息，包括文件的创建、修改或上次访问时间，以及有关其数据块在磁盘上的位置的信息（例如，某种类型的指针）。 我们将有关文件的所有此类信息称为**元数据（metadata）**； 事实上，文件系统内的任何不是纯用户数据的信息通常都被称为此类信息。 图 40.1 显示了来自 ext2 [P09] 的示例 inode。
类型信息保存在目录条目中，因此在inode本身中找不到。
Figure 40.1: Simplified Ext2 Inode
inode 设计中最重要的决定之一是它如何引用数据块的位置。 一种简单的方法是在 inode 中有一个或多个直接指针（direct pointers，磁盘地址）； 每个指针指向一个属于该文件的磁盘块。 这种方法是有限的：例如，如果您想要一个非常大的文件（例如，大于了块的大小乘以 inode 中的直接指针数量），那么您就不走运了。
多级索引 The Multi-Level Index
为了支持更大的文件，文件系统设计者不得不在 inode 中引入不同的结构。 一个常见的想法是拥有一个称为间接指针（indirect pointer）的特殊指针。 它不是指向包含用户数据的块，而是指向包含更多指针的块，其中每个指针都指向用户数据。 因此，一个 inode 可能有一些固定数量的直接指针（例如，12）和一个间接指针。 如果文件增长到足够大，则会分配一个间接块（从磁盘的数据块区域），并将用于间接指针的 inode 位置设置为指向它。 假设 4 KB 块和 4 字节磁盘地址（译者注：如40.1图所示，60字节用于一组磁盘指针，共有15个，即一个磁盘指针/磁盘地址为4字节，只是这里假设有12个直接指针和一个间接指针），又增加了 1024 个指针（译者注：这个唯一的间接指针指向了另一个4 KB块，这个块可以装下1024个4字节的磁盘指针）； 文件可以增长到 (12 + 1024) · 4K 或 4144KB。
Tip：考虑基于区段（extents）的方法 另一种方法是使用区段（extents）而不是指针。 区段只是一个磁盘指针加上一个长度（以块为单位）； 因此，不需要为文件的每个块都需要一个指针，只需要一个指针和一个长度来指定文件在磁盘上的位置。 只有一个区段是有局限的，因为在分配文件时可能无法找到连续的磁盘可用空间块。 因此，基于区段的文件系统通常允许多个区段，从而在文件分配期间给予文件系统更多的自由。 在比较这两种方法时，基于指针的方法最灵活，但每个文件使用大量元数据（特别是对于大文件）。 基于区段的方法不太灵活但更紧凑； 特别是，当磁盘上有足够的可用空间并且文件可以连续布局时，它们工作得很好（无论如何，这实际上是任何文件分配策略的目标）。
毫不奇怪，在这种方法中，您可能希望支持更大的文件。 为此，只需为 inode 添加另一个指针：**双间接指针（double indirect pointer）**。 **这个指针指向的是一个包含指向间接块的指针的块，每个间接块都包含指向数据块的指针**。 因此，双间接块增加了使用额外 1024 ·1024 或 100 万个 4KB 块来增长文件的可能性，换句话说，支持大小超过 4GB 的文件。 **不过，您可能想要更多，而且我们打赌您知道这将走向何方：三重间接指针（triple indirect pointer）**。<br />总的来说，这种不平衡的树被称为指向文件块的**多级索引（multi-level index）**方法。 让我们检查一个带有 12 个直接指针以及单和双间接块的示例。 假设块大小为 4 KB，指针为 4 字节，则该结构可以容纳大小略高于 4 GB 的文件（即 (12 + 1024 + 10242) × 4 KB）。 你能算出通过添加三重间接块可以处理多大的文件吗？ （提示：相当大）<br />许多文件系统使用多级索引，包括Linux ext2[P09]和ext3等常用文件系统，NetApp的WAFL，以及最初的UNIX文件系统。 其他文件系统，包括 SGI XFS 和 Linux ext4，使用**区段（extents）**而不是简单的指针； 有关基于区段的方案如何工作的详细信息，请参阅前面Tip中的内容（它们类似于虚拟内存讨论中的段）。<br />**您可能想知道：为什么要使用这样的不平衡树？ 为什么不采用不同的方法？** 好吧，事实证明，许多研究人员都研究了文件系统及其使用方式，而且几乎每次他们都发现了几十年来一直适用的某些“真相（truths）”。 **其中一项发现是大多数文件都很小（most files are small）。 这种不平衡的设计反映了这样一个现实； 如果大多数文件确实很小，则针对这种情况进行优化是有意义的。 因此，使用少量的直接指针（12 是典型数字），一个 inode 可以直接指向 48 KB 的数据，对于较大的文件需要一个（或多个）间接块。** 见 Agrawal 等 [A+07] 用于最近的一项研究； 图 40.2 总结了这些结果。<br /><br />当然，在inode设计的空间里，还有很多其他的可能性； **归根结底，inode只是一个数据结构，任何存储相关信息，并能有效查询的数据结构就足够了**。 由于文件系统软件很容易更改，因此如果工作负载或技术发生变化，您应该愿意探索不同的设计。
40.4 目录结构 Directory Organization
在 vsfs 中（就像在许多文件系统中一样），目录的组织很简单； 一个目录基本上只包含（条目名称，inode 编号）对的列表。 对于给定目录中的每个文件或目录，目录的数据块中有一个字符串和一个数字。 对于每个字符串，也可能有一个长度（假设名称可变）。
例如，假设目录 dir（inode 编号 5）中有三个文件（foo、bar 和 foobar 是一个很长的名称），inode 编号分别为 12、13 和 24。 dir 的磁盘数据可能如下所示：
在此示例中，每个条目都有一个 inode 编号（inode number）、记录长度（record length，名称加上任何剩余空间的总字节数）、字符串长度（string length，名称的实际长度），最后是条目的名称。 请注意，每个目录都有两个额外的条目， . “点”和 ..“点-点”； dot 目录只是当前目录（在本例中为 dir），而 dot-dot 是父目录（在本例中为根目录）。
删除文件（例如，调用 unlink()）可能会在目录中间留下一个空白空间，因此也应该有某种方法来标记它（例如，使用保留的 inode 编号，例如零）。 这样的删除是使用记录长度（record length）的一个原因：新条目可能会重用旧的、更大的条目，因此其中有额外的空间。
Aside：基于链表（LINKED-BASED）的方法 设计 inode 的另一种更简单的方法是使用链表（linked list）。 因此，在 inode 内部，您只需要一个指向文件的第一个块的指针，而不是有多个指针。 要处理更大的文件，请在该数据块的末尾添加另一个指针，依此类推，这样您就可以支持大文件。 您可能已经猜到了，链接文件分配（linked file allocation）对于某些工作负载的性能很差； 例如，考虑读取文件的最后一个块，或者只是进行随机访问。 因此，为了使链接分配更好地工作，一些系统会在内存中保存链接信息表（table of link information），而不是将下一个指针与数据块本身一起存储。 该表由数据块D的地址索引； 条目的内容只是 D 的下一个指针，即文件中 D 之后的下一个块的地址。空值也可能在那里（表示文件结束），或其他一些标记来表示特定块是空闲的。 拥有这样一个下一个指针表（a table of next pointers）使得链接分配方案可以有效地进行随机文件访问，只需首先扫描（在内存中）表以找到所需的块，然后直接访问（在磁盘上）它。 这样的表是不是很耳熟？ 我们所描述的是所谓的文件分配表（file allocation table）或 FAT 文件系统（FAT file system）的基本结构。 是的，这个经典的旧 Windows 文件系统，在 NTFS [C94] 之前，是基于一个简单的基于链接的分配方案。 与标准 UNIX 文件系统还有其他不同之处。 例如，本身没有 inode，而是存储有关文件的元数据并直接引用所述文件的第一个块的目录条目，这使得创建硬链接变得不可能。 参见 Brouwer [B02] 了解更多不优雅的细节。
您可能想知道目录的确切存储位置。** 通常，文件系统将目录视为一种特殊类型的文件。 因此，目录有一个 inode，位于 inode 表的某处（inode 的类型字段标记为“目录”而不是“常规文件”）**。 **该目录具有由 inode 指向的数据块（可能还有间接块）； 这些数据块位于我们简单文件系统的数据块区域中。 因此，我们的磁盘结构保持不变。**<br />我们还应该再次注意到，**这个简单的目录条目线性列表并不是存储此类信息的唯一方法**。和前面一样，任何数据结构都是可能的。例如，XFS [S+96]以B-树的形式存储目录，使得文件创建操作(必须确保在创建文件名之前没有使用它)比使用简单列表的系统更快，而这些简单列表必须全部扫描。
Aside：空闲空间管理 管理空闲空间的方法有很多； 位图只是一种方式。 一些早期的文件系统使用空闲列表（free lists），其中超级块中的单个指针指向第一个空闲块； 在那个块内，下一个空闲指针被保存，从而通过系统的空闲块形成一个链表。 当需要一个块时，使用头块并相应地更新链表。 现代文件系统使用更复杂的数据结构。 例如，SGI 的 XFS [S+96] 使用某种形式的 B 树（B-tree）来紧凑地表示磁盘的哪些块是空闲的。 与任何数据结构一样，不同的时空权衡是可能的。
40.5 空闲空间管理 Free Space Management
文件系统必须跟踪哪些 inode 和数据块是空闲的，哪些不是，以便在分配新文件或目录时，可以为其找到空间。 因此，空闲空间管理（free space management）对所有文件系统都很重要。 在 vsfs 中，我们有两个用于此任务的简单位图。
例如，当我们创建一个文件时，我们必须为该文件分配一个 inode。 因此，文件系统将在位图中搜索空闲的 inode，并将其分配给文件； 文件系统必须将 inode 标记为已使用（使用 1），并最终使用正确的信息更新磁盘位图。 分配数据块时会发生一组类似的活动。
在为新文件分配数据块时，也可能需要考虑其他一些因素。 例如，某些 Linux 文件系统，例如 ext2 和 ext3，会在创建新文件并需要数据块时查找一系列空闲的块（比如 8 个）； 通过找到这样一个空闲块序列，然后将它们分配给新创建的文件，文件系统可以保证文件的一部分在磁盘上是连续的，从而提高性能。 因此，这种预分配策略是为数据块分配空间时常用的启发式方法。
40.6 访问路径：读和写 Access Paths: Reading and Writing
现在我们对文件和目录如何存储在磁盘上有了一些了解，我们应该能够在读取或写入文件的活动期间遵循操作流程。 因此，了解在此访问路径（access path）上发生了什么是了解文件系统如何工作的第二个关键； 请注意！
对于以下示例，让我们假设文件系统已安装，因此超级块已在内存中（译者注：挂载文件系统时，操作系统首先读取超级块，超级块即到了内存中）。 其他所有内容（即 inode、目录）仍在磁盘上。
从磁盘读取一个文件 Reading A File From Disk
在这个简单的例子中，让我们首先假设您只想打开一个文件（例如 /foo/bar），读取它，然后关闭它。 对于这个简单的例子，我们假设文件只有 12KB（即 3 个块）。
当您发出 open(“/foo/bar”, O_RDONLY) 调用时，文件系统首先需要找到文件 bar 的 inode，以获取文件的一些基本信息（权限信息、文件大小等） . 为此，文件系统必须能够找到 inode，但它现在所拥有的只是完整路径名。 文件系统必须遍历（traverse）路径名，从而找到所需的 inode。
所有遍历都从文件系统的根目录开始，在根目录中简称为 /。 因此，FS 将从磁盘读取的第一件事是根目录的 inode。 但是这个 inode 在哪里呢？ 要找到一个 inode，我们必须知道它的 i-number。 通常，我们会在其父目录中查找文件或目录的 i-number； 根没有父级（根据定义）。 因此，根 inode 编号必须是“众所周知的”； 当文件系统被挂载时，FS 必须知道它是什么。 在大多数 UNIX 文件系统中，根 inode 编号为 2。因此，要开始该过程，FS 读取包含 inode 编号 2 的块（第一个 inode 块）。
一旦 inode 被读入，FS 就可以查看它的内部以找到指向包含根目录内容的数据块的指针。 因此，FS 将使用这些磁盘上的指针来读取目录，在这种情况下查找 foo 的条目。 通过读入一个或多个目录数据块，它会找到 foo 的条目； 一旦找到，FS 也将找到接下来需要的 foo 的 inode 编号（假设它是 44）。
下一步是递归遍历路径名，直到找到所需的 inode。 在本例中，FS 读取包含 foo 的 inode 的块，然后读取其目录数据，最终找到 bar 的 inode 编号。 open() 的最后一步是将 bar 的 inode 读入内存； 然后 FS 进行最后的权限检查，在每个进程打开文件表（per-process open-file table）（译者注：这里指的是文件描述符表，注意与系统级的打开文件表区别开）中为此进程分配一个文件描述符，并将其返回给用户。
Aside：读取不访问分配结构（READS DON’T ACCESS ALLOCATION STRUCTURES） 我们已经看到许多学生对位图等分配结构感到困惑。 特别是，许多人通常认为，当您只是读取文件而不分配任何新块时，仍会参考位图。 这不是真的！ 分配结构（Allocation structures），例如位图，仅在需要分配时访问。 inode、目录和间接块具有完成读取请求所需的所有信息； 当 inode 已经指向块时，无需确保块已经被分配。
**一旦打开，程序就可以发出 read() 系统调用来读取文件。 因此，第一次读取（在偏移量 0 处，除非调用了 lseek()），因此将读取文件的第一个块，查询 inode 以找到这样一个块的位置； 它还可以使用新的上次访问时间更新 inode。 读取将进一步更新此文件描述符的内存中的打开文件表（译者注：这里指文件描述符表），更新文件偏移量，以便下一次读取将读取第二个文件块等。**<br />在某些时候，文件将被关闭。 这里要做的工作要少得多； **显然，文件描述符应该被释放，但现在，这就是 FS 真正需要做的。 不发生磁盘 I/O。**<br />整个过程的描述见图 40.3 ； 时间在图中向下增加。 **在图中，open 导致进行大量读取以最终定位文件的 inode。 之后，读取每个块需要文件系统首先查询 inode，然后读取该块，然后通过写入更新 inode 的 last-accessed-time 字段。** 花一些时间并了解正在发生的事情。<br /><br />**Figure 40.3: File Read Timeline (Time Increasing Downward)**<br />另请注意，**open 生成的 I/O 量与路径名的长度成正比。 对于路径中的每个附加目录，我们必须读取其 inode 及其数据。 更糟糕的是存在大目录； 在这里，我们只需要读取一个块来获取目录的内容，而对于一个大目录，我们可能需要读取许多数据块才能找到所需的条目。 是的，读取文件时生活会变得很糟糕； 正如您即将发现的那样，写入一个文件（尤其是创建一个新文件）甚至更糟。**
写一个文件到磁盘 Writing A File To Disk
写入文件是一个类似的过程。 首先，必须打开文件（如上）。 然后，应用程序可以发出 write() 调用以使用新内容更新文件。 最后，文件被关闭。
与读取不同，写入文件也可能分配（allocate）一个块（例如，除非该块被覆盖）。 在写出一个新文件时，每次写入不仅要向磁盘写入数据，还必须首先决定将哪个块分配给文件，从而相应地更新磁盘的其他结构（例如，数据位图和 inode）。 因此，每次写入文件在逻辑上会生成五个 I/O：一个读取数据位图（然后更新以将新分配的块标记为已使用），一个写入位图（将其新状态反映到磁盘） ，另外第二个读取然后写入 inode（使用新块的位置更新），最后一个写入实际块本身。
考虑到文件创建等简单而常见的操作时，写入流量（traffic）甚至更糟。 要创建文件，文件系统不仅要分配一个 inode，还要在包含新文件的目录中分配空间。 这样做的 I/O 流量总量相当高：一次读取 inode 位图（以找到空闲的 inode），一次写入 inode 位图（以标记它已分配），一次写入新的 inode 本身（ 初始化它），一个到目录的数据（将文件的高级名称链接到它的 inode 号），以及一个对目录 inode 的读写以更新它。 如果目录需要增长以容纳新条目，则还需要额外的 I/O（即数据位图和新目录块）。 所有这一切只是为了创建一个文件！
让我们看一个具体的例子，其中创建了文件 /foo/bar，并向其中写入了三个块。 图 40.4 显示了 open()（创建文件）和三个 4KB 写入中的每一个期间发生的情况。
Figure 40.4: File Creation Timeline (Time Increasing Downward)
在图中，对磁盘的读取和写入被分组，系统调用导致它们发生，它们可能发生的粗略顺序从图的顶部到底部。 您可以看到创建文件需要多少工作：在本例中为 10 个 I/O，遍历路径名，然后最终创建文件。 您还可以看到，每个分配写入需要 5 个 I/O：一对读取和更新 inode，另一对读取和更新数据位图，最后是数据本身的写入。 文件系统如何以合理的效率完成这些工作？
关键的问题：如何降低文件系统I/O成本 即使是最简单的操作，如打开、读取或写入文件，也会产生大量分散在磁盘上的 I/O 操作。 文件系统可以做些什么来降低执行如此多 I/O 的高成本？
40.7
缓存和缓冲 Caching and Buffering
如上例所示，读取和写入文件可能很昂贵，会导致对（慢速）磁盘的许多 I/O。 为了解决这个显然的巨大性能问题，大多数文件系统积极使用系统内存 (DRAM) 来缓存重要的块。
想象一下上面的打开示例：如果没有缓存，每个打开的文件都需要对目录层次结构中的每一级至少进行两次读取（一次读取相关目录的 inode，至少一次读取其数据）。 使用长路径名（例如，/1/2/3/ … /100/file.txt），文件系统实际上会执行数百次读取来打开文件！
早期的文件系统因此引入了固定大小的缓存（fixed-size cache）来保存常用的块。 正如我们对虚拟内存的讨论，诸如 LRU 和不同变体之类的策略将决定将哪些块保留在缓存中。 这个固定大小的缓存通常会在启动时分配到大约总内存的 10%。
然而，这种内存的静态划分可能是浪费的。 如果文件系统在给定的时间点不需要 10% 的内存怎么办？ 使用上述固定大小的方法，文件缓存中未使用的页面不能重新用于其他用途，从而浪费掉。
相反，现代系统采用动态划分（dynamic partitioning）方法。 具体来说，许多现代操作系统将虚拟内存页面和文件系统页面集成到一个统一的页面缓存（unified page cache）中 [S00]。 通过这种方式，可以更灵活地跨虚拟内存和文件系统分配内存，具体取决于在给定时间哪个需要更多内存。
现在想象一下带有缓存的文件打开示例。 第一次打开可能会产生大量 I/O 流量来读取目录 inode 和数据，但随后打开同一文件（或同一目录中的文件）的文件将几乎全部命中缓存，因此不需要 I/O。
Tip：理解静态划分和动态划分 在不同的客户端/用户之间划分资源时，您可以使用静态划分或动态划分（static partitioning or dynamic partitioning）。 静态方法只是简单地将资源一次分成固定比例； 例如，如果有两个可能的内存用户，您可以将一些固定的内存分配给一个用户，其余的给另一个用户。 动态方法更灵活，随着时间的推移提供不同数量的资源； 例如，一个用户可能会在一段时间内获得更高比例的磁盘带宽，但随后系统可能会切换并决定为不同的用户提供更大比例的可用磁盘带宽。 每种方法都有其优点。 静态划分可确保每个用户获得一定的资源份额，通常提供更可预测的性能，并且通常更容易实现。 动态划分可以实现更好的利用率（通过让资源匮乏的用户消耗其他空闲资源），但实现起来可能更复杂，而且如果用户的空闲资源被其他用户占用，并且需要很长时间才能回收，则会导致性能下降 。 通常情况下，没有最好的方法。 相反，您应该考虑手头的问题并决定哪种方法最合适。 确实，你不应该一直这样做吗？
让我们也考虑一下缓存对写入的影响。虽然可以通过足够大的缓存完全避免读取 I/O，但写入流量必须转到磁盘才能保持持久。因此，缓存对写入流量的过滤器（filter）与读取流量的过滤器不同。也就是说，写缓冲（write buffering，有时被这样称作）当然具有许多性能优势。首先，通过延迟写入，文件系统可以将一些更新批处理（batch）到更小的 I/O 集；例如，如果 inode 位图在创建一个文件时更新，然后在片刻之后创建另一个文件时更新，文件系统会通过在第一次更新后延迟写入来节约一次 I/O。其次，通过在内存中缓冲大量写入，系统可以调度（schedule）后续的 I/O，从而提高性能。最后，通过延迟它们完全避免了一些写入；例如，如果应用程序创建一个文件然后删除它，则将文件创建延迟写入
磁盘，可以完全避免（avoid）写入。在这种情况下，懒惰（在将块写入磁盘时）是一种美德。
由于上述原因，大多数现代文件系统在内存中缓冲写入 5 到 30 秒，这代表了另一种权衡：如果系统在更新传播到磁盘之前崩溃，更新就会丢失； 但是，通过在内存中保持写入更长时间，可以通过批处理、调度甚至避免写入来提高性能。
Tip：理解持久性/性能的权衡 存储系统通常会为用户带来持久性/性能的权衡。如果用户希望写入的数据立即持久化，则系统必须全力以赴将新写入的数据提交到磁盘，因此写入速度很慢（但很安全）。但是，如果用户可以容忍少量数据丢失，系统可以将写入在内存中缓冲一段时间，然后再写入磁盘（在后台）。这样做会使写入看起来很快完成，从而提高感官性能；但是，如果发生崩溃，尚未提交到磁盘的写入将丢失，因此需要权衡。要了解如何正确进行这种权衡，最好了解使用存储系统的应用程序需要什么；例如，虽然丢失 Web 浏览器下载的最后几张图像可能是可以容忍的，但丢失向您的银行帐户添加资金的部分数据库交易可能不太能容忍。当然，除非你很富有；既然如此，你何必那么在意囤积每一分钱呢？
某些应用程序（例如数据库）不喜欢这种权衡。 因此，为了避免由于写缓冲而导致的意外数据丢失，他们只是通过调用 fsync()、使用绕过缓存的**直接 I/O （direct I/O）**接口或通过使用**原始磁盘（raw disk）**接口并完全避免文件系统来强制写入磁盘。 虽然大多数应用程序都在忍受文件系统所做的权衡，但如果默认设置不令人满意，则有足够的控件可以让系统执行您想要的操作。
参加数据库课程以了解更多关于老式数据库的信息以及他们以前坚持避免使用操作系统并自己控制一切。 但是要小心！ 那些搞数据库的人总是试图对操作系统说坏话。 为你感到羞耻，数据库人。 耻辱。
40.8 总结
Summary
我们已经看到了构建文件系统所需的基本机制。 每个文件都需要一些信息（元数据），通常存储在称为 inode 的结构中。 目录只是一种存储名称→inode-number 映射的特定类型的文件。 还需要其他结构； 例如，文件系统通常使用位图等结构来跟踪哪些 inode 或数据块是空闲的或已分配的。
文件系统设计的绝妙之处在于它的自由； 我们在接下来的章节中探索的文件系统都利用这种自由来优化文件系统的某些方面。 显然，我们还没有探索许多策略决定。 例如，当创建一个新文件时，它应该放在磁盘上的什么位置？ 该策略和其他策略也将成为未来章节的主题。 或者他们会吗？
尾白神秘的音乐，让您对文件系统主题更加感兴趣。
References
[A+07] “A Five-Year Study of File-System Metadata” by Nitin Agrawal, William J. Bolosky,
John R. Douceur, Jacob R. Lorch. FAST ’07, San Jose, California, February 2007.
最近对文件系统实际使用方式的出色分析。 使用其中的参考书目追踪 1980 年代初期的文件系统分析论文。
[B07] “ZFS: The Last Word in File Systems” by Jeff Bonwick and Bill Moore. https://pages.cs.wisc.edu/~remzi/OSTEP/Citations/zfs_last.pdf
最新的重要文件系统之一，功能齐全，功能强大。 我们应该有一章关于它，也许很快就会有。
[B02] “The FAT File System” by Andries Brouwer.
September, 2002. https://www.win.tue.nl/~aeb/linux/fs/fat/fat.html
对 FAT 的清晰描述。 文件系统类型，而不是培根类型。 虽然你不得不承认，培根脂肪可能味道更好。
[C94] “Inside the Windows NT File System” by Helen Custer. Microsoft Press, 1994.
一本关于 NTFS 的小书； 其他地方可能有更多技术细节。
[H+88] “Scale and Performance in a Distributed File System” by John H. Howard, Michael
L. Kazar, Sherri G. Menees, David A. Nichols, M. Satyanarayanan, Robert N. Sidebotham,
Michael J. West.. ACM TOCS, Volume 6:1, February 1988.
典型的分布式文件系统;我们稍后会了解更多，别担心。
[P09] “The Second Extended File System: Internal Layout” by Dave Poirier. 2009. http://www.nongnu.org/ext2-doc/ext2.html
ext2是一个非常简单的Linux文件系统，基于FFS (Berkeley Fast file system)。我们会在下一章读到它。
[RT74] “The UNIX Time-Sharing System” by M. Ritchie, K. Thompson. CACM Volume 17:7,
1974.
关于UNIX的原始论文。阅读它，了解现代操作系统的基础。
[S00] “UBC: An Efficient Unified I/O and Memory Caching Subsystem for NetBSD” by Chuck
Silvers. FREENIX, 2000.
这是一篇关于NetBSD集成文件系统缓存和虚拟内存页面缓存的好文章。许多其他系统也做同样的事情。
[S+96] “Scalability in the XFS File System” by Adan Sweeney, Doug Doucette, Wei Hu, Curtis
Anderson, Mike Nishimoto, Geoff Peck. USENIX ’96, January 1996, San Diego, California.
第一次尝试使操作具有可扩展性，包括在目录中拥有数百万个文件之类的事情，这是一个中心焦点。 将想法推向极致的一个很好的例子。 这个文件系统背后的关键思想：一切都是一棵树。 我们也应该有一个关于这个文件系统的章节。
Homework (Simulation)
使用这个工具 vsfs.py 来研究文件系统状态如何随着各种操作的发生而变化。 文件系统以空状态开始，只有一个根目录。 随着模拟的进行，会执行各种操作，从而缓慢地改变文件系统的磁盘状态。 有关详细信息，请参阅自述文件。
Questions
- 使用一些不同的随机种子(比如17、18、19、20)运行模拟器，看看您是否能够找出在每个状态更改之间必须发生哪些操作。
- 现在执行相同的操作，使用不同的随机种子(比如21,22,23,24)，除了使用-r标志运行之外，这样就可以在显示操作时猜测状态的变化。关于inode和数据块分配算法，您能得出什么结论?它们更喜欢分配哪些块?
- 现在将文件系统中的数据块数量减少到非常低的数量(比如两个)，并为100个左右的请求运行模拟器。在这种高度受限的布局中，文件系统最终会包含哪些类型的文件?什么类型的操作会失败?
- 现在执行同样的操作，但是使用inode。对于非常少的inode，哪些类型的操作可以成功?哪一个通常会失败?文件系统的最终状态可能是什么?
若有收获，就点个赞吧
0 人点赞
