Log-structured File System

发表于 更新于 分类于 ，

tTm8U.png

The Design and Implementation of a Log-Structured File System 是 Mendel Rosenblum 和 John K. Ousterhout 在90年代初发表的一篇经典论文，作者认为随机读不是 主要问题：随着越来越大的内存，大部分的读操作都能被 cache，因此 LFS 主要要解决的是减少对硬盘的随机写操作。

作者在论文中用一个 Sprite LFS 来描述。

File System As Log

t9Jzy.png

对于文件的写入，也是类似通过 append log 的方式进行追加数据。大家如果记得话 Kafka 的话， Kafka 基于 顺序写 的方式提高了写入的吞吐量。 想法非常的朴质，但是有两点需要解决：1. 如何通过日志读取最终文件，这个很容易理解。2. 如何管理空闲的数据段。

管理空闲的数据段就会涉及到如下状态的处理，假如某个值为 A, A',A'',A''' 的顺序写入，我们最终只需要 A''' 的状态，而其他的并不需要。

名词列表

名词 用途
Inode 定位文件块，包含存储保护位、更新时间等
Inode map 定位log中inode的位置，包含最近访问时间和版本号
Indriect block 定位大容量数据块
Segement summary 标识segment的内容(文件数量以及每个block的偏移量)
Segement usage table 计算segments中存活的bytes数，并为segement中的数据存储的写 时间
Super Block 存储静态配置信息，包括segements的数量和大小
Checkpoint region 定位inode map、segment useage table所在的block，并标识log中上一个check point的位置
Directory change log 记录目录操作，从而保证inode 中的引用数量一致性

文件读取

常规的 log-structured 的数据格式，显然我们需要从零开始一直读取到最后的日志。那显然太慢了，Sprite LFS 为了提高性能，每个文件都有一个 inode 的数据结构，保存一些元数据与 前十个10 个 数据Blocks ，对于大文件来说 10 个数据块显然不够，inode 还包含一个或多个 indirect blocks 的磁盘地址，每个 indirect blocks 包含更多数据或间接块的地址。

t9aof.png

因为 Inode 非确定的出现在任意一个位置，因此我们还需要定位 Inode 本身。LFS 里面用了一种 Inode map 去存 Inode 的地址。

t9iDU.png

但是 Inode map 也是按照 Block 的方式写入日志中的，因此我们势必需要一个固定的区域来定位，那就有两种方式， Inode Map 存在固定的位置，或者再间接引用。在 LFS 中是有一个固定的 checkpoint 区域来储存 inode map 的位置。

tTRLy.png

空间管理

Sprite LFS 将磁盘分成了很多个 segment

t9K5S.png

segment 是在内存中，当储存的数据量超过 限制大小 之后才会向磁盘落盘。

垃圾回收

日志系统最大的问题显然是需要回收那些不需要的空间的，为了压缩空间，加入了 segment cleaning 技术，Sprite LFS 分了三步来处理这个问题：1. 读取一部分 segments 到内存 2. 标记还存活的数据 3. 将活着的数据写入较少的 segments

tTUM6.png

为了确定哪些 Block 已经无效了，LFS 在 Segment 开头处中储存了一种 Segment Summary 数据体，Segment Summary 中存储了段中每个 Data Block 的地址，和这个 Data Block 的 Inode Number （文件号），以及该 Block 在文件中的 offset。对于任意 Block，只要对比该 Block 的地址，和通过 Inode Map 查询这个 Block 的地址是否相同，就能判断这个 Block 是否过期。

tTx1X.png

如上图中，我们 Inode Map 中储存的 Inode2 的版本是 2，而在 Segment Summary 中 Inode2 的版本是 1 因此这部分的数据就是无效的。

故障恢复

  • LFS 的每个 Segment 都存储了下一个 Segment 的地址，像链表一样。
  • 在 Checkpoint 中，LFS 存储了这个链表的第一个 Segment 和最后一个 Segment 的地址，因此只要读取 Checkpoint 就能恢复出整个文件系统。
  • LFS 每 30 秒更新一次 Checkpoint 中的数据。

tTMOp.png

  1. 当我们更新 Checkpoint 的出现问题，如果 Head Tail 都没有更新，等于没有创建，再来一次即可。
  2. 当我们更新 Checkpoint 的出现问题，如果 Head 更新，Tail 没有更新的话
    • LFS 在硬盘的头部和尾部存储了两个 Checkpoint，每次 Checkpoint 时 LFS 交替地存储在头部或是尾部的 Checkpoint 中。 这样即使写入一个 Checkpoint 失败， LFS 也能恢复到上一个 Checkpoint
    • 同时 LFS 利用时间戳来检测 Checkpoint 的失败：在写入 Checkpoint 时，先更新头指针和对应的时间戳，再更新 Checkpoint 中的其它内容，最后更新尾指针和相同的时间戳。如果 LFS 在读取 Checkpoint 时发现头指针和尾指针的时间戳不一致，就知道这个 Checkpoint 并没有完成。

总结

为什么 LFS 被大家喜欢，LFS 将文件系统按照日志的方式进行储存，假设大部分读都可以在 Buffer Cache 中完成，而写入速度是更高优先级，通过 Segment 的机制让随机写入变成顺序写入，并且很容易的完成快速恢复。

但是 LFS 并非是没有缺点，在 compared FFS to a BSD port of Sprite’s LFS 论文提及到：

  • 磁盘常常是满的（回收器需要在大量的Segment中才能找到一点点可以回收的空间）
  • 写操作随机（因为空闲空间将均匀地分布在各个段中，迫使回收器读取许多段以释放空间）

类似于 Java 如何控制垃圾回收反而是一个更复杂的问题，大概也是从 1991 诞生之后并没有大规模的普及，但是对后世的很多系统都产生了深远的影响。