本文为MIT 6.S081课程第八章教材内容翻译加整理。
本课程前置知识主要涉及:
今天这节课也是讲解文件系统的logging,这节课讲的是Linux中的广泛使用的ext3文件系统所使用的logging系统,同时我们也会讨论在高性能文件系统中添加log需要面对的一些问题。首先我会花几分钟来回顾一下,为什么我们要学习logging。
这里有一个术语,当我们谈到log时,与今天阅读的论文所用到的journal是同一件事情,它们是同义词。除此之外,今天的论文是有关向ext2增加journal,并得到ext3文件系统(注,所以可以认为ext3文件系统就是ext2加上了logging系统)
。
接下来我将从这几个方面来讨论ext3文件系统:某种程度上将其与XV6进行对比;解释ext3是如何修复XV6的logging存在的性能问题;解释ext3在故障恢复时语义上的一些变化。
首先来回顾一下XV6的logging系统。我们有一个磁盘用来存储XV6的文件系统,你可以认为磁盘分为了两个部分:
(注,Frans和Robert在这里可能有些概念不统一,对于Frans来说,目录内容应该也属于文件内容,目录是一种特殊的文件;而对于Robert来说,目录内容是metadata。)
,另一类就是持有了文件内容的block,或者叫data block。在计算机上,我们会有一些用户程序调用write/create系统调用来修改文件系统。在内核中存在block cache,最初write请求会被发到block cache。block cache就是磁盘中block在内存中的拷贝,所以最初对于文件block或者inode的更新走到了block cache。
在write系统调用的最后,这些更新都被拷贝到了log中,之后我们会更新header block的计数来表明当前的transaction已经结束了。在文件系统的代码中,任何修改了文件系统的系统调用函数中,某个位置会有begin_op,表明马上就要进行一系列对于文件系统的更新了,不过在完成所有的更新之前,不要执行任何一个更新。在begin_op之后是一系列的read/write操作。最后是end_op,用来告诉文件系统现在已经完成了所有write操作。所以在begin_op和end_op之间,所有的write block操作只会走到block cache中。当系统调用走到了end_op函数,文件系统会将修改过的block cache拷贝到log中。
在拷贝完成之后,文件系统会将修改过的block数量,通过一个磁盘写操作写入到log的header block,这次写入被称为commit point。在commit point之前,如果发生了crash,在重启时,整个transaction的所有写磁盘操作最后都不会应用。在commit point之后,即使立即发生了crash,重启时恢复软件会发现在log header中记录的修改过的block数量不为0,接下来就会将log header中记录的所有block,从log区域写入到文件系统区域。
这里实际上使得系统调用中位于begin_op和end_op之间的所有写操作在面对crash时具备原子性。也就是说,要么文件系统在crash之前更新了log的header block,这样所有的写操作都能生效;要么crash发生在文件系统更新log的header block之前,这样没有一个写操作能生效。
在crash并重启时,必须有一些恢复软件能读取log的header block,并判断里面是否记录了未被应用的block编号,如果有的话,需要写(也有可能是重写)log block到文件系统中对应的位置;如果没有的话,恢复软件什么也不用做。
这里有几个超级重要的点,不仅针对XV6,对于大部分logging系统都适用:
所以在XV6中,end_op做了大量的工作,首先是将所有的block记录在log中,之后是更新log header。在没有crash的正常情况,文件系统需要再次将所有的block写入到磁盘的文件系统中。磁盘中的文件系统更新完成之后,XV6文件系统还需要删除header block记录的变更了的block数量,以表明transaction已经完成了,之后就可以重用log空间。
在向log写入任何新内容之前,删除header block中记录的block数量也很重要。因为你不会想要在header block中记录的还是前一个transaction的信息,而log中记录的又是一个新的transaction的数据。可以假设新的transaction对应的是与之前不同的block编号的数据,这样的话,在crash重启时,log中的数据会被写入到之前记录的旧的block编号位置。所以我们必须要先清除header block。
freeing rule的意思就是,在从log中删除一个transaction之前,我们必须将所有log中的所有block都写到文件系统中。
这些规则使得,就算一个文件系统更新可能会复杂且包含多个写操作,但是每次更新都是原子的,在crash并重启之后,要么所有的写操作都生效,要么没有写操作能生效。
要介绍Linux的logging方案,就需要了解XV6的logging有什么问题?为什么Linux不使用与XV6完全一样的logging方案?这里的回答简单来说就是XV6的logging太慢了。
XV6中的任何一个例如create/write的系统调用,需要在整个transaction完成之后才能返回。所以在创建文件的系统调用返回到用户空间之前,它需要完成所有end_op包含的内容,这包括了:
之后才能从系统调用中返回。在任何一个文件系统调用的commit过程中,不仅是占据了大量的时间,而且其他系统调用也不能对文件系统有任何的更新。所以这里的系统调用实际上是一次一个的发生,而每个系统调用需要许多个写磁盘的操作。这里每个系统调用需要等待它包含的所有写磁盘结束,对应的技术术语被称为synchronize。XV6的系统调用对于写磁盘操作来说是同步的(synchronized),所以它非常非常的慢。在使用机械硬盘时,它出奇的慢,因为每个写磁盘都需要花费10毫秒,而每个系统调用又包含了多个写磁盘操作。所以XV6每秒只能完成几个更改文件系统的系统调用。如果我们在SSD上运行XV6会快一些,但是离真正的高效还差得远。
另一件需要注意的更具体的事情是,在XV6的logging方案中,每个block都被写了两次。第一次写入到了log,第二次才写入到实际的位置。虽然这么做有它的原因,但是ext3可以一定程度上修复这个问题。
ext3文件系统就是基于今天要阅读的论文,再加上几年的开发得到的,并且ext3也曾经广泛的应用过。ext3是针对之前一种的文件系统(ext2)logging方案的修改,所以ext3就是在几乎不改变之前的ext2文件系统的前提下,在其上增加一层logging系统。所以某种程度来说,logging是一个容易升级的模块。
ext3的数据结构与XV6是类似的。在内存中,存在block cache,这是一种write-back cache(注,区别于write-through cache,指的是cache稍后才会同步到真正的后端)
。block cache中缓存了一些block,其中的一些是干净的数据,因为它们与磁盘上的数据是一致的;其他一些是脏数据,因为从磁盘读出来之后被修改过;有一些被固定在cache中,基于前面介绍的write-ahead rule和freeing rule,不被允许写回到磁盘中。
除此之外,ext3还维护了一些transaction信息。它可以维护多个在不同阶段的transaction的信息。每个transaction的信息包含有:
在磁盘上,与XV6一样:
目前为止,这与XV6非常相似。主要的区别在于ext3可以同时跟踪多个在不同执行阶段的transaction。
接下来我们详细看一下ext3的log中有什么,这与XV6中的log有点不一样。在log的最开始,是super block。这是log的super block,而不是文件系统的super block。log的super block包含了log中第一个有效的transaction的起始位置和序列号。起始位置就是磁盘上log分区的block编号,序列号就是前面提到的每个transaction都有的序列号。log是磁盘上一段固定大小的连续的block。log中,除了super block以外的block存储了transaction。每个transaction在log中包含了:
因为log中可能有多个transaction,commit block之后可能会跟着下一个transaction的descriptor block,data block和commit block。所以log可能会很长并包含多个transaction。我们可以认为super block中的起始位置和序列号属于最早的,排名最靠前的,并且是有效的transaction。
这里有一些细节对于后面的内容很重要。在crash之后的恢复过程会扫描log,为了将descriptor block和commit block与data block区分开,descriptor block和commit block会以一个32bit的魔法数字作为起始。这个魔法数字不太可能出现在数据中,并且可以帮助恢复软件区分不同的block。
有没有可能使用一个descriptor block管理两个transaction?是不是只能一个transaction结束了才能开始下一个transaction?
记住这里的log的结构,它对于后面的内容也很重要。
ext3通过3种方式提升了性能:
这些基本上就是ext3有的,而XV6没有的特性。接下来我将一一介绍这里的特性。
有关batching,XV6不是也支持多个系统调用同时执行start_op和end_op,然后再一起commit吗?
首先是异步的系统调用。这表示系统调用修改完位于缓存中的block之后就返回,并不会触发写磁盘。所以这里明显的优势就是系统调用能够快速的返回。同时它也使得I/O可以并行的运行,也就是说应用程序可以调用一些文件系统的系统调用,但是应用程序可以很快从系统调用中返回并继续运算,与此同时文件系统在后台会并行的完成之前的系统调用所要求的写磁盘操作。这被称为I/O concurrency,如果没有异步系统调用,很难获得I/O concurrency,或者说很难同时进行磁盘操作和应用程序运算,因为同步系统调用中,应用程序总是要等待磁盘操作结束才能从系统调用中返回。
另一个异步系统调用带来的好处是,它使得大量的批量执行变得容易。
异步系统调用的缺点是系统调用的返回并不能表示系统调用应该完成的工作实际完成了。举个例子,如果你创建了一个文件并写了一些数据然后关闭文件并在console向用户输出done,最后你把电脑的电给断了。尽管所有的系统调用都完成了,程序也输出了done,但是在你重启之后,你的数据并不一定存在。这意味着,在异步系统调用的世界里,如果应用程序关心可能发生的crash,那么应用程序代码应该更加的小心。这在XV6并不是什么大事,因为如果XV6中的write返回了,那么数据就在磁盘上,crash之后也还在。而ext3中,如果write返回了,你完全不能确定crash之后数据还在不在。所以一些应用程序的代码应该仔细编写,例如对于数据库,对于文本编辑器,我如果写了一个文件,我不想在我写文件过程断电然后再重启之后看到的是垃圾文件或者不完整的文件,我想看到的要么是旧的文件,要么是新的文件。
所以文件系统对于这类应用程序也提供了一些工具以确保在crash之后可以有预期的结果。这里的工具是一个系统调用,叫做fsync,所有的UNIX都有这个系统调用。这个系统调用接收一个文件描述符作为参数,它会告诉文件系统去完成所有的与该文件相关的写磁盘操作,在所有的数据都确认写入到磁盘之后,fsync才会返回。所以如果你查看数据库,文本编辑器或者一些非常关心文件数据的应用程序的源代码,你将会看到精心放置的对于fsync的调用。fsync可以帮助解决异步系统调用的问题。对于大部分程序,例如编译器,如果crash了编译器的输出丢失了其实没什么,所以许多程序并不会调用fsync,并且乐于获得异步系统调用带来的高性能。
这是不是有时也被称为flush,因为我之前经常听到这个单词?
以上就是异步系统调用,下一个ext3使用的技术是批量执行(batching)。在任何时候,ext3只会有一个open transaction。ext3中的一个transaction可以包含多个不同的系统调用。所以ext3是这么工作的:
为什么这是个好的方案呢?
ext3使用的最后一个技术就是concurrency,相比XV6这里包含了两种concurrency。
通常来说会有位于不同阶段的多个transaction,新的系统调用不必等待旧的transaction提交到log或者写入到文件系统。对比之下,XV6中新的系统调用就需要等待前一个transaction完全完成。
如果一个block cache正在被更新,而这个block又正在被写入到磁盘的过程中,会怎样呢?
concurrency之所以能帮助提升性能,是因为它可以帮助我们并行的运行系统调用,我们可以得到多核的并行能力。如果我们可以在运行应用程序和系统调用的同时,来写磁盘,我们可以得到I/O concurrency,也就是同时运行CPU和磁盘I/O。这些都能帮助我们更有效,更精细的使用硬件资源。
接下来我们大概过一下Linux中的文件系统调用,并介绍抽象上每个系统调用的结构。
在Linux的文件系统中,我们需要每个系统调用都声明一系列写操作的开始和结束。实际上在任何transaction系统中,都需要明确的表示开始和结束,这样之间的所有内容都是原子的。所以系统调用中会调用start函数。ext3需要知道当前正在进行的系统调用个数,所以每个系统调用在调用了start函数之后,会得到一个handle,它某种程度上唯一识别了当前系统调用。当前系统调用的所有写操作都是通过这个handle来识别跟踪的(注,handle是ext3 transaction中的一部分数据)。
之后系统调用需要读写block,它可以通过get获取block在buffer中的缓存,同时告诉handle这个block需要被读或者被写。如果你需要更改多个block,类似的操作可能会执行多次。之后是修改位于缓存中的block。
当这个系统调用结束时,它会调用stop函数,并将handle作为参数传入。
除非transaction中所有已经开始的系统调用都完成了,transaction是不能commit的。因为可能有多个transaction,文件系统需要有种方式能够记住系统调用属于哪个transaction,这样当系统调用结束时,文件系统就知道这是哪个transaction正在等待的系统调用,所以handle需要作为参数传递给stop函数。
因为每个transaction都有一堆block与之关联,修改这些block就是transaction的一部分内容,所以我们将handle作为参数传递给get函数是为了告诉logging系统,这个block是handle对应的transaction的一部分。
stop函数并不会导致transaction的commit,它只是告诉logging系统,当前的transaction少了一个正在进行的系统调用。transaction只能在所有已经开始了的系统调用都执行了stop之后才能commit。所以transaction需要记住所有已经开始了的handle,这样才能在系统调用结束的时候做好记录。
基于上面的系统调用的结构,接下来我将介绍commit transaction完整的步骤。每隔5秒,文件系统都会commit当前的open transaction,下面是commit transaction涉及到的步骤:
在一个非常繁忙的系统中,log的头指针一直追着尾指针在跑(注,也就是说一直没有新的log空间)
。在当前最早的transaction的所有步骤都完成之前,或许不能开始commit一个新的transaction,因为我们需要重复利用最早的transaction对应的log空间。不过人们通常会将log设置的足够大,让这种情况就不太可能发生。
你刚刚说没有进程会等待这些步骤完成,那么这些步骤是在哪里完成的呢?
我有个有关重用log空间的问题,假设我们使用了一段特定的log空间,并且这段log空间占据了是刚刚释放出来的所有log空间,但是还不够,那么文件系统会等待另一部分的log空间释放出来吗,还是会做点别的?
是的,所以可能是这样,我先写入T10的block到现有的log空闲区域,但是如果最后log足够大并且我们用光了空闲区域,我们就需要等待T7的空间被释放出来,是吗?
如果新的transaction需要的空间走到了T8,那么现在就需要等待T7,T8结束,这是怎么工作的呢?
有关如何重用log空间,这里有个小细节。在log的最开始有一个super block,所以在任何时候log都是由一个super block和一些transaction组成。假设T4是最新的transaction,之前是T1,T2,T3。
我们是否能重用一段log空间,取决于相应的transaction,例如T2,是否已经commit并且写入到文件系统的实际位置中,这样在crash并重启时就不需要重新执行这段transaction了。同时也取决于T2之前的的所有transaction是否已经被释放了。所有的这些条件都满足时,我们就可以释放并重用T2对应的log空间。
为了简化重启时恢复软件的工作,当决定释放某段log空间时,文件系统会更新super block中的指针将其指向当前最早的transaction的起始位置。
之后如果crash并重启,恢复软件会读取super block,并找到log的起始位置。所以如果crash了,内存中的所有数据都会消失,例如文件系统中记录的哪些block被写入到了磁盘中这些信息都会丢失,所以可以假设这时内存中没有可用的数据,唯一可用的数据存在于磁盘中。当然我们这里的讨论都是基于磁盘还是完好的,所以你可以认为只是一次电力故障,系统突然停止了运行过程,在电力恢复时,断电那一瞬间磁盘中的数据还存在。我们并没有考虑磁盘被损坏或者被摧毁的情况。
crash或许会打断任何在进行中的transaction,或许transaction正在commit,或许transaction正在向文件系统写block。让我重新画一个例子,我们在log中有一个super block,之后是transaction T6,T7,T8,在T8之后是一个已近被释放了log空间的T5,假设T8已经用了T5的一部分空间。并且现在super block指向的是T6的起始位置,因为T6是最早的transaction。
现在crash并重启,恢复软件读取super block就可以知道log的起始位置,之后恢复软件会在log中一直扫描并尝试找到log的结束位置,现在我们需要有一种方式确定log的结束位置。我们知道每个transaction包含了一个descriptor block,里面记录了该transaction中包含了多少个data block,假设descriptor block记录了17个block,那么恢复软件会扫描17个data block,最后是commit block。这样可以一直扫描到T8。
在扫描T8时有两种可能,一种可能是T8完成了commit,并且包含了commit block。这时恢复软件并不知道T8就是最后一个transaction,所以它会接着看T8的commit block的下一个block,来看看这是不是一个有效的descriptor block。我们知道这不是一个descriptor block,而是一个包含在T5内的随机block。现在的问题是恢复软件如何可靠的区分出来呢?
但是,现在我们看到的block可能是包含了任意数据的data block,所以它可能是文件中的一个data block并且也是以魔法数字作为起始。所以这里的最后一个细节是,logging系统需要能区分一个以魔法数字作为起始的descriptor block和一个以魔法数字作为起始的data block。你可以想到各种方法来实现这种区分,ext3是这样做的,当它向log写一个block时,如果这个block既不是descriptor block也不是commit block,但是又以魔法数字作为起始,文件系统会以0替换前32bit,并在transaction的descriptor block中为该data block设置一个bit。这个bit表示,对应的data block本来是以魔法数字作为起始,但是现在我们将其替换成了0。而恢复软件会检查这个bit位,在将block写回到文件系统之前,会用魔法数字替换0。
也就是为了应对某个data block中起始数据是以魔法数字开头的情况。
因此,在log中,除了descriptor和commit block,不会有其他的block以这32bit的魔法数字作为起始。所以我们不会有模棱两可的判断,如果一个commit block之后的block以魔法数字作为起始,那么它必然是一个descriptor block。所以恢复软件会从super block指向的位置开始一直扫描,直到:
这时,恢复软件会停止扫描,并认为最后一个有效的commit block是log的结束位置。或许在最后一个commit block之后会跟一个并没有commit完成的transaction(注,上面的第二种情况),但是恢复软件会忽略未完成的transaction,因为这个transaction并没有包含所有的写操作,所以它并不能原子性的恢复。之后恢复软件会回到log的最开始位置,并将每个log block写入到文件系统的实际位置,直到走到最后一个有效的commit block。之后才是启动剩下的操作系统,并且运行普通的程序。在恢复完成之前,是不能运行任何程序的,因为这个时候文件系统并不是有效的。
XV6相比这里的log机制,缺少了什么呢?
但是在XV6我还是可以有多个transaction,只是说不能异步的执行它们,对吗?
以上就是ext3中相对来说直观的部分。实际上还有一些棘手的细节我想讨论一下。之前我提到过,ext3中存在一个open transaction,但是当ext3决定要关闭该transaction时,它需要等待该transaction中的所有系统调用都结束,之后才能开始新的transaction。假设我们现在有transaction T1,其中包含了多个系统调用。
如果我们想要关闭T1,我们需要停止接收新的系统调用,因为我们想要等待现有的系统调用结束,这样才能commit transaction。所以直到这些系统调用都结束了,在ext3中不能允许开始任何新的系统调用。所以只有在T1中的系统调用完成之后,才能开始在接下来的transaction T2中接收系统调用。在这之间有一段时间,新的系统调用是被拦截的,这降低了性能,因为我们本来应该执行系统调用的但是又不被允许。
这里的问题是,直到T1中所有的系统调用都结束之前,ext3为什么不让T2中的系统调用开始执行呢?让我们来看一下没有这个限制条件可能会带来的错误的场景。我们假设T1只包含了一个系统调用,这是一个create系统调用用来创建文件x。在create系统调用结束之前,文件系统决定开始一个新的transaction T2用来接收create之后的所有系统调用。我们假设T2在T1结束之前就开始了,T2对另一个文件y调用了unlink系统调用。unlink会释放与y关联的inode。
假设在下面的时间点T2将inode标记为空闲的,create会为x分配inode,或许它在之后的一个时间点分配了inode。
因为create在unlink释放inode之后分配的inode,它可能会重用同一个inode,所以x可能会获得y的inode,假设是inode 17。目前为止没有问题,因为unlink本来就是释放inode。当T1中的create结束之后,我们会关闭T1,在最后我们会将T1的所有更新都写入到磁盘的log中。之后unlink还要花点时间才能结束,但是在它结束之前计算机crash了。
在重启并运行恢复软件时,可以发现T1已经commit了,而T2没有。所以恢复软件会完全忽略T2,这意味着T2中的unlink就跟没有发生过一样,恢复软件不会执行T2中的unlink,也就不会删除文件y。所以crash并重启之后y文件仍然存在,并还在使用inode 17。然而T1又完成了,x文件使用的也是inode 17,所以现在我们错误的有了两个文件都使用了相同的inode,这意味着它们共享了文件内容,向一个文件写数据会神奇的出现在另一个文件中。这完全是错误的,因为我们本来想的是删除y,并为x分配一个空闲的inode,而不是一个已经在使用中的inode。这里可以这么想,T2中的unlink修改了一个block,最终这个修改过的block被前一个transaction所使用。T2中修改的信息,被T1所使用了,这意味着我们丢失了T2的原子性。因为T2的目标是unlink的效果要么是全发生,要么是完全不发生。但是刚刚的例子中,因为T1使用了T2中释放的inode,这意味着T2中部分修改已经生效了,但是其他的修改随着crash又丢失了。
或许你可以想到一些修复这里问题的方法,或许T1可以发现inode是由后一个transaction释放的而不去使用它。而ext3采用了一个非常简单的方法,在前一个transaction中所有系统调用都结束之前,它不允许任何新的系统调用执行。所以transaction T1也就不可能看到之后的transaction包含的更新。因为直到T1 commit了,整个unlink都不被允许执行。
当你关闭一个open transaction时,具体会发生什么呢?会对当前的缓存做一个快照吗?
以上是众多ext3需要处理的小细节之一,因为为了支持并发,ext3需要处理各种各样的特殊细节,但是我们没有时间讨论所有的细节。
最后我希望同学们记住的有关logging和ext3的是:
你刚刚说有一个文件系统线程会做这里所有的工作,那么只能有一个这样的线程,否则的话就会有不同步的问题了,对吗?
当你在讨论crash的时候,你有一个图是T8正在使用之前释放的T5的空间,如果T8在crash的时候还没有commit,并且T5的commit block正好在T8的descriptor block所指定的位置,这样会不会不正确的表明T8已经被commit了(注,这时T8有一个假的commit block)?
我们可以在transaction T8开始的时候就知道它的大小吗?
为什么不在descriptor block里面记录commit信息。虽然这样可能不太好,因为要回到之前的一个位置去更新之前的一个block。
log中的data block是怎么写入到文件系统中的?