摘要
本文提出了一种新的磁盘存储管理技术，称为日志结构的文件系统。日志结构的文件系统以类似日志的结构将所有的修改按顺序写入磁盘，从而加快了文件写入和崩溃恢复的速度。日志是磁盘上唯一的结构；它包含索引信息，以便可以有效地从日志中读回文件。为了在磁盘上保持大的空闲区域以实现快速写入，我们将日志分成若干段，并使用段清理器来压缩严重碎片化的段的实时信息。我们提出了一系列的模拟，证明了基于成本和效益的简单清理策略的效率。我们已经实现了一个名为Sprite LFS的日志结构文件系统的原型；它在小文件的写入方面比目前的Unix文件系统要好一个数量级，而在读取和大文件的写入方面与Unix的性能相匹配或超过。即使包括清理的开销，Sprite LFS也可以使用70%的磁盘带宽进行写入，而Unix文件系统通常只能使用5-10%。
1 引言
在过去的十年中，CPU的速度急剧增加，而磁盘访问时间只得到缓慢的改善。这种趋势在未来可能会继续下去，它将导致越来越多的应用程序因为磁盘而出现瓶颈。为了减少这个问题的影响，我们设计了一种新的磁盘存储管理技术，称为日志结构的文件系统(log-structured file system)，它比目前的文件系统更有效地使用磁盘。
日志结构的文件系统是基于这样的假设：文件被缓存在主内存中，而且内存大小的增加会使缓存在满足读取请求方面越来越高效[1]。因此，磁盘交互将由写操作主导。log-structured file system 以日志的形式顺序的将所有新信息写入磁盘。这种方法通过消除几乎所有的寻道来显着提高写入性能。日志的顺序性也允许更快的崩溃恢复：目前的Unix文件系统通常必须扫描整个磁盘以恢复崩溃后的一致性，但日志结构的文件系统只需要检查日志中最近的部分。
日志的概念并不新鲜，最近的一些文件系统已经将日志作为一种辅助结构，以加快写入和崩溃恢复的速度[2, 3] 。然而，这些其他的系统只是将日志用于临时存储；信息的持久化仍然是磁盘上的传统随机访问存储结构。相比之下，日志结构的文件系统将数据持久化在日志中：磁盘上没有其他结构。日志包含索引信息，以便可以以与当前文件系统相当的效率回读文件。
为了使日志结构的文件系统有效地运行，它必须确保总是有大段的自由空间可供写入新的数据。这是日志结构文件系统设计中最困难的挑战。在本文中，我们提出了一个基于被称为 “段 “的大空间的解决方案，其中一个段清理程序通过压缩严重碎片化的段中的实时数据，不断地重新生成空段。我们使用一个模拟器来探索不同的清理策略，并发现了一个基于成本和效益的简单而有效的算法：它将较老的、变化较慢的数据与年轻的快速变化的数据分开，并在清理过程中对它们进行不同处理。
我们已经构建了一个名为Sprite LFS的日志结构文件系统原型，该系统现在作为Sprite网络操作系统的一部分在生产中使用[4]。基准程序表明，Sprite LFS的原始写入速度比Unix的小文件写入速度快一个数量级以上。即使是其他工作负载，例如包括读取和大文件访问，Sprite LFS在所有情况下都至少和Unix一样快，只有一种情况除外（文件在随机写入后顺序读取）。我们还测量了生产系统中的长期清理开销。总的来说，Sprite LFS允许大约65-75%的磁盘原始带宽用于写入新数据（其余的用于清理）。作为比较，Unix系统只能利用磁盘原始带宽的5-10%来写新数据；其余的时间都用于寻道。
本文的其余部分被组织成六个部分。第2节回顾了为20世纪90年代的计算机设计文件系统时的问题。第3节讨论了日志结构文件系统的设计方案，并推导出Sprite LFS的结构，特别是对清理机制的关注。第4节描述了Sprite LFS的崩溃恢复系统。第5节使用基准程序和清洁开销的长期测量来评估Sprite LFS。第6节将Sprite LFS与其他文件系统进行比较，第7节为结论。
2 1990年代的文件系统的设计
文件系统的设计受两种原始力量的支配：技术和工作负荷，前者提供了一套基本的构件，后者决定了必须有效地进行的一系列操作。本节总结了正在发生的技术变化，并描述了它们对文件系统设计的影响。它还描述了影响Sprite LFS设计的工作负载，并说明目前的文件系统是如何没有能力应对工作负载和技术变化的。
2.1 技术
技术的三个组成部分对文件系统的设计特别重要：处理器、磁盘和主存储器。处理器之所以重要，是因为它们的速度正以近乎指数级的速度增长，而且这种改进似乎可能会持续到90年代的大部分时间。这给计算机系统的所有其他元素带来了压力，使其也要加速，这样系统才不会变得不平衡。
磁盘技术也在迅速改进，但改进主要是在成本和容量方面，而不是性能方面。磁盘性能有两个组成部分：传输带宽和访问时间。虽然这两个因素都在改善，但改善的速度比CPU速度慢得多。随着磁盘阵列和平行头磁盘的使用，磁盘传输带宽可以得到大幅改善[5]，但访问时间似乎不可能有大的改善（它是由机械运动决定的，很难改善）。如果一个应用程序导致一连串的小磁盘传输，并以寻道方式分开，那么即使有更快的处理器，该应用程序在未来十年内也不可能有很大的速度提升。
技术的第三个组成部分是主内存，它的大小正在以指数级的速度增长。现代文件系统将最近使用的文件数据缓存在主内存中，更大的主内存使得更大的文件缓存成为可能。这对文件系统的行为有两个影响。首先，更大的文件缓存改变了磁盘的工作量，吸收了更大一部分的读取请求[1, 6]。为了安全起见，大多数写请求最终必须反映在磁盘上，所以磁盘流量（和磁盘性能）将越来越多地被写所支配。
大型文件缓存的第二个影响是，它们可以作为写缓冲区，在将任何一个修改过的块写到磁盘之前，可以收集大量的修改过的块。缓冲可以使写块的效率更高，例如，在一次连续的传输中，只用一次寻道就把它们全部写入。当然，写缓冲的缺点是增加了崩溃时的数据损失量。在本文中，我们将假设崩溃并不频繁，在每次崩溃中损失几秒钟或几分钟的工作是可以接受的；对于需要更好的崩溃恢复的应用，可以使用非易失性RAM作为写缓冲器。
2.2 工作负载
几种不同的文件系统工作负载在计算机应用中很常见。对于文件系统设计来说，最难处理的工作负载之一是在办公室和工程环境中发现的。办公室和工程应用往往以对小文件的访问为主；一些研究测得的平均文件大小只有几千字节[1, 6-8]。小文件通常会导致较小的随机磁盘I/O，而且这种文件的创建和删除时间往往被文件系统 “元数据”（用于定位文件属性和块的数据结构）的更新所主导。
以对大文件的顺序访问为主的工作负载，如在超级计算环境中发现的那些，也构成了有趣的问题，但对文件系统软件来说不是。有许多技术可以确保这些文件按顺序排列在磁盘上，因此I/O性能往往受限于I/O和内存子系统的带宽，而不是文件分配策略。在设计一个日志结构的文件系统时，我们决定把重点放在小文件访问的效率上，而把提高大文件访问的带宽留给硬件设计者来解决。幸运的是，Sprite LFS中使用的技术对大文件和小文件都很有效。
2.3 现有文件系统的问题
目前的文件系统有两个普遍的问题，使它们难以应付90年代的技术和工作负荷。首先，它们在磁盘上传播信息的方式导致了太多的小型访问。例如，Berkeley Unix的快速文件系统（Unix FFS）[9]在将每个文件按顺序排列在磁盘上方面相当有效，但它在物理上将不同的文件分开。此外，一个文件的属性（’’inode’’）与文件的内容是分开的，包含文件名的目录条目也是如此。在Unix FFS中创建一个新的文件至少需要五次独立的磁盘I/O，每次都有一次寻道：两次对文件属性的不同访问，加上一次对文件数据、目录数据和目录属性的访问。在这样的系统中写小文件时，只有不到5%的磁盘潜在带宽用于新数据；其余的时间都花在了寻找上。
当前文件系统的第二个问题是，它们倾向于同步写入：应用程序必须等待写入完成，而不是在后台处理写入时继续。例如，即使Unix FFS以异步方式写入文件数据块，但文件系统的元数据结构，如目录和inodes是同步写入的。对于有许多小文件的工作负载，磁盘流量被同步元数据写入所支配。同步写入将应用程序的性能与磁盘的性能结合起来，使应用程序很难从更快的CPU中受益。它们还破坏了文件缓存作为写缓冲器的潜在用途。不幸的是，像NFS[10]这样的网络文件系统已经在过去不存在的地方引入了额外的同步行为。这简化了崩溃恢复，但却降低了写入性能。
在本文中，我们用Berkeley Unix快速文件系统（Unix FFS）作为当前文件系统设计的一个例子，并将其与日志结构的文件系统进行比较。使用Unix FFS的设计是因为它在文献中得到了很好的记录，并在几个流行的Unix操作系统中使用。本节介绍的问题并不是Unix FFS所特有的，在大多数其他文件系统中也可以找到。
3 日志结构文件系统
日志结构文件系统的基本思想是通过在文件缓存中缓冲一系列文件系统更改，然后在单个磁盘写操作中按顺序将所有更改写入磁盘来提高写入性能。写操作写入磁盘的信息包括文件数据块、属性、索引块、目录，以及几乎所有用于管理文件系统的其他信息。对于包含许多小文件的工作负载，日志结构文件系统将传统文件系统的许多小同步随机写入转换为可以利用近 100% 原始磁盘的大型异步顺序传输
虽然日志结构的文件系统的基本想法很简单，但有两个关键问题必须解决以达到日志方法的潜在好处。第一个问题是如何从日志中检索信息；这就是下面第3.1节的主题。第二个问题是如何管理磁盘上的自由空间，使大段的自由空间总是可以用来写入新数据。这是一个更加困难的问题；这是第3.2-3.6节的主题。表1包含了Sprite LFS用于解决上述问题的磁盘数据结构的摘要；本文后面的章节将详细讨论这些数据结构。
3.1. 文件定位和读取
尽管 “日志结构化”这个术语可能意味着需要连续扫描来检索日志中的信息，但在Sprite LFS中却不是这样的。我们的目标是与之相对应或超过Unix FFS的读取性能。为了实现这一目标，Sprite LFS在日志中输出索引结构，允许随机访问检索。Sprite LFS使用的基本结构与Unix FFS使用的结构相同：每个文件都有一个称为inode的数据结构，它包含文件的属性（类型、所有者、权限等）以及文件前十个块的磁盘地址；对于大于十个块的文件，inode还包含一个或多个间接块的磁盘地址，每个间接块包含更多数据或间接块的地址。一旦找到一个文件的inode，读取该文件所需的磁盘I/O数量与Sprite LFS和Unix FFS是一致的.
在 Unix FFS 中，每个索引节点都位于磁盘上的固定位置；给定一个文件的标识号，一个简单的计算就可以得出文件 inode 的磁盘地址。相比之下，Sprite LFS 不会将 inode 放置在固定位置；它们被写入日志。 Sprite LFS 使用一种称为 inode map 的数据结构来维护每个 inode 的当前位置。给定一个文件的标识号，必须索引 inode 映射以确定 inode 的磁盘地址。 inode map被分成块写入日志；每个磁盘上的固定检查点区域标识所有 inode 映射块的位置。幸运的是，inode 映射足够紧凑，可以将活动部分缓存在主内存中：inode 映射查找很少需要磁盘访问。
图1显示了在不同目录下创建两个新文件后，Sprite LFS和Unix FFS中会出现的磁盘布局。虽然这两种布局具有相同的逻辑结构，但日志结构的文件系统产生的布局要紧凑得多。因此，Sprite LFS的写性能比Unix FFS好得多，而其读性能也同样好。
Figure 1 shows the disk layouts that would occur in Sprite LFS and Unix FFS after creating two new files in different directories. Although the two layouts have the same logical structure, the log-structured file system produces a much more compact arrangement. As a result, the write performance of Sprite LFS is much better than Unix FFS, while its read performance is just as good.
3.2 可用空间的管理: segment
日志结构的文件系统最困难的设计问题是可用空间的管理。我们的目标是尽可能的保留最大的可用空间，以便写入新的数据。最初，所有的空闲空间都在磁盘上的一个单一区间内，但是当日志到达磁盘的末端时，由于文件的删除和修改空闲空间将被分割成许多小范围。
因此，文件系统有两个选择：交织(thread)和复制。这在图2中有所说明。第一种选择是把实时数据留在原地, 可用空间与日志相互穿插。不幸的是，交织会导致可用空间严重碎片化，因此不可能进行大的连续写入，而日志结构的文件系统也不会比传统文件系统快。第二种选择是把实时数据从日志中复制出来，以便留下大的可用空间供写入。在本文中，我们将假设实时数据以压缩的形式写回到日志的头部；它也可以被移到另一个日志结构的文件系统中，形成一个日志的层次结构，或者它可以被移到一些完全不同的文件系统或存档。复制的缺点是它的成本，特别是对于生命周期较长的文件；在最简单的情况下，日志在磁盘上循环工作，实时数据被复制回日志中，每一次传递中所有生命周期较长的日志都必须在磁盘上被复制一次。
Sprite LFS使用交织和复制的组合。磁盘被划分为固定大小的段。段总是按顺序从头写到尾，并且在重写段之前必须将所有活动数据复制出段。此外，日志是以段为单位进行的；如果系统可以将生命周期较长的数据收集到一起，形成段，这些段可以被跳过，这样数据就不必被重复复制。段的大小被选择得尽可能大，以便读或写整个段的传输时间远远大于寻求段起始位置的成本。这使得整个段的操作几乎以磁盘的全部带宽运行，无论段的访问顺序如何。Sprite LFS目前使用的段大小为512KB或1M。
3.3. 段的清理机制
将实时数据从段中复制出来的过程被称为 “段清理”。在Sprite LFS中，这是一个简单的三步过程：将一些段读入内存，识别实时数据，并将实时数据写回一个较小数量的清洁段。这个操作完成后，被读取的段被标记为干净的，它们可以用于新的数据或进行额外的清理。
识别每个段中活动的数据是作为清理段工作的一部分, 以便能够被再次写入.还必须能够识别每个区块所属的文件以及区块在文件中的位置；需要这些信息来更新文件的inode，使其指向区块的新位置。Sprite LFS通过在每个区段中写入一个区段摘要块，解决了这两个问题。摘要块标识了写在段中的每一条信息；例如，对于每个文件数据块，摘要块包含文件号和该块的块号。当需要一个以上的日志写入来填充段时，段可以包含多个段摘要块。(当文件缓存中的脏块数量不足以填满一个段时，就会发生部分段的写入。) 段落摘要块在写入过程中造成的开销很小，它们在崩溃恢复过程中（见第4节）以及在清洁过程中很有用。
Sprite LFS还使用段摘要信息来区分活动的块和已被覆盖或删除的块。一旦确定一个块的身份，它的有效性可以通过检查文件的inode或间接块来确定，看适当的块指针是否仍然指向这个块。如果仍有指针指向，那么该块是活动的；如果不是，那么该块是死的。Sprite LFS通过在每个文件的inode 映射条目中保留一个版本号来稍微优化这个检查；每当文件被删除或被截断到长度为0时，版本号就会被增加。版本号与节点号相结合，形成了文件内容的唯一标识符（UID）。区段摘要块为区段中的每个区块记录这个uid；如果区段被清理时，一个区块的uid与当前存储在inode 映射中的uid不匹配，该区块可以立即被丢弃，而不必检查文件的inode。
这种清理方法意味着Sprite中没有自由块列表或位图。除了节省内存和磁盘空间外，消除这些数据结构也简化了崩溃恢复。如果这些数据结构存在，就需要额外的代码来记录这些结构的变化并在崩溃后恢复一致性。
3.4 段清理策略
鉴于上述的基本机制，必须解决四个策略问题:
- 段落清理器应该何时执行？一些可能的选择是让它在后台以低优先级持续运行，或者只在晚上运行，或者只在磁盘空间快用完时运行。
- 一次应该清理多少个段？分段清理提供了一个重新组织磁盘上数据的机会；一次清理的段数越多，重新组织的机会就越多。
- 哪些片段应该被清理？一个明显的选择是那些最零散的，但事实证明这不是最好的选择。
- 当活块被写出时，应该如何分组？一种可能性是试图提高未来读取的局部性，例如，将同一目录下的文件分组为新的区段；我们称这种方法为 “年龄排序”
在我们迄今为止的工作中，我们没有系统地解决上述策列中的前两个问题。Sprite LFS在清洁段的数量低于一个阈值（通常是几十个段）时开始清理段。它每次清理几十个片段，直到清洁片段的数量超过另一个阈值（通常是50-100个清洁片段）。Sprite LFS的整体性能似乎对阈值的确切选择不是很敏感。相比之下，第三和第四个策略决定是非常重要的：根据我们的经验，它们是决定日志结构文件系统性能的主要因素。第3节的其余部分讨论了我们对哪些段要清理以及如何对实时数据进行分组的分析。
我们使用一个叫做写成本的术语来比较清理策略。写入成本是指每写一个字节的新数据，包括所有的清洁开销，磁盘忙碌的平均时间。写入成本表示为如果没有清洁开销，并且数据可以在没有寻道时间或旋转延迟的情况下以全带宽写入所需时间的倍数。写入成本为1.0是完美的：这意味着新数据可以以全磁盘带宽写入，并且没有清洁开销。写入成本为10意味着只有磁盘最大带宽的十分之一被实际用于写入新数据；其余的磁盘时间被用于寻道、旋转延迟或清洁。
对于一个有大段的日志结构的文件系统来说，寻找和旋转延迟对于写入和清理来说都是可以忽略不计的，所以写入成本是移入和移出磁盘的字节总数除以这些代表新数据的字节数。这个成本是由被清理的数据段的利用率（仍然存在的数据部分）决定的。在稳定状态下，清洁器必须为每一个写入的新数据段生成一个清洁段。为了做到这一点，它完整地读取N个数据段，并写出N * u个活数据段（其中u是数据段的利用率，0 ≤ u < 1）。这就为新数据创造了N*(1-u)段连续的可用空间。因此
在上面的公式中，我们做了一个保守的假设，即必须完整地读取一个段以恢复活块；在实践中，只读取活块可能会更快，特别是在利用率很低的情况下（我们还没有在Sprite LFS中尝试过）。如果一个要清理的段没有活块（u = 0），那么就根本不需要读取，写入成本为1.0。
图3显示了写入成本与u的关系。作为参考，Unix FFS在小文件工作负载上最多使用5-10%的磁盘带宽，写入成本为10-20（具体测量见[11]和第5.1节的图8）。有了日志、延迟写入和磁盘请求排序，这可能会提高到带宽的25%左右[12]，或者写入成本为4。 图3表明，为了使日志结构文件系统的性能优于当前的Unix FFS，所清理的段的利用率必须小于0.8；为了使性能优于改进的Unix FFS，利用率必须小于0.5。
值得注意的是，上面讨论的利用率并不是磁盘中包含实时数据的总体比例；它只是被清理的段中实时块的比例。文件使用情况的变化将导致一些区段的利用率低于其他区段，清理者可以选择利用率最低的区段进行清理；这些区段的利用率将低于磁盘的总体平均水平。
即使如此，日志结构文件系统的性能也可以通过减少磁盘空间的整体利用率来提高。由于使用的磁盘空间较少，被清理的段会有较少的活块，从而降低了写入成本。日志结构文件系统提供了一种成本-性能的权衡：如果磁盘空间利用不足，可以实现更高的性能，但每个可用字节的成本很高；如果磁盘容量利用率提高，存储成本降低，但性能也会降低。这种性能和空间利用之间的权衡不是日志结构文件系统所独有的。例如，Unix FFS只允许90%的磁盘空间被文件占用。剩余的10%保持空闲，以允许空间分配算法有效运行。
在一个日志结构的文件系统中，以低成本实现高性能的关键是迫使磁盘进入一个二元段分布，其中大部分段几乎是满的，少数是空的或几乎是空的，而清洁器几乎总是可以用空段工作。这使得磁盘的整体容量利用率很高，但又能提供较低的写入成本。下一节描述了我们如何在Sprite LFS中实现这种双峰分布。
3.5 模拟结果
我们构建了一个简单的文件系统模拟器，以便我们可以在受控条件下分析不同的清理策略。模拟器的模型不反映实际的文件系统使用模式（它的模型比现实严苛得多），但它帮助我们理解随机访问模式和局部性的影响，这两者都可以用来降低清理成本。模拟器将文件系统建模为固定数量的 4 KB 文件，选择的数量可产生特定的整体磁盘容量利用率。在每一步，模拟器用新数据覆盖其中一个文件, 并选择以下两种伪随机访问模式之一：
- Uniform: 每个文件在每个步骤中被选中的可能性相同。
- Hot-and-cold: 文件被分为两组。一组包含10%的文件；它被称为热组，因为它的文件有90%的时间被选中。另一组被称为冷组；它包含90%的文件，但它们只有10%的时间被选中。在组内，每个文件被选中的可能性是相同的。这种访问模式是一种简单的定位形式。
在这种方法中，整个磁盘容量的利用率是恒定的，没有读取流量的模型。模拟器一直运行到所有的干净段被耗尽，然后模拟清洁器的行动，直到干净段的阈值数量再次可用。在每次运行中，都允许模拟器运行，直到写入成本稳定下来，所有的冷启动差异都被消除。
图4将两组模拟的结果叠加到图3的曲线上。 在 “LFS uniform “的模拟中，使用了统一的访问模式。清理器使用了一个简单的贪婪策略，它总是选择使用率最低的片段来清理。当写出实时数据时，清洁器并不试图重新组织数据：实时数据块按照它们在被清洁段中出现的相同顺序写出（对于统一访问模式，没有理由期望从重新组织中得到任何改进）。
即使有统一的随机访问模式，分段利用率的变化也会使写入成本大大低于从整体磁盘容量利用率和公式（1）中预测的水平。例如，在75%的总体磁盘容量利用率下，被清理的段的平均利用率只有55%。在整体磁盘容量利用率低于20%的情况下，写入成本下降到2.0以下；这意味着一些被清理的段根本没有活块，因此不需要被读入。
LFS冷热曲线显示了在访问模式中存在位置性时的写入成本，如上所述。这条曲线的清理策略与’’LFS uniform’’的清理策略相同，只是在再次写出之前，对活块按年龄进行排序。这意味着长寿命（冷）数据倾向于与短寿命（热）数据隔离在不同的区段；我们认为这种方法会导致所需的区段利用率的双峰分布。
图4显示了一个令人惊讶的结果，即位置性和”更好”的分组导致了比没有位置性的系统更差的性能! 我们尝试改变定位程度（例如，95%的访问量为5%的数据），发现随着定位程度的增加，性能越来越差。图5显示了这个非直观的结果的原因。在贪婪策略下，一个段直到成为所有段中利用率最低的，才会被清理。因此，每个段的利用率最终都会下降到清洁阈值，包括冷段。不幸的是，冷段的利用率下降得很慢，所以这些段往往在清洁点以上徘徊很长时间。图5显示，在有位置性的模拟中，比起没有位置性的模拟，更多的段聚集在清理点周围。总的结果是，冷段往往会在很长一段时间内占用大量的空闲块。
在研究了这些数字之后，我们意识到，热段和冷段必须被清洁器区别对待。冷段的可用空间比热段的可用空间更有价值，因为一旦冷段被清理，它将需要很长时间才能重新积累不可用的可用空间。换句话说，一旦系统从有冷数据的段中回收可用块，在冷数据变成碎片并 “再次收回 “之前，它将获得 “保留 “它们的时间。相比之下，清理一个热段的好处较少，因为数据可能会很快死亡，可用空间会迅速重新积累；系统可能会推迟清理，让更多的块在当前段中死亡。一个段的可用空间的价值是基于该段中数据的稳定性。不幸的是，如果不知道未来的访问模式，就无法预测其稳定性。使用一个假设，即一个段中的数据越老，它可能保持不变的时间就越长，稳定性可以通过数据的年龄来估计。
为了测试这个理论，我们模拟了一个新的策列来选择要清理的段。该策列根据清理该段的好处和清理该段的成本对每个段进行评级，并选择好处与成本比率最高的段。效益有两个组成部分：将被回收的可用空间的数量和空间可能保持可用的时间。可用空间的数量只是1-u，其中u是该段的利用率。我们使用段中任何块的最近修改时间（即最年轻的块的年龄）作为空间可能保持可用的时间的估计。清洁的好处是由这两个部分相乘形成的时空乘积。清洁区块的成本是1+u（读取区块的一个单位成本，写回实时数据的u）。结合所有这些因素，我们得到:
我们称此策列为 cost-benefit; 它允许冷段即使利用率比热段高时也会被清理。
我们在冷热访问模式下重新进行了模拟，采用了cost-benefit策略，并对实时数据进行了年龄排序。从图6可以看出，成本效益策略产生了我们所希望的段的双峰分布。清理策略在大约75%的利用率下清理冷段，但要等到热段的利用率达到15%左右才清理。由于90%的写入都是对热文件的写入，所以大部分被清理的段都是热段。图7显示，成本效益策略比贪婪策略减少了多达50%的写入成本，即使在相对较高的磁盘容量利用率下，日志结构的文件系统也比最好的Unix FFS要好。我们模拟了一些其他程度和种类的定位，发现随着定位的增加，成本效益策略变得更好。
仿真实验说服了我们在Sprite LFS中实施cost-benefit。正如在第5.2节中所看到的，Sprite LFS中实际文件系统的行为甚至比图7中预测的要好。
3.6 段使用表
为了支持cost-benefit清理策略，Sprite LFS 维护了一个名为段用法表（segment usage table）的数据结构。对于每个段，该表记录了段中的活动字节数和段中任何块的最新修改时间。这两个值是段清理器在选择要清理的段时使用的。这些值在段被写入时被初始化，当文件被删除或块被覆盖时，活动字节数被递减。如果计数下降到零，则可以在不清理的情况下重用段。段使用表的块被写入日志，块的地址被存储在检查点区域（详见第4节）。
为了按年龄对活动块进行排序，段摘要信息记录了写入该段的最年轻块的年龄。目前，Sprite LFS不保留文件中每个块的修改时间；它只保留整个文件的单一修改时间。对于没有整体修改的文件，这个估计会不正确。我们计划修改段的摘要信息以包括每个块的修改时间。
4 崩溃恢复
当系统崩溃时，在磁盘上进行的最后几次操作可能使其处于不一致的状态（例如，可能写入了一个新文件，但没有写入包含该文件的目录）；在重新启动期间，操作系统必须审查这些操作，以纠正任何不一致的地方。在没有日志的传统Unix文件系统中，系统无法确定最后一次修改的位置，所以它必须扫描磁盘上的所有元数据结构以恢复一致性。这些扫描的成本已经很高了（在典型的配置中为数十分钟），而且随着存储系统的扩展，成本也越来越高。
在一个日志结构的文件系统中，最后一次磁盘操作的位置很容易确定：它们在日志的末尾。因此，在崩溃之后，应该可以很快恢复。日志的这一优点是众所周知的，并且在数据库系统[13]和其他文件系统[2, 3, 14]中都得到了应用。像许多其他的日志系统一样，Sprite LFS使用双管齐下的方法进行恢复：检查点，定义文件系统的一致状态，以及向前滚动，用于恢复自上一个检查点以来写入的信息。
4.1 检查点
检查点是日志中所有文件系统结构一致且完整的位置。 Sprite LFS 使用两阶段过程来创建检查点。首先，它将所有修改的信息写到日志中，包括文件数据块、间接块、inode，以及inode map和segment usage table的块。其次，它将检查点区域写入磁盘上的特殊固定位置。检查点区域包含 inode 映射和段使用表中所有块的地址，加上当前时间和指向最后写入的段的指针。
在重新启动时，Sprite LFS 会读取检查点区域，并使用该信息来初始化主存数据结构。为了处理检查点操作期间的崩溃，实际上有两个检查点区域，检查点操作在这两个区域之间交替进行。检查点时间位于检查点区域的最后一个块中，因此如果检查点操作失败，时间将不会更新。在重新启动时，系统会读取两个检查点区域，并使用最近时间的那个。
Sprite LFS每隔一段时间以及在文件系统被卸载或系统关闭时执行检查点。检查点之间的长间隔可以减少写检查点的开销，但会增加恢复过程中向前滚动所需的时间；短的检查点间隔可以提高恢复时间，但会增加正常操作的成本。Sprite LFS目前使用的检查点间隔为30秒，这可能太短了。一个替代定期检查点的方法是在一定数量的新数据被写入日志后执行检查点；这将对恢复时间设定一个限制，同时在文件系统不以最大吞吐量运行时减少检查点的开销。
4.2 回滚(roll-forward)
原则上，在崩溃后重新启动是安全的，只需读取最新的检查点区域并丢弃该检查点之后日志中的任何数据。这将导致即时恢复，但自上次检查点以来写入的任何数据都会丢失。为了恢复尽可能多的信息，Sprite LFS扫描了上次检查点之后写入的日志段。这个操作被称为 “回滚”。
在回滚过程中，Sprite LFS使用段摘要块中的信息来恢复最近写入的文件数据。当摘要块显示存在一个新的节点时，Sprite LFS会更新它从检查点读取的节点图，这样节点图就会指向新的节点副本。这将自动把文件的新数据块纳入恢复的文件系统。如果发现一个文件的数据块，但没有该文件的inode的新副本，那么回滚的代码就会认为磁盘上的文件的新版本是不完整的，它将忽略新的数据块。
回滚代码还调整从检查点读取的段使用表中的利用率。自检查点以来写入的段的利用率将为零；它们必须被调整以反映回滚后剩余的实时数据。旧段的利用率也必须调整，以反映文件的删除和覆盖（这两种情况可以通过日志中新节点的出现来识别）。
回滚的最后一个问题是如何恢复目录条目和 inode 之间的一致性。每个 inode 都包含引用该 inode 的目录条目数；当计数降为零时，文件将被删除。不幸的是，当一个 inode 已经用新的引用计数写入日志而包含相应目录条目的块尚未写入时，可能会发生崩溃，反之亦然。
为了恢复目录和 inode 之间的一致性，Sprite LFS 为每个目录更改在日志中输出一条特殊记录。该记录包括操作代码（创建、链接、重命名或取消链接）、目录条目的位置（目录的 i 编号和目录中的位置）、目录条目的内容（名称和 i 编号)，以及条目中命名的 inode 的新引用计数。这些记录统称为目录操作日志； Sprite LFS 保证每个目录操作日志条目都出现在日志中对应的目录块或 inode 之前。
在回滚过程中，目录操作日志用于确保目录条目和 inode 之间的一致性：如果出现日志条目但 inode 和目录块没有同时写入，则回滚更新目录和/或 inode 以完成操作 . 回滚操作可能会导致在目录中添加或删除条目，并更新索引节点上的引用计数。 恢复程序将更改的目录、inode、inode 映射和段使用表块附加到日志中，并写入一个新的检查点区域以包含它们。 唯一无法完成的操作是创建一个从未写入 inode 的新文件； 在这种情况下，目录条目将被删除。 除了其他功能外，目录日志还可以轻松提供原子重命名操作。
目录操作日志和检查点之间的交互给 Sprite LFS 带来了额外的同步问题。 特别是，每个检查点必须代表目录操作日志与日志中的 inode 和目录块一致的状态。 这需要额外的同步以防止在写入检查点时修改目录。
5 使用 Sprite LFS 的经验
我们于 1989 年底开始实施 Sprite LFS，到 1990 年中期，它作为 Sprite 网络操作系统的一部分开始运行。 自 1990 年秋季以来，它已被用于管理五个不同的磁盘分区，这些分区被大约 30 名用户用于日常计算。 本文中描述的所有功能都已在 Sprite LFS 中实现，但尚未在生产系统中安装回滚功能。 生产环境中磁盘使用较短的检查点间隔（30 秒），并在重新启动时丢弃最后一个检查点之后的所有信息。
当我们开始这个项目时，我们担心日志结构的文件系统可能比传统文件系统的实现要复杂得多。但实际上，Sprite LFS并没有比Unix FFS[9]更复杂。Sprite LFS在段清理方面有额外的复杂性，但这被Unix FFS所要求的位图和布局策略的取消所补偿；此外，Sprite LFS中的检查点和滚动代码并不比扫描Unix FFS磁盘以恢复一致性的fsck代码[15]更复杂。像Episode[2]或Cedar[3]这样的日志文件系统可能比Unix FFS或Sprite LFS更复杂一些，因为它们同时包括日志和布局代码。
在日常使用中，Sprite LFS给用户的感觉与Sprite中类似Unix FFS的文件系统没有什么不同。原因是所使用的机器速度不够快，在目前的工作负荷下，磁盘被束缚了。例如在修改后的Andrew基准[11]上，使用第5.1节介绍的配置，Sprite LFS只比SunOS快20%。大部分速度的提高是由于Sprite LFS中同步写的取消。即使有了Unix FFS的同步写入，该基准的CPU利用率也超过了80%，限制了磁盘存储管理的变化可能带来的速度提升。
5.1 微型测试
我们用一组小型基准程序来测量Sprite LFS的最佳性能，并将其与SunOS 4.0.3进行比较，后者的文件系统是基于Unix FFS的。这些基准是合成的，所以它们并不代表现实的工作负载，但它们说明了这两个文件系统的优点和缺点。这两个系统使用的机器是Sun-4/260（8.7整数SPECmarks），有32兆内存，一个Sun SCSI3 HBA和一个Wren IV磁盘（1.3 MBytes/sec最大传输带宽，17.5毫秒平均寻道时间）。对于LFS和SunOS，磁盘被格式化为具有大约300兆字节可用存储空间的文件系统。SunOS使用八千字节的块大小，而Sprite LFS使用四千字节的块大小和一百万字节的段大小。在每一种情况下，系统都在运行多用户，但在测试期间是静止的。对于Sprite LFS来说，在基准运行期间没有进行清理，所以测量结果代表了最佳情况下的性能；关于清理开销的测量，见下面的5.2节。
图8显示了一个创建、读取和删除大量小文件的基准测试的结果。在该基准的创建和删除阶段，Sprite LFS的速度几乎是SunOS的10倍。Sprite LFS在读回文件时也更快；这是因为文件是按照创建时的顺序读取的，而且日志结构的文件系统将文件密集地打包在日志中。此外，Sprite LFS在创建阶段只让磁盘保持17%的忙碌，而CPU则处于饱和状态。相比之下，SunOS在创建阶段有85%的时间保持磁盘忙碌，尽管只有大约1.2%的磁盘潜在带宽被用于新数据。这意味着，随着CPU速度的提高，Sprite LFS的性能将再提高4-6倍（见图8（b））。在SunOS中几乎不能预期有任何改进。
尽管Sprite的设计是为了在有许多小文件访问的工作负载上提高效率，但图9显示它在大文件方面也有竞争力的性能。Sprite LFS在所有情况下都比SunOS的写带宽高。它对随机写入的速度要快得多，因为它把它们变成了对日志的连续写入；它对连续写入的速度也更快，因为它把许多块分组为一个大的I/O，而SunOS对每个块执行单独的磁盘操作（SunOS的一个较新版本对写入进行分组[16]，因此应该有与Sprite LFS相当的性能）。两种系统的读取性能相似，除了在随机写入一个文件后按顺序读取的情况；在这种情况下，读取需要在Sprite LFS中寻找，所以其性能大大低于SunOS。
图9说明了一个事实，即日志结构的文件系统在磁盘上产生了与传统文件系统不同的定位形式。传统的文件系统通过假设某些访问模式（文件的顺序阅读，在一个目录中使用多个文件的趋势，等等）来实现逻辑定位；然后，如果有必要，它在写入时额外付出更多，以便在磁盘上为假设的阅读模式组织最佳信息。相比之下，日志结构的文件系统实现了时间上的定位：在同一时间创建或修改的信息将在磁盘上被紧密分组。如果时间定位与逻辑定位一致，就像按顺序写入然后按顺序读取的文件那样，那么日志结构文件系统在大文件上的性能应该与传统文件系统差不多。如果时间定位与逻辑定位不同，那么系统的表现也会不同。Sprite LFS处理随机写入的效率更高，因为它在磁盘上按顺序写入。为了实现逻辑定位，SunOS为随机写入付出了更多的代价，但它处理顺序重读的效率更高。随机读取在这两个系统中具有差不多的性能，尽管块的布局非常不同。然而，如果非顺序读取与非顺序写入的顺序相同，那么Sprite会快得多。
5.2 清理的开销
上一节的微型基准测试结果对 Sprite LFS 的性能给出了乐观的看法，因为它们不包括任何清理开销（基准运行期间的写入成本为 1.0）。 为了评估清理成本和成本效益清理政策的有效性，我们在几个月的时间里记录了我们生产日志结构文件系统的统计数据。 观测了五个系统：
- /user6: Sprite 开发人员的主目录。 工作量包括程序开发、文本处理、电子通信和模拟。
- /pcs 并行处理和 VLSI 电路设计研究的主目录和项目区域。
- /src/kernel Sprite 内核的源代码和二进制文件。
- /swap2 Sprite 客户端工作站交换文件。 工作负载包括 40 个无盘 Sprite 工作站的虚拟内存后备存储。 文件往往很大、稀疏且访问不连续。
- /tmp 40个Sprite工作站的临时文件存储区。
表 2 显示了在四个月的清洁期间收集的统计数据。为了消除启动影响，我们在文件系统投入使用后等待了几个月才开始测量。生产文件系统的行为比第 3 节中的模拟预测的要好得多。尽管整体磁盘容量利用率在 11-75% 之间，但超过一半的已清理段是完全空的。即使是非空段的利用率也远低于平均磁盘利用率。与相应模拟中的 2.5-3 写入成本相比，总体写入成本范围为 1.2 到 1.6。图 10 显示了段利用率的分布，收集在 /user6 磁盘的最近快照中。
我们认为，有两个原因导致Sprite LFS的清理成本低于模拟结果。首先，模拟中的所有文件都只有一个块长。在实践中，有大量较长的文件，而且它们往往是作为一个整体被写入和删除。这就导致了个别区段内更大的位置性。在最好的情况下，如果一个文件比一个区段长得多，删除该文件将产生一个或多个完全空的区段。模拟和现实的第二个区别是，模拟的参考模式均匀地分布在热和冷文件组中。在实践中，有大量的文件几乎从未被写入（现实中的冷段比模拟中的冷段要冷得多）。日志结构的文件系统会将非常冷的文件隔离在段中，并且从不清理它们。在模拟中，每个区段最终都会收到修改，因此必须进行清理。
如果说第5.1节中对Sprite LFS的测量有点过于乐观，那么本节中的测量则是过于悲观。在实践中，有可能在夜间或其他空闲时段进行大量的清洁工作，这样在活动爆发期间就可以获得清洁的片段。我们对Sprite LFS还没有足够的经验来知道这是否可以做到。此外，我们希望Sprite LFS的性能能够随着我们经验的积累和算法的调整而提高。例如，我们还没有仔细分析一次清理多少段的策略问题，但我们认为这可能会影响系统隔离热数据和冷数据的能力。
5.3 崩溃恢复
尽管崩溃恢复代码尚未安装在生产系统上，但该代码运行良好，足以对各种崩溃场景进行定时恢复。 恢复时间取决于检查点间隔以及正在执行的操作的速率和类型。 表 3 显示了不同文件大小和恢复的文件数据量的恢复时间。 不同的崩溃配置是通过运行一个程序生成的，该程序在系统崩溃之前创建了 1、10 或 50 兆字节的固定大小文件。 使用了一个特殊版本的 Sprite LFS，它具有无限的检查点间隔并且从不将目录更改写入磁盘。 在恢复前滚期间，必须将创建的文件添加到 inode 映射、创建目录条目并更新段使用表。
表 3 显示恢复时间随最后一个检查点和崩溃之间写入的文件的数量和大小而变化。 可以通过限制检查点之间写入的数据量来限制恢复时间。 根据表 2 中的平均文件大小和每日写入流量，一个小时的检查点间隔将导致大约一秒的平均恢复时间。 使用观察到的最大写入速率 150 兆字节/小时，对于每 70 秒的检查点间隔长度，最大恢复时间将增加一秒。
5.4 Sprite LFS 中的其他开销
表 4 显示了写入磁盘的各种数据的相对重要性，包括它们在磁盘上占用的活动块数量以及它们代表的写入日志的数据量。 磁盘上 99% 以上的实时数据由文件数据块和间接块组成。 然而，大约 13% 的写入日志的信息由 inode、inode 映射块和段映射块组成，所有这些都倾向于被快速覆盖。 仅 inode 映射就占写入日志的所有数据的 7% 以上。 我们怀疑这是因为 Sprite LFS 目前使用的检查点间隔较短，这会迫使元数据比必要的更频繁地写入磁盘。 当我们安装回滚恢复并增加检查点间隔时，我们预计元数据的日志带宽开销会大幅下降。
6 相关工作
日志结构文件系统概念和 Sprite LFS 设计借鉴了许多不同存储管理系统的思想。 具有类似日志结构的文件系统已经出现在几个关于在一次写入媒体上构建文件系统的提案中[17, 18]。 除了以仅附加方式写入所有更改外，这些系统还维护索引信息，就像 Sprite LFS inode 映射和 inode 一样，用于快速定位和读取文件。 它们与 Sprite LFS 的不同之处在于，介质的一次写入特性使得文件系统无需回收日志空间。
Sprite LFS 中使用的段清理方法很像为编程语言开发的清理垃圾收集器[19]。 在 Sprite LFS 中清理的段期间，成本效益段选择和块的年龄排序将文件分成几代，这与分代垃圾收集方案非常相似[20]。 这些垃圾收集方案与 Sprite LFS 之间的显着区别在于，在分代垃圾收集器中可以进行高效的随机访问，而顺序访问对于在文件系统中实现高性能是必需的。 此外，Sprite LFS 可以利用块一次最多属于一个文件这一事实，使用比编程语言系统中使用的算法更简单的算法来识别垃圾。
Sprite LFS 中使用的日志方案类似于数据库系统中首创的方案。 几乎所有的数据库系统都使用预写日志记录来实现崩溃恢复和高性能[13]，但与 Sprite LFS 不同的是它们使用日志的方式。 Sprite LFS 和数据库系统都将日志视为关于磁盘上数据状态的最新“真相”。 主要区别在于数据库系统不使用日志作为数据的最终存储库：为此保留了一个单独的数据区域。 这些数据库系统的独立数据区意味着它们不需要 Sprite LFS 的段清理机制来回收日志空间。 当记录的更改已写入其最终位置时，可以回收数据库系统中日志占用的空间。 由于所有读取请求都是从数据区处理的，因此可以在不影响读取性能的情况下极大地压缩日志。 通常只将更改的字节写入数据库日志，而不是像 Sprite LFS 中那样写入整个块。
使用“重做日志”的检查点和前滚的 Sprite LFS 崩溃恢复机制类似于数据库系统和对象存储库中使用的技术 [21]。 Sprite LFS 中的实现被简化了，因为日志是数据的最终归宿。 Sprite LFS 恢复不是对单独的数据副本重做操作，而是确保索引指向日志中数据的最新副本。
在文件缓存中收集数据并将其以大批量写方式写入磁盘类似于数据库系统中的组提交概念 [22] 以及主内存数据库系统中使用的技术 [23、24]。
7 结论
日志结构文件系统背后的基本原理很简单：在主内存的文件缓存中收集大量新数据，然后通过可以使用所有磁盘带宽的单个大 I/O 将数据写入磁盘 . 由于需要在磁盘上维护大的空闲区域，实现这个想法很复杂，但是我们的模拟分析和我们使用 Sprite LFS 的经验都表明，可以通过基于成本和收益的简单策略来实现低清理开销。 虽然我们开发了一个日志结构的文件系统来支持具有许多小文件的工作负载，但该方法也适用于大文件访问。 特别是，对于整个创建和删除的非常大的文件，基本上根本没有清理开销。
最重要的是，日志结构文件系统可以比现有文件系统更有效地使用磁盘一个数量级。 这应该可以在 I/O 限制再次威胁到计算机系统的可扩展性之前利用几代更快的处理器。
8 致谢
Diane Greene, Mary Baker, John Hartman, Mike Kupfer, Ken Shirriff and Jim Mott-Smith provided helpful comments on drafts of this paper.
References
John K. Ousterhout, Herve Da Costa, David Harrison, John A. Kunze, Mike Kupfer, and James G. Thompson, ‘‘A Trace-Driven Analysis of the Unix 4.2 BSD File System,’’ Proceedings of the 10th Symposium on Operating Systems Principles, pp. 15-24 ACM, (1985).
Michael L. Kazar, Bruce W. Leverett, Owen T. Anderson, Vasilis Apostolides, Beth A. Bottos, Sailesh Chutani, Craig F. Everhart, W. Anthony Mason, Shu-Tsui Tu, and Edward R. Zayas, ‘‘DEcorum File System Architectural Overview,’’ Proceedings of the USENIX 1990 Summer Conference, pp. 151-164 (Jun 1990).
Robert B. Hagmann, ‘‘Reimplementing the Cedar File System Using Logging and Group Commit,’’ Proceedings of the 11th Symposium on Operating Systems Principles, pp. 155-162 (Nov 1987).
John K. Ousterhout, Andrew R. Cherenson, Frederick Douglis, Michael N. Nelson, and Brent B. Welch, ‘‘The Sprite Network Operating System,’’ IEEE Computer 21(2) pp. 23-36 (1988).
David A. Patterson, Garth Gibson, and Randy H. Katz, ‘‘A Case for Redundant Arrays of Inexpensive Disks (RAID),’’ ACM SIGMOD 88, pp. 109-116 (Jun 1988).
Mary G. Baker, John H. Hartman, Michael D. Kupfer, Ken W. Shirriff, and John K. Ousterhout, ‘‘Measurements of a Distributed File System,’’ Proceedings of the 13th Symposium on Operating Systems Principles, ACM, (Oct 1991).
M. Satyanarayanan, ‘‘A Study of File Sizes and Functional Lifetimes,’’ Proceedings of the 8th Symposium on Operating Systems Principles, pp. 96-108 ACM, (1981).
Edward D. Lazowska, John Zahorjan, David R Cheriton, and Willy Zwaenepoel, ‘‘File Access erformance of Diskless Workstations,’’ Transactions on Computer Systems 4(3) pp. 238-268 (Aug 1986).
Marshall K. McKusick, ‘‘A Fast File System for Unix,’’ Transactions on Computer Systems 2(3) pp.
181-197 ACM, (1984).R. Sandberg, ‘‘Design and Implementation of the Sun Network Filesystem,’’ Proceedings of the USENIX 1985 Summer Conference, pp. 119-130 (Jun 1985).
John K. Ousterhout, ‘‘Why Aren’t Operating Systems Getting Faster As Fast as Hardware?,’’Proceedings of the USENIX 1990 Summer Conference, pp. 247-256 (Jun 1990).
Margo I. Seltzer, Peter M. Chen, and John K. Ousterhout, ‘‘Disk Scheduling Revisited,’’ roceedings of the Winter 1990 USENIX Technical Conference, (January 1990).
Jim Gray, ‘‘Notes on Data Base Operating Systems,’’ in Operating Systems, An Advanced Course, Springer-Verlag (1979).
A. Chang, M. F. Mergen, R. K. Rader, J. A. Roberts, and S. L. Porter, ‘‘Evolution of storage facilities in AIX Version 3 for RISC System/6000 processors,’’ IBM Journal of Research and Development 34(1) pp. 105-109 (Jan 1990).
Marshall Kirk McKusick, Willian N. Joy, Samuel J. Leffler, and Robert S. Fabry, ‘‘Fsck - The UNIX File System Check Program,’’ Unix System Manager’s Manual - 4.3 BSD Virtual VAX-11 Version,
USENIX, (Apr 1986).Larry McVoy and Steve Kleiman, ‘‘Extent-like Performance from a UNIX File System,’’ Proceedings of the USENIX 1991 Winter Conference, (Jan 1991).
D. Reed and Liba Svobodova, ‘‘SWALLOW: A Distributed Data Storage System for a Local Network,’’ Local Networks for Computer Communications, pp. 355-373 North-Holland, (1981).
Ross S. Finlayson and David R. Cheriton, ‘‘Log Files: An Extended File Service Exploiting WriteOnce Storage,’’ Proceedings of the 11th Symposium on Operating Systems Principles, pp. 129-148 ACM, (Nov 1987).
H. G. Baker, ‘‘List Processing in Real Time on a Serial Computer,’’ A.I. Working Paper 139, MIT-AI Lab, Boston, MA (April 1977).
Henry Lieberman and Carl Hewitt, ‘‘A Real-Time Garbage Collector Based on the Lifetimes of Objects,’’ Communications of the ACM 26(6) pp. 419-429 (1983).
Brian M. Oki, Barbara H. Liskov, and Robert W. Scheifler, ‘‘Reliable Object Storage to Support Atomic Actions,’’ Proceedings of the 10th Symposium on Operating Systems Principles, pp. 147-159 ACM, (1985).
David J. DeWitt, Randy H. Katz, Frank Olken, L. D. Shapiro, Mike R. Stonebraker, and David Wood, ‘‘Implementation Techniques for Main Memory Database Systems,’’ Proceedings of SIGMOD 1984, pp. 1-8 (Jun 1984).
Kenneth Salem and Hector Garcia-Molina, ‘‘Crash Recovery Mechanisms for Main Storage Database Systems,’’ CS-TR-034-86, Princeton University, Princeton, NJ (1986).
Robert B. Hagmann, ‘‘A Crash Recovery Scheme for a Memory-Resident Database System,’’ IEEE Transactions on Computers C-35(9)(Sep 1986).