前言

LSM 引擎针 的业界相关优化方案已经有很多了，优化的方向也是在不同workload纬度上进行取舍。
比如头条的Amap ，中科的dCompaction 是为了降低Compaction的写放大（写放大除了消耗ss），却在一定程度上降低了读性能；

奥斯汀大学 17年发表在顶会SOSP上的pebblesdb 较为有效得降低了写放大，写吞吐相比于原LSM实现提升2-2.7x，同时在range query有一定的优化，性能甚至超过了原有LSM的range query。

悉尼大学 19年发表在顶会UTC上的SILK 通过rocksdb的rate limiter来 通过客户端压力的监控来对 LSM内部整个IO进行限速控制，随未减少写放大，但却有效得降低了compaction对上层吞吐的qps和抖动的影响，尤其是长尾延时的优化上有效降低且极为稳定。

还有很多其他的优化方案，甚至专门有人整理了一篇LSM的优化论文，对业界数十篇LSM相关优化论文做了一个总结：
LSM-based Storage Techniques: A Survey
当然，rocksdb社区也在努力研究有效的compaction优化方案，本节想要介绍一下rocksdb 原生实现的compaction IO层的限速方案，通过compaction限速来降低compaction的IO对Client的 qps 和 波动的影响。

通过本文，你能够了解到如下关于rocksdb/LSM的知识点：

1. compaction为什么会影响上层qps （纯写场景）?
2. rocksdb rate limiter 基本限速接口
3. rocksdb rate limiter 原理实现
4. rocksdb rate limter 的限制

ps: 文中涉及到的源代码 都是基于rocksdb 6.4.6版本，不同的版本之间可能有实现细节上的差异，不过主体逻辑都是差不多的。

1. Compaction为什么会影响Client qps

1.1 基本LSM介绍

如下图 是一个基本的LSM 树的分层结构（以下的操作描述是针对传统LSM 的实现进行描述的，没有完整描述整个rocksdb的基本实现）：

内存中有一个 write-buffer, 在rocksdb 上 也叫做 memtable
磁盘上从 L0-Ln也是一个分层结构： 每一层可以有很多有序字节表(sstables)，其中L0层的sst之间可以有重叠，大于L0层的sst文件严格有序 且层内sst之间不能有重叠keys.

如下图 两种请求落到LSM 中：

• Client 的update请求 会写入到内存中的write buffer之中即可返回，后续的写入由internal operation – flush and compaction来负责。

• Client 的read 请求 会先读 write buffer，如果读不到则按照磁盘上的L0 - Ln逐层读取。
  

1.2 LSM internal ops

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.3 长尾延时的原因

• 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对这个过程的优化。

2. Rate limiter 基本限速接口

社区Rate Limiter 介绍
核心接口：

RateLimiter* rate_limiter = NewGenericRateLimiter(
    rate_bytes_per_sec /* int64_t */, 
    refill_period_us /* int64_t */,
    fairness /* int32_t */);

将该接口加入到应用中的option的方式就是：

options.rate_limiter.reset(
					rocksdb::NewGenericRateLimiter(
					rate_bytes_per_sec /* int64_t */,
					refill_period_us /* int64_t */,
					fairness /* int32_t */));

核心参数如下三个：

• rate_bytes_per_sec 这个是最常用也是大家使用起来最有效的一个参数，用来控制compaction或者flush过程中每秒写入的量。比如，设置了200M， 表示当compaction 累积的总写入token达到 200M /s 时才会触发系统调用的write.
• refill_period_us 用来控制 token 更新的频率；比如设置的rate_bytes_per_sec是10M/s， 且refill_period_us 设置的是100ms,那么表示 每100ms即可重新调用一次compaction的写入。针对1M的大value 可以立即写入，而小于1M的数据则需要消耗CPU， 累积到1M 触发一次写入。
• fairness 表示低优先级请求获得处理的概率。
  RateLimiter 支持接受高优先级线程 和 低优先级线程的请求，一半flush操作是最高的优先级，其次是 L0 --> L1 compaction优先级较高，最后则是Higher Level compactions 优先级最低。那么这个参数 fairness表示 即使现在有较多的高优先级任务在调度，低优先级的任务也有 1 / fairness 的机会能够被调度，从而防止被饿死。

3. Rate Limiter 限速原理实现

3.1 Rate Limiter的传入

先从我们的客户端入口来看 创建了RateLimiter 都做了一些什么？
rocksdb::NewGenericRateLimiter 接口主要是做一些初始化变量的工作：

以上类是继承自RateLimiter 类，能够提供更加精确的限速控制，比如初始化变量中的RateLimiter::Mode mode来制定限速是针对只读 或者 只写 或者 所有的读写。

这个时候我们初始化好了rate_limter的对象，并将其传给options中，应用拿着options打开了rocksdb,具体的DB::Open过程中会初始化DBImpl对象

初始化该对象的过程中会拿着我们之前创建好的rate_limiter 进行全局option的初始化工作：

在DBOptions SanitizeOptions函数中 能够看到通过rate_limiter 结合其他配置 或者交给指定的配置来达到后续限速的目的。

同时还会有在其他地方直接使用的rate_limiter对象 达到限速的目的：
在从sst file中调用read接口读取数据时能够通过rate_limiter 限制读请求的速率

同理当需要通过flush或者compaction 过程向sst文件中写入数据的时候可以通过rate limiter限制写入的速率

3.2 Rate Limiter 控制 sync datablock的速率

接着上文 RateLimiter 不为空时会将rate_bytes_per_sec 数值作为delayed_write_rate的速率。
这个delayed_write_rate参数会在rocksdb的Write Stall 的限速中进行描述，这里简单说一下 rocksdb 触发Write Stall 的几种原因：

• 过多memtables. 当此时内存中有 max_write_buffer_number 个memtables等待被flush，写会被完全Stall
  在rocksdb的日志中会有如下记录：

  Stopping writes because we have 5 immutable memtables (waiting for flush), max_write_buffer_number is set to 5
  

• 过多的L0 SST files. 当L0的sst 文件个数超过level0_slowdown_writes_trigger个之后，会触发write stall;当L0文件个数达到level0_stop_writes_trigger 之后写入会完全阻塞。
  在rocksdb的日志中会有类似如下记录:

  Stalling writes because we have 4 level-0 files
  Stopping writes because we have 20 level-0 files
  

• 过多的待处理 Compaction-bytes. 当预估的待处理Compaction 总大小达到了soft_pending_compaction_bytes会触发Stall，达到了hard_pending_compaction_bytes 会触发stop write。
  在rocksdb的日志中会有类似记录如下：

  Stalling writes because of estimated pending compaction bytes 500000000
  Stopping writes because of estimated pending compaction bytes 1000000000
  

回到上文中提到的bytes_per_sync参数：
在rocksdb 进行Compaction或Flush过程中 ，写入数据之前 会通过OpenCompactionOutputFile函数 创建WritableFileWriter 对象，来负责将即将写入的数据通过posix接口进行数据处理写入到文件系统的page cache或者 direct写入到磁盘之中。
创建WritableFileWriter 对象的过程中会将 通过option 传入的rate_limiter 传入到该对象之中。

到实际写入时，会通过BlockBasedTableBuilder::Add --> BlockBasedTableBuilder::Flush() --> BlockBasedTableBuilder::WriteBlock() --> BlockBasedTableBuilder::WriteRawBlock() --> WritableFileWriter::Append() --> WritableFileWriter::Flush() 以及WritableFileWriter::WriteBuffered()这两个函数

其中WritableFileWriter::Flush() 这个函数中会调用如下逻辑：
即当前写入到内存中缓存的数据偏移地址 相比于上一次的偏移地址 大小超过了1M，则触发一次RangeSync

RangeSync中也需要strict_bytes_per_sync_ 参数为1 才会是一次真正的sync系统调用。

这里为什么会有这样的配置呢，简单描述一下rocksdb写sst文件的逻辑：
原生配置是将所有的sst文件中的datablock,filterblock, index block,等所有的数据block写到内存（page cache）之后统一调用一次对当前文件句柄的sync操作，从而有效减少IO次数。

但是问题是类似这样大批量的累积sync 可能会导致compaction/flush 在每隔一段时间占用巨量的IO带宽，从而造成client的latency spike或者qps下降。

所以通过 rate_limiter配置 + bytes_per_sync + strict_bytes_per_sync_ 能够减少大批量的累积sync,而让整个IO均匀分不到整个compaction/flush的写入链路，可能client 的qps还是会有下降，但是不会出现过高的latency spike.

3.3 Rate Limiter控制写入速率

回到上文 Compaction / Flush的写入链条：
BlockBasedTableBuilder::Add --> BlockBasedTableBuilder::Flush() --> BlockBasedTableBuilder::WriteBlock() --> BlockBasedTableBuilder::WriteRawBlock() --> WritableFileWriter::Append() --> WritableFileWriter::Flush() 以及WritableFileWriter::WriteBuffered()这两个函数
看看WritableFileWriter::WriteBuffered() 函数，它是负责向缓冲区中添加数据：

通过 调用rate_limiter的RequestToken函数 --》 调用GenericRateLimiter::Request函数，来检测添加的数据大小left 是否满足开始配置的rate_limiter的rate_bytes_per_sec限速大小，如果未达到，则会让当前线程休眠，并按照refill_period_us频率来定时更新待写入的bytes是否满足写入的速率要求，并及时填充写入缓冲区。

此时当前的写入过程会阻塞，直到left累积到rate_limiter的写入限速阈值，才会继续向当前的文件句柄中正常写入。

4. rocksdb Rate Limiter的限制

静态的限速控制：
无法灵活变通， 后台internal ops的写入速率，比如偶尔Client 压力较大，需要降低internal ops写入速率对client的影响；偶尔Client 压力较小， 又可以增加internal ops,将之前累积的待写入的数据写入。

实际的测试，刚开始能够提供较为稳定的qps latency。但是在写入一段时间之后，随着数据量的增加，静态的Rate limter无法保证 internal ops(flush , L0–>L1 compaction 以及 higher level compactions) 在不影响client latency的情况下及时有效的处理，从而出现了较高的latency spike.

当然rocksdb后续推出的 auto tune 以及 业界的 TRIAD 和 SILK设计 看他们的描述 都能够有效的降低latency spike，后续会尝试有效测试 并发掘背后实现机理 之后分享出来。