LevelDB之Leveled-Compaction
https://github.com/imjoey/blog/issues/6
https://www.jianshu.com/p/99cc0df8ed21
https://juejin.im/post/5c99f0556fb9a070e82c1fcf
目录
一、前言
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。