LSM 优化系列（三）-- 【ATC‘19】9SILK- Preventing Latency Spikes in Log-Structured Merge Key-Value Stores

1. Latency Spike in LSM

论文原地址 可以参考

在 USENIX Annual Technical Conference2019的定会上，该篇论文提出了解决LSM 架构在update 或者有部分update参与的场景下出现的长尾延时问题。

关于LSM架构下的长尾延时问题，之前在介绍rocksdb的Rate Limiter 实现原理 时提到过，这里简单描述一下。

1.1 LSM三种internal操作

• Flush 由write-buffer 写入 L0
• L0-L1 Compaction 因为L0 层文件之间允许有key的重叠（LSM 为了追求写性能，使用append only方式写入key，write-buffer一般是skiplist的结构），所以只允许单线程将L0的文件通过compaction写入L1
• Higher Level Compactions 大于L0层 的文件严格有序，所以可以通过多线程进行compaction.
  

Flush 操作如下：

• 请求写入到(write-buffer)memtable之中，当达到write_buffer_size大小 进行memtable switch
• 旧的memtable变成只读的用来 Flush，同时生成一个新的memtable用来接收客户端请求
• Flush的过程就是在L0 生成一个sst文件描述符，将immutable 中的数据通过系统调用写入该文件描述符代表的文件中。
  

L0–> L1 Compaction 操作如下：

• 将一个L0的sst文件和多个L1 的文件进行合并
• 目的是节省足够的空间来让write-buffer持续向L0 Flush
  

Higher Level Compactions操作如下：
对整个LSM进行GC，主要丢弃一些多key的副本 和 删除对应的key的values

这个过程并不如L0–>L1的compaction 紧急，但是会产生巨量的IO操作，这个过程可以后台并发进行。

1.2 长尾延时的原因

• L0满， 无法接收 write-buff不能及时Flush，阻塞客户端
  
  因果链如下：
  没有协调好internal ops – 》 Higher Level Compactions 占用了过多的IO --》L0–>L1 compaction 过慢 --》L0没有足够的空间 --》Write-buffer无法继续刷新。
• Flush 太慢，客户端阻塞
  
  因果链如下：
  没有协调好internal ops --》 Higher Level Comapction占用了过多的I/O --》 Flushing 过程中没有足够的IO资源 --》Flushing 过慢 --》Write-buffer提早写满而无法切换成immutable memtable，阻塞客户端请求。

综上我们知道了在LSM 下客户端长尾延时主要是由于三种 内部操作的IO资源未合理得协调好导致 最终的客户端操作发生了阻塞。

针对长尾延时的优化我们需要通过协调内部的internal 操作之间的关联，保证Flushing 优先级最高，能够占用最多的IO资源；同时也需要在合理的时机完成L0–L1的Compaction 以及 优先级最低但是又十分必要的Higher Level Compaction。

以下简单介绍一下Rocksdb 内部原生的Rate Limiter对这个过程的优化。

综上可以看到传统LSM的长尾延时问题 主要是由于LSM 三个internal ops（Flush, L0–>L1 compaction ,Higher Level Compactions）的调度策略导致的。

2. 长尾延时的业界解决方案

2.1 Rocksdb

首先对比了Rocksdb 实现的LSM,开启和关闭Compaction时的长尾延时情况如下：

可以看到开启Internal ops（橘黄色部分） 之后 整个长尾延时相比于未开 高了接近4个量级。

2.2 Rate-Limited Rocksdb

通过限制 internal ops的I/O带宽 是一个业界比较认可的限制长尾延时问题的方法，SILK开发人员也对Rocksdb自实现的Rate Limiter做了测试。关于Rate Limter的实现可以参考Rocklsdb Rate Limiter实现原理。

通过设置不同的Limit Rate来对长尾延时的情况进行统计，得到如下测试结果：

可以看出随着 限制internal ops带宽越来越高，那么长尾延时 维持在较低的时间 越来越长。

但是这并不能无限制得增加internal ops的限制带宽，因为随着compaction 累积的量越多，后期会 较高概率有一次累积 更多的compaction 与上层吞吐来争抢IO带宽。

2.3 TRIAD

ATC’17 TRIAD TRIAD: Creating Synergies Between Memory,
Disk and Log in Log Structured Key-Value Stores 是一个非常有代表性的先进系统，来降低internal ops对长尾延时的影响，SILK对该系统也做了对应的测试。

TRIAD 通过调度 减少 L0–》L1 的compaction 降低 compaction 对client 的吞吐影响，但是这个问题会导致Higher Level Compactions的增加。所以上图中可以看出在1000s以后较长的一段时间内，整体的长尾延时还是会增加。

2.4 Pebblesdb

关于Pebblesdb 的整体介绍可以参考Pebblesdb: Building Key-Value Stores Using FLSM

SILK也对pebblesdb的长尾延时做了整体的测试，在读敏感的workload下(95:5)workload下，长尾延时保持在一个非常好的效果，但是在运行了8个小时之后，compaction大量接入，整体的系统效率被严重阻塞。

因为Pebblesdb运行guards内部存在重叠key，所以到后期大量的Higher level compactions抢占了系统的资源，导致整个client的IO被阻塞，整个stall一直持续直到compaction完成终止。

2.5 Lessons Learned

1. 对于较高的长尾延时出现的主要原因是 写被存在于内存的write buffer 填满阻塞了。
   Write buffer满主要有如下两个原因
   a. L0满，造成write-buffer向L0 flush被终止。从而导致客户端无法持续向新的write-buffer写入。这里L0满的原因是，L0–》L1 Compaction的过程中没有IO被更高层compaction 产生的I/O抢占，导致L0 提前满。
   b. Flush slow，由于更高层的并发compaction导致Flush的IO被抢占，从而产生Flush的速度没有write-buffer的写入速度快。
2. 仅仅限制 internal ops的IO带宽并无法解决Flush或者L0 ->L1 compaction等优先级较高的任务被 Higher Level Compactions抢占的问题。所以Rocksdb的 Rate Limiter 以及 Rocksdb的Auto tune等都会导致后续Higher Level compactions抢占优先级较高的任务的IO，从而间接导致write-buffer full.
3. 近些年的一些LSM优化的方法 提出为了提升吞吐，将Compaction下沉到更高层来做，这在短期内能够收获较为稳定的延时以及较高的吞吐，但是在跑了很长一段时间之后就会出现大量的Compaction抢占系统资源的问题，从而导致Client qps stall。

综上 ，我们能够得出如下结论，并不是所有的internal ops都需要平等共享系统资源，比如 Flush 以及 L0->L1 Compaction，就是优先级比较高的internal ops，这一些操作不能及时完成，就会导致Client ops被stall。

3. SILK 实现

SILK 在总结了之前业界相关的优化方案，为了避免再次出现上文2.5中指出的Lesson learned，核心的设计思想将遵循如下三个原则。

3.1 SILK 设计原则

1. 让Internal ops都有能够获得IO带宽的机会。SILK 在client 的流量洪峰时会减少Higher level Compaction的IO带宽占用，在client 流量低峰时增加Higher Level的Compactions的带宽。
2. 对LSM tree的internal ops进行优先级调度。正如SILK将LSM的internal ops分为三种不同的操作，并调度优先级来降低对Clinet的长尾延时的影响。SILK的调度策略如下：
   a. SILK确保Flush足够快，即Flush的优先级最高。从而为内存中的write-buffer接受客户端的请求留下足够的空间。Flush的速度是直接影响客户端的长尾延时问题。
   b. SILK 将L0 -> L1 Compaction的速度放在第二优先级，确保L0不会达到它的容量上限，从而保证Flush能够有足够的空间完成操作。
   c. SILK 将Higher Level Compaction的优先级设置为最低，因为这些Compactions的目的是为了维持LSM的形状，并不会短期内对Client的长尾延时造成影响。

3.2 SILK 详细实现

3.2.1 按照概率分配I/O带宽

SILK会持续监控 Client操作被分配的I/O带宽，并且分配可用的带宽给到internal ops。
根据客户端 qps的波动情况，配置对应的监控粒度，用来决定为internal ops分配带宽的比例。当前SILK的实现配置的监控粒度是10ms。

具体配置方式如下：

T B/s : 表示在LSM 架构的KV存储中 ，总的I/O带宽
C B/s: SILK 监控的Client操作占用的I/O带宽

则internal ops可用的带宽是：I = T - C - µ B/s,其中 µ 可以理解为是一个小的buffer。

为了灵活得调整I/O带宽，SILK使用了Rocksdb标准的Rate Limiter, 同时SILK 为Flushing和 L0->L1 Compaction，也维护了一个最小的可配置的I/O带宽 时间间隔。

3.2.2 优先级调度 和 可抢占的 Internal ops设计

SILK 维护了internal work的线程池。当一个Flush任务或者一个Compaction任务处理完成之后，线程池会根据当前LSM 不同层待Compaction的量以及内存中write-buffer的状态 来判断是否需要调度更多的线程进行对应的internal (Flush 或者 L0 Compaction)任务的调度处理。
接下来主要介绍一下SILK 维护的两个线程池：一个 为flushing的 high-priority 线程池，另一个低优先级的Compactions线程池。

Flushing 在所有的internal ops中优先级最高。所以它有自己专有的线程池，并且有权限抢占其他任何低优先级的I/O带宽。Flushing的最小带宽需要能够满足从immutable memtable flush的速度快于active memtable的更新速度。当前 实现的SILK 允许内存中存在两个memtable(一个是接受更新的active memtable，另一个只读的immutable memtable) 和一个flush线程，可以通过设置memtable的个数来让client ops低时延维持时间更久。

ps : 这里提到的memtable 也是之前描述的write-buffer,都是LSM在内存中使用跳表维护的有序组件。

L0–》L1 Compaction。L0->L1的compaction 主要是为了保证L0有足够的空间来接受Flush的结果。SILK的实现中 这个internal ops并没有专用的线程进行调度，而是在需要进行L0–>L1的Compaction时 从Compaction pool中随机选择一个线程抢占 进行L0->L1的处理。

这里有必要说明一下，L0–>L1 的compaction这么重要，为什么我们不实用多线程调度，从而加快这个过程？
因为L0的sst文件之间存在key的overlap，为了保证大于L0的层内sst文件之间不存在overlap，则需要保证L0的文件处理的原子性，所以这里只能使用一个线程进行调度。

而Rocksdb原生的实现中为了减少L0的文件重叠度，也会调度L0–>L0的compaction，这里SILK仍然会沿用rocksdb的逻辑（SILK是基于rocksdb 5.7版本进行的改造），只是会将L0–>L0的Compaction 看作L0–>L1 一样的优先级。

Higher Level Compactions。更高层的Compaction 拥有调度的优先级最低。比如L1–>L2进行Compaction的过程中任务被L0–>L1的Compaction需求抢占，这个时候SILK会丢弃掉当前正在做的Compaction任务，不过实际的测试并没有发现这个操作对性能产生非常明显的影响。

SILK控制了总的KV store的I/O带宽，通过在Compaction线程池中调度更低优先级的 Compactions来完成这一过程。比较有趣的是 SILK能够根据 Compactions 任务的紧急程度进行对应I/O带宽的分配，从而能够降低整个LSM tree发生Latency Spike的概率 。

4. 性能数据

Nutanix 的workload是：write:read:scan的比例 – 57:41:2 ，客户端稳定输出的峰值20k/s
可以看到 SILK 能够在很长的一段时间保证客户端p99维持在1ms以下，且吞吐能够和客户端接近，相比于其他的系统则 比较有优势。

在Synthetic的workload下，拥有较高的写比例，同时 peek也由原来的20k/s 逐渐下降到 每隔10s 20k, 每隔50s 20k，每隔100s 20k, 更长时间之后来一次洪峰20k

可以看到silk 的延时会随着洪峰持续的时间而逐渐增加，如果洪峰是间断性来临(比如 洪峰维持10s, 50s, 100s)，则SILK能够提供非常稳定且较低的延时。而因为洪峰的持续时间越长，待Compaction的量累积越多，Higher level compactions的影响越大（已经无法避免得调度更高层的Compaction）。
不过还是能够看到silk是有能力支撑突然而来的流量洪峰，保证吞吐的前提下并维持在一个较低的延时上。

50% read 和 50% write 场景下，这里SILK 将自己和前两种不同的 internal限速策略进行对比，比如 ：
第一行蓝色的表示 动态分配internal IO的带宽，关闭 支持优先级抢占的调度策略。这个前期能够维持一个平稳的延时，但是随着 Compaction 量的累积，后期仍会降低高优先级的操作。
第二行只开启 优先级抢占的策略，关闭动态分配IO带宽的策略。因为 internal ops能够进行不同优先级之间的调度抢占，但是没有办法统筹整体的IO带宽，从而导致后期 Higher Level 的Compaction量增加，无法增大I/O带宽，使得internal ops的调度和client的 调度出现冲突。

第三行 SILK 是融合了以上两种的策略，可以看到整体能够维持在一个非常平稳的延时和吞吐上。

5. 业界相关LSM优化的展望

在这里 ，SILK介绍了三个方向的LSM相关的优化 以及 近些年业界已有的优化方案，非常有参考价值。

5.1 降低Compaction开销方向

5.2 Compaction变种 或者 实现相关的代替方案

5.3 在LSM 的数据结构和相关算法上的一些优化

LSM 的作为新生代存储引擎的基础架构，优异的写吞吐，天然支持的冷热分离架构下提供足量的读的优化。
有得必有失，Compaction的 数据回收和 merge sort带来的I/O 调度 挑战让后来者想要不断去征服这座性能高峰，为引擎界引入足以和B树相媲美的经典架构。

学无止境，不过还好有高手指路，能够发现如此精彩的存储世界，叹之有幸！！！