MyBlog
LSM-Tree Compaction 之 STCS, LCS
last modified: 2021-03-14 14:43
一、读放大，空间放大问题
读放大
MemTable持续Flush成SSTable，SSTable数量持续增长，读操作需要从新到旧查找不同SStable，即产生读放大问题：一次Query产生多次磁盘I/O。
空间放大
LSM-Tree使用append模式写数据，没有in-place update，所以同一条数据可能存在于多个SSTables中，同时删除数据使用墓碑机制， 删除的数据仍旧保留在磁盘，即产生空间放大。
二、读、空间放大优化及写放大问题
写放大
LSM-Tree使用了Compaction机制，周期性将SSTable进行Compact，使SSTable数量下降。这样1）使数据量变少（合并Update，删除Delete数据），缓解空间放大问题。 2）使用SSTable个数变少，Query所需查询的次数变少，缓解读放大问题。
但Compaction过程遍历SSTable文件，内存归并完成后回写磁盘，产生了新的写放大问题。
在SSD盘上，写放大问题相比传统HDD盘更加突出，因为
1）SSD写数据都要先擦除再写入，其平均擦写数有上限，写放大降低了其使用寿命
2）相比于HDD，SSD上顺序写比起随机写的效率提升并没有那明显，顺序写还来的性能提升能否抵消写放大带来的开销，也是一个问题
所有的Compaction机制，都是在读放大，空间放大和写放大之间做取舍。Cassandra, RocksDB等基于LSM-Tree实现的数据存储， 都提供不同的Compaction策略，供业务根据实际场景进行选择。
下面将总结常见的Compaction策略，分析其优劣。
三、Compaction策略及优劣比较
3.1 Size-Tiered Compaction Strategy(STCS)
Size-Tiered是Cassandra等的默认Compaction策略。其原理非常简单，MemTable会周期性的Flush成SSTable， 因此产生了大量的Small SSTables（50M default in cassandra）。
当Small SSTables达到一定数量（Default 4），Small SSTable被Compact为一个Medium Table。依次的Medium被合为Large，Large最终被合为Huge，如下图所示，
实际生产的STCS实现稍微复杂一些，因为SSTables间的数据重叠，Compact后得到的SSTables大小不一。根据大小被分到不同的Bucket，每个Bucket有一个 独立Processor负责处理。Size Tiered Compaction Strategy In Apache Cassandra
Size-Tiered Compaction会产生非常少的，约对数量级的SSTables，但其最大的问题在于空间放大。
Facebook的一个研究表明，在SSD流行的今天，磁盘空间已成为Facebook最主要的资源瓶颈。Optimizing Space Amplification in RocksDB
storage space is most often the primary bottleneck when using Flash SSDs under typical production workloads at Facebook
STCS的空间放大问题多严重呢，scylladb做过2个实验，
实验一：Write-only workload
实验过程：以10K（大约占用3M磁盘） QPS的速度，在单节点，单Shard上写入30 Million数据
图中可以看出，数据以约3M每秒速度写入，在125, 250和375秒处发生Small->Medium Compaction，在500秒处发生Medium->Large Compaction，在2000秒处 发生Large->Huge的Compaction。
Compaction发生时，磁盘使用量会上升，因为Compact过程中，旧SSTables不能删除，直到新的Compact后的SSTable生成完毕。 实验可以看到，在某个点（2000秒处），当我们需要Compact所有SSTables时，产生了2倍的空间放大。
然而，这不是最糟糕的情况。
实验二：Overwrite large SSTables
当我们Update已经存在于Huge SSTables中的数据时，新的数据依次途经Small->Medium->Large->Huge SSTables，产生了4倍的空间放大。再加上实验一中的 Compaction导致的放大，总共有5倍空间放大。
更糟糕的是，更新的数据不一定存在4份，在Small tiers的数据还可能有多份，进一步加剧了空间放大。
实验过程：重复15次，每次写入相同的4 Million数据，来模拟数据Overwrite的情况。
可以看到，最终数据量仅为1.2G，但过程中磁盘最高占用达到9.3G，产生了8倍的空间放大。过程中多次达到峰值，并且长期维持了3倍的空间放大水平上。
3.2 Leveled Compaction Strategy(LCS)
Cassandra 2011年在v1.0版本中引入了Leveled Compaction，它的设计来自于Google的LevelDB。
Leveled Compaction做的第一件事情就是消除大SSTable的Compact，它引入了”run”的概念，每个run包含一组小的（默认160M）、fixed-sized的SSTables （在Level Compaction中这些Fixed-sized SSTables叫作fragments）。
一个run中的SSTables之间不存在重叠的token ranges. 使用run带来的好处是，它将大的SSTable拆解， 在做Compaction时，无需整个大SSTable的Compact，而只要按需做部分Fixed-sized SSTable的Compact。
Leveled Compaction将Small SSTables划分为Levels，每个Level的所有SSTables构成run：
Level 0 (L0) 包含的是最新从MemTables Flush来的SSTables，当它们的数量增长时，将被从L0层移走到下一层。
Leveled Compaction中，每一层是一个run，其包含的SSTable数逐层递增，比如L1是一个包含10个SSTables的run，L2是一个包含100个SSTables的run， L3是一个包含1000个SSTables的run，以此类推。（Cassandra中默认的Level间倍数因子是10）
Leveled Compaction的目标是让L0层为空：
当产生了足够的L0 SSTables(e.g., 4)，我们将它们Compact到L1.
- 过程是，Compact L0与L1的所有SSTables，并按fixed-size进行切分（160M），替换L1的所有SSTables形成新的run。
L1的SSTables个数有可能超过上限(10 SSTables)，这种情况下，我们选择一个L1的SSTable，将它Compact到L2.
- 这个SSTable是L1 run中10个SSTables之一，因此占据了整个run 1/10的token range。同时L2中的一个SSTable占据了整个L2 run 1/100的token range。 因此我们要Compact的L1 SSTable，大约会与L2的10个SSTable存在数据重叠。
- 我们要做的是，将L1的一个SSTable，和L2中与这一个SSTable存在数据重叠的10个SSTables进行Compact。合并后的数据切分为Fixed-sized SSTable， 然后将L2输入的SSTables替换为Compact后的SSTables，将L1被pick出的一个SSTable删除。
完成L1 Compact到L2后，L2亦可能超过Desired SSTable数（100个SSTables），则继续从L2选一个SSTable，从L3选约10个SSTables，继续2过程。
And so on.
分析下LCS的空间放大，LCS不再做大SSTable的Compaction，只做约11个Fixed-sized SSTable的合并（11 * 160M），不到2G的常量级空间占用。
LCS仍存在重复数据的问题，LCS最好的情况是最后一个Level是满的。比如最后一Level是L3，有1000个SSTables，因为这是一个run，所以不存在重叠的 token range，这种情况下，假设L2 100个SSTables，和L1 10个SSTables都与L3数据重叠，则会产生1.11倍（1110/1000）的空间放大。
LCS在最坏情况下，如L3只有100个SSTables，L2的100个SSTables和L1的10个SSTables都与L3重叠，则产生2.1倍（210/100）空间放大。但比起STCS最坏8倍的空间放大，其表现依旧出色。 （Optimizing Space Amplification in RocksDB 这篇论文介绍了针对LCS最坏情况的优化）
对比STCS的两个空间放大实验，LCS的表现，
LCS很好解决了空间放大问题，但却带来了另一个写放大问题。
在STCS实验一中磁盘最终占用8.8G，但过程中监测写入了50G数据。（ScyllaDB实验数据）也就是STCS产生了大约5倍的写放大，分析其写放大来源于：一次commit log，4层tier写。STCS的写放大与tier层数相关，也就是O(logN)的复杂度。
但在LCS中，写放大问题尤为严重，上述对比实验一共监测到110G的数据写入，即大约有13倍的写放大。下面分析LCS的写放大来源，
不管是STCS的Tier，还是LCS的Level，都存在数据从第一层到最底层的Tier或Level的数据Copy，但是两者亦存在不同，
STCS选取该Tier的所有SSTables进行Compact（e.g., 4）如X bytes，并产生X bytes写入（假设没有Overwrite的最坏情况）
LCS选取一个SSTable，X bytes。接着选取下一Level的10个SSTables。Compact后产生11 * X的写入
因此最坏情况下，LCS写放大问题是STCS的11倍。所有写放大问题，本质上都是数据有序的要求引起的。
但不是所有Workload都会发生上述最坏的情况，比如在一些Write-heavy的Workload：很少有Cold数据的访问， 且大多数的Write数据都会在近期被更新。这种场景下Compact大部分发生在L0和L1，因为大量的Update/Delete在Low Level已被合并，SSTables数不会增长， 也就不会产生11倍的写放大问题。