翻译：The Log-Structured Merge-Tree (LSM-Tree)
翻译：The Log-Structured Merge-Tree (LSM-Tree)
Patrick O'Neil[1], Edward Cheng[2]
Dieter Gawlick[3], Elizabeth O'Neil[1]
摘要
高性能事务系统应用程序通常在提供活动跟踪的历史记录表；同时，事务系统生成$日志记录，用于系统恢复。这两种生成的信息都可以受益于有效的索引。众所周知的设置中的一个例子是TPC-a基准应用程序，该应用程序经过修改以支持对特定账户的账户活动历史记录的有效查询。这需要在快速增长的历史记录表上按帐户id进行索引。不幸的是，基于磁盘的标准索引结构（如B树）将有效地使事务的输入/输出成本翻倍，以实时维护此类索引，从而使系统总成本增加50%。显然，需要一种以低成本维护实时索引的方法。日志结构合并树（LSM树）是一种基于磁盘的数据结构，旨在为长时间内经历高记录插入（和删除）率的文件提供低成本索引。LSM树使用一种延迟和批量索引更改的算法，以一种类似于合并排序的有效方式将基于内存的组件的更改级联到一个或多个磁盘组件。在此过程中，所有索引值都可以通过内存组件或其中一个磁盘组件连续进行检索（除了非常短的锁定期）。与传统访问方法（如B-树）相比，该算法大大减少了磁盘臂的移动，并将在使用传统访问方法进行插入的磁盘臂成本超过存储介质成本的领域提高成本性能。LSM树方法还推广到插入和删除以外的操作。然而，在某些情况下，需要立即响应的索引查找将失去输入/输出效率，因此LSM树在索引插入比检索条目的查找更常见的应用程序中最有用。例如，这似乎是历史表和日志文件的常见属性。第6节的结论将LSM树访问方法中内存和磁盘组件的混合使用与混合方法在内存中缓冲磁盘页面的常见优势进行了比较。
1、引言
随着活动流管理系统中的长寿命事务在商业上可用（10、11、12、20、24、27），将越来越需要提供对事务日志记录的索引访问。传统上，事务日志记录侧重于中止和恢复，并要求系统在正常处理中引用相对较短的历史，偶尔进行事务回滚，而恢复是使用批处理顺序读取执行的。然而，随着系统承担更复杂活动的责任，组成单个长期活动的事件的持续时间和数量将增加，有时需要实时查看过去的事务步骤，以提醒用户已经完成了什么。同时，系统已知的活动事件总数将增加到现在用于跟踪活动日志的内存驻留数据结构不再可行的程度，尽管预期内存成本会持续下降。需要回答有关大量过去活动日志的查询意味着索引日志访问将变得越来越重要。
即使在当前的事务系统中，提供索引以支持对具有高插入量的历史表的查询也具有明显的价值。网络、电子邮件和其他几乎是事务性的系统会生成大量日志，这往往会损害其主机系统。从一个具体的众所周知的例子开始，我们在下面的例子1.1和1.2中探索了一种改进的TPC-a基准。注意，本文中的例子涉及特定的数值参数值，以便于表示；推广这些结果是一项简单的任务。还要注意的是，尽管历史表和日志都涉及时间序列数据，但不假设LSM树的索引项具有相同的时态键顺序。与检索率相比，提高效率的唯一假设是较高的更新率。
五分钟规则
以下两个例子都依赖于五分钟规则13。这一基本结果表明，当页面引用频率超过大约每60秒一次时，我们可以通过购买内存缓冲空间来保持页面在内存中，从而避免磁盘I/O，从而降低系统成本。60秒的时间段是近似值，即提供每秒一次I/O的磁盘臂的摊销成本与在1秒内摊销4KB的磁盘页的缓冲内存成本之间的比率。根据第3节的表示法，该比率是COSTP/COSTm除以以MB为单位的页面大小。在这里，我们只是在用磁盘访问换取内存缓冲，而这种权衡会带来经济收益。请注意，随着内存价格比磁盘价格下降得更快，60秒的时间段预计会逐年增长。1995年它比1987年定义的5分钟小，部分原因是技术原因（不同的缓冲假设），部分原因是中间引入了极其廉价的批量生产磁盘。
示例1.1.
考虑TPC-A基准26设想的多用户应用程序，该应用程序每秒运行1000个事务（该速率可以扩展，但我们将在下面的内容中只考虑1000个TPS）。每笔交易都会从三个表中的每一个表中更新一个列值，从余额列中随机选择一行（包含100个字节）提取金额增量：分支表（包含1000行）、柜员表（包含10000行）和账户表（包含100000000行）；然后，事务在提交之前将一个50字节的行写入历史记录表，其中包含以下列：帐户ID、分支ID、出纳员ID、增量和时间戳。
预测磁盘和内存成本的公认计算表明，账户表页面在未来几年内不会驻留内存（见参考文献6），而分行和出纳表现在应该完全驻留内存。在给定的假设下，重复引用Accounts表的同一磁盘页面将相隔约2500秒，远低于根据五分钟规则证明缓冲区驻留的频率。现在，每个事务需要大约两个磁盘I/O，一个用于读取所需的帐户记录（我们将访问的页面已在缓冲区中的罕见情况视为无关紧要），另一个用于写出之前的脏帐户页面，以便在缓冲区中为读取腾出空间（稳态行为所必需）。因此，1000个TPS将对应于大约每秒2000个I/O。这需要80个盘臂（执行器），标称速率为13中假设的每盘臂每秒25 I/O。在此后的8年（1987年至1995年）中，速率每年上升不到10%，因此标称速率现在约为每秒40 I/O，或每秒2000 I/O为50个磁盘臂。在6中，TPC应用程序的磁盘成本约为系统总成本的一半，尽管在IBM大型机系统上略低。然而，由于内存和CPU的成本下降速度都快于磁盘，因此支持I/O的成本显然是总系统成本中不断增长的一部分。
示例1.2.
现在，我们考虑高插入量历史记录表上的一个索引，并证明这样的索引本质上使TPC应用程序的磁盘成本增加了一倍。历史表的“账户ID与时间戳串联”（账户ID | |时间戳）索引对于支持对最近账户活动的有效查询至关重要，例如：
-- (1.1)
Select \* from History where History.Acct-ID =%custacctid and History.Timestamp > %custdatetime如果账户ID | |时间戳索引不存在，则此类查询需要直接搜索历史表的所有行，因此变得不切实际。仅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，其中检索的频率远低于插入（大多数人要求最近的帐户活动的频率几乎不如他们写支票或存款的频率）。在这种情况下，降低索引插入的成本至关重要；同时，查找访问足够频繁，因此必须维护某种索引，因为不可能对所有记录进行顺序搜索。
这是本文的计划。在第2节中，我们介绍了两分量LSM树算法。在第3节中，我们分析了LSM树的性能，并激励了多分量LSM树。在第4节中，我们概述了LSM树的并发和恢复概念。在第5节中，我们考虑了竞争访问方法及其在感兴趣的应用程序中的性能。第6节包含结论，其中我们评估了LSM树的一些含义，并提供了一些扩展建议。
2、两个组成部分 LSM-Tree Algorithm
LSM树由两个或多个树状组件数据结构组成。在本节中，我们将处理简单的两部分情况，并假设LSM树正在为历史表中的行建立索引，如示例1.2所示。请参见下面的图2.1。
双组件LSM树有一个完全驻留内存的较小组件，称为C0树（或C0组件），和一个驻留在磁盘上的较大组件，称为C1树（或C1组件）。尽管C1组件驻留在磁盘上，但C1中经常引用的页面节点将一如既往地保留在内存缓冲区中（缓冲区未显示），因此C1的常见高级目录节点可以被视为驻留在内存中。
在生成每个新的历史记录行时，首先以通常的方式将用于恢复此插入的日志记录写入顺序日志文件。然后，将历史记录行的索引项插入驻留在内存中的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，而单页节点用于匹配索引查找，以最小化缓冲需求。设想256 KB的多页块大小包含根下的节点；根据定义，根节点始终是单个页面。
滚动合并在一系列合并步骤中起作用。读取包含C1树叶节点的多页块会使一系列条目驻留在C1缓冲区中。然后，每个合并步骤读取缓冲在该块中的C1树的磁盘页面大小的叶节点，将来自叶节点的条目与取自C0树叶级的条目合并，从而减小C0的大小，并创建新合并的C1树叶节点。
在合并之前包含旧C1树节点的缓冲多页块称为清空块，新叶节点写入另一个缓冲多页块称为填充块。当该填充块已被C1的新合并叶节点填满时，该块将写入磁盘上的新空闲区域。包含合并结果的新多页块如图2.2所示，位于前一个节点的右侧。随后的合并步骤将C0和C1分量的索引值段增加到一起，直到达到最大值，滚动合并从最小值再次开始。
新合并的块被写入新的磁盘位置，因此旧块不会被覆盖，并且在崩溃时可以恢复。C1中的父目录节点（也缓冲在内存中）会更新以反映这种新的叶结构，但通常会在缓冲区中保留更长的时间，以最小化I/O；合并步骤完成后，C1组件中的旧叶节点无效，然后从C1目录中删除。通常，在每个合并步骤之后，合并的C1组件将有剩余的叶级条目，因为合并步骤不太可能产生新节点，就像旧叶节点清空一样。同样的考虑也适用于多页块，因为通常当填充块填充了新合并的节点时，会有许多节点包含仍在收缩块中的条目。这些剩余条目以及更新的目录节点信息会在块内存缓冲区中保留一段时间，而不会写入磁盘。第4节详细介绍了在合并步骤期间提供并发性和在崩溃期间从丢失内存中恢复的技术。为了减少恢复过程中的重建时间，定期采取合并过程的检查点，将所有缓冲信息强制存储到磁盘。
2.1LSM-tree两个组件如何生长
为了从LSM树的生长开始跟踪其变形，让我们首先插入内存中的C0树组件。与C1树不同，C0树不应具有类似B树的结构。首先，节点可以是任何大小：因为C0树从不位于磁盘上，所以不需要坚持使用磁盘页面大小的节点，因此我们不需要牺牲CPU效率来最小化深度。因此，a (2-3) 树或AVL树（如在1中解释的）是C0树的可能替代结构。当不断增长的C0树首次达到其阈值大小时，将从C0树中删除最左侧的条目序列（这应以有效的批处理方式完成，而不是一次只删除一个条目），并将其重新组织为完全填充的C1树叶节点。连续叶节点从左到右放置在驻留缓冲区的多页块的初始页中，直到块满为止；然后将该块写入磁盘，成为C1树磁盘驻留叶级别的第一部分。随着连续叶节点的添加，C1树的目录节点结构在内存缓冲区中创建，详细说明如下。
C1树叶子级别的连续多页块以不断增加的键序列顺序写入磁盘，以保持C0树阈值大小不超过其阈值。上层C1树目录节点维护在单独的多页块缓冲区中，或者维护在单页缓冲区中，从总内存和磁盘臂成本的角度来看，这两个缓冲区更有意义；这些目录节点中的条目包含分隔符，这些分隔符将访问传递到下面的单个单页节点，如在B树中。其目的是沿着单页索引节点的路径提供有效的精确匹配访问，直至叶级，避免在这种情况下进行多页块读取，以最小化内存缓冲区需求。因此，我们读取和写入用于滚动合并或远程检索的多页块，以及用于索引查找（精确匹配）访问的单页节点。21中介绍了一种支持这种二分法的稍有不同的架构。在写出一系列叶节点块时，通常允许C1目录节点的部分完整多页块保留在缓冲区中。在以下情况下，C1目录节点被强制到磁盘上的新位置：
o包含目录节点的多页块缓冲区变满o根节点拆分，增加C1树的深度（深度大于2）o执行检查点
在第一种情况下，已填充的单个多页块被写入磁盘。在后两种情况下，所有多页块缓冲区和目录节点缓冲区都刷新到磁盘。
在C0树最右边的叶子条目第一次写入C1树后，该过程从两棵树的左端开始，除了现在和连续的过程外，C1树的多页叶子级块必须读入缓冲区并与C0树中的条目合并，从而创建新的C1多页叶子块以写入磁盘。
一旦合并开始，情况就更加复杂。我们将两分量LSM树中的滚动合并过程描绘为具有概念光标，该光标以量化步骤缓慢循环通过C0树和C1树组件的相等键值，将索引数据从C0树绘制到磁盘上的C1树。滚动合并光标位于C1树的叶级，也位于每个更高的目录级内。在每个级别上，C1树的所有当前合并多页块通常将分为两个块：其条目已耗尽但保留合并光标尚未到达的信息的“清空”块，以及反映到目前为止合并结果的“填充”块。将有一个类似的“填充节点”和“清空节点”来定义光标，它肯定会驻留在缓冲区中。出于并发访问的目的，每个级别上的清空块和填充块都包含整数个C1树的页面大小的节点，这些节点恰好位于缓冲区中。（在重组单个节点的合并步骤中，阻止对这些节点上条目的其他类型的并发访问。）每当需要将所有缓冲节点完全刷新到磁盘时，各级的所有缓冲信息都必须写入磁盘上的新位置（位置反映在上级目录信息中，并有一个顺序日志条目用于恢复目的）。稍后，当C1树的某个级别上缓冲区中的填充块填充并且必须再次刷新时，它会转到一个新位置。在恢复过程中可能仍然需要的旧信息永远不会在磁盘上被覆盖，只有在新的写入成功并具有更多最新信息时才会失效。第4节对滚动合并过程进行了更详细的解释，其中考虑了并发和恢复设计。
LSM树的一个重要效率考虑因素是，当C1树的特定级别上的滚动合并过程以相对较高的速率通过节点时，所有读写都在多页块中。通过消除寻道时间和旋转延迟，我们有望获得比正常B树条目插入中涉及的随机页面I/O更大的优势。（下文第3.2节分析了这一优势。）始终将多页块写入新位置的想法受到Rosenblum和Ousterhout23设计的日志结构文件系统的启发，日志结构合并树就是从该系统中命名的。请注意，连续使用新磁盘空间进行新的多页块写入意味着正在写入的磁盘区域将被包裹，旧的丢弃块必须重新使用。这种簿记可以在内存表中完成；旧的多页块将失效并作为单个单元重用，并且通过检查点保证恢复。在日志结构文件系统中，旧块的重用涉及大量的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组件中找到所需值，则匹配索引查找完成。另一个例子是，当find标准使用最近的时间戳值时，我们可以限制搜索，以便所搜索的条目还不能迁移到最大的组件。当合并光标在（Ci，Ci+1）对中循环时，我们通常有理由保留最近（在最后τi秒内）插入的Ci中的条目，只允许较旧的条目进入Ci+1。在最频繁的查找引用是最近插入的值的情况下，许多查找可以在C0树中完成，因此，C0树实现了一个有价值的内存缓冲功能。23中也提到了这一点，这是一个重要的效率考虑因素。例如，在中断事件中访问的短期事务撤消日志的索引在创建后相对较短的时间内将有很大比例的访问，我们可以预计这些索引中的大多数将保持内存驻留状态。通过跟踪每个事务的开始时间，我们可以保证在最后τ0秒内开始的事务的所有日志将在组件C0中找到，而不依赖于磁盘组件。
2.3 LSM树中的删除、更新和长延迟查找
我们注意到，删除可以与插入共享延迟和批处理的宝贵属性。删除索引行时，如果在C0树中的适当位置未找到键值条目，则可以将删除节点条目放置在该位置，该位置也由键值索引，但注意要删除的条目行ID（RID）。实际删除可以在滚动合并过程中的稍后时间完成，即遇到实际索引项时：我们说删除节点项在合并过程中迁移到更大的组件，并在遇到关联项时消除它。同时，必须通过删除节点条目过滤查找请求，以避免返回对已删除记录的引用。由于删除节点条目将位于比条目本身更早的组件的适当键值位置，因此在搜索相关键值的过程中容易执行该过滤，并且在许多情况下，该过滤器将减少确定条目被删除的开销。导致索引值更改的记录更新在任何类型的应用程序中都是不常见的，但如果我们将更新视为先删除后插入，则LSM树可以延迟处理此类更新。
我们绘制了另一种类型的操作，用于有效修改索引。称为谓词删除的过程提供了一种通过简单断言谓词来执行批量删除的方法，例如，将删除所有时间戳超过20天的索引值的谓词。当最旧（最大）组件中受影响的条目在滚动合并的正常过程中驻留时，此断言会导致它们在合并过程中被删除。还有另一种类型的操作，长延迟查找，提供了一种有效的方法来响应查询，其中结果可以等待最慢游标的循环周期。在组件C0中插入一个查找注释条目，当它迁移到后面的组件时，查找实际上是在一段较长的时间内执行的。一旦find note条目分发到LSM树最大相关组件的适当区域，长延迟查找的RID累积列表就完成了。
3、性价比和多组件LSM树
在本节中，我们从两个组件的LSM树开始，分析LSM树的性价比。我们通过类比提供相同索引功能的B树来分析LSM树，比较用于大量新插入的I/O资源。正如我们将在第5节中讨论的那样，其他基于磁盘的访问方法在插入新索引项的I/O成本方面与B树相当。我们在这里对LSM树和B树进行比较的最重要原因是，这两种结构很容易进行比较，它们都包含在叶级按排序序列索引的每一行的条目，上层目录信息通过页面大小节点的路径进行访问。通过类比效率较低但易于理解的B-树行为，有效地说明了LSM树中新条目插入的I/O优势分析。
在接下来的第3.2节中，我们比较了输入/输出插入成本，并证明两个组件的LSM树与B树的小成本比是两个因素的乘积。第一个因素，COSTπ/COSTP，对应于通过执行所有操作在LSM树中获得的优势
多页块中的I/O，从而通过节省大量寻道和旋转延迟时间来更有效地利用磁盘臂。COSTπ项表示作为多页块的一部分在磁盘上读取或写入页面的磁盘开销，COSTP表示随机读取或写入页面的开销。确定LSMtree和B树之间I/O成本比的第二个因子为1/M，表示在合并步骤中获得的批处理效率。M是从C0合并到C1的页面大小的叶节点中的平均条目数。与（大型）B树相比，在每个叶中插入多个条目具有优势，在B树中，插入的每个条目通常需要两个I/O来读取和写入其所在的叶节点。由于五分钟规则，在示例1.2中，从B树读入的叶页不太可能在其保留在缓冲区中的短时间内再次被引用以进行第二次插入。因此，在B树索引中没有批处理效应：读入每个叶节点，插入新条目，然后再次写出。然而，在LSM树中，只要C0分量与C1分量相比足够大，就会存在重要的批处理效应。例如，对于16字节索引项，我们可以预期在一个完全压缩的4kbyte节点中有250个条目。如果C0分量的大小是C1分量的1/25，那么在节点I/O期间，我们将期望（大约）10个新条目进入每个新的C1节点（共250个条目）。很明显，由于这两个因素，LSM树比B树具有效率优势，而“滚动合并”过程是获得这一优势的基础。
与多页块的效率与单页I/O的效率之比相对应的因子COSTπ/COSTP是一个常数，我们不能用LSM树结构对其产生任何影响。然而，合并步长的1/M分批效率与C0和C1分量之间的大小比成正比；与C1分量相比，C0分量越大，合并效率越高；在某种程度上，这意味着我们可以通过使用更大的C0组件来节省额外的磁盘arm成本，但这需要更大的内存成本来包含C0组件。有一种优化的大小组合，以最小化磁盘臂和内存容量的总成本，但对于大型C0来说，该解决方案的内存成本可能相当高。正是这种考虑促使人们需要多组件LSM树，这在第3.3节中进行了研究。三组件LSM树具有内存驻留组件C0和磁盘驻留组件C1和C2，其中，组件的大小随下标的增加而增加。C0和C1之间有一个滚动合并过程，C1和C2之间有一个单独的滚动合并过程，每次较小的组件超过其阈值大小时，都会将条目从较小的组件移到较大的组件。三分量LSM树的优点是，通过选择C1来优化C0和C1之间以及C1和C2之间的大小组合比，可以从几何上提高批处理效率。因此，C0内存组件的大小与总索引的比例可以大大减小，成本显著提高。
第3.4节推导了一个数学程序，用于获得多组件LSM树不同组件的最佳相对大小，以最小化内存和磁盘的总成本。
3.1 磁盘模型
LSM树相对于B树的优势主要在于$\color{red}{降低了I/O成本}$（尽管与其他已知的软磁盘结构相比，100%满的磁盘组件也具有容量成本优势）。LSM树的这种I/O成本优势的一部分是，一个页面I/O可以与多页面块的许多其他页面一起摊销。
定义3.1.1输入/输出成本和数据温度。当我们在磁盘、表中的行或索引中的条目上存储特定类型的数据时，我们发现，随着存储的数据量的增加，在给定的应用程序环境中正常使用时，磁盘臂的利用率越来越高。当我们购买磁盘时，我们要为两件事付费：第一，磁盘容量，第二，磁盘I/O速率。通常，这两者中的一个将成为任何类型使用的限制因素。如果容量是限制因素，我们将填充磁盘，并发现提供I/O的磁盘臂仅被应用程序部分利用；另一方面，我们可能会发现，当我们添加数据时，磁盘臂达到其完全利用率，而磁盘仅部分充满，这意味着输入/输出速率是限制因素。
高峰使用期间的随机页面I/O有一个成本COSTP，它基于磁盘臂的公平租金，而作为大型多页面块I/O一部分的磁盘页面I/O的成本将表示为成本π，这个数量要小得多，因为它在多个页面上分摊寻道时间和旋转延迟。我们采用以下存储成本术语：
COSTd = cost of 1 MByte of disk storage
COSTm = cost of 1 MByte of memory storage
COSTP = disk arm cost to provide 1 page/second I/O rate, for random pages
COSTπ = disk arm cost to provide 1 page/second I/O rate, as part of multi-page block I/O
定一个应用程序引用的数据体具有S MB的存储空间和每秒H个随机页面的I/O传输（我们假设没有数据被缓冲），磁盘臂的租金由以下公式得出：
H-COSTP和磁盘介质的租金由S.COSTd给出。根据哪种成本是限制因素，另一种成本是免费的，因此访问此磁盘驻留数据的计算成本cost-D由以下公式得出：
COST-D = max(S.COSTd, H.COSTP)
COST-D还将是支持此应用程序的数据访问的总成本COST-TOT，假设没有任何磁盘页面缓冲在内存中。在这种情况下，即使总存储需求S保持不变，总成本也会随着随机输入/输出速率H线性增加。现在，内存缓冲的重点是在某个点用内存缓冲替换磁盘输入/输出，将输入/输出速率提高到相同的总存储量。如果我们假设在这些情况下，可以提前填充内存缓冲以支持随机输入/输出请求，则磁盘的成本下降到仅磁盘介质的成本，因此访问该缓冲区驻留数据的计算成本cost-B，就是内存成本加上磁盘介质成本：
COST-B = S.COSTm + S.COSTd
现在，该应用程序支持数据访问的总成本是这两个计算成本中的最小值：
COST-TOT = min(max(S.COSTd, H.COSTP), S.COSTm + S.COSTd)
当给定数据量S的页面访问速率H增加时，cost-TOT图中有三种成本状态。见图3.1，其中我们绘制了cost-TOT/MB与H/S的关系图，或每秒每兆字节的访问量。如果S较小，则COST-TOT受磁盘介质成本S.COSTd的限制，S.COSTd是固定S的常数。随着H/S的增加，成本由磁盘臂使用H.COSTP决定，并与固定S的H/S增加成正比。最后，在五分钟规则规定了记忆驻留，主导因素为S.COSTm+S.COSTd，由当前价格的记忆项COSTm>>COSTd决定。根据Copeland等人6，我们将数据体的温度定义为H/S，并将这三种成本状态命名为冷、热和热。热数据具有足够高的访问速率H，因此温度H/S，以证明内存缓冲区驻留的合理性（见6）。另一个极端是，冷数据的磁盘容量有限：它必须占用的磁盘卷具有足够的磁盘臂来满足I/O速率。中间是热数据，其访问要求必须通过限制每个磁盘臂下使用的数据容量来满足，因此磁盘臂是使用的限制。这些范围划分如下：
Tf = COSTd/COSTP = temperature division point between cold and warm data ("freezing")
Tb = COSTm/COSTP = temperature division point between warm and hot data ("boiling")
对于使用成本π的多页块访问情况，存在类似定义的范围。暖区和热区之间的划分是五分钟规则13的推广。
如6所强调的，当数据库表被统一访问时，计算其温度是很简单的。然而，该温度的相关性取决于访问方法：相关温度涉及实际磁盘访问速率，而不是逻辑插入速率（包括批量缓冲插入）。表示LSM树实现的功能的一种方法是，它减少了实际的磁盘访问，从而降低了索引数据的有效温度。第6节的结论再次讨论了这一观点。
多页块输入/输出优势
多页块输入/输出的优势是几种早期访问方法的核心，例如有界无序文件16、SB树21和日志结构文件23。1989年，一份分析IBM 3380磁盘上DB2实用程序性能的IBM出版物29给出了以下分析：“……完成单页读取的时间估计约为20毫秒（假设10ms寻道，8.3ms旋转延迟，1.7ms读取）……执行64个连续页的顺序预取读取的时间估计约为125ms（假设10ms寻道，8.3ms旋转延迟，106.9ms读取64条记录页面），或每页约2ms。“因此，多页块I/O的每页2毫秒与随机I/O的20毫秒之比意味着磁盘臂的租用成本之比，COSTπ/COSTP，约等于1/10。对最近SCSI-2磁盘读取4kbyte页面的分析给出了9毫秒寻道、5.5毫秒旋转延迟和1.2毫秒读取，总计16毫秒。读取64个连续4kbyte页面需要9毫秒寻道、5.5毫秒旋转延迟，读64页80毫秒，或总共95毫秒，约1.5毫秒/页。
成本π/COSTP再次等于约1/10。
我们分析了一个工作站服务器系统，其中SCSI-2磁盘容量为1 GB，成本约为1000美元，峰值速率约为每秒60-70 I/O。避免长I/O队列的标称可用I/O速率较低，约为每秒40 I/O。多块输入/输出优势显著。
1995年典型工作站成本：
COSTm = $100/MByte
COSTd = $1/MByte
COSTP = $25/(IOs/sec)
COSTπ = $2.5/(IOs/sec)
Tf = COSTd/COSTP = .04 IOs/(sec.MByte) ("freezing point")
Tb = COSTm/COSTP = 4 IOs/(sec.MByte) ("boiling point")
我们使用Tb值来推导五分钟规则的参考间隔τ，该规则断言，维持每秒一页的输入/输出速率的数据所产生的成本与保存它所需的内存相同。共同成本是：
(1/τ).COSTP = pagesize.COSTm
求解τ，我们看到τ=（1/pagesize）。（COSTP/COSTm）=1/（pagesize.Tb），对于上面给出的值，对于0.004 MB的页面，我们得到τ=1/（.004.4）62.5秒/IO。
示例3.1。为了在示例1.1的TPC-a应用程序中实现1000个TPS的速率，Account表每秒将有H=2000个I/O，其本身由100字节的100000000行组成，总计S=10GB。这里的磁盘存储成本是S.COSTd=10000美元，而磁盘I/O成本是H.COSTP=50000美元。温度T=H/S=2000/10000=0.2，远高于冰点（系数5），但也远低于沸点。这些热数据仅使用其磁盘容量的1/5来存储数据。我们为磁盘臂而不是容量付费。当我们考虑示例1.2的历史表的20天帐户ID | |时间戳索引时，情况类似。正如我们在示例1.2中计算的那样，这样的B树索引需要大约9.2 GB的叶级条目。假设一棵正在生长的树只有大约70%的容量，那么整个树将需要13.8GB，但它的输入/输出速率（仅针对插入）与Account表相同，这意味着具有可比的温度。
3.2 LSM树和B树输入/输出成本的比较
我们将考虑索引操作的输入/输出成本，我们称之为可合并：插入、删除、更新和长延迟查找。下面的讨论提供了一种分析，将LSM树与B树进行比较。
B-树插入成本公式。
考虑执行B树插入的磁盘臂租用成本。我们必须首先访问树中条目应该放置的位置，这需要搜索树的节点。我们假设对树的连续插入是在叶子级别的随机位置，因此由于过去的插入，访问路径中的节点页不会始终驻留在缓冲区中。一系列不断增加的键值插入，在正确的情况下插入，是不符合此假设的一种相对常见的情况。我们注意到，这种正确的插入情况已经可以通过B-树数据结构非常有效地处理，因为随着B-树不断向右增长，几乎没有I/O；实际上，这是发生B树负载的基本情况。还有许多其他建议的结构可以通过不断增加的值来处理索引日志记录8。
在21中，用De表示的B树的有效深度被定义为在沿B树的目录级别进行随机键值搜索期间未在缓冲区中找到的平均页数。对于示例1.2中用于索引帐户ID | |时间戳的大小的B树，De的值通常约为2。
为了执行B树的插入，我们对叶级页面（De I/O）执行键值搜索，更新它，并（在稳定状态下）写出相应的脏叶页面（1 I/O）。我们可以证明，相对不频繁的节点分裂对我们的分析影响不大，因此忽略它们。在此过程中读取和写入的页面均为随机访问，具有成本成本，因此B-树插入的总I/O成本COSTB-ins由以下公式得出：
（3.1）COSTB ins=COSTP。（De+1）
LSM树插入成本公式。
为了评估LSM树中插入的成本，我们需要考虑多个插入的摊销，因为对内存组件C0的单个插入偶尔会产生任何I/O影响。正如我们在本节开头所解释的那样，LSMtree相对于B树的性能优势基于两种不同的批处理效果。第一个是已经提到的页面I/O成本降低，即成本π。第二种是基于这样的想法，即将新插入的条目合并到C1树中的延迟通常允许大量条目在C0中积累时间；因此，在从磁盘到内存和从内存返回的过程中，几个条目将合并到每个C1树叶页中。相比之下，我们一直假设B树叶页在内存中引用太少，无法进行多个条目插入。
定义3.2.1.批合并参数M。为了量化这种多个entriesper-leaf批处理效果，将给定LSM树的参数M定义为滚动合并期间插入C1树每个单页叶节点的C0树中的平均条目数。我们断言参数M是表征LSM树的相对稳定值。事实上，M的值由索引项大小和C1树和C0树的叶级之间的大小比率决定。我们定义了以下新的尺寸参数：
Se = entry (index entry) size in bytes
Sp = page size in bytes
S0 = size in MBytes of C0 component leaf level S1 = size in MBytes of C1 component leaf level.
然后，页面的条目数约为Sp/Se，位于组件C0中的LSM树的条目分数为S0/（S0+S1），因此参数M由以下公式得出：
(3.2) M = (Sp/Se). (S0/(S0 + S1))
注意，与C1相比，分量C0越大，参数M越大。
典型的实现可能有S1=40.S0，每个磁盘页的条目数Sp/Se为200，因此M=5。给定参数M，我们现在可以给出插入LSM树的条目的成本LSM ins的粗略公式。我们只需将C1树叶节点放入内存并再次写入的每页成本2。成本π在这段时间内合并到C1树叶节点的M个插入上进行摊销。
(3.3) COSTLSM-ins = 2.COSTπ/M
注意，在LSM树和B树的情况下，我们忽略了与索引更新的I/O相关的相对较小的成本。
LSM树和B树插入成本的比较
如果我们将插入的成本公式（3.1）和（3.3）与两种数据结构进行比较，我们会看到比率：
(3.4) COSTLSM-ins/COSTB-ins = K1.(COSTπ/COSTP).(1/M)
其中K1是一个（近似）常数，2/（De+1），对于我们一直在考虑的指数大小，其值约为0.67。该公式表明，LSM树中插入的成本比与B树中插入的成本比与我们讨论的两个批处理效果中的每一个成正比：成本π/COSTP，一个小分数，对应于多页块中页面I/O的成本与随机页面I/O的比，以及1/M，其中M是滚动合并期间每页批处理的条目数。通常，这两个比率的乘积将使成本比率提高近两个数量级。当然，只有在索引具有相对较高的温度（如B树）的情况下，这种改进才可能实现，因此在移动到LSM树索引时，可以大大减少磁盘数量。
示例3.2。如果我们假设示例1.2中的索引占用1 GB的磁盘空间，但需要占用10 GB才能实现必要的磁盘arm访问速率，那么在节省磁盘arm成本方面肯定还有改进的空间。如果等式（3.4）中给出的插入成本之比为0.02=1/50，那么我们可以缩减索引和磁盘成本：由于条目密集，磁盘臂利用率降低，LSM树只需要占用0.7GB的磁盘空间。然而，我们看到，更高效的LSM树只能将成本降低到磁盘容量所需的水平。如果我们从一个1Gbyte的B树开始，该树被限制在35Gbyte上以接收所需的磁盘arm服务，那么成本提高的比例就可以完全实现。
3.3多分量LSM树
给定LSM树的参数M定义为滚动合并期间插入C1树的每个单页叶节点的C0树中的平均条目数。我们一直认为数量M大于1，因为新条目在合并到C1树的节点之前可以在C0树中累积的延迟期。然而，从等式（3.2）中可以清楚地看出，如果C1树与C0树相比非常大，或者条目非常大并且只适合一个小数字到一个页面，则数量M可能小于1。M的这样一个值意味着，对于从C0树合并的每个条目，平均必须将多个C1树页面带入和移出内存。在公式（3.4）中M非常小的情况下，特别是当M<K1.COSTπ/COSTP时，这甚至可以取消多页磁盘读取的批处理效果，因此我们最好使用普通B树代替LSM树进行插入。
为了避免M的小值，具有双分量LSM树的唯一过程是相对于C1增加C0分量的大小。考虑给定总叶条目大小S（S=S0+S1，一个近似稳定的值）的双分量LSM树，并假设在C0中插入新条目的速率R恒定（以字节/秒为单位）。为简单起见，我们假设插入C0的条目在退出到组件C1之前不会被删除，因此条目必须通过滚动合并以与插入C0相同的速率迁移到组件C1，以使C0的大小接近其阈值大小。（假设总大小S近似稳定，这也意味着插入C0的速率必须通过C1的恒定删除速率来平衡，可能使用一系列谓词删除。）随着C0大小的变化，我们会影响合并光标的循环速度。以字节/秒为单位向C1的恒定迁移速率要求滚动合并光标以恒定速率（以字节/秒为单位）在C0的条目中移动，因此，随着C0的大小减小，C0中索引值从最小到最大的循环速率将增加；因此，C1中执行滚动合并的多页块的输入/输出速率也必须增加。如果一个条目的C0大小是可能的，那么在这个概念上的极端点上，我们需要在每个新插入的条目的C1的所有多页块中循环，这对I/O有巨大的需求。合并C0和C1的方法，而不是像B-树那样为每个新插入的条目访问C1的相关节点，将成为我们的瓶颈。相比之下，较大尺寸的C0组件将减缓合并光标的循环，并降低插入的I/O成本。然而，这将增加内存驻留组件C0的成本。
现在，C0有一个标准大小，由LSMtree的总成本（C0的内存成本加上C1组件的媒体/磁盘臂成本）最小化的点确定。为了达到这种平衡，我们从一个大的C0组件开始，将C1组件紧密地封装在磁盘介质上。如果C0组件足够大，我们将有一个非常小的C1输入/输出速率。我们现在可以减小C0的大小，用昂贵的内存换取廉价的磁盘空间，直到服务C1的输入/输出速率增加到C1组件介质上的磁盘臂以全速运行为止。在这一点上，进一步节省C0的内存成本将导致介质成本增加，因为我们需要将C1组件分布在部分满的磁盘上，以减少磁盘臂负载，并且在某些时候，随着我们继续收缩C0，我们将达到最低成本点。现在，在双分量LSM树中，我们为C0确定的规范大小在内存使用方面仍然非常昂贵。另一种选择是考虑采用由三个或更多组件组成的LSM树。从概念上讲，如果C0组件的大小太大，以至于内存成本是一个重要因素，那么我们考虑在这两个极端之间创建另一个中等大小的基于磁盘的组件。这将允许我们限制磁盘臂的成本，同时减少C0组件的尺寸。
通常，K+1分量的LSM树具有分量C0、C1、C2、…、CK-1和CK，它们是大小递增的索引树结构；C0组件树是内存驻留的，所有其他组件都是磁盘驻留的（但与任何磁盘驻留访问树一样，常用页面缓冲在内存中）。在插入的压力下，所有组件对（Ci-1，Ci）之间都有异步滚动合并过程，每次较小的组件Ci-1超过其阈值大小时，都会将条目从较小的组件移到较大的组件。在LSM树中插入的长寿命条目的生命周期内，它从C0树开始，最终通过一系列K异步滚动合并步骤迁移到CK。
这里的重点是在插入流量下的性能，因为我们假设LSM树存在于以插入为主的环境中。三个或三个以上组件的LSM树发现在性能上有所下降，通常是每个磁盘组件多出一个页面I/O。
3.4 LSM树：组件尺寸
在本节中，我们推导了插入到多个组件的LSM树中的I/O成本公式，并从数学上演示了如何为各种组件选择最佳阈值大小。扩展示例3.3说明了B树的系统成本，两个组件的LSM树的改进系统成本，以及三个组件的LSM树的更大节约。
我们将LSM树组件S（Ci）的大小定义为它在叶级包含的条目的字节数；分量Ci的大小由Si表示，S（Ci）=Si，S是所有分量中所有叶级条目的总大小，S=∑i Si。我们假设LSM树的组件C0有一个相对稳定的插入速率R，以字节/秒为单位，为简单起见，所有新插入的条目通过一系列滚动合并步骤循环到组件CK。我们还假设每个分量C0、C1、…、CK-1的大小接近于最大阈值大小，由当前分析确定。由于在一些标准时间段内删除平衡插入，因此假设组件CK具有相对稳定的大小。从组件CK的删除可以被认为是在不增加向组件C0插入R的速率的情况下发生的。
给定具有固定总大小S和内存组件大小S0的K个组件的LSM树，该树完全由变量ri，i=1，…，K描述，表示相邻组件对之间的大小比，ri=Si/Si-1，如下所述，执行组件对（Ci-1，Ci）之间所有正在进行的合并操作的总页面i/O速率可以表示为R的函数，插入C0的速率和比率ri。我们假设不同组件的块以混合方式在不同的磁盘臂上分条，以实现利用率的平衡，因此最小化H与最小化总磁盘臂成本相同（至少在磁盘臂而不是介质容量构成选通成本的任何范围内）。寻找使给定R的总输入/输出速率H最小化的ri值是一个标准的微积分最小化问题。结果表明，总大小S固定的假设导致了一个相当困难的问题，ri值之间存在某种复杂的递归关系。然而，如果我们做出最大组件大小SK是固定的（以及内存大小S0）的类似假设，如我们将在定理3.1中所示，当所有值ri等于单个常数值r时，这个最小化问题就解决了。我们在定理3.2中给出了与ri值相关的更精确的解，其中总大小S保持不变，并认为ri的常数值r在所有实际感兴趣的领域中给出了类似的结果。假设所有ri因子的常数r为Si=ri.S0。因此，总尺寸S由单个组件尺寸的总和得出，S=S0+r.S0+r2.S0+…+rK.S0，我们可以根据S和S0求解r。
因此，在定理3.1中，我们证明了为了最小化多分量LSMtree的总I/O速率H，在固定SK、S0和插入速率R的情况下，我们在最小和最大之间的几何级数中确定中间分量的大小。我们将看到，与双分量LSM树的情况一样，如果我们允许S0变化，而R和SK保持不变，并将H表示为S0的函数，则H随S0的减小而增加。我们现在可以最小化LSM树的总成本，内存加磁盘臂成本，通过改变S0的大小。对于给定数量的组件，实现最优总成本的适当过程如下例3.3所示。总成本中唯一剩余的自由变量是组件数量K+1。我们在本节末尾讨论了该值的权衡。
定理3.1.给定K+1个组件的LSM树，具有固定的最大组件大小SK、插入速率R和内存组件大小S0，当比率ri=Si/Si-1都等于公共值R时，执行所有合并的总页面输入/输出速率H最小化。因此，总大小S由单个组件大小的总和给出，（3.5）S=S0+R.S0+r2.S0+…+rK.S0，我们可以用S和S0求解r。类似地，总页面输入/输出速率H由下式得出：
（3.6）H=（2R/Sp）。（K。（1+r）-1/2），其中Sp是每页的字节数。
证据由于我们假设条目在到达组件CK之前不会被删除，因此在稳定状态下，很明显，插入到C0的速率R（以字节/秒为单位）与通过将合并从组件Ci-1滚出到组件Ci来迁移条目的速率相同，对于所有i，0<i≤ K、 考虑组件Ci-1驻留在磁盘上的情况。然后，从Ci-1到Ci的合并需要以每秒R/Sp页的速率从组件Ci-1进行多页块读取，其中Sp是每页的字节数（我们从条目从Ci-1迁移出的速率R（以每秒字节为单位）得出，假设所有遇到的条目都从Ci-1中删除；在一般情况下，其他假设是可能的）。合并还需要以ri的速率从Ci进行多页读取。每秒R/Sp页面数（这是因为滚动合并光标在ri=Si/Si-1上经过的页面数是Ci-1页面数的两倍）。最后，合并需要以每秒（ri+1）R/Sp页的速率进行多页磁盘写入，以写出属于Ci的新合并数据。注意，这里我们考虑的是合并导致的Ci组件的放大尺寸。将所有驻留在磁盘上的组件Ci相加，我们得到了多页I/O的总速率H，单位为每秒页数，由下式得出：
（3.7）H=（R/Sp）（（2.r1+2）+（2.r2+2）+…+（2.rK-1+2）+（2.rK+1）），
其中（2.ri+k）形式的每个项表示组件Ci:ri上的所有输入/输出。R/Sp读入Ci中的页面，用于从Ci-1合并到Ci，（ri+1）R/Sp写出Ci中的页面，用于同一个合并，R/Sp读入Ci中的页面，用于从Ci合并到Ci+1。显然，C0没有术语，组件CK的术语没有这一最终添加。等式（3.7）可以改写为：
K
（3.8）H=（2R/Sp）(∑ ri+K-）
1.
K
我们希望在以下条件下最小化该函数的值：∏ri=（SK/S0）=C，a
1.
K K-1
常数为了解决这个问题，我们最小化∑ri，用C替换术语rK。∏ri-1。
1 1
取每个自由变量rj，j=1，…，K-1的偏导数，并将其等于
K-1
零，我们得到一组形式相同的方程：0=1-r1j C。∏ri-1，即
1.
K-1
当所有rj（包括rK）等于C时，明确求解。∏ri-1，o
最小化总成本
从定理3.1可以看出，如果我们允许S0变化，而R和SK保持不变，并将总输入/输出速率H表示为S0的函数，那么由于R通过等式（3.5）随S0的减少而增加，而H通过等式（3.6）与R成正比，显然，H随着S0的减少而增加。我们现在可以通过用昂贵的内存换取廉价的磁盘来最小化LSM树的总成本，就像在双组件情况下一样。如果我们计算存储LSM树所需的磁盘介质以及保持这些磁盘臂充分利用的总I/O速率H，这将成为我们计算的起点，以确定成本最小化的S0的大小。从这一点来看，随着我们进一步减小C0的大小，磁盘介质的成本成反比增加，因为我们已经进入了磁盘臂成本是限制因素的区域。下面的示例3.3是二分量和三分量LSM树的该过程的基于数值的说明。在本例之前，我们提供了两部分情况的分析推导。
总成本是内存成本COSTm的总和。S0和磁盘成本，其本身是磁盘存储和I/O成本的最大值，这里基于多页块访问速率H（以每秒页数为单位）：
COSTtot=COSTm。S0+最大值COSTd.S1，COSTπ.H
考虑两个分量的情况，因此在等式（3.6）中，K=1，r=S1/S0
s=（COSTm.S0）/（COSTd.S1）=相对于S1数据的存储成本的内存成本。
t=2（（R/Sp）/S1）。（COSTπ/COSTd）（COSTm/COSTd）
C=成本Tot/（成本D.S1）=相对于S1数据存储成本的总成本
然后，代入方程（3.6）并简化，假设S0/S1较小，我们得到一个近似值：
C≈ s+最大值（1，t/s）
相对成本C是两个变量t和s的函数；变量t是一种归一化温度，用于测量应用程序所需的基本多页块输入/输出速率。变量s表示我们决定使用多少内存来实现LSM树。为了确定S0的大小，最简单的规则是遵循s=t行，其中C=s+1，磁盘存储和I/O容量得到充分利用。对于t<=1，该规则是最小成本的，但对于t>1，最小-C的轨迹遵循曲线s=t1/2，其中C=2.t1/2。将结果返回到维数形式，对于t>=1：
（3.8）COSTmin=2（COSTm.S1）（2.COSTπR/Sp）1/2
因此，LSM树的总成本（对于t≥ 1） 被视为几何平均数的两倍，即足够存储LSM树中所有数据的内存成本（非常高）和支持以最便宜的方式将其插入写入磁盘所需的多页块I/O所需的磁盘成本（极低）。总成本的一半用于S0的内存，另一半用于S1的I/O访问磁盘。磁盘存储成本没有显示出来，因为t>=1确保数据足够热，使磁盘I/O在最小点上优于磁盘存储。注意，与B-树的R相比，渐近地，成本为R1/2，为R->∞.
在t<=1的情况下，冷却器的情况下，最小成本出现在s=t，其中C=t+1<2。这意味着在这种情况下，总成本始终小于将S1存储在磁盘上的基本成本的两倍。在这种情况下，我们根据存储需求调整磁盘大小，然后使用其所有I/O容量来最小化内存使用。
示例3.3.我们考虑示例3.1中详述的帐户ID |时间戳索引。以下分析仅计算插入的成本，索引的插入速率R为每秒16000字节（1000个16字节索引项，不计算开销），导致20天数据或9.2 GB数据的索引为5.76亿个项。
使用B-树来支持索引，磁盘I/O将成为限制因素，如我们在示例3.1中所看到的-叶级数据是热的。我们需要使用足够的磁盘空间来提供每秒H=2000的随机I/O，以在叶级更新随机页面（这假设所有目录节点都驻留在内存中）。使用第3.1节表格中的典型值COSTP=$25，我们发现输入/输出的成本为H.COSTP=$50000。我们计算了在内存中缓冲上层节点的成本，如下所示。假设叶节点已满70%，0.7。（4K/16）=每个叶节点180个条目，因此叶上方的级别包含约5.76亿/180=320万个指向从属叶的条目。如果我们允许一些前缀压缩，这样我们可以在这个级别上为一个节点容纳200个条目，这意味着大约16000页，每个页4 KB，或64 MB，内存成本为每MB 100美元，或6400美元。我们忽略了在这个级别上节点缓冲的相对较小的成本，并说B树的总成本是磁盘50000美元加内存6400美元，或总成本为56400美元。
对于包含两个组件（C0和C1）的LSM树，我们需要一个9.2 GB的S1磁盘来存储条目，代价是开销D。S1=9200美元。我们将这些数据紧密地打包在磁盘上，并使用多页块I/O计算磁盘臂中同等成本支持的总I/O速率H，因为H=9200/成本π=3700页/秒。现在在等式（3.6）中，我们在如上所述设置总输入/输出速率H、速率r为16000字节/秒、Sp为4K后求解r。根据得到的r=S1/S0=460和S1=9.2 GB的事实，我们计算出C0的内存为20MB，成本为2000美元。这是简单的s=t解决方案，总成本为11200美元，充分利用了磁盘容量和I/O能力。由于t=.22小于1，因此这是最优解。我们为包含合并块的2MB内存增加了200美元，总成本达到11400美元。这是对B树成本的重大改进。
下面是对解决方案的完整解释。R=16000字节/秒的插入速率转换为4页/秒，需要从C0合并到C1。由于C1比C0大460倍，来自C0的新条目平均合并到C1中除460个条目之外的位置。因此，从C0合并一个页面需要读取和写入460页C1，总计3680页/秒。但这正是9.2磁盘在多块I/O容量中所提供的，每个磁盘提供400页/秒，是40页/秒标称随机I/O速率的10倍。
由于本例显示了通过两个组件充分利用磁盘资源，因此我们没有理由在这里探索三组件LSM树。更完整的分析将考虑如何在索引中执行偶然发现，并考虑利用更多的磁盘臂。下面的示例显示了一种情况，其中三个组件为纯插入工作负载提供了改进的成本。
示例3.4.考虑示例3.3，R增加了10倍。请注意，对于500GB的磁盘，B树解决方案现在的成本为500000美元，以支持每秒20000次I/O的I/O速率；其中491 GB将无法使用。但B-树的大小相同，我们仍然需要支付6400美元来缓冲内存中的目录，总成本为506400美元。在LSM树分析中，R增加10倍意味着t增加相同的系数，达到2.2。由于t大于1，最好的2组件解决方案不会利用所有磁盘容量。我们使用等式（3.8）计算了两组件LSM树的最低成本27000美元，其中一半用于支付13.5GB的磁盘，另一半用于支付135MB的内存。这里有4.3 GB的磁盘未使用。缓冲区内存为2M字节，总成本为27200美元。
下面是对双分量解的完整解释。插入速率R=160000字节/秒转换为40页/秒，需要从C0合并到C1。由于C1比C0大68倍，因此从C0合并一个页面需要68页读取和68页写入C1，总计每秒5450页。但这正是13.5磁盘在多块I/O容量中提供的功能。
对于R=160000字节/秒的情况，使用三个组件的LSM树，计算两个组件的最大磁盘组件的成本和成本平衡的I/O速率。对于i=1，2，当Si/Si-1=r时，根据定理3.1，我们计算完全占用的磁盘臂的r=23和S0=17mbytes（内存成本为1700美元）。较小的磁盘组件仅为较大磁盘组件的1/23。现在，从这一点开始增加内存大小没有良好的成本效果，而减小内存大小将导致磁盘成本的相应因子平方增加。由于磁盘的成本目前远高于内存成本，因此我们无法通过减少内存大小来获得成本效益。因此，在三分量情况下，我们有一个类似的s=t解。允许额外的4MB内存用于缓冲，对于两个滚动合并操作，成本为400美元，因此，3组件LSM树的总成本为9200美元（磁盘）加上2100美元（内存），或11300美元的总成本，这是对2组件LSM树成本的进一步重大改进。
以下是对三分量解决方案的完整解释。内存组件C0有17 MB，较小的磁盘组件C1比C1大23倍（400 MB），C2比C1大23倍（9.2 GB）。必须从C0合并到C1的40页/秒数据中的每一页需要23页的读取和23页的写入，即每秒1840页。类似地，每秒40页从C1合并到C2，每一页都需要23页的C2读写。两个输入/输出速率之和为3680，正好是9.2 G磁盘的多块输入/输出容量。
与简单的B树相比，由两个或三个组件组成的LSM树需要更多的I/O来进行查找操作。在任何一种情况下，最大的组件看起来都非常类似于相应的简单B树，但在LSM树的情况下，我们没有支付6400美元的内存来缓冲索引中叶子级别上的节点。树中更高的节点相对较少，因此是可忽略的，我们可以假设它们是缓冲的。显然，如果查找条目的查询足够频繁，我们愿意支付缓冲所有目录节点的费用。在三分量情况下，我们还需要考虑C1分量。由于它比最大的组件小23倍，我们可以很容易地缓冲其所有非叶节点，因此应在分析中增加此成本。C1中的无缓冲叶访问需要在寻找C2中的条目的情况下进行另一次额外的查找读取，并且需要决定是否缓冲C2的目录。因此，对于三个组件的情况，在简单B树中查找所需的两个I/O上可能会有一些额外的页面读取（计算叶节点页面写入的一个I/O）。对于双组分情况，可能会有一个额外的读取。如果我们购买内存来缓冲LSM树组件叶级以上的节点，我们可以在两个组件的情况下满足B树的速度，并在某些情况下在三个组件的情况下支付一个额外的只读。在三组件情况下添加缓冲的总成本将为17700美元，仍然远低于B树。但最好将这笔钱用在其他方面：全面分析应该将整个工作量的总成本降到最低，包括更新和检索。
根据定理3.1的结果，我们通过改变大小比ri来最小化给定S0的合并操作所需的总I/O，然后通过选择S0来实现最佳磁盘臂和介质成本来最小化总成本。LSM树中唯一可能剩下的变化是提供的组件总数K+1。结果表明，随着组件数量的增加，S0的大小继续减小，直到达到组件大小之间的比值r达到值e=2.71…，或者直到我们达到冷数据状态。然而，我们可以从示例3.4中看出，随着部件数量的增加，连续较小的S0部件对总成本的影响越来越小；在由三个组件组成的LSM树中，内存大小S0已减少到17MB。此外，增加组件数量会带来成本：执行额外滚动合并的CPU成本和缓冲这些合并节点的内存成本（这实际上会淹没常见成本模式下C0的内存成本）。此外，需要立即响应的索引查找有时必须从所有组件树中执行检索。这些考虑对适当数量的组件提出了强烈的限制，三个组件可能是实践中看到的最多的组件。
4.LSM树中的并发和恢复
在本节中，我们研究了用于为LSM树提供并发性和恢复的方法。为了实现这一点，我们需要为滚动合并过程绘制更详细的设计级别。我们将为以后的工作留下并发和恢复算法正确性的正式演示，并尝试在这里简单地激发所提出的设计。
4.1 LSM树中的并发性
一般来说，我们给出了一个K+1组件的LSM树，C0，C1，C2，…，CK-1和CK，其大小不断增加，其中C0组件树是内存驻留的，所有其他组件是磁盘驻留的。所有组件对（Ci-1，Ci）之间都有异步滚动合并过程，每次较小的组件Ci-1超过其阈值大小时，都会将条目从较小的组件移到较大的组件。每个驻留在磁盘上的组件都是由B树结构中的页面大小的节点构成的，除了根下所有级别的键序列顺序的多个节点位于多页面块上。上层目录信息
树通道中的一个通道通过单页节点向下访问，并指示多页块上的节点序列，以便可以一次执行对此类块的读取或写入。在大多数情况下，每个多页块都挤满了单页节点，但正如我们将看到的那样，在一些情况下，这样的块中存在数量较少的节点。在这种情况下，LSM树的活动节点将落在多页块的连续页面集上，尽管不一定是块的初始页面。除了这些连续页面不一定是多页面块上的初始页面这一事实外，LSM树组件的结构与21中提出的SB树的结构相同，读者可参考该结构以获取支持细节。
基于磁盘的组件Ci的节点可以单独驻留在单页内存缓冲区中，就像执行相等匹配查找时一样，也可以驻留在其包含的多页块中。由于长距离查找或滚动合并光标高速通过所述块，多页块将在内存中缓冲。在任何情况下，Ci组件的所有未锁定节点都可以随时进行目录查找，磁盘访问将执行查找以定位内存中的任何节点，即使它作为参与滚动合并的多页块的一部分驻留。考虑到这些因素，LSM树的并发方法必须调解三种不同类型的物理冲突。
（i） 查找操作不应在执行滚动合并的不同进程修改节点内容的同时访问基于磁盘的组件的节点。
（ii）在C0组件中的查找或插入不应访问树的同一部分，不同进程正在同时更改该部分以执行到C1的滚动合并。
（i）从Ci-1向外滚动合并到Ci的光标有时需要移过从Ci向外滚动合并到Ci+1的光标，因为从组件Ci-1向外迁移的速率始终至少与从Ci向外迁移的速率相同，这意味着连接到较小组件Ci-1的光标的循环速率更快。
无论采用何种并发方法，都必须允许在交叉点（从Ci迁移出）一个进程落后于另一个进程的情况下进行此通道。
节点是LSM树中使用的锁定单元，以避免在并发访问基于磁盘的组件期间发生物理冲突。由于滚动合并而更新的节点锁定在写模式，而在查找期间读取的节点锁定在读模式；人们很好地理解了避免死锁的目录锁定方法（例如，请参见3）。C0中采用的锁定方法取决于所使用的数据结构。例如，在（2-3）树的情况下，我们可以写锁位于单个（2-3）目录节点下的子树，该目录节点包含合并到C1节点期间受影响范围内的所有条目；同时，查找操作将在读取模式下锁定其访问路径上的所有（2-3）节点，以便一种类型的访问将排除另一种类型的访问。注意，我们只考虑在28意义上的多级锁定的最低物理级别上的并发性。我们将更多抽象锁的问题留给了其他人，例如用于保持事务隔离的密钥范围锁定，并暂时避免了幻影更新的问题；有关讨论，请参见4、14。因此，一旦扫描了叶级正在查找的条目，就会释放读取锁。光标下（所有）节点的写锁在每个节点从较大组件合并后释放。这为远程查找或更快的光标通过相对较慢的光标位置提供了机会，从而解决了上述（iii）点。
现在假设我们正在两个基于磁盘的组件之间执行滚动合并，将条目从Ci-1迁移到Ci，我们称之为滚动合并的内部组件，再迁移到Ci，我们称之为外部组件。光标在Ci-1的叶级节点内始终有一个定义良好的内部组件位置，指向它将要迁移到Ci的下一个条目，同时沿着访问叶级节点位置的路径在Ci-1的每个更高目录级别中有一个位置。光标在Ci中也有一个外部组件位置，位于叶级和访问路径沿线的上层，对应于它将在合并过程中考虑的条目。当合并光标通过内部和外部组件的连续条目时，通过合并创建的Ci的新叶节点立即按从左到右的顺序放置在新的缓冲区驻留多页块中。因此，围绕当前光标位置的Ci组件节点通常会在内存中分为两个部分完整的多页块缓冲区：“清空”块，其条目已耗尽，但保留合并光标尚未到达的信息，和“填充”块，它反映了到目前为止的合并结果，但还不够满，无法在磁盘上写入。出于并发访问目的，清空块和填充块都包含整数个C1树的页面大小的节点，这些节点恰好位于缓冲区中。在重组单个节点的合并步骤操作期间，所涉及的节点被锁定在写入模式，从而阻止对条目的其他类型的并发访问。
在滚动合并的最常用方法中，我们可能希望在组件Ci-1中保留某些条目，而不是在光标经过时将所有条目迁移到Ci。在这种情况下，围绕合并光标的Ci-1组件中的节点也将分为两个缓冲区驻留多页块，一个是包含合并光标尚未到达的Ci-1节点的“清空”块，另一个是由左向右放置的节点“填充”块，包含合并游标最近传递并保留在组件Ci-1中的条目。在这种最常见的情况下，合并光标的位置在任何时候都会影响四个不同的节点：即将发生合并的清空块中的内部和外部组件节点，以及随着光标移动正在写入新信息的填充块中的内部和外部组件节点。显然，这四个节点在任何时候都可能不完全满，包含块也是如此。在合并实际修改节点结构期间，我们在所有四个节点上设置写锁，并在量化瞬间释放这些锁，以允许更快的光标通过；每当外部组件中清空块中的节点完全耗尽时，我们选择释放锁，但此时其他三个节点通常会不足满。这没问题，因为我们可以对一棵树执行所有访问操作，该树中的节点不完全满，而块中的节点也不完全满。一个光标经过另一个光标的情况需要特别仔细考虑，因为通常被绕过的滚动合并的光标位置将在其内部组件上无效，并且必须做出重新定位光标的规定。注意，上述所有注意事项也适用于由于光标移动而发生更改的两个组件的不同目录级别。然而，高级目录节点通常不会驻留在多页块缓冲区中，因此必须使用稍有不同的算法，但仍会有一个“填充”节点和一个“清空”节点。在LSM树的实现提供了额外的经验之后，我们将这些复杂的考虑留到以后的工作中。
到目前为止，我们还没有特别考虑正在考虑的滚动合并从内部组件C0定向到外部C1组件的情况。事实上，与基于磁盘的内部组件相比，这是一种相对简单的情况。与所有这些合并步骤一样，一个CPU应该完全专用于此任务，以便其他访问尽可能短的时间内被写锁排除。应预先计算要合并的C0条目的范围，并使用前面介绍的方法预先对此条目范围进行写锁定。然后，通过批量删除C0组件中的条目来节省CPU时间，而无需在每次删除单个条目后尝试重新平衡；合并步骤完成后，可以完全重新平衡C0树。
4.2 LSM树中的恢复
随着新条目插入到LSM树的C0组件中，滚动合并过程将条目信息迁移到连续较大的组件中，这项工作在内存缓冲的多页块中进行。与任何此类内存缓冲更改一样，在将其写入磁盘之前，工作不会抵抗系统故障。我们面临着一个经典的恢复问题：在崩溃发生和内存丢失后重建内存中发生的工作。正如我们在第2章开头提到的，我们不需要创建特殊日志来恢复新创建记录上的索引项：这些新记录的事务性插入日志在正常事件过程中写入到顺序日志文件中，将这些插入日志（通常包含所有字段值以及插入记录所在的RID）作为重建索引项的逻辑基础很简单。这种恢复索引的新方法必须内置到系统恢复算法中，可能会延长对此类事务历史插入日志进行存储回收之前的时间，但这是一个次要考虑因素。
为了演示LSM树索引的恢复，我们必须仔细定义检查点的形式，并证明我们知道在顺序日志文件中从何处开始，以及如何应用连续日志，以便确定地将更新复制到需要恢复的索引。我们使用的方案如下。当在时间T0请求检查点时，我们完成操作中的所有合并步骤，以便释放节点锁，然后将所有新条目插入延迟到LSM树，直到检查点完成；此时，我们使用以下操作创建一个LSMtree检查点。
o我们将组件C0的内容写入一个已知的磁盘位置；在此之后，可以再次开始向C0插入条目，但合并步骤继续推迟。
o我们将基于磁盘的组件的所有脏内存缓冲节点刷新到磁盘。o我们创建了一个包含以下信息的特殊检查点日志：
o时间T0时最后插入的索引行的日志序列号LSN0 o所有组件根的磁盘地址o所有合并游标在各个组件中的位置o用于动态分配新多页块的当前信息。
一旦这个检查点信息被放置在磁盘上，我们就可以恢复LSM树的常规操作。在崩溃和随后重新启动的情况下，可以找到该检查点，并将保存的组件C0加载回内存，以及继续滚动合并所需的其他组件的缓冲块。然后，从LSN0后的第一个LSN开始的日志被读入内存，并将其相关索引项输入LSM树。截至检查点时，包含所有索引信息的所有基于磁盘的组件的位置都记录在从根开始的组件目录中，其位置从检查点日志中已知。这些信息都不会被多页磁盘块的后续写入擦除，因为这些写入操作总是在磁盘上的新位置进行，直到后续检查点使过时的多页块变得不必要。当我们恢复索引行的插入日志时，我们将新条目放入C0组件；现在，滚动合并再次开始，覆盖自检查点以来写入的任何多页块，但恢复所有新的索引项，直到最近插入的行被索引并完成恢复。
这种恢复方法显然有效，唯一的缺点是在检查点过程中发生各种磁盘写入时可能会出现较大的暂停。然而，这种暂停并不十分重要，因为我们可以在短时间内将C0组件写入磁盘，然后在其余写入磁盘完成时恢复对C0组件的插入；这只会导致比通常更长的延迟期，在此期间，新插入到C0的索引项不会合并到更大的基于磁盘的组件中。一旦检查点完成，滚动合并过程可以赶上它错过的工作。注意，上面的检查点日志列表中提到的最后一条信息是动态分配新的多页块的当前信息。在崩溃的情况下，我们需要找出在恢复过程中，我们的动态磁盘存储分配算法中有哪些多页块可用。这显然不是一个难题；事实上，在23中必须解决一个更困难的问题，即垃圾收集此类块中的碎片信息。
恢复的另一个细节与目录信息有关。请注意，随着滚动合并的进行，每次从要清空的磁盘引入多页块或更高级别的目录节点时，必须立即为其分配一个新的磁盘位置，以防在清空完成之前出现检查点，并且必须将剩余的缓冲信息强制输出到磁盘。这意味着必须立即更正指向清空节点的目录条目，以指向新节点位置。类似地，我们必须立即为新创建的节点分配磁盘位置，以便树中的目录条目能够立即指向磁盘上的适当位置。在每一点上，我们都需要注意，包含指向由滚动合并缓冲的较低级别节点的指针的目录节点也会被缓冲；只有这样，我们才能快速进行所有必要的修改，这样检查点就不会被阻塞，等待I/O更正目录。此外，在出现检查点并将多页块读回内存缓冲区以继续滚动合并后，必须将所有涉及的块分配到新的磁盘位置，因此必须更正指向辅助节点的所有目录指针。如果这听起来像是一个很大的工作，读者应该记得，没有额外的I/O必要的和涉及的指针数量可能只有大约64为每个块缓冲。此外，这些更改应该在大量合并节点上分摊，假设检查点的使用频率仅足以保持恢复时间不超过几分钟；这意味着检查点之间需要几分钟的输入/输出。
5、与其他接入方式的性价比比较
在我们的介绍性示例1.2中，我们考虑了历史文件上Acct ID | |时间戳索引的B树，因为它是商业系统中使用的最常见的基于磁盘的访问方法。我们现在要展示的是，没有任何其他磁盘索引结构能够始终如一地提供优异的I/O性能。为了推动这一说法，我们提出以下论点。
假设我们正在处理任意索引结构。回想一下，我们计算了Acct ID | |时间戳索引中的条目数，假设它们在8小时内的20天累积期内每秒生成1000个条目。给定长度为16字节的索引项（4字节用于帐户ID，8字节用于时间戳，4字节用于历史行RID），这意味着9.2 GB的条目或大约230万个4KB的索引页，即使没有浪费空间。由于指数方法的具体选择，这些结论都不会改变。B-树的叶级具有一定数量的浪费空间和上层目录节点，而可扩展哈希表的浪费空间有所不同，没有目录节点，但这两种结构都必须包含9.2 GB的条目，如上所述。现在，为了向索引结构中插入新的索引项，我们需要计算要插入该项的页面，并确保该页面是内存驻留的。问题自然而然地出现了：新插入的条目通常放在已经存在的所有9.2 GB索引条目中的任意位置吗？对于大多数经典的访问方法结构，答案是肯定的。
定义5.1。如果索引方案允许根据键值将新插入的索引项立即按其最终排序顺序放置，并且所有其他项都已存在，则基于磁盘的访问方法的索引结构具有连续结构的特性。
回想一下，TPC基准应用程序中的连续事务具有从100000000个可能值中的每个值随机生成的Acct ID值。根据定义1.1，账户ID | |时间戳索引的每个新条目插入将被放置在已经存在的230万页条目之一的一个非常随机的位置。例如，在B-树中，576000000个累积条目将包含每个账户ID的平均5.76个条目；假设具有相同账户ID的每个条目都有一个不同的时间戳。因此，每个新条目插入将放在具有相同账户ID的所有条目的右侧。但这仍然会随机选择100000000个插入点，这当然意味着每个新插入将在现有230万页条目中的随机一页上。相比之下，在可扩展散列方案9中，新条目具有排序顺序，该排序顺序是根据Acct ID | | Timestamp键值计算的散列值，显然，新条目与所有已存在的条目按顺序放置的可能性相同。
现在，230万页是一个连续体结构中9.2 GB条目的最小数量，并且假设每秒插入1000次，这样一个结构的每一页大约每2300秒访问一次新插入；根据五分钟规则，保持所有这些页面都处于缓冲状态是不经济的。如果我们考虑较大的节点来保存有界无序文件16中的条目，这没有任何优势，因为尽管有更高的引用频率，但缓冲节点的内存成本也更大，这两种影响相互抵消。一般来说，一个页面被读入内存缓冲区以进行条目插入，然后必须从缓冲区中删除以为其他页面腾出空间。在事务系统中，在将磁盘页从缓冲区中删除之前对其进行就地更新，此更新需要对每个索引插入进行第二次I/O。因此，我们能够声明，不延迟更新的连续结构将需要每个索引插入至少两个I/O，与B树大致相同。
大多数现有的基于磁盘的访问方法是连续结构，包括B树5及其大量变体，如SB树21、有界无序文件16、各种类型的散列方案，如可扩展散列9，以及无数其他方案。然而，有几种访问方法可以将其条目从一个段迁移到另一个段：Kolovson和Stonebraker的MD/OD RTREE（15）和Lomet和Salzberg的时间分割B树（17、18）。差分文件方法25还收集小组件中的更改，然后对全尺寸结构进行更新。我们将更深入地考虑这些结构。
首先，我们应该准确分析为什么LSM树在I/O性能方面优于连续结构，在某些情况下将磁盘臂负载减少了两个数量级。在最一般的公式中，LSM树的优势来自两个因素：（1）保持组件C0内存驻留的能力，以及（2）仔细的延迟放置。将原始插入件制作成基于内存的组件至关重要。正是因为这个原因，在连续结构中插入新条目需要两个I/O：必须放置它们的索引的大小不能经济地缓冲在内存中。如果无法确保组件C0在LSM树中的可靠内存驻留，如果这只是缓冲相对较小的磁盘驻留结构的概率伴随，则可能会出现内存驻留属性恶化的情况，这将导致LSM树性能的严重恶化，因为越来越多的新条目插入导致额外的I/O。在保证初始插入不会导致I/O的情况下，支持LSM树中高性能的第二个因素，即在索引的更大连续体中仔细延迟放置，对于保证组件C0在昂贵的内存介质中不受控制的情况下不会增长非常重要。事实上，多分量LSM树提供了一系列延迟放置，以最小化我们的总成本。事实证明，考虑到特殊结构不是连续结构，虽然提供了在新插入项的最终位置的延迟放置，但这并不是为了保证新插入的初始组件仍然驻留在内存中。相反，该组件被视为驻留在定义文件中的磁盘，尽管很大一部分可能缓冲在内存中。但是，由于无法控制这一因素，组件可能会增长为主要驻留在磁盘上，因此输入/输出性能将下降到一个点，即每个新插入至少需要两个输入/输出，就像B树一样。
时间分割B-树
首先，我们考虑Lomet和Salzberg（17，18）的时间分裂B树或TSB树。TSB树是一种二维搜索结构，通过时间戳和键值的维度来定位记录。假设每次插入具有给定键值的记录时，旧记录就会过时；然而，所有记录的永久历史记录，无论是否过时，都会被编入索引。当在TSB树的（当前）节点中插入一个新条目时，该节点没有接受它的空间，可以根据情况按键值或时间分割该节点。如果按时间t拆分节点，则时间戳范围小于t的所有条目都会转到拆分的历史节点，时间戳范围大于t的所有条目都会转到当前节点。目标是最终将过时的记录迁移到TSB树的一个历史组件，该组件位于廉价的一次写入存储器上。树的所有当前记录和当前节点都位于磁盘上。
我们看到TSB树的模型与我们的有所不同。当写入具有相同帐户ID的新历史行时，我们不认为旧的历史行在任何意义上过时。毫无疑问，TSB树的当前节点集形成了一个单独的组件，该组件将更新推迟到长期组件。然而，没有人试图像LSM树的C0组件那样将当前树保留在内存中。实际上，当前树表示为驻留在磁盘上，而历史树驻留在一次写入存储器上。没有人声称TSB树加速了插入性能；设计的目的是为随时间生成的所有记录提供历史索引。如果没有一个保证内存驻留的组件来执行新的插入，我们又回到了每个条目插入两个I/O的情况。
MD/OD R-树
Kolovson和Stonebraker15的MD/OD R树与TSB树相当，因为它使用二维访问方法（R树）变体，通过时间戳范围和键值对历史记录进行聚类和索引。在MD/OD Rtree中引入的重要R树变体是，该结构意味着跨越磁盘（MD）和光盘（OD）；与TSB树一样，最终的目标是将过时的记录迁移到具有叶页和适当目录页的存档Rtree，这些页和目录页包含在廉价的一次性写入光存储中。这种迁移通过真空吸尘器过程（VCP）进行。每当磁盘上的R树索引达到阈值大小时，VCP就会将最旧叶页的一部分移动到光盘上的存档R树。本文研究了这一过程的两种不同变体，包括抽真空的百分比以及存档树和当前R树是一种还是两种结构（MD/OT-RT-1和MD/OT-RT-2）。与TSB树一样，当前（MD R树）表示为驻留在磁盘上，而存档树（OD R树）驻留在一次写入存储上，并且没有人声称MD/OD Rtree可以加速插入性能。显然，OD目标排除了滚动合并技术。如果没有一个保证内存驻留的组件来执行新的插入，我们返回到每个条目插入两个I/O的情况。事实上，即使15中使用了少量的模拟记录，图4也表明，对于所研究的两种变体结构，每次插入读取的平均页数从未低于2。如果将LSM树和MD/OD R树提升到内存层次结构的一个级别以使用内存和磁盘，则LSM树和MD/OD R树之间存在粗略的对应关系，但由于三种介质的特性不同，大多数细节并不相同。
差分文件
差分文件方法25从一个主数据文件开始，该文件在很长一段时间内保持不变，而新添加的记录被放置到称为差分文件的特定溢出区域。在未来的某个时刻（未仔细指定），假设更改将与主数据文件合并，并将启动一个新的差异文件。本文的大部分内容都与动态区域小得多的优点有关，并提供了避免双重访问的方法，通过唯一的记录标识符查找操作，该标识符需要首先查看差异文件（通过某些索引），然后查看主数据文件（可能通过单独的索引）。提出了布卢姆过滤器的概念，作为避免这种双重访问的主要机制。同样，与上面定义的访问方法一样，差分文件没有保留差分文件内存的规定。第3.4节建议，在转储差分文件并随后将其合并到主文件时，可以合理地将“差分”文件保存在内存缓存中，以允许在线重组。此方法未作进一步分析。它对应于在C1与C2合并时在内存中保留C0组件的想法，但该演示似乎假设插入速率相对较慢，这已由第3.2节中给出的每小时100次更改的10000000记录文件示例证实。不建议差分文件始终驻留在内存中，也没有提及插入操作的I/O节省。
选择性延迟文本索引更新
Dadum、Lum、Praedel和Schlageter7的文本索引维护方法也旨在通过延迟实际磁盘写入来提高索引更新中的系统性能。索引更新会缓存在内存中，直到与查询冲突或由后台任务强制输出。这是一个文本系统，与正在更新的文档相关联的关键字和与查询相关联的关键字之间存在冲突。更新后，查询将从磁盘上的索引中运行。因此，与LSM树不同，内存缓存不是授权索引的一部分。延迟方法允许在强制和滴流情况下批量更新。然而，更新的模式看起来仍然类似于连续结构。
结论和建议的扩展
由于B-树在内存中缓冲了流行的目录节点，因此它实际上是一种混合数据结构，将大多数数据的低磁盘媒体存储成本与最流行数据的高内存可访问性成本结合在一起。LSM树将此层次结构扩展到多个级别，并结合了合并I/O在执行多页磁盘读取时的优势。
在图6.1中，我们对图3.1进行了扩展，绘制了“每兆字节访问成本”与“每兆字节访问速率”（即数据温度）的关系图，用于通过B-树和两个组件的LSM树进行数据访问，即磁盘组件数K=1。从最低访问速率开始，“冷”数据的成本与其所在的磁盘介质成比例；根据典型的成本数字，“冰点”高达每秒0.04 I/O，磁盘访问成本为每兆字节1美元。“热数据”区域开始于冰点，此时磁盘臂成为访问的限制因素，媒体利用不足；在示例3.3中，每兆字节每秒1页I/O的成本为每兆字节25美元。最后，当访问如此频繁以至于B-树访问的数据应该保留在内存缓冲区中时，我们有“热数据”；在每兆字节100美元的内存中，这种访问速率的成本将是每兆字节100美元，这意味着每兆字节至少有4个I/O的速率，即“沸点”。
成本/兆字节
缓冲对B-树的影响是，当访问速率进入热数据区域时，图变平，因此更频繁的访问不会导致更高的成本，从而延长热数据上升线的斜率。稍加考虑，可以看出，LSM树的作用是降低访问成本，对于插入和删除等可合并操作的任何实际访问速率，都非常接近冷数据。此外，许多表示B树内存驻留的访问速率情况（图4.1中标记为“热数据”的情况）大多可以在具有LSM树的磁盘上容纳。在这些情况下，数据在逻辑访问速率（插入数/秒）方面是热的，但在物理磁盘访问速率方面是热的，因为LSM树的批处理效应。对于具有可合并操作优势的应用程序来说，这是一个极其显著的优势。
6.1 LSM树应用的扩展
首先，应该清楚的是，LSM树条目本身可以包含记录，而不是指向磁盘上其他位置记录的RID。这意味着记录本身可以按其键值进行聚类。这样做的成本是较大的条目和以字节/秒为单位的插入速率R的同时加速，从而导致光标移动和总I/O速率H的加速。然而，正如我们在示例3.3中看到的那样，三分量LSM树应该能够提供必要的循环，而以存储记录和索引的磁盘介质为代价，在任何情况下，都需要所有这些磁盘介质以非集群方式存储行。
集群的优势可能具有相当重要的性能影响。例如，考虑托管事务方法20，由于长寿命更新的非阻塞性，它是支持工作流管理的良好层。在托管方法中，长期交易可以生成对各种聚合托管字段的大量增量更改。使用的方法是留出请求的增量金额（托管数量），并解锁并发请求的聚合记录。我们需要为这些托管数量保留日志，我们可以为这些日志考虑两个可能的聚类索引：生成事务的事务ID（TID）和获取托管数量的字段的字段ID（FID）。我们可能很容易有二十个托管日志，其中一个TID在一段较长的时间内存在（足够长的时间，使日志不再驻留在经典日志结构中的内存中），并且在事务执行提交或中止之前，通过TID进行聚类是很重要的，这决定了这些日志的最终效果。在提交的情况下，从字段中取出的数量将是永久性的，并且可以简单地忘记日志，但在中止的情况下，我们希望将数量返回到日志的FID指定的字段。需要一定的速度。在处理中止时，应访问中止事务的日志（通过TID进行聚类是一个重要优势），并应更正具有相应FID的字段。但是，如果该字段不是内存驻留字段，而不是在包含记录中读取，则可以通过其FID重新创建日志（放置在不同的LSM树中）。然后，当托管字段读回内存时，我们将尝试访问由FID聚集的所有日志，这些日志可能需要执行一些更新；同样，可能会访问大量日志，将这些日志聚集在LSM树中是一个重要的节约。使用LSM树首先通过TID对托管日志进行聚类，然后在相关字段不在内存中时通过FID对托管日志进行聚类，这将节省大量I/O，其中长期事务会对冷数据或热数据进行大量更新。这种方法是对20中“扩展场”概念的改进。
第2.2节末尾提到的LSM树算法的另一个可能变化是，可能在分量Ci中保留最近的条目（在最后τi秒内生成），而不是让它们迁移到Ci+1。这一想法提出了许多替代方案。一种变体表明，在光标循环期间，可能会生成时间键索引，如TSB树提供的索引。滚动合并可用于为新版本插入提供极大的效率，多组件结构建议将最终组件迁移到一次写入存储，并对存档时间键索引进行大量控制。这种方法显然值得进一步研究，并已成为一份会议文件22的主题。
进一步研究的其他想法包括以下内容。
（1） 将定理3.1和示例3.3的成本分析方法扩展到以下情况：为了实现输入/输出平衡，必须使用合并来平衡一定比例的查找操作。由于磁盘上增加了负载，因此将无法再将所有磁盘I/O容量分配给滚动合并操作并针对这种情况进行优化。必须留出一定比例的磁盘容量用于查找操作负载。扩展成本分析的其他方法是允许在迁移到组件CK之前删除，并考虑在（Ci-1，Ci）合并期间在内部组件Ci-1中保留一定比例的最近条目。
（2） 很明显，我们可以卸载CPU工作来维护LSM树，这样就不必由生成日志记录的CPU来完成。我们只需要将日志传递给另一个CPU，然后再传递find请求。在有共享内存的情况下，查找几乎可以在不增加延迟的情况下完成。这种分布式工作的设计需要仔细考虑。
致谢
作者感谢Jim Gray和Dave Lomet的帮助，他们都阅读了本文的早期版本，并提出了宝贵的改进建议。此外，审稿人对这篇文章提出了许多有价值的建议。
[1] Dept. of Math & C.S, UMass/Boston, Boston, MA 02125-3393, {poneil | eoneil}@cs.umb.edu
[2] Digital Equipment Corporation, Palo Alto, CA 94301, edwardc@pa.dec.com
[3] Oracle Corporation, Redwood Shores, CA, dgawlick@us.oracle.com
本文系外文翻译，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文系外文翻译，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。