[arXiv'19] Multi-Tier Buffer Management and Storage System Design for Non-Volatile Memory

Multi-Tier Buffer Management and Storage System Design for Non-Volatile Memory

作者： Joy Arulraj, Andrew Pavlo, Krishna Teja Malladi

论文概要

Abstract

buffer的一个基本假设就数据必须先迁移到DRAM中，存储设备比DRAM慢得多。 然而NVM打破了这个限制条件，其性能与DRAM相近。

本文介绍的是一个管理由“DRAM、NVM和SSD”组成的多层存储结构，充分利用NVM的特性。提出了一组优化，来最大化不同设备间数据迁移的效能。

Introduction

DBMS（数据库管理系统）访问非易失存储（例如SSD）的数据的方式是：在需要的时候将他们载入到易失性内存（例如DRAM）中。DBMS对缓存的规范化管理，是基于以下假设的：

1. 要操作一个数据，只能将其copy到DRAM中；

2. 存储比DRAM慢了很多数量级

然而新兴的NVM打破了这种假设。

NVM设备支持类似于DRAM的低延迟读写，但具有持久的写和像SSD一样的大存储容量。传统的缓冲区管理方法与这种新的硬件环境不兼容。这源于NVM和规范存储技术之间的两个差异。首先，要处理驻留在磁盘上的数据，缓冲区管理器必须将其复制到DRAM, DBMS才能执行任何操作。相反，CPU可以直接操作驻留在nvm上的数据。其次，NVM缩小了易失性和非易失性设备之间的性能差距。

在本文中，我们提出了管理和设计由DRAM、NVM和SSD组成的多层存储层次的技术。我们提出了一组优化来最大化存储层次结构中不同设备之间数据迁移的效用。这些优化是通过引入NVM来实现的。例如，由于DBMS可以直接操作驻留在NVM中的数据，因此缓冲区管理器不必急于将数据从NVM复制到DRAM。我们的结果表明，这种惰性数据迁移技术确保只有经常引用的数据被提升到DRAM。

最近的研究集中在优化特定NVM技术和存储层次的缓冲区管理策略上。Renen等人提出了一种多层BUffer管理器，可以将数据从SSD迁移到DRAM。当一个页面从DRAM中被赶出时，缓冲区管理器会根据它最近是否被访问而将它允许进入NVM缓冲区。Kwon等人提出了一个多层文件系统，不将NVM保留的data缓存到DRAM中，而且当执行同步写操作的时候Bypass DRAM。尽管这些缓冲区管理策略在其目标环境中工作良好，但它们不能推广到其他NVM技术、存储层次结构和工作负载。

我们通过引入数据迁移优化分类来解决这个问题，该分类包含了以前系统中使用的特定技术。我们说明缓冲区管理策略必须根据设备和工作负载特征进行调整。鉴于此，我们在缓冲区管理器中使用一种称为自适应数据迁移的自适应机制，它可以为任意工作负载和存储层次结构实现近乎最优的缓冲区管理策略，而不需要任何手动调优。之前关于nvm感知存储管理的研究没有解决针对目标工作负载和系统成本预算设计多层存储系统的问题[11,24,32,34,45,56]。我们提出了一个存储系统推荐解决这个问题。综上所述，我们做出了以下贡献：

• 我们介绍了支持nvm的数据迁移优化的分类，并提出了管理多层存储层次结构的策略（第三节）

• 我们在缓冲区管理器中引入了一种自适应机制，它可以为任意工作负载和存储层次结构实现近乎最优的策略，而不需要任何手动调优（第四节）

• 我们介绍了一个推荐系统，用于为目标工作负载和系统成本预算设计多层存储层次结构(第5节)。

• 我们演示了支持nvm的缓冲区管理器和存储系统设计器提高了吞吐量，并降低了跨不同事务和分析处理工作负载的成本(第6节)

Background

Buffer管理

缓冲区管理器将可用内存划分为一组固定大小的槽(slot)，这些槽统称为缓冲区。DBMS的高级组件，如查询执行引擎，不需要关心页面是否在缓冲区中。它们只需要请求缓冲区管理器来检索页面。如果另一个组件请求的页面在缓冲区中不存在，缓冲区管理器透明地从非易失性存储中检索页面。

缓冲区管理器在内存缓冲区中维护关于每个页面的临时元数据。这个元数据包括对页面进行的活动引用的数量，以及页面从存储中被带入缓冲区后是否被修改过。如果另一个组件请求的页面已经存在于缓冲区中，那么它将增加对该页面的活动引用的数量，并返回包含该页面的槽的地址。否则，缓冲区管理器根据替换策略(例如，最近最少使用)，选择一个槽位进行替换。如果选择替换的页面包含任何修改，缓冲区管理器将把这些更改传播到非易失性存储上的相应页面。然后，它将请求的页面从存储器复制到替换槽中，并返回槽的地址。

buffer管理器对于何时以及哪些页被刷新到非易失性存储没有完全的自主权。它与DBMS日志管理器协调，以确保事务所做的更改在提交时是持久的，如果系统failure的需要恢复的时候，事务进行的未提交的改变需要逆转。 这些限制也就是durability和failure atomicity属性。

如果事务修改了一个块，然后提交，而Buffer管理器还没有将更新后的块写入持久存储，那么失败将使块处于旧的无效状态，从而违反持久性属性。另一方面，如果Buffer管理器决定写一个属于活动事务的修改块，它就违反了原子性属性。为了防止这种情况发生，缓冲区管理器不做自动替换决策。

这一段的后半部分我还没有充分理解，存疑。

由于DRAM缓冲区的内容在系统故障后丢失，日志管理器在持久存储器上记录从故障中恢复所需的信息。在更新一个页面之前，DBMS将它的旧内容写入日志(即页面的before image)。类似地，当一个页面即将从缓冲池中被驱逐时，它的当前内容将记录在日志中(即页面的after image)。在恢复过程中，DBMS使用日志中的信息将数据库恢复到事务一致的状态。为了限制恢复期间重放日志所花费的时间，DBMS在运行时定期设置检查点。

NVM DBMSs

DBMS的性能受到从磁盘上检索数据和持久化数据(例如，包含日志记录的页面)的速度的限制。如图1a所示，缓冲区管理器将页面从SSD复制到DRAM，以便DBMS对其进行操作。由于DRAM访问比SSD操作快100,dbms在DRAM上管理一个大的缓冲池。然而，由于三个因素，部署大容量DRAM系统是困难的。

首先，它提高了系统的总成本，因为它比二级存储技术贵50美元。

其次，增加DRAM容量提高了系统的总功耗。Lefurgy等人报告说，多达40%的系统总能量被商用服务器的DRAM消耗。

最后，由于前几代晶体管和电容的缩放技术的限制，DRAM的缩放面临重大挑战。

成本、功耗、DRAM工艺

新型的NVM技术，填补了DRAM和SSD的性能与成本之间的gap。NVM由于其固有的设备特性而支持比DRAM更高的数据密度。因此，它比DRAM便宜。与ssd类似，在NVM技术中，每比特的写周期数是有限的。使用支持nvm的缓冲区管理策略来减少写操作的次数，可以延长设备的生命周期。

由于NVM设备比DRAM慢，用价格相似、容量更高的NVM设备替换DRAM会降低DBMS的性能。下图（b）这种架构，，只有当NVM延迟小于DRAM的2倍时，才能提供与DRAM-ssd层次结构相当的性能(第6.7节)。

存储层次

存储系统支持DRAM、NVM和SSD的多层存储结构，如上图(c)所示，可以同时实现性能最大化和成本最小化。原因有两方面:

1. 首先，NVM缓冲区缓存了工作集的很大一部分，从而减少了SSD访问。

2. DRAM缓冲区作为NVM之上的缓存，只存储数据库中最热的页面。

在DRAM-SSD层次结构中，缓冲区管理器决定在磁盘和内存之间移动哪些页面以及何时移动它们。然而，对于DRAM-NVM-SSD系统，除了决定应该迁移什么/何时迁移数据外，它还必须决定将数据移动到哪里(即哪个存储层)。在下一节中，我们将讨论NVM的特性如何影响这个决定。

NVM感知的Buffer管理

NVM在存储层次中引入了新的数据流路径。通过利用这些额外的选项，缓冲区管理器减少了不同层之间的数据移动，并最小化了对NVM的写入次数。前者提高了DBMS的性能，后者延长了NVM设备的寿命。

数据流路径

上图给出了在multi-tier存储层次中的data flow路径。

1. 默认read路径：① SSD到NVM -> ② NVM再到DRAM -> ③ 到处理器的cache

2. 默认write路径：④ cache到DRAM -> ⑤ DRAM到NVM -> ⑥ NVM到SSD

重点讲述⑦⑧⑨⑩是如何最大化NVM的性能收益同时延长其生命周期的。

READ的时候Bypass DRAM

一个参数D_r， 代表read操作的时候将数据copy到DRAM中的概率。 传统情况下（eager migration）这个值为1。 如果将这个值调小，就可以减少DRAM与NVM中的数据迁移。当DRAM的容量比NVM小的时候，这个策略就会有收益。这种“lazy migration stratage”确保了NVM中的冷数据不会将DRAM中的热数据置换出去。

冷热怎么保障的？仅仅靠概率应该做不到吧？

D_r的最优值取决于workload。

使用预先迁移策略，缓冲区管理器总是在服务读操作时将块带入DRAM。因此，如果应用程序随后更新了相同的块，写操作将在DRAM上执行。相比之下，延迟迁移策略会增加NVM上的写操作次数。这是因为当缓冲区管理器采用这种策略时，被更新的块更有可能驻留在NVM上。对于使用倾斜访问模式的DBMS应用程序来说，这不是一个问题。这样的应用程序倾向于修改缓存在DRAM中的热数据，即使缓冲区管理器使用了延迟迁移策略。

Bypass DRAM during Writes

确保包含日志和检查点记录的页面的持久性对于DBMS的可恢复性至关重要，DBMS的性能受到与在非易失性存储上持久化这些页面相关的I/O开销的限制。由于事务倾向于生成多个日志记录，而且每个日志记录的大小都很小，所以大多数dbms使用group commit优化来减少这个I/O开销。DBMS首先将DRAM缓冲区(④)中的一组事务的日志记录分批处理，然后通过一次写入SSD(⑥)将它们一起刷新。这提高了操作吞吐量，并在多个事务之间摊销了I/O开销。

与SSD不同，CPU可以直接在NVM上执行写操作。缓冲区管理器利用这条路径以更低的开销提供synchronous persistence。

好处：

1. 延迟低， DRAM与NVM的写延迟相当；

2. 避免热数据从DRAM中换出去

依然是一个D_w，D_w是数据写到DRAM的概率，传统方案下是1。

REAM Bypass NVM

当buffer管理器检测到数据既不在DRAM，也不再NVM的时候，直接将其copy到DRAM中，绕过NVM。

用一个N_r来表示：读取的时候数据从SSD到NVM的概率，传统方案下是1。

Write Bypass NVM

确保只有DRAM频繁swap out的页才写入NVM（缓冲区标识warmer的page），其他的直接写入DRAM。防止colder的DRAM页污染NVM buffer。

用一个参数N_w代表DRAM到NVM的写概率。

Adaptive Data Migration

根据前面的描述，数据迁移包含四种可能性：读/写 * Bypass DRAM/MVM

Bypass what	读	写
DRAM	控制数据读入DRAM的比例，避免NVM中的冷数据将DRAM中的热数据迁移出去	数据空的log commit操作，直接写入NVM，避免热数据从DRAM中换出去
NVM	如果数据既不在DRAM中也不在NVM中，那么考虑直接从DRAM copy到NVM	在DRAMcache中进行标识，确保只有频繁swap的页面才会从DRAM写入NVM，避免DRAM中的colder页污染NVM缓冲区

buffer管理器必须根据负载特征和存储层次来调整这些策略，否则就没有实际意义。

buffer管理器在运行时保持监控着两个target metrics：

1. 缓冲区管理器的吞吐量

2. 在NVM上执行的写操作的数量

目标是决定最优的参数，来① 最大化吞吐，同时② 最小化NVM的写入。

侯选数据迁移策略的cost function有两个与这些target matrix相关的带权组件相关。

Cost(T, W) = T + (λ/ w)

为了适应缓冲区管理器的数据迁移策略，我们采用了一种称为模拟退火(simulated annealing， SA)的迭代搜索方法。它是一种概率爬山算法，通过一组局部最优的迁移来寻找全局极值。

每一步随机生成一个与当前配置相近的新配置，并计算成本。 如果新的成本更低，那么就立刻接受新的配置； 如果新的成本比较高，那么就以玻尔兹曼接受概率因子来随机接受新的配置。

这里的具体算法比较复杂，没有过多关注。

存储层次结构的选择

前面的工作都是给定了存储层次机构+特定负载，选择最佳的数据迁移配置策略。然而还不清楚在给定系统成本约束的情况下如果为特定的工作负载选择这样的层次结构。

我们可以把一个多层的存储结构看作是一个n层的线性结构: L0、L1、,,,Ln。 每一层的性能由两个因数决定：平均访问时间t以及设备的容量C。 假设第i层的所有block在所有更低层都有备份。 也就是说系统的最大容量是由最底层决定的。

我们可以通过在特定级别找到请求的数据块的概率来描述设备容量对性能的影响。用H来表达命中率。H是随着设备容量C而单调递增的函数。特定level的每个存储单元的成本由成本函数P(t)给出。 这个成本与访问时间呈单调递减关系。（也就是成本越高，访问时间越短）

$h_i = H(C_i)-H(C_{i-1})$

其中hi表示在存储层次中第i层成功访问的相对数量。每个块请求的有效平均访问时间：

$T = \sum\limits_{i=1}^{n}{h_i}(\sum\limits_{j=1}^{i}{t_j})$

为了最大化DBMS的吞吐，需要最小化T，同时受限制于系统成本预算B，因此就是， 最小化：

$T = \sum\limits_{i=1}^{n}(1-H(C_{i-1}))t_i$

同时满足：

$\sum\limits_{i=1}^{n}P(t_i)C_i \leq B$

存储层次推荐系统

H是一个表示负载局部性的函数，没有一个封闭的形式。我们通过开发一个推荐系统来绕过这个限制，该系统可以跨候选存储层次来度量目标工作负载上的实际吞吐量，从而确定最优系统。 这个系统的目的是，给定系统预算的前提下，确定一个DRAM, NVM, and/or SSD的系统下的最大user-defined objective function。

Discussion

我的思考