从 NILFS2 看 Log-Structure 文件系统（3）

look_w

NILFS2 的实现很多喜欢 Linux 的人都喜欢追根究底。NILFS2 如何实现这一切的？这个问题时常困扰着我，在这里，我试图将自己的理解写出来。
简述 Log structure files systemNILFS2 是一种 Log-Structure File System。最早的 Log-Structure File System 由 TCL/TK 语言的创始人 John Kenneth Ousterhout 在 Sprite 操作系统中实现。其基本思想是将底层设备当作一种只能追加写 (append) 的设备。将文件修改顺序追加写入磁盘，而不覆盖旧数据。顺序写入能避免很多寻道 (seek) 操作。seek 是一种机械操作，很难提高速度。因此减少 seek 能极大提高文件系统的写效率。
图 4 演示了 NILFS2 的追加写入，作为对比，图 5 演示了 EXT2 的随机写入。
图 4. NILFS2 的写入操作图 5 ext2 的写入操作文件 File1 的内容从 version1 修改为 version2，文件系统会执行两个写操作，一是修改存放文件内容的 block；二是修改存放文件 metadata 内容的 block。
图 5 演示 EXT2 文件系统。File1 文件的内容存放在磁盘 block A 内，File1 的 metadata 存放在 block B 中。Block B 存放在磁盘的固定位置，因此和 block A 不可能顺序排放。修改文件需要写 block A 和 B，如此便需要一个 seek 操作。
在 NILFS2 中，当文件修改时，data 和 metadata 都采用追加的方式写到 disk 的末尾，如图 4 所示。文件本来的 data 存放在 block A，metadata 存放在 block B。NILFS2 并不直接修改 Block A 和 B，而是在 disk 末尾，顺序写入新的 block C 和 D。C 和 D 顺序排放，没有 seek 操作。
追加写入的信息只包括修改的内容。比如文件 File1 占用了 2 个 disk block，但在这次修改中，只有 block B 的内容被修改，那么 NILFS 只会把修改原来 Block B 的内容写入 Block C，另外一个 Block 则原封不动，不会将文件 File1 的所有 block 都追加到磁盘末尾。这种只记录修改数据的操作一般被称为 Log。
下图描述了文件内容增加后的情形。
图 6. 文件内容增加文件本来存储在磁盘 block A 和 B 中，当增加新的数据后，NILFS2 需要将新数据写入 block C。请注意，NILFS2 只将新的 block C 写入 Log，而未修改的 A 和 B 并不写入 Log。Inode 还指向原来的 A 和 B。
假如写操作并不增加文件大小，而只是修改了以前的内容，比如对保存在 block B 上的内容进行修改，那么新的磁盘结构如下：
图 7. 文件内容修改Inode 将指向新的数据块 C，而原来的 block B 则不再被引用。
垃圾收集Log-Structure 文件系统设计中最困难的部分就是垃圾收集。您已经了解到，文件系统的任何修改都将被顺序写入 Log 的末尾，日积月累，终究会写到整个磁盘的最后一个 block。到那个时候，NILFS2 必须回收一部分磁盘空间以便新的数据写入。回收磁盘空间就是垃圾收集的职责。
垃圾收集是现代编程语言的重要研究课题，早在 Lisp 语言中，人们就实现了垃圾收集，用来自动回收程序所分配的内存。虽然传统的 GC 算法主要目的是回收内存，但假如我们将磁盘和 RAM 都当作存储设备，那么他们之间除了读写速率和方式不同之外没有太大的差别。
NILFS2 文件系统借鉴了编程语言的 Garbage Collection 研究成果，采用 Copy Compact 算法来自动回收磁盘空间。
内存 Copy Compact 算法将整个内存空间分成两部分，第一部分给用户使用。当需要进行垃圾收集时，GC 将第一部分中有用的数据拷贝到第二部分，Copy 完成后，两个内存块的角色进行交换。用户便开始使用第二部分分配内存。这样来回切换，从而完成 GC 的工作。
文件系统需要回收磁盘空间时，假如也将整个磁盘分成两部分实在太浪费，并且需要被拷贝的 block 将非常多，效率很低，因为文件数据往往是长期存在，不像内存数据一样经常变化。为此 NILFS2 将磁盘分成多个大小相同的 Segment，在 Segment 间采用 Copy Compact 算法。每次只将某个 segment 中有用的数据 copy 到新的 segment，然后将该 segment 标记为空闲。
NILFS2 的 GC 由用户态的精灵进程 cleanerd 负责。用户调用 mount 时，内核将启动 cleanerd 进程。Cleanerd 通过 ioctl 接口进入内核执行垃圾清理工作。cleanerd 具体的流程涉及到 checkpoint，因此我将在后续章节中再介绍 NILFS GC 的详细流程。
Metadata 文件和 Super Root Block任何文件系统都需要使用大量的元数据。我们所熟悉的很多其他文件系统，比如 ext2 使用磁盘的固定区域保存文件系统的 metadata。NILFS2 则使用特殊的 metadata 文件保存 metadata。
目前，NILFS2 使用四种元数据文件。

• Inode file (ifile)  保存文件的 inode，相当于 ext2 的 inode table；
• Checkpoint file (cpfile) 用来保存所有的 checkpoint 数据；
• Segment usage file (sufile) 保存着 segment 的磁盘使用情况；
• Data address translation file (DAT) 将数据块的虚拟地址影射为真正的物理地址，这是为了实现物理数据可重定位。

除了 Metadata 文件之外，NILFS2 还有一个重要元数据，Super Root Block( 简称 SR)。SR 存放在每个 Log 的固定位置。其中存储了三个特殊的 inode，分别指向元数据文件 DAT，cpfile 和 sufile。
各种数据结构之间的关系前面介绍了很多磁盘数据结构，下图描绘他们之间的关系。
图 8. 各种数据结构的关系有了这张图，我们便可以尝试描述 NILFS2 文件管理的基本思路。
文件 /nilfs/oldfile 存放在 NILFS2 上。读取 oldfile 的过程如下：
将 NILFS2 文件系统 mount 到 /nilfs 目录时，Linux 会调用 nilfs_get_sb 函数，在内存中构建 NILFS2 的 VFS superblock 数据结构。
从 superblock，NILFS 可以得到最近一个 checkpoint 的 Super Root block。从 SR 中进一步得到 cpfile 的 inode。通过 cpfile 的 inode，可以找到 cpfile 的内容，在其中查找 ifile 所在的 inode block，从而得到 ifile。
NILFS2 的根目录拥有一个固定的 inode 号。用这个 inode 号在 ifile 中查找便可以得到根目录的 inode。
Root dentry 中保存了 /nilfs 的 inode，通过 inode，便可以得到 /nilfs 这个目录文件在磁盘上存放的 block，读取这些 block 便可以得到 /nilfs 的目录文件的内容。目前 NILFS2 的目录采用顺序表结构。
图 9. /nilfs 目录文件的内容在这个 dir 文件表中可以找到文件 oldfile 的 inode number：oldfile_ino。用它作为索引，在 ifile 中查找 oldfile 的 inode 在磁盘上的具体存储地址。
ifile 中保存了文件系统中所有文件的 Inode，为了提高查找效率，ifile 采用 BTree 保存信息。用 inode number 作为 Key 在 BTree 中查找，便可得到相应文件的 inode。在本例中，用 oldfile_ino 在 ifile 中查找，便能找到 oldfile 所对应的 inode。根据 inode，便可以找到 oldfile 所有的数据 block。进而读取文件的内容。