[论文]The Log-Structured Merge-Tree (LSM-Tree)翻译 摘要.高性能的事务系统应用程序通常会在历史表中插入行，以提供活动的跟踪；同时，事务系统生成日志记录以用于系统恢复。这两种生成的信息都可以从高效的索引中受益。一个著名的例子是TPC-A基准应用程序，它被修改以支持对特定账户的历史活动的高效查询。这要求在快速增长的历史表上按账户ID建立索引。不幸的是，标准的基于磁盘的索引结构（例如B树）会有效地将事务的I/O成本加倍，以实时维护这样的索引，从而使系统总成本增加高达50%。显然，找到一种低成本的实时索引维护方法是非常有价值的。Log-Structured Merge-tree (LSM树) 是一种基于磁盘的数据结构，设计用于为高频插入（和删除）记录的文件提供低成本的索引。LSM树使用一种算法，将索引更改推迟并批量处理，以类似归并排序的高效方式将更改从基于内存的组件级联至一个或多个磁盘组件。在此过程中，所有索引值始终可以进行检索（除了非常短暂的锁定期间），可以通过内存组件或磁盘组件之一进行访问。与传统的访问方法（如B树）相比，该算法大大减少了磁盘臂的移动，从而在插入操作的磁盘臂成本高于存储介质成本的领域中提高了成本性能。LSM树方法也可以推广到除插入和删除以外的操作。然而，在某些情况下，需要立即响应的索引查找操作将会失去I/O效率，因此LSM树在插入操作比检索条目更常见的应用中最为有用。例如，这似乎是历史表和日志文件的常见特性。第6节的结论将LSM树访问方法中内存和磁盘组件的混合使用与常见的混合方法优势进行了比较，即将磁盘页缓冲在内存中的优势。引言随着活动流管理系统中的长期事务逐渐商用化（[10], [11], [12], [20], [24], [27]），对事务日志记录的索引访问需求也将不断增加。传统的事务日志记录主要关注事务的中止和恢复，通常只需系统在正常处理过程中参考相对短期的历史，并在偶尔的事务回滚时使用批量顺序读取进行恢复。然而，随着系统承担更复杂的活动，组成单个长期活动的事件持续时间和数量将增加，甚至有时需要实时查看过去的事务步骤，以提醒用户已完成的内容。同时，系统已知的活跃事件总数将增加，以至于目前用于跟踪活跃日志的内存常驻数据结构变得不可行，尽管预计内存成本将继续降低。对大量过去活动日志的查询需求意味着索引日志访问将变得越来越重要。即使在当前的事务系统中，为支持高插入量的历史表查询提供索引也是很有价值的。网络系统、电子邮件以及其他准事务系统往往生成大量日志，给其宿主系统带来负担。为了从具体且广为人知的示例开始，我们在接下来的示例1.1和1.2中探讨了修改后的TPC-A基准。请注意，本文中呈现的示例涉及特定的数值参数以便于演示；推广这些结果是很简单的。另外，虽然历史表和日志都涉及时间序列数据，但LSM树的索引项并不假设具有相同的时间键顺序。提高效率的唯一假设是更新速率高于检索速率。五分钟法则以下两个示例都依赖于“五分钟法则” [13]。这一基本结果表明，当页面引用频率超过每60秒一次时，通过购买内存缓冲区来保持页面在内存中，从而避免磁盘I/O，可以降低系统成本。60秒的时间段是一个近似值，它反映了磁盘臂提供每秒一个I/O的折算成本与4 KB磁盘页面的内存缓冲成本之间的比率。按照第3节的符号表示，这个比率是COSTP/COSTm除以页面大小（以MB为单位）。这里我们只是利用磁盘访问与内存缓冲之间的权衡获得经济上的收益。请注意，随着内存价格下降得比磁盘臂更快，这一60秒的时间段预计会随着时间的推移而增加。1995年时这一时间段比1987年定义的五分钟更短，部分原因是技术因素（不同的缓冲假设），部分原因是极其廉价的大量生产磁盘的引入。示例1.1考虑TPC-A基准所设想的多用户应用程序[26]，其每秒运行1000个事务（此速率可以调整，但以下我们仅考虑1000 TPS）。每个事务在三个表中的一行中随机选取一个包含100字节的行，对其Balance列值进行更新，减去一个Delta金额：Branch表包含1000行，Teller表包含10,000行，而Account表包含100,000,000行；事务然后在提交前向History表写入一行50字节的数据，其中包含列：Account-ID, Branch-ID, Teller-ID, Delta和Timestamp。计算表明，Account表的页面在未来几年内不会常驻内存（见参考文献[6]），而Branch和Teller表应该可以完全驻留在内存中。在给定的假设下，对Account表的同一磁盘页面的重复访问间隔大约为2500秒，远低于根据五分钟法则维持缓冲驻留所需的频率。现在每个事务需要大约两个磁盘I/O，一个用于读取所需的Account记录（我们将访问到缓冲中的页面的情况视为微不足道），另一个用于将之前的脏Account页面写出，以在缓冲区中腾出空间以供读取（这是稳态操作所必需的）。因此，1000 TPS对应于大约2000次I/O每秒。这在假定每磁盘臂每秒25次I/O的名义速率下需要80个磁盘臂（参见[13]）。从1987年到1995年，速率每年增长不到10％，使得名义速率现在大约为每秒40次I/O，即2000 I/O每秒需要50个磁盘臂。根据参考文献[6]，磁盘的成本约占TPC应用系统总成本的一半，尽管在IBM大型机系统上的成本有所减少。然而，随着内存和CPU成本下降速度快于磁盘，支持I/O的成本显然已成为系统总成本的一个日益增长的组成部分。示例1.2现在我们考虑一个高插入量的History表索引，并展示该索引如何实质上将TPC应用程序的磁盘成本翻倍。对于History表上的“Account-ID和Timestamp拼接”（Acct-ID||Timestamp）的索引，对于支持最近账户活动的高效查询至关重要，如以下查询：(1.1)Select * from History where History.Acct-ID = %custacctid and History.Timestamp > %custdatetime; 如果缺少Acct-ID||Timestamp索引，则这样的查询需要直接搜索History表的所有行，因此实际上不可行。仅在Acct-ID上创建索引可以提供大部分的优势，但如果不包含Timestamp，成本考虑不会改变，因此我们在此假设更有用的拼接索引。维护此类实时的B树索引需要哪些资源？我们看到每秒生成1000条B树项，并假设一个20天的累计周期，每天8小时，索引项大小为16字节，这意味着磁盘上有576,000,000个条目，占用约9.2 GB的空间，即在索引叶级上大约需要2.3百万个页面，即使没有浪费空间。由于事务性Acct-ID值是随机选择的，每个事务至少需要一次从该索引中读取页面，并在稳态下还需写出页面。根据五分钟法则，这些索引页面不会驻留在缓冲区中（磁盘页面读取间隔约2300秒），因此所有I/O均为磁盘操作。这种新增的2000次每秒I/O，加上更新Account表所需的2000次每秒I/O，需要额外购买50个磁盘臂，磁盘需求翻倍。上述数值乐观地假设可以在非高峰时段批量执行删除操作，以将日志文件索引保持在20天的长度之内。我们为History文件中的Acct-ID||Timestamp索引选择了B树，因为它是商业系统中最常用的基于磁盘的访问方法，事实上，没有传统的磁盘索引结构能够始终提供更优的I/O成本/性能。我们将在第5节中讨论得出此结论的原因。本文提出的LSM树访问方法使我们能够以更少的磁盘臂使用成本，执行Account-ID||Timestamp索引的频繁插入操作，因此成本降低一个数量级。LSM树采用一种推迟和批量处理索引更改的算法，以类似归并排序的高效方式将更改迁移到磁盘上。正如我们将在第5节看到的那样，将索引项位置推迟到最终磁盘位置的功能至关重要，而在一般的LSM树情况下，还存在一系列级联的推迟位置。LSM树结构还支持索引的其他操作，例如删除、更新，甚至长延迟查找操作，具有相同的推迟效率。只有需要立即响应的查找操作的成本相对较高。LSM树的一个重要应用领域如示例1.2所示，在插入操作远比检索操作频繁的情况下（例如，大多数人查询最近账户活动的频率远低于支票存款的频率）。在这种情况下，降低索引插入成本至关重要；同时，查找访问的频率足够高，以至于必须维护某种类型的索引，因为遍历所有记录的顺序搜索是不可行的。本文的结构如下。在第2节中，我们介绍了双组件的LSM树算法。在第3节中，我们分析了LSM树的性能，并探讨多组件LSM树的动机。在第4节中，我们简要介绍了LSM树的并发性和恢复概念。第5节中，我们考察了在感兴趣的应用中，其他竞争性访问方法的性能。第6节包含结论，评估了LSM树的一些影响，并提供了一些扩展建议。2 双组件LSM树算法LSM树由两个或多个树状的组件数据结构组成。本节我们讨论简单的双组件情况，并假设LSM树用于索引示例1.2中History表中的行。参见下方的图2.1。一个双组件LSM树有一个较小的组件，完全驻留在内存中，称为C0树（或C0组件），以及一个驻留在磁盘上的较大组件，称为C1树（或C1组件）。尽管C1组件驻留在磁盘上，但C1中经常被引用的页面节点会如常保留在内存缓冲区中（缓冲区未显示），因此可以保证C1的高层目录节点驻留在内存中。当生成每条新的History行时，首先将用于恢复该插入的日志记录以常规方式写入顺序日志文件。接着，History行的索引条目插入内存驻留的C0树中，之后它会逐步迁移到磁盘上的C1树中；任何索引条目的搜索会先在C0树中查找，然后再在C1树中查找。在C0树中的条目迁移到磁盘驻留的C1树之前存在一定的延迟（延迟），这意味着需要恢复那些在崩溃前未写入磁盘的索引条目。恢复过程将在第4节中讨论，目前我们仅指出，可以将允许我们恢复History行新插入内容的日志记录视为逻辑日志；在恢复期间，我们可以重建已插入的History行，同时重建必要的索引条目，以重新获得丢失的C0内容。将索引条目插入内存驻留的C0树没有I/O成本。然而，与磁盘相比，容纳C0组件的内存成本较高，这限制了其大小。因此，我们需要一种高效的方法将条目迁移到驻留在低成本磁盘介质上的C1树。为此，只要C0树因插入操作达到接近最大允许的阈值大小，就会启动一个滚动合并过程，将C0树中某一连续段的条目删除，并将其合并到磁盘上的C1树中。图2.2描绘了滚动合并过程的概念图。C1树的目录结构与B树类似，但进行了优化以适应顺序磁盘访问，节点100%填满，根节点以下的每一层中的单页节点序列被打包成连续的多页磁盘块，以提高磁盘臂的效率；这种优化也在SB树中使用过【21】。在滚动合并和长距离检索过程中使用多页块I/O，而在匹配索引查找时使用单页节点，以最小化缓冲需求。设想根节点以下的多页块大小为256 KB，根节点定义上始终为单页。滚动合并以一系列合并步骤执行。C1树的叶节点被读取到一个多页块中，使得C1树中的一系列条目驻留在缓冲区中。每个合并步骤接着读取缓冲块中的一个磁盘页大小的C1树叶节点，将其条目与来自C0树叶级别的条目合并，从而减小C0的大小，并创建C1树的新合并叶节点。在合并前包含旧C1树节点的缓冲多页块称为空块，而新合并的C1树叶节点被写入另一个称为填充块的缓冲多页块中。当这个填充块已满且包含新合并的C1叶节点时，它会写入磁盘上的新空闲区域。图2.2中，新包含合并结果的多页块位于旧节点的右侧。后续的合并步骤将逐步合并C0和C1组件中增大的索引值段，直到达到最大值，滚动合并再从最小值开始。新合并的块被写入新的磁盘位置，因此旧块不会被覆盖，这样在崩溃时可以用于恢复。C1中的父目录节点也缓存在内存中，并会更新以反映新的叶节点结构，但通常会更长时间地保留在缓冲区中以减少I/O；合并步骤完成后，来自C1组件的旧叶节点会被标记为无效，并从C1目录中删除。通常，在每次合并步骤后，合并后的C1组件会剩下一些叶级别的条目，因为合并步骤不太可能恰好在旧叶节点清空时生成一个新节点。多页块也有类似情况，因为当填充块满载新合并的节点时，通常会在缩小的块中仍然保留许多包含条目的节点。这些剩余的条目以及更新的目录节点信息会暂时留在块内存缓冲区中，而不会立即写入磁盘。关于在合并步骤中提供并发性和在崩溃时恢复丢失内存的技术将在第4节详细讨论。为了减少恢复中的重建时间，合并过程会定期进行检查点操作，将所有缓冲的信息强制写入磁盘。2.1 两组件 LSM 树的增长方式为了追踪 LSM 树从开始增长到成熟的演变过程，我们先从第一次插入到内存中的 C0 树组件开始。与 C1 树不同，C0 树不必具有类似 B 树的结构。一方面，节点可以是任意大小：由于 C0 树从不存储在磁盘上，因此我们不需要坚持磁盘页面大小的节点，也不需要牺牲 CPU 效率来最小化树的深度。因此，(2-3) 树或 AVL 树（例如在 [1] 中解释的那样）都可以作为 C0 树的备选结构。当增长中的 C0 树首次达到其阈值大小时，从 C0 树中删除一个最左边的条目序列（应采用高效的批处理方式，而不是一次删除一个条目），并重新组织为 100% 填满的 C1 树叶节点。连续的叶节点从左到右放置在一个缓冲区内的多页块的初始页面中，直到该块填满；然后，这个块被写入磁盘，成为 C1 树磁盘驻留叶级的第一个部分。随着连续叶节点的添加，C1 树的目录节点结构在内存缓冲区中创建，具体细节如下所述。C1 树叶级的连续多页块按不断增加的关键字顺序写入磁盘，以防止 C0 树超过其阈值。C1 树的上层目录节点在单独的多页块缓冲区中或单页缓冲区中维护，具体选择取决于总内存和磁盘臂成本的考量；这些目录节点中的条目包含分隔符，用于将访问导向下方的单页节点，就像 B 树中的结构一样。目的是沿着单页索引节点路径提供高效的精确匹配访问，直达叶级，从而在这种情况下避免多页块读取，以最小化内存缓冲区需求。因此，我们在滚动合并或长程检索时读取和写入多页块，而在索引查找（精确匹配）访问时使用单页节点。支持这种二分方法的稍有不同的结构在 [21] 中提出。C1 目录节点的部分填满的多页块通常允许在写入一系列叶节点块的同时留在缓冲区中。当以下情况发生时，C1 目录节点会被强制写入磁盘上的新位置：一个包含目录节点的多页块缓冲区已满根节点分裂，增加了 C1 树的深度（使其深度大于两层）执行了检查点操作在第一种情况下，已填满的单个多页块会写入磁盘。在后两种情况下，所有多页块缓冲区和目录节点缓冲区都会被刷新到磁盘上。当 C0 树的最右叶节点第一次写入到 C1 树中后，进程会从两个树的左端重新开始，但现在以及之后的每一轮，C1 树的多页叶级块必须读入缓冲区，并与 C0 树中的条目合并，从而创建新的 C1 树多页叶块写入磁盘。一旦合并开始，情况会更加复杂。我们可以将两组件 LSM 树中的滚动合并过程设想为一个概念性的“游标”，该游标以量化步长缓慢地循环穿过 C0 树和 C1 树组件中具有相同键值的部分，将索引数据从 C0 树转移到磁盘上的 C1 树。滚动合并游标在 C1 树的叶级以及每一个更高的目录级别上都有一个位置。在每个级别，所有当前正在合并的 C1 树多页块通常会被分为两个块：“清空”块和“填充”块。“清空”块包含已被耗尽但仍保留未被合并游标触及的信息的条目，而“填充”块则反映了合并到目前为止的结果。类似地，每个级别都会有一个表示游标的“填充节点”和“清空节点”，这些节点肯定会常驻缓冲区。为了支持并发访问，每个级别的清空块和填充块都包含 C1 树中的整页大小节点，这些节点仅暂时驻留在缓冲区中。（在重组个别节点的合并步骤期间，对这些节点条目的其他并发访问会被阻塞。）每当需要完全刷新所有缓冲节点到磁盘时，每个级别的所有缓冲信息必须被写入磁盘上的新位置（其位置会在上级目录信息中反映，并且会有用于恢复的顺序日志条目）。稍后，当 C1 树某一级别中的填充块在缓冲区中装满并需要再次刷新时，它将被写入一个新的位置。旧的信息在恢复期间可能仍需要，因此不会直接覆盖，只是随着更新信息的成功写入而被标记为无效。在第 4 节中有更详细的滚动合并过程的解释，涵盖了并发性和恢复设计。对于 LSM 树来说，当 C1 树某一级别的滚动合并过程以相对较高的速度穿过节点时，所有读写操作都发生在多页块中，这一点在效率上尤为重要。通过消除寻道时间和旋转延迟，相比于普通 B 树中条目插入时涉及的随机页面 I/O，我们可以获得巨大的优势（此优势在第 3.2 节中进行分析）。始终将多页块写入新位置的理念受到了 Rosenblum 和 Ousterhout 提出的日志结构化文件系统（Log-Structured File System）的启发，LSM 树也因此得名。值得注意的是，为新多页块写入连续使用新磁盘空间意味着写入的磁盘区域会循环，旧的已废弃块必须被重用。这种记录可以通过内存表来完成；旧的多页块会被标记为无效并作为单元重新使用，恢复通过检查点来保证。在日志结构化文件系统中，旧块的重用会涉及大量 I/O，因为这些块通常只部分释放，因此重用需要一次块读取和块写入。而在 LSM 树中，块在滚动合并的尾部会完全释放，因此不会涉及额外的 I/O。2.2 在 LSM 树索引中查找当通过 LSM 树索引执行精确匹配查找或需要立即响应的范围查找时，首先会在 C0 树中进行搜索，然后在 C1 树中搜索所需的值或值范围。与 B 树相比，这可能会带来轻微的 CPU 开销，因为可能需要搜索两个目录。对于有多个组件的 LSM 树，还可能会产生一些 I/O 开销。为了对第 3 章有所预见，我们可以将多组件 LSM 树定义为由 C0、C1、C2、...、CK-1 和 CK 组成的索引树结构，组件尺寸依次增大，其中 C0 为内存驻留，其他所有组件都驻留在磁盘上。在所有组件对 (Ci-1, Ci) 之间存在异步滚动合并过程，每当较小的组件 Ci-1 超出其阈值时，条目会从较小组件移动到较大组件中。通常情况下，为保证 LSM 树中的所有条目都被检查到，在进行精确匹配查找或范围查找时，需要通过其索引结构访问每个组件 Ci。然而，也有一些优化方案可以将搜索范围限制在最初的一部分组件内。首先，如果通过生成逻辑确保了唯一索引值，例如时间戳保证唯一性，那么一旦在早期组件 Ci 中找到匹配值，查找即告完成。另一种情况是，如果查找条件使用了最近的时间戳值，那么目标条目还未迁移到最大的组件中时，可以限制我们的搜索范围。当合并游标循环穿过 (Ci, Ci+1) 组件对时，我们经常会有理由保留最近插入的条目（在过去 τi 秒内）在组件 Ci 中，仅允许较旧的条目转移到 Ci+1。如果最常见的查找是针对最近插入的值，则许多查找可以在 C0 树中完成，因此 C0 树发挥了重要的内存缓冲功能。这一点在 [23] 中也有所提及，并且是一个重要的效率考量。例如，在事务终止（abort）事件中访问短期事务 UNDO 日志的索引，创建后的一段相对较短时间内将有大量访问，我们可以预期大多数这些索引会留在内存中。通过记录每个事务的起始时间，我们可以确保所有在过去 τ0 秒内开始的事务日志都可以在 C0 组件中找到，而无需访问磁盘组件。2.3 LSM 树中的删除、更新和长延迟查找我们注意到，删除操作可以与插入操作共享推迟和批处理的宝贵属性。当一个索引行被删除时，如果在 C0 树的相应位置没有找到该键值条目，可以在该位置放置一个删除节点条目，同样以键值为索引，但该条目标记了一个删除的记录 ID（RID）。实际的删除操作可以在滚动合并过程中稍后进行，当实际的索引条目被遇到时：我们说删除节点条目会在合并过程中迁移到较大的组件中，并在遇到时将关联条目删除。与此同时，查找请求必须通过删除节点条目进行过滤，以避免返回已删除记录的引用。在查找相关的键值时，过滤操作很容易执行，因为删除节点条目将位于比该条目本身更早的组件的相应键值位置，并且在许多情况下，这种过滤会减少确定某条目已被删除的开销。在任何类型的应用程序中，记录更新导致索引值变化的情况都很少见，但如果我们将更新视为先删除再插入，LSM 树可以以推迟的方式处理此类更新。我们简要描述了另一种高效的索引修改操作。谓词删除（predicate deletion）是一种通过简单地断言谓词来执行批量删除的方法，例如，断言所有时间戳超过 20 天的索引值将被删除。当受影响的条目位于最旧（最大）的组件中，并在滚动合并的正常过程中变为驻留时，这种断言会导致它们在合并过程中被直接删除。另一种操作是长延迟查找（long-latency find），这为响应查询提供了一种高效的方法，其中结果可以等待最慢游标的循环周期。在组件 C0 中插入一个查找节点条目，查找操作实际上会在一个较长的时间段内进行，随着它向后续组件迁移。一旦查找节点条目已循环到 LSM 树中最大相关组件的适当区域，长延迟查找的累积记录 ID（RID）列表便完成。

[6.S081]journal-design论文翻译 原文journal-designIntroduction文件系统是任何现代操作系统的核心部分，人们期望它们既快速又极其可靠。然而，问题仍然会发生，机器可能会因为硬件、软件或电源故障而意外宕机。在意外重启之后，系统可能需要一段时间才能将其文件系统恢复到一致状态。随着磁盘容量的增长，这段时间可能成为一个严重问题，导致系统下线一小时甚至更长时间，因为磁盘需要进行扫描、检查和修复。尽管磁盘驱动器每年都在变得更快，但与它们巨大的容量增加相比，这种速度增长是适度的。不幸的是，每个磁盘容量翻倍都会导致使用传统文件系统检查技术时恢复时间翻倍。在系统可用性至关重要的情况下，这可能是无法割舍的时间，因此需要一种机制来避免每次机器重启时都需要昂贵的恢复阶段。What’s in a filesystem?任何文件系统都需要满足一定的功能要求，这些要求通常由文件系统所服务的操作系统所决定。文件系统在应用程序中的表现方式是其中之一，操作系统通常要求文件名遵循特定的约定，并且文件具有特定的属性，这些属性以特定的方式进行解释。然而，文件系统的许多内部方面并没有受到如此严格的限制，文件系统的实现者可以在一定程度上自由设计。数据在磁盘上的布局（或者在非本地文件系统的情况下，可能是网络协议）、内部缓存的详细信息以及用于调度磁盘I/O的算法，这些都是可以在不必违反文件系统应用程序接口规范的情况下进行更改的事项。我们选择一种设计而不是另一种设计的原因有很多。与旧文件系统的兼容性可能是一个问题：例如，Linux提供了UMSDOS文件系统，它在标准的MSDOS磁盘文件结构之上实现了POSIX文件系统的语义。在尝试解决Linux上长时间文件系统恢复时间的问题时，我们牢记了一些目标：使用新文件系统不应严重影响性能；不得破坏与现有应用程序的兼容性；文件系统的可靠性不得以任何方式受损。Filesystem Reliability在谈论文件系统可靠性时，有许多问题需要考虑。针对这个特定项目，我们主要关注在文件系统崩溃时能够可靠地恢复内容的可靠性，我们可以确定以下几个方面：保护性：在崩溃之前在磁盘上稳定的数据绝不能受到损坏。显然，正在写入磁盘的文件在崩溃时不能保证完全完好，但是任何已经安全保存在磁盘上的文件都不能被恢复系统触及。可预测性：我们需要可预测的故障模式，以便可靠地进行恢复。原子性：许多文件系统操作需要完成大量单独的IO操作。一个很好的例子是将文件从一个目录重命名为另一个目录。如果这种文件系统操作在磁盘上完全完成或在恢复完成后完全撤销，那么恢复就是原子的。（例如，在重命名示例中，恢复应该在崩溃后将旧文件名或新文件名提交到磁盘，但不应同时存在两者。）Existing implementationsLinux的ext2fs文件系统提供了保护性恢复，但是它是非原子的且不可预测的。实际上，可预测性是一个比表面看起来更复杂的属性。为了能够可靠地在崩溃后清理，恢复阶段必须能够确定在磁盘上遇到不一致性的情况下文件系统当时正在尝试做什么。一般来说，这需要文件系统在单个更新操作更改多个磁盘块时以可预测的顺序将其写入磁盘。有许多实现磁盘写入顺序的方法。最简单的方法是在提交下一个写入设备驱动程序之前等待第一个写入完成，即“同步元数据更新”方法。这是BSD快速文件系统采用的方法，它出现在4.2BSD中，启发了许多后来的Unix文件系统，包括ext2fs。然而，同步元数据更新的主要缺点是其性能。如果文件系统操作需要等待磁盘IO完成，那么我们就无法将多个文件系统更新批量写入单个磁盘。例如，如果我们在同一个目录块上创建了十几个目录条目，那么同步更新要求我们将该块分别写回磁盘十几次。有几种方法可以解决这个性能问题。一种保持磁盘写入顺序的方法，而不必等待IO完成，是在内存中维护磁盘缓冲区之间的顺序，并确保当我们最终写回数据时，直到所有前置块都安全地写入磁盘后，我们才写入一个块，即“延迟有序写入”技术。延迟有序写入的一个复杂之处在于很容易陷入缓存缓冲区之间存在循环依赖的情况。例如，如果我们试图在两个目录之间重命名文件，并同时将另一个文件从第二个目录重命名到第一个目录，则最终会出现两个目录块互相依赖的情况：在另一个目录块写入磁盘之前，不能将任何一个目录块写入磁盘。Ganger的“软更新”机制巧妙地避开了这个问题，如果在我们第一次尝试将缓冲区写入磁盘时，仍存在未解决的依赖关系，则有选择地回滚缓冲区内特定的更新。一旦所有依赖关系都得到满足，缺失的更新将稍后恢复。这使我们能够按任意顺序写出缓冲区，即使存在循环依赖。软更新机制已被FreeBSD采用，并将作为其下一个主要内核版本的一部分提供。然而，所有这些方法都存在一个共同的问题。尽管它们确保整个文件系统操作过程中磁盘的状态是可预测的，但恢复过程仍然需要扫描整个磁盘才能找到并修复任何未完成的操作。恢复变得更可靠，但不一定更快。然而，可以通过不牺牲可靠性和可预测性来加速文件系统恢复。这通常是由保证文件系统更新原子完成的文件系统来实现的（在这些系统中，单个文件系统更新通常称为事务）。原子更新背后的基本原理是，文件系统可以将一整批新数据写入磁盘，但是这些更新在进行最终提交更新之前不会生效。如果提交涉及将单个块写入磁盘，则崩溃只能导致两种情况：要么已经将提交记录写入磁盘，此时可以假定所有已提交的文件系统操作在磁盘上都是完整和一致的；要么提交记录丢失，在这种情况下，我们必须忽略由于崩溃时尚未提交的部分不完整更新而导致的任何其他写入。这自然需要文件系统更新将更新数据的旧版本和新版本都保留在磁盘上的某个地方，直到提交时刻。实现这一点有多种方法。在某些情况下，文件系统将更新数据的新副本保存在与旧副本不同的位置，并且一旦更新被提交到磁盘，就会最终重新使用旧空间。Network Appliance的WAFL文件系统采用了这种方法，它通过维护一个可以通过简单地将树节点复制到新位置并然后在树的根部更新一个磁盘块来以原子方式更新树形文件系统数据。日志结构文件系统通过将所有文件系统数据（包括文件内容和元数据）连续写入磁盘流（“日志”）来实现相同的目的。使用这种方案查找数据的位置可能比传统文件系统更复杂，但是日志具有一个很大的优势，即相对容易在日志中放置标记，以指示在某个点之前所有数据都已提交并且在磁盘上一致。由于日志的性质使得大多数写入以连续的流进行且无需磁盘寻道，因此写入这样的文件系统特别快。许多文件系统都是基于这种设计编写的，包括Sprite LFS和Berkeley LFS。Linux上也有一个原型LFS实现。最后，还有一类原子更新的文件系统，其中未完成更新的旧版本和新版本通过将新版本写入磁盘上的不同位置来保留，直到更新提交为止。提交后，文件系统可以将更新后的磁盘块的新版本写回磁盘上的原位置。这就是“日志”（有时称为“日志增强”）文件系统的工作方式。当更新磁盘上的元数据时，更新将记录在保留用作日志的磁盘的单独区域中。完成的文件系统事务将在日志中添加一个提交记录，只有在提交安全写入磁盘后，文件系统才能将元数据写回其原始位置。事务是原子的，因为在崩溃后我们总是可以根据日志是否包含事务的提交记录来撤消事务（丢弃日志中的新数据）或重做事务（将日志副本复制回原始副本）。许多现代文件系统都采用了此设计的变体。Designing a new filesystem for Linux这种针对Linux的新文件系统设计的主要动机是消除崩溃后长时间的文件系统恢复时间。因此，我们选择了文件系统日志记录方案作为工作的基础。日志记录通过始终记录磁盘上潜在不一致的所有数据到日志中，实现了快速的文件系统恢复。因此，文件系统恢复可以通过扫描日志并将所有已提交的数据复制回主文件系统区域来实现。这样做是快速的，因为日志通常远小于完整的文件系统。它只需要足够大的空间来记录几秒钟的未提交更新。选择日志记录还有另一个重要优势。与传统文件系统不同，日志记录文件系统将临时数据保存在新位置，与磁盘上的永久数据和元数据无关。因此，这种文件系统不要求永久数据以任何特定方式存储。特别是，可以在新文件系统中使用ext2fs文件系统的磁盘结构，并将现有的ext2fs代码用作日志记录版本的基础。因此，我们并不是为Linux设计一个新的文件系统。相反，我们正在向现有的ext2fs添加一个新功能——事务性文件系统日志记录。Anatomy of a transaction在考虑日志记录文件系统时的一个核心概念是事务，对应于文件系统的单个更新。每个应用程序发出的单个文件系统请求都会导致一个事务，其中包含由该请求产生的所有已更改的元数据。例如，对文件的写入将导致对磁盘上文件inode中的修改时间戳的更新，并且如果写入扩展了文件，则可能还会更新长度信息和块映射信息。如果为文件分配了新的块，那么配额信息、空闲磁盘空间和已使用块位图都必须更新，并且所有这些都必须记录在事务中。在事务中还有另一个隐藏的操作，我们必须意识到。事务还涉及读取文件系统的现有内容，这就对事务之间的顺序产生了约束。修改磁盘上的块的事务不能在读取该新数据并根据读取的内容更新磁盘的事务之后提交。即使这两个事务永远不会尝试将相同的块写回，依赖关系仍然存在——想象一下一个事务从目录中的一个块中删除一个文件名，另一个事务将相同的文件名插入到不同的块中。这两个操作可能不会在它们写入的块中重叠，但是第二个操作仅在第一个操作成功后才有效（违反此规则会导致重复的目录条目）。最后，还有一个超出元数据更新顺序的排序要求。在我们可以提交为文件分配新块的事务之前，我们必须确保该事务创建的所有数据块实际上已经被写入磁盘（我们将这些数据块称为依赖数据）。忽略此要求实际上不会损害文件系统的元数据的完整性，但可能导致在崩溃恢复后新文件仍然包含之前的文件内容，这既是安全风险也是一致性问题。Merging transactions许多日志记录文件系统中使用的术语和技术都来自数据库领域，在那里，日志记录是确保复杂事务的原子提交的标准机制。然而，传统数据库事务与文件系统之间存在许多差异，其中一些差异使我们能够大大简化事务处理。最大的两个差异之一是文件系统没有事务中止，而且所有文件系统事务都相对短暂。在数据库中，有时我们希望在事务进行到一半时中止事务，放弃我们到目前为止所做的任何更改，但是在ext2fs中并非如此——在我们开始对文件系统进行任何更改之前，我们已经检查了更改是否可以合法完成。在开始写入更改之前中止事务（例如，如果创建文件操作发现同名文件已存在，则可能中止事务）并不会造成问题，因为在这种情况下，我们可以简单地提交没有更改的事务并达到相同的效果。第二个差异——文件系统事务的短生命周期——很重要，因为它意味着我们可以极大地简化事务之间的依赖关系。如果我们必须处理一些非常长期的事务，那么我们需要允许事务以任何顺序独立提交，只要它们不互相冲突，否则单个搁置的事务可能会拖慢整个系统。然而，如果所有事务都足够快，则我们可以要求事务以严格的顺序顺序提交到磁盘，而不会显著影响性能。有了这个观察结果，我们可以对事务模型进行简化，从而大大减少实现的复杂性，同时提高性能。与其为每个文件系统更新创建一个单独的事务，我们简单地每隔一段时间创建一个新事务，并允许所有文件系统服务调用将它们的更新添加到该单一的系统级合并事务中。这种机制有一个很大的优点。因为合并事务中的所有操作将一起提交到日志中，所以我们不必为非常频繁更新的任何元数据块编写单独的副本。特别是对于创建新文件等操作，通常每次对文件的写入都会导致文件被扩展，从而连续更新相同的配额、位图块和inode块。在合并事务的生命周期内多次更新的任何块只需要提交一次到磁盘即可。关于何时提交当前合并事务并启动新事务的决定是一项策略决策，应该由用户控制，因为它涉及影响系统性能的权衡。提交等待时间越长，日志中就可以合并更多的文件系统操作，因此长期来说需要的IO操作就越少。然而，较长的提交会占用更多的内存和磁盘空间，并且在发生崩溃时留下更大的丢失更新的时间窗口。它们还可能导致磁盘活动风暴，使文件系统的响应时间不太可预测。On-disk representation日志记录的ext2fs文件系统在磁盘上的布局将完全与现有的ext2fs内核兼容。传统的UNIX文件系统通过将每个文件与磁盘上的唯一编号的inode关联来存储数据，并且ext2fs设计已经包含了一些预留的inode编号。我们使用其中一个保留的inode来存储文件系统的日志，除此之外，在所有其他方面，文件系统将与现有的Linux内核兼容。现有的ext2fs设计包括一组兼容性位图，其中的位可以设置为指示文件系统使用某些扩展功能。通过为日志记录扩展功能分配一个新的兼容性位，我们可以确保即使旧内核能够成功挂载新的、带有日志记录的ext2fs文件系统，它们也将被禁止以任何方式对文件系统进行写入。Format of the filesystem journal日志文件的工作很简单：在我们提交事务的过程中，它记录文件系统元数据块的新内容。日志的唯一其他要求是我们必须能够以原子方式提交其中包含的事务。我们向日志中写入三种不同类型的数据块：元数据块、描述符块和头部块。日志元数据块包含一个事务更新后文件系统元数据单个块的完整内容。这意味着无论我们对文件系统元数据块进行多么小的更改，我们都必须写入一个完整的日志块以记录更改。然而，出于以下两个原因，这实际上相对廉价：日志写入通常很快，因为大多数写入日志的操作都是顺序的，并且我们可以轻松地将日志IO批处理成大型簇，以便磁盘控制器有效处理；通过将来自文件系统缓存的更改的整个元数据缓冲区的内容写入日志，我们避免了在日志记录代码中进行大量的CPU工作。Linux内核已经为我们提供了一种非常高效的机制，用于将缓冲区缓存中现有块的内容写入到磁盘的其他位置。每个缓冲区在缓冲区缓存中都由一个称为buffer_head的结构描述，其中包括有关将缓冲区的数据写入的磁盘块的信息。如果我们想要将整个缓冲区块写入到新位置而不干扰buffer_head，我们只需创建一个新的临时buffer_head，将描述从旧缓冲区块复制到其中，然后编辑临时buffer_head中的设备块编号字段，以指向日志文件内的一个块。然后，我们可以直接将临时buffer_head提交给设备IO系统，并在IO完成后丢弃它。描述符块是描述其他日志元数据块的日志块。每当我们要将元数据块写入日志时，我们都需要记录元数据通常位于的磁盘块，以便恢复机制可以将元数据复制回主文件系统。在日志中的每组元数据块之前都会写入一个描述符块，其中包含要写入的元数据块数以及它们的磁盘块编号。描述符块和元数据块都按顺序写入日志，每当我们到达日志末尾时，就重新从日志开头开始写入。始终保持日志的当前头（最后一个写入的块的块编号）和尾部（日志中未被取消固定的最旧块，如下所述）。每当我们用完日志空间时（即日志的头已经循环回到尾部并赶上尾部），我们会暂停新的日志写入，直到日志的尾部已经清理并释放更多空间。最后，日志文件包含一些位于固定位置的头部块。这些记录了日志的当前头和尾部，以及一个序列号。在恢复时，将扫描头部块以找到具有最高序列号的块，并且在恢复过程中扫描日志时，我们只需从记录在该头部块中的尾部到头部的所有日志块。Committing and checkpointing the journal在某个时刻，要么是因为距上次提交已经等待了足够长的时间，要么是因为日志空间不足，我们将希望将未处理的文件系统更新作为一个新的复合事务提交到日志中。一旦复合事务完全提交，我们还没有完成它。我们需要跟踪记录在事务中记录的元数据缓冲区，以便我们可以注意到它们何时被写回到磁盘上的主要位置。回想一下，当我们提交一个事务时，新的更新后的文件系统块位于日志中，但尚未同步回它们在磁盘上的永久位置（我们需要保持旧块未同步，以防在提交日志之前崩溃）。一旦日志已提交，磁盘上的旧版本就不再重要了，我们可以在自己方便的时候将缓冲区写回其主位置。然而，在我们完成同步这些缓冲区之前，我们不能删除日志中的数据副本。要完全提交和完成事务的检查点，我们需要经历以下阶段：关闭事务。此时，我们创建一个新的事务，在其中记录将来开始的任何文件系统操作。任何现有的、未完成的操作仍将使用现有的事务：我们不能将单个文件系统操作分割成多个事务！开始将事务刷新到磁盘。在单独的日志写入内核线程的上下文中，我们开始写入由事务修改的所有元数据缓冲区到日志中。在这个阶段，我们还必须写入任何相关的数据（参见上文中的事务解剖）。当一个缓冲区被提交时，将其标记为固定在事务中，直到它不再是脏的（它已通过常规的写回机制写回到主存储中）。等待此事务中所有未完成的文件系统操作完成。我们可以在所有操作完成之前安全地开始写入日志，并且允许这两个步骤在某种程度上重叠会更快。等待所有未完成的事务更新完全记录在日志中。更新日志头块以记录日志的新头和尾部，将事务提交到磁盘。写入事务的更新缓冲区到日志时，我们标记它们为在日志中固定该事务。只有当缓冲区被同步到其磁盘上的主位置时，它们才会变为未固定。只有当事务的最后一个缓冲区变为未固定时，我们才能重新使用事务占用的日志块。当发生这种情况时，再次写入一组日志头，记录日志尾的新位置。现在释放的空间可以被稍后的事务重用。Collisions between transactions为了提高性能，在提交事务时，我们并不完全暂停文件系统更新。相反，我们创建一个新的复合事务，用于记录在提交旧事务时到达的更新。这就引出了一个问题：如果一个更新要访问已经由另一个正在提交的较旧事务拥有的元数据缓冲区，该怎么办呢？为了提交旧事务，我们需要将其缓冲区写入日志，但我们不能在该写入中包含任何不属于该事务的更改，因为这将允许我们提交不完整的更新。如果新事务只想读取相关缓冲区，那么就没有问题：我们已经在两个事务之间创建了一个读/写依赖关系，但由于复合事务始终按严格的顺序提交，我们可以安全地忽略这种冲突。如果新事务想要写入缓冲区，则情况就更复杂了。我们需要旧缓冲区的副本来提交第一个事务，但我们又不能让新事务在修改缓冲区时继续进行。解决方案是在这些情况下制作缓冲区的新副本。一个副本提供给新事务进行修改。另一个副本仍由旧事务拥有，并将像往常一样提交到日志中。一旦该事务提交，这个副本就会被简单地删除。当然，我们不能在这个缓冲区安全地记录到文件系统其他位置之前回收旧事务的日志空间，但由于该缓冲区必须被提交到下一个事务的日志记录中，这是自动处理的。Project status and future work这仍然是一个正在进行的工作。最初实现的设计稳定且简单，我们不认为需要进行重大的设计修订才能完成实现。上文描述的设计相对直接，除了处理日志文件管理、缓冲区与事务之间的关联以及在非正常关闭后恢复文件系统的代码外，对现有的 ext2fs 代码需要进行的修改很少。一旦我们有一个稳定的代码库进行测试，我们可以在许多可能的方向上扩展基本设计。其中最重要的是调整文件系统性能。这将需要我们研究日志系统中的任意参数对性能的影响，如提交频率和日志大小。这还将涉及研究瓶颈，以确定通过对系统设计进行修改是否可能改进性能，并且已经提出了几个可能的扩展设计。一个研究领域可能是考虑压缩日志更新。当前的方案要求我们将整个元数据块写入日志，即使只修改了块中的一个位也是如此。我们可以通过仅记录缓冲区中的更改值而不是完全记录缓冲区来轻松压缩这样的更新。然而，目前尚不清楚这是否会带来任何重大的性能优势。当前的方案对于大多数写操作不需要进行内存到内存的复制，这在CPU和总线利用率方面是一个很大的性能优势。由于写出整个缓冲区产生的IO操作是廉价的 - 更新是连续的，在现代磁盘IO系统上，它们直接从主存储器传输到磁盘控制器，而无需通过缓存或CPU。另一个重要的可能的扩展领域是支持快速 NFS 服务器。NFS 设计允许客户端在服务器崩溃时优雅地恢复：客户端将在服务器重新启动时重新连接。如果发生这样的崩溃，则服务器尚未安全写入磁盘的任何客户端数据都将丢失，因此 NFS 要求服务器在将客户端的文件系统请求提交到服务器的磁盘之前不得确认其完成。这对于支持通用目的的文件系统来说可能是一个尴尬的特性。NFS 服务器的性能通常是通过对客户端请求的响应时间来衡量的，如果这些响应必须等待文件系统更新同步到磁盘，那么整体性能将受到在磁盘上的文件系统更新延迟的限制。这与文件系统的大多数其他用途相反，在这些用途中，性能是根据缓存更新的延迟而不是磁盘上的更新延迟来衡量的。有一些文件系统专门设计来解决这个问题。WAFL 是一种基于事务的树型文件系统，可以在磁盘的任何位置写入更新，但是 Calaveras 文件系统通过使用类似于上文提出的日志的方式达到相同的目标。区别在于 Calaveras 为每个应用程序文件系统请求在日志中记录一个单独的事务，从而尽快在磁盘上完成单个更新。提议的 ext2fs 日志记录中的提交批处理牺牲了快速提交以获得吞吐量，而代价是延迟（磁盘上的延迟被缓存的影响隐藏了）。ext2fs 日志记录可能使其更适合用于 NFS 服务器的两种方法可能是使用较小的事务和记录文件数据以及元数据。通过调整提交到日志的事务的大小，我们可能能够大幅改进提交单个更新的回转时间。NFS 还要求将数据写入磁盘尽快提交，原则上没有理由不扩展日志文件以涵盖普通文件数据的写入。最后，值得注意的是，这个方案中没有任何阻止我们将单个日志文件共享给几个不同的文件系统。在一个单独的完全为此目的保留的磁盘上允许多个文件系统记录日志几乎不需要额外的工作，而在有许多经历重负的日志文件系统的情况下，这可能会带来显著的性能提升。这个独立的日志磁盘几乎完全是顺序写入的，因此可以维持高吞吐量，而不会影响主文件系统磁盘上可用的带宽。Conclusions本文中概述的文件系统设计应该相对现有的 Linux 上的 ext2fs 文件系统提供显著优势。它应该通过使文件系统在崩溃后更可预测地和更快速地恢复来提高可用性和可靠性，并且在正常操作期间不会造成太大的性能损失。日常性能的最显著影响是，新创建的文件将需要迅速同步到磁盘，以便将创建操作提交到日志，而不是允许内核通常支持的数据延迟写回。这可能使得日志文件系统不适合在 /tmp 文件系统上使用。该设计应该对现有的 ext2fs 代码库需要进行最少的更改：大部分功能由一个新的日志机制提供，该机制将通过简单的事务缓冲区 IO 接口与主要的 ext2fs 代码进行交互。最后，这里提出的设计是基于现有的 ext2fs 磁盘文件系统布局的，因此可以向现有的 ext2fs 文件系统添加一个事务日志，利用新功能，而无需重新格式化文件系统。