SoftUpdates一项消除大多数同步写操作的技术(1)

作者及顾问：Marshall Kirk McKusick；卡内基梅隆大学 Gregory R. Ganger中文翻译：北京工业大学计算机学院 李鑫 <delphij@cnfug.org>

　　--------------------------------------------------------------------------这篇论文最初发表于1999年6月6日至11日举行的USENIX年度技术会议中，Freenix会议录的第1-17页。其版权归Marshall Kirk McKusick和Greg Ganger所有，作者保留所有权力。这篇论文在作者的许可下被翻译和重新发布。在保持此版权宣示完整的前提下，允许对本文进行非商业目的的重新发布。--------------------------------------------------------------------------

　　摘要

　　传统上，维持掉电或系统崩溃后的文件系统一致性维护主要采用两种方法：其一是对存在依赖顺序的元数据(metadata)进行同步写入，其二是用写通式日志来将原子操作组织在一起。Soft Updates，一种不同于它们的方法，是一种通过保证元数据按依赖顺序更新来确保磁盘上文件系统的总保持一致的实现机制。使用SoftUpdates避免了对于独立日志或大量同步写操作的需求。同时，它还能将很多以前独立且同步进行的操作合并，从而在文件操作密集的环境(例如程序开发、邮件服务器等)中减少40%-70%的写操作。在提高性能的同时，SoftUpdates还可以更好地维持文件系统的一致性。通过保证不一致性仅存在于未声明的块或i-节点，SoftUpdate能够消除对于系统崩溃后运行文件系统检查程序的依赖。这样，在重启后文件系统立即处于可用状态。另外，可以通过一个后台任务在处于运行状态的文件系统中回收丢失的块和i-节点。

　　这篇论文描述了集成到4.4BSD快速文件系统(Fast Filesystem)中的一个SoftUpdates实现。它详细介绍了建立一个成品级质量的系统时，对研究原型以及BSD系统做的修改。同时，它也讨论了在将SoftUpdates从研究转入现实中的经验、难处，以及从中得到的教训; 那些非常规的文件系统操作(例如，fsck和‘fsync’)，需要进行的重新考虑和增加的代码。最终实现的系统得到的体验证明了早先的研究成果：SoftUpdates很好地融合进了现有的文件系统，保证了元数据关联性，并基本达到了最佳的性能。

　　第1节 研究背景与导言

　　元数据(如文件目录，i-节点，以及空闲块映射表)指明原始数据存储(raw storage)的结构。元数据提供指针和描述符，通过它们将磁盘上的扇区联结成文件，并区分它们。为了长期维持可靠存储，文件系统必须在遭遇非预期的系统崩溃，如断电和操作系统故障时，保证元数据的完整性。由于类似的崩溃通常导致保存于易失性主存中的全部信息的丢失，保存在非易失性存储器(例如，磁盘)中的信息必须总具有足够的一致性以便确定性地重建文件系统的一致。特别地，文件系统在磁盘上的镜像绝不能包含悬挂指针，也不能有足以导致二义性的资源所有权指针，或未引用的活动资源。维持这些原则通常需要顺序地(或按原子操作分组)更新小的元数据对象。

　　

　　过去，BSD快速文件系统(FFS)及其派生系统采用同步写入来保证稳定的存储器写入次序。例如，在BSD系统中创建一个文件，首先需要分配和初始化新的i-节点并填充一个新的目录指向项。由于采用同步写入，文件系统将强制创建文件的应用程序等待这些初始化操作的完成，其结果是，在这些系统中类似创建、删除文件这样的操作将以磁盘，而不是CPU/内存的速度进行。由于磁盘操作相对于其他部件来说更慢，同步写入会降低系统性能。元数据更新问题也可以在采用NVRAM技术的前提下通过其他机制解决，例如，可以使用不间断电源(UPS)或Flash。此时只需要保证NVRAM的一致性，而更新可以按任何方便的方式复制到磁盘上。还有一种是将操作分组为包含某种写进式日志的原子操作或使用 shadowpaging。总而言之，这些方法通过在磁盘上增加可以在系统故障或介质损坏之后用来重建提交的元数据附加信息来达到目的。很多现代文件系统成功地使用了写通式日志来获得比同步写入更好的性能。在[Ganger & Patt, 1994]中建议了另一种方式，SoftUpdates，并在研究模型中进行了评估。使用SoftUpdates，文件系统延迟写入(如回写式缓存)元数据的修改，追踪更新的依赖关系，并在回写时保持它们之间的一一依赖关系。因为很多元数据块包含大量指针，如果依赖关系仅以块级记录时循环依赖会经常发生，因此SoftUpdates追踪以指针为单位的依赖关系，这使得块能够以任意顺序写入。非独立的更新在其他写入前将回滚(rolled-back)，并在写入完成后恢复，循环依赖问题从而被消除。使用SoftUpdates时，应用程序总是看到最新的元数据块副本，而磁盘上的数据总是和其上的其他内容一致。在这篇论文中，我们描述了在NetBSD, OpenBSD, FreeBSD, BSDI操作系统中采用的4.4BSD FFS中集成SoftUpdates的过程。同时，我们讨论了其中的经验、教训，并描述了文件系统中一些比较复杂的难题，使用核心内存追踪依赖关系，完整的“fsync”调用实现，一些系统调用的语义等等。在fsck中正确地检测和处理丢失的资源，干净并正确地完成一个unmount系统调用需要进行的额外考虑，以及相应地增加代码的复杂程度。尽管存在这些困难，我们的性能试验证实了早先研究的结论。特别地，在BSD FFS中使用SoftUpdates消除了绝大多数同步写入，并且，和理论最佳情况(完全异步更新的FFS)的差异不到5%。同时，SoftUpdate使BSD FFS语义更明确、完整性更强健，并提供更好的安全保证。此外，它还能在崩溃之后立即恢复(不再需要先行执行fsck)。这篇论文的其余部分包括：第2节，描述BSD FFS操作中的更新依赖关系；第3节描述BSD SoftUpdates实现如何处理它们，包括关键的数据结构，如何使用这些结构，以及集成到4.4BSD操作系统中的过程；第4节讨论了我们将原型转化为生产环境实现中得到的经验和教训；第5节简要总结了在4.4BSD系统中引入SoftUpdates后的性能改善；第6节讨论了新增的文件系统快照支持，以及这一特性如何在一个活动的文件系统中被用于后台执行的局部fsck；第7节概要描述了BSD SoftUpdates代码的状态和可用性。

　　

　　第2节 BSD快速文件系统中的更新依赖关系

　　很多重要的文件系统操作由一系列相关的对分散的元数据更新组成。为了保证在出现了非预期的故障后能够恢复，这些修改通常必须以一个特定的顺序复制到可靠存储。例如创建一个新文件时，文件系统首先分配一个i-节点，对其进行初始化并创建一个指向它的目录项。如果系统在新目录项已被写入，而对应i-节点尚未写入时崩溃，则完整性将被破坏，因为磁盘上的i-节点状态未知。为了确保元数据的一致性，初始化过的i-节点必须先于新的目录项到达可靠存储器。我们称这一需求为更新依赖关系——安全地写入目录项依赖于首先写入i-节点。更新顺序可以用三条简单的规则描述：

　　1. 绝不在一个结构被初始化之前指向它(例如，i-节点必须在目录项引用它之前初始化)2. 绝不在所有指向某一资源的指针都被清零之前重用这一资源(例如，指向数据块的i-节点指针必须在那个数据块分配给其他i-节点之前全部清零)3. 绝不在指向一个活资源的新指针设置成功之前对旧指针实施复位操作(例如，对一个文件进行更名时，在写入新名字之前不应移去这个i-节点的旧名字)。

　　本节将描述BSD FFS中的更新依赖关系问题，限于篇幅，我们假定读者对[McKusick etal, 1996]描述的BSD FFS有初步的了解。

　　总共有8个BSD FFS操作需要顺序地进行更新以保证崩溃后的恢复：创建文件，删除文件，创建目录，移除目录，文件/目录更名，块分配，间接块维护，以及空闲映射表管理。

　　i-节点和数据块是BSD FFS管理的两种主要资源。为了管理这些资源，使用了两个位映射表来管理这些资源。对于文件系统的每一个i-节点，i-节点位映射表中都有一个对应位，当该位置1表示此i-节点在用，而置0则表示此i-节点空闲。同样，对于每个数据块，在数据块位映射表中也有一个对应位表示它是空闲还是在用。FFS文件系统可以被分割为以柱面组(cylinder groups)为单位的固定大小的单元。每个柱面组都有一个包括在当前柱面组中的i-节点和数据块的位映射表的块。对于一个大的文件系统，这一组织结构使核心内存(kernel memory)中能够只存放这种小的文件系统单元。活动的柱面组都被存放在单独的I/O缓冲区中，并可以进行独立于其他柱面组的写操作。

　　创建文件时，在不同的独立块中的三组元数据都将被修改。首先是一个新的、初始化过的i-节点，其内容包括文件类型、被设置为1的连接计数(这表示它是活动的，如被某一目录项引用)、它的权限以及其他信息；随后是i-节点位映射表，以反映i-节点被分配这一状况；最后是新目录项，它将包括新的文件名，以及一个指向i-节点的指针。为确保位映射表总反映全部已经分配资源，位映射表必须在i-节点或目录项之前写入。由于初始化好的i-节点在写盘之前处于未知状态，规则1要求所有关于它的相关更新必须它写入后进行。尽管未被明确地要求，绝大多数FFS实现在创建文件这一系统调用返回之前，也写入目录块。这个附加的同步写入确保了当应用程序在其后进行“fsync”系统调用时文件名已经被保存到可靠的存储器中。如果没这么做，那么“fsync”调用将必须查找所有未写入的包含该文件名字的目录块，并写入磁盘。类似的更新依赖关系也存在于为一个i-节点指定另一个名字时(也称hard link，硬连接)，因为增加第二个名字需要文件系统增加i-节点的连接计数，并在写入目录项之前重写这个i-节点。

　　

　　删除文件时，将修改目录块，i-节点，以及若干柱面组位映射表。在目录块中，相关的目录项将被“移除”，这一操作将i-节点指针清零。在i-节点块中，相关i-节点的类型字段、连接计数，以及数据块指针将被清零。被删文件的数据块以及i-节点