LSM-tree不同合并方式的分析和比较

Author Avatar
MorphLing 7月 04, 2022

LSM-tree不同合并方式的分析和比较

摘要

本文首先介绍了LSM-tree的基本概念，包括历史由来、基本结构、组件实现、合并方式和常见的优化方法。接着以Leveling和Tiering两种合并方式为例，引出了不同合并方法在不同操作上的性能取舍，并从磁盘I/O的角度进行代价分析，从写代价、单点查询、区间查询和空间放大的角度分析不同合并方式的开销。然后介绍了一种基于Leveling和Tiering，将两者结合的Dostoevsky合并方式，介绍这种方式的优缺点。最后介绍了关于合并方式的未来研究方向。

介绍

LSM-tree被广泛采用于现代NoSQL系统中的存储层。因此有大量的相关研究，比如数据库系统和操作系统两大领域都在尝试对LSM-tree进行改善。

与传统的索引结构in-place的更新方式不同，LSM-tree采取一种out-of-place的更新方式：首先在内存中对所有写操作进行缓存，并在之后将它们刷进磁盘，并通过一连串的IO进行合并。这种设计带来了许多好处，包括非常好的写效率、高空间利用率、可协调性和对并发控制、并发恢复的简化。这些优势使得LSM-trees能够服务于各种类型的负载。

由于LSM-tree的流行性，有许多关于LSM-tree的设计优化被提出，这篇文章首先对LSM-tree的基本概念作简单的介绍，接着以leveling和tiering两种合并方式为切入点，分析两种合并方式在性能差异，介绍与两者相关的优化，以及未来的研究方向。

基本概念

LSM-tree的历史由来

索引结构可以有两种方式来处理更新，分别是in-place和out-of-place。使用in-place方式更新的结构，比如B+-tree，通过直接覆盖旧记录来存储新的更新。比如Fig 1a中，通过将键值k1的value从v1更新至v4，那么键值对(k1, v1)直接因这次更新被修改了。这些结构（in-place update）通常倾向于读优化，因为只有每个记录的最近版本被存储了。然而，这种设计牺牲了写性能，因为更新会导致随机IO，而且通常索引页会被更新和删除划分成很多个碎片，导致空间利用率的降低。

下图比较了in-place update和out-of-place update的差异。

image-20220627175052394

Fig 1

相反，对于out-of-place update结构，比如LSM-tree，总是更新到新的位置而不是覆盖旧的记录。比如Fig 1b，更新(k1, v4)被存到了新的地方，而不是直接更新(k1, v1)。这种设计改进了写性能因为能利用连续IO来处理读操作。这同样能够简化恢复操作，因为没有覆盖旧数据。但最主要的问题是，这种设计的读性能被牺牲了，因为一个记录可能被存在多处位置。进一步说，这些结构通常需要一个将分散数据重新组织和处理，来不断地改进存储和查询效率。

out-of-place的想法从1970年代就被提出并用于数据库系统，但那时还存在许多问题，比如将数据存储到仅追加的日志会导致低的读效率，因为相关的记录被分散在整个日志中。另一个问题是低的空间利用率，因为无用的日志没有被移除。同时也没有标准的代价模型去分析各种代价之间的权衡，直到1996年LSM-tree被提出解决了这些问题。

LSM-tree的基本结构

最初的LSM-tree设计包含了一系列组件$C_0,C_1,\cdots,C_k$，就如Fig 2中所示。每个组件的结构都像一颗B+-tree，$C_0$驻留在内存并服务于即将到来的写操作，剩下的所有组件驻留在磁盘中。当$C_i$写满了，一个滚动合并进程会被触发，将$C_i$中一定范围的叶节点页(leaf pages)合并入$C_{i+1}$。这种设计通常指的是现在所说的层级合并策略。但这种最开始的层级合并进程并没有被现在的基于LSM-tree的层数系统使用，因为它的实现复杂度过高。最初关于LSM-tree的论文表示，当处于一个稳定的负载时，叶节点的数量保持静态，如果所有的相邻组件的大小比例都相同($T_i=|C_{i+1}|/|C_i|$)，写性能此时能够被优化。这个原则对所有LSM-tree的后续实现和改进产生影响。

Fig 2

LSM-tree的组件实现

从内部来看，LSM-tree的组件可以使用任何索引结构来实现。如今LSM-tree的实现通常会用内存组件构成一个并发数据结构，比如skip-list或者B+-tree，在磁盘组件上则用B+-tree或者SSTable(sorted-string tables)，一个SSTable包含一系列数据块和一个索引块；数据块存储了按照key排序后的键值对，索引块存储了所有数据块的键值区间。

由数据结构的特点发现，SSTable可以通过index结构找到要读取的数据块磁盘位置，那么对于单点的插入和查询在磁盘IO上的复杂度是$O(1)$的，这为后面的代价分析提供了基础。

LSM-tree的合并方式

在LSM-tree上询问需要搜索多个组件才能保证一致，也就是要找到每个键值的最后版本。这里分成点查和区间查，点查需要找到特定键对应的值，可以简单地从最新的组件找到最旧的组件，这样第一次匹配一定就是最后版本，可以立刻停下。区间查可以同时查询所有的组件，把查询结果放进一个优先队列来保证一致。当磁盘组件随着时间积累，查询性能会逐渐变差，因为需要检查更多的组件。为了解决这个问题，磁盘组件会逐渐合并并减少组件数量。

合并实际上是LSM tree这种架构里面的核心问题，也直接影响到实现的效率和成本。我们可以假设合并操作存在两个极端情况：

image-20220627161943029

Fig 3

  • 第一种极端如Fig 3左上的log方案，即完全不进行合并，所有数据全部写入Log，然后直接灌入SStable，这种做法更新代价当然是最低的，直接写入磁盘即可。但是一旦要查询或者更新一个键值对，开销就会非常大。因为此时磁盘上的记录既没有排序，也没有去除废弃的记录，只能线性一个一个查，效率低下。而且空间利用率非常低，数据会随着输入线性增长，磁盘空间会被迅速占满。

  • 第二种极端如Fig 3右下sorted array方案，每次得到一条新的写入，立刻进行compaction，时刻维持整个数据更新到最新值，并保持sorted状态。这样的查询效率显然最高，但是需要每次更新都去调整，进行排序和更新的开销太大。

所以现实中的LSM-tree都是在这两种方案之间的折中。会在更新积累到一定程度后再做一次合并。

LSM-tree的常见优化方法

这里有两种常见的优化方法，已经被用在了如今大多数LSM-tree的实现中：

布隆过滤器：布隆过滤器是一个节约空间的概率数据结构，能够帮助回答集合成员查询问题。它支持两种操作：插入一个key，和回答给定集合中是否包含一个key。插入key时，对key进行多次hash操作，映射到为一个二进制向量的多个位置，置这些位置为1。检查指定的key是否存在时，同样方法哈希，如果多个哈希的位置都是1，说明该key可能存在，否则一定不存在。这种设计下布隆过滤器报告可能会有假阳性，但不会有假阴性。布隆过滤器可以被放置在磁盘组件的顶端，来改进点查询效率。在搜索磁盘组件之前，可以首先检查布隆过滤器，只有当布隆过滤器认为可能存在key时再去B+-tree上搜索。另一种用法是在每个叶节点页上加一个布隆过滤器，这样只要先在非叶节点上搜索（假设非页节点总是小到能够被cache容纳），用布隆过滤器减少对叶节点的访问，以此减少磁盘IO次数。需要注意的是，布隆过滤器造成的假阳性不会影响到查询的正确性，但会造成一些IO的浪费。这个假阳性的概率可以由$(1-e^{-kn/m})^k$计算，k是hash函数个数，n是键值个数，m是向量长度。进一步可以计算出，使得假阳性概率最低的最优的哈希函数个数$k=\frac{m}{n}\ln 2$。因为布隆过滤器很小，能够被缓存在内存中，磁盘IO的次数会显著减少。

分区：另一种常见的优化是把LSM-tree磁盘组件分成多个通常大小固定的小分区。为了减少术语上造成的误解，我们用SSTable来表示这样的分区。这个优化有很多好处，首先，分区把一次大合并操作拆分成多个小合并，这和每次merge操作的进程时间、创建新组件的临时磁盘空间需求是相关的。进一步，分区可以优化连续新建key的负载，以及只有重叠key的混合更新。对于连续新建的key，实际上不会有合并发生，因为没有重复的key区间。对于混合更新，组件冷区间的合并频率会大幅减少。最开始的LSM-tree由于滚动合并的设计，可以自然从分区中受益，但由于级联合并在实现上的复杂性，如今的LSM-tree通常使用物理上的分区，而不是级联合并。一种早期的分区方法是用分区指数文件(PE-file)。一个PE-file包含多个分区，每个分区可以在逻辑上看成一颗独立的LSM-tree。一个分区可以在它过大的时候被进一步分成两个分区。但是这种设计要求分区之间有严格的区间限制，会减少合并的自由度。

比较Leveling和Tiering两种合并方式

介绍

之前提到，不同的合并方式会对LSM-tree的读写性能、空间利用率产生不同的影响。这里主要考虑两种基础的合并策略：Leveling和Tiering。

Fig 4a表示leveling合并策略，每一层只包含一个组件，但是第L层的组件比第L-1层的组件大T倍。结果就是，第L层的组件会被第L-1层的组件合并多次，直到它被填满，并被合并入L+1层的组件。如图中的例子，level 0被合并入level 1，使得level 1的组件变得更大了。

相反，tiering合并策略在每一层都维护最多T个组件，当第L层满了，它的T个组件会被一起合并到一个L+1层的新组件。图中，level 0的两个组件一起合并形成了一个level 1的新组件。值得一提的是，如果level L已经达到配置中的最大层数，那么生成的新组件会停留在第L层。实际情况中，对于一个稳定的工作负载（插入量等于删除量，那么level的总数保持静态）。总的来说，leveling合并策略优化查询性能，因为组件更少，搜索需要的代价也更少。而tiering合并策略更注重优化写，因为它减少了合并的频率。

Fig 4

代价分析

为了进一步理解LSM-tree的性能取舍，需要具体分析写、点查询、区间查询和空间放大的代价分析上。代价会被磁盘IO次数来决定。分析过程只考虑了一个未分区的LSM-tree，并只考虑最坏情况下的代价。

假设LSM-tree的大小比例为T，并假设共有L层。实际情况下，对于稳定的LSM-tree，插入和删除的数据量相同，L维持静态。假设B是页大小，也就是每一页能存放的记录条数。P是一个内存组件的页数。那么，一个内存组件可以容纳至多$B\cdot P$条数据，并且第i层可以容纳最多$T^{i+1}\cdot B\cdot P$条数据。给定N为数据总量，最大的level包含了大约$N\cdot \frac{T}{T+1}$条数据，因为它比上一层大T倍。于是，数据量为N时，层的数量可以被估计成$L=\lceil \log_T(\frac{N}{B\cdot P}\cdot \frac{T}{T+1}\rceil$。

现在开始分析各种操作会产生的代价。

写代价

写代价衡量了插入一条数据进LSM-tree的均摊IO代价。需要注意，因为插入一条数据进内存并不会带来任何磁盘IO，所以度量了把记录合并入最深一层的整体IO代价。对于leveling merge，每层的组件都会被合并T-1次，直到它被填满，并推入下一层。对于tiering merge，同一层的多个组件只会被合并一次，并直接被推入下一层。因为每一个磁盘页包含B条记录，每条记录的写代价会变为$O(T\cdot\frac{L}{B})$（对于leveling）和$O(\frac{L}{B})$（对于tiering）。

为了方便理解，这里具体解释一下复杂度的计算，可以考虑一条记录是如何从第0层逐层合并入最后一层的，在leveling策略下，每条记录在每一层都会参与合并T次，这部分的开销是$O(T\cdot L)$；tiering策略下，每条记录在每一层只会参与1次合并，总体开销是$O(L)$，由于一次IO可以同时操作B条记录，所以分母上除去B。

单点查询

单点查询的I/O代价取决于LSM-tree中组件的数量。在不使用布隆过滤器的情况下，一次点查询的IO开销将会是$O(L)$(leveling)或$O(T\cdot L)$(tiering)。然而，布隆过滤器能极大改进点查的开销。对于一个无结果的点查，例如说搜索一个不存在的key，所有磁盘IO都由布隆过滤器假阳性造成。假设所有布隆过滤器有M位，且在所有level上有同样的假阳性概率。对于N个key，每个布隆过滤器假阳性概率是$O(e^{-\frac{M}{N}})$。所以对于不存在的key，查询开销是$O(L\cdot e^{-\frac{M}{N}})$(leveling)和$O(T\cdot L\cdot e^{-\frac{m}{N}})$(tiering)。key存在且唯一时，至少需要一次I/O来获取条目，假设布隆过滤器误报率远小于1，那么成功的点查询的I/O成本都将是$O(1)$。

区间查询

区间查询的I/O代价取决于查询长度。设s是区间查询不同的键值数量，当$\frac{s}{B}>2\cdot L$时区间查询被认为是长的，此时I/O代价由最深的level决定，因为最深的level包含了大部分数据。否则为短查询，此时I/O代价来自所有level，因为查询必须向每个磁盘组件发出一个I/O。因此长范围查询的开销是$O(\frac{s}{B})$(leveling)和$O(T\cdot \frac{s}{B})$(tiering)。短范围开销是$O(L)$(leveling)和$O(T\cdot L)$(tiering)。

空间放大

空间放大的原因是一个键值可能存在于不同位置上，导致空间利用率下降，我们定义空间放大为条目总数除以唯一(unique)条目数量。对于leveling，最差的情况是前L-1个level上都有数据，这大概包括了$\frac{1}{T}$的总数据，这些数据都是对最大level中条目的更新造成的。所以最差情况下leveling的写放大是$O(\frac{T+1}{T})$。对于tiering，最差情况是最大层中的所有组件的key集合都完全相同，所以最差情况下tiering的空间放大是$O(T)$。

几种情况下Leveling和Tiering的代价开销可以总结如下表：

image-20220627125134196

Table 1

总体而言，leveling可以优化查询性能和空间利用率，但是组件必须更频繁地合并，导致更高的写入成本。同时由于布隆过滤器的优化，两者在点查询的代价上其实差距很小，但区间查询和空间利用率会受到显著影响。

在分区优化上的差异

虽然说分区与合并策略是正交的，也就是leveling和tiering两种分区策略都可以支持分区优化，但是分区优化的实现方式是不同的。目前似乎只有基于LSM-tree的工业存储系统（如LevelDB和RocksDB）完全实现了leveling策略下的分区，一些论文也提出了各种形式的tiering策略下的分区方法，以获得更好的写性能。

Leveling分区

在LevelDB首创的分区leveling合并策略中，每个level的磁盘组件被范围划分成多个固定大小的SSTable。如Fig 5所示，每个SSTable都有一个用来表示其key范围的标记。注意到level 0的磁盘组件没有分区，因为它们是直接从内存中刷下来的。这种设计可以帮助系统处理突发的写请求，因为level 0可以容忍多个未分区的组件。在合并过程中，我们将选取L+1里与被合并SSTable存在重叠的SSTable，并生成新的L+1层的SSTable。例如Fig 5中，标记为0-30的SSTable将和下一层0-15、16-32的SSTable合并，产生新的标记为0-10、11-19、20-32的SSTable，而原本的SSTable将被垃圾回收。可以使用不同的策略来选择接下来在每个Level合并哪个SSTable。例如，LevelDB使用循环策略（round-robin policy）以最小化总的写开销。

image-20220627172443097

Fig 5

Tiering分区

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

首先是Fig 6所示的垂直分组策略。这种策略下，有着重叠区间的SSTables会被分到同组，这样组间就有不相交的键区间了。在合并操作过程中，一组内的所有SSTable都会被合并，产生的SSTable的区间会根据下一层分组情况来。比如图中0-30、0-31这一组被合并了，由于下一层的分组情况，生成了0-12、17-31两个SSTable，并被添加入对应的组。请注意合并前后的状态不同，合并前，0-30、0-31有重叠的区间，所以当遇到一个点查询，这两个SSTable都要被查。但经过合并，0-12、17-31没有重叠区间，那就只有一个需要被点查询访问。并且这种设计下，SSTable不再是固定大小，而是取决于下一层的分组情况。

image-20220627174710049

Fig 6

再来看Fig 7所示的水平分组策略是怎样的。这种策略下，每一个组件都被按照区间分入了一个固定大小的SSTables的集合，直接作为一个逻辑上的组。每一组还会维护一个活跃组，也是第一个接受上一层被合并的SSTable的组。在未分区的情况下，这个活跃组可以看成是上一层被合并部分的组件。一次合并操作会选择那些有重叠区间的SSTables，并把生成的SSTable添加到下一层的活跃组。如图所示，第一层标记了35-70和35-65的SSTable被一起合并了，35-52和53-70被添加到第二层的第一个组。然而，尽管SSTable在水平分组下是固定大小的，一个SSTable仍然可能与其他组内的SSTables有大量的重叠区间。

image-20220627174739581

Fig 7

Dostoevsky：一种改进的合并方式

上面介绍的两种合并方式，简单来说，Leveling 会有写放大问题，而 Tiering 则会有读放大以及空间放大问题。为了更好地在空间和性能上平衡这些问题，提出了Dostoevsky方法，它并没有单纯的采用 Leveling 或者 Tiering，而是采用将两者结合的方式。

Lazy Leveling

Lazy Leveling混合了 Tiering 以及 Leveling，在最大层使用 Leveling，而其它层使用 Tiering。另外，因为小的 Level 现在使用的是 Tiering，为了加速点查，Dostoevsky 为不同的 Level 的 Bloom filter 使用了不同的内存。

image-20220627181545752

Fig 8

Lazy Leveling相较于Leveling，主要达到做到了以下三点：

  1. 降低了更新的开销
  2. 在点查询、长区间查询和空间利用率维持原有的性能优势
  3. 在短查询上的性能效果仍然保持良好

Fluid LSM-Tree

在 Lazy Leveling基础上面，Dostoevsky引入了Fluid LSM-Tree，相比于Lazy Leveling最大层是Leveling，其它层是 Tiering，Fluid使用了一个可调解的方式，在最大层使用最多Z runs，而其它层最多使用K runs。

这里引入了runs的概念，runs就是一个或者多个有序不重叠的SSTable文件。从Level 1层开始，Leveling 的runs就是 1，而Tiering则可能是T-1。

可以发现：

  1. Z = 1， K = 1，就是 Leveled Compaction
  2. Z = T - 1， K = T - 1，就是 Tiered Compaction
  3. Z = 1， K = T - 1，就是 Lazy Leveling

image-20220627182409229

Fig 9

Fig 9 是使用Fluid模型之后不同case的开销，但这里的代价分析更加复杂。很难通过分析和计算的方式去确定 Z 和 K，这一部分似乎只能通过tuning，也就是不断调整 Z，K 和 T，在不同的应用场景去测试，从而找到一个比较优的配置。

合并方式的未来研究方向

分区tiering结构

Tiering已经被许多LSM树改进，以减少LSM树的写放大。本文讨论了两种可能的分区tiering方案，即水平分组和垂直分组，这基本已覆盖了所有tiering分组方案。然而，这两种方案的性能特点和权衡尚不清楚。一般来说，垂直分组在选择合并SSTable时具有更大的自由度，而水平分组则确保SSTable的大小是固定的。系统地评价这两种方案，并可能设计出结合两者优点的新方案，是今后的一个研究方向。

混合合并策略

大多数LSM树的改进都假定在LSM树的所有级别上采用同样的合并策略。然而，在某些工作负载下这被证明是次优的。leveling和tiering的混合合并策略可以提供比leveling更好的写性能，并且对点查找、长距离查询和空间放大的影响最小。本文给出了一种混合合并策略，即Dostoevsky方法，但进一步设计和实现这种带有混合合并策略的LSM树，并分析因此而产生的新问题将是一个未来的研究方向。

结论

LSM-tree在现代NoSQL系统中越来越受欢迎，因为它具有超强的写性能、高空间利用率、磁盘上数据的不变性和可调性等优点。这些因素使得LSM树能够被广泛采用和部署，以服务于各种工作负载。

本文中对LSM-tree的基本概念进行了解和回顾，并在LSM-tree的一个核心问题：合并方式上进行了深入的了解，回顾已有的研究工作，介绍了Leveling、Tiering和Dostoevsky等合并方法，并从代价的角度分析不同操作上的开销，并介绍不同操作的开销之间如何权衡。并在本文的最后讨论了更改分区tiering结构和混合合并策略的两种未来研究方向。

参考

  1. Chen Luo · Michael J. Carey: LSM-based Storage Techniques: A Survey

  2. Dayan, N., Idreos, S.: Dostoevsky: Better space-time trade-offs for LSM-tree based key-value stores via adaptive removal of superfluous merging. In: ACM SIGMOD, pp. 505–520 (2018)

  3. WIPIPEDIA: Log-structured merge-tree
  4. LevelDB documents: https://github.com/google/leveldb/blob/main/doc/impl.md
  5. RocksDB Leveled-Compaction: https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
  6. ScyllaDB’s Compaction Strategies Series: Space Amplification in Size-Tiered Compaction: https://www.scylladb.com/2018/01/17/compaction-series-space-amplification/