ATC’23 Calcspar

• ATC’23 Calcspar: A Contract-Aware LSM Store for Cloud Storage with Low Latency Spikes

TLDR

• 面向特定场景：云存储 EBS，IOPS 合约，主要优化尾延迟

• 方案：
• IOPS Stabilizer for EBS 类似于令牌桶的机制限制 IOPS 的使用
• Congestion-Aware IOPS Allocating 多队列+时间窗口，本质是一个多优先级队列来执行 I/O
• Fluctuation-Aware Caching 忙时被动 LRU，闲时主动预取
• Opportunistic Compaction 不同层级 Compaction 赋予不同优先级，限制突发 I/O

Abstract

• 云存储越来越受欢迎，因为它的即用即付等特性显著降低了存储成本。然而，社区对其合约模型和延迟特性的探索还不够充分。随着基于 LSM 树的键值存储(LSM存储)成为许多云应用程序的构建块，云存储如何影响键值访问的性能至关重要。本研究揭示了Amazon Elastic Block Store (EBS) 在不同 I/O 压力下的显著延迟差异，这对 LSM Store 在云存储上的读取性能提出了挑战。为了减少相应的尾部延迟，我们提出了用于云存储的 Calcspar、合约感知LSM 存储，它通过调节对云存储的 I/O 请求速率和使用数据缓存吸收多余的 I/O 请求，有效地解决了这一挑战。我们专门开发了一个波动感知缓存来降低工作负载波动带来的高延迟。此外，我们构建了一个拥塞感知 IOPS 分配器，以减少LSM 存储内部操作读取延迟的影响。我们在 EBS 上使用不同的实际工作负载评估了 Calcspar，并将其与最先进的存储进行了比较。结果表明，Calcspar 可以在保持正常读写性能的同时显著减少尾部延迟，将第 99 百分位延迟保持在 550us 以下，并将平均延迟减少 66%。

Introduction

• 近年来，许多企业和组织将其数据转移到云端的趋势推动了云存储的发展。这是由于云存储的高级特性和成本效益。例如，Amazon Web Services (AWS) 是世界上采用最广泛的云平台，它在按需付费的基础上提供了各种具有高可伸缩性和可靠性的存储服务(例如，Elastic Block Store, EBS)，这使它们更具吸引力。另一个重要的趋势是基于 LSM 树的键值存储，如RocksDB、LevelDB、Bigtable、Dynamo 和 TiDB，正在成为许多云应用的构建模块。但是，现有的 LSM 存储都没有针对云存储进行优化，以消除长尾延迟。值得注意的是，平衡估计的峰值性能与云存储性能预算(例如，IOPS) 是具有挑战性的。尽管许多云存储提供商宣传弹性存储 volumes 可以适应不断变化的性能需求，但这些 volumes 的扩展能力无法适应不可避免的流量波动。例如，AWS EBS 只支持增加购买的 IOPS，这需要数小时甚至数天才能完成。因此，面对短期的负载变化，仅仅依靠弹性 volumes 进行及时调整是不切实际的。

• 为了理解云存储如何响应流量波动，我们研究了AWS EBS 卷的延迟特性。结果表明，EBS 保证了一种称为服务水平协议 (SLA) 的服务协议，如果访问不超过付费 IOPS，则每个请求的处理延迟都在适当的阈值范围内。我们观察到，当一个时间窗口内的需求超过 IOPS 协议时，每个连续请求的处理延迟会急剧增加。此外，云存储的合约模型表明，付费 IOPS 越高，延迟越低。但是，这种协议受到 IOPS 预算的限制，如果 IOPS 被透支，自然会影响延迟方面的性能。

• 云存储中有限的 IOPS 导致的延迟峰值严重影响 LSM 存储上对延迟敏感的应用程序的性能。我们以部署最广泛的 LSM 存储实现之一 RocksDB 为例。RocksDB 首先写入内存表(memtable)，以便以合理的低延迟快速响应。直到内存中的表被填满，RocksDB 然后将表持久化到大块写(例如，sstable)的存储卷中，从而将随机写聚合为顺序写。这种写方案减少了写请求的数量，实现了较高的写吞吐量。然后，它使用内部压缩机制将传入的数据合并到多个级别的磁盘表中。虽然内部压缩操作保证了每一级数据的有序性，从而提高了查找性能，但是一个读操作仍然需要遍历多个级别，从而导致读放大。由于云存储卷上的 IOPS 有限，因此 RocksDB 的读性能会受到很大的限制。

• 在 LSM 存储中避免读延迟峰值有几个挑战。
• 首先，读请求性能波动很大，因为云存储容量不够灵活，无法及时跟上工作负载的变化。工作负载波动导致 LSM 存储访问云存储卷的读 I/O 数量变化较大。当 I/O 数量超过云存储卷的付费 IOPS 时，请求延迟会增加。
• 其次，LSM 存储中的读放大进一步加剧了工作负载的波动。多级数据布局不可避免地会导致读取放大问题，例如在 LSM-Tree L0 级别发现的问题需要遍历多个表，因此读取单个键值对可能会生成多个 I/O。
• 第三，云存储卷的速度限制机制与 LSM 存储内部的多线程并发机制相冲突，云存储卷上多线程之间的请求拥塞导致延迟数倍增加。
• 第四，LSM 存储的内部固有机制加大了对云存储卷读延迟的损害。不规律的 flush 操作或不确定大小的压缩操作会导致访问云存储卷的 I/O 数量突然增加，导致尾延迟高。
• 最后，为了获得更好的尾部延迟，成本和性能之间的权衡会成倍地增加成本，从而导致严重的资源浪费和有限的吞吐量改进。

• 对于上述挑战，一个自然的解决方案是与云存储容量签订更高的 IOPS 预算，确保 LSM 存储的 I/O 数量不超过付费IOPS，以保持最佳延迟。然而，这增加了成本。此外，实际生产环境中的峰值 IOPS 需求很难预测。相反，我们的目标是在特定 IOPS 预算下探索 LSM 存储的最佳性能。

• 本文介绍了 Calcspar，这是一个基于 Amazon EBS 的云存储容量合约感知 LSM 存储，具有较低的延迟峰值，并且可以容忍外部工作负载波动和内部操作争用。Calcspar 首先采用波动感知缓存，它结合了 hotspot-aware 主动预取和位移感知被动缓存，以适应不断变化的工作负载。预取策略在高负载期间识别热点，在低负载期间主动提取热点，从而平滑外部负载变化。然后，在高负载期间，被动缓存利用临时局域性挤出陈旧的预取数据，并在不发出额外请求的情况下适应热点变化。然后，Calcspar 利用一个感知拥塞的 IOPS 分配器为不同的内部请求分配优先级，并避免由于有限的 IOPS 预算而增加的延迟。分配器使用多队列节流结构来防止线程拥塞。然后，机会性压缩将不同 LSM 级别的写请求分配到不同的优先级队列中，从而平衡读放大和写节流。本文的贡献包括：
• 1) 我们对云存储卷的性能进行了深入的分析，这首先说明了延迟和负载压力之间的不成文契约。
• 2) 基于观察结果，提出了云存储卷的限速性能模型，并通过实验验证了该模型，揭示了获得最佳延迟的机会。
• 3) 我们提出的 Calcspar 更适合 AWS 云存储卷，其中 IOPS 预算对性能至关重要，并且显着降低了 LSM-Tree 的尾部延迟。

云存储性能建模

云存储的合约模型

• 云存储提供商(如AWS)为用户提供各种具有成本效益的存储卷，以满足他们的独特需求并适应不断变化的市场。表 1 给出了云存储的合同模型，说明了相应卷类型的价格和性能关系。该定价基于 2022 年 7 月A WS 东北-2地区的块存储[3,4]。合约模型表明，IOPS 价格越高，对应类型的时延越低。因此，用户需要根据自己的需求选择合适的存储容量和 IOPS 预算。但是，付费 IOPS 只能保证返回 I/O 的数量，而不能保证最优延迟。此外，EBS 性能扩展只支持增加付费 IOPS，并且需要数小时到数天才能生效。当负载超过 IOPS 时，如何响应请求还没有达成一致。因此，相应的延迟特性通常被现有的 LSM 存储所忽略。

Unwritten Latency Performance

• 为了揭示隐藏的延迟特征并理解上述合约模型如何影响 LSM 存储的性能，我们首先在云存储卷上进行了一系列实验，然后提出了一个性能模型。

• 实验 1：不同 I/O 压力下时延的累积分布函数(CDF)。我们通过在不同压力下发送 4KB 随机读请求来测量 EBS 卷 gp2、gp3、io1 和 io2 的延迟，每个卷支付 3000 IOPS。我们使用 fio 通过控制提交 IOPS (即每秒提交给EBS的I/O数量)的大小来调整 I/O 压力。然而，云存储卷处理的 IOPS 不会超过付费 IOPS。图 1 显示了支持以下两个发现的延迟 CDF 结果。
• 当 I/O 压力超过付费 IOPS 时，延迟会明显增加。相反，当提交 IOPS 低于付费 IOPS 时，它们的平均延迟性能要好得多。例如，io2 的平均延迟甚至达到 100μs。
• 在考虑表 1 时，IOPS 预算与成本成正比。成本稍高的 io2 具有最好和最稳定的延迟。最便宜的 gp3 (最初提供 3000 IOPS) 的延迟性能远低于其他三种 EBS 类型。

• 实验 2：有限的 IOPS 预算。在本实验中，我们探讨了不同IOPS预算下的延迟 CDF。我们在两个不同的压强下计算一个 io2。请求延迟分布如图 2 所示。结果表明：与付费IOPS无关，提交 IOPS 超过付费 IOPS 时的访问时延比未超过付费 IOPS 时的访问时延大5倍以上。当提交 IOPS 不超过对应的付费 IOPS 时，第 99 百分位延迟小于 270μs。但是，当提交 IOPS 超过付费 IOPS 时，访问时延会增加到 1000 ~ 11000μs。这些长尾延迟会降低用户体验

• 实验 3：延迟峰值升高。为了探索高 I/O 压力下延迟峰值背后的原因，我们严格控制了 1000 iops io2 卷的单线程 I/O 发送速率。每个请求的延迟时间如图 3 所示。第 1 秒，当提交 IOPS 不超过付费 IOPS 时，时延小于 200μs。第二秒，提交 IOPS 为 1600，前 1000 个请求的延迟与第一秒相同。但是，其余 600 个请求的延迟明显增加到 1000μs 左右，相当于每秒1/IOPS。第5秒的提交 IOPS 是付费 IOPS 的2倍，前 1000 个请求可以获得较低的延迟，后1000 个请求的延迟再次变为 1/IOPS 秒。虽然提交 IOPS 下降到 1000，但后续请求的时延仍然很高。直到我们在第 14 秒暂停工作负载并在第 15 秒恢复它，延迟才会恢复。
• 我们推测观察结果背后的原因是由于 EBS 内部的速度限制机制，它通过透支下一个 1 秒的 IOPS 来处理当前多余的 I/O，同时，惩罚性的改进延迟是 1/IOPS，以防止超出支付的请求继续得到响应。
• 例如，第 2 秒内最后 600 个 I/O 请求从第 3 秒开始消耗 600 IOPS。因此，只有剩下的400个(=1000-600) 可以在第三秒内快速送达。当在第 14 秒内没有发送 I/O 请求时，透支将被还清。因此，延迟在接下来的 15 - 19 秒内恢复到较低的水平
• 由于云服务的资源是按使用付费的，因此云存储提供商使用这种机制来维护 SLA，以防止用户不断获得超出其支付的收益。同时，通过增加延迟，从用户的角度继续操作;因此，没有机会召回服务。

• 实验 4：线程阻塞。在这个实验中评估了线程数对延迟的影响。将两个不同的 I/O 压力发送到具有不同线程数的每个 io2 卷。请求平均延迟如图 4 所示。当提交 IOPS 不超过付费 IOPS时，平均延迟保持在 120μs 左右，不随线程数增加而增加。但是，当提交 IOPS 大于支付 IOPS 时，访问时延首先增长到 1/IOPS，并随线程数线性增长。这一现象与排队论一致，因此我们根据排队论的知识推测如下:
• 请求在进入 EBS 时排队，队列大小等于付费 IOPS。EBS 中的延迟将遵循以下两个规则:
• 1) 当提交 IOPS 低于付费 IOPS 时，每个请求的延迟将在阈值附近，具体取决于 EBS类型。
• 2) 当提交 IOPS 超过付费 IOPS 时，响应时间 W 符合排队方程 W = L/A，其中 A 为付费 IOPS, L 为线程数。

EBS 延迟模型

• 假设 EBS 卷有一个缓冲队列(称为 I/O 域)来维护请求，其中队列长度等于付费 IOPS。当请求到达时，I/O 域在队列中分配一个空闲槽。然后，EBS 从 I/O 域中提取请求以迅速执行它们。当响应的请求数量超过支付 IOPS 时，EBS 停止获取新的请求。因此，挂起的请求将被阻塞，直到 EBS 能够恢复服务为止。在多线程工作负载下可能发生拥塞，尽管所有线程在一秒钟内提交的请求总数估计不高于预算。这是因为线程调度的不确定性会更频繁地触发一些工作线程，从而意外地透支预算。这样的透支会导致随后的请求被阻塞，从而导致每个请求的延迟明显增加

• 透支的规则。EBS 控制请求的响应速度，以管理 I/O 域的旋转。具体来说，我们使用 token 描述了 EBS 的速度控制机制。每个云存储卷保留一个令牌桶和一个借阅池 borrowing pool，其中包含与支付 IOPS 相同数量的令牌。用户请求首先从令牌桶中获得常规令牌。如果桶中没有令牌，则必须从借款池 borrowing pool 中获取透支 overdraft 令牌。EBS 确保携带常规令牌的请求能够快速返回。相反，带有透支 overdraft 令牌的请求处理缓慢，以确保用户不会使用太多 IOPS 来维护 SLA。EBS 以每秒 IOPS 令牌进行补充，这些令牌在借阅池 borrowing pool 中按优先级排列。

• 上述 EBS 延迟模型解释了上述关于云存储延迟的发现(#1和#2)和推测(原因#1和#2):
• 1) 当提交 IOPS 不超过付费 IOPS 时，请求获得常规令牌并快速返回，线程之间的请求不会阻塞，因此获得最佳延迟。
• 2) 当提交 IOPS 超过支付 IOPS 时，部分请求获得透支令牌。
• 3) 当返回速度低于请求到达速度时，未处理的请求将填满 I/O 域槽，并通过先补充借用池来进一步补充令牌，使高延迟状态持续较长时间。
• 4) I/O 域的线程间阻塞导致用户感知延迟增加。

RocksDB 性能建模

IOPS 限制下的 RocksDB

• 正如上述性能模型所示，云存储更多地强调延迟和 IOPS 的限制，而不是带宽。证据是允许的请求大小相对较大，并且增加 IOPS 预算是昂贵的。这样的合约和性能模型适合带宽敏感的工作负载；然而，它不适合许多延迟敏感和请求繁重的工作负载。例如，我们的分析表明， RocksDB 中的数据写入和压缩在云存储上工作得很好，因为它的请求大小更大，请求数量有限。但是，由于 IOPS 预算有限，严重影响了 RocksDB 的读性能。许多使用 RocksDB 服务元数据索引的应用程序期望具有出色的读吞吐量以及低而稳定的读延迟。不幸的是，如果底层设备是云存储，它们将无法实现其目的。

• RocksDB 在云存储上不能很好地工作，因为它的 LSM-Tree 通常是一个写优化的索引结构，而不是为了减少读 I/O 的数量而进行调优。此外，LSM-Tree 的层次结构导致许多读请求需要访问索引表的多个级别才能找到相应的键。相反，写操作可以在一个后端请求最终到达云存储之前被缓存并聚合成大块。如图 6 所示，我们对具有不同付费 IOPS 的 io2 存储卷执行读写压力测试。随着 IOPS 的增加，读吞吐量增加，写吞吐量保持不变。因此，在云上部署 RocksDB 时，通常云存储卷的最大带宽为 1000MB/s 就足够了。但是，RocksDB 读 I/O 很容易反复达到 IOPS限制，导致 tail latency 升高。

避免延迟峰值的挑战

• 本小节详细介绍在云存储中优化 RocksDB 读性能时遇到的几个挑战。为了分析性能，我们使用了 Facebook 最新的基准 Mixgraph[12]，它综合生成了准确代表真实平台负载波动的键值请求

• 挑战 1：读取延迟波动很大，因为云存储不够灵活，无法满足不断变化的需求。在本实验中，我们在单个线程中向 io2 卷发送波动读请求。为了减少开销，io2 存储卷的付费 IOPS 为波动请求的平均值。从图 7 的实验结果可以看出，RocksDB 受云存储卷的延迟特性影响较大。当QPS (client queries per second)超过付费 IOPS 时，正在执行的 QPS (黑线下的白色部分)可能会在短时间内超过付费 IOPS，这是由透支规则造成的。然后执行的 QPS 将下降到付费IOPS，并且用户感知的延迟明显高于低负载时。这还会导致用户的过多请求不被执行(图 7 顶部的红色部分)，并且它们将被阻塞。随着客户端请求数量下降到付费 IOPS 以下，延迟下降到最低水平，这会导致另一个问题，即付费 IOPS 在低负载期间被浪费，如图 7 中绿色部分所示。

• 挑战 2：LSM-Tree 中的读放大进一步增强了负载波动。RocksDB 的写聚合和分层数据布局导致了显著的读 I/O 放大。如图 8 所示，实际 IOPS 约为提交 IOPS 的 3 倍，放大了负载的波动性，当访问 I/O 超过付费 IOPS 时，请求延迟会很高。此外，L0 和 L1 级别占用的数据量很小，但占 I/O 访问的近 1/3

• 挑战 3：线程I/O竞争。多个线程之间的请求在 I/O 域中拥塞，导致尾部延迟成倍增加。我们用 10 个线程发送与图 7 中相同的QPS。图 9 中的结果显示，与单线程相比，高负载下的延迟增加了 10 倍。这是因为每秒发送到 io2 的请求越多，请求返回的速度就会比进入 I/O 域的请求慢。当 I/O 域满时，请求在每个线程上排队，因此延迟感知是线程的倍数。

• 挑战 4：大容量写阻塞。我们发送了一些写请求，同时保持读 QPS 不变，以测量写操作对用户读请求的影响，结果如图 10 所示。在第 70 秒，RocksDB 启动了压缩 Compaction 操作，占用了更多的 IOPS，导致部分用户的请求进入队列等待。因此，第 99 个百分位数的延迟突发为 40ms。其次，在第 300 秒，即使在低负载的情况下，RocksDB 内部也会发起一些 Compaction 操作，阻塞用户请求，造成高延迟。

• 挑战 5：性能 vs 成本。我们选择负载的最高 QPS 和最低 QPS 的平均值作为基准成本来衡量RocksDB 在相同负载下选择不同成本的存储卷时的性能。图 11 中的结果显示，随着成本的增加，虽然延迟似乎减少了，但由于严重的资源浪费，吞吐量并没有提高。

Calcspar Design

• 要构建充分利用云存储卷的最佳延迟的 LSM 存储，必须解决由观察到的透支规则和线程 I/O 拥塞引起的高延迟。我们建议 Calcspar 以经济有效的方式研究 LSM 存储的最佳延迟，而不是简单地增加费用来提高存储卷的付费 IOPS 以避免透支和拥塞。由于每秒可用的 IOPS 数量有限，Calcspar 在图 12 中的四种设计整体上回答了有关获得最佳延迟的问题:
• (1) 如何平滑高于付费 IOPS(§4.1和§4.3)的 I/O 平台。
• (2) 如何为用户和 LSM 内部 I/O 请求获取每秒最多可用 I/O(§4.2和§4.4)。

IOPS Stabilizer for EBS

• Calcspar 首先旨在防止 EBS 的延迟波动。正如§2.2中所讨论的，透支规则不会提高吞吐量，但会在高请求压力下提高 EBS 的处理延迟。一旦 EBS 进入透支状态，应用程序就不能提取任何挂起的请求，因此失去了进一步优化的机会，只能等待。Calcspar 不是被动地检测意外的延迟峰值，而是通过只提交具有最高优先级的请求来主动控制高负载期间的 I/O 数量。为了实现这一点，Calcspar 采用了观察到的 EBS 延迟模型(§2.3)。

• 图 13 详细介绍了 IOPS 稳定器，它控制请求速率以匹配 EBS I/O 预算，从而消除了透支延迟峰值。其本质是将令牌速度限制机制模仿到上层应用程序，该机制在 EBS 内部被广泛忽略。我们要求每个请求在访问 EBS 之前必须获得一个令牌。每秒刷新令牌的数量由付费 IOPS 决定。通过控制令牌的数量，Calcspar 保证发送到 EBS 的请求不会超过支付的 IOPS，因此 EBS 的处理延迟可以保证在几十微秒内。因此，一旦请求成功获得令牌，应用程序可以期待更稳定的延迟

Congestion-Aware IOPS Allocating

• Calcspar 的第二个目标是消除线程间请求拥塞造成的延迟峰值。为了最小化云存储成本，我们假设付费 IOPS 只保证满足平均使用率的 I/O。因此，由于 IOPS 稳定器提供的令牌有限，现代 LSM 存储所采用的多线程设计将不可避免地造成拥塞。许多工作通过调整 I/O 堆栈或利用多设备并行性来优先执行对延迟敏感的 I/O[11,20,26]。但是，它们不能阻止不那么关键的 I/O 请求在每个时间段(例如一秒钟)占用宝贵的可用令牌。为了解决这个问题，Calcspar 使用不同优先级的多队列和时间窗口策略，以确保关键请求不会偶尔被阻塞，并以最佳方式提供服务。

多优先级队列

• Calcspar 采用多优先级队列机制对不同的 I/O 请求进行分类，并根据动态时间窗口策略分配 I/O 令牌。Calcspar 将直接影响 LSM 存储的 I/O 视为用户感知请求，并将不会立即妨碍用户请求的 I/O 分类为非用户感知请求。用户感知请求主要用于响应前台用户请求，因此 Calcspar 将它们放在最高优先级队列中。非用户感知请求主要来自 LSM 后台任务(例如，压缩和预取)。由于不同的后台任务对读/写放大的影响不同，Calcspar 将它们分配到中优先级或低优先级队列。例如，预取请求进入最低优先级队列。注意，后面会进一步区分压缩请求

动态时间窗口策略

• Calcspar 采用动态时间窗策略优化每秒付费 I/O 的利用率。在此策略下，时间窗口表示一秒内的一段时间，在此期间，Calcspar 以最佳努力为基础授予获取令牌的请求，因此窗口的大小与队列的优先级相匹配。队列的时间窗口在每一秒周期的尾部对齐，使 Calcspar 能够优先处理来自高优先级队列的 I/O，而不是来自低优先级队列的 I/O。这确保了优先处理来自最高优先级队列的请求，从而最大限度地减少了它们被中低优先级请求阻塞的可能性。具体来说，Calcspar 总是为高优先级队列分配一秒钟的时间窗口。对于其他队列，Calcspar 根据前一秒分配的令牌动态调整它们的时间窗口大小，使用公式 Allocated_IOPS / Paid_IOPS。例如，在一秒的时间段内，Calcspar 分别将时间窗口 [0,1)、[0.7,1) 和 [0.9,1) 分配给高优先级队列、中优先级队列和低优先级队列。在这种情况下，时间窗口 [0.9,1) 表示低优先级队列中的请求直到第 0.9 秒才能获得令牌。相反，具有时间窗口 [0,1) 的高优先级队列中的请求有资格在到达时竞争令牌。

Fluctuation-Aware Caching

• 考虑到 LSM 存储的读 I/O 放大问题会在 EBS 上引起明显的延迟峰值，因此，在工作负载较重时，EBS 延迟感知缓存在平坦化对 EBS 的 I/O 请求平台以及在工作负载较轻时提高付费 IOPS 利用率方面发挥了重要作用。我们发现很少有现有的缓存方案是为此目的而设计的，而且它们的设计指标没有考虑底层 EBS 的可用付费 IOPS。当工作负载波动时，这将显著影响最佳缓存策略的选择。

热点感知的主动预取

• 当工作负载较轻时，Calcspar 消耗空闲的付费 IOPS，通过预取 SSTable 来换取更好的缓存命中率。Calcspar 以 EBS 块为单位管理数据(例如，256KB，这是 EBS 对一个 I/O 请求允许的最大大小)，这确保了每个预取 I/O 读取尽可能多的数据。然后，Calcspar 维护一个全局表，使用基于访问历史的指数平滑算法来跟踪 EBS 块的热度。此外，Calcspar 定期和主动地重新加热频繁访问的 LSM 顶层(例如 L0 和 L1) 数据，因为 LSM 以自上而下的方式存储检索的键值对。

感知移位的被动缓存

• 当工作负载很重时，EBS 延迟感知的缓存应该最小化对 EBS 的 I/O，同时提高空间效率。在这种情况下，Calcspar 被动地管理缓存空间。Calcspar 细化了以 4KB 为单位的缓存空间管理，并使用 LRU 策略来提高空间效率，因为清除任何数据都可能因为与用户请求访问 EBS 竞争一个 I/O 而受到惩罚

缓存集成

• Calcspar 集成了上面介绍的两种缓存策略，并根据工作负载在它们之间进行切换。这两个策略管理相同的缓存空间，但在任何时候，只有一个是活动的，并清除数据。当最高优先级队列请求消耗超过 95% 的令牌时，Calcspar 认为工作负载很重，并激活 shift 感知被动缓存策略。否则，Calcspar 将使用 Hotspot-Aware 主动预取策略获取可用的付费 IOPS。值得注意的是，全局表的内存开销可以忽略不计，因为 1GB的数据需要大 约64KB 的内存。此外，在低负载期间，由粗粒度热点感知主动预取造成的最小缓存污染不会导致整体性能下降。这是因为只有频繁访问的数据(称为热数据)是基于历史访问模式加载的。此外，考虑到低负载期间可用的充足 IOPS 预算和云存储一贯的低延迟，缓存丢失造成的损失可以忽略不计。

Opportunistic Compaction

• Calcspar 的最后一个目标是修复 LSM 压缩 I/O。在启动压缩后，它对至少两个 SSTable 的批量读操作和至少一个 SSTable 的写操作将与用户 I/O 请求竞争。另一方面，LSM 存储逐级检索键值对，并以写时复制的方式合并 sstable，为 Calcspar 提供了在不同级别上区分压缩作业的 I/O 的机会，从而减轻了 LSM 压缩操作对付费 IOPS 的竞争。对于显著影响读 I/O 放大的 L0 sstable, Calcspar 优先对它们进行压缩。对于 L1 和 L2 sstable, Calcspar 将它们的压缩 I/O 放到中等优先级队列中，在那里它们被随机处理。对于 L2 以下级别的 sstable, Calcspar 将这些压缩I/O 分配给最低优先级队列，因为短期延迟对性能没有明显影响。

Evaluation

• 主要改善了尾延迟

Related Work

• 延迟敏感的存储栈优化

• LSM Compaction 优化

• 软硬协同来优化延迟

• 数据缓存

• 减小存储开销
• Mutant
• PrismDB
• RocksMash
• SA-LSM

Conclusion

• 本文对 AWS EBS 云存储的延迟机制进行了深入的探索和建模。实验分析表明，当请求超过阈值时，EBS 合约中有限的 IOPS 预算会导致终端用户的高延迟峰值。我们特别研究了基于 LSM 树的键值存储，它既放大了外部工作负载波动，又造成了内部请求拥塞。我们提出 Calcspar，这是一个基于合约的 LSM 存储，用于减少延迟峰值的云存储。在不同的工作负载压力下，Calcspar 中的波动感知缓存策略将第 99 百分位延迟减少了 66% 以上，而不会产生明显的缓存成本。感知拥塞的 IOPS 分配通过为内部操作分配不同的优先级和防止线程 I/O 争用，进一步避免了多达 60x 尾部延迟峰值。我们的敏感性研究表明，Calcspar 适用于不同的云存储容量。因此，Calcspar 可以作为云存储提供商的配套服务，为终端用户显著平衡性能和成本。