Optimizing Caching on Modern Storage Devices with Orthus

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

概述

本文介绍了非层次缓存（NHC，non-hierarchical caching），现代存储层次结构中的一种新式缓存方法。与传统缓存相比，NHC 通过将过载重定向到层次结构中较低的设备（如果这么做有好处）来提高性能。 NHC 动态调整分配和访问策略，以最大限度提高性能（如高吞吐，较低的 99% 延迟）。我们在 Orthus-CAS（块层 cache 内核模块，基于 OpenCAS）和 Orthus-KV（用户态 kv 缓存层，基于 Wisckey）中实现了 NHC。我们通过深入的实证研究展示了 NHC 的性能：在一系列实际的工作负载下，Orthus-CAS 和 Orthus-KV 在各种现代层次结构上提供显著的更好性能（高达两倍）。

场景

这种高命中率和高负载在生产缓存系统中很常见。例如，Twitter 最近的一项研究表明，十个 Twemcache 集群中有八个的未命中率低于 5%。研究还表明，缓存层经常承受重负载（即，它们是带宽饱和的）。

简介

存储层次结构的概念长期以来一直是计算机系统设计的中心。事实上，在广泛使用的教科书上可以找到关于层次结构及其基本性质的假设：快速存储器是昂贵的，所以存储器层次结构被组织为几个级别，每个比下个级别更小、更快、更贵的字节都离处理器更远。

为了处理层次结构的性质，系统通常会采取两种策略：

缓存（cache）
分层（tiering）

考虑具有两个存储层的系统：性能层（快，小，贵）和容量层（慢，大，便宜）使用缓存时，所有的数据都驻留在容量层。热数据的副本通过缓存替换算法放置于性能层中。采用分层时，热数据放置于性能层中，并且会在一段时间内迁移数据（而不是复制数据）。如果足够多的请求被发送到性能层，则总体性能接近于性能层的峰值性能。因此，传统的缓存和分层策略都努力确保大多数访问命中性能层。

虽然这种优化命中率的传统艺能可能仍然使用于传统的层次结构（例如 CPU cache vs DRAM，或是 DRAM vs 硬盘），但存储设备的快速演进在现代存储层次结构中使这种说法变得复杂。实际上，很多新的 NVM 和低延迟 SSD 的出现引入了具有重叠性能特征的设备（也就是层次之间的性能差距很小，并且可能在某些情况下有重叠）。因此，必须重新考虑如何在存储分层结构中管理此类设备。为了更好地理解这个问题，考虑一个两级的层次结构：

容量层：基于 Flash 的固态硬盘
性能层：看起来更快的 Optane 在某些情况下，Optane 优于 Flash，因此传统的缓存/分层结构运行良好。然而，在其他情况下，比如高并发的工作负载时，设备的性能相似（也就是此时的存储层次结构不是一个层次结构），因此传统的缓存和分层没有利用容量层可用的全部带宽。我们需要一种不同的方法来最大化性能。

为了解决这个问题，我们引入了非层次缓存 NHC，这是一种用于现代存储层次结构的新缓存方法。

核心思想：当传统缓存向性能层发送的请求多于有用的请求时，一些额外的负载可以动态地转移到容量层设备。

这在两个方面对传统缓存进行了改进：

通过监控性能并调整发送到每个设备的请求，NHC 可以从容量层设备中提供更多可用的性能
当设备间的数据移动不能提高性能时，NHC 会避免这样的移动虽然将过量负载重定向到层次结构中较低的想法同时适用于缓存和分层，但我们的重点放在缓存上。先前的工作已经解决了缓存的一些限制，将多余写入从 SSD offload 到 HDD。然而有两个关键的局限性：

它们不对缓存中存在的项的访问链路进行重定向
它们不适应不断变化的工作负载和并发级别（对于现代设备来说尤为重要）我们在两个系统中实现了 NHC：Orthus-CAS 和 Orthus-KV。在负载较低的情况下，Orthus 的行为类似于传统缓存。在其他情况下，他们将缓存层的过重负载卸载到容量层，从而提高了性能。通过严格的评估，在各种实际设备和模拟设备上，Orthus 的实施极大地提高了性能（高达两倍）。

动机

管理存储分层结构

存储层次结构由下面两部分组成：

多个异构存储设备
在这些设备之间传输数据的策略为了简单起见，我们假设一个由一个或两个设备组成的层次结构：
性能设备 $D_{hi}$
容量设备 $D_{lo}$ 传统上有两种方法用于管理这种层次结构：缓存和分层。

使用缓存时，热数据从 $D_{lo}$ 复制到 $D_{hi}$ （在每次未命中时）。为了给这些热数据腾出空间，缓存通过 ARC、LRU 或者 LFU 等算法驱逐冷数据。数据移动的粒度通常在 4k block。分层类似于缓存，在性能设备中维护热数据。然而，与缓存不同的是，访问 $D_{lo}$ 上的数据时，不一定被提升为 $D_{hi}$ 。数据可以直接从 $D_{lo}$ 中提供。数据仅在较长的时间范围（数小时/数天）内定期迁移，并执行长期优化的数据排布。分层通常以较粗的粒度（如整个卷/较大的 extent）。虽然缓存可以对工作负载的变化做出快速的反应，但是分层无法做到。为了最大限度提高性能，缓存和分层都努力确保从高性能设备为大多数的访问提供服务。因此，大部分缓存和分层都旨在最大限度的提高性能设备的命中率。

存储硬件演进趋势

延迟在降低
带宽差距不明确为了更好地了解这些设备的性能重叠，图 2 显示了在改变并发级别的情况下，针对 4KB 读/加载和写/存储的各种实际设备的吞吐量。

读：

低并发读：设备对之间有显著差异
高并发读：Optane 和 Flash 的性能几乎相同

写：

低并发写：/
高并发写：由于 NVM 并发写入的低性能，在 NVM/Optane 中，比率从低并发的好得多变成高并发时的差得多

总结：

与传统的层次结构不同，新的存储层次结构可能不是层次结构，相邻层的（NVM/Optane）的性能可能相似
新设备的性能取决于不同的工作负载和并发级别。

传统和现代存储层次结构中的缓存

对缓存性能建模
实证分析，填充模型没有的重要细节
对 Splitting 的方法进行了建模，突出传统缓存的缺点
1. Splitting 时，数据只是跨设备拆分，运行时不执行任何迁移。
2. 当接入链路在性能设备和容量设备之间得到最佳的 splitting 时，splitting 的性能优于缓存

不妨假设

有两个设备 $D_{hi}$ 和 $D_{lo}$ ，分别以 $R_{hi}$ 和 $R_{lo}$ op/s 执行
工作负载具有很低并发性（一次一个请求）或者高并发性（一次很多请求）
只有读（简化分析，不需要考虑 cache replacement 中的 dirty write-back）

建模

缓存命中率 hit rate： $H \in [0, 1]$ 考虑两个极端：极低的并发和极高的并发

每次一个请求

每次一个请求，每个请求的平均时间为：

T_{\text {cache }, 1}=H \cdot T_{\text {hit }}+(1-H) \cdot T_{\text {miss }}

$T_{hit}$ 是 fast device 速率的倒数

T_{hit}=\frac{1}{R_{h i}}

$T_{miss}$ 是从 slow device 获取数据并且写入到 fast device 的成本

T_{\text {miss }}=\frac{1}{R_{h i}}+\frac{1}{R_{l o}}

对应的带宽：

B_{cache,1}=\frac{1}{T_{cache,1}}=\frac{R_{h i} \cdot R_{l o}}{H \cdot R_{l o}+(1-H) \cdot\left(R_{h i}+R_{l o}\right)}

每次 N 个请求

命中的请求数： $H \cdot N$ 未命中请求数： $(1-H)\cdot N$ 命中的请求直接由 fast device 返回。未命中的请求先访问 fast device 再访问 slow device，所以不管是命中还是不命中 fast device，都需要访问 fast device。

T_{\text {slow }}(N)=N \cdot(1-H) \cdot \frac{1}{R_{l o}} \\ T_{f a s t}(N)=N \cdot(1-H) \cdot \frac{1}{R_{h i}}+N \cdot H \cdot \frac{1}{R_{h i}}=N \cdot \frac{1}{R_{h i}}

总完成时间取决于最后完成的设备：

\begin{aligned} T_{\text {cache }, \text { many }}(N) &=\max \left(T_{\text {slow }}(N), T_{\text {fast }}(N)\right) \\ &=\max \left(N \cdot \frac{1-H}{R_{l o}}, N \cdot \frac{1}{R_{h i}}\right) \end{aligned}

带宽为：

B_{\text {cache,many }}=\frac{1}{\max \left(\frac{1-H}{R_{l o}}, \frac{1}{R_{h i}}\right)}

用于对照的 Splitting 策略

Split rate： $S\in[0,1]$ ，表示 $S$ 份额的请求数由 $D_{hi}$ 服务， $(1-S)$ 份额的请求由 $D_{lo}$ 服务。带宽为：

\begin{array}{r} B_{\text {split }, 1}=\frac{1}{\frac{1-S}{R_{l o}}+\frac{S}{R_{h i}}} \\ B_{\text {split,many }}=\frac{1}{\max \left(\frac{1-S}{R_{l o}}, \frac{S}{R_{h i}}\right)} \end{array}

解析模型

Ratio=\frac{R_{hi}}{R_{lo}}

纵轴表示带宽，横轴表示 Cache 命中率或 Split 率。令 $R_{hi}=100$ 。第一张图， $Ratio=100:1$ ，显示的是传统架构下的 Cache 策略和 Split 策略的比较。随着命中率的提升，系统的带宽也随之提升。即便是命中率为 $80\%$ ，总性能也相当低，因为慢速设备带来的惩罚较高（ $R_{lo}=1$ ）。图二， $Ratio=100:10$ ，此时 $R_{hi}=100，R_{lo}=10$ 。需要注意的细微差别：高并发下，即使命中率略低于 $1$ ，也能实现完美的性能，因为未完成的请求隐藏了未命中的惩罚。图三， $Ratio=100:50=2:1$ ，用以模拟现代的存储层次结构。两点发现。

Cache 受限于 $D_{hi}$ 的性能，无法实现两种设备的综合性能。
最大化 $D_{hi}$ 响应的请求数并不总是能提供最佳性能。在大量并发的情况下，当大约三分之二的请求指向 $D_{hi}$ 时，Split 实现了 $D_{hi}$ 和 $D_{lo}$ 的聚合带宽。进一步增加分流率只会降低性能。因此，在现代层次结构中，关键不是最大化命中率或拆分率，而是找到必须发送到每个设备的正确比例的请求。图四，对照。

真实世界

传统层次结构

DRAM + Flash SSD 现代层次结构：
NVM + Optane，Optane DCPM 128GB + Optane 905P SSD
Optane SSD + Flash SSD Bench 工具 HFIO（Hierarchical Flexible I/O Benchmark Suite）：
LRU-replacement policy for caching
HFIO 生成具有各种参数的复合工作负载（例如，混合读写、局部性、并发数）。
HFIO 精确控制 Cache Layer 大小和访问位置以获得所需的命中率
bs=32k
只做随机读写
上图中，第二行和第三行低并发时， $D_{hi}$ 没有被充分利用，因此提高命中率/拆分率可以提高性能。高并发时，最大化命中率不会得到峰值性能。这些情况下，容量设备提供了可观的性能，因此在最佳拆分率的情况下，Split 提供的性能比 Cache 更好。

实验揭示了模型没有的复杂性，最佳拆分率取决于几个因素：

并行度
读写比例 Figure 5 中可以看到，对于 Optane + Flash，读密集型负载的最佳拆分率为 $90\%$ ，写密集型负载的最佳拆分率是 $60\%$ ，这是因为 Optane 和 Flash 的写入性能差异小于读取性能差异。NVM+Optane 也存在类似结果。

总结和启示

经典缓存在现代层次结构中不再有效：它没有利用容量层可以提供的相当大的性能。
在高命中率和高速缓存层负载过重的情况下，一些请求可以卸载到容量设备。这种高命中率和高负载在生产缓存系统中很常见。例如 Twitter 最近的一项研究表明，十个 Twemcache 集群中有八个的未命中率低于 5% [98]。研究还表明，缓存层经常承受重负载（即，它们是带宽饱和的）[17, 56]。

解决方案：

增加层次结构中缓存设备的数量；然而，这种方法可能非常昂贵，因为性能设备的成本更高。
将请求卸载到容量层提供了一种更经济的方式来实现显着的改进。这种卸载方法可以通过优化将请求拆分到每个设备来提供所有设备的总体性能。为了使 Split 方法运行良好，动态调整拆分速率至关重要，因为在现代层次结构中，最佳速率变化很大，具体取决于写入比率和并发级别等因素。 Tiering 存在与现代层次结构中的缓存类似的缺点。在这项工作中，我们专注于改进缓存有两个主要原因：
从根本上讲，将访问分层以优化分割是很困难的：
- 迁移或复制以匹配当前分层中的最佳拆分可能会损害性能。相比之下，缓存可以轻松绕过缓存命中容量设备；热数据的副本在两台设备上始终可用。
我们认为在许多情况下，缓存可能是唯一合适的解决方案，而分层可能不合适。例如，应用程序只能在需要持久性时使用 DRAM 作为缓存，并且不能在 DRAM+NVM 层次结构中分层。

NHC：Non-Hierarchical Caching

设计目标

性能比经典缓存结构更好。尝试找到最佳的命中率。最坏的情况下退化到经典缓存。
零额外配置，没有比经典缓存更多的假设
适应动态变化的负载

主要思想

为了提高整体性能，将多余负载卸载到容量设备上。如何实现？预热时，识别当前工作集，数据加载到 $D_{hi}$ 中。命中率稳定后，多余负载发送到 $D_{lo}$ 多余的负载由两个部分组成：

读命中缓存时， $D_{hi}$ 已经满载。
读未命中缓存时，传统缓存结构从 $D_{lo}$ 移动数据到 $D_{hi}$ 以提高缓存命中率。然而提高缓存命中率并不能提高性能，因为 $D_{hi}$ 已经满载。 NHC 通过基于反馈的方法确定超载。如果工作负载永远在变化，降级为传统缓存。对设备特性做出假设：
设备性能存在上限
增加负载不会降低性能
设备性能达到上限前，随着负载的提高， $D_{hi}$ 的性能增幅比 $D_{lo}$ 高。经典缓存尝试找到一个工作集使得命中率最高。

架构

相比传统缓存，增加了：Cache controller 和 Cache Scheduler。

两个变量：

data_admit（ $da$ ）控制 read miss 的行为
- $da=1$ ，在 $D_{hi}$ 中通过缓存替换策略分配
- $da=0$ ，read miss 由 $D_{lo}$ 处理。经典缓存就是 $da=1$ 的情况。
load*admit（ $la$ ）控制 read hit 的行为每次 read hit 时生成一个随机数 $R\in[0,1.0]$ ，如果 $R\leq la$ ，请求给 $D*{hi}$ ，否则给 $D_{lo}$ 。传统缓存就是 $la=1$ 的情况，每次请求都先给 $D_{hi}$ 处理。 $la=0$ 时，所有命中的读发送到 $D_{lo}$ 。

NHC 对于写入：

$da$ 和 $la$ 不控制 write hit/misses
Write-back 可能会在 $D_{hi}$ 上引入脏数据， $D_{lo}$ 上有旧数据。此时 NHC 不会向 $D_{lo}$ 发送读。

Cache Scheduler Algorithm

调度程序有两种状态：

增加在 $D_{hi}$ 上缓存的数据量，最大化命中率
保持缓存中的数据不变，调整发送到每个设备的负载。

$f(x)$ 是一个函数，返回 $la=x$ 时的性能。如何得到对应的性能？通过设置 $la=x$ 一段时间测量，得到性能。

$step$ 是 load_admit 迭代的 step size，目标是提高 hit rate

进入一个循环，每次循环进行：

$da=1$ ， $la=1$ （此时行为类似于传统缓存，每次请求都先给 $D_{hi}$ 处理）
等待缓存命中率稳定（如何判定 stable？）
$da=0$ （请求都通过 $D_{lo}$ 处理）调整 $la$
start_hit_rate = 当前 hit_rate
迭代
- $ratio=1$
- $max_f$
  - $la=ratio-step$
  - $la=ratio$
  - $la=ratio+step$
- 如果 $ratio-step$ 性能最好，设置 $la=ratio-step$
- 如果 $ratio+step$ 性能最好，设置 $la=ratio+step$
- 如果 $ratio$ 性能最好，设置 $la=ratio$ 。如果 $la=1$ ，则从 1. 开始重新迭代
- 如果当前的 hit rate 比一开始记录的 start_hit_rate 更低，就从 1. 开始重开

实现

什么是 hit rate stable？最后 100ms 中，命中率的变化在 0.1% 以内。简单的启发式算法，但很有效。

原因是：轻量的工作负载下，NHC 可以快速切换到传统缓存。高负载下，更高的 hit rate 会让 NHC bypass more hits

评估

在 95% hit ratio 和 Load-2.0 的情况下，性能提高：

DRAM+NVM：+21%
NVM+Optane：+32%
Optane+Flash：+54%

Hit ratio 为 80% 的情况下，改进幅度略有降低。

第三，在这些层次结构中，Optane+Flash 与 Orthus-CAS 的改进最大，因为 Optane 和 Flash 之间的性能差异最小，其次是 NVM+Optane 和 DRAM+NVM。我们使用 FlashSim 的结果显示了从业者如何预测在其目标层次结构上使用 NHC 的改进。最后，我们的测量表明 Orthus-CAS 适应复杂的设备特性。在 80% 的命中率下，经典缓存在任何实际层次结构上都无法达到 1.0 的标准化吞吐量，因为缓存未命中会向缓存设备引入额外的写入。 NHC 处理这种复杂性。