翻译内容
2. The Two Component LSM-Tree Algorithm
一个LSM-tree是有两个或更多类似树的组件构成。本节分析两个组件的情况，并且假定内容是历史表索引。见图2.1.
两个组件的的LSM-tree有一个更小内存存储的C0树和一个大点的磁盘存储的C1树组成。虽然C1时磁盘存储，频繁使用的C1内容会保存到内存中，所以C1中高层次目录可以当做在内存中看待。
每次新行插入会先以一般方式写入日志到log文件。索引先插入C0，之后会迁移内容到C1树的磁盘上。搜索先从C0开始，再写入C1.在C0树中的条目迁移到磁盘所在的C1树之前，存在一定的延迟(延迟)，这意味着需要恢复在崩溃之前没有迁移到磁盘的索引条目。
恢复将在第4节中讨论，但现在我们只注意允许我们恢复History行新插入的日志记录可以被视为逻辑日志;在恢复期间，我们可以重构已插入的History行，并同时重新创建索引这些行所需的任何条目，以重新获取C0丢失的内容。（有道翻译）
插入数据到C0没有磁盘I/O操作。然而，C0组件占用更多内存，有大小的限制。需要高效的把C0迁移到存储在磁盘上的C1的过程。
为了实现这一点，每当由于插入而导致的C0树达到接近分配的最大大小的阈值时，一个正在进行的滚动合并进程将从C0树中删除一些连续的条目片段，并将其合并到磁盘上的C1树中。图2.2描述了滚动合并过程的概念图。（有道翻译）
C1树具有与b树类似的目录结构，但它对顺序磁盘访问进行了优化，节点100%满，根以下每一层的单页节点序列打包在连续的多页磁盘块中，以实现高效的arm使用;这种优化也被用于SB-tree[21]。多页块I/O用于滚动合并和长范围检索，而单页节点用于匹配索引发现以最小化缓冲需求。256kbytes的多页块被设想包含根下的节点;根据定义，根节点始终是单个页面。（有道翻译）
回滚合并操作是一系列合并步骤。读取多页C1树叶子节点内容，排序存储在C1点缓存内。每次在缓存读取一个磁盘页大小的内容，和C0合并，这样C0变大，创建一个新的C1节点。
包含旧节点的多页块被称为空块，新内容写入新的填充块。当新的填充快填满C1的节点，写入磁盘空闲区域。新内容在图2.2的右边。后续的合并步骤导致索引段不断增长直到达到最大值，再次从最小开始合并。
新内容写入磁盘新位置，旧的磁盘块不会被覆盖，在程序挂掉的情况下还可以恢复。C1中的父目录也在缓存中，会更新叶子节点的机构，但一般会在缓存保存一段时间来减少I/O操作；旧的叶子结点在合并完成后就失效了，之后会在C1的目录中删除。一般情况下，每个合并步骤会有失效的叶子节点，但是不一定有新的节点，只是有旧的空节点。
对于多页块也同样需要考虑，因为通常当填充块已经填充了新合并的节点时，仍然会有许多包含条目的节点在收缩的块中。（有道翻译）
失效的内容，随着更新目录信息，仍然会保存一段时间才会写入磁盘。合并和恢复相关并发处理在第四章。为了减少恢复操作内容，会周期性的保存一个检查点保存所有缓存内容到磁盘。
2.1 How a Two Component LSM-tree Grows
跟踪LSM-tree增加内容的变化过程，先从内存存储的C0树插入开始。不像C1，C0没有类似B树的结构。首先，大小没有限制：不需要匹配磁盘页大小，C0不会存储在磁盘上，所以不需要消耗CPU减少深度。因此一个（2-3）树活在AVL-tree是两个可以选择的C0结构。当C0达到边界大小，一个最左边的序列会从C0删除（批量操作，而不是每条内容只想一次）重组写入填满C1的子节点。连续的叶子节点从左到右存储在缓存的多页存储块中，直到存满；然后存储磁盘称为C1的叶节点。C1的节点目录连续的存储在内存中，详细内容后续分析。
以不断增加的键序顺序将C1树叶子级的连续多页块写入磁盘，以防止C0树阈值大小超过其阈值。上层C1树目录节点是在单独的多页块缓冲区中维护的，或者是在单页缓冲区中维护的，从总内存和磁盘臂成本的角度来看，哪个更有意义;这些目录节点中的条目包含分隔符，分隔符引导对下面单个单页节点的访问，就像在b -树中一样。这样做的目的是沿着单页索引节点到叶节点的路径提供高效的精确匹配访问，在这种情况下避免多页块读取，以最小化内存缓冲区需求。因此，我们为滚动合并或长范围检索读写多页块，为索引的find(精确匹配)访问读写单页节点。（有道翻译）
一个不同的架构见[21].
在写出叶节点块序列时，C1目录节点的部分满的多页块通常允许留在缓冲区中。（有道翻译）
C1目录在下面的情况会强制写入磁盘新空间：
多页缓存满；
根分裂，增加一层深度；
执行检查点。
在第一种情况下，已填满的单个多页块被写入磁盘。后面两种情况，多页块的缓存和目录缓存写入磁盘。
最右边的C0树的叶子条目后首次写入C1树,左边的过程重新开始的两棵树,现在除了和连续通过多页面C1树的叶级块必须读入缓冲区和合并C0树中的条目,从而创建新的C1多页叶块，将其写入磁盘。（有道翻译）
一旦开始合并，场景就更复杂了。
我们将两个组件lsm树中的滚动合并过程描绘为一个概念性游标，它以量化的步骤缓慢地循环C0树和C1树组件的相同键值，将索引数据从C0树提取到磁盘上的C1树。（有道翻译）。
位置标记在C1的叶子层上，同时在每一个更高层的目录上。每层，C1的当前多页块一般分成两块：
空块：保留了已删除但是合并标记还没有执行到的内容，
填充块：合并结果保存。
缓存中的填充块和空快都有类似的填充节点和空节点对应。出于并发操作目的，每层的空快和填充快都有一个整数表示页节点大小，简化缓存操作。(在合并操作重构节点阶段，其他并发操作节点的被阻塞。)
当一个完整flush缓存操作执行，所有缓存信息写入新磁盘新位置，带有目录信息序列化操作log用于恢复信息）。之后，一个填充快需要写入磁盘时，会写入一个新的磁盘位置。旧的信息仍然可能用于恢复信息，只有更新成功了，信息才失效。第四章更详细介绍合并处理过程，包括并发和恢复的设计实现。
当在C1树的特定级别上滚动合并进程以相对较高的速度通过节点时，所有读和写都在多页块中，这是lsm树的一个重要效率考虑因素。通过消除寻道时间和旋转延迟，我们期望获得比普通b树插入所涉及的随机页面I/O更大的优势。(详细信息见3.2.) 总是将多页块写入新位置的想法受到了Rosenblum和Ousterhout[23]设计的日志结构文件系统的启发，日志结构合并树就是从这个系统中获得名字的。请注意，为新的多页块写而持续使用新的磁盘空间意味着要写入的磁盘区域将被包装，并且必须重用旧的丢弃的块。这种簿记可以在内存表中完成;旧的多页块失效并作为单个单元重用，恢复由检查点保证。在日志结构文件系统中，旧块的重用涉及大量的I/O，因为块通常只被部分释放，所以重用需要读块和写块。在LSM-Tree中，滚动合并的后缘完全释放了块，因此不涉及额外的I/O。（有道翻译）
2.2 Finds in the LSM-tree Index
当一个明确匹配的搜索或者顺序搜索请求立即执行，首先搜索C0，之后的C1.这可能稍微超过B-tree的比较开销，因为可能需要搜索两个目录。LSM中超过两个组件，可能有I/O开销。预测第三章，定义一个多个组件C0～CK，索引结构增加大小，C0存储在内存，其他在磁盘。
在所有组件对(Ci-1, Ci)之间存在异步滚动合并进程，每当较小的组件Ci-1超过其阈值时，这些进程就将条目从较小的组件移到较大的组件。（有道翻译）
作为一个规则，为了保证检索所有的LSM内容都检查一遍，需要一个精确匹配搜索或者顺序遍历每个组件的索引结构。然而，有一些方法可以优化搜索在一个受限的初始子集。
首先，在生成逻辑保证惟一索引值的情况下(如保证时间戳是不同的)，如果匹配的索引find在早期Ci组件中找到所需的值，那么它就是完整的。另一个例子是，当find条件使用最近的时间戳值时，我们可以限制搜索，以便搜索的条目还不能迁移到最大的组件。当合并游标在(Ci, Ci+1)对中循环时，我们通常有理由保留Ci中最近插入的条目(最近τi秒)，只允许较老的条目输出到Ci+1。在最频繁的查找引用是最近插入的值的情况下，许多查找可以在C0树中完成，因此C0树实现了有价值的内存缓冲功能。这一点也在[23]中提出，并代表了一个重要的效率考虑。例如，在中断事件中访问的短期事务UNDO日志的索引将在创建后相对较短的时间内有很大比例的访问，我们可以预期这些索引中的大多数将保留在内存中。通过跟踪每一笔交易的开始时间，我们可以保证所有在最后τ0秒内开始的交易的日志，例如，将在组件C0中找到，而无需求助于磁盘组件。（有道翻译）
2.3 Deletes, Updates and Long-Latency Finds in the LSM-tree
我们注意到，删除和插入可以共享延迟和批处理的有价值的属性。当删除索引行时，如果在C0树的适当位置没有找到键值条目，则可以将删除节点条目放置在该位置，也根据键值建立索引，但注意要删除的条目row ID (RID)。实际的删除可以在稍后的滚动合并过程中进行，当遇到实际的索引项时:我们说删除节点条目在合并期间迁移到更大的组件，并在遇到相关条目时消灭它。同时，必须通过删除节点条目过滤查找请求，以避免返回对已删除记录的引用。在搜索相关的键值时，这种筛选很容易执行，因为delete节点条目将位于比条目本身更早的组件的适当的键值位置，而且在许多情况下，这种筛选将减少确定删除条目的开销。在任何类型的应用程序中，导致索引值更改的记录更新都是不常见的，但如果我们将更新看作是先删除后插入，则lsm树可以以延迟的方式处理这种更新。（有道翻译）
我们简述了另一种有效的索引修改操作。称为谓词删除的过程提供了一种执行批删除的方法，只需断言一个谓词，例如断言所有时间戳超过20天的索引值都要删除。当最旧(最大)组件中的受影响项在滚动合并的正常过程中成为常驻项时，此断言将导致它们在合并过程中被删除。还有另一种类型的操作，即长延迟查找，提供了一种有效的方法来响应查询，其中结果可以等待最慢的currensor的循环周期。在组件C0中插入一个查找记录条目，当它迁移到后面的组件时，查找实际上是在一段较长的时间内执行的。一旦查找记录条目被分发到lsm树中最大相关组件的适当区域，用于长延迟查找的累积rid列表就完成了。
（有道翻译）
吐槽：作者的长句子太长了。
todo：再分析一下，部分没有自己翻译，仔细读一遍
