单机数据持久-文件系统实现

type

status

date

slug

summary

整体组织

需要做的第一件事是将磁盘分成块（block）。简单的文件系统只使用一种块大小，这里正是这样做的，选择常用的4KB。

构建文件系统的磁盘分区：一系列块，每块大小为4KB。在大小为N个4KB块的分区中，这些块的地址为从0到N−1。假设有一个非常小的磁盘，只有64块：

为了构建文件系统，需要在这些块中存储什么。当然，首先想到的是用户数据。将用于存放用户数据的磁盘区域称为数据区域（data region），简单起见，将磁盘的固定部分留给这些块，例如磁盘上64个块的最后56个：

文件系统还必须记录每个文件的信息，该信息是元数据（metadata）的关键部分。为了存储这些信息，文件系统通常有一个名为inode的结构。为了存放inode，还需要在磁盘上留出一些空间。将这部分磁盘称为inode表（inode table），它只是保存了一个磁盘上inode的数组。因此，假设将64个块中的5块用于inode，磁盘映像看起来如下：

inode通常不是那么大，假设每个inode有256字节，一个4KB块可以容纳16个inode，而上面的文件系统则包含80个inode。在简单的文件系统中，这个数字表示文件系统中可以拥有的最大文件数量。

还需要某种方法来记录inode或数据块是空闲还是已分配。当然，可能有许多分配记录方法。我们选择一种简单而流行的结构，称为位图（bitmap），一种用于数据区域（数据位图，data bitmap），另一种用于inode表（inode位图，inode bitmap）。位图是一种简单的结构：每个位用于指示相应的对象/块是空闲（0）还是正在使用（1）。因此新的磁盘布局如下，包含inode位图（i）和数据位图（d）：

在极简文件系统的磁盘结构设计中，还有一块。将它保留给超级块（superblock），用S表示。超级块包含关于该特定文件系统的信息，包括例如文件系统中有多少个inode和数据块、inode表的开始位置等等。它可能还包括一些幻数，来标识文件系统类型。

在挂载文件系统时，操作系统将首先读取超级块，初始化各种参数，然后将该卷添加到文件系统树中。当卷中的文件被访问时，系统就会知道在哪里查找所需的磁盘上的结构。

文件组织：inode

文件系统最重要的磁盘结构之一是inode，几乎所有的文件系统都有类似的结构。

数据结构—— inode：inode 是许多文件系统中使用的通用名称，用于描述保存给定文件的元数据的结构，例如其长度、权限以及其组成块的位置。它是index node（索引节点）的缩写，因为inode号用于索引磁盘上的inode数组，以便查找该inode号对应的inode。inode的设计是文件系统设计的一个关键部分。大多数现代系统对于它们记录的每个文件都有这样的结构，但也许用了不同的名字（如dnodes、fnodes 等）。

每个inode都由一个数字（称为inumber）隐式引用，之前称之为文件的低级名称（low-levelname）。在VSFS（和其他简单的文件系统）中，给定一个inumber，能够直接计算磁盘上相应节点的位置。假设inode区域从12KB开始（即超级块从0KB开始，inode位图在4KB地址，数据位图在8KB，因此inode表紧随其后）。因此，在VSFS中为文件系统分区的开头提供了以下布局：

要读取inode号32，文件系统首先会计算inode区域的偏移量（32×inode的大小，即8192），将它加上磁盘inode表的起始地址（inodeStartAddr = 12KB），从而得到希望的inode块的正确字节地址：20KB。回想一下，磁盘不是按字节可寻址的，而是由大量可寻址扇区组成，通常是512字节。因此，为了获取包含索引节点32的索引节点块，文件系统将向节点（即40）发出一个读取请求，取得期望的inode块。

更一般地说，inode 块的扇区地址iaddr可以计算如下：

在每个inode中，实际上是所有关于文件的信息：文件类型（例如，常规文件、目录等）、大小、分配给它的块数、保护信息（如谁拥有该文件以及谁可以访问它）、一些时间信息（包括文件创建、修改或上次访问的时间文件下），以及有关其数据块驻留在磁盘上的位置的信息（如某种类型的指针）。我们将所有关于文件的信息称为元数据（metadata）。

设计inode时，最重要的决定之一是它如何引用数据块的位置。一种简单的方法是在inode中有一个或多个直接指针（磁盘地址）。每个指针指向属于该文件的一个磁盘块。这种方法有局限：例如，如果你想要一个非常大的文件，那就无法实现了。

多级索引

为了支持更大的文件，文件系统设计者必须在inode中引入不同的结构。一个常见的思路是有一个称为间接指针（indirect pointer）的特殊指针。它不是指向包含用户数据的块，而是指向包含更多指针的块，每个指针指向用户数据。因此，inode可以有一些固定数量（例如12个）的直接指针和一个间接指针。如果文件变得足够大，则会分配一个间接块（来自磁盘的数据块区域），并将inode的间接指针设置为指向它。假设一个块是4KB，磁盘地址是4字节，那就增加了1024个指针。文件可以增长到（12 + 1024）×4KB，即4144KB。

另一种方法是使用范围（extent）而不是指针。范围就是一个磁盘指针加一个长度（以块为单位）。因此，不需要指向文件的每个块的指针，只需要指针和长度来指定文件的磁盘位置。不过只有一个范围是有局限的，因为分配文件时可能无法找到连续的磁盘可用空间块。因此，基于范围的文件系统通常允许多个范围，从而在文件分配期间给予文件系统更多的自由。

在间接指针这种方法中，可能希望支持更大的文件。为此，只需添加另一个指向inode的指针：双重间接指针（double indirect pointer）。该指针指的是一个包含间接块指针的块，每个间接块都包含指向数据块的指针。因此，双重间接块提供了可能性，允许使用额外的1024×1024个4KB块来增长文件，换言之，支持超过4GB大小的文件。

这种不平衡树被称为指向文件块的多级索引（multi-level index）方法。许多文件系统使用多级索引，包括常用的文件系统，如Linux ext2和ext3，以及原始的UNIX文件系统。其他文件系统，包括Linux ext4，使用范围而不是简单的指针。

为什么使用这样的不平衡树？其中一个原因是，大多数文件很小。这种不平衡的设计反映了这样的现实。如果大多数文件确实很小，那么为这种情况优化是有意义的。

目录组织

在VSFS中（像许多文件系统一样），目录的组织很简单。一个目录基本上只包含一个二元组（条目名称，inode号）的列表。对于给定目录中的每个文件或目录，目录的数据块中都有一个字符串和一个数字。对于每个字符串，可能还有一个长度（假定采用可变大小的名称）。

例如，假设目录dir（inode号是5）中有3 个文件（foo、bar 和foobar），inode号分别为12、13 和24。dir 在磁盘上的数据可能如下所示：

每个条目都有一个inode 号，记录长度（名称的总字节数加上所有的剩余空间），字符串长度（名称的实际长度），最后是条目的名称。请注意，每个目录有两个额外的条目：.（点）和..（点点）。点目录就是当前目录（本例中为dir），而点点是父目录（本例中是根目录）。

删除一个文件（例如调用unlink()）会在目录中间留下一段空白空间，因此应该有一些方法来标记它（例如，用一个保留的inode 号，比如0）。这种删除是使用记录长度的一个原因：新条目可能会重复使用旧的、更大的条目，从而在其中留有额外的空间。

通常，文件系统将目录视为特殊类型的文件。因此，目录有一个inode，位于inode表中的某处（inode表中的inode标记为“目录”的类型字段，而不是“常规文件”）。该目录具有由inode 指向的数据块（也可能是间接块）。这些数据块存在于简单文件系统的数据块区域中。磁盘结构因此保持不变。

空闲空间管理

文件系统必须记录哪些inode 和数据块是空闲的，哪些不是，这样在分配新文件或目录时，就可以为它找到空间。因此，空闲空间管理（free space management）对于所有文件系统都很重要。在VSFS 中，用两个简单的位图来完成这个任务。

例如，当创建一个文件时，必须为该文件分配一个inode。文件系统将通过位图搜索一个空闲的内容，并将其分配给该文件。文件系统必须将inode 标记为已使用（用1），并最终用正确的信息更新磁盘上的位图。分配数据块时会发生类似的一组活动。

为新文件分配数据块时，还可能会考虑其他一些注意事项。例如，一些Linux 文件系统（如ext2 和ext3）在创建新文件并需要数据块时，会寻找一系列空闲块（如8 块）。通过找到这样一系列空闲块，然后将它们分配给新创建的文件，文件系统保证文件的一部分将在磁盘上并且是连续的，从而提高性能。因此，这种预分配（pre-allocation）策略，是为数据块分配空间时的常用启发式方法。

管理空闲空间可以有很多方法，位图只是其中一种。一些早期的文件系统使用空闲列表（free list），其中超级块中的单个指针保持指向第一个空闲块。在该块内部保留下一个空闲指针，从而通过系统的空闲块形成列表。在需要块时，使用头块并相应地更新列表。

现代文件系统使用更复杂的数据结构。例如，SGI 的XFS使用某种形式的B 树（B-tree）来紧凑地表示磁盘的哪些块是空闲的。与所有数据结构一样，不同的时间-空间折中也是可能的。

访问路径：读取和写入

假设文件系统已经挂载，因此超级块已经在内存中。其他所有内容（如inode、目录）仍在磁盘上。

从磁盘读取文件

当发出一个open("/foo/bar", O_RDONLY)调用时，文件系统首先需要找到文件bar的inode，从而获取关于该文件的一些基本信息（权限信息、文件大小等等）。为此，文件系统必须能够找到inode，但它现在只有完整的路径名。文件系统必须遍历路径名，从而找到所需的inode。

所有遍历都从文件系统的根开始，即根目录（root directory），它就记为/。因此，文件系统的第一次磁盘读取是根目录的inode。但是这个inode在哪里？要找到inode，必须知道它的i-number。通常，在其父目录中找到文件或目录的i-number。根没有父目录（根据定义）。因此，根的inode号必须是“众所周知的”。在挂载文件系统时，文件系统必须知道它是什么。在大多数UNIX文件系统中，根的inode号为2。因此，要开始该过程，文件系统会读入inode号2的块（第一个inode块）。

一旦inode被读入，文件系统可以在其中查找指向数据块的指针，数据块包含根目录的内容。因此，文件系统将使用这些磁盘上的指针来读取目录，寻找foo的条目。通过读入一个或多个目录数据块，它将找到foo的条目。一旦找到，文件系统也会找到下一个需要的foo的inode号。

下一步是递归遍历路径名，直到找到所需的inode。在这个例子中，文件系统读取包含foo的inode及其目录数据的块，最后找到bar的inode号。open()的最后一步是将bar的inode读入内存。然后文件系统进行最后的权限检查，在每个进程的打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。

打开后，程序可以发出read()系统调用，从文件中读取。第一次读取（除非lseek()已被调用，则在偏移量0处）将在文件的第一个块中读取，查阅inode以查找这个块的位置。它也会用新的最后访问时间更新inode。读取将进一步更新此文件描述符在内存中的打开文件表，更新文件偏移量，以便下一次读取会读取第二个文件块，等等。

整个流程总结起来就是：先打开文件，然后递归地多次读取，以便最终找到文件的inode。之后，读取每个块需要文件系统首先查询inode，然后读取该块，再更新inode的最后访问时间字段。

写入磁盘

写入文件是一个类似的过程。首先，文件必须打开。其次，应用程序可以发出write()调用以用新内容更新文件。最后，关闭该文件。

与读取不同，写入文件也可能会分配（allocate）一个块（除非块被覆写）。当写入一个新文件时，每次写入操作不仅需要将数据写入磁盘，还必须首先决定将哪个块分配给文件，从而相应地更新磁盘的其他结构（例如数据位图和inode）。因此，每次写入文件在逻辑上会导致5个I/O：一个读取数据位图（然后更新以标记新分配的块被使用），一个写入位图（将它的新状态存入磁盘），再是两次读取，然后写入inode（用新块的位置更新），最后一次写入真正的数据块本身。

考虑简单和常见的操作（例如文件创建），写入的工作量更大。要创建一个文件，文件系统不仅要分配一个inode，还要在包含新文件的目录中分配空间。这样做的I/O工作总量非常大：一个读取inode位图（查找空闲inode），一个写入inode位图（将其标记为已分配），一个写入新的inode本身（初始化它），一个写入目录的数据（将文件的高级名称链接到它的inode号），以及一个读写目录inode以便更新它。如果目录需要增长以容纳新条目，则还需要额外的I/O（即数据位图和新目录块）。

一个具体的例子，创建file/foo/bar，并且向它写入了 3 个块：

在该表中，对磁盘的读取和写入放在导致它们发生的系统调用之下，它们可能发生的大致顺序从表的顶部到底部依次进行。在这种情况下，有10 次I/O，用于遍历路径名，然后创建文件。每个分配写入需要5 次I/O：一对读取和更新inode，另一对读取和更新数据位图，最后写入数据本身。文件系统如何以合理的效率完成这些任务？

即使是最简单的操作，如打开、读取或写入文件，也会产生大量I/O 操作，分散在磁盘上。文件系统可以做些什么，来降低执行如此多I/O 的高成本？

缓存和缓冲

读取和写入文件可能是昂贵的，会导致（慢速）磁盘的许多I/O。这显然是一个巨大的性能问题，为了弥补，大多数文件系统积极使用系统内存（DRAM）来缓存重要的块。

没有缓存，每个打开的文件都需要对目录层次结构中的每个级别至少进行两次读取（一次读取相关目录的inode，并且至少有一次读取其数据）。使用长路径名（例如，/1/2/3/…/100/file.txt），文件系统只是为了打开文件，就要执行数百次读取！

早期的文件系统因此引入了一个固定大小的缓存（fixed-size cache）来保存常用的块。正如虚拟内存时一样，LRU 及不同变体策略会决定哪些块保留在缓存中。这个固定大小的缓存通常会在启动时分配，大约占总内存的10%。

然而，这种静态的内存划分（static partitioning）可能导致浪费。如果文件系统在给定的时间点不需要10%的内存，该怎么办？使用上述固定大小的方法，文件高速缓存中的未使用页面不能被重新用于其他一些用途，因此导致浪费。

相比之下，现代系统采用动态划分（dynamic partitioning）方法。具体来说，许多现代操作系统将虚拟内存页面和文件系统页面集成到统一页面缓存中（unified page cache）。通过这种方式，可以在虚拟内存和文件系统之间更灵活地分配内存，具体取决于在给定时间哪种内存需要更多的内存。

静态方法简单地将资源一次分成固定的比例。动态方法更灵活，随着时间的推移提供不同数量的资源。

每种方法都有其优点。静态划分可确保每个用户共享一些资源，通常提供更可预测的性能，也更易于实现。动态划分可以实现更好的利用率（通过让资源匮乏的用户占用其他空闲资源），但实现起来可能会更复杂，并且可能导致空闲资源被其他用户占用，然后在需要时花费很长时间收回，从而导致这些用户性能很差

想象一下有缓存的文件打开的例子。第一次打开可能会产生很多I/O 流量，来读取目录的inode 和数据，但是随后文件打开的同一文件（或同一目录中的文件），大部分会命中缓存，因此不需要I/O。

考虑一下缓存对写入的影响。尽管可以通过足够大的缓存完全避免读取I/O，但写入流量必须进入磁盘，才能实现持久。因此，高速缓存不能减少写入流量，像对读取那样。虽然这么说，写缓冲（write buffering）肯定有许多优点。首先，通过延迟写入，文件系统可以将一些更新编成一批（batch），放入一组较小的I/O 中。例如，如果在创建一个文件时，inode 位图被更新，稍后在创建另一个文件时又被更新，则文件系统会在第一次更新后延迟写入，从而节省一次I/O。其次，通过将一些写入缓冲在内存中，系统可以调度（schedule）后续的I/O，从而提高性能。最后，一些写入可以通过拖延来完全避免。例如，如果应用程序创建文件并将其删除，则将文件创建延迟写入磁盘，可以完全避免（avoid）写入。在这种情况下，懒惰（在将块写入磁盘时）是一种美德。

由于上述原因，大多数现代文件系统将写入在内存中缓冲5～30s，这代表了另一种折中：如果系统在更新传递到磁盘之前崩溃，更新就会丢失。但是，将内存写入时间延长，则可以通过批处理、调度甚至避免写入，提高性能。

某些应用程序（如数据库）不喜欢这种折中。因此，为了避免由于写入缓冲导致的意外数据丢失，它们就强制写入磁盘，通过调用fsync()，使用绕过缓存的直接I/O（direct I/O）接口，或者使用原始磁盘（raw disk）接口并完全避免使用文件系统。虽然大多数应用程序能接受文件系统的折中，但是如果默认设置不能令人满意，那么有足够的控制可以让系统按照你的要求进行操作。