前言

这两天花了点时间读了下The Design and Implementation of a Log-Structured File System,92年的一篇经典文章。Idea其实很简单,就是利用大内存缓存足够多的内容后,然后一次性顺序的写到磁盘中。LFS的所有写入都是顺序添加。极大提升写效率。思想简单,但是实现比较tricky,有各种细节需要注意,却不复杂,很符合人类直觉。

位置在变化的inode

LFS比较关键的一个点,在于inode不是存在一个fix的位置,而是每次写入一个新的块的时候,都会生成新的inode。之所以这样做是因为,传统的文件系统将inode放在fix位置,当添加或者更新块的时候,需要seek到多个位置去查找inode,查找间接块等,物理运动极其耗时。而LFS这样做了之后,只需要顺序接下去写就行了,但如果是添加的话,还需要读取一次旧的inode块,来维护新的inode块。

但是寻找inode又是一个问题,传统文件中,反正inode数组位置是固定的,只需要位置加上filenumber偏移量就可以了。而在LFS中,存在一个叫imap的数组来索引到最新的inode。也就是说当每次写的时候,在最后总会加上一块imap,来索引最新的inode地址(旧的失效)。到最后整个磁盘中有很多分块的imap。

但是最后还是需要一块fix的位置来存磁盘中所有最新的imap的地址,即checkpoint region(CR)。比如说放在磁盘最开始的地方。CR肯定是需要磁盘seek过去更新,不过这个更新是周期性的,长时间的,比如30秒。而且所有最新imap,是足够小,可以存在内存的。所以只需要磁盘挂载的时候一次性seek到各个位置读入一次所有的imap即可(所有目的都是为了减少seek)。

大概情况如上图。当然还有目录的情况,目录其实也是个文件(保存file name: file number的映射) ,所以处理其实是和普通文件一样的。

垃圾回收

垃圾回收对LFS的性能影响最大的一方面。由于LFS是顺序写的,每次都会产生新的数据块,那么旧的数据块则需要处理掉。处理方式也很简单,比如说一大块连续的磁盘空间(segment),简单的将一段segment中所有live的数据块,顺序的写出即可,那么原先的segment既可以复用了。这种方式可以尽可能保留大块的连续空间,而是很多的碎片。

判断数据块是否过期(live),也是需要处理的问题。论文中提出两种方法,这边讲一种。两种方法都是要在segment中保留一块 segment summary blocksegment summary block记录每一个block的file number和版本号,同时会在imap里保存最新的版本号。每次判断的时候只需要判断版本号有没有过期即可。

文章中有这么一句话对垃圾回收的性能影响的概括。

Overall, Sprite LFS permits about 65-75% of a disk’s raw bandwidth to be used for writing new data (the rest is used for cleaning). For comparison, Unix systems can only utilize 5-10% of a disk’s raw bandwidth for writing new data; the rest of the time is spent seeking.

Crash recovery

LFS的恢复也很方便,所有的imap地址都会周期性的更新到CR中,所以恢复的时候只要直接CR中读即可。这里有个问题是有可能在写入CR的时候断电,导致数据不一致。LFS采用了使用两块CR的方式,两块交替着,在写的时候,开头和结尾都会加上时间戳,若没有相匹配的时间戳,说明这块CR数据一致性有问题。则读取另一块。还有一个问题就是,CR更新时间有间隔,所以会损失几秒种的数据,论文中提到可以在log上向前继续扫描恢复数据,因为LFS是只顺序添加的。

不足之处

论文中也到了LFS的不足之处,就在随机写一个文件后,会生成很多新的块,相互之间不连续,当需要连续读的时候,将会导致更多的seek。

Even for other workloads, such as those including reads and large-file accesses, Sprite LFS is at least as fast as Unix in all cases but one (files read sequentially after being written randomly).

Reference

[1] The Design and Implementation of a Log-Structured File System. SOSP 91’

[2] Operating Systems: Three Easy Pieces. Chapter: Log-structured File Systems