日志结构文件目录 | Uonlra‘s Blog

type

status

date

slug

summary

按顺序写入磁盘

现在我们需要实现将文件系统状态的所有更新转换为对磁盘的一些列写入。例如，现在我们正在将数据块D写入文件。将数据块写入磁盘可能导致以下磁盘布局，其中D写在磁盘地址A0。

当用户写入数据块时，不仅是数据被写入磁盘；还有其他需要更新的元数据（metadata)。在这个例子中，我们将文件的inode写入磁盘，并将其指向数据块D。

顺序而高效地写入

简单的顺序写入磁盘不足以实现最佳策略，还必须向驱动器发出大量连续写入才能获得良好的写入性能。为了实现这一目的，LFS使用了一种写入缓冲（write buffering ）的技术。在写入磁盘前，LFS会跟踪内存中的更新。收到足够数量的更新时，会立即将它们写入磁盘，从而确保有效使用磁盘。

LFS 一次写入的大块更新被称为段。LFS会缓冲内存段中的更新，然后将该段一次性写入磁盘。只要段足够大，这些写入就会很有效。在下例中，FLS将两组更新缓冲到一个小段中。第一次更新是对文件 j 的4 次块写入，第二次是添加到文件K的一个块。然后LFS，立即将整个七个块的段提交到磁盘。

LFS在写入磁盘前应该缓冲多少次更新，这取决于磁盘本身，特别是与传输速率相比定位开销有多高。

查找 inode

在经典的文件系统（如FFS）,查找 inode 很容易，因为它们以数组形式组织，并放在磁盘的固定位置上。

在Unix 文件系统中，所有的 inode 保存在磁盘的固定位置。给定一个inode 号和起始地址，要查找特定的inode ，只需将inode 号乘以inode 的大小，然后将其加上磁盘数组的起始地址，即可计算器确切的磁盘地址。

在 FFS 系统中，必须知道每个 inode 块的大小和每个 inode 的起始地址。

在LFS ，查找inode 很难实现，因为我们已经将 inode 分散在整个磁盘上，且永远不会覆盖，即最新版本的inode 会不断移动。

间接解决方案 — inode 映射（inode map, imap）

在 inode 号和 inode 之间引入了一个间接层（level of indirection)。imap 是一个结构，将inode 号作为输入，并生成最新版本的 inode 的磁盘地址。可以将其想象为简单的数组，每个条目有四个字节。每次将inode写入磁盘时，imap都会使用器新位置进行更新。

💡

间接层（level of indirection)

计算机科学中大多数问题的解决方案就是一个间接层。将研究的每个虚拟化（如虚拟内存）视为间接层。当然 LFS 中的 inode 映射是 inode 号的虚拟化。但是间接会造成额外得到开销。

imap 需要保存持久写入磁盘，这样允许LFS 在崩溃时仍能记录 inode 位置，从而按设想允许。它可以存在磁盘的固定位置，但是由于它经常更新，因此需要更新文件结构，然后写入imap, 性能会受到影响。

LFS 将 inode 映射的块放在它写入所有其他新信息的位置旁边。因此，当将数据块追加到文件K时，LFS实际上将新数据块，其 inode 和一段 inode 映射写入磁盘。

检查点区域

为了找到 inode 映射，文件系统必须在磁盘上有一些固定且已知的位置，才能开始文件查找。

LFS在磁盘上只要一个固定的位置（），称为检查定点区域（checkpoint region，CR）。检查点区域包括指向最新的 inode 映射片段的指针，因此可以通过首先读取CR 来找到inode映射片段。磁盘布局的整体结构包括一个检查点区域，每个inode 映射包括inode 的地址，inode 指向文件。

假设从内存中没有任何东西开始。我们必须读取的第一个磁盘数据结构是检查点区域。检查点区域包含指向整个 inode 映射的指针（磁盘地址），因此 LFS 读入整个 inode 映射并将其缓存在内存中。在此之后，当给定文件的 inode 号时，LFS 只是在 imap 中查很 inode 号到inode 磁盘地址的映射，并读入最新版本的 inode。

要从文件中读取块，此时，LFS 完全按照典型的 UNIX 文件系统进行操作，方法是使用直接指针或间接指针或双重间接指针。

垃圾集

LFS 会反复将最新版本的文件写入磁盘上的新位置。此过程在保持写入效率的同时，LFS会在整个磁盘中分旧版本的文件系统。这些旧版本就称为垃圾（garbage）。

为了处理旧版本的inode, 数据块，我们保留那些旧版本并且允许用户恢复旧文件版本。这样的文件系统称版本控制文件系统（versioning file system)。

LFS只保留文件的最新活版本。因此，LFS必须定时查找文件数据，索引节点和其他结构的旧的死版本，并清理它们。清理应该使磁盘上的块再次空闲，以便在后续的写入中使用。清理过程是垃圾收集（garbage collection）的一种形式，可以自动为程序释放未使用的内存。

如果 LFS 清理程序在清理过程中简单地通过并释放单个数据块，索引节点等，文件系统在磁盘上分配的空间之间混合了一些空闲洞（hole）。写入性能会大幅下降，因为 LFS 无法很到一个大块连续区域，以便顺序地写入磁盘，获得高性能。实际上，LFS 清理程序按段工作，从而为后续写入清理出大块空间（写入新的段，只包含活着的块，释放旧块）。

确定块的死活

LFS 会为描述每个块的每个段添加一些额外信息。具体地说，对于每个数据块 D，LFS 包括其 inode 号（它属于哪个文件）及其偏移量（这是该文件的哪一块）。该信息记录在一个数据结构中，位于段头部，称为段摘要块（segment summary block）。

何时清理，清理何处

LFS 必须包含一组策略，以确定何时清理以及哪些块值得清理。确定何时清理比较容易。要么是周期性的，要么是空闲时间，要么是因为磁盘已满。

为了确定清理哪些块，有一种试图分离冷热段的方法。热段是经常覆盖内容的段。因此，对于这样的段，最好的策略是在清理之前等待很长时间，因为越来越多的块被覆盖（在新的段中），从而被释放以供使用。相比之下，冷段可能有一些死块，但其余的内容相对稳定。因此，应该尽快清理冷段，延迟清理热段，并开发出一种完全符合要求的试探算法。

崩溃恢复和日志

LFS 在写入相关结构（log，CR等）时崩溃

为了确保 CR 更新以原子方式发生，LFS 实际上保留了CR，每个位于磁盘的一端，并交替写入它们。当使用最新的指向 inode 映射和其他信息的指针更新 CR 时LFS 还实现了一个谨慎的协议：它首先写出一个头（带有时间戳），然后写出 CR 的主体，然后最后写出最后一部分（也带有时间戳）。如果系统在 CR 更新期间崩溃，LFS 可以通过查看一对不一致的时间戳来检测到这一点。LFS 将始终选择使用具有一致时间戳的最新 CR，从而实现 CR 的一致更新。

系统在 LFS 写入磁盘时崩溃

由于 LFS 每隔 30s 左右写入一次 CR，因此文件系统的最后一致快照可能很旧。因此，在重新启动时，LFS 可以通过简单地读取检查点区域、它指向的imap 片段以及后续文件和目录，从而轻松地恢复。但是，最后许多秒的更新将会丢失。

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

小结

LFS 引入了一种更新磁盘的新方法。它总是写入磁盘的未使用部分，然后通过清理回收旧空间，而不是在原来的位置覆盖文件。这种方法在数据库系统中称为影子分页（shadowpaging），在文件系统中有时称为写时复制（copy-on-write），可以实现高效写入，因为 LFS 可以将所有更新收集到内存的段中，然后按顺序一起写入。

这种方法的缺点是它会产生垃圾。旧数据的副本分散在整个磁盘中，如果想要为后续使用回收这样的空间，则必须定期清理旧的数据段。