LSM-Tree 结构的存储系统,将离散的随机写请求,通过WAL + Compaction机制变为批量的顺序写请求,
提升写入性能。但是,多个level、每层多个SST文件的架构也存在一些问题:

  • 读放大:当查询一个key时,需要遵循从新到旧的查找过程,直到找到想要的数据。虽然有全局manifest文件索引、
    每个SSTable还有Bloom filter,但是逐层的步骤不可避免,这个过程可能需要不止一次的磁盘IO,尤其是做query range时,影响更明显;
  • 空间放大:所有写入都是顺序写,修改和删除操作也是通过写入新的 SN 来实现,所以无效数据不会随着delete一起立即删除,
    而是在compaction时实现物理删除;
  • 写放大:每层level,在SSTable数量到达一定阈值时,会发生compation操作(本层和下一层中的相同key如果有重叠,
    会进行排序后的重写)

整体结构

每一个 Record 由 <Key, SN(Sequence Number), ValueType, Value> 四部分组成。SN 是在写入数据时生成的一个全局递增的整数,
ValueType 表明这个 Record 是否为有效的 Record。 Record 被分为多层保存,从 Level 0 开始到 Level N。除 Level 0 外,
每一个 Level 内的 Record 都是有序的,且被分别保存在多个文件中,每个文件被称作一个 SStable。

写入流程:

  • 生成一个新的SN.
  • 将 Record 写入WAL(write ahead log),保证Crash Safe(Consistency Safe).
  • 将 Record 写入内存中的 Memtable.

当 MemTable(可读可写) 中的数据量超过某个值(一般4MB)时,会变为 Immutable memtable(可读)。通过双buffer的机制,
有效减少了 MemTable 在写满时,由于flush到磁盘可能产生的阻塞问题。

查询流程

一般读取有两种方式:

  1. 通过get接口读取数据.
  2. 创建一个snapshot,基于该snapshot调用get接口读取数据.

这两种方式本质一样,都是快照读,第一种方式会先隐式的创建一个数据库当前状态的快照,然后基于这个快照再去调用get方法读.

具体的步骤如下:

  • 在Memtable(skipList)中查找指定的key,若搜索到符合条件的key就结束查找;
  • 在Immutable memtable(skipList)中查找指定的key,若搜索到符合条件的key就结束查找;
  • 按照level0 -> levelN的顺序在每层中的sstable文件中查找指定的key,若搜索到符合条件的数据项就结束查找

    注意在每一层sstable中查找数据时,都是按序依次查找sstable的。
    0层的文件比较特殊。由于0层的文件中可能存在key重合的情况,因此在0层中,文件编号大的sstable优先查找。理由是文件编号较大的sstable中存储的总是最新的数据。
    非0层文件,一层中所有文件之间的key不重合,因此可以借助sstable的元数据(一个文件中最小与最大的key值)进行快速定位,每一层只需要查找一个sstable文件的内容。

在memory db或者sstable的查找过程中,需要根据指定的序列号拼接一个internalKey,查找用户key一致,且seq号不大于指定seq 的数据.

Compaction(压缩)

Minor Compaction

是指将内存中 Immutable memtable 的数据持久化为 0 层的 sstable 文件的过程,若干个0层文件中key是可能存在 overlap 的。
是一个时效性非常高的操作,要求在尽可能短的时间内完成,否则会阻塞正常的写入操作。minor compaction 的优先级高于 major compaction,
当同时发生时,会暂停 major compaction。 minor compaction 操作重写文件会带来很大的带宽压力以及短时间IO压力。 因此可以认为,
它就是使用短时间的IO消耗以及带宽消耗换取后续查询的低延迟。

Major Compaction

对相邻两个层的 sstable 进行多路归并排序,对文件中的 key 重新排序,过滤掉冗余版本后(视情况决定是否删除原文件),重新生成新的 sstable 的过程。

一次读取需要在内存中进行效率为O(log n)的查询。 若没有在内存中命中,则需要从 sstable 文件中查找。因为0层可能存在overlap,最差情况需要遍历0层所有文件。
随着运行时间的增长,minor compaction 导致 0 层文件的个数会越来越多,查询效率也会越来越低,这显然是不能接受的。 因此,需要 major compaction 机制通过将0层中的文件,
合并为若干个没有数据重叠的1层文件,一次的查找过程就可以进行优化。 compaction 归并的一个原因就是为了提高读取的效率,优化读放大问题。

一般 major compaction 的触发机制需要满足这几个条件:

  • 当0层文件数超过预定的上限(默认为4个)
  • 当 i 层文件的总大小超过(10 ^ i) MB
  • 当某个文件无效读取的次数过多

因为 major compaction 是为了解决 0层文件过多导致读取效率低,但是如果仅关注 i 层的文件个数,在多次major compaction后,i+1 层会发生同样的问题,
因此需要对每层的文件总数设定阈值。在某层文件个数达到阈值时,启动major compaction,提升读取效率,并且降低后续 compaction 的IO开销。

上述的机制可以保证合并的进行,但仍存在一种极端问题:当i层合并完成之后,i+1层的文件同时达到数据上限,更糟糕的是,最差情况下0->n层都会发生连锁更新。
因此在合并时增加了这样两种机制:

错峰合并
  1. 一个文件一个查询的开销为10ms,若某个文件的查询次数过多,且查询在该文件中不命中,那么这种行为就可以视为无效查询开销
  2. 一个1MB的文件,其合并的开销为25ms。因此当一个1MB文件的文件无效查询超过25次时,对其合并
采样探测

在sstable文件的metadata中,有一个额外的字段seekLeft,默认为文件的大小除以16kb。采样的过程:
记录本次访问的第一个sstable文件,如果在该文件中访问命中,则不做任何处理;若未命中,对该文件的seekLeft标志做减一操作。
seekLeft标志减少到0时,触发对该文件的错峰合并。

最终目标

Compaction 的设计一方面需要保证Compaction的基本效果,另一方面又不会带来严重的IO压力。
然而,并没有一种设计策略能够适用于所有应用场景或所有数据集。Compaction选择什么样的策略需要根据不同的业务场景、不同数据集特征进行确定。
设计Compaction策略需要根据业务数据特点,目标就是降低读、写、空间三者的放大,不断权衡如下几点:

  • 合理控制读放大:避免因Minor Freeze增多导致读取时延出现明显增大,避免请求读取过多SSTable;
  • 合理控制写放大:避免一次又一次地Compact相同的数据;
  • 合理控制空间放大:避免让不需要的多版本数据,已经删除的数据和过期的数据长时间占据存储空间,避免在Compaction过程中占用过多临时存储空间,
    及时释放已经Compact完成的无用SSTable的存储空间;

Compaction流程

压缩整体过程分为这几步:

  1. 寻找合适的输入文件
  2. 扩大输入文件集合
  3. 多路合并
寻找输入文件
  • 对于 0 层文件数过多引发的合并场景或由于 i 层文件总量过大的合并场景,采用轮转的方法选择起始输入文件,记录了上一次该层合并的文件的最大key,
    下一次则选择在此key之后的首个文件。
  • 对于错峰合并,起始输入文件则为该查询次数过多的文件。
扩大输入文件集合
  1. 在 i 层确定起始输入文件。
  2. 在 i 层中,查找与起始输入文件有key重叠的文件(这种情况一般发生在0层),构成 i 层的输入文件,结果为红线标注的文件。
  3. 利用 i 层的输入文件,在 i+1 层寻找有 key 重叠的文件,构成 i、i+1层的输入文件,结果为绿线标注的文件。
  4. 利用两层的输入文件,在不扩大 i+1 层输入文件的前提下,查找 i 层有key重叠的文件,构成最终全部的输入文件,结果为蓝线标注的文件。
    expand_collect
多路合并

将输入文件内所有的数据项,按序排列之后,输出到 i+1 层的若干个新文件中。在合并的过程中,相同key的冗余数据,仅保留最新版本的那一份。
如果文件中存在某些仍在使用的旧版本数据,此时不能立即删除,需要等到使用结束,释放文件句柄后,根据引用计数来清除。