深入探讨 LSM Compaction 机制

简介： compaction在以LSM-Tree为架构的系统中是非常关键的模块，log append的方式带来了高吞吐的写，内存中的数据到达上限后不断刷盘，数据范围互相交叠的层越来越多，相同key的数据不断积累，引起读性能下降和空间膨胀。因此，compaction机制被引入，通过周期性的后台任务不断的回收旧版本数据和将多层合并为一层的方式来优化读性能和空间问题。而compaction的策略和任务调度成为新的难题，看似简单的功能，实则需要各方面的权衡，涉及空间、I/O、cpu资源和缓存等多个层面。这篇文章将从compaction策略、挑战、几个主流lsmtree系统的实现和学术上的研究几个方向来探讨

什么是LSM-Tree

LSM-tree 在 NoSQL 系统里非常常见，基本已经成为必选方案了。

LSM-tree 是专门为 key-value 存储系统设计的，key-value 类型的存储系统最主要的就两个个功能，put（k，v）：写入一个（k，v），get（k）：给定一个 k 查找 v。

LSM-tree 最大的特点就是写入速度快，主要利用了磁盘的顺序写，pk掉了需要随机写入的 B-tree。

下图是 LSM-tree 的组成部分，是一个多层结构，就更一个树一样，上小下大。首先是内存的 C0 层，保存了所有最近写入的 （k，v），这个内存结构是有序的，并且可以随时原地更新，同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上，每一层都是一个在 key 上有序的结构。

写入流程：一个 put（k，v） 操作来了，首先追加到写前日志（Write Ahead Log，也就是真正写入之前记录的日志）中，接下来加到 C0 层。当 C0 层的数据达到一定大小，就把 C0 层 和 C1 层合并，类似归并排序，这个过程就是Compaction（合并）。合并出来的新的 new-C1 会顺序写磁盘，替换掉原来的 old-C1。当 C1 层达到一定大小，会继续和下层合并。合并之后所有旧文件都可以删掉，留下新的。

注意数据的写入可能重复，新版本需要覆盖老版本。什么叫新版本，我先写（a=1），再写（a=233），233 就是新版本了。假如 a 老版本已经到 Ck 层了，这时候 C0 层来了个新版本，这个时候不会去管底下的文件有没有老版本，老版本的清理是在合并的时候做的。

写入过程基本只用到了内存结构，Compaction 可以后台异步完成，不阻塞写入。

查询流程：在写入流程中可以看到，最新的数据在 C0 层，最老的数据在 Ck 层，所以查询也是先查 C0 层，如果没有要查的 k，再查 C1，逐层查。

一次查询可能需要多次单点查询，稍微慢一些。所以 LSM-tree 主要针对的场景是写密集、少量查询的场景。

LSM-tree 被用在各种键值数据库中，如 LevelDB，RocksDB，还有分布式行式存储数据库 Cassandra 也用了 LSM-tree 的存储架构。

LevelDB

其实光看上边这个模型还有点问题，比如将 C0 跟 C1 合并之后，新的写入怎么办？另外，每次都要将 C0 跟 C1 合并，这个后台整理也很麻烦啊。这里以 LevelDB 为例，看一下实际系统是怎么利用 LSM-tree 的思想的。

下边这个图是 LevelDB 的架构，首先，LSM-tree 被分成三种文件，第一种是内存中的两个 memtable，一个是正常的接收写入请求的 memtable，一个是不可修改的immutable memtable。

另外一部分是磁盘上的 SStable （Sorted String Table），有序字符串表，这个有序的字符串就是数据的 key。SStable 一共有七层（L0 到 L6）。下一层的总大小限制是上一层的 10 倍。

写入流程：首先将写入操作加到写前日志中，接下来把数据写到 memtable中，当 memtable 满了，就将这个 memtable 切换为不可更改的 immutable memtable，并新开一个 memtable 接收新的写入请求。而这个 immutable memtable 就可以刷磁盘了。这里刷磁盘是直接刷成 L0 层的 SSTable 文件，并不直接跟 L0 层的文件合并。

每一层的所有文件总大小是有限制的，每下一层大十倍。一旦某一层的总大小超过阈值了，就选择一个文件和下一层的文件合并。就像玩 2048 一样，每次能触发合并都会触发，这在 2048 里是最爽的，但是在系统里是挺麻烦的事，因为需要倒腾的数据多，但是也不是坏事，因为这样可以加速查询。

这里注意，所有下一层被影响到的文件都会参与 Compaction。合并之后，保证 L1 到 L6 层的每一层的数据都是在 key 上全局有序的。而 L0 层是可以有重叠的。

上图是个例子，一个 immutable memtable 刷到 L0 层后，触发 L0 和 L1 的合并，假如黄色的文件是涉及本次合并的，合并后，L0 层的就被删掉了，L1 层的就更新了，L1 层还是全局有序的，三个文件的数据顺序是 abcdef。

虽然 L0 层的多个文件在同一层，但也是有先后关系的，后面的同个 key 的数据也会覆盖前面的。这里怎么区分呢？为每个key-value加个版本号。所以在 Compaction 时候应该只会留下最新的版本。

查询流程：先查memtable，再查 immutable memtable，然后查 L0 层的所有文件，最后一层一层往下查。

LSM-tree读写放大

读写放大（read and write amplification）是 LSM-tree 的主要问题，这么定义的：读写放大 = 磁盘上实际读写的数据量 / 用户需要的数据量。注意是和磁盘交互的数据量才算，这份数据在内存里计算了多少次是不关心的。比如用户本来要写 1KB 数据，结果你在内存里计算了1个小时，最后往磁盘写了 10KB 的数据，写放大就是 10，读也类似。

写放大：我们以 RocksDB 的 Level Style Compaction 机制为例，这种合并机制每次拿上一层的所有文件和下一层合并，下一层大小是上一层的 r 倍。这样单次合并的写放大就是 r 倍，这里是 r 倍还是 r+1 倍跟具体实现有关，我们举个例子。

假如现在有三层，文件大小分别是：9，90，900，r=10。又写了个 1，这时候就会不断合并，1+9=10，10+90=100，100+900=1000。总共写了 10+100+1000。按理来说写放大应该为 1110/1，但是各种论文里不是这么说的，论文里说的是等号右边的比上加号左边的和，也就是10/1 + 100/10 + 1000/100 = 30 = r * level。个人感觉写放大是一个过程，用一个数字衡量不太准确，而且这也只是最坏情况。

读放大：为了查询一个 1KB 的数据。最坏需要读 L0 层的 8 个文件，再读 L1 到 L6 的每一个文件，一共 14 个文件。而每一个文件内部需要读 16KB 的索引，4KB的布隆过滤器，4KB的数据块（看不懂不重要，只要知道从一个SSTable里查一个key，需要读这么多东西就可以了）。一共 24*14/1=336倍。key-value 越小读放大越大。

总结

关于 LSM-tree 的内容和 LevelDB 的设计思想就介绍完了，主要包括写前日志 WAL，memtable，SStable 三个部分。逐层合并，逐层查找。LSM-tree 的主要劣势是读写放大，关于读写放大可以通过一些其他策略去降低。

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