日志结构文件系统

1 引言

20 世纪 90 年代初，伯克利分校的一个由 John Ousterhout 教授和研究生 Mendel Rosenblum 领导的小组开发了一种新的文件系统，称为日志结构文件系统。他们这样做的动机基于以下观察：

• 系统内存不断增长：随着内存变大，内存中可以缓存更多数据。随着越来越多的数据被缓存，磁盘流量越来越多地由写入组成，因为读取由缓存提供服务。因此，文件系统的性能很大程度上取决于其写入性能。
• 随机I/O 性能和顺序I/O 性能之间存在很大差距：多年来硬盘传输带宽大幅增加；随着更多的位被封装到驱动器的表面，访问所述位时的带宽增加。然而，寻道和旋转延迟成本却缓慢下降；让廉价的小型电机更快地旋转盘片或更快地移动磁盘臂是一项挑战。因此，如果您能够以顺序方式使用磁盘，那么与导致寻道和旋转的方法相比，您将获得相当大的性能优势。
• 现有文件系统在许多常见工作负载上表现不佳：例如，FFS将执行大量写入来创建一个大小为一个块的新文件：一个用于新的inode，一个用于更新inode位图，一个用于包含该文件的目录数据块，一个用于更新目录inode，一个用于作为新文件一部分的新数据块，并且还需要对数据位图进行一次写入以标记数据块已被分配。因此，尽管 FFS 将所有这些块放置在同一块组内，但 FFS 需要进行许多短寻道和随后的旋转延迟，因此性能远低于峰值顺序带宽。
• 文件系统不支持RAID：例如，RAID-4 和RAID-5 都存在小写入问题，即对单个块的逻辑写入会导致发生4 个物理I/O。现有文件系统不会尝试避免这种最坏情况的 RAID 写入行为。

因此，理想的文件系统将关注写入性能，并尝试利用磁盘的顺序带宽。此外，它在常见工作负载上表现良好，这些工作负载不仅写出数据，而且还经常更新磁盘上的元数据结构。最后，它在 RAID 和单个磁盘上都能很好地工作。 Rosenblum 和 Ousterhout 推出的新型文件系统称为 LFS，是日志结构文件系统的缩写。当写入磁盘时，LFS 首先将所有更新（包括元数据！）缓冲在内存段中；当该段已满时，它会通过一次长的、顺序的传输写入未使用的磁盘部分。 LFS 永远不会覆盖现有数据，而是始终将段写入空闲位置。由于段很大，因此磁盘（或 RAID）可以得到有效利用，文件系统的性能也接近顶峰。

关键：如何使所有写入顺序写入？

文件系统如何将所有写入转换为顺序写入？对于读取，此任务是不可能的，因为要读取的所需块可能位于磁盘上的任何位置。然而，对于写入，文件系统总是有一个选择，而我们希望利用的正是这个选择。

2 按顺序写入磁盘

因此，我们面临的第一个挑战是：如何将文件系统状态的所有更新转化为一系列对磁盘的顺序写入？为了更好地理解这一点，让我们举一个简单的例子。假设我们正在向文件写入一个数据块 D。将数据块写入磁盘可能会导致以下磁盘布局，D 被写入磁盘地址 A0：

然而，当用户写入数据块时，写入磁盘的不仅是数据，还有其他需要更新的元数据。在这种情况下，我们也把文件的 inode (I) 写入磁盘，并让它指向数据块 D。写入磁盘后，数据块和 inode 的如下图所示（注意，inode 看起来和数据块一样大，但一般情况下并非如此；在大多数系统中，数据块的大小为 4 KB，而 inode 则小得多，约为 128 字节）：

这种简单地将所有更新（如数据块、inodes 等）按顺序写入磁盘的基本思想是 LFS 的核心。理解了这一点，你就掌握了基本思想。但正如所有复杂的系统一样，细节决定成败。

3 顺序有效地写入

不幸的是，顺序写入磁盘（单独）不足以保证高效写入。例如，想象一下，如果我们在时间 $T$ 向地址 $A$ 写入一个块。然后我们等待一会儿，并在时间 $T + \delta$ 的地址 $A + 1$（按顺序排列的下一个块地址）写入磁盘。不幸的是，在第一次和第二次写入之间，磁盘发生了旋转；当您发出第二次写入时，它将在提交之前等待大部分旋转（具体来说，如果旋转需要时间 $T_{rotation}$，则磁盘将等待 $T_{rotation}-\delta$，然后才能将第二次写入提交到磁盘表面）。因此，您可以看到，仅仅按顺序写入磁盘不足以实现峰值性能；相反，您必须向驱动器发出大量连续写入（或一次大型写入）才能获得良好的写入性能。

为了实现这一目标，LFS 使用一种称为写入缓冲的古老技术。在写入磁盘之前，LFS 会跟踪内存中的更新；当它收到足够数量的更新时，它会立即将它们全部写入磁盘，从而确保磁盘的有效使用。

LFS 一次写入的大块更新被称为一个段。尽管这个术语在计算机系统中被滥用，但在这里它只是指 LFS 用来分组写入的一个相对较大的块。因此，当写入磁盘时，LFS 将更新缓冲在内存中的段中，然后将该段全部写入磁盘。只要段足够大，这些写入就会高效。

下面是一个示例，其中 LFS 将两组更新缓冲到一个小段中；实际的段更大（几MB）。第一个更新是对文件 j 的四个块写入；第二个是向文件 k 添加一个块。然后，LFS 将七个块的整个段一次性提交到磁盘。这些块的最终磁盘布局如下：

4 缓冲多大

这就提出了以下问题：在写入磁盘之前，LFS 应该缓冲多少个更新？当然，答案取决于磁盘本身，特别是定位开销与传输速率相比有多高。

例如，假设每次写入之前的定位（即旋转和寻道开销）大约需要 $T_{position}$秒。进一步假设磁盘传输速率为$R_{peak}\text{ MB/s}$。在这样的磁盘上运行时，LFS 在写入之前应该缓冲多少？

思考这个问题的方法是，每次写入时，您都会付出固定的定位成本开销。因此，您需要写多少才能摊销该成本？你写的越多越好（显然），并且你越接近达到峰值带宽。

为了获得具体的答案，我们假设我们正在写 $D\text{ MB}$。写这块数据的时间（$T_{write}$）是定位时间$T_{position}$加上传输时间$\frac{D}{R_{peak}}$，或者： $$ T_{write}=T_{position}+\frac{D}{R_{peak}} $$ 因此，有效写入率（$R_{effective}$）就是写入的数据量除以写入的总时间： $$ R_{effective}=\frac{D}{T_{write}}=\frac{D}{T_{position}+\frac{D}{R_{peak}}} $$ 我们感兴趣的是让有效率 ($R_{effective}$) 接近峰值率。具体来说，我们希望有效速率是峰值速率的某个分数 $F$，其中 $0 < F < 1$（典型的 F 可能是 $0.9$，或峰值速率的 $90%$）。在数学形式上，这意味着我们需要$R_{effective}=F\times R_{peak}$ 。

至此，我们可以求解$D$： $$ R_{effective}=\frac{D}{T_{write}}=\frac{D}{T_{position}+\frac{D}{R_{peak}}} $$

$$ D=F\times R_{peak}\times(T_{position}+\frac{D}{R_{peak}}) $$

$$ D=(F\times R_{peak}\times T_{position})+(F\times R_{peak}\times \frac{D}{R_{peak}}) $$

$$ D=\frac{F}{1-F}\times R_{peak}\times T_{position} $$

举个例子，磁盘的定位时间为$10\text{ ms}$，峰值传输率为$100\text{ MB/s}$；假设我们想要峰值的 $90%$ 的有效带宽 ($F = 0.9$)。在本例中，$D = \frac{0.9}{0.1}\times 100\text{ MB/s} \times 0.01 \text{ s} = 9\text{ MB}$。尝试一些不同的值，看看我们需要缓冲多少才能接近峰值带宽。需要多少才能达到峰值的 $95%$？ $99%$？

5 问题：查找 Inode

为了了解如何在 LFS 中查找 inode，让我们简要回顾一下如何在典型的 UNIX 文件系统中查找 inode。在典型的文件系统（例如 FFS）甚至旧的 UNIX 文件系统中，查找 inode 很容易，因为它们被组织在数组中并放置在磁盘上的固定位置。

例如，旧的 UNIX 文件系统将所有inode保存在磁盘的固定部分。因此，给定 inode number和起始地址，要查找特定 inode，只需将 inode number乘以 inode 的大小，然后将其添加到磁盘阵列的起始地址，即可计算出其准确的磁盘地址。 基于数组的索引（给定 inode number）既快速又简单。

在 FFS 中查找给定 inode number的 inode 只是稍微复杂一些，因为 FFS 将 inode 表分割成块，并将一组 inode 放置在每个柱面组中。因此，我们必须知道每个inode块有多大以及每个inode的起始地址。之后的计算类似，也很容易。

在LFS，生活更加困难。为什么？好吧，我们已经成功地将inode分散在整个磁盘上！更糟糕的是，我们永远不会就地覆盖，因此最新版本的索引节点（即我们想要的）不断移动。

6 通过间接解决方案：Inode Map

为了解决这个问题，LFS 的设计者通过一个名为 inode map（imap）的数据结构，在 inode number和 inode 之间引入了一层间接关系。imap 是一种将 inode number作为输入并生成该 inode 最新版本磁盘地址的结构。因此，可以想象它通常是作为一个简单的数组来实现的，每个条目有 4 个字节（磁盘指针）。当 inode 被写入磁盘时，imap 就会根据新的位置进行更新。

不幸的是，imap 需要保持持久性（即写入磁盘），这样做可以让 LFS 在崩溃时跟踪 inode 的位置，从而按预期运行。因此，有一个问题：imap 应该放在磁盘的哪个位置？

当然，它可以位于磁盘的固定位置。遗憾的是，由于它经常更新，这就需要在更新文件结构后再写入 imap，因此性能会受到影响（也就是说，在每次更新和 imap 的固定位置之间会有更多的磁盘寻道）。

相反，LFS 会在写入所有其他新信息的位置旁边放置 inode 映射块。因此，在向文件 k 添加数据块时，LFS 实际上是将新数据块、其 inode 和 inode 映射的一部分一起写入磁盘，如下所示：

在这张图中，存储在标记为 imap 的块中的 imap 数组的一块告诉 LFS inode k 位于磁盘地址 A1；这个 inode 又告诉 LFS 它的数据块 D 位于地址 A0。

7 完成解决方案：检查点区域

7.1 如何找到inode map

你可能已经注意到这里的问题了。既然inode map的各个部分也分布在磁盘上，我们如何找到inode map呢？归根结底，没有什么神奇的：文件系统必须在磁盘上有一些固定且已知的位置才能开始文件查找。

LFS 在磁盘上为此提供了一个固定位置，称为检查点区域 (CR)。检查点区域包含指向最新的 inode map片段的指针（即地址），因此可以通过首先读取 CR 来找到 inode map片段。请注意，检查点区域仅定期更新（例如每 30 秒左右），因此性能不会受到不良影响。因此，磁盘布局的整体结构包含一个检查点区域（指向 inode map的最新部分）；每个 inode 映射片段都包含 inode 的地址； inode 指向文件（和目录），就像典型的 UNIX 文件系统一样。

下面是检查点区域（注意它位于磁盘的起始位置，地址为 0）以及单个 imap 块、inode 和数据块的示例。一个真正的文件系统当然会有一个大得多的 CR（事实上，它会有两个，我们稍后会了解到）、许多 imap 块，当然还有更多的 inode、数据块等。

7.2 从磁盘读取文件

为了确保你理解 LFS 的工作原理，现在让我们来了解一下从磁盘读取文件的过程。假设内存中什么都没有。我们必须读取的第一个磁盘数据结构是检查点区域。检查点区域包含指向整个 inode map的指针（即磁盘地址），因此 LFS 会读入整个 inode map并缓存在内存中。在此之后，当得到文件的 inode number时，LFS 只需在 imap 中查找 inode number到 inode磁盘地址的映射，然后读入最新版本的 inode。

此时，LFS 会根据需要使用直接指针、间接指针或双向间接指针，完全按照典型 UNIX 文件系统的方式读取文件块。在普通情况下，LFS 从磁盘读取文件时执行的 I/O 次数应与典型文件系统相同；整个 imap 已被缓存，因此 LFS 在读取过程中所做的额外工作就是在 imap 中查找 inode 的地址。

7.3 关于目录

到目前为止，我们已经通过仅考虑inode和数据块来简化了我们的讨论。但是，要访问文件系统中的文件（例如 /home/zfhe/foo），还必须访问某些目录。那么LFS是如何存储目录数据的呢？

幸运的是，目录结构与经典 UNIX 文件系统基本相同，因为目录只是（名称、inode number）映射的集合。例如，当在磁盘上创建文件时，LFS 必须写入新的 inode、一些数据以及引用该文件的目录数据及其 inode。请记住，LFS 将在磁盘上按顺序执行此操作（在缓冲更新一段时间后）。因此，在目录中创建文件foo 将导致磁盘上出现以下新结构：

inode map的片段包含目录文件 dir 以及新创建的文件 f 的位置信息。因此，当访问文件 foo （inode number为 $k$）时，您首先会在inode map（通常缓存在内存中）中查找目录 dir ($A3$) 的inode的位置；然后读取目录 inode，它给出目录数据的位置 ($A2$)；读取此数据块即可获得 (foo, k) 的名称到 inode number的映射。然后再次查阅inode map，找到inode number k（$A1$）的位置，最后在地址$A0$处读取所需的数据块。

LFS 中 inode 映射还解决了另一个严重问题，称为递归更新问题。任何从不就地更新（例如 LFS），而是将更新移动到磁盘上的新位置的文件系统都会出现此问题。

具体来说，每当更新inode时，它在磁盘上的位置就会发生变化。如果我们不小心的话，这也会导致指向该文件的目录的更新，然后会强制要求更改该目录的父目录，依此类推，一直沿着文件系统树向上更新。

LFS通过inode map巧妙地避免了这个问题。尽管inode的位置可能会发生变化，但这种变化永远不会反映在目录本身中；相反，当目录保存相同的名称到inode number映射时，imap 结构会被更新。因此，通过间接，LFS 避免了递归更新问题。

8 新问题：垃圾回收

8.1 基本介绍

您可能已经注意到 LFS 的另一个问题；它将文件的最新版本（包括其inode和数据）重复写入磁盘上的新位置。此过程在保持写入效率的同时，意味着 LFS 会将旧版本的文件结构分散在整个磁盘上。我们称这些旧版本为垃圾。例如，假设我们有一个由inode number $k$ 引用的现有文件，它指向单个数据块 $D0$。我们现在更新该块，生成新的inode和新的数据块。 LFS 的最终磁盘布局看起来像这样（注意，为了简单起见，我们省略了 imap 和其他结构；新的 imap 块也必须写入磁盘以指向新的 inode）：

在图中，您可以看到磁盘上的inode和数据块都有两个版本，一个是旧版本（左侧），另一个是当前的、即时的版本（右侧）。通过（逻辑上）更新数据块这一简单行为，LFS 必须持久化大量新结构，从而在磁盘上留下旧版本的数据块。

举个例子，想象我们将一个块附加到原始文件 k 上。在这种情况下，会生成新版本的 inode，但旧数据块仍由 inode 指向。因此它仍然是有效的，并且完全属于当前文件系统：

那么我们应该如何处理这些旧版本的inode、数据块等呢？可以保留这些旧版本并允许用户恢复旧文件版本（例如，当他们不小心覆盖或删除文件时，这样做可能非常方便）；这种文件系统称为版本控制文件系统，因为它跟踪文件的不同版本。

然而，LFS 仅保留文件的最新实时版本；因此（在后台），LFS 必须定期查找文件数据、inode和其他结构的这些旧的无效版本，并清理它们；因此，清理应该使磁盘上的块再次空闲以供后续写入使用。请注意，清理过程是垃圾回收的一种形式，这是编程语言中出现的一种技术，可以自动释放程序未使用的内存。

前面我们讨论了段的重要性，因为它们是在 LFS 中实现对磁盘进行大量写入的机制。事实证明，它们对于有效清理也是不可或缺的。想象一下，如果 LFS 清理器在清理过程中简单地遍历并释放单个数据块、inode等，会发生什么。结果：文件系统在磁盘上分配的空间之间混合了一定数量的空闲孔。写入性能将大幅下降，因为 LFS 无法找到大的连续区域来顺序且高性能地写入磁盘。

相反，LFS 清理器逐段工作，从而为后续写入清理大块空间。基本清理过程如下。 LFS 清理器定期读取一些旧的（部分使用的）段，确定这些段中哪些块是有效的，然后写出一组新的段，其中仅包含有效的块，从而释放旧的段以供写入。具体来说，我们期望清理程序读取 $M$ 个现有段，将其内容压缩为 $N$ 个新段（其中 $N < M$ ），然后将 $N$ 个段写入磁盘的新位置。然后，旧的 $M$ 段将被释放，可供文件系统用于后续写入。

然而，我们现在面临两个问题。

• 第一个是机制：LFS 如何判断段内哪些块是有效块，哪些块是无效块？
• 第二个是策略：清理程序应该多久运行一次，以及应该选择清理哪些部分？

8.2 确定块有效性

我们首先解决机制问题。给定磁盘段 $S$ 内的数据块 $D$，LFS 必须能够确定 $D$ 是否处于有效状态。为此，LFS 向描述每个块的每个段添加了一些额外信息。具体来说，LFS包括每个数据块$D$包括它的inode number（它属于哪个文件）和它的偏移量（它是文件的哪个块）。该信息记录在段头部的结构中，称为段摘要块。

有了这些信息，就可以很容易地确定一个块是有效的还是无效的。对于位于磁盘上地址 $A$ 的块 $D$，查看段摘要块并找到其inode number $N$ 和偏移量 $T$ 。接下来，在 imap 中查找 $N$ 所在的位置并从磁盘读取 $N$（也许它已经在内存中，这样更好）。最后，使用偏移量 $T$ ，查看 inode（或某个间接块）以查看 inode 认为该文件的第 $T$ 个块位于磁盘上的位置。如果它准确地指向磁盘地址A，LFS可以断定块D是有效的。如果它指向其他地方，LFS 可以断定 D 没有在使用中（即它已失效），从而知道不再需要该版本。这是伪代码摘要：

1
2
3
4
5
6

(N, T) = SegmentSummary[A];
inode = Read(imap[N]);
if (inode[T] == A)
// block D is alive
else
// block D is garbage

下面是描述该机制的图，其中段摘要块（标记为 $SS$）记录了地址 $A0$ 处的数据块实际上是文件 k 偏移量 0 处的一部分。通过检查 k 的 imap，可以找到 inode，并看到它确实指向该位置。

LFS 会采取一些快捷方式来提高确定有效性过程的效率。例如，当文件被截断或删除时，LFS 会增加其版本号，并在 imap 中记录新的版本号。通过在磁盘段中记录版本号，LFS 只需将磁盘上的版本号与 imap 中的版本号进行比较，就能缩短上述较长时间的检查，从而避免额外的读取。

8.3 策略问题：清理哪些块以及何时清理

除上述机制外，LFS 还必须包含一套策略，以确定何时清理以及哪些块值得清理；确定何时清理比较简单：定期、空闲时或磁盘已满而不得不清理时。

而确定清理哪些块则更具挑战性，这也是许多研究论文的主题。在最初的 LFS 论文中，作者描述了一种试图分离热段和冷段的方法。热段是指内容经常被覆盖的段，因此，对于这样的段，最好的策略是等待很长时间再进行清理，因为越来越多的数据块被覆盖（在新的段中），从而被释放出来以供使用。

相比之下，冷段可能会有一些无效块，但其余内容相对稳定。因此，作者得出结论，应该尽早清理冷段，晚些清理热段，并开发了一种启发式方法来实现这一目标。然而，与大多数策略一样，这种策略并不完美；后来的方法展示了如何做得更好。

9 崩溃恢复和日志

最后一个问题：如果 LFS 写入磁盘时系统崩溃，会发生什么？更新期间的崩溃对于文件系统来说是很棘手的，因此 LFS 也必须考虑这一点。

在正常操作期间，LFS 缓冲段中的写入，然后（当段已满或经过一定时间时）将该段写入磁盘。 LFS 将这些写入组织在日志中，即检查点区域指向头段和尾段，每个段都指向下一个要写入的段。 LFS 还定期更新检查点区域。在这些操作（写入段、写入 CR）期间显然可能会发生崩溃。那么 LFS 如何处理写入这些结构期间的崩溃呢？

我们先来说第二种情况。为了确保 CR 更新以原子方式发生，LFS 实际上保留了两个 CR，分别位于磁盘的两端，并交替写入。 LFS 在使用指向 inode map的最新指针和其他信息更新 CR 时还实现了谨慎的协议；具体来说，它首先写出一个标头（带有时间戳），然后写出 CR 的主题，最后写出最后一个块（也带有时间戳）。如果系统在 CR 更新期间崩溃，LFS 可以通过查看一对不一致的时间戳来检测到这一情况。 LFS总是会选择使用最新的具有一致时间戳的CR，从而实现CR的一致更新。

现在我们来解决第一种情况。由于 LFS 大约每 30 秒写入一次 CR，因此文件系统的最后一个一致快照可能相当旧。因此，重新启动后，LFS 可以通过简单地读取检查点区域、它指向的 imap 片段以及后续文件和目录来轻松恢复；但是，最后几秒的更新将会丢失。

为了改进这一点，LFS 尝试通过数据库社区中称为前滚的技术来重建许多这些段。基本思想是从最后一个检查点区域开始，找到日志的末尾（包含在 CR 中），然后使用它来读取接下来的段并查看其中是否有任何有效的更新。如果有，LFS 会相应地更新文件系统，从而恢复自上一个检查点以来写入的大部分数据和元数据。