ACM TACO22：持久内存垃圾回收机制下的对象寻址方法

近些年来，持久内存（Persistent Memory）由于读写性能与DRAM接近，同时具备DRAM缺乏的数据持久性，因此在对数据可靠性具备较高需求的业务场景中得到深度应用。用户使用与内存相同的编程方式分配、访问持久内存数据。因此，持久内存同样面临与传统内存相似的内存碎片与内存泄露问题，并同样依赖垃圾回收机制解决上述问题。

然而，应用级垃圾收集机制引起的数据移动可能会使指向持久内存对象的指针失效。而由于持久对象存在无法被应用级垃圾回收机制感知的情况，导致后者难以修复失效的指针，因而破坏持久对象可重用性。为此，本文提出了移动无关寻址的概念，令可能无法被垃圾回收机制感知的指针指向一个确保可以被感知到的、指向被移动对象的间接跳转指针，并在对象移动后及时更新该跳转指针，从而确保对象移动后，被垃圾回收机制感知的指针不会失效。

文章设计和比较了三种新的持久对象编址与寻址方案，并在五个基准测试和一个真实应用中评估了这三种设计方案。结果表明，这三种解决方案，特别是由硬件支持的LGPointer方案，可以在合理的空间和时间开销内解决这个问题。

该成果“Preserving Addressability Upon GC-Triggered Data Movements on Non-Volatile Memory”已被期刊ACM Transactions on Architecture and Code Optimization（TACO）收录（Volume 19，Issue 2，April 2022，Article No.：28, pp 1-26），该期刊是ACM在体系结构领域的顶级期刊，年录用文章约38篇。

• 论文链接：
• https://doi.org/10.1145/3511706

摘要

应用级垃圾收集机制（Garbage Collection，GC）的运行会导致数据发生移动，造成NVM上对象正确寻址的复杂性。我们提出移动无关寻址（Movement-Oblivious Addressing，MOA）的概念，即在对象地址变化时，保留持久性对象的可寻址性。通过一个新设计的指针结构将不同持久内存区域（NVRegion）的对象之间的直接引用替换为间接引用，在对象移动时，只需要更新对象所在的区域内的引用，其他区域的间接引用在进行转换后，仍然可以到达该对象。

指针设计方案OPointer将区域ID和对象ID嵌入指针中，然后查找两个独立的表来定位对象地址。但当对象的数量在不断增加时，过大的表会导致查找效率降低。因此，我们提出了SGPointer，通过设置对象组来控制表的大小，以及受多级页表设计启发产生的LGPointer来增加对象分组的灵活性。这些解决方案使GC在对象移动时也具有跨内存区域寻址能力。且我们提出了纯软件实现和基于硬件的实现两种实现方法，以满足不同情况下的需求。

本工作中提出的技术仅产生0.4%（硬件解决方案）或21%（软件解决方案）的性能开销，且所提出的技术给NVM带来的额外写入流量可以忽略不计。实验证明，这些解决方案可以有效实现MOA。

背景与动机

NVM的好处主要体现在数据的可重用性上：数据可以在执行相同或不同程序时重用，而不需要类似于传统持久性存储进行对象序列化和反序列化。为了利用NVM的这个优势，必须在不同的NVM程序中保持持久性对象的可寻址性。

然而，应用程序级的垃圾收集机制会自动管理程序所使用的内存。它检测失效对象，收回它们占用的内存，并将空闲的内存空间聚集在一起，以减少内存的碎片化。这种操作可能会导致原有的对象指针失效。

图1通过一个实际数据集和三个应用程序的示例来说明这个问题，每个应用程序都对应于一个真实世界的软件程序（假定已经被修改为支持NVM）。

第一个程序OpenRefine_NVM，使用存储原始数据的NVRegion 1，这些数据包含学生的基本信息。NVRegion 2存储了从原始数据反序列化的Java对象，以方便从Java程序中访问数据集。第二个程序Tableau_NVM，结合清理过的数据和一些人口普查数据，产生了NVRegion 3。它包含生成的图表，在每个节点中建立一个引用，将其与NVRegion 2中的学生记录联系起来。

随后，第三个程序MTL_NVM会从清理过的学生数据集中建立起学生成绩预测模型。当MTL_NVM分配数据时，会自动触发垃圾收集机制。该机制会移动NVRegion 2上的学生记录。但MTL_NVM的视图只包括NVRegion 2和NVRegion 4，所以并不会更新NVRegion 3的引用，从而导致NVRegion 3的引用失效。

图1 GC导致NVM上数据可寻址性丢失的示例（NVM即为持久内存）

即NVM可能由许多内存区域组成，每个区域是独立的，一个对象可能被不同区域中的多个程序中的其他对象所引用。由于权限和创建访问时间的问题，当某个程序中的垃圾收集线程移动对象时，该线程没有办法更新指向该对象的所有指针，从而导致未更新的指针失效。

设计与实现

首先我们需要给出MOA的定义，明确我们的工作范围，然后通过三种逐步递进的方案来实现NVM上对象的MOA。这三个方案有一个共同的基本想法，即通过新的指针结构和辅助寻址方案，用间接引用取代直接引用。

移动无关寻址的定义：令O为一个数据对象，令S为时间t内指向O的数据引用的集合。∀p,p∈S⇔L1=T(p)，其中L1是对象O的虚拟地址，T(p)函数返回引用p对应的目标地址。

如果一个寻址机制满足以下条件，即为移动无关寻址的：当对象O在时间t内将其虚拟地址从L1( L1≠L2)改为L2时，∀p,p∈S，T (p)的目标地址在时间t之后立即改变为L2。

Opointer解决方案：该方案的基本思想是，当有数据移动时，通过用间接引用替换直接引用，将需要进行的地址更新操作本地化。替换过程是通过一个新的指针结构和一些辅助系统数据结构以及运行时的操作实现的。

OPointer将8B的指针分成两个字段。前32位表示区域ID（RID），后32位表示对象ID（OID），每个OID与需要MOA的对象相关。

图2为Opointer的引用转换示例和伪代码。对OPointer引用进行转换包括两个操作，通过利用RTB（将RID转化为区域的基址的表）和OTB（将OID转化为区域内偏移量的表），将OPointer中包含的RID和OID分别翻译成目标持久内存区域的基地址和该区域中对象的偏移量，然后将它们组合成目标对象的地址。

图2 OPointer的解除引用说明

OPointer的主要缺点是访问OTB频繁且访问速度慢。它为每个被其他区域引用的对象分配一个OID，因此，OTB的大小可能很大，且每次引用转换都需要访问OTB。OTB较大可能会导致多次缓存未命中，从而引用转换速度很慢。

多尺寸Pointer（SGPointer）：SGPointer是OPointer的一个变种。它通过将对象分组，并在分组对象中共享组ID（GID）来减少OTB的大小。在SGPointer中，一个对象组是一个连续的内存空间，具有以下属性：（1）一个对象组是数据移动的最小单位；（2）一个对象可以超出它所属组；（3）一个组不能与另一个组重叠；（4）组的大小是预定义的。

如图3所示，指针现在由四部分组成，RID、T、GID和Offset。前30位为RID，后面两位构成T字段。T可以是0-3，分别对应于实现方案中的1 B、256 B、4 KB和64 KB，用于表示一个对象组的大小类型。剩下的位构成GID和Offset字段，表示组ID和组内偏移量。

图3 SGPointer示例

OPointer中较大的OTB和AOTB（OTB逆操作的表）被小得多的GTB（组ID转化为组的基地址的表）和AGTB（GTB逆操作的表）所取代，数据定位效率和缓存性能均有所提升。

辅助数据结构也被相应改变，以支持多尺寸的设计。SGPointer使用了四个GTB，作为一种优化，SGPointer使用一个AGTB而不是四个AGTB。它通过将组的类型字段与GID连接起来，将每个区域内的偏移量与由组类型字段和GID组成的值进行映射。

多级Pointer（LGPointer）：尽管SGPointer提供了组大小的灵活选择，但每个组的大小是固定的。如果一个大的组在运行中出现碎片化问题，它无法通过分解成更小的组来缓解这个问题。我们引入了LGPointer来增强SGPointer在组大小上的动态适应性。在这种设计中，在运行时，一个对象组可以被分割成多个较小的组，多个小组可以合并成一个大组，且这些操作对应用程序、程序员和用户都是透明的。

图4上面的方框显示了一个多级GPointer的结构。前32位为RID。接下来的32位被分为四个字段，P0到P3，它们是与GTB相关的索引。

图4 多层次的GTB示例

P0是第一级GTB的索引，即GTB0。GTB0中的一个条目是两种类型之一。如果它的类型位是0，该条目是对象区域中下一级GTB（GTB1）的偏移量。如果该位为1，它是区域中一个16MB的对象组的偏移量，指针P1P2P3一起构成了该16MB对象组中的对象偏移量。GTB1和GTB2的设计与GTB0相同，只是它们对应的对象组大小为64KB和256B，对象偏移量分别为P2P3和P3。因为GTB3中是1 B的大小，所以不需要组内偏移量。每个对象区域只有一个GTB0，但有n i-1个GTBi（n i-1是所有GTB(i - 1)的条目总数；i = 1, 2, 3）。

多级GPointer的另一个特性是，允许分割和合并满足条件的对象组。分割时首先定位要分割的对象组的GTB条目，然后准备一个下一级的GTB，最后用新的GTB的区域内偏移量填充被分割的条目，并将类型位设置为0。组合并将符合条件的小组合并到一个大组中，以减少GID的数量。这个过程与组拆分相反，但合并需要符合一定的限制条件，以避免空间中的组冲突。

多级Gpointer方案中的组大小的动态可调整性，为增强GTB访问的局部性和减少组中内存的碎片化提供了机会。

硬件支持：这三种类型的指针都以指针重定向为中心，因此，它们都有一定的重定向开销。我们提出了使用硬件来加速指针的重定向过程。主要想法是在指针转换中避免基于软件的位操作，用专用的TLB（translation lookaside buffer）来进行缓存转换。

具体而言，我们在OPointer的硬件支持设计中，引入了一个区域-对象转换旁观缓冲器（ROTLB）。在SGPointer设计中引入了一个多尺寸区域组的TLB（RSGTLB）。在LGPointer的硬件支持中，使用了四个可以并行搜索的缓冲区，每个缓冲区用于四种级别的指针种的一种。

先前的研究表明，GC对NVM程序产生了1.01%到34.8%的运行时间开销。本工作中提出的技术会产生0.4%（硬件解决方案）或21%（软件解决方案）的性能开销，且所提出的技术给NVM带来的额外写入流量可以忽略不计。实验表明，基于硬件实现的SGPointer和LGPointer方案可以有效实现MOA。

详细内容请参见：

Chencheng Ye, Yuanchao Xu, Xipeng Shen, Hai Jin, Xiaofei Liao, and Yan Solihin. Preserving Addressability Upon GC-Triggered Data Movements on Non-Volatile Memory. ACM Transactions on Architecture and Code Optimization (TACO), 2022, 19(2): 1-26.

https://doi.org/10.1145/3511706

转载请注明来自网盾网络安全培训，本文标题：《ACM TACO22：持久内存垃圾回收机制下的对象寻址方法》

标签：垃圾持久性