LevelDB之Leveled-Compaction

LevelDB之Leveled-Compaction

LevelDB是Google开发的一款高性能存储引擎，它采用LSM（Log-Structured Merge-Tree）模型来优化读写性能。本文将深入探讨LevelDB中Leveled-Compaction的原理和实现细节，并通过与Size-Tired Compaction的对比，帮助读者理解不同合并策略的优劣。

一、前言

LevelDB是Google出品的具有读写高性能的存储引擎，其没有采用传统的B+ Tree（MySQL InnoDB）的存储模型，而是使用了LSM（Log Structure Merge-Tree)。LSM模型中的一个重要组成就是称作SSTable（Sorted String Table）的结构。本文先简单介绍LSM中使用的几种结构，然后着重介绍在众多Compaction算法中的Leveled-Compaction。

二、LSM

LSM是通过将磁盘的随机写改为顺序写来提高写的性能，核心思想是把数据的添加或修改放到内存中，当内存中数据达到一定size后，然后dump（也就是变成了顺序写）到磁盘中。LSM中有MemTable、ImmutableMemTable、SSTable等几个概念，下面分别介绍

1、MemTable

MemTable在内存中，记录最近修改的数据。一般其内部使用SkipList结构存储按key排序后的有序数据，当其存储的数据达到一定size后，就变成ImmutableMemTable，同时新建一个新的MemTable；后续的数据修改操作均在新的MemTable内进行。

2、ImmutableMemTable

ImmutableMemTable就是只读不写的MemTable，它与MemTable一起保证的写操作无锁化。其内部的数据是有序的，所以dump到磁盘时保证了高效的顺序写，形成了新的SSTable文件。

3、SSTable

SSTable内存储的是一系列的有序键值对，形式如下图所示。当SSTable文件较大时，为了提高读的性能，也可以生成key-offset索引，此索引一般都记录在内存中。

4、SSTable Compaction

由于不断有ImmutableMemTable会dump到磁盘中成为新的SSTable文件，所以SSTable文件的数量会逐渐增多，其内部存储的数据也会产生很多过期数据（key的旧数据），所以需要对SSTable文件进行定期Compaction，一方面减少SSTable文件的数量，同时也删除过期的数据。

SSTable Compaction有多种算法，比如Cassandra默认的基于文件大小的Size-Tired Compaction、基于时间序列的Date-Tiered Compaction，以及Leveled Compaction。

这里主要以Cassandra中的Leveled Compaction算法为例来分析（这也是LevelDB名字的由来）。

Leveled Compaction

SSTable被划分到不同的level中，详细的Leveled Compaction算法描述如下：

• 每个SSTable文件的固定大小为160M
• 从ImmutableMemTable创建的SSTable文件划分到Level-0中
• 每个Level有SSTable文件数量的限制。在除了Level-0的任意Level中，两级Level之间的SSTable文件数量呈指数级倍数。比如：Level-1中有10个SSTable文件，Level-2有100个SSTable文件
• 在除了Level-0的任意Level中，SSTable文件之间所包含的key的范围不重叠。（也就是说，每个Level的所有SSTable文件，可以看做是一个大的SSTable文件）
• 如果Level-0中SSTable数量超过限制（比如：4），那么自动回将这4个Level-0的SSTable文件与Level-1的所有10个SSTable文件进行Compaction。（这里需要特别注意：level-0比较特殊，各个SSTable之间是有重叠的，所以只能将4个SSTable与Level1中所有进行整体上的Merge和切分（如原博客所述）。但level-1及其以上，各个SSTable之间没有重叠key，当SSTable个数超过阈值时，可以只选择一个或者多个SSTable与下一level值域对应的SSTable进行合并，由于每一级的SSTable大小相同，可以有效避免写放大）
• 在Compaction过程中，首先对所有的SSTable文件按key进行归并排序，然后将排序后结果写入到新的SSTable文件中，如果SSTable文件大小到了160M上限，就新生成SSTable继续写。如此类推，直到写完所有数据。
• 删除参与Compaction的Level-0的4个和Level-1的10个旧的SSTable文件
• 此时Level-0的SSTable便merge到Level-1中了，那么如果Level-1的SSTable文件数量超过上限，那么就从Level-1中选出 1 个超量的SSTable文件，然后将其与Level-2中的SSTable文件进行Compaction。
• 查看选出的Level-1 SSTable文件中key的范围
• 从Level-2中选出能覆盖该范围的所有SSTable文件
• 将以上的所有SSTable文件根据上面介绍的算法继续进行Compaction
  注：一般情况下，Level-1和Level-2的Compaction，只会涉及Level-2内大概1/10的SSTable文件，这样可以大幅降低参与Compcation的SSTable文件数量（相比于Size-Tired Compaction），进一步提升提升性能
• 如果Level-2中的文件数量超过限制，则继续按照上述算法选出超量的SSTable文件与Level-3中的SSTable文件进行Compaction

三、RockDB的合并策略图解

1、 L0 compaction

当L0的文件数量达到level0_file_num_compaction_trigger的值时，触发L0和L1的合并。通常必须将所有L0的文件合并到L1中，因为L0的文件的key是有交叠的(overlapping)。

L0与L1的compaction

2、 高层Compaction

当L0 compaction完成后，L1的文件总size或者文件数量可能会超过阈值，触发L1向L2的合并。从L1至少选择一个文件，合并到L2中key有交叠的文件中。

L1向L2合并

同样的，合并后可能会触发下一各level的compaction。

合并后的L2

L2向L3合并

合并后的L3也需要做Compaction.

合并后的L3

3、 并行Compaction

并行compaction

max_background_compactions控制了并行compaction的最大数量。

四、size-tired和level合并策略比较

上文已经提到，我们需要对
SSTables
做合并：将多个
SSTable
文件合并成一个
SSTable
文件，并对同一个key，只保留最新的值。

那这里讨论的合并策略（Compaction Strategy）又是什么呢？

A compaction strategy is what determines which of the sstables will be compacted, and when.

也就是说，合并策略是指：1）选择什么时候做合并；2）哪些
SSTable
会合并成一个
SSTable
。

目前广泛应用的策略有两种：
size-tiered
策略和
leveled
策略。

• HBase采用的是
  size-tiered
  策略。
• LevelDB和RocksDB采用的是
  leveled
  策略。
• Cassandra两种策略都支持。

这里简要介绍下两种策略的基本原理。后面研究
LevelDB
源码时再详细描述
leveled
策略。

size-tiered
策略

简称STCS（Size-Tiered Compaction Strategy）。其基本原理是，每当某个尺寸的
SSTable
数量达到既定个数时，合并成一个大的
SSTable
，如下图所示：

它的优点是比较直观，实现简单，但是缺点是合并时的空间放大效应（Space Amplification）比较严重，具体请参考Scylla’s Compaction Strategies Series: Space Amplification in Size-Tiered Compaction。

空间放大效应，比如说数据本身只占用2GB，但是在合并时需要有额外的8G空间才能完成合并，那空间放大就是4倍。

leveled
策略

STCS
策略之所以有严重的空间放大问题，主要是因为它需要将所有SSTable文件合并成一个文件，只有在合并完成后才能删除小的SSTable文件。那如果我们可以每次只处理小部分
SSTable
文件，就可以大大改善空间放大问题了。

leveled
策略，简称LCS（Leveled Compaction Strategy），核心思想就是将数据分成互不重叠的一系列固定大小（例如 2 MB）的
SSTable
文件，再将其分层（level）管理。对每个
Level
，我们都有一份清单文件记录着当前
Level
内每个
SSTable
文件存储的key的范围。

Level和Level的区别在于它所保存的
SSTable
文件的最大数量：
Level-L
最多只能保存10 L个
SSTable
文件（但是
Level 0
是个例外，后面再说）。

注：上图中，"run of"就表示一个系列，这些文件互不重叠，共同组成该
level
的所有数据。

Level 1
有10个文件；
Level 2
有100个文件；依此类推。

下面对照着上图再详细描述下
LCS
压缩策略：

先来看一下当
Level >= 1
时的合并策略。以
Level 1
为例，当
Level 1
的
SSTable
数量超过10个时，我们将多余的
SSTable
转存到
Level-2
。为了不破坏
Level-2
本身的互不重叠性，我们需要将
Level-2
内与这些待转存的
SSTable
有重叠的
SSTable
挑出来，然后将这些
SSTable
文件重新合并去重，形成新的一组
SSTable
文件。如果这组新的
SSTable
文件导致
Level-2
的总文件数量超过100个，再将多余的文件按照同样的规则转存到
Level-3
。

再来看看
Level 0
。
Level 0
的
SSTable
文件是直接从
memtable
转化来的：你没法保证这些
SSTable
互不重叠。所以，我们规定
Level 0
数量不能超过4个：当达到4个时，我们将这4个文件一起处理：合并去重，形成一组互不重叠的
SSTable
文件，再将其按照上一段描述的策略转存到
Level 1
。