Data tiering in heterogeneous memory systems

Paper

发布日期: 2023-11-09

文章字数: 5.2k

阅读时长: 18 分

阅读次数:

1. 论文信息

(EuroSys), 2016
Data tiering in heterogeneous memory systems

所有作者及单位

Subramanya R Dulloor, Amitabha Roy, Narayanan Sundaram, Nadathur Satish, Rajesh Sankaran, Jeff Jackson, Intel Labs
Subramanya R Dulloor, Karsten Schwan, 佐治亚理工学院
Zheguang Zhao, 布朗大学

2. Background

NVM的一个关键使用模型是更便宜的高容量易失性存储器。数据中心运营商一定会问，这种使用NVM取代大部分DRAM内存的模式是否会导致其应用程序大幅放缓？回答这个问题至关重要，因为巨大的性能影响将成为采用此类系统的障碍。

模拟器的设置：
该系统上DRAM的延迟和带宽分别为150ns和40GB/s。NVM技术正在不断发展，并且可能会表现出一系列性能特征，具体取决于技术和控制器设计的细节。因此，我们改变NVM模拟器[39]的参数来反映这种情况，首先将延迟从300ns改变到600ns，同时保持带宽与DRAM相同，然后将带宽从40GB/s改变（与DRAM相同）。）降至5GB/s（DRAM的12.5%），同时将延迟固定在最坏情况下的600ns。

从图上来看，横坐标是延迟和带宽，设置的是随着延迟增加，带宽也逐渐增加的情况。

表明将数据结构放置在特定类型的内存中对性能的影响取决于对其的访问模式。这种依赖性是由于不同的内存访问模式（顺序、随机和指针跳转）在现代超标量乱序处理器上具有非常不同的有效延迟。访问应用程序数据结构的频率本身不足以确定这些数据结构的相对“热度”。

将访问模式分为3种来测量：

指针跳转会经历最大的停顿延迟，等于内存的实际物理延迟。
随机访问，乱序执行可以有效隐藏一些内存延迟。
流式访问，预取器在隐藏内存延迟方面更加有效。
这些访问模式的性能的数量级差异验证了我们的观察，即仅访问频率不足以确定数据结构的“热度”。

3. 解决了什么问题

代表性应用程序进行了全面研究，包括键值存储 (MemC3)、内存数据库 (VoltDB) 和图形分析框架 (GraphMat)（在模拟器上运行）。我们的结论是，确实可以混合使用少量快速DRAM和大量较慢的NVM，而不会对应用程序的性能产生成比例的影响。需要注意的是，这个结果只能通过仔细放置数据结构来实现。本文的贡献是设计和实现了一组库和自动工具，使程序员能够以最少的努力实现最佳的数据放置。

4. 其他学者解决这个问题的思路和缺陷

为了克服“仅NVM”系统中的性能下降问题，未来的系统可能会将NVM与少量DRAM结合起来，从而形成真正的异构内存架构。处理此类系统中DRAM和NVM不同特性的一个简单方法是将DRAM视为NVM的缓存，并应用经典的paging技术按需在它们之间动态移动数据。不幸的是，由于多种原因，该解决方案会导致性能不佳。

首先，它忽略了具有不同访问特性的对象可以位于同一页面上的事实，迫使位于同一位置的对象面临paging系统的相同处理。其次，paging会带来较高的开销[17]，这通常是不可接受的，特别是在直接连接的NVM环境中，数据不需要paging即可访问。事实上，本文考虑的大多数应用程序都明确禁止对其整个内存数据进行paging（例如使用mlock），强调需要比传统分页更复杂的解决方案。

paging是啥意思？应该是指按照4KB来组织页面。因为这边的引用在讨论加入临界于传统存储和内存设备之间的设备后，页面回收的效率将可能没有原来那么好了。

5. 围绕该问题作者如何构建解决思路

设计总览

根据上面的分析，作者认为内存访问的延迟是来自CPU对不同访问模式的延迟。所以数据的放置首先需要识别他们的数据结构，标记数据结构的分配，运行时得到数据结构优先级，然后结束分析转为运行时确定最佳放置位置。（有点奇怪）

本例中的应用程序使用XMem API分配三个数据结构（树、哈希和缓冲区）。每个数据结构的内存分配均由单独的jemalloc实例管理。应用程序使用的标签代表（T1、T2 和 T3）被分配内部优先级，用于决定放置。

用PIN工具记录访问的信息，在缓冲区扫描。如果一个值是一下个访问的地址，那么就是指针跳转类型的。如果这次访问和下次访问靠近，连续元素相差相同数量的位置，那么认为是流式访问。总数减去这两者，得到随机访问的数量。

然后根据一系列建模，用贪心算法去决定放置。

修改应用程序以使用X-Mem API只需要在任何应用程序中编写很少（10到50）行代码。对于每个应用程序，我们首先确定随着应用程序数据大小而增长并占据应用程序内存占用的重要部分的数据结构。只有这样大的数据结构才使用X-Mem API进行分配；其他数据继续使用默认系统分配器在DRAM中分配。每个数据结构都被赋予一个唯一的标签。我们正在探索自动化为每个数据结构附加唯一标签的过程的选项，也许作为编译器扩展。

6. 环境配置

混合内存仿真平台（HMEP）[39]由英特尔构建，用于支持混合内存系统软件堆栈的探索。 HMEP通过实施以下方式实现混合内存与实际应用的研究：(i)DRAM和模拟NVM的独立物理内存范围（使用自定义 BIOS），以及(ii)可配置延迟和时间的细粒度模拟NVM的带宽（使用自定义CPU微代码）。HMEP之前已在其他研究中使用过 [20,26,27,43,44,56]，并在其他地方详细描述过[39]。

我们展示了六种HMEP配置的结果，代表了NVM的性能范围（表1）。在这些配置中，NVM的延迟范围为DRAM延迟的2倍到4倍（300ns、450ns和600ns），NVM的带宽范围为DRAM带宽的1/4倍到1/8倍（10GB/s到5GB/s）。此外，我们还评估了系统中NVM与DRAM大小的不同比例。我们使用1/T来指代DRAM大小为系统中总可用内存的1/T的设置。在所有测试中，我们为应用程序提供固定数量的总内存（等于DRAM和NVM的总和）。与这些设置相对应，我们还考虑了总内存的成本。一般来说，NVM成本源自之前的研究，预计基于NVM（PCM）的SSD比企业MLC NAND闪存SSD贵4倍[33]。基于DDR的DRAM[19]的普遍价格以及保守估计，本工作中假设的可直接寻址NVM设备将比基于NVM的SSD更昂贵（至少在最初），我们假设DRAM是5×按每比特成本计算，比NVM更贵。由于本文感兴趣的大型内存系统中的内存成本明显高于其他服务器组件，因此我们使用上述成本估算作为服务器总成本的代理。

7. 从结果看，作者如何有力证明他解决了问题

评估有两个目标。首先是表明所有三个应用程序的性能很大程度上取决于其中每个数据结构的放置选择。其次，我们的目标是证明我们的放置技术可以正确识别每个数据结构的访问模式，并通过X-Mem实现最佳数据放置。为了证明所有情况下的结果，我们提供了两个基线进行比较。第一种是纯NVM——其中应用程序的内存完全从NVM分配。仅NVM描述了混合内存系统中未经修改的应用程序的最坏情况性能。第二种是仅DRAM，它代表当所有访问的数据都分配在快速DRAM中时应用程序的最佳性能。

红色柱状图是开销。

7.1 MLP GraphMat

MLP(memory-level parallelism)可以帮助CPU更好地利用系统内存层次结构，从而减少内存访问延迟并提高计算效率。MLP的内存层次通常包括寄存器、高速缓存、主内存和可能还有其他级别的内存。当CPU执行指令时，它会不断地从不同的内存层次中获取数据，而不仅仅依赖于主内存。这可以通过预取数据到高速缓存、使用多级高速缓存、乱序执行指令等技术来实现。通过充分利用MLP，CPU可以在等待内存数据返回时执行其他指令，从而提高整体性能。MLP的具体实现和性能提升取决于处理器的架构和设计，以及编写的程序的特性。

GraphMat采用顶点程序，并在后端将其映射为高度优化、可扩展的稀疏矩阵操作。GraphMat以迭代广义稀疏矩阵-稀疏向量乘法（或SPMV）的方式实现图算法，更新与顶点相关的一些数据（如 Pagerank）。下图是在代表Twitter follower网络[34]的大图上执行Pagerank算法[23]，32G. Graphmat具有三种主要数据结构：稀疏向量、顶点数据的稠密向量，最后是压缩稀疏行格式的图的邻接矩阵。顶点数据的稀疏向量是在每次迭代上构建的，并且由计算中活动顶点的数据组成。通过读取和写入稀疏向量而不是顶点的全稠密向量Graphmat实现了更好的缓存效率。从X-Mem的API可以发现对数据结构的访问量是很有倾向性的。

图8显示了运行测试时GraphMat的带宽要求和有效延迟。有效延迟（显示为实际物理内存延迟的百分比）通过测量每次最后一级缓存缺失时由于待读取而导致的core停滞，近似于应用程序中的平均内存读取延迟。GraphMat可以实现很高的带宽使用率（读取带宽高达25GB/s，写入带宽高达15GB/s），但由于GraphMat能够利用CPU的MLP（内存级并行性），其有效延迟很低（大多低于20%）。因此，GraphMat的性能对较低的带宽高度敏感，但对较高的延迟只有一定程度的敏感。这就解释了为什么GraphMat的纯NVM性能会随着带宽的降低而降低，而不是随着延迟的增加而增加（图9a最高的那条线）。

GraphMat仅适用于NVM的性能比仅适用于DRAM的性能差2.6倍至5.9倍，并且在较低峰值NVM带宽下性能下降尤其急剧。大部分性能差距可归因于稀疏向量，稀疏向量仅占GraphMat占用空间（32GB）的3.5%（但是他很热）。图9b描述了使用稀疏向量的SPMV操作对GraphMat整体运行时间的巨大贡献。超过1/16，性能会受到对大型邻接矩阵的统一（带宽限制）访问的限制。因此，1/2的性能是仅DRAM的1.09倍到1.29倍，比 1/16 略有改进，但成本更高。

7.2 VoltDB

内存数据库利用架构和应用程序趋势来避免许多通常与基于磁盘的OLTP数据库相关的开销[12,13,15,51]。VoltDB就是这样的内存数据库之一，它是一种符合ACID的分布式主内存关系数据库，它实现了H-Store的无共享架构 [51]。将仓库数量设置为512个，VoltDB中的站点数量设置为8个，从而产生40GB内存占用。TPC-C吞吐量以每秒总事务数报告。

图11显示，VoltDB的性能只对内存延迟敏感，这可以解释为VoltDB中的随机访问（尤其是对索引的访问）造成了较高的有效延迟，有时甚至超过50%（图10b）。在TPC-C工作负载中，VoltDB的平均读取带宽为2.3GB/s，写入带宽仅为1.3GB/s（图10a），因此对较低的带宽并不敏感。

VoltDB中的TPC-C包含28个此类数据结构，其中前10个数据结构（按大小）约占总内存占用的99%。表4说明了X-Mem的放置算法在这前10个数据结构中的应用。中间结果和其他数据结构使用默认的系统分配器在DRAM中分配。

1/16的性能比纯NVM提高了24%到48%。STOCK表和小型CUSTOMER表-在DRAM中。1/8（此处未显示以避免混乱）和1/4的性能并不比1/16好多少。在1/2时，X-Mem能够将VoltDB的所有数据结构放入DRAM中，除了非常大但不经常使用的“CUSTOMER NAME”.图11b显示了TPC-C事务的延迟分布，因为它是OLTP工作负载的重要指标。当我们转向NVM中包含更多数据的配置时，平均事务延迟会增加。然而，这种增加受到布局算法的调节，导致事务延迟接近DRAM，即使对于1/16配置也是如此。

7.3 MemC3

作为大型数据中心中的缓存，键值存储变得越来越重要[21]。我们研究了Memcached[10] 的一个变体，称为MemC3[28]，这是开源Memcached的最新进展，它比现有实现提高了内存效率和吞吐量。 MemC3实现了布谷鸟哈希cuckoo hashing的变体，以避免Memcached中常见的昂贵的随机相关访问。此外，MemC3用乐观并发控制方案取代了Memcached的独占全局锁定。在加载阶段，MemC3服务器填充了大约64GB的数据集。密钥大小固定为16字节，值的大小范围从16B到8K，大致遵循Facebook发布的数据中ETC跟踪中值的分布 [21]。超过90%的值的大小为512字节或更小。然而，大于512字节的值几乎占据了缓存空间的50%工作负载的总内存占用量约为100GB。

在执行阶段，客户端再次根据ETC请求跟踪中的值分布生成5000万个随机查询。工作负载读取繁重（95%GET和5%SET），并且当前不包含任何DELETE请求（和ycsb差不多竟然）。我们报告完成测试的总时间。图12显示MemC3的性能特征，客户端每次请求一种大小的值（从16B到8K）。图12a显示MemC3的读取带宽范围为1.8 GB/s至14GB/s，写入带宽范围为1GB/s至6.5GB/s，具体取决于值的大小。由于顺序性能的提高，有效延迟在较大值时减少（从48%到4%）（图12b）。

MemC3对较高延迟而不是较低带宽的敏感性（如图13a中仅NVM的性能所示）可以通过工作负载中较小值的较大偏差来解释。图13b通过分解不同值大小的NVM-only开销进一步说明了这一事实。MemC3在启动时为cuckoo哈希表分配内存，并使用动态slab分配器来分配值，slab类型由slab分配的大小决定。哈希表和slabs均使用xmalloc进行分配，因此X-Mem中总共有9个数据结构（表5），因为每个板类型都被视为单独的数据结构。表5显示了由X-Mem放置算法确定的这些数据结构的优先级。请注意，X-Mem为各种板类型确定的优先级完全遵循图13b中仅NVM开销的值细分，这证明了X-Mem放置模型的准确性。在1/8分层中，只有12.5%的应用程序数据位于DRAM中，性能比仅NVM提高了8%到17%，因为X-Mem分配了MemC3的布谷鸟哈希DRAM。 1/4的表现甚至更好，将性能提高到仅DRAM的6%到13%，主要是因为X-Mem现在能够将大量小值放入DRAM中，并减少对NVM的随机访问次数。

表5还显示了为什么仅凭数据结构的访问频率不足以确定将其置于更快内存中的好处。例如，布谷鸟哈希和256B在访问频率和内存占用方面都比较接近，但由于访问模式不同，在每个内存区域的收益方面却形成了鲜明对比。

7.4 实际部署

虽然用xmalloc和xfree替换malloc和free很简单，但根据实现情况，为各个数据结构分配唯一的标记可能需要更多的工作。在我们的例子中，修改VoltDB需要付出最多的努力，但仍然涉及不到50行代码的更改。对于面向对象的程序来说，工作量要低得多，因为可以定义特定于类的分配器来调用xmalloc，而不是将这些调用分散在代码中。虽然这个过程并不繁重，但仍然需要手动操作和对应用程序源代码的充分理解。我们计划探索自动标记应用程序数据结构的动态分配的技术，至少在托管语言和运行时的上下文中[24,32,50]。👍 👍 👍

在剖析步骤中进行内存跟踪（使用Pin）会大大降低应用程序的运行速度（在我们的测试中最高可达40倍），因此只适合离线使用，不适用于生产。我们考虑过的一个方案是采用基于采样的剖析[55]。由于担心采样剖析器可能无法捕捉到指针追逐和strided扫描等紧密间隔的内存访问之间的关系，这个想法被搁置了。我们目前正在探索对x86 ISA的扩展，以实现必要的剖析，但无需昂贵的跟踪每次内存访问的过程。不过，剖析器仍然是初步部署的解决方案。我们还发现，在保留各种数据结构之间关系的同时，缩小工作负载的规模也很有用，这样可以减少剖析所花费的时间。

当内存区域从DRAM迁移到NVM时，X-Mem通过等待mbind调用返回来执行“同步”迁移。在我们的实验中，这种迁移的开销可以忽略不计，因为与应用程序的整体运行时间相比，分配所花费的时间相对较少。表6显示了区域大小范围从64M到1G的迁移的原始开销。 1G区域可以比较小区域摊销5%到8%的迁移成本。然而，**使用1G区域的真正好处是它允许在大多数64位服务器上使用大型（1GB）硬件页面；与4K页的基准相比，迁移开销进一步减少了60%**。虽然我们了解在内存占用较大的应用程序中使用具有大页面的1G区域的好处[27]，但X-Mem的当前实现使用64 MB区域（默认情况下）来减少内部碎片。此外，由于Linux内核的限制，X-Mem使用4K硬件页面。