2023年7月17日
第21卷，第3期

远端内存中的指针

对数据和计算应如何组织方式的重新思考

Ethan Miller、George Neville-Neil、Achilles Benetopoulos、Pankaj Mehra 和 Daniel Bittman

在数据中心内存技术领域，这是一个最好的时代，也是一个最坏的时代。根据 IDC（国际数据公司）的数据，DRAM（动态随机存取存储器）在 2022 年的收入超过 1000 亿美元。然而，预期的增长率接近零线，许多生产商要么报告了亏损季度，要么据传很快就会这样做。从数据中心客户的角度来看，据一些估计，租用内存的成本从每年每千兆字节 20 美元到 30 美元不等，而直接采购的资源成本仅为 2 美元到 4 美元。最重要的是，SaaS（软件即服务）终端用户，例如，被迫预先租用他们需要的所有内存。据一些粗略估计，他们最终使用的内存不到 25%，时间超过 75%。¹⁰

CXL（Compute Express Link，计算扩展链接）是一种硬件方面正在兴起的新技术⁹，有望提供远端内存。因此，内存容量可能会更大，带宽甚至可能更高，但代价是更高的延迟。优化将首先寻求保持远端层级内存的“冷度”，其次，最大限度地减少进出这些层级的访问和提升速率。^1,5 第三，为远端内存开发的主动提升和降级技术，以整个对象而不是一次一个缓存行进行提升/降级，以便利用批量缓存和驱逐，从而避免重复产生长延迟。最后，将具有许多依赖性访问的计算卸载到近内存处理器，已经被视为一种将内存延迟排除在应用程序吞吐量分母之外的方法。¹¹ 对于远端内存，这将是必要的优化。

追逐“近”内存指针

在内存中对丰富连接的数据进行操作的应用程序，大量参与指针追逐操作，无论是直接地（例如，深度学习推荐模型中的图处理）还是间接地（例如，数据库中的 B+ 树索引管理）。图 1 显示了远端内存中指针追逐应用程序的示例：[1] 图遍历，[2] B+ 索引中的键查找，以及 [3] 开放散列下的冲突解决。

先前工作² 的数据表明，随着数据结构扩展超出单个主机的内存限制，导致应用程序数据溢出到远端内存，程序员被迫对函数和数据放置、互通和编排做出复杂决策。

远端内存的性能特征

默认情况下，指针（如图 1 中的节点间指针）是在创建它们的进程的虚拟地址空间中定义的。因此，如果不进行优化，指针追逐操作及其依赖性访问可能会使支持内存级并行性的微体系结构资源（例如，重排序缓冲区）不堪重负，即使在具有本地内存的单个 CPU 上也是如此。由于延迟范围可能从 150 纳秒到超过 300 纳秒²，远端内存进一步加剧了这个问题。

在分布式环境中，简单的指针追逐卸载而不考虑虚拟地址到物理地址的转换，会导致与父进程进行大量的节点间协调。¹⁵ 有效优化指针追逐操作需要最大限度地减少执行遍历的近内存处理器与运行父进程的服务器之间的通信。

开发远端内存就绪的应用程序

来自 HPC（高性能计算）和数据库工作负载的证据表明，在 CPU 和 GPU 上，指针丰富的稀疏内存操作效率极低^4,14，在某些情况下，性能甚至低于峰值性能的百分之一。这导致应用程序希望将此类工作卸载到近内存处理器。在远端内存的情况下，近内存处理器本身位于指针丰富数据的父进程的转换上下文之外。因此，指针必须在这些新的异构解耦系统中处处有意义。

为了降低基础设施租金，云应用程序也希望利用解耦的远端内存作为可伸缩的内存资源，该资源可以随着数据量的增长和缩小而增长和缩小。此外，他们希望独立扩展其内存和计算资源。例如，数据库服务希望根据查询负载灵活地向上或向下调整计算能力。远端内存中指针丰富的数据必须在现有和新的计算实例之间以低开销共享。

关于远端内存的先前工作

传统操作系统中的指针仅在父进程的内存空间中有效。因此，在进程、节点和设备之间共享指针丰富的数据需要序列化-反序列化。即使在最近扩展的现有技术中，通过使用特殊指针来标记降级到远端内存的数据的悬空引用，这种限制仍然存在。^7,16 这些指针只能从数据创建的原始上下文中取消引用，从而排除了内存和计算的独立扩展。

诸如 PGAS（分区全局地址空间）之类的全局地址空间支持有限形式的全局指针，这些指针仅在跨多个节点的一组进程的生命周期内持续存在。诸如 PMDK（持久内存开发套件）之类的 NVM（非易失性内存）库支持基于对象的指针，但它们的“大型”存储格式指针超过 64 位长，并且它们的遍历无法卸载。

诸如 VMware 的 Nu proclets¹³ 之类的商业虚拟化框架只能通过牺牲安全性（例如，关闭地址空间布局随机化）来维持全局指针的假象。

Microsoft CompuCache¹⁴ 也支持全局指针，但即使在解耦的内存设备上，也通过在完整的 VM 之上使用繁重的数据库运行时来实现。所有指针，无论是在主机还是在 CompuCache 中，都仅限于 VM 本地。跨设备进行指针追逐需要重复返回到主机。

Teleport¹⁵ 支持指针追逐卸载到远程内存，但通过定向地、按需地将虚拟地址到物理地址的转换上下文传输到每个已传输函数的目标位置来实现。

因此，关于远端内存的操作系统构造的先前工作缺少全局不变指针的基础，这些指针可以与包含远端内存的集群中的任何节点或设备共享和取消引用。

不变指针

在以对象粒度组织数据时，全局不变指针必须包含包含目标数据的对象的 ID，以及该数据的偏移量。无论指针在何处取消引用，都可以解释此对象 ID。理想情况下，不变指针应：(1) 不大于 64 位；(2) 允许访问部分驻留的对象。现有方法不满足第一个标准（例如，PMDK）或第二个标准（例如，AIFM¹²）；AIFM（应用程序集成远端内存）对于驻留和非驻留对象具有不同的指针形式。然而，提供真正全局不变的指针对于卸载“随处运行”的代码是必要的。

Twizzler³ 是一种操作系统，它通过使用对象本地的上下文引入全局不变指针，缩短其表示形式，同时允许任何可以读取指针的 CPU 完全解析其目标。这是通过 FOT（外部对象表）完成的，FOT 是系统中每个对象的一部分，确保任何单个对象都是自包含的。

对象的 FOT 包含每个外部对象的标识信息，这些外部对象是对象中指针的目标。由于这些信息存储在有序表中，因此存储的指针使用 FOT 中的索引作为完整寻址信息的替代，如图 2 所示的转换过程。这种方法允许指针保持较小：例如，64 位指针可以包含 24 位“本地”对象 ID 和 40 位偏移量。虽然这限制了可以从单个对象引用的外部对象的数量为 2²⁴，但不同的对象有自己的 FOT，并且可以引用不同的对象集，因此系统中对象的总数仅受对象 ID 大小的限制。

这种方法还允许广泛的解析器，这些解析器将 FOT 中的标识信息转换为对象 ID。例如，FOT 可能包含静态对象 ID 或等效于文件系统名称的名称，以便由名称解析器解析为对象 ID。不要求名称在不同位置解析为相同的对象 ID：名为 /var/log/syslog 的对象可能在不同的系统节点上解析为不同的对象 ID。名称解析器本身可以是可插拔的：FOT 只需要以系统中的任何节点都可以运行解析器以返回对象 ID 的方式标识解析器。

虽然首次访问外部对象可能相对较慢，但后续访问非常快，因为到对象 ID 的解析会被缓存。系统将对象映射到节点的“客户物理”地址空间，利用已用于虚拟化的 MMU（内存管理单元）硬件。然后，它将对象所在的客户物理空间映射到引用该对象的任何进程的客户虚拟空间，使用扩展页表从 CPU 加载/存储路径中删除软件，并允许系统以内存速度运行。这对于效率是必要的：即使每次加载和存储操作的系统软件交互最小，也会显着降低计算速度。

初步实验³ 表明，Twizzler 的方法在为对象内和对象间不变指针保留低延迟指针解引用方面是有效的。在以 2.3GHz 运行的 Intel Xeon Gold CPU 上，对象内指针解引用大约需要 0.4 纳秒，与“正常”解引用所需的时间大致相同。缓存的对象间指针解引用需要 3.2 纳秒，比对象内解引用稍慢，但仍然足够快，因为考虑到多兆字节的对象，预计此类引用相对较少。首次引用外部对象速度较慢，为 28 纳秒，但仍然合理。如果名称解析比解释静态全长（128 位）对象 ID 更复杂，则时间会更长；但是，无论在同一进程中从对象 A 到对象 B 的指针被解引用多少次，这些惩罚都只支付一次。

在微观层面（内存键/值存储）和宏观层面（使用不同后端的 YCSB [Yahoo! 云服务基准]）上的基准测试同样显示了这种方法的出色性能。图 3 顶部的图表显示了 YCSB 基准测试在 SQLite 上使用四个后端时的性能：原生 SQLite 后端；利用 mmap 的 LMDB（Lightning 内存映射数据库）后端；我们实现的 PMDK 后端，它在 PMDK 下使用红黑树；以及 Twizzler，它使用带有不变指针方法的红黑树。

不变指针方法优于所有其他方法，同时提供了“随处运行”不变指针的灵活性。图 3 底部的图表类似地表明，由于编程模型的简单性和解引用指针的低开销，这些不变指针提供了比其他方法更低的延迟。特别是 PMDK 明显较慢，因为它的指针为 128 位长，需要额外的寄存器空间和内存操作才能读取和解引用。

重要的是要注意，PMDK 和 Twizzler 实现运行相同的后端代码，仅对编程模型进行了更改；这表明使用对象上下文本地的 64 位指针而不是像 PMDK 那样使用 128 位指针的好处。

Elephance MemOS 是 Twizzler 的一个分支，正在开发用于在 CXL 远端内存设备上运行。它将被移植并针对用作 CXL 解耦内存节点中的控制器的 SoC（片上系统）进行优化。

使用内存对象和不变指针进行编程

对于软件开发人员而言，内存解耦意味着什么？如何围绕它构建系统？此类系统的架构将旨在对大多数程序员隐藏细节，因此他们的代码无需更改即可在这些新系统上运行。

构建系统以提供解耦内存的方式有三种：应用程序库、对操作系统内存系统的修改以及在硬件层操作系统之下的更改，如图 4 所示。在图中，一组应用程序服务器通过共享总线连接到一组 MemOS 节点。远端内存中指针丰富的应用程序数据驻留在 MemOS 节点上。指针可以是：(1) 对象间且在同一设备上，(2) 设备间对象间，或 (3) 对象内。

解耦内存可用的第一种方式可能是通过直接链接到应用程序的应用程序库，如图 4 顶部 (A) 所示。内存垫片充当专门的内存分配器，它知道如何使用 MAP（内存访问协议）来处理远程内存。MAP 可能取决于当前的技术，例如 RDMA（远程直接内存访问），或者可能是更新的技术，例如 CXL3。

许多语言（例如，依赖于 C 库进行内存的 Python）将能够使用内存垫片来处理语言中对象的内存，从而使 Python 程序员无需了解任何关于解耦内存的信息。对于直接处理指针的 C 和 C++ 等语言，程序员将必须使用内存垫片 API 来管理远程内存。Python 和类似的托管内存语言在大数据和机器学习应用程序中的普及意味着这些领域的程序员可以以透明的方式使用解耦内存，无论内存垫片位于软件堆栈中的哪个位置。

扩展操作系统的虚拟内存系统以与内存垫片集成是堆栈中插入解耦内存的下一个逻辑位置，如图 5 中的 (B) 所示。同样，特定的 MAP 不会暴露给内核开发人员，只有内存垫片 API。Linux 操作系统已经具有 HMM（异构内存管理）⁸，这是一个自然的插入内存垫片的位置。一旦垫片集成到操作系统本身中，所有应用程序都可以透明地使用解耦内存，而无需修改其源代码或与专用库链接。

远端内存可以放置在堆栈中最深处的位置是在硬件本身中。来自英特尔和 AMD 的 CPU 中集成的内存控制器已经开始支持早期版本的 CXL 解耦内存。未来，功能更强大的控制器将以透明的方式向操作系统呈现本地和远程内存，但与其他两种情况一样，将需要一个 MAP 来插入硬件和远程内存之间。在这种情况下，协议将是 CXL 3。

虽然将内存垫片放入硬件可能会产生最高的带宽、最低的延迟和最大的可移植性，但仍有理由继续使用内存垫片作为链接到软件中的库。首先也是最重要的是，直接链接到内存垫片为程序员提供了控制级别。一旦此类功能嵌入到操作系统或内存控制器中，应用程序程序员将失去对远程内存系统的控制和可见性。虽然许多人会很高兴不必自己管理内存，但应用程序将保留对这种控制成为一项功能的需求。分布式内存的新型内存架构必须首先在软件中进行尝试，并且某些架构可能过于专业而无法在硬件中实现。

考虑一个指针是全局不变的内存系统，这在 MemOS 中是可能的，但在基于指针的系统中尚不常见。在软件中构建和调试这样的系统使得快速迭代设计成为可能——这在内存控制器中是不可能的，并且在操作系统中调试肯定更困难。可以使用全局不变指针的应用程序具有明显的优势，因为计算可以在任何节点上进行，而无需应用程序知道指针可能驻留在哪里。此外，可以移动代码而不是数据来实现计算效率——同样，因为无论指针驻留在哪个计算节点上，指针本身都是计算所依赖的全局句柄，而不是像今天这样的本地内存中的地址。

主要结论

有效利用新兴的远端内存技术需要考虑在父进程上下文之外操作丰富连接的数据。正在开发中的操作系统技术通过公开诸如内存对象和全局不变指针之类的抽象来提供帮助，这些抽象可以由设备和新实例化的计算遍历。这些想法将允许在具有解耦内存节点的未来异构分布式系统上运行的应用程序利用近内存处理来获得更高的性能，并独立扩展其内存和计算资源以降低成本。

参考文献

1. Al Maruf, H., et al. 2023. TPP: 用于支持 CXL 的分层内存的透明页面放置。在第 28 届国际编程语言和操作系统体系结构支持会议 3, 742–755; https://dl.acm.org/doi/10.1145/3582016.3582063.

2. Berger, D. S., et al. 2023. 公有云平台中基于 CXL 的内存池的设计权衡。IEEE Micro 43(2), 30–38; https://dl.acm.org/doi/abs/10.1109/MM.2023.3241586.

3. Bittman, D., et al. 2020. Twizzler：用于非易失性内存的以数据为中心的操作系统。在Usenix 年度技术会议论文集中; https://dl.acm.org/doi/pdf/10.5555/3489146.3489151.

4. Dongarra, J. 2021. 一个不太简单的软件问题。图灵奖讲座; https://www.youtube.com/watch?v=cSO0Tc2w5Dg.

5. Duraisamy, P., et al. 2023. 面向仓库规模内存分层的自适应系统架构。在第 28 届国际编程语言和操作系统体系结构支持会议 3, 727–741; https://dl.acm.org/doi/10.1145/3582016.3582031.

6. Hsieh, K., et al. 2016. 加速 3D 堆叠内存中的指针追逐：挑战、机制、评估。IEEE 第 34 届国际计算机设计会议 (ICCD), 25–32; https://ieeexplore.ieee.org/document/7753257.

7. Jennings, S. 2013. zswap 压缩交换缓存。LWN.net; https://lwn.net/Articles/537422/.

8. 内核开发社区。异构内存管理。Linux 内核 5.0.0; https://linuxkernel.org.cn/doc/html/v5.0/vm/hmm.html.

9. Mehra, P., Coughlin, T. 2022. 使用解耦驯服内存。计算机 55(9), 94–98; https://ieeexplore.ieee.org/document/9869614.

10. Michelogiannakis, G., et al. 2022. HPC 中机架内资源解耦的案例。 体系结构和代码优化事务 19(2), 1–26; https://dl.acm.org/doi/10.1145/3514245.

11. Rodrigues, A., Gokhale, M., Voskuilen, G. 2019. 面向分散-聚集架构：硬件和软件问题。在国际内存系统研讨会论文集, 261–271; https://dl.acm.org/doi/10.1145/3357526.3357571.

12. Ruan, Z. et al. 2020. AIFM：高性能、应用程序集成的远端内存。在第 14 届 Usenix 操作系统设计与实现研讨会 (OSDI) 论文集中; https://dl.acm.org/doi/pdf/10.5555/3488766.3488784.

13. Ruan, Z., et al. 2023. Nu：通过逻辑进程实现微秒级资源可替代性。在第 20 届 Usenix 网络系统设计与实现研讨会 (NSDI) 论文集； https://www.usenix.org/system/files/nsdi23-ruan.pdf.

14. Zhang, Q., et al. 2022. CompuCache：使用 Spot VM 的远程可计算缓存。第 12 届创新数据系统研究年会 (CIDR); https://www.cidrdb.org/cidr2022/papers/p31-zhang.pdf.

15. Zhang, Q., et al. 2022. 使用 Teleport 优化解耦数据中心中的数据密集型系统。在国际数据管理会议 (SIGMOD) 论文集； https://dl.acm.org/doi/10.1145/3514221.3517856.

16. Zhou, Y., et al. 2022. Carbink：容错远端内存。在第 16 届 Usenix 操作系统设计与实现研讨会 (OSDI) 论文集； https://www.usenix.org/system/files/osdi22-zhou-yang.pdf.

Ethan Miller 自 2009 年以来一直是 Pure Storage 的技术人员。他是加州大学圣克鲁兹分校计算机科学与工程系的荣誉退休教授，曾在那里担任 Veritas 存储系统总统讲席教授；创立了存储系统研究中心；并领导了 Ceph 分布式文件系统、Twizzler 操作系统的开发。在加州大学伯克利分校攻读博士学位期间，他是 RAID 项目的成员。他的研究兴趣包括非易失性内存系统、存储系统的安全性和可靠性以及可扩展和长期存储系统。

Achilles Benetopoulos 是加州大学圣克鲁兹分校的博士生，致力于分布式系统、数据库和编程语言的交叉领域。此前，他曾在多家公司担任软件工程师多年，负责堆栈的各个层面。

George Neville-Neil 从事网络和操作系统代码的工作，既为了乐趣也为了盈利。他还教授各种与编程相关的课程。他的兴趣是计算机安全、操作系统、网络、时间协议以及大型代码库的维护和管理。他是 The Kollected Kode Vicious 的作者，也是 The Design and Implementation of the FreeBSD Operating System 的合著者。他毕业于波士顿东北大学，获得学士学位。他的软件作为 VxWorks 的一部分部署在 NASA 的火星任务中。他是一位狂热的自行车爱好者和旅行家，目前居住在纽约市。

Pankaj Mehra 是 Elephance Memory 的创始人，自 2013 年以来一直在内存和存储行业担任执行技术和管理职位。他曾任三星产品规划副总裁、SanDisk 和 Western Digital 高级研究员以及惠普杰出技术专家。Pankaj 曾在 IIT Delhi、加州大学圣克鲁兹分校和 IBM TJ Watson 研究中心担任教职和访问职位。他是服务器、存储、互连和人工智能领域 100 多本书籍、论文和专利的作者/发明人。

Daniel Bittman 是 Elephance Memory 的联合创始人兼 Twizzler 操作系统的主要维护者。他获得了加州大学圣克鲁兹分校计算机科学博士学位，师从 Peter Alvaro 和 Ethan Miller。在不进行操作系统研究时，他会在山中远足。

最初发表于 Queue 第 21 卷，第 3 期—
在数字图书馆中评论本文

更多相关文章

Simson Garfinkel, Jon Stewart - 磨砺你的工具
本文介绍了我们在最初发布十年后更新高性能数字取证工具 BE (bulk_extractor) 的经验。在 2018 年至 2022 年期间，我们将该程序从 C++98 更新到 C++17。我们还进行了完整的代码重构并采用了单元测试框架。DF 工具必须经常更新，以跟上其使用方式的变化。对 bulk_extractor 工具更新的描述可以作为可以并且应该做什么的示例。

Pat Helland - 自主计算
自主计算是一种业务工作模式，它使用协作来连接领地及其特使。这种模式基于纸质表格，已经使用了几个世纪。在这里，我们解释了领地、协作和特使。我们研究了特使如何在自主边界之外工作，并且在保持局外人身份的同时仍然很方便。我们还研究了如何在不同领地之间启动工作、长时间运行并最终完成。

Archie L. Cobbs - 持久性编程
几年前，我的团队正在为增强型 911 (E911) 紧急呼叫中心进行一个商业 Java 开发项目。我们尝试使用传统的 Java over SQL 数据库模型来满足该项目的数据存储需求，但感到非常沮丧。在对项目的特定需求（和非需求）进行一些反思后，我们深吸一口气，并决定从头开始创建我们自己的自定义持久层。

Torsten Ullrich - 真实世界的字符串比较
在许多语言中，字符串比较是初学者的一个陷阱。对于任何 Unicode 字符串作为输入，比较通常甚至会给高级用户带来问题。Unicode 中不同字符的语义等价性要求在比较字符串之前对其进行规范化。本文展示了如何正确处理 Unicode 序列。两个字符串的相等性比较通常会引起关于按值比较、对象引用比较、严格相等和松散相等之间差异的问题。最重要的方面是语义等价性。