回顾了LSM-tree的历史，以及leveling和tiering两种合并方式，接着介绍布隆过滤器和分区（对于tiering还有两种分区方案）这两个普遍的优化，简要带过并发控制和恢复技术后，最后在写，点查询，范围查询，空间放大等角度分析了两种合并方式的开销。

1 Introduction

1)日志结构的合并树(LSM-tree)被广泛应用于现代NoSQL系统的存储层.LSM树首先在内存中缓冲所有写操作，然后将它们刷新到磁盘，并使用顺序I/O合并它们。这种设计带来了许多优点，包括优越的写性能、高的空间利用率、可调性以及简化并发控制和恢复。这些优点使LSM树能够服务于各种各样的工作负载

2 LSM-tree basics

2.1 History of LSM-trees

通常，索引结构可以选择两种策略中的一种来处理更新，即就地（in-place）更新和非就地（即异位，out-of-place）更新。就地更新结构，如B+树，直接覆盖旧记录来存储新更新。例如，在图1a中，为了将key k1的值从v1更新到v4，索引条目(k1, v1)被直接修改以应用该更新。这些结构通常是读优化的，因为只存储每个记录的最新版本。然而，这种设计牺牲了写性能，因为更新会导致随机I/O。此外，索引页可以被更新和删除所分割，从而减少空间利用率。

异位（out-of-place）的更新结构，例如LSM-tree总是将更新存储到新的位置，而不是覆盖旧的条目。例如在图1b中，更新(k1, v4)被存储到一个新的位置，而不是直接更新旧的条目(k1, v1)。这种设计提高了写性能，因为它可以利用顺序I/O来处理写。它还可以通过不覆盖旧数据来简化恢复过程。然而，这种设计的主要问题是牺牲了读取性能，因为记录可能存储在多个位置中的任何一个。此外，这些结构通常需要一个独立的数据重组过程，以不断提高存储和查询效率

2.2 Today's LSM-trees

2.2.1 Basic structure

今天的LSM树实现仍然应用异位更新来减少随机I/O。所有传入的写操作都被追加到内存组件中。插入或更新操作只是添加一个新条目，而删除操作则添加一个antimatter条目，表明key已被删除。然而，目前的LSM树实现通常利用磁盘组件（disk components）[5] 的不变性来简化并发控制和恢复。多个磁盘组件合并(merge)[6]成一个新的组件，无需修改现有组件。这与原来的LSM树[51]提出的滚动合并过程不同。

在内部，可以使用任何索引结构实现LSM树组件。今天的LSM树实现——通常使用跳表或B +树等并发数据结构来组织内存组件，而使用B+树或排序字符串表(sorted-string tables， SSTables)来组织磁盘组件。SSTable包含一个数据块列表和一个索引块：数据块存储按键排序的键值对，索引块存储所有数据块的键范围。

LSM树上的查询必须搜索多个组件以执行协调（reconciliation），即查找每个键的最新版本。获取特定键值的点查找查询（point lookup query）可以简单地逐个搜索所有组件(从最新到最老)，并在找到第一个匹配项后立即停止。范围查询（range query）可以同时搜索所有组件，将搜索结果输入优先级队列以执行调整。

随着时间的推移，磁盘组件越来越多，LSM-tree的查询性能趋于下降，因为必须检查更多的组件。为了解决这个问题，磁盘组件逐渐合并，以减少组件的总数.

2.2.2 Some well-known optimizations

目前大多数LSM树实现都使用了两种众所周知的优化。

Bloom filter    Bloom过滤器[12]是一种空间效率高的概率数据结构，旨在帮助回答集合成员查询（set membership queries）。它支持两种操作，即插入键和测试给定键的成员关系。为了插入一个键，它应用多个哈希函数将键映射到位向量中的多个位置，并将这些位置上的位设为1。为了检查给定键是否存在，该键再次散列到多个位置。如果所有位都是1，则Bloom过滤器报告键可能存在。按照设计，Bloom过滤器可以报告假阳性，但不能报告假阴性[8]。

由于Bloom过滤器非常小，通常可以缓存到内存中，因此使用它们可以大大减少点查找的磁盘I/O数量。

Partitioning。另一种常用的优化是将LSM树的磁盘组件范围划分为多个(通常是固定大小的)小分区。为了尽量减少由不同术语造成的混淆，我们使用术语SSTable来表示这样的分区，它遵循LevelDB[40]中的术语。这种优化有几个优点。首先，分区将一个大的组件合并操作分解为多个较小的操作，限制了合并操作的处理时间以及创建新组件所需的磁盘空间。此外，分区可以通过只合并具有重叠键范围的组件来优化具有顺序创建键或倾斜更新的工作负载。对于按顺序创建的键，基本上不执行合并，因为没有键范围重叠的组件。对于倾斜更新，冷更新范围的组件的合并频率可以大大降低。需要注意的是，原来的LSM-tree[51]会自动利用分区，因为它可以滚动合并。然而，由于滚动合并的实现复杂性，今天的LSM树实现通常选择实际的物理分区而不是滚动合并。

将分区应用到LSM树的一个早期建议是分区指数文件(partitioned exponential file，PE文件)[35]。一个PE文件包含多个分区，其中每个分区在逻辑上都可以看作一个独立的LSM树。当一个分区变得太大时，可以进一步将其分割为两个分区。然而，这种设计在分区之间强制执行严格的键范围边界，这降低了合并的灵活性。

现在我们讨论在当今的LSM树实现中使用的分区优化。需要注意的是，分区与合并策略是正交的；leveling merge和tiering merge(以及其他新兴的合并策略)都可以用于支持分区。据我们所知，只有基于LSM的工业存储系统(如LevelDB[40]和RocksDB[57])完全实现了分区水平合并策略（partitioned leveling merge policy）。最近的一些论文[6,49,58,76,79]提出了各种形式的分区分层合并策略（partitioned tiering merge policy），以获得更好的写性能[9]。

在LevelDB[40]首创的分区leveling merge policy中，每个级别（Level）的磁盘组件被范围划分为多个固定大小的SSTable，如图4所示。每个SSTable在图中都有其key范围的标记。注意，Level 0的磁盘组件没有分区，因为它们是直接从内存中刷下的。这种设计还可以帮助系统吸收突发写（absorb write bursts），因为它可以在Level 0容忍多个未分区组件。为了将Level L的SSTable合并为Level L+1的SSTable，我们将选取其所有Level L+1的重叠的SSTable[10]，并将这些重叠的SSTable与之合并，生成新的仍在Level L+1的SSTable。例如在图4中，Level 1标记为0-30的SSTable与Level 2标记为0-15和16-32的SSTable合并。这个合并操作产生在第2级标记为0-10、11-19和20-32的新的SSTables，然后旧的SSTable将被垃圾收集。可以使用不同的策略来选择接下来在每个Level合并哪个SSTable。例如，LevelDB使用循环策略（round-robin policy）以最小化总的写开销。[11]

分区优化也可以应用到tiering merge policy中。然而，这样做的一个主要问题是，每个级别可能包含多个具有重叠键范围的SSTables。这些SSTable必须根据它们的近代性（recency）进行适当的排序，以确保正确性。在每个层次上，可以采用两种可能的方案来组织SSTable，即垂直分组和水平分组。在这两种方案中，每一层的SSTable被组织成组。垂直分组方案将键范围重叠的SSTable分组在一起，使分组具有分离的键范围。因此，它可以被看作是partitioned leveling merge的一种扩展，以支持tiering。或者，在水平分组方案下，每个逻辑磁盘组件被范围划分为一组SSTable，直接作为一个组。这允许在SSTable单元的基础上增量地形成磁盘组件。下面我们将详细讨论这两种方案。

垂直分组方案示例如图5所示。在这种方案中，具有重叠键范围的SSTable被分组在一起，这样分组就具有不相交的键范围。在合并操作中，一个组中的所有SSTable被合并在一起，根据下一层重叠组的键范围产生最终的SSTable，然后将这些SSTable添加到这些重叠组中。例如在图中，level 1标记为0-30和0-31的SSTable被合并在一起，生成标记为0-12和17-31的SSTable，然后加入到2级重叠组中。请注意合并操作前后的SSTable之间的区别。在进行合并操作之前，标记为0-30和0-31的SSTable具有重叠的键范围，点查找查询必须一起检查它们。然而，在合并操作之后，标记为0-12和17-31的SSTables具有不相连的键范围，并且只有其中一个需要通过点查找查询进行检查。还应当指出，在这一办法下，SSTable的规模不再是固定的，因为它们是根据下一级重叠组的键范围产生的。

图6显示了水平分组方案的一个示例。在该方案中，每个组件被范围划分为一组固定大小的SSTable，直接作为一个逻辑组。每个level L进一步维护一个活跃组，这也是第一个组，接收从上一级别合并的新SSTable。这个活动组可以看作是由Level L-1的组件在未分区情况下合并而成的部分组件。合并操作从一个级别上的所有组中选择键范围重叠的SSTable，并将得到的SSTable添加到下一级别的活跃组中。例如在图中，Level 1标记为35-70和35-65的SSTable被合并在一起，Level 2标记为35-52和53-70的SSTable被添加到第一组。然而，尽管在水平分组方案下，SSTable的大小是固定的，但仍然有可能一个组中的一个SSTable与其他组中的大量SSTable重叠。