>

字数 2.5k 阅读 12 评论 6

1992SOSP-The Design and Implementation of a Log-Structured File System
By Mendel Rosenblum

Mendel is the founder of VMware, and also an investor in Datriums

LFS, Log-structured File System 简单来说就是用日志方式来组织的文件系统，由于日志是一条一条添加的（没有修改），所以这是最直观的解释。
LFS 跟 FFS（Fast File System）的出发点是一样的，那就是顺序写（Sequential Write）有更高的性能。随着内存技术的提高，很多内容都可以留在 Cache 中，读的性能得到了极大的提高，那么，影响文件系统性能的瓶颈就在写操作上了。 LFS 使用 Copy-On-Write 而不是 Update-In-Place 的方式，有效的提升写性能。

  • Basic idea: Buffer all writes (data + metadata) using an in-memory segment; once the segment is full, write the segment to a log
    • The segment write is a sequential write, so its fast
    • We write one large segment (e.g., 4 MB) instead of a bunch of block-sized chunks to ensure that, at worst, we pay only one seek and then no rotational latencies (instead of one seek and possibly many rotational latencies)
    • There are no in-place writes!
  • Reads still require random seeks, but physical RAM is plentiful, so buffer cache hit rate should be high

1）4 个主要的出发点

  • System memories are growing
    内存增大之后，更多内容可以被 Cache，读性能提高，写操作成为瓶颈
  • There is a large gap between random I/O performance and sequential I/O performance
    磁盘转速和寻道技术限制了随机 I/O 性能
  • Existing file systems perform poorly on many common workloads
    普通的单个写操作实际上包含多个写操作，导致性能低下。
  • File systems are not RAID-aware
    没有考虑 RAID

2）Log-structured File System by Rosenblum & Ousterhout

  • 当准备往 disk 写内容的时候， 先在内存的某个 segment 中进行 buffer，包括（data 和 metadata）
  • 当 segment 满的时候，把内容写入一个新申请的 disk 区域。
  • LFS 绝不覆盖已有数据，而总是把内心写入未使用过的区域。
  • 由于 segment 比较大（几 MB），磁盘利用率会得到极大的提升。

问题的关键：如何才能把所有操作都变成顺序操作？

  • 读操作：不可能，因为 block 可能在磁盘中的任意地方
  • 写操作：有可能。

3）如何顺序写？

使用一种非常老的技术 Write buffering，也就是，在写入 disk 之前，现在 memory 中把操作缓存，当收到足够多的操作之后，再一次性写入 disk。

作为对比：
（1）一次只写入一个 block 和其 inode 信息

（1）一次写入多个 block 和对应 inode 信息

4）缓存多大合适？

写入操作的耗时主要跟两个因素有关：寻道速度 + 传输速率

比如：我们的磁盘寻道平均耗时 10ms，传输速率峰值是 100 MB/s，假设我们要使用 90% 的带宽，也就是 100 MB * 0.9 = 90 MB/s，那么我们可以得出缓存 D = 90 MB/s * 0.01 seconds = 9 MB。

5）如何找到 inode？

在 FFS 中或者传统的 Unix File System 中，找到 inode 很简单，因为它们是在磁盘的固定位置，保存在一个数组中。FFS 中，inode 则分布在每个 Cylinder Group 中的固定位置。

但是，在 LFS 中，事情变得复杂，因为我们把 inode 散布在整个磁盘中，因为我们从不原地覆盖的写。

解决办法：

使用 Inode Map (imap)

简单来说，就是用一个间接引用来保存 inode 的实际磁盘地址，这个 imap 中的每个条目用 inode number 对应一个 inode address，imap 必须是持久保存的（persistent），因此必须保存在 disk 中，那么把它保存在磁盘哪个位置合适？

如果保存在磁盘某个固定位置，那么寻道时间的开销依然很大，LFS 采用的方式是把 data, inode 和 imap 三者一起写入磁盘，如下：

Checkpoint Region

从上图我们可以看到，现在 imap 也分布在整个磁盘了，我们又该如何找到 imap 呢？终究还是逃不过啊。
所以，最终，我们还是需要在磁盘上有一个固定的位置能保存全局的索引信息。

LFS 使用一个叫 checkpoint region(CR) 的磁盘固定位置，它保存着指向最新的 inode map 的引用(pointer)，因此 imap 可以通过先创建 CR 的方式来找到。
CR 会已固定的周期进行更新，比如每 30 秒更新一次，因为其对性能影响不大。

6）从硬盘读取文件

为了更好的理解 LFS 原理，我们还需要了解它是如何读取文件的。

首先，我们必须先从磁盘中把 CR 读取到内存，它包含指向整个 imap 的信息。然后，只要我们给定一个 inode number，我们就能找到其对应的磁盘地址，然后读取其最新的 inode version，从而得到最新的 block 地址。

如何存取目录？
目录也是 Unix 中的普通文件，它保存的内容是 name 和 inode 的一一对应关系。当创建一个新文件的时候，也需要更新文件对它的索引。

7) Garbage Colleciton

由于我们不断把新内容写入新的磁盘地址，老的内容就变成 Garbage。

我们有两种方式写入新的 Block 和 inode：

1）append 一个新的 block 和 新 inode map

2）append 新 block 和 新 inode map，同时，这个新的 inode map 也保留对老的 block 的引用

第二种方式给了用户更多选择，因为保留多个版本的信息可以让用户对数据有更多权限，比如误删之后的数据恢复。这种方式也叫 “versioning file system”。

旧数据的管理除了进行数据恢复，还需要定时清理，已保证磁盘有高效可用的空间，一个 GC 算法的好坏主要体现在可以及时释放大量连续的磁盘空间，而不是离散的磁盘空间。

LFS cleaner 基于 segment 来进行处理，它的基本流程如下：

  • 周期性地读取老的 segments（partially used），判断其中的哪些 blocks 仍然有效（live）
  • 然后把那些 live 的 blocks 写入（compact/merge）一个新的 segment，释放老的 segment

如何判断 Block liveness

为了判断 Block 是否 live 的了，LFS 在 segment 中添加了一个叫做 segment summary block(SS) 来记录每个 block 对应的 inode number N 和其 offset T。

具体流程：

  • block D 所在地址 A，在 segment summary block 中找到其对应的 N 和 T
  • 在 imap 中找到 N 所在的地址，把其读取进内存
  • 根据 T 计算这个 block 的地址，如果它指向的是磁盘地址，那么就是 live，否则就不是 live。

伪代码

1
2
3
4
5
6
(N, T) = SegmentSummary[A];
inode = Read(imap[N]);
if (inode[T] == A)
    // block D is alive
else
    // block D is garbage

Clean Policy: When and Which？

1）When？
很简单，周期性或者磁盘不够用时执行 clean 即可

2）Which？
决定清理哪些 block 有些复杂，在原始的 LFS 论文中，作者提出了一种把 segment 分成 hot 和 cold 的方式。对于 hot segment 来说，由于会频繁进行覆盖写操作，因此等待较长时间再 clean 是比较合适的，而 cold segment 则可以更早进行清理，以便尽快腾出空间。

8）Crash Recovery And The Log

CR 是周期性的更新的（每隔 30 秒），为了保证每次 CR 的更新是原子操作，LFS 实际上会使用两个 CRs，它们各在磁盘的两端，在更新 CR 的时候，LFS 也定义了一套协议规则，先写入一个 header（with timestamp），然后写入 CR body，最后再写入一个最后一个 block（with timestamp），如果更新的时候 Crush 了，LFS 通过检查 timestamp 是否匹配就可以判断 CR 是否有效。

由于更新需要花时间，所以实际上进行系统恢复的时候，会丢失一些信息（several seconds）。

为了解决这个缺陷，LFS 使用了一种叫做 “roll forward” 的技术（常用在 database 领域），最基本的思想就是：

从上一次 CR 开始，找到最后的 log（包含在 CR 中），使用它来读取后续的 segments 并判断其中是否存在有效的 updates。如果存在，LFS 就根据其来更新系统。

注：有兴趣的读者可以查看 Rosenblum 的原论文 “Design and Implementation of the Log-structured File System” 了解更多细节。

LFS 的优势和劣势

data can be lost if it has been written but not checkpointed. This can be mitigated by decreasing the time between checkpoints or allowing applications to ask to wait until the next checkpoint before proceeding.

most reads are absorbed by cache; writes always append to the log, so they are sequential and very fast.

blocks are located on disk in exactly (or almost exactly) the order in which they were last written. Even if reads miss cache, they will have good locality if the order in which files are read mimics the order in which they are written.

LFS is good for flash memory (solid-state disks or SSDs): flash memory degrades with each subsequent write, but LFS naturally levels out writes evenly across all segments.

SSDs also require write operations on very large segments; writing segments fits these usage characteristics very well.

思考

LSM 除了有更好的写性能，还有其它一些好处。比如，由于 SSTable 文件是不可修改的，这让对他们的锁操作非常简单。一般来说，唯一的竞争资源就是 Memtable，相对来说需要相对复杂的锁机制来管理在不同的级别。

而如 Scylladb，通过异步 IO，非阻塞线程，线程和线程之间通过消息通讯，没有内存的共享，没有互斥锁，也没有原子操作来大幅的提高了 cpu 的效率。

2016年，Lanyue Lu等人发布了WiscKey论文，这篇论文提出了一种新的设计 WiscKey: Separating Keys from Values

in SSD-conscious Storage，专门为SSD所优化，将key和value分别存储以减少I/O放大。key存在LSM tree中， value存在WAL中，叫做value log。

通常情况下，key比较小，所以LSM tree比较小，当获取value值的时候，再从SSD存储中读取。

参考文章：
从 NILFS2 看 Log-Structure 文件系统
Linux 内核的文件 Cache 管理机制介绍
Linux Cache 机制探究 | P.Linux Laboratory

http://www.eecs.harvard.edu/~cs161/notes/lfs.pdf