摘要.

高性能的事务系统应用程序通常会在历史表中插入行，以提供活动的跟踪；同时，事务系统生成日志记录以用于系统恢复。这两种生成的信息都可以从高效的索引中受益。一个著名的例子是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）列表便完成。