【Lecture note】Log-structured File Systems

Log-structured File Systems

Background

上世纪90年，伯克利一位教授基于当时以下考量思考理想文件系统的设计准则。

• 未来系统内存不断增长。
• 随机I/O性能远不如顺序I/O性能。
• 现有文件系统在许多常见的workloads中表现不佳。
• 文件系统对RAID不感知。

理想文件系统写性能至关重要，可尝试利用磁盘顺序写的高带宽特性，且在元数据更新频繁的情况下依旧运行良好。最有，文件系统需友好支持RAID。

于是乎，该教授设计了Log-structured file system，既LFS。LFS会将写磁盘的数据暂时缓冲起来，以segment(通常是MB size)为的单位下刷到磁盘。LFS不覆盖原有数据，只是不断地分配新的write segment。由于segment通常为几MB，所以写segment时磁盘为顺序写，由此LFS可达到很高的写带宽。

LFS Design

Writing to disk sequentially

首先思考如何将文件系统的所有write updates转换为LFS所需要的顺序写。

向磁盘写入一个文件时，需要写入data block和更新对应的inode block。遵循循序写的理念，LFS顺序写入这两块block到磁盘，如下所示，data block后的inode的信息表示其inode拥有的data block为A0。

Writing Sequentially and effectively

考虑到磁头的旋转，简单的将每次文件更新的block追加写如磁盘中并不能完全达到磁盘顺序写的峰值带宽。LFS考虑在内存中开辟一块buffer暂存追加写的block数据，集满一个segment后再下刷至磁盘中。而通常segment的大小为MB计算，整个segment的下刷期间磁盘磁头可不必考虑定位问题，故可接近磁盘顺序写满带宽。

下图为向内存中追加写两个文件的segment的layout示例。

Problem：finding inodes

但以上追加写data block和inode block的方式会引发一个问题，那就是定位inode困难。

传统文件系统中inode被组织成array的形式，通过inode table的及地址和inode number可简单的定位到特定inode的地址。但LFS的设计理念中inode block被分散到了整个磁盘中，且存在inode的版本替换问题。

Solution through indirection： The inode map

LFS针对"finding inodes"问题的解决方案是再inode number和inodes之间引入中间层inode map。

inode map根据输入的inode number输出最新version的inode地址，可组织成array的形式。当一个inode被追加写到磁盘中时，inode map需要既是更新。且由于元数据频发更新引发inode map的频繁更新，inode map不宜固定到特定地址(否则会打乱顺序写)，直接更新到对平updata metadata block的后面即可。

如下所示，可以inode mapi定位inode[k]的地址为A1，找到AI后再定位其data block的地址为A0。

Completing The solution： The checkpoint region

但因为inode map仍然是分散在整个磁盘中的数据结构，这会引来如何定位inode map的问题。

LFS的解决方案时磁盘中固定区域check point region，CR区来定位最新version的inode map，且CR区的持久化更新可定时(如30s)，这对磁盘性能的影响微忽极微。

至此的磁盘layout如下所示，当读取一个文件时，首先根据CR区定位到最新的inode map，然后根据文件的inode number查阅inode map，定位对应的inode的地址，最后根据地址读取inode信息来获取data block的最终位置并读取出来。

What about directories？

之前的简化模型只讨论了data block和inode block，现在引入目录的讨论。

如创建一个文件/dir1/foo.file，LFS会依次向磁盘中写入data block、data block的inode、dir的data block(内容即文件名到文件inode的映射)、dir的inode block、inode map，如下所示。

读取文件/dir1/foo.file时，首先从inode map中定位其目录dir1的inode地址，依次读取器dir1内容定位到foo.file的inode编号k，再通过inode map寻找inode k的地址，最终定位到data block。

A new problem： Garbage collection

由上观察到一个file再LFS中会在不断地更新中遗留无效的版本(无效的data block和inode block)。这些无效的版本数据被称为garbage，需要LFS进行删除以回收磁盘空间。

前面提到过LFS以segment为单位进行刷盘，所以LFS的garbage collection同样时以segment为单位进行回收。回收执行时LFS选择N个已经满的segment，读取其中的有效的data | inode blocks，刷到M个新的segment中。由于M<N，所以LFS的一次GC可以回收磁盘(N-M)*segment size大小的空间。segment中valid block由segment额外附带的记录信息定位。

Crash recovery and the log

LFS需要向磁盘中下刷segment和CR，若在下刷中途出现系统崩溃，LFS需要一定手段保证其下刷的原子性。

保证segment的原子性比较简单，既把一个segment的write视作一个log即可。这样有可能会损失崩溃前好几秒的更新信息，后续有人提出解决方案，这里不赘述。保证CR原子性LFS的方案是在磁盘的首和尾都存有CR副本，并交替写入。CR被系统时间戳信息所包围，崩溃restarting时可检测并选择首位具有完整且最近时间戳的CR。

summary

LFS引入了一种新的更新磁盘的方法，其总是将wirte请求写入还未被使用的磁盘空间，并且定时回收以前使用过的存有无效数据的磁盘空间。LSM的序列write极大的提高了文件系统的write性能。