[FAST'21] The Storage Hierarchy is Not a Hierarchy

The Storage Hierarchy is Not a Hierarchy: Optimizing Caching on Modern Storage Devices with Orthus

作者： Kan Wu, Zhihan Guo, Guanzhou Hu, and Kaiwei Tu, University of Wisconsin–Madison; Ramnatthan Alagappan, VMware Research; Rathijit Sen and Kwanghyun Park, Microsoft; Andrea C. Arpaci-Dusseau and Remzi H. Arpaci-Dusseau, University of Wisconsin–Madison

论文概要

Abstract

  动态调整allocation和access decision，从而最大化性能。在Orthus-CAS（一个块层缓存内核模块）和Orthus-KV（一个针对KV存储的用户层caching层）上实现。

  在各种现代层次结构下，在一系列实际工作负载下，Orthus-KV和Orthus-CAS提供了比经典缓存显著更好的性能(最多2倍)。

Introduction

  层次化的概念计算机系统设计，甚至很多教科书中都有描述。

Since fast memory is expensive, a memory hierarchy is organized into several levels – each smaller, faster, and more expensive per byte than the next lower level, which is farther from the processor.

  为了应对层次结构的本质，系统通常采用两种策略:缓存（caching）和分层（Tiering）。对于个一个两层的结构，下面的capacity layer的用来存放所有数据，而上面的performance layer用来存放热数据的备份，并搭配一个缓存替换算法。Tiering算法也是利用performance layer来存放热数据，然而与caching不同，它在更长的时间尺度上对数据进行迁移（migrate）而不是存储备份。随着足够高比例的请求到达fast层，整体的性能会接近于fast层。 因此传统的caching和tiering的都努力确保大多数访问都到达performance layer。

这里似乎是一个历史发展的问题。 以前的cache很小，而且数据容易丢失，因此只用来存储一部分数据的备份。 但是现在SSD用作HDD的备份，可以存储大量的数据，而且可以保持数小时甚至数天，这也就是论文中说的"unlike caching, it migrates data (instead of copying) on longer time scales". caching机制下，缓存失效只会影响性能，很少会导致性能损失；而在tiering机制下，故障是不能容忍的，所以需要类似RAID的数据保护方案，这种保护开销可能会影响性能，而且需要更多的空间。

另外，如果一个数据在底层命中，tiring分区并不需要将其迁移到上层， 数据的迁移是在更长的时间周期内决定的。因此caching更能适应快速变化的负载。

  虽然这种分层的智慧适用于传统的存储层次结构，例如CPU缓存和DRAM、DRAM和hard disk，但是存储设备的快速发展使得现代存储层次结构种的这种叙述变得很复杂。具体来说， 很多新的NVM存储器和低延迟的SSD的出现，引入了很多具有重叠性能的设备。因此，重新考虑怎么在存储层次中管理这些设备是很重要的问题。

  为了更好地理解这个问题，考虑用传统的Flash-Based SSD作为capacity层，用更新更快的Optane SSD作为性能层。 在一些情况下，Optane的性能更好，因此传统的架构依然适用；但是在其他场景下（即，当工作负载具有高并发性时），两个SSD的性能是相近的，因此这种存储分层实际上不是分层结构。因此，传统的caching和tiering并没有利用容量层提供的全部带宽。需要一种不同的方法来最大化性能。

  为了解决这个问题，他们提出了一种非层次化的缓存策略（NHC）。NHC为现代设备提供了最大的性能，即便设备特性很复杂、工作负载不断变化。NHC的关键insight是当经典缓存向performanc device发送的请求多于有用的时候，一些多余的负载可以动态地移动到capacity device上。这在两个方面改进了传统的caching。首先，通过监控性能并调整发送到每个设备的请求，这种方式从capacity设备上获取了额外的性能；另外，如果数据的迁移不会提升性能，那么NHC就不会在设备间移动数据。 虽然这种思路对于caching和tiring都适用，但是他们将重点放在了caching上。

  以前的工作已经解决了缓存的一些限制，将多余的写操作从ssd卸载到底层磁盘。然而他们有两个严重的问题： 1. 他们不重定向已经在cache中的条目(cache hit)；2. 他们不适应不断变化的工作负载和并发级别(这对现代设备来说是至关重要的)。

后面讲了在哪些平台上实现的、性能怎么样...不再赘述

Motivation

在本节中，我们将讨论存储层次结构管理的经典解决方案。然后，我们将回顾当前和近期的设备，并讨论它们如何改变存储层次结构。

  1. 管理存储层次

传统的缓存算法大多用来提升上层缓存的命中率，然而现在的存储设备分层并不明显，有很多overlap的部分，因此需要重新设计算法。

  1. 硬件存储趋势

Example

Latency

Read(GB/s)

Write(GB/s)

Cost ($/GB)

DRAM

80ns

15

15

~7

NVDIMM

300ns

6.8

2.3

~5

Low-latency SSD

10us

2.5

2.3

1

NVMe Flash SSD

80us

~3.0

~2.0

0.3

SATA Flash SSD

180us

0.5

0.5

0.15

存储系统现在正处于快速的变革。 这些存储设备虽然看起来有一个有序的latency排序，但是其实带宽差距并不明显。 很难根据二者建了一个总的顺序。

图2

执行的都是4KB的读、写， 控制并发数不同。几个设备对：① DRAM/NVM；② NVM/Optane；③ Optane/Flash

对于低并发的读请求，可以清楚地看到设备对之间的显著差距，因此可以认为：存在一个整体的顺序。然而，对于高并发的读请求，这些比值在动态变化。在最极端的情况下，Optane SSD和Flash SSD具有基本一致的性能。

对于写请求，结果更加有趣：由于NVM的并发写性能较差，在NVM/Optane这一组，这个比值在低并发很高，而在高并发很低。

总结来看就是两点：

  1. 现在的存储层次中，相邻的两层的性能可能十分相近；

  2. 每个存储层次的性能都是不断变化的，与负载特性（读、写、并发性）都有关系。

Characterizing Caching in Traditional and Modern Storage Hierarchies

在模型处理的时候有很多简单抽象： 1. 两个设备的rate都是固定不变的（这里我理解的rate就是传输速度）； 2. 负载是只读的，不设计到脏页的回写； 3. 要么一次一个请求（低并发）、要么一次很多请求（高并发）

总之，这部分得到的结论就是：

在现在的存储结构中，如果你和以往一样单纯地增加高性能存储层的命中率， 反而会导致性能的下降。 你需要做的工作是：找到两层命中率的合适的比例。

最佳分割率取决于几个因素： 不同设备、并行程度、写比率。

这个问题在caching机制与tiring机制下是类似的，然而本文重点研究caching：

  1. tiering的优化比较复杂，为了调整数据分布 需要迁移数据，可能会损害性能；

  2. 很多场景下，caching是唯一的选择，tiering并不适用。

Design

本文设计了非层次缓存（NHC），充分发挥了capacity layer的性能，而不是仅仅利用他们的容量。目标：

  1. 与经典的caching策略性能相当或更优；

  2. 不需要了解更多的内部细节，或者进行额外配置；

  3. 鲁棒性，对于动态变化的负载

NHC可以描述为以下三步：

  1. 在预热系统时(或在重大工作负载更改后)，NHC利用经典缓存来识别当前工作集并将数据加载到Dhi;这确保了NHC的性能至少和传统缓存一样好。

  2. 其次，在命中率稳定之后，NHC通过将多余的负载发送到容量设备来改进传统缓存。多余的负载由两部分组成：

    • 读命中没有带来性能提升，因为performance层已经满载了；

    • 读miss导致的不必要的数据迁移，（传统的结构下，读miss会导致数据迁移到上一层）然而当顶层已经满载的情况下，数据迁移并不会导致性能提升。（所以是以一种feedback-based机制来决定多组负载的）

      这里我认为存在问题：性能层满载之后就不再进行数据交换了，可能冷热数据的时效性不强？另外，这种策略只能保证整体性能的最优，无法保证具体的某个负载，因此与多租户其实是不兼容的。

  3. 如果检测到负载变化了，NHC就变为传统的caching策略。（所以如果负载在不断变化，NHC算法会退化为传统算法）

Formal Definition

在给定周期内，总的负载是W

w：由性能层执行的负载

W-w：由容量层执行的负载

对设备的几个基本假设：

  1. 设备的容量有上限L；

  2. 增加workload不会导致设备性能的下降；

  3. 在到达上限前，性能设备的性能曲线梯度比容量设备大。

如下图所示，可以通过为cache controller和a non-hierarchical cache scheduler增加决策点的方式，将传统的Caching算法升级到NHC。

NHC架构图

经典的控制器从用户/应用接收读、写请求，然后基于替换策略（比如LRU）来控制性能层的内容。 新的控制器控制经典控制器的决策是否执行，以及在何处提供cache读命中。调度器优化了一个目标性能指标，这个指标可以由终端用户提供(例如，ops/sec)，也可以使用设备级度量(例如，请求延迟)。

NHC调度器使用一个布尔型data_admit (da)和一个变量load_admit (la)执行此控制。da标志控制D_hi上发生读miss时的行为:设置da时，根据缓存替换策略，在D_hi中分配miss的数据项;当da未设置时，miss由D_lo处理，不会在D_hi中分配。经典缓存对应于da标志为true的情况。

变量la控制如何处理读命中，并指定应该发送给D_hi的读命中的百分比; 当la为0时，所有读命中都被发送到Dlo。具体来说，对于每个读命中，生成一个随机数R;如果R <= la，请求被发送到D_hi;否则，它将被发送到D_lo。在经典缓存中，la总是1。

NHC框架可以搭配任何传统的缓存写分配策略（由用户指定），该策略处理写命中/失败。前面提到的da / la并不对写hit或者miss进行控制。 然而如果性能设备上的数据是dirty的，DHC就不会把读请求送到D_lo

问题在于read的时候怎么知道是不是dirty的，不还是要查D_hi才行吗？？？

Cache调度算法

算法分为两个state：

  1. 增加Dhi上缓存的数据量，以最大化命中率： 让cache控制器执行经典的cache算法，也就是da为true，la为1，直到性能层的命中率基本稳定。

  2. 保持缓存的数据不变，同时调整发送到每个设备的负载：尝试将一些请求从性能层发送到容量层，增加容量层的性能，同时又不降低性能层的性能。

如果在阶段2的时候，发现所有的请求都发送到性能层（也就是la == 1）的时候性能最好，就说明此时性能层可能还没达到性能最大利用，所以就回到阶段1。

cache的命中率还是靠经典的缓存算法来保证的，所以：

  1. 当负载变化的时候，就重新回到stage 1；

  2. 当命中率开始drop的时候，就重新回到stage 1；

  3. 如果负载一直无法稳定，就一直保持着经典cache算法的逻辑。

NHC可以从延迟、吞吐、尾延迟等方向来优化性能，这个性能检测可以在 OS、应用层、操作系统等多个地方检测。

对于写操作，NHC不调整写分配策略

NHC适应动态负载：NHC使用f定期测量目标指标(例如，吞吐量)，并通过调整负载进入比(以类似于梯度下降的方式)来优化它。NHC只需要Δf就可以确定最佳的访问分割。因为调优只涉及一个参数(load-admission ratio)，所以它成本低，收敛速度快。因此，通过持续调优，NHC可以处理频繁变化的工作负载。

总结:NHC优化了经典缓存，从而有效地使用容量设备的性能。NHC在两个方面改进了传统缓存。

  1. 首先，当Dhi的性能得到充分利用时，NHC不允许读miss的数据进入性能层。

  2. 其次，当性能层的性能达到峰值时，NHC通过将性能层中一些请求发送到容量层（即便这些请求可能会在性能层命中），从而利用到容量层的性能。

通过在运行时确定适当的负载，NHC可以从容量层获得有用的性能，而不是仅使用容量层来处理性能层miss的请求。

Implementation

  NHC在① Orthus-CAS 和 ② Orthus-KV两个地方进行了实现，前者是个通用块层的内核模块、后者是一个用户层的kv存储。

  WiscKey(FAST 2016)是基于LevelDB的，主要的区别在于K-V分离。他们将NHC和WiscKey的persistent block cache layer进行了整合，这部分工作他们称为Orthus-KV。

对于命中率稳定的定义

  在过去的100毫秒内，命中率的变化不足0.1%。这个简单的启发式工作得很好，因为NHC不需要完美的命中率-稳定性检测。高强度的工作负载只会让NHC绕过更多的Hits，低强度的工作负载下NHC会快速切换到经典的缓存算法。

目标性能指标

  他们的实现支持三个指标：吞吐，平均延迟和尾延迟。 默认情况是吞吐。在优化吞吐的时候，采用的是Linux块层的统计，优化延迟的时候，测量的是end-to-end的延迟。

调优参数

  NHC实现必须度量目标指标并定期调优参数。NHC适应工作负载变化的速度取决于目标性能度量之间的间隔和步长。间隔越小，调优收敛得越快。尽管频繁的调优意味着更多的CPU开销，但是我们的CPU开销可以忽略不计。我们发现Linux块层计数器在间隔小于5ms时是不准确的，所以我们使用了最小但准确的间隔5ms。步长越大收敛速度越快，但可能会得到次优结果。NHC在每一步中调整2%的load ratio;我们发现这给出了一个合理的收敛时间，最终结果与较小的步长相似。我们为未来的工作留下一个自适应的步长。

实现的开销

  在经典的cache算法上实现NHC十分简单，他们在Open CAS和WiscKey上分别只加了460和228行代码。

我的思考

这边论文突出：

  1. 问题很关键，但实现很简单，只需要很小的改动；

  2. 讲解思路清晰，每一步都目标明确；

  3. 在真实系统上进行了实现，实用性可以保证。

我的一些想法：

  1. 其实这是一个很初步的设想，并不涉及多租户请求、请求类型， 单单只能用来提升全局性能。

  2. 基于反馈的调节机制，load admition三种配置需要三个周期才能得到。

Previous[FAST'21] D2FQNext[ATC' 20] Austere Flash Caching with Deduplication and Compression

Last updated

Was this helpful?