LFS[Log-structured File System]也是由Berkeley的研究人员最先提出并实现的，他们当时认为随机I/O和顺序I/O之间存在着巨大性能差异，其实就是顺序I/O快，随机I/O慢[因为要磁盘需要seek和rorate的时间]。所以说随机I/O成了bottleneck拖了后腿。但是记得在介绍FFS的blog中说过，即便在FFS中，一个write操作其实是至少5次write操作，因为写入一个data block还要更新对应的metadata信息，这里面就比不可少的需要随机I/O。要是能够只用顺序读写就好了，可以大幅度提高I/O效率了。同时Berkeley的研究人员还认为write操作占据了全部操作的很大一部分，因为Memory在快速增长，能够Cache的数据也越来越多那么就要涉及更多的write操作。所以基于这样两个考虑：(1)write占所有disk操作大部分；(2)随机IO性能比连续IO差很多，要是能只用连续I/O就会大幅度提高性能，LFS不更新任何数据只提供append[追加]操作，同时会建立buffer将多次操作放进一个segment里一次性写入来有效利用顺序IO。

Write Sequentially

确定basic idea之后，最重要的问题就是如何做到？比如如何把所有update的操作通过顺序IO写入disk？LFS的操作就是创建一个segment把所有的update的写入这个segment。比如现在我要往磁盘写入data block D，LFS就先把D放到一个segment里，同时后面写上对应的inode的信息[每个block都要有inode信息，要不找不到阿！]，然后再写一个大一点的文件，包含data block 1,2,3,4[用数字为了和前面的D区别开]，然后再放入一个这个文件的inode，来确定block 1，2，3，4的位置。第一格需要解决的问题就是如何寻找inode，因为不同于其他文件系统inode有固定的位置存放方便系统访问，LFS的inode是会分散在各个segment，也就是分散在整个disk。无法确定inode的具体位置，也就无法确定具体数据的位置。LFS适用inode map来解决这个问题，其实这又是个用户映射和定位的数据结构，里面存着inode和对应这个inode最新版本[inode有时也会被更新]的地址信息。所以先写入block，然后写入对应的inode，再写入imap。所以只要知道imap就可以知道inode就可以知道数据的具体位置。那么问题又出现了，如何获得imap的信息[按照imap方式，它也会处于整个disk上]，LFS还拥有一个checkpoint region的数据结构存着所有的imap的地址，这个结构存在整个disk的开始位置也就是address 0，这样一个固定的数据结构位置就可以直接访问了。这样一旦一个segment写满就用一次顺序IO写入磁盘，对应metadata也已经各就各位，一旦有需要就可以立即获得具体位置。

Garbage Collection

如果按照LFS的执行逻辑，不overwrite任何数据，只是进行append操作，那么很自然地就可以想到整个系统将会存在同一个数据的很多版本，因为以前update的操作[删除旧版本保留新版本]，现在就变成了保留旧版本追加进新版本。如果一个系统同时保留新旧版本并trace整个文件的变化过程，这就是versioning file system。LFS不是versioning file system，所以LFS选择定期删除旧版本。具体说来，LFS会segment-by-segment的更新已经确定为过期或者失效的文件。判断过期文件的方法也很简单，每个segment会记录每个data block第一次写入时的metadata[这些metadata描述了data block的具体位置]，一旦data block失效[比如更新或者删除]，该data block对应的inode信息会被更新，但是此时segment存着的该数据的初始metadata还在，所以只要定期比较这两处的关于数据的地址信息是否一致就可以了，如果一致就认为该数据还有效，反之则认为无效，就可以进行删除工作。但是如果直接删除，可以想想，整个磁盘会出现很多空白，而不是连续写满的情况。所以直接删除会产生什么碎片并大幅度降低disk的IO性能。LFS的做法是，把几个segment的有效信息提取出来组成新的完整的segment，这样比如一开始M个segment，重组之后有就会变成N格segment，一般情况下，M<N，这样disk就有新的完整的可用空间由于后续读写，原本的M个segment就会本彻底清除。

Crash Recovery

LFS的恢复机制也是通过log来完成的，之前提到的checkpoint region其实有两个，一个放在磁盘的头部，一个放在磁盘的尾部，两个CR进行交互更新，如果发生错误就从最近的一次checkpoint恢复。这里只简述基本思路并不设计具体细节。但是还是要重点提一下，开发系统细节很重要，因为很多时候大系统的basic idea都比较简单易懂，甚至只是在一个被经常讨论的trade-off之间选择一个并进行强化或者优化，而重点在于开发系统的过程中会遇到很多想象不到的问题，而真正做出系统克服这些问题才是一个好的System Work，正如那句经典名言devil is in the details