The Log-Structured Merge-Tree (LSM-Tree) 论文原文：https://www.cs.umb.edu/~poneil/lsmtree.pdf
原文部分翻译
摘要：
高性能事务系统应用程序通常在历史记录表中插入行，以提供活动跟踪；同时，事务系统生成用于系统恢复的日志记录。这两种类型的生成信息都可以从高效的索引中受益。众所周知的设置中的一个例子是TPC-a基准应用程序，该应用程序经过修改以支持对特定帐户的帐户活动的历史记录进行有效查询。这需要在快速增长的历史记录表上按帐户id进行索引。不幸的是，标准的基于磁盘的索引结构（如B树）将有效地使事务的I/O成本翻倍，以实时维护这样的索引，从而使系统总成本增加50%。显然，需要一种以低成本维护实时索引的方法。日志结构合并树（LSM树）是一种基于磁盘的数据结构，旨在为在较长时间内经历高速记录插入（和删除）的文件提供低成本索引。LSM树使用一种算法来延迟和批处理索引更改，以一种让人想起合并排序的高效方式将更改从基于内存的组件级联到一个或多个磁盘组件。在此过程中，所有索引值都可以通过内存组件或一个磁盘组件连续访问（除了非常短的锁定期）。与B树等传统访问方法相比，该算法大大减少了磁盘臂的移动，并将在使用传统访问方法插入磁盘臂的成本超过存储介质成本的领域提高性价比。LSM树方法还推广到插入和删除以外的操作。然而，在某些情况下，需要立即响应的索引查找将失去I/O效率，因此LSM树在索引插入比检索条目的查找更常见的应用程序中最有用。例如，这似乎是历史记录表和日志文件的常见属性。第6节的结论将LSM树访问方法中内存和磁盘组件的混合使用与混合方法在内存中缓冲磁盘页面的普遍优势进行了比较。
1.简介
随着活动流管理系统中的长期事务变得可商业化（[10]、[11]、[12]、[20]、[24]、[27]），将越来越需要提供对事务日志记录的索引访问。传统上，事务日志记录侧重于中止和恢复，并要求系统在正常处理中引用相对短期的历史，偶尔进行事务回滚，而恢复则使用批处理顺序读取来执行。然而，随着系统承担起更复杂活动的责任，构成单个长期活动的事件的持续时间和数量将增加到有时需要实时回顾过去的事务步骤以提醒用户已经完成了什么的程度。与此同时，系统已知的活动事件的总数将增加到现在用于跟踪活动日志的驻留在存储器中的数据结构不再可行的程度，尽管预计存储器成本会持续下降。需要回答关于大量过去活动日志的查询，这意味着索引日志访问将变得越来越重要。
即使使用当前的事务系统，提供索引以支持对具有高插入量的历史表的查询也有明显的价值。网络、电子邮件和其他几乎是事务性的系统会产生巨大的日志，这往往会损害它们的主机系统。从一个具体且众所周知的例子开始，我们在下面的例子1.1和1.2中探讨了一个修改的TPC-a基准。请注意，本文中给出的示例处理特定的数值参数值，以便于表示；推广这些结果是一项简单的任务。还要注意的是，尽管历史表和日志都涉及时间序列数据，但LSM树的索引条目并不假定具有相同的时间键顺序。与检索率相比，提高效率的唯一假设是高更新率。
五分钟规则
以下两个例子都依赖于五分钟规则[13]。这个基本结果表明，当页面引用频率超过大约每60秒一次时，我们可以通过购买内存缓冲区空间来将页面保存在内存中，从而避免磁盘I/O，从而降低系统成本。大约60秒的时间段，是每秒提供一个I/O的磁盘臂的摊销成本与在一秒内摊销的缓冲4K字节磁盘页的内存成本之间的比率。根据第3节的注释，该比率是COSTP/COSTm除以以兆字节为单位的页面大小。在这里，我们只是用磁盘访问换取内存缓冲区，而这种权衡会带来经济收益。请注意，由于内存价格的下降速度快于磁盘价格，预计60秒的时间段将在未来几年内增长。1995年它比1987年定义的5分钟更小的原因，部分是技术性的（不同的缓冲假设），部分是由于引入了极为廉价的批量生产磁盘。
示例1.1.考虑一下TPC-A基准[26]设想的每秒运行1000个事务的多用户应用程序（这个速率可以缩放，但我们在下面只考虑1000个TPS）。每次交易都会更新一个列值，从Balance列中随机选择一行，从三个表中的每一个表中提取一个金额Delta，该行包含100个字节：Branch表有1000行，Teller表有10000行，Account表有100000000行；然后，事务在提交之前将一个50字节的行写入History表，其中包含列：Account ID、Branch ID、Teller ID、Delta和Timestamp。
预测磁盘和内存成本的公认计算表明，Account表页面在未来几年内不会驻留在内存中（见参考文献[6]），而Branch和Teller表现在应该完全驻留在内存上。在给定的假设下，重复引用Accounts表的同一磁盘页的时间间隔约为2500秒，远低于五分钟规则证明缓冲区驻留合理性所需的频率。现在，每个事务大约需要两个磁盘I/O，一个用于读取所需的Account记录（我们将访问的页面已经在缓冲区中的罕见情况视为无关紧要），另一个用于写出之前的脏Account页面，以便在缓冲区内为读取腾出空间（稳态行为所必需）。因此，1000个TPS将对应于每秒大约2000个I/O。这需要80个磁盘臂（执行器），标称速率为[13]中假设的每磁盘臂每秒25个I/O。自那以后的8年里（1987年至1995年），该速率每年攀升不到10%，因此现在的标称速率约为每秒40个I/O，或每秒2000个I/O时为50个磁盘臂。据计算，TPC应用程序的磁盘成本约为[6]中系统总成本的一半，尽管在IBM大型机系统上的成本略低。然而，支持I/O的成本显然是整个系统成本中不断增长的一部分，因为内存和CPU的成本下降速度都快于磁盘。
示例1.2.现在，我们考虑高插入卷历史记录表上的一个索引，并证明这样的索引实际上使TPC应用程序的磁盘成本翻了一番。历史记录表的“与时间戳连接的帐户ID”（帐户ID ||时间戳）索引对于支持对最近帐户活动的有效查询至关重要，例如：
(1.1) Select * from History
where History.Acct-ID = %custacctid
and History.Timestamp > %custdatetime;
如果不存在Acct ID||时间戳索引，则这样的查询需要直接搜索History表的所有行，因此变得不切实际。Acct ID上的索引单独提供了大部分好处，但如果省略了时间戳，那么接下来的成本考虑不会改变，所以我们在这里假设更有用的串联索引。需要什么资源来实时维护这样一个二级B树索引？我们看到，B树中的条目每秒生成1000个，假设20天的累积期，每天8小时，索引条目为16字节，这意味着9.2 GB磁盘上需要576000000个条目，或者索引叶级别需要大约230万页，即使没有浪费空间。由于交易账户ID值是随机选择的，因此每个交易都需要从该索引中至少读取一个页面，在稳定状态下也需要写入一个页面。根据五分钟规则，这些索引页不会驻留在缓冲区中（磁盘页读取间隔约2300秒），因此所有I/O都指向磁盘。在更新Account表所需的2000个I/O的基础上，每秒增加2000个I/O，这需要额外购买50个磁盘臂，使我们的磁盘需求翻了一番。该图乐观地假设，将日志文件索引保持20天所需的删除可以在空闲使用期间作为批处理作业执行。我们考虑了历史文件上的Acct ID||时间戳索引的B树，因为它是商业系统中使用的最常见的基于磁盘的访问方法，事实上，没有一种经典的磁盘索引结构能够始终如一地提供卓越的I/O成本/性能。我们将在第5节中讨论导致我们得出这一结论的考虑因素。
本文中提出的LSM树访问方法使我们能够用更少的磁盘臂使用来执行帐户ID ||时间戳索引的频繁索引插入，因此成本降低了一个数量级。LSM树使用一种算法来延迟和批处理索引更改，以一种特别有效的方式将更改迁移到磁盘，让人想起合并排序。正如我们将在第5节中看到的，将索引项放置延迟到最终磁盘位置的功能至关重要，在一般的LSM树情况下，有一系列这样的延迟放置。LSM树结构还支持其他索引操作，如删除、更新，甚至具有相同延迟效率的长延迟查找操作。只有那些需要立即做出反应的发现成本仍然相对较高。LSM树有效使用的一个主要领域是在示例1.2等应用程序中，其中检索的频率远低于插入（大多数人不会像开支票或存款那样频繁地询问最近的帐户活动）。在这种情况下，降低索引插入的成本至关重要；同时，find访问非常频繁，必须维护某种索引，因为不可能对所有记录进行顺序搜索。
这是论文的平面图。在第2节中，我们介绍了双分量LSM树算法。在第3节中，我们分析了LSM树的性能，并对多分量LSM树进行了激励。在第4节中，我们简要介绍了LSM树的并发和恢复概念。在第5节中，我们考虑了竞争访问方法及其对感兴趣的应用程序的性能。第6节包含结论，我们在其中评估了LSM树的一些含义，并提供了一些扩展建议。
2.二元LSM树算法
LSM树由两个或多个树状组件数据结构组成。我们在本节中处理简单的两个组件的情况，并假设LSM树正在为History表中的行进行索引，如示例1.2所示。参见下图2.1。两个组件的LSM树有一个较小的组件，它完全驻留在内存中，称为C0树（或C0组件），还有一个较大的组件驻留在磁盘上，称为C1树（或C1组件）。尽管C1组件驻留在磁盘上，但C1中频繁引用的页面节点将照常保留在内存缓冲区中（缓冲区未显示），因此C1的流行高级目录节点可以被视为驻留在内存中。
当生成每个新的历史记录行时，将首先以通常的方式将用于恢复此插入的日志记录写入顺序日志文件。然后，History行的索引条目被插入到驻留在内存中的C0树中，之后它将及时迁移到磁盘上的C1树；对索引条目的任何搜索将首先在C0中查找，然后在C1中查找。C0树中的条目迁移到驻留在磁盘上的C1树之前会有一定的延迟，这意味着需要恢复在崩溃之前没有到达磁盘的索引条目。恢复在第4节中进行了讨论，但目前我们只注意到，允许我们恢复历史记录行的新插入的日志记录可以被视为逻辑日志；在恢复过程中，我们可以重建已经插入的历史记录行，同时重新创建任何所需的条目来索引这些行，以重新获取C0的丢失内容。
将索引条目插入驻留在存储器中的C0树的操作没有I/O成本。然而，与磁盘相比，容纳C0组件的内存容量成本很高，这对其大小造成了限制。我们需要一种有效的方法将条目迁移到位于低成本磁盘介质上的C1树中。为了实现这一点，每当C0树由于插入而达到接近分配的最大值的阈值大小时，正在进行的滚动合并过程用于从C0树中删除一些连续的条目段，并将其合并到磁盘上的C1树中。图2.2描绘了滚动合并过程的概念图。
C1树具有与B树类似的目录结构，但针对顺序磁盘访问进行了优化，节点100%满，根下每一级上的单页节点序列打包在连续的多页磁盘块中，以实现高效的arm使用；这种优化也被用于SB树[21]中。多页块I/O用于滚动合并和远程检索，而单页节点用于匹配索引查找，以最大限度地减少缓冲需求。256KB的多页块大小被设想为包含根以下的节点；根节点根据定义总是一个页面。
滚动合并在一系列合并步骤中起作用。对包含C1树的叶节点的多页块的读取使得C1缓冲器中的一系列条目驻留。然后，每个合并步骤读取在该块中缓冲的C1树的磁盘页面大小的叶节点，将来自叶节点的条目与取自C0树的叶级别的条目合并，从而减小C0的大小，并创建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树的深度（深度大于2）
*. 执行检查点
在第一种情况下，已填充的单个多页块被写入磁盘。在后两种情况下，所有多页块缓冲区和目录节点缓冲区都会刷新到磁盘。
在C0树的最右边的叶条目第一次被写入C1树之后，该过程在两个树的左端重新开始，除了现在和随着连续的通过，C1树的多页叶级块必须被读取到缓冲区中，并与C0树中的条目合并，从而创建要写入磁盘的C1的新的多页页叶块。
一旦合并开始，情况就会变得更加复杂。我们将两个组件的LSM树中的滚动合并过程描绘为具有概念光标，该概念光标以量化的步骤缓慢地循环通过C0树和C1树组件的相等键值，将索引数据从C0树提取到磁盘上的C1树。滚动合并光标的位置在C1树的叶级别上，也在每个更高的目录级别内。在每个级别上，C1树的所有当前合并的多页块通常会分为两个块：“清空”块和“填充”块，前者的条目已经耗尽，但保留了合并光标尚未到达的信息，后者反映了到目前为止合并的结果。将有一个类似的“填充节点”和“清空节点”来定义光标，光标肯定会驻留在缓冲区中。出于并发访问的目的，每一级上的清空块和填充块都包含C1树的整数个页面大小的节点，这些节点恰好驻留在缓冲区中。（在重组单个节点的合并步骤中，对这些节点上的条目的其他类型的并发访问将被阻止。）每当需要将所有缓冲节点完全刷新到磁盘时，每个级别的所有缓冲信息都必须写入磁盘上的新位置（位置反映在上级目录信息中，并有一个顺序日志条目用于恢复）。稍后，当C1树的某个级别上的缓冲区中的填充块填充并且必须再次刷新时，它将转到新的位置。恢复过程中可能仍然需要的旧信息永远不会在磁盘上被覆盖，只有在新写入成功并获得更多最新信息时才会失效。第4节对滚动合并过程进行了更详细的解释，其中考虑了并发和恢复设计。
LSM树的一个重要的效率考虑是，当C1树的特定级别上的滚动合并过程以相对较高的速率通过节点时，所有的读取和写入都在多页块中。通过消除寻道时间和旋转延迟，我们有望获得比正常B树条目插入中涉及的随机页面I/O更大的优势。（这一优势在下文第3.2节中进行了分析。）总是将多页块写入新位置的想法受到Rosenblum和Ousterhout[23]设计的日志结构化文件系统的启发，日志结构化合并树由此得名。请注意，不断使用新的磁盘空间进行新的多页块写入意味着要写入的磁盘区域将被包裹，并且必须重用旧的丢弃块。这种记账可以在内存表中完成；旧的多页块被作废并作为单个单元重用，并且通过检查点来保证恢复。在日志结构文件系统中，旧块的重用涉及大量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）对中循环时，我们通常有理由保留最近插入的Ci中的条目（在最后τi秒内），只允许较旧的条目进入Ci+1。在最频繁的查找引用是最近插入的值的情况下，可以在C0树中完成许多查找，因此C0树实现了有价值的内存缓冲功能。这一点也在[23]中提出，代表了一个重要的效率考虑因素。例如，在中止事件中访问的短期事务UNDO日志的索引在创建后相对较短的时间内将有很大一部分访问，并且我们可以预期这些索引中的大多数将保持驻留在内存中。通过跟踪每个事务的启动时间，我们可以保证，例如，在最后τ0秒内启动的事务的所有日志都将在组件C0中找到，而无需求助于磁盘组件。
2.3 LSM树中的删除、更新和长延迟查找
我们注意到，删除可以与插入共享延迟和批处理的宝贵财产。删除索引行时，如果在C0树中的适当位置没有找到键值条目，则可以将删除节点条目放置在该位置，也按键值进行索引，但要注意要删除的条目row ID（RID）。实际的删除可以在滚动合并过程中的稍后时间进行，当遇到实际的索引条目时：我们说删除节点条目在合并过程中迁移到更大的组件，并在遇到关联条目时消除它。同时，必须通过删除节点条目过滤查找请求，以避免返回对已删除记录的引用。这种过滤在搜索相关键值的过程中很容易执行，因为删除节点条目将位于比条目本身更早的组件的适当键值位置，并且在许多情况下，这种过滤将减少确定条目被删除的开销。导致索引值更改的记录更新在任何类型的应用程序中都是不常见的，但如果我们将更新视为删除后插入，则LSM树可以以延迟的方式处理此类更新。
我们绘制了另一种类型的操作，用于有效地修改索引。一种称为谓词删除的过程提供了一种执行批量删除的方法，只需断言一个谓词，例如时间戳超过20天的所有索引值都将被删除的谓词。当最旧（最大）组件中受影响的条目在滚动合并的正常过程中驻留时，此断言会导致它们在合并过程中被丢弃。另一种类型的操作，长延迟查找，提供了一种有效的方式来响应查询，其中结果可以等待最慢光标的循环周期。在组件C0中插入一个查找注释条目，当它迁移到后面的组件时，查找实际上是在一段较长的时间内执行的。一旦查找注释条目已经分发到LSM树的最大相关组件的适当区域，则用于长延迟查找的RID的累积列表就完成了。