compaction策略
compaction的主要作用是数据的gc和归并排序，是lsm-tree系统正常运转必须要做的操作，但是compaction任务运行期间会带来很大的资源开销，压缩/解压缩、数据拷贝和compare消耗大量cpu，读写数据引起disk I/O。compaction策略约束了lsm-tree的形状，决定哪些文件需要合并、任务的大小和触发的条件，不同的策略对读写放大、空间放大和临时空间的大小有不同的影响，一般系统会支持不同的策略并配有多个调整参数，可根据不同的应用场景选取更合适的方式。
基础概念
读放大
每次读请求带来的读盘次数
写放大
每写1byte数据带来n bytes的数据写盘，写放大为n。本质上写放大需要跟全局有序做权衡，对序要求越高的系统写放大就会越严重，B-Tree系列是随时有序的代表，写放大也更为严重，而LSM-Tree将序延迟到后台compaction处理，减少了写入放大。再近一步优化和权衡，lsm-tree系统下不同的compaction策略也会带来不同的放大结果。
空间放大
所占空间大小/实际数据量大小，空间放大主要与未回收的过期数据量(old version/deleted entries)相关。传统数据库使用廉价磁盘，空间放大并未作为主要考虑，在以ssd为主流存储介质的今天，节省成本是不得不做的事情。
临时空间
compaction任务运行时需要临时空间，compaction完成后旧数据才可以删除。与compaction任务的拆分粒度相关。
sstable
ordered string table
有些系统使用了不同的名字，都是类似的含义，这里介绍策略时统一使用sstable来描述。
Size-tired compaction
size-tired适合write-intensive workload，有较低的写放大，缺点是读放大和空间放大较高。简单看一下这个策略的实现，如下图所示(图来自scylla)，memtable周期地刷到sstable，可以看作每层之中有多个ordered runs，最底层是最大的一层，tiered尽量使得相同层的sstable/run大小相近，当一层的数据size达限制后将整层合并并flush到下一层成为一个更大的sstable，一直合并直到某一层数量未达到限制停止。
tired的缺点是空间放大和读放大:
- 对于读操作，这里忽略cache和bloom filter等上层优化，大部分的点读按数据量来推测是会落在最大一层的，而range查询需要合并所有层的结果，runs越多，读放大越严重。Dostoevsky这篇论文详细分析了point lookup(考虑bloom filter)、short和long range lookup的I/O cost，具体可参照下文Dostoevsky部分。
- 如果重复的写同一批数据，可能是更新或者删除，假设相邻level的size比为T，每个level包含的run数达到T时即触发整层的合并，空间放大为O(T)，实际运行中还要考虑临时空间的使用，需要预留出这部分空间。在scylla的测试中，T为4的设定中1.2g数据量最大使用空间达到了9.3g，可见tiered策略对空间的要求是比较苛刻的。
leveled compaction
leveled策略可以减小空间放大和读放大。
LSM-Tree由多个level组成，每个level的size维持上一个level的T倍，当所有相邻level的size比T是相同值的时候写放大最小。
如下这张图所示，leveled每层由多个sstable组成一个有序的的run，sstables之间互相也保持有序的关系，每层的数据size到达上限后与下一层的run merge。这种方式将level的多个run降为一个，减小了读放大和空间放大，小sstable的方式提供了精细化任务拆分和控制的条件，控制任务大小也就是控制临时空间的大小。
在相邻level数据量比设定为10的场景下，在largest level数据量足够满的情况下，worst-case:其它level都是update最大层的entries，其它level总数据量/bottom数据量大约是0.11，空间放大为11%。即便在largest level不足够满，未能达到数据量比例时，最差也只有1倍的空间放大，相比tiered的T倍(相邻level size比)空间放大，leveled就比较有优势了，适合读多写少的场景。
leveled策略的问题是写放大，同样分析相邻level数据量比为10的设定下worst-case，level a层的数据与level a+1层的所有数据都有交叠，level a向下合并时涉及level a+1全量的数据，共有原数据11倍大小的数据量被写盘，写放大为tired的11倍。这是理论上最差的情况，随机写非常多的场景会更接近这个数值。一般情况新写入的数据短时间再次被更新的概率会比较大，符合时间局部性，这种情况由于旧版本数据被合并掉总数据量几乎不变，不会触发向下合并。
Hybrid
tiered和leveled混合的方式。很多系统使用两者混合的方式以取得读写放大、空间放大之间进一步的权衡。相比tiered可以获得更少的空间放大和读放大，相比leveled可以有更少的写放大。
time series
一般time-series数据的特点如下：
- 索引key和写入时间相关
- 数据按照时间顺序写入，只有少量数据不遵守这个顺序
- 数据只能通过TTL或者删除整个partion来删除
- 数据写入的速度几乎是恒定的
- 数据查询通常是在一个特定的partition中的，例如"values from the last hour/day/week"
因此针对这些特点，很多系统引入了特定的compaction策略来提升性能，每个sstable有开始和结束时间标记，挑选sstable时按照时间range，相似range的sstable逐渐合并，越老的sstable range越大，sstable之间几乎没有时间range交叠，这样应对特定时间filter的查询能够有效地挑选对应的sstables。
key-value stores in industry
每个系统都是围绕着"how and when"这个主旨来选择策略和调度机制的，如何挑选文件，由什么条件触发。
偏向写优化的系统，bigtable、hbase、canssdra。偏向空间优化和读优化的系统，rocksdb。
rocksdb
rocksdb在compaction机制上支持的方式比较多，也做了很多的优化工作，除了经典的tiered和leveled之外，rocksdb在两者基础之上可以有两种混合方式的表现，定义为leveled-N和tiered+leveled。
leveled
rocksdb的leveled compaction实现实际上是结合了tiered，level0是tiered的实现方式，除L0层外其它都是leveled。level0的每个run由一次flush memtables得来，多个run之间范围有交叠，其它levels由多个sstables组成一个有序的run。这种结合方式的好处一是减小了写入放大，二是可以在写入负载较高时快速释放memtable以缓解内存的压力。leveled是rocksdb默认的compaction方式。
tiered(Universal)
tiered在最大层维护全量的N份副本会带来N倍的空间放大，rocksdb增加了参数来限制最差的空间放大，最多只允许最大层有K个runs，K的范围是2～N。
tiered在rocksdb中是依赖Universal Compaction来实现的，用户使用leveled无法应对高写入的速率时可以尝试使用Universal Style。
leveled-n
leveled-n是leveled优化了写放大的实现方式，允许每层有多个有序的runs，compaction时merge L-1层的所有runs和Ln的一个sort run，Dostoevsky中提出的lazying compaction也是类似的思想，本质上是通过调整最大层run的数量和相邻level的size比T来平衡读写放大和空间放大。
tiered+leveled
tiered+leveled属于Hybrid方式，允许Lk层是tiered方式，Ln层是leveled方式(n > k)，rocksdb在这种方式的表现形式是memtable会保留多个和level0层允许有多个run，可以看作内存层和level0层是tiered，1-n层是leveled，不过内存中不做合并，可能只将level 0标为tiered更合适。
scylla
scylla支持tired、leveled compaction策略，默认为Size-tired compaction，面向写优化场景。并增加了size-tired优化版本incremental compaction和针对时间特定场景的date-tired compaction。
incremental compaction(IC)
针对size-tired临时空间放大问题提出的优化版本，原始的size-tired中每个sstable是一个有序的文件，多个sstable合并成为更大的sstable，至少需要预留50%的临时空间。IC将sstable分为多个分片(默认1G)，以分片为合并单位增量地进行，合并完成的分片可以将旧数据的空间释放出来，降低了临时空间放大。
Time-window compaction(TWCS)
scylla最开始支持了date-tiered，最初由canssdra实现并使用，TWCS是date-tiered的替换版本，同一时间窗口的sstables按照tiered策略合并，不同时间窗口的sstable不会在一起合并。都属于time series，time场景下优化读性能。
hbase
hbase的compaction类型分为minor和major两种，与bigtable类似，minor挑选部分store files合并，数据量少而频繁，不回收多版本数据(避免处理一些相同key的问题)。major将所有store files合并为一个，major涉及数据量比较大，一般很久才会触发(天级别)或者手动触发，major会处理过期数据。
hbase的store files与sstable是类似的概念，hbase弱化了层次的概念，每个file是一个有序的run，hbase在0.94和0.96两个版本中分别提出两种挑选合并文件的策略:RatioBasedCompactionPolicy，ExploringCompactionPolicy。RatioBased从老到新扫描未在合并队列中的store files直到满足合并大小(依赖ratio参数)，总是优先合并老的store files，Exploring会扫描所有的未在合并队列中的store files，在多个满足条件(ratio)的集合中选择总size最小的，以尽可能减少io的消耗。分类上这两种策略都属于tiered compaction。hbase也支持date-tiered compaction。
在hbase-2.0.0中，提出了in-memory compaction的新特性。本质上是为了减少flush的频率进而减少compaction，减少写放大，适合重复更新热点数据的场景，过期版本数据可以在内存中就被消除。对于大多都是unique的写场景反而会带来性能下降，因为compaction要消耗cpu资源。
挑战
compaction任务执行对性能造成显著影响，主要表现在两方面：compaction过程中对io/cpu资源的消耗，compaction完成时造成批量的cache失效。另外一个在lsm-tree这种结构下存在的比较棘手的问题是需要delete的记录不能立刻被消除，要消除的记录可能会存在每一层，需要通过全量的compaction才能消除，这对资源是非常大的消耗。
资源消耗
任务运行时的压缩/解压缩、拷贝、compare消耗cpu资源，读写数据消耗i/o资源。
cache失效
compaction完成生效时旧数据文件失效，cache中的数据同样也会失效，compaction任务越大数据越热，cache失效越严重。cache miss率升高引起大量的读i/o，读i/o请求与compaction任务执行时读文件请求之间进一步争抢资源，加剧读性能的降低。
delete entries
- 在lsm-tree中，delete/update都是写一条新的记录，delete记录一般使用一位flag来区分，delete记录堆积会带来更多的空间放大和写放大，更为严重的是在range delete场景下，读性能会受到很大影响。而目前系统消除delete的方式需要触发全量的compaction，带来过多的资源消耗，这是一种非常贵的解决方式。rocksdb实现了根据delete 记录的分布来挑选文件来合并的优化方式，以达到消除delete和相关记录的目的，这样可以避免一些多余的数据合并，是一种优化手段，但是对于delete广泛分布在各个文件中的情况依然无法避免全量的compaction。
- 对统计信息的影响，如果是用在关系型数据库中，例如myrocks，会导致统计信息不准影响sql优化器的决策。
- Lethe论文中还提到带来侵犯隐私的风险，用户要求删除的数据没有在一定时间内物理删除，甚至在用户注销后数据还存在，会引起法律风险。
学术研究
分布式kv store的compaction管理
这篇论文(参考1)提出在分布式kv store中，使用offload compaction到单独的server和增量cache回填的方式来解决compaction对资源消耗和cache失效的问题。实现和评估基于hbase，hbase是由bigtable衍生，基本架构与bigtable非常相似，使用zookeeper保持一致性，按照key range将数据水平切分到多个region server，数据持久化在hdfs中，region server中维护memstore接收新的数据写入，block cache缓存hdfs中的数据文件。
offload compaction
在hbase的架构中，增加两个新的组件：compaction manager，compaction servers集合。compaction server可动态增加或者减少，与region server一样从hdfs中读取数据，合并完成再写入hdfs。compaction manager与hbase master类似，管理compaction server的集合和从region server到compaction server的映射。region server的compaction任务offload到compaction server上，接收合并完的数据用于缓存的预热。
remote cache
region server中的compaction offload到remote server后，compaction的数据可以同步填充到remote server的内存中，对于这部分数据的访问请求可以选择访问本地的disk和远程server的内存，其实是disk i/o与网络i/o之间的比对，测试效果一般，没有很明显的改善。
smart cache
访问远程cache并没有达到很好的效果，因此作者又提出使用远程cache增量预热本地cache的方式。按照key range增量地填充并淘汰对应key range的旧数据，这样不会造成大批量的原本在caceh中的数据被淘汰。对于请求的数据，要么落在旧的cache中，要么落在新填充的cache中，很小的概率是属于刚被淘汰而还未被填充的数据范围。因此这种方式效果测试很好，几乎没有cache miss。
分布式场景下可以从外部方式来解决compaction带来的问题，这是单机系统做不到的，像smart cache这种解决方式，在单机中无法同时在内存中保存新旧两份数据，避免不了性能的抖动，而在分布式场景下，利用远程的内存保存新的数据并一点点地替换掉本地的cache，而compaction前后的数据对于读请求返回的是一致的结果，因此这种方式可以保证正确性，也达到了很好的效果。
PebblesDB
这篇论文(参考2)提出了一种LSM Tree的改良结构叫做FLSM，主要目的是通过减少compaction过程中的rewrite来减小写放大，并使用FLSM构建了高性能kv store，叫做PebblesDB。FLSM的设计思想来源于skip list和lsm-tree的结合，写放大的本质来源于compaction过程中数据的rewrite，写放大会减少像SSD这种有擦写次数限制设备的寿命，增大存储代价，降低写吞吐。FLSM通过加入guard将数据分成互不相交的单元，每个单元包含多个range交叠的sstables，在将level i合并到level i+1时，相比于重写level i+1的sstables，FLSM只是将根据guards新划分的sstable放到level i+1，并不会与level i+1的sstables做merge。这不仅减小了写放大，也加快了compaction的速度。但是会对读产生一定影响，作者也提出了优化读的方式：Seek-Based Compaction用seek()次数作为触发compaction的条件，减少热guard内的sstabels的数量，从而减少read的开销；Parallel Seeks，使用多个线程并行search sstables，每个线程读一个sstable，再将结果merge起来。这样即使在一个guard中有多个sstables，也只需要付出一小部分overhead。
guards的信息保存在内存中，与LSM的元信息一样，写wal日志，crash后可以通过manifest日志保证数据不丢失。
用guard来分区和seek-based compaction是比较新颖的点，FLSM的确可以减小写放大，但带来的read问题我认为并没有解决，并行seek受限太多。seek-based compaction感觉倒是可以继续优化的一个点，读请求很多时候反映了数据的冷热以及需要合并的紧迫程度，这部分如果能够更精准的判断将对于"做有效的合并"带来很大帮助。
Dostoevsky
这篇论文(参考3)详细地分析了各种操作在tired和leveled不同策略下的i/o复杂度，使用了level num、相邻level size比、entry数量、buffer size等一系列相关变量推导出不同操作具体的I/O代价公式和空间放大，对于point read还考虑了bloom filter带来的影响，range query分了short和long两种来分析。并且提出了优化策略lazying leveling，是tiering和leveling的结合体，最大一层使用leveling其它层使用tiering，lazying适合包含update、point lookup和long range lookup的混合负载，tiering适合大多为update的负载，leveling适合大多为lookup的负载。通过控制merge频率在tiering、leveling和lazying leveling几种不同策略下转换以适应不同的workload，称作fluid LSM((类似rocksdb的leveled-n))，并提出Dostoevsky，在执行期间动态计算最优配置以到达最大吞吐。
从作者的分析中可以看出compaction这个机制的复杂程度，要使用一套通用机制在不同场景下消耗最少的资源带来最好的性能基本是不可能的，实际工业界实现中需要考虑更多的因素(cache、delete、任务拆分粒度、复用技术等)，因此大部分系统使用多种策略多个参数用以适配不同场景。
详细解析
一点思考
compaction的代价在单机中是不可避免的，但不同的策略会带来不同的读写和空间放大，也是近几年学术上关于lsm-tree系统研究的一个方向，重点在于如何从策略选择上优化worst-case。大多数系统支持多种compaction实现策略，通过适配多种不同参数以满足不同业务场景下的需求，这也是不断完善的一个过程，遇到问题解决问题，大多数时候可以work，但不可避免的会遇到复杂场景、多种混合负载下的极端问题，依赖调参数或者人工操作compaction来解决总是不那么优雅和及时。在分布式场景下可以将策略当作黑盒，很多问题可以依靠外部资源来化解，更多的是依赖调度策略。
在真实应用中，大多数业务负载并不会持续让系统处于worst-case中，而大费周折去解决worst-case是否不是那么必要？例如选择一种"绕"的方式来让系统处于更平稳的状态，低峰期承担更多任务以卸掉低level的重担，空车以迎接高峰时期的洪荒之力，当然这也只是一种理想状态，事实总比预想要复杂，总是不会完全按照预期的走向发展，这使得我们没有办法按照一些规则或者配置来做预先处理。可以想到需要引入调度控制，重心由合并策略转向调度策略，根据负载曲线调度不同任务以达到不同时期对资源的需求，这或许是更为复杂的一个话题，也希望会有更多这个方向上的研究和探索出现。
参考：
1.https://www.scylladb.com/2016/08/30/date-tiered-compaction-strategy/
2.Compaction management in distributed key-value datastores
3.PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees
4.Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging
5.Lethe: A Tunable Delete-Aware LSM Engine
6.https://github.com/facebook/rocksdb/wiki/Compaction
7.https://smalldatum.blogspot.com/2018/08/name-that-compaction-algorithm.html
8.http://smalldatum.blogspot.com/2015/11/read-write-space-amplification-b-tree.html
