保持一致性: Journaling

29 Aug 2012 by fleuria

一个比较容易混淆的概念是,Journaling主要负责的是数据一致性的维护,而并不特别关心数据的恢复。

上篇post记了些FFS相关的笔记,不过忽略了文件系统的Journaling,在这里单独记一下。

情景

凡是需要分多次写才能完成的一项任务,如果在中途中断便有可能会造成不一致。

文件系统中的操作恰恰大多为分步进行,除了对数据块的操作,更附带着对元数据的更新。试想删除一个文件的情景1,顺序如下:

  1. 删除目录中对应的目录项
  2. 释放inode

如果1与2之间系统崩溃,那么就会形成一个不被任何目录项引用的inode,然而它的引用计数大于零,无法回收利用。换句话说,这就造成了文件系统元数据的不一致。

同步写

上一篇post中提到,文件系统会尽量等缓存中的数据块成簇,再一齐写入,考虑到磁盘的机械原理,这样可以大大地增大文件系统的吞吐。

然而代价是,写操作的顺序无法保证。回到上面删除文件的情景,如果写操作的顺序反了过来:

  1. 释放inode
  2. 删除目录中对应的目录项

如果在两步操作之间系统崩溃,目录中就留有了一项错误的映射,引用了一个不存在的inode。到这里还不是大问题,fsck可以轻松解决它。

真正糟糕的是,如果这个inode号被一个新的文件使用了,那么目录中的这项映射就奇怪地指向了一个不相干的文件,fsck将无法辨认哪个目录项才是正确的。

可见保证两项写的顺序是有必要的。然而性能呢?每写一次数据,随着更新一次元数据,机械臂免不了来来回回运动一番。磁盘大块读大块写的愿景也就破坏了。

崩溃恢复

在系统启动时,会首先执行一次fsck进行一致性检查。

如果存在不一致问题,则遍历文件系统中的冗余信息尽力修复。若出现类似上文提到的fsck无法确认的问题,就出现一个交互界面,让用户来给出选择。

用过Windows XP的我们一定对强制关机后的蓝色界面中消耗掉的时间之长印象深刻。可以想见,fsck是一件相当耗时的工作。

A Simple Solution To Above All

便是Journaling。

将文件系统的所有变更追加到一个日志文件中。系统崩溃之后,只要检查日志文件的末尾,即可在一定程度上恢复崩溃时进行的操作,快速地恢复文件系统的一致性。2

Journaling的写入很容易做到连续的大块写,符合磁盘的机械性质。此外因为有了Journaling做保证,原先文件系统中的同步写可以得到消除,在某种程度上对性能也是更加有益的。

What To Log

记录文件系统中所有数据的变更是个有吸引力的方案,然而会大幅地损失性能。试图兼顾写性能与所有数据可靠的Log-structured FS则属于全新的文件系统结构,并非为既有的文件系统加入journaling支持的可行方向。

退一步,可以只记录元数据3的变更,止于保证文件系统本身的一致性。至于用户数据的一致性可以交给用户程序自己来保证——毕竟不是所有的应用程序都对数据的一致性敏感。

Metadata Logging

可见Metadata Logging是一条很中庸的解决方案:

  • 不需要修改文件系统的结构,保持了原先文件系统的兼容;
  • 性能与一致性之间的平衡;
  • 易于实现。

Redo-only Log以及约束

日志文件系统中的技术与术语许多都是来自数据库的事务处理。不过一些不同允许文件系统的Journaling实现简化许多:

  • 文件系统中的事务不会中断
  • 文件系统中事务的寿命相对较短

从而文件系统无需考虑事务的回滚,也无需考虑事务之间复杂的依赖关系。只要在日志中将变更记录下来,必要时根据日志“重播”这些变更就够了。这种仅用于“重播”的日志,被称作Redo-only Log。

简化归简化,几项约束仍必须遵守:

  • Ordering Garantee:

    保证实写必须在Log写入磁盘之后;

  • Transactional Garantee:

    如果是连续的两项操作,那么必须先保证两项操作的Log都已写入磁盘,随后才能实写(实写的顺序则不重要)。

约束的意义就在于,只要满足了少数的几条原则,其余的任何优化都可以做。

实例:BFS

BFS采用Metadata Logging为既有的文件系统提供了Journaling支持,并给出了一个简单的实现(不到1000行,可惜没有开源)。

BFS将以下操作视为事务:

  • 创建/删除一个文件或者目录
  • 重命名一个文件
  • 更改文件的大小
  • 创建/更改/删除文件的atrribute

BFS为journal预留了一块固定大小的区域,以循环缓冲区(Circular Buffer)的形式使用。

每条journal的内存布局与磁盘布局如下:

可见每条journal中的数据以块为单位,第一块用以记录数据块的数目以及数据块到盘块地址的映射,后跟修改过的数据块。

它的接口十分简单,只有3个函数:

  • struct log_handle* start_transaction(bfs_info *bfs);

    负责新建一个事务,并且:

    1. 获取日志的互斥访问
    2. 执行一些检查工作,比如日志的可用空间是否足够
  • ssize_t log_write_blocks(bfs_info *bfs, struct log_handle *lh, off_t block_number, const void *data, int number_of_blocks);

    记录一项新的变更。

    这里有一条优化是,如果在事务期间同一数据块被多次修改,只保留最后的版本即可。

  • int end_transaction(bfs_info *bfs, struct log_handle *lh);

    结束一个事务,这时会:

    1. 必要时,将日志在内存中的Cache写入磁盘
    2. 同时为日志在内存中的每块Cache绑定一个回调函数。

      这个回调函数会在这块Cache被写入完成后被调用,用以获知何时整个事务写入完毕。

Batching Transactions(或者Group Commit)

出于性能的考虑,BFS并不会在调用end_transaction()时立即将journal写入磁盘,而是将多个事务攒起来,一齐写入。这里只要保证实写在事务写入完毕之后的约束就好了。

实例:Ext2

与BFS为一条操作新建事务然后Group Commit的策略不同,ext2只保留一个全局的事务,一段时间内系统的所有元数据的写操作都交给这同一个事务来记录,随后一齐写入。

Collisions Between Transactions

出于性能考虑,在写入事务期间并不会阻止创建新的事务。如果新的事务需要修改提交中的事务中的数据会怎么办?

这里的一个Workaround是,拷贝一份这块数据的Cache到一块临时的Buffer中,将新的修改都放在这块Buffer上。待前一个事务提交完毕,将这个Buffer中的内容拷贝回数据块对应的Cache即可。


References

  • Unix Internals
  • the Design and Implementation of 4.4BSD
  • Practical File System Design
  • Journaling the Linux ext2fs Filesystem
  • The Design and Implementation of a Log-Structured File System

Footnotes

  1. 简单起见,这里假定文件的引用计数为1。
  2. 但不一定能保证数据不丢失,也不一定能保证用户数据的一致性。这就是为什么数据库程序仍需要自己实现一套Journaling机制的原因之一。
  3. 甚至可以只记录影响一致性的部分,至于时间戳等不那么重要的字段也可以忽略。