ATC’19 SILK | Notion Blog

type

status

date

slug

summary

References

Blog

SILK： Preventing Latency Spikes in Log-Structured Merge Key-Value Stores阅读笔记

Introduction 这篇论文是ATC2019的best paper，因为最近在研究一些关于尾延迟的问题，偶然看到了这篇paper着重对写操作的长尾延迟（Tail Latency）进行了优化，所以简单看了一下其中对Tail Latency的一些分析以及…

https://zhuanlan.zhihu.com/p/586671735

Preventing Latency Spikes LSM Key-Value Stores

0. 介绍当前，以LevelDB、RocksDB为代表的LSM-tree k-v存储引擎广泛应用，所以研究和优化的非常多，无论是学术界和工业界，之前也有介绍多个相关的工作。今天也因为 "利奇马"到访杭州，所以难得清闲在家里…

https://zhuanlan.zhihu.com/p/77543818

Preventing Latency Spikes LSM Key-Value Stores

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

学无止境，不过还好有高手指路，能够发现如此精彩的存储世界，叹之有幸！！！LSM 的作为新生代存储引擎的基础架构，优异的写吞吐，天然支持的冷热分离架构下提供足量的读的优化。有得必有失，Compaction的数据回收和 merge sort带来的I/O 调度挑战让后来者想要不断去征服这座性能高峰，为引擎界引入足以和B树相媲美的经典架构。

https://blog.csdn.net/Z_Stand/article/details/109683804

原资料

SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores

www.usenix.org

https://www.usenix.org/sites/default/files/conference/protected-files/atc19_slides_balmau_0.pdf

www.usenix.org

https://www.usenix.org/sites/default/files/conference/protected-files/atc19_slides_balmau_0.pdf

SILK-USENIXATC2019

theoanab • Updated Dec 25, 2023

Abstract

已经有广泛的文献证明，LSM Comapction 严重影响了吞吐量，现有的一些优化方案有：限制 compactions 和 flushes 的速率，选择合适的压缩策略，通过所谓的碎片化 LSMs 将压缩限制到最高级别（PebblesDB 的 FLSM）

本文更关注延迟，因为现有的优化吞吐量的方案并不会解决长尾问题，反而可能会加剧该现象。造成长尾的根本原因是客户端写、flush、compaction 操作之间的干扰。所以本文提出了一个 I/O 调度器来减少干扰：

在低负载期间，机会地将更多带宽分配给内部操作
优先执行 flush 和较低级别的 compactions 操作
抢占式的 Compactions

基于 RocksDB 的 SILK，测试表明相比于 RocksDB 和 TRIAD 尾延迟降低了两个数量级，且未对性能产生任何负面影响。

Introduction

应用场景：延迟敏感型负载

以往的工作：现有的工作大多都是提升系统吞吐量的，但基本都没减少尾延迟。

问题和原因分析：造成延迟的主要原因主要是客户端操作到达系统的时候，系统恰恰正在执行后台的任务，两者之间产生了干扰。虽然内部操作发生的次数比较少，且开销并不是特别大，但是在实际生产环境中其出现的频率已经足够影响到尾延迟的，特别是在一些客户端负载较重的时候。

解决问题的固有思路的问题：

限制内部操作的带宽（这个可能是生产环境中应用的比较多的）

理论上可以一定程度上避免内部工作和客户端负载之间的干扰造成的延迟 spike。但实际观察发现并非如此
举个例子，突发的写入触发突发的 flushes，如果这时候一定数量的压缩操作同时进行，flush 操作不得不和 compaction 共享有限的带宽资源，然后就会出现都变慢的情况，反过来会导致内存组件很快填满然后阻塞客户端写入，从而产生延迟 spike。

限制压缩的速度也是低效的

因为压缩限速之后可能导致 tree 的较低层次很快就被填满，会让 flush 停顿，反过来 stall writes

本文的思路：客户端负载和不同内部操作施加的负载之间需要协调，所以设计了一个调度器 SILK

客户端和内部操作之间动态分配带宽
优先考虑可能阻塞客户端操作的内部操作
允许抢占不太重要的内部操作执行

LSM KV background

LSM 架构不再赘述

Operation

LSM 的操作按照本文的逻辑分为了两种，分别使用了不相干的线程池分别执行操作：

客户端操作：常见的 KV 读写操作。客户端操作按照 FIFO 的顺序执行，由一个包含固定大小的线程数的线程池来执行
内部操作：flush 和 compaction。

flush 操作不会做额外的操作，直接把内存组件写入到磁盘中即可
compaction 操作在很多 KV 系统中是可以并行执行的，除了 L0-L1 之间的 compaction，因为 L0 键范围可能重叠。compaction 因为需要读旧的 SSTable 然后写新的 SSTable 所以会引入比较大的 I/O 开销。
系统内部也是维护了一个 FIFO 队列，两种操作分别入队。内存组件满了之后一个 flush 请求将入队，一个 flush 完成之后或者一个 compaction 完成之后可能会有一个新的 compaction 请求入队。内部工作线程池为内部工作队列中的请求提供服务。在当前的 LSM KVs 中，为了维护 LSM 树的结构，只要系统认为该操作有必要，就会进入一个内部操作队列（比如到了每个 level 的最大容量或者最大文件数量限制）

State-of-the-art LSM-based systems

RocksDB

TRAID

PebblesDB

Performance requirements for LSM KVs

Low tail latency

Predictable throughput

Small main memory footprint

LSM issues: 客户端操作和内部操作之间会互相产生影响，表现出来的就是内部操作会影响客户端操作的响应延迟，但内部操作并不知道客户端负载的情况。

负载较重的时候，compaction 操作会处理大量数据且执行很长时间，占用很久的带宽，从而导致一些问题：假设 flush 操作没有得到定时执行，那么客户端写入操作将被阻塞；
其次 L0->L1 压缩缓慢的话将导致 L0 层大量数据累积，当道到了 L0 层最大文件数量时整个系统都会挂起。

Experimental study of tail latency

Setup

YCSB

update-intensive workload，R:W=50:50, items 1KB (workload A)
uniform data distribution （便于排除倾斜负载中内存缓存带来的影响）

参数：尽可能调了参数

参考 RocksDB Tuning Guide
参考 PebblesDB

HW：

20-core Intel Xeon （two 10-core 2.8 GHz processors）
256 GB of RAM
960GB SSD Samsung 843T
cgroup 限制 1GB 内存使用

其他配置：

除非特别强调，都没限制内部操作的 I/O 带宽
除非特别强调，RocksDB 两个内存组件 128MB each
内部操作最大并发数 10
延迟每秒测一次，99th 延迟间隔 1s

RocksDB

对比对象：开启了 compaction 和 flush 的 RocksDB 和未开启内部操作的 RocksDB

关闭 flush 意味着内存组件写满之后直接被 discard
数据存储预先在磁盘上填充了完整的键集，因此，如果有必要，可以通过读取来访问持久性存储

结果表明在 50th\90th 延迟方面，两种情况都很少出现 latency spike，但是对于 99th 无内部操作的 RocksDB 基本要少 2-4 个数量级的延迟。

原因分析：内存组件填充满了阻塞了写操作，读操作又排队在写之后。

下图所示即为 write latency spike 的例子。

一开始 L1-L2 的 compaction 在并行的执行，然后客户端持续写入，L0 -> L1 也开始执行，但客户端仍然在持续写入，而 L0->L1 没法并行执行，就出现了从 14-23 这段时间内的大量压缩线程执行，但是 L0->L1 只有一个线程执行的情况
因为 I/O 资源会被平均分配，所以 L0->L1 压缩线程就变相地被减慢了，因此反过来就会造成 flush 操作被临时挂起。

下图所示，因为 flush 太慢造成内存组件很快填满，延迟显著增加。

从 t=0 开始刷新需要非常长的时间 (5秒，而典型的刷新需要1-2秒)
原因是因为这时候恰好很多压缩线程在同时执行，因为有限的可用 I/O 带宽导致 flush 很慢。

Rate-limited RocksDB

对比对象：限制内部操作 I/O 带宽的 RocksDB

下图展示了将带宽限制到 50/75/90 MB 时侯的 99th 延迟，为了便于阅读，图中只展示了尾延迟显著恶化的时间点。

结果表明分配给内部操作的带宽越高，系统能够延迟 lantency spike 发生的时间越长
然而，限制内部操作的带宽会减慢它们的速度。因此，这种方法增加了一种可能性，即在以后的某个时间点，许多压缩同时运行，争夺有限的I/O带宽。

RocksDB with increased Cm

对比对象：增大内存组件的大小来看内存 buffer 大小是否会影响 RocksDB 延迟。

增大内存组件可使用的内存为 1GB，首先分为 2 个 500MB，然后分为 10 个 100MB。我们还改变了最大的 flush 次数，用一个和十个并行的 flush 线程进行试验。

我们发现使用 10 个内存组件和 1 个 flush 线程在推迟 latency spike 方面是最有效的，因为内存吸收了更多的写操作，而且从内存到 L0 的数据流和 L0 到 L1 的数据流是比较相近的。然而，在所有这些情况中，我们迟早都会遇到尾部延迟峰值，原因与上面场景中的原因类似

TRAID

减少内部操作的开销是不足够减小资源争用的。使用 TRAID 作为代表测试，99th 尾延迟结果如下所示。TRIAD 主要通过键重叠程度来决定何时执行 L0->L1 的 compaction，推迟 compactions 到更低的层次（离内存组件更近）将会导致更高层次的 compaction 被推迟，所以长远来看 TRIAD 增加了并发压缩执行的可能性。因此客户端操作的 99th延迟在1000s 之前几乎没有发生 spike，在那之后频繁发生。

PebblesDB

下图展示了 PebblesDB 的情况，实验在 10500s 之后结束，尽管给了 PebblesDB 更多内存，还是会把分配的内存给耗尽。内存的消耗主要是因为在写敏感的负载中频繁地创建 guards 以及 bloomfilter。在正常运行期间，由于没有压缩，Pebbledb 提供了非常好的尾部延迟。换句话说，LSM 树通过使用 guards 重新构建，但没有发生数据压缩。

为了创建一个 PebblesDB 经历压缩的情况，我们在一个读密集型工作负载(95:5)下运行它，这减少了内存压力。在这种工作负载下，尾部延迟在早期仍然很好，但是在大约 8 小时后，当压缩开始时，系统实际上会停止运行。当PebblesDB必须在树的最高层次上执行非常需要资源的压缩时，它会暂停客户端操作。当这样的压缩发生时，所有用于内部操作的线程都是繁忙的，因此它们不能从树的较低层次下推 guard 和键。因此，为了维护树的完整性，PebblesDB 会暂停客户端操作，直到压缩结束。

Lessons learned

大概有三个 lessons

尾延迟的主要原因是因为内存组件被写满而阻塞了写操作

根本原因有二：

磁盘组件 L0 层满了，导致 flush 操作挂起，而 L0 满是因为 L0->L1 的 Compaction 速度没有跟上
恰好大量压缩线程在执行，因为有限的可用带宽的原因导致 flushing 很慢

简单地限制内部操作带宽不会解决 flush 时可用资源有限的问题，反而可能会加剧该现象

这个方法本质是推迟了后台 compaction 操作的进行，但长远来看增加了之后多个压缩操作同时进行的可能性
Chen Luo 等人关于 Compaction 的稳定性的研究也表明了 尽可能快地处理写操作可以最小化每次写操作的延迟。

VLDB’19 On Performance Stability in LSM-based Storage Systems

现有的提高吞吐量的方法也只是延迟了 latency spike，长远来看还是加剧了该问题

最近的方法来提高吞吐量, 如选择性开始 compaction 或只执行最高 level 的 compaction, 避免延迟 spike 在短期内发生，但从长远来看还是加剧了该问题，因为他们也增加了之后许多 Compaction 并发执行的可能性

总结

从 Lesson1 可以推断出，不是所有的内部操作都是平等的。在比较低的层次执行内部操作是很 critical 的，因为离内存组件比较近，如果不能很快地完成的话或者定时完成的话，会导致客户端操作陷入停顿

而后两个 Lessons 更多的是给的测试相关的启发，为了全面发现问题，应该适当延长测试时间，以免未发现相关问题。

SILK

SILK design principles

Opportunistically allocating I/O bandwidth to internal operations

基于一个如下所示的事实，生产环境中的负载通常是会随着时间变化的。

在客户机负载峰值期间，SILK 为更高级别的压缩分配更少的 I/O 带宽，并利用短暂的低负载时期来促进内部操作的处理。

动态 I/O 调节让 SILK 可以

限制客户端操作和内部操作之间的影响
避免长期积累过多的内部工作，防止长期超负荷的情况

Prioritizing internal operations at the lower levels of the tree

通过从 Lesson1 中学到的经验，给 flush 操作以及 L0->L1 的压缩操作引入优先执行的策略。

SILK 将内部操作分成了三种类型，根据其对客户端操作延迟可能带来的影响进行分类：

Flush 需要足够快，从而让内存及时被释放以吸收前端写，这是直接影响写延迟的操作
L0->L1 的压缩操作第二优先级，确保 L0 不会到达其容量限制，所以 flush 操作才能够顺利完成

是否可以考虑修改 L0 合并触发的条件来缓解该问题？

L1 及其以下的压缩操作为最低优先级，因为这些操作主要是为了维持 LSM 的树形结构，在短期内不会对延迟造成显著影响。

Preempting compactions

SILK 实现了新的压缩算法允许在更低 level 的内部操作抢占较高 level 的压缩操作

SILK implementation

Opportunistically allocating I/O bandwidth

使用单独的线程来监控客户端的负载情况并限制内部操作的带宽。

监控的粒度是可配置的，取决于负载的波动频率，在 SILK 中被配置为 10ms

假设 LSM KV 总可用 I/O 带宽为 T B/s，客户端请求经过监控发现使用了 C B/s，那么可分配给内部操作的带宽为 B/s，其中 ε 是一个小 buffer。为了调整I/O带宽，SILK使用了一个标准速率限制器。SILK 维护一个最小可配置的 I/O 带宽阈值以供 flush 以及 L0->L1 的 compaction，因为这些操作直接影响延迟，所以还是需要保证一直可以执行。

为了最小化与更改速率限制相关的开销，只有当当前值与新测量值之间的差异很大时，SILK 才会调整限制。作者设置了经验值阈值为 10MB/s，发现更低的阈值或造成频繁的 rate limit 的变化，ε 是为了吸收客户端负载的小波动，这些小波动没什么必要通过速率限制器来调整内部的操作带宽。

Prioritizing and preempting internal operations

LSM 内部工作都是由一个内部线程池完成的，一旦一个内部操作完成，系统通过评估 levels 的大小和内存组件的状态来检查是否需要更多的内部操作，如果需要的话，就会调度更多的内部操作在工作队列中。为了实现前面描述的优先内部操作，SILK 维护了两个 worker 线程池，一个用于高优先级的 flushing，一个用于低优先级的 compaction。

Flushing

Flush 操作有专门的线程池，且总是可以访问可用的 I/O 带宽来执行操作，选择的最小刷新带宽足以在活动内存组件填满之前刷新不可变内存组件。
SILK 现有的实现中允许两个内存组件和一个刷新线程，如果内存约束允许，使用多个内存组件和刷新线程可能有助于维持较长的客户端活动高峰。

L0 to L1 compaction

SILK 需要 L0 到 L1 的 compaction，以确保 L0 上有足够的 flush 空间。与刷新不同，这些 compaction 操作没有专用的线程池。如果需要进行 L0 到 L1 压缩，并且压缩池中的所有线程都在运行更高级别的压缩，那么其中一个线程将被抢占。这样，L0 到 L1 压缩就不会在更高级别的压缩后面等待。在当前实现中，抢占压缩任务是随机选择的。（即 L0->L1 的压缩操作会抢占别的级别的压缩线程）
L0 到 L1 压缩，就像所有内部操作一样，都要服从动态 I/O 节流，然而，这种类型的压缩永远不会暂停，即使 SILK 可能选择不为压缩提供带宽。为了保持 L0 到 L1 压缩运行，SILK 暂时将此作业移动到高优先级线程池，并通过高优先级线程保持其运行（比如和 flush 线程相同优先级）。在这种情况下，上面提到的最小 flush 带宽由 flush 线程和 L0 到 L1 压缩线程共享。由于键范围重叠导致的一致性问题，一次最多只能运行一个 L0 到 L1 压缩，因此，只有一个额外的线程被添加到高优先级线程池中。RocksDB 最近的版本支持 L0 到 L0 压缩 RocksDB Blog Level-based Compaction Changes，作为一种优化，可以快速减少 L0 上 sstable 的数量，由于这种优化有利于进行刷新，因此 SILK 将这种情况视为 L0 到 L1 压缩。

Higher-level compactions

在低优先级压缩线程池中调度高于 L1 级别的压缩。它们利用可用的I/O带宽，如动态速率限制器所示。SILK 可以单独暂停和恢复这些较大的压缩(因为 L0 到 L1 压缩抢占)，也可以在线程池级别(因为高用户负载)暂停和恢复这些较大的压缩。

L1 到 L2 压缩可能会因为 L0 到 L1 压缩所做的工作而失效，因为抢占，在这种情况下，SILK 将丢弃由高级压缩完成的部分工作。我们没有发现这种浪费的工作对性能有显著影响。

SILK 支持并行压缩，默认情况下，假定线程具有同样的压缩能力，每个线程都可以获得相似的资源共享。LSM kv 不允许从 L0 到 L1 的并行压缩，因此，如果允许许多并行压缩，那么大多数压缩线程都在更高的级别上工作。这对客户端操作延迟是有害的，因为 L0 到 L1 压缩是系统性能的关键，并且会从获取大量资源中获益。减少线程池的大小，再加上 SILK 的压缩抢占方案，允许每个内部工作线程访问更大的资源份额，从而更快地完成关键压缩。

以往推荐将压缩线程数设置为 core 数量，但是，我们发现压缩线程的数量应该取决于总驱动器 I/O 带宽和单个压缩操作所需的 I/O 带宽。例如，对于一个带宽为200MB/s的驱动器，四个内部工作线程是一个合适的选择；即使所有的线程都并行运行，它们仍然会被分配足够多的带宽来快速完成压缩操作。

目前，SILK 控制为低优先级线程池中的压缩分配的总 I/O 带宽。需要探索的一个有趣策略是，根据压缩任务的紧迫程度，在更细的粒度上为压缩分配不同数量的带宽。我们发现，当前的方法在不增加复杂性的情况下带来了良好的改进

Evaluation

Setup

RocksDB-SILK, TRIAD-SILK, RocksDB, TRIAD, RocksDB that uses the auto-tuned rate limiter

focusing on write-intensive workloads

db_bench

Measurements:

负载生成器线程根据工作负载特征在开放循环中发出请求。它们将请求保存在KV存储工作线程的队列中
延迟是在loadgenerator线程侧测量的，它同时捕捉队列时间和处理时间
测量第99百分位的尾部延迟和一秒间隔内的吞吐量(即，不是整个实验运行的累积)。

Dataset:

生产和合成工作负载的数据集大小都大约为500GB。kv元组的尺寸在生产和合成工作量之间有所不同

Config:

128MB memory component size and two memory components
flushing and L0 to L1 compactions proceed at a rate of 50MB/s if SILK paused the other internal operations
The total I/O bandwidth allocated to the LSM KV store is 200MB/s.
level0-slowdown level0-stop are configured to very large values in all data stores so as not to artificially interfere with the measured latency
thread pool of 4 threads for internal operations (including the flushing thread)
All systems are pinned to 16 cores, out of which 8 are used by the worker threads, and 8 are used by the internal operations and other LSM threads (e.g., monitoring the client load in SILK)
The load-generator threads run on separate dedicated cores.

Note: Compression and commit logging are disabled

Nutanix workload

57:41:2 write:read:scan

客户端请求以突发的方式到达(峰值约为20K请求/s)，由低活动周期(山谷约为数百请求/s或更少)分隔。山谷的典型持续时间在5到20秒之间，平均山谷长度约为15秒。大多数峰值(大约90%)是10 - 20秒之间的短脉冲。较长的峰值(>100)构成了工作负载的其余部分。最大峰值持续约400秒。

延迟下降明显，相比于 RocksDB TRAID 下降了三个数量级，相比于 AUTO-TUNED RocksDB 下降了2个数量级。当有更多的内部工作要做时，自动调优器只会增加I/O带宽，而且它与用户负载无关。

SILK中的吞吐量接近所提供的客户机负载，而RocksDB中的吞吐量波动较大。由于内部操作的干扰，客户端操作在工作线程队列中构建。当它们能够继续运行时，它们会被快速处理，从而导致吞吐量峰值。TRIAD和自动调优的RocksDB与所提供的客户机负载更接近，但吞吐量仍然存在波动，这与尾部延迟的增加有关。

显示了 Cm 不能立即刷新的次数(左图)，以及与实验持续时间相关的写入停滞时间(右图)。TRAID 因为 L0->L1 压缩策略的关系延迟 flush 的问题最严重。

展示了rocksdb - silk在生产工作负载24小时运行时的第99百分位延迟和吞吐量时间序列。

显示了在生产工作负载的200秒内，在RocksDB-SILK中的I/O带宽分配的详细信息。内部的工作可能会暂时推迟，但最终是要长期完成的。RocksDB-SILK在24小时内压缩了大约3TB的数据，而且等待调度的压缩操作从不超过3个。工作线程没有写停顿，整个实验中排队的操作少于3个。

YCSB benchmarks

SILK 对于不同分布的负载影响不大。uniform 分布下，SILK 在写密集的负载下开销最大，因为需要频繁地压缩、调度。读的话和 TRAID 差距不大，因为 L0 中每个 file 都有 Bloomfilter，在 L0 中第一次找到以后就返回了不需要见所有的 L0 的文件（注意需要按照时间先后顺序或版本信息来检索）。所以大部分时间只有 L0 中的一个文件被读取，但是 SILK 延缓了 L0->L1 的压缩会导致一定程度上对读性能的影响。

zipfan 分布下大多数请求在内存中就处理了，因此 compaction 也比较少，因此 SILK 带来的吞吐量影响也就比较少。

尾延迟下降就比较明显了

Stress testing for long peaks

Workload description.

主要基于 YCSB-A，读写50：50，其中，我们改变客户端负载峰值和谷值之间的比例(逐渐增加峰值持续时间，同时保持谷值持续时间不变)。8B key, 1024B value, uniform key distribution。低活动期间的客户端负载大约是10K operations/s，高峰期间大约是 40K operations/s。为了给系统施加压力，所提供的峰值和低谷负载都比我们的生产工作负载要高。

Results

前三行显示了一个50:50的写:读工作负载，其中峰值:山谷长度的比例是不同的:峰值持续10秒、50秒和100秒，而山谷持续10秒。SILK可以轻松地在客户机负载中维持这些峰值和低谷，从而保持低延迟和稳定的吞吐量。

在图的最后两行，我们展示了一个长峰值的实验结果，看看SILK的性能在什么时候开始下降。

第四行显示50:50写:读工作负载的结果，最后一行显示90:10写:读工作负载的结果。
尽管有关键内部工作的优先级，但如果峰值负载高且峰值持续时间长，系统无法为内部工作分配足够的资源，性能最终会开始下降。此外，正如预期的那样，写操作的比例影响峰值可维持的时间。对于90%的写工作负载，SILK的性能在大约500秒(峰值时为300秒)时开始下降，而对于50%的写工作负载，峰值可以维持到大约700秒(峰值时为500秒)。尽管表现出性能下降，SILK仍然能够处理代表真实应用程序的具有挑战性的工作负载。我们的生产工作负载最多有400个峰值，50%的写和负载峰值只达到合成工作负载峰值的一半

Breakdown

如下展示了 SILK 各种变体的性能表现。一行显示了一个版本，其中我们启用了SILK的动态I/O带宽速率限制，但禁用了优先级和抢占。第二行显示的是互补版本，它使用优先级和抢占，但I/O带宽不受控制。最后一排是 SILK。单独而言，这两种技术都不能维持客户机负载。

通过动态带宽分配，减少了内部和外部的工作干扰，然而，随着实验的进行和需要进行更大的 compaction，紧急的内部操作减慢了
良好的优先级将树结构保持在接近内存组件的级别上，允许刷新和L0 - L1压缩在不降低速度的情况下进行。然而，当需要进行更大的 compaction 时，带宽不受控制这一事实会导致内部和外部工作之间的负干扰

SILK+

Abstract

期刊 TOCS20 上发表的 extend 文章，相比于 SILK 多了一个点：separating client requests by size and by data access path。根据估计的请求处理时间以及数据访问路径来分离客户端请求。

Introduction

尾延迟的另外一个重要原因是：从操作组合和 item 大小来看，工作负载的异构性，几个计算量更大的请求会降低大部分较小请求的速度。即负载的一些内在特性。

针对较大的 KV 项或跨越多个KV项的请求(例如，范围扫描)会延迟较小的延迟敏感请求。由于 LSM KVs 的线程体系结构以及客户端操作类型之间缺乏区分，导致了这种队头阻塞。YCSB 中没有设计这种 item 大小变化的情况，固定了项的大小。就其实大量的生产环境中的负载的 KV 项大小都是会变化的，不是一成不变的。

在内存数据存储的背景下，研究了 head-of-line 阻塞的问题。相反，在持久的 KV 存储情况下，它得到的关注较少。原因是，在传统的 LSM KVs 中，工作负载不均的影响被内部操作的干扰所抵消。一旦内部操作干扰的问题被缓解，负载异构的问题就还是会显现出来。

典型的 LSM KV 工作负载包含对不同 KV 项目大小的读、写和扫描的混合。下图展示了 Nutanix 生产环境中的工作负载的分布，在Facebook、维基百科、Flickr和Memcachier的生产工作负载中也报告了类似的条目大小变化。如上所述，最先进的LSM KVs在 first-come-first-served 的基础上为客户端操作提供服务，这会导致小型操作在更耗时的请求之后被阻塞。

初步实验证明问题

导致尾部延迟的另一个重要原因(尽管在当前系统中更难显示)是工作负载不均。在最先进的LSM kv中，由工作负载异构引起的延迟被客户机请求和内部LSM工作的干扰所掩盖。

Exposing head-of-line blocking in LSM KVs

为了暴露在异构工作负载下的队头阻塞，我们在实验期间禁用了LSM内部操作。因此将不会存在 flush 和 compaction 带来的干扰。

负载：YCSB-A(R:W=50:50)，但是每一项的大小的分布是不固定的：40% small items of 1B–15B，59.9% medium items of 16B–1500B，0.1% large items of 1501B–1MB

下图 A 展示了 RocksDB 的读写操作延迟，即使没有压缩干扰，即使超过 99% 的操作都是小的(即，预期的服务时间是几微秒)，第 99 个百分位延迟也会增加 3 个数量级，达到1600微秒。高尾延迟是由于队首阻塞而发生的

Existing strategies for head-of-line blocking

之前的研究中没有人研究过 Head-of-line blocking，因为这个问题被其他导致延迟的原因给掩盖了，然而，在之前的工作中已经解决了 head-of-line blocking 这个更大的问题。在较高的层次上，有两种策略可以用来缓解头部阻塞：

Preempting operations

Preempting operations：如果操作抢占是可能的，那么客户端请求就被分配给工作线程队列，这样每个队列的请求处理时间的差异就会最大化，操作抢占是基于已知的事实，即最短剩余处理时间(SRPT)抢占策略可以最小化平均完成时间，对于具有重尾特性(具有高方差)的请求处理时间分布特别有效。这种策略在数据中心的作业调度环境中是成功的，数据中心作业和 LSM KV 操作之间的一个关键区别是操作所花费的时间。在数据中心，作业运行几秒钟，甚至几个小时，在 KVs 中，大多数操作预计在几微秒或几秒钟内完成。这些紧张的时间限制使得抢占逻辑所增加的开销在成本上难以承受，因为如果没有硬件和操作系统的特殊支持，抢占大多数操作是不可能的

Grouping operations

Grouping operations：如果不可能抢占，则将请求分离到队列中，以便使每个队列的请求处理时间变化最小。操作分组基于Pollaczek-Khinchine公式，该公式指出，在一般情况下，请求完成时间与请求处理时间的方差成比例。在此基础上，已经开发了几种大小间隔任务分配(SITA)调度策略，根据估计的处理时间将请求分离到不同的队列中。这种方法在内存中的KVs中得到了成功的应用。估算处理时间的一个流行策略是将处理时间与项目大小(即需要读或写的数据量)关联起来。但是，如果也访问磁盘，这种策略就不会成功，这在大多数LSM KV工作负载中都是如此

Existing strategies not suitable for LSM KVs

为了证明现有的内存中KVs方法在持久化KVs中是无效的，我们在RocksDB上运行了一个实验，其中工作负载适合内存，工作负载需要访问磁盘。我们可以在内存设置中复制现有的结果——因为所有的服务都是从内存提供的，所以请求大小可以很好地估计请求处理时间。然而，在磁盘上，单凭请求的大小并不能很好地反映请求成本。请求可能需要访问磁盘，这比仅从内存提供请求要昂贵得多。

图9(b)显示了 RocksDB 和区分了请求大小的 RocksDB 的第99百分位数读写请求延迟。在这两种情况下都禁用了压缩。由于读写请求的访问模式不同，按大小分开请求在LSM KVs中没有区别。写在内存中完成，而一些读需要转到磁盘。相反，如果整个工作负载适合内存，此策略可以将尾部延迟减少35%，因为数据访问路径不再影响延迟(图9(c))

简而言之就是因为磁盘访问的开销导致现有的请求调度策略带来的收益并不明显

Lessons

多了一个 lesson: 现有的在异构工作负载情况下改善尾部延迟的方法在LSM KVs域中并不有效。

SILK

Principles

主要多一条：为客户端请求服务的磁盘访问不应该阻塞其他可以在内存中完成的客户端请求。

Client request separation：SILK+实现了一个新的客户端请求分离机制，该机制根据请求的估计处理时间将其放置到不同的工作线程队列中。SILK+实现了一种新的技术来估计处理请求的时间。SILK+的技术与现有的方法不同，它考虑了请求的大小(即请求写入或读取的字节数)和数据访问模式(即请求是从内存还是磁盘提供的)。

简而言之就是 SILK+ 设计了一种新的基于负载请求特性的且应用在 LSM KVs 的 IO 调度策略

Implementation

相比于 ATC19 多了一些伪代码

Opportunistically Allocating I/O Bandwidth

SILK+ 持续监控客户端操作所使用的带宽，并将可用的剩余I/O带宽分配给内部操作(算法1，第6-18行)。客户机负载监视和速率限制由单独的 SILK+ thread处理。监视粒度(SILK_SLEEP_TIME)是一个系统参数，它取决于工作负载中的波动频率;SILK+中的监控粒度目前配置为10毫秒。

如果LSM KV存储可用的总I/O带宽是 T B/s，则SILK+测量带宽客户端请求使用的 C B/s 模式，它不断调整内部操作带宽到 I=T−C−ϵ B/s。为了调整 I/O 带宽，SILK+使用了一个标准速率限制器，它有一个基于令牌的实现 RocksDB Rate Limiter，SILK+维护了用于刷新和L0到L1压缩的最小可配置I/O带宽阈值，因为这些操作直接影响客户端延迟。

为了最小化与更改速率限制相关的开销，SILK+仅在当前值与新测量值之间的差异显著时才调整限制(算法1，第9行)。我们根据经验将这个阈值(BW_CHANGE_THRESHOLD)设置为10 MB/s。我们发现，较低的阈值会导致频率限制的过度频繁变化。ϵ 的作用是考虑到客户端负载的微小波动，这些波动不足以用速率限制器调整内部操作带宽。

Prioritizing Internal Operations

回想一下，在LSM KVs中，内部工作是由内部工作线程池处理的。一旦刷新或压缩完成，系统将通过评估级别的大小和内存组件的状态来检查是否需要更多的内部工作。如果需要，将在内部工作队列中调度更多的内部工作任务。SILK+维护三个内部工作线程池:一个高优先级的池用于刷新，一个中等优先级的池用于L0到L1压缩，以及一个低优先级的池用于更高级别的压缩(算法1，第1 - 3行)。带宽通过令牌控制，令牌通过I/O带宽速率限制器跟踪 RocksDB Rate Limiter

Flushing: 最高优先级，刷新有它们专用的线程池，并且总是能够访问内部操作可用的I/O带宽。选择的最小刷新带宽足以在活动内存组件填满之前刷新不可变内存组件。SILK+的当前实现允许两个内存组件(即一个不可变组件和一个活动组件)和一个刷新线程。如果内存约束允许，使用多个内存组件和刷新线程可能有助于维持较长的客户端活动高峰。

L0 to L1 compaction:

SILK+ 需要L0到L1的压缩，以确保L0上有足够的 flush 空间。L0到L1压缩有一个专用的中等优先级线程池。当调度程序分配I/O带宽时，L0到L1压缩优先于更高级别的压缩(算法1，第21-29行)。
和所有内部操作一样，L0到L1压缩也需要动态I/O节流。然而，这种压缩从来不会暂停，即使在SILK+严重限制内部操作上的I/O带宽以对用户请求进行优先级排序的情况下，这种压缩也会以最小的带宽运行。在这种情况下，上面提到的最小带宽由刷新线程和 L0 to L1 compaction 共享。由于键范围重叠导致的一致性问题，最多一次只能运行一个L0到L1压缩。在内部工作I/O带宽的极端限制下，flush线程和L0到L1压缩线程平均共享最小带宽。RocksDB最近的版本支持L0到L0压缩，作为一种优化，可以快速减少L0上sstable的数量。由于这种优化有利于进行刷新，因此SILK+将这种情况视为L0到L1压缩。

Higher-level compactions: 在低优先级压缩线程池中调度高于L1级别的压缩。它们利用可用的I/O带宽，SILK+可以在线程池级别暂停和恢复这些较大的压缩(因为用户负载很高)。

Client Request Separation

SILK+的客户端请求分离策略依赖于以下原则:

(P1) 在执行客户端请求分离时，同时考虑请求大小和数据访问路径;
(P2) 大的请求不应该被饿死或删除以减少延迟;
(P3) 保持所有工作线程都处于忙碌状态比实现完美的负载平衡更重要。

SILK+定义了以下类型的请求: 拆分基于对典型工作负载的分析

(1) 小的内存请求(例如，可以在内存组件中完成的写和读请求;SHORT_WRITE和SHORT_READ，如算法2所示);
(2) 大的内存请求(例如，写和读可以在内存组件中完成;如算法2中的LONG_WRITE和LONG_READ);
(3) 持久存储请求(即从磁盘组件读取和扫描，如算法2中的DISK_READ)。

但是，如果有必要，可以将此方法一般化，以包含不同的或更细粒度的分割。例如，SILK+可以使用更自动化的方法来确定分割。参考一些分类方式

NSDI2019：Size-aware sharding for improving tail latencies in in-memory key-value stores
TPDS05: Workload-aware load balancing for clustered web servers

每个工作线程都有自己的请求队列，专门化一种类型的请求(例如，只服务简短的写)。这种方法的一个优点是工作线程之间不需要同步。然而，可能会出现资源利用率不足的问题：根据工作负载，一些工作线程可能是空闲的，这与 P3 相矛盾。为了避免这种问题，SILK+使用负载平衡器，它

(1) 实现将用户请求分配给队列的逻辑
(2) 负责确保所有工作线程都处于繁忙状态。工作线程只需要服务其队列中的下一个请求(算法2，第37-42行)。负载平衡器静态地为每个工作线程分配一个类关联。假设一个类型为C的用户请求R到达控制器。R的处理方法如下：

(1) Preferred queue 优先队列。如果有一个与类 C 有亲缘关系的空队列 Q，则将 R 添加到 Q 中(算法2，第15-21行)
(2) All queues full 所有队列已满。如果所有队列(包括与类C没有关联的队列)至少有一个请求进入队列，则 R 进入与类 C 有关联的最空队列(算法2，第33-35行)。
(3) Work stealing 工作窃取。如果所有与 classC 有关联的队列都不是空的，但是有另一个队列 Q' 是空的，并且与一个处理时间比 C 更昂贵的操作类有关联，那么R将发送到 Q'。否则，我们继续进行情况2(算法2，第25-31行)。

工作窃取算法确保工作线程一次只能窃取一个请求，因为它们的队列需要为空才能发生工作窃取。因此，工作线程队列中不会出现无关联的请求堆积。

该算法还确保关联类中的请求不会在关联类之外的请求之后等待多个操作。最后，如果一个具有亲和性的请求 R_A 在一个没有亲和性的请求之后等待，那么总是比短。例如，长时间扫描不可能被与短写有关联的工作线程窃取。

Queue assignment strategy

对于读请求，负载平衡器事先不知道读KV项的大小。为了对读请求进行分类，负载平衡器乐观地假设所有读都是内存中的短读(算法2，第6-11行)。当读取被处理时，KV存储检查KV项是否存在于内存中。如果是，并且值大小很小，则请求完成。如果没有，请求返回给负载均衡器，并指示是否在内存中没有找到KV项目(即请求需要转到磁盘)，或者是否在内存中找到了KV项目，但这个值很大。然后，负载平衡器将读请求重新调度到适当的队列。对于写请求，负载均衡器很容易将它们分配到正确的队列，因为当请求到达时，更新大小是已知的。

Evaluation

多了一个测试

图19显示了Nutanix工作负载中SILK+的第99百分位延迟。我们比较SILK+有三个版本的RocksDB——原始的RocksDB、按大小分隔请求的RocksDB(与SILK+执行大小分离的方式相同)，以及将读和写请求分隔到不同队列的RocksDB。所有版本的 RocskDB 都在禁用压缩的情况下运行，因为压缩造成的干扰太大，无法注意到这些更细微的延迟变化。SILK+在启用所有内部操作的情况下运行，因为机会I/O分配和内部操作优先级减轻了压缩干扰。在本实验中，将扫描请求视为多次读取。

Others

https://github.com/facebook/rocksdb/wiki/Rate-Limiter

RocksDB Rate Limiter源码解析