单机数据持久-日志结构文件系统type
status
date
slug
summary
tags
category
icon
password
Property
在 20 世纪 90 年代早期，由 John Ousterhout 教授和研究生 Mendel Rosenblum 领导的伯克利小组开发了一种新的文件系统，称为日志结构文件系统(LFS)。他们这样做的动机是基于以下观察：
- 内存大小不断增长。
随着内存越来越大，可以在内存中缓存更多数据。随着更多数据的缓存，磁盘流量将越来越多地由写入组成，因为读取将在缓存中进行处理。因此，文件系统性能很大程度上取决于写入性能。
- 随机 I/O 性能与顺序 I/O 性能之间存在巨大的差距，且不断扩大：传输带宽每年增加约 50%～ 100%。
寻道和旋转延迟成本下降得较慢，可能每年 5%～ 10%。因此，如果能够以顺序方式使用磁盘，则可以获得巨大的性能优势，随着时间的推移而增长。
- 现有文件系统在许多常见工作负载上表现不佳。
例如，FFS 会执行大量写入，以创建大小为一个块的新文件：一个用于新的 inode，一个用于更新 inode 位图，一个用于文件所在的目录数据块，一个用于目录 inode 以更新它，一个用于新数据块，它是新文件的一部分，另一个是数据位图，用于将数据块标记为已分配。因此，尽管 FFS 会将所有这些块放在同一个块组中，但 FFS 会导致许多短寻道和随后的旋转延迟，因此性能远远低于峰值顺序带宽。
- 文件系统不支持 RAID。
例如，RAID-4 和 RAID-5 具有小写入问题（small-write problem），即对单个块的逻辑写入会导致 4 个物理 I/O 发生。现有的文件系统不会试图避免这种最坏情况的 RAID 写入行为。
因此，理想的文件系统会专注于写入性能，并尝试利用磁盘的顺序带宽。此外，它在常见工作负载上表现良好，这种负载不仅写出数据，还经常更新磁盘上的元数据结构。最后，它可以在 RAID 和单个磁盘上运行良好。
引入的新型文件系统 Rosenblum 和 Ousterhout 称为 LFS，是日志结构文件系统（Log-structured File System）的缩写。写入磁盘时，LFS 首先将所有更新（包括元数据！）缓冲在内存段中。当段已满时，它会在一次长时间的顺序传输中写入磁盘，并传输到磁盘的未使用部分。LFS 永远不会覆写现有数据，而是始终将段写入空闲位置。由于段很大，因此可以有效地使用磁盘，并且文件系统的性能接近其峰值。
按顺序写入磁盘
如何将文件系统状态的所有更新转换为对磁盘的一系列顺序写入？
假设将数据块D 写入文件。将数据块写入磁盘可能会导致以下磁盘布局，其中D 写在磁盘地址A0：
当用户写入数据块时，不仅是数据被写入磁盘；还有其他需要更新的元数据（metadata）。在这个例子中，将文件的 inode（I）也写入磁盘，并将其指向数据块 D。写入磁盘时，数据块和 inode 看起来像这样（注意 inode 看起来和数据块一样大，但通常情况并非如此。在大多数系统中，数据块大小为 4KB，而 inode 小得多，大约 128B）
简单地将所有更新（例如数据块、inode 等）顺序写入磁盘的这一基本思想是LFS 的核心。
顺序而高效地写入
为了防止过于频繁的写入导致的旋转延迟（即便是在同一磁道进行多次写入也会有旋转到写入点带来的延迟），LFS 使用了一种称为写入缓冲（write buffering）的古老技术。在写入磁盘之前，LFS 会跟踪内存中的更新。收到足够数量的更新时，会立即将它们写入磁盘， 从而确保有效使用磁盘。
LFS 一次写入的大块更新被称为段（segment），也就是对写入进行分组的大块。因此，在写入磁盘时，LFS 会缓冲内存段中的更新，然后将该段一次性写入磁盘。只要段足够大，这些写入就会很有效。
下面是一个例子，其中 LFS 将两组更新缓冲到一个小段中。实际段更大（几 MB）。第一次更新是对文件 j 的 4 次块写入，第二次是添加到文件 k 的一个块。然后，LFS 立即将整个七个块的段提交到磁盘。这些块的磁盘布局如下：
要缓冲多少
可以根据定位开销计算来判断，通过增大缓存来摊销定位开销，来达到最大效率（最优效率，不可能 100%，一般就 90%）
假设要写入数据。写数据块的时间是定位时间的加上的传输时间 ，即
因此，有效写入速率（ ）就是写入的数据量除以写入的总时间，即
希望有效速率与峰值速率的比值是某个分数，其中 （典型的可能是0.9，即峰值速率的90%）。
可以解出：
一个磁盘的定位时间为10ms，峰值传输速率为100MB/s。假设希望有效带宽达到峰值的90%（F = 0.9）。在这种情况下，
如何在LFS 中很到inode?
通过间接解决方案：inode 映射
由于 inode 现在分布在磁盘各个随机位置，需要方法找到inode块
LFS 的设计者通过名为 inode 映射（inode map，imap）的数据结构，在 inode 号和 inode 之间引入了一个间接层（level of indirection）。imap 是一个结构，它将 inode 号作为输入，并生成最新版本的 inode 的磁盘地址。
为了防止 imap 和 inode 块过远导致的寻道延迟，LFS 将inode 映射的块放在它写入所有其他新信息的位置旁边。因此，当将
数据块追加到文件k 时，LFS 实际上将新数据块，其inode 和一段inode 映射一起写入磁盘：
LFS 在磁盘上只有这样一个固定的位置，称为检查点区域（checkpoint region，CR）。检查点区域包含指向最新的 inode 映射片段（imap）的指针（即地址），因此可以通过首先读取 CR 来找到最新的 inode 映射片段。检查点区域仅定期更新（例如每 30s 左右），因此性能不会受到影响。
在该图中，imap 数组存储在标记为 imap 的块中，它告诉 LFS，inode k 位于磁盘地址 A1。接下来，这个 inode 告诉 LFS 它的数据块 D 在地址 A0。CR 存储了最新的 imap 的位置。
从磁盘读取文件：回顾
从磁盘读取文件时必须发生的事情：假设从内存中没有任何东西开始。我们必须读取的第一个磁盘数据结构是检查点区域。检查点区域包含指向整个 inode 映射的指针（磁盘地址），因此 LFS 读入整个 inode 映射并将其缓存在内存中。在此之后，当给定文件的 inode 号时，LFS 只是在 imap 中查找 inode 号到 inode 磁盘地址的映射，并读入最新版本的 inode。要从文件中读取块，此时，LFS 完全按照典型的 UNIX 文件系统进行操作，方法是使用直接指针或间接指针或双重间接指针。在通常情况下，从磁盘读取文件时，LFS 应执行与典型文件系统相同数量的 I/O，整个 imap 被缓存，因此 LFS 在读取过程中所做的额外工作是在 imap 中查找 inode 的地址。
目录如何
目录结构与传统的 UNIX 文件系统基本相同，因为目录只是（名称，inode 号）映射的集合。例如，在磁盘上创建文件时，LFS 必须同时写入新的 inode，一些数据，以及引用此文件的目录数据及其 inode。请记住，LFS 将在磁盘上按顺序写入（在缓冲更新一段时间后）。因此，在目录中创建文件 foo，将导致磁盘上的以下新结构：
inode 映射的片段包含目录文件 dir 以及新创建的文件 foo 的位置信息。因此，访问文件 foo（具有 inode 号 f）时，你先要查看 inode 映射（通常缓存在内存中），找到目录 dir 的 inode 的位置 A3。然后读取目录的 inode，它给你目录数据的位置 A2。读取此数据块为你提供名称到 inode 号的映射（foo，k）。然后再次查阅 inode 映射，很到 inode 号 k 的位置 A1，最后在地址 A0 处读取所需的数据块。
inode 映射还解决了 LFS 中存在的另一个严重问题，称为递归更新问题（recursive update problem）。每当更新 inode 时，它在磁盘上的位置都会发生变化。如果不小心，这也会导致对指向该文件的目录的更新，然后必须更改该目录的父目录，依此类推，一路沿文件系统树向上。
LFS 巧妙地避免了inode 映射的这个问题。即使inode 的位置可能会发生变化，更改也不会反映在目录本身中。事实上，imap 结构被更新，而目录保持相同的名称到inumber 的映射。因此，通过间接，LFS 避免了递归更新问题。
一个新问题：垃圾收集
LFS 会反复将最新版本的文件（包括其inode 和数据）写入磁盘上的新位置。此过程在保持写入效率的同时，意味着LFS 会在整个磁盘中分散旧版本的文件结构。这些旧版本称为垃圾（garbage）。
假设有一个由inode 号k引用的现有文件，该文件指向单个数据块D0。现在覆盖该块，生成新的inode和新的数据块。由此产生的LFS 磁盘布局看起来像这样（注意，简单起见省略了imap 和其他结构。还需要将一个新的imap 大块写入磁盘，以指向新的inode）：
可以看到inode 和数据块在磁盘上有两个版本，一个是旧的（左边那个），一个是当前的，因此是活的（live，右边那个）。对于覆盖数据块的简单行为，LFS 必须持久许多新结构，从而在磁盘上留下上述块的旧版本。
假设将一块添加到该原始文件k 中。在这种情况下，会生成新版本的inode，但旧数据块仍由旧inode 指向。因此，它仍然存在，并且与当前文件系统分离：
如何处理这些旧版本的inode、数据块等呢？
可以保留那些旧版本并允许用户恢复旧文件版本（例如，当他们意外覆盖或删除文件时，这样做可能非常方便）。这样的文件系统称为版本控制文件系统（versioning file system），因为它跟踪文件的不同版本。
LFS 只保留文件的最新活版本。因此（在后台），LFS 必须定期查找文件数据， 索引节点和其他结构的旧的死版本，并清理（clean）它们，也就是垃圾收集（garbage collection）。
为了防止垃圾收集产生大量碎片（小而离散的空闲块），需要有碎片整理功能。LFS 清理程序按段工作，从而为后续写入清理出大块空间。基本清理过程的工作原理如下：LFS 清理程序定期读入许多旧的（部分使用的）段，确定哪些块在这些段中存在，然后写出一组或多组新的段，只包含其中活着的块，从而释放旧块用于写入（干净的段）。
确定块的死活
给定磁盘段S 内的数据块D，LFS 必须能够确定D 是不是活的。为此，LFS 会为描述每个块的每个段添加一些额外信息。具体地说，对于每个数据块D，LFS 包括其inode 号（它属于哪个文件）及其偏移量（这是该文件的哪一块）。该信息记录在一个数据结构中，位于段头部，称为段摘要块（segment summary block）。
在段的头部设立称为段摘要块（segment summary block），信息包括段中的每一块属于哪个文件的哪一块。如位于 A0 的块 D 属于文件 k 的第 0 块，就有记录 A0:(k,0)。通过查找段摘要块中的记录，再比对该文件内的块目前的实际位置（通过最新 imap 找到 k 的 inode，找对应块序号的块的位置），就能判断当前块是否是死块。段摘要块也是只写一次的，和其他块一起从内存缓冲段中写入。
LFS 使用版本号方式取代摘要。LFS 在文件被截断或删除时，会增加其版本号（version number），并在 imap 中记录新版本号。LFS 可以简单地通过将磁盘版本号与 imap 中的版本号进行比较，跳过上述较长的检查， 从而避免额外的读取。
策略问题：要清理哪些块，何时清理
在最初的 LFS 论文中，作者描述了一种试图分离冷热段的方法。热段是经常覆盖内容的段。因此，对于这样的段，最好的策略是在清理之前等待很长时间，因为越来越多的块被覆盖（在新的段中），从而被释放以供使用，这种段即使清理了，在新段中也会被很快覆盖，所以不需要过于频繁的清理。相比之下，冷段可能有一些死块，但其余的内容相对稳定。因此，作者得出结论，应该尽快清理冷段，延迟清理热段，并开发出一种完全符合要求的试探算法。但是，与大多数政策一样，这只是一种方法，当然并非“最佳”方法。后来的一些方法展示了如何做得更好。
崩溃恢复和日志
利用日志系统，写入段后需要加检查点表示写入完成（把检查点理解为游戏中的存档点），检查点依次写在固定的 log 段中。为了保证检查点的一致性，需要在检查点的头尾加上一致的时间戳。重启时需要读取最新时间戳的完整（头尾都有时间戳且一致）的检查点，从中可以获取最新的段的位置，从而找到最新的 imap。
如果是异常复位，检查点后的数据就会丢失，如果有必要可以尝试读取最后一个检查点对应的段的后一个段（这个段可能也会包含在检查点中，名为将要写入的下一个段），也就是没写完的段，尝试恢复已写入的数据。