MemLiner: Lining up Tracing and Application for a Far-Memory-Friendly Runtime

1 简介

数据中心现在广泛部署需要大量内存开销的数据分析系统和机器学习系统，如Neo4j、Cassandra、Spark、TensorFlow等，因而越来越受到内存限制（memory constrained）。为了缓解内存约束，远端内存（far-memory）技术越来越具有吸引力，其使得应用程序可以通过网络和适配的硬件访问远程内存（remote memory），并且相对于本地块存储设备有着更低的延迟和更高的带宽。
大多数远端内存系统的设计基于缓存-交换（cache-and-swap）机制，即应用程序所在主机的内存作为远端内存的数据缓存（data cache）。因此具有优秀局部性和高效性的缓存技术对于该系统的优化是十分关键的。
然而，数据中心的大多数负载源自使用高级语言编写的应用程序，如Java、Go和Python，垃圾回收严重干扰了这些程序的远程内存访问的局部性和预取算法。Figure 1说明了这种冲突干扰，应用程序线程按照编程顺序访问内存，与此同时GC线程也会并发（concurrently）从根对象（root objects）开始遍历扫描活跃内存对象（live objects），而这两者并不协调，导致严重的性能问题。

问题1：资源争用：
GC线程的内存扫描不仅会遍历近期使用的块（标记活跃），也会遍历近期不使用的块（标记淘汰），然而在远端内存系统中，这些不需要使用的块仍会在GC扫描时被拉回内存，可能导致应用程序内存未名中并且增大RDMA带宽。本文中的实验证明，使用25%内存配置的Shenandoah GC上的Spark程序会因为GC的资源争用导致12倍的端到端性能衰减，这是使用STW（stop-the-world）的默认G1 GC的5倍。

问题2：无效预取：
由于GC线程并发扫描内存，导致操作系统级的预取算法无法识别和学习应用程序的内存访问路径在远端内存系统中，即使为简单的顺序模式。这使得操作系统认为应用程序的访问过于随机，因而预取器会无效预取或放弃预取。

SOTA：
以往的GC优化方案中并不聚焦于大内存足迹（memory footprint）,比如Platinum算法主要聚焦于在内存充裕的服务器上提高并发GC的吞吐量并降低时延。而远端内存技术主要关注于为主机提供远大于本地内存的内存空间，因此需要针对其开发新的GC算法。一项近期的研究Semeru将JVM分离为两个以支持在分离式（disaggregating）硬件下运行Java程序，CPU-JVM在CPU服务器上运行程序、memory-JVM在内存服务器上运行GC。这种分离设计的初衷是在内存所在的内存服务器上直接运行GC，而非在远程服务器上调用而带来性能开销，同时减轻远程服务器的负载。缺点是引入了额外的开发挑战。另一项研究AIFM则提出了一种新的运行时来提高远端内存系统的预取-交换性能。但其面向原生语言（C/C++）程序，因而无法简单移植到高级语言运行时GC。

MemLiner：
MemLiner是针对使用远程内存的高级语言应用程序的全自动运行时技术，其设计基于以下两个观察：（1）应用程序的对象访问和GC的并不是无关的，仅仅只是不在时域上对齐，因为GC扫描的活跃内存必然是应用程序在此前访问过的，同时应用程序近期访问的所有对象必然是GC扫描的目标；（2）尽管改变应用程序线程的内存访问顺序是破坏语义的，但GC线程不是，GC线程扫描追踪的目的是标记哪些对象可达（仍被使用），因此追踪的顺序不影响GC。因此MemLiner设计的关键点便是对齐工作集，使得GC线程的访问尽量对其应用程序线程的内存访问，以增大工作集的重合度，消除资源争用，优化按需交换。MemLiner主要解决了以下问题：

1. 如何将GC线程对齐至应用线程：传统方法是让GC简单地从根开始遍历对象调用图（object graph）；为了对齐，MemLiner采用了基于优先级的算法，应用线程通知GC其正在访问的对象，GC立刻追踪并标记当前对象图中可立即访问到的那部分对象。MemLiner修改了读写屏障（read-write barrier）使其支持这种通知，详见4.1节。
2. 何时打破对齐使得GC可以在不引入额外延迟的情况下完成工作。在GC标记之后还需要释放无效堆空间来完成回收，而这会带来应用线程的严重时延，因为这一过程需要很长时间并访问很多对象。事实上，严格的对齐是不必要的，因为诸如循环等情形下，应用程序会反复访问对象，而GC仅需要标记一次。因此MemLiner支持GC线程打破对齐而去进行其他空间的遍历。为了减少GC的干扰，MemLiner优先以下两类对象的不对齐访问：（1）应用程序在未来极可能访问的；（2）应用程序不久前曾访问并且须在内存中停留的。详见4.2节。
   MemLiner集成在OpenJDK 12的G1和Shenandoah GC中，并测试了Spark、Cassandra、Neo4J、QuickCached和DayTrade应用环境。在25%和13%的内存配置下，G1 GC平均端到端执行时间提高1.48倍和1.51倍，Shenandoah GC则为2.16倍和1.80倍，可提升Leap预取覆盖率1.5倍、准确率1.7倍。参考转移算力的Semeru方案，MemLiner可以在不转移的前提下提供可观的性能。

Key Takeway：相比于之前的工作——从头设计的AIFM和Kone、优化交换的InfiniSwap和FastSwap、分布式运行时Semeru——MemLiner采用易于适配（easy-to-adopt）的非侵入（non-intrusive）方案即可提升大多新老应用的性能。MemLiner和此前的所有方案都不同，其对齐应用线程和GC线程的内存访问以减小线程级干扰，使得无需考虑远程访问机制即可优化应用程序本地内存工作集。

2 背景

...

3 动机

追踪线程和应用间的干扰：
论文首先设计了一个对比实验，在有两台服务器的远端内存系统上运行Spark逻辑回归（LR），负载为Wikipedia数据集，OpenJDK 12使用默认的G1 GC，其内存配置为充足的25%，并且总堆内存为32GB、主机堆内存最多8GB。实验对比了开启和关闭G1 GC并发追踪时缺页错误（page fault）并计算了Linux页交换预取器的预取准确率。Figure 2(a)和2(b)对比了缺页错误发生的位置，可以发现启用并发追踪后缺页错误更为随机，因而导致缓存利用率低且预取准确率（见Figure 2(c)）显著降低。对于应用线程来说，缺页错误的发生速率由无并发追踪的3.5k/s跃升至开启并发追踪后的9.6k/s，可见干扰程度之严重。

为何不直接禁用并发追踪？
现代GC使用并发追踪的目的是为了在回收阶段可以尽量减少暂停时间，以保证时延敏感（latency-sensitive）的应用程序随时可用，因此如Shenandoah GC的算法必须依赖并发机制，即使是G1 GC这里采用STW机制的算法可以在STW期间再执行扫描，但禁用并发仍会显著带来端到端延时。对上述试验重复运行10次并测量每次的端到端执行时间和GC暂停时间，结果表明禁用并发后总执行时间平均增加18%、GC STW时间增加2.7倍，其中最长一次的full-heap GC用时76.9s，这么长时间的暂停显然无法接受。

Key Takeway：
GC线程和应用线程的内存访问模式大相径庭，因而导致显著的工作集增加和预取器失效，而简单的禁用并发追踪则会带来长时间的暂停因而无法作为有效的解决方案，因此需要提出新的GC优化方案。MemLiner则以此为动机，提出了一种无需额外引入GC暂停的方法来优化本地内存命中和既有预取器的效率，进而有效减少应用端到端执行时间。

4 设计和实现

4.1节介绍如何使得GC并发追踪可以立即发生在应用线程访问内存后，4.2节介绍如何设计新的基于优先度的算法使得GC可以在低干扰的前提下追踪其余的活跃对象。MemLiner的实现位于两个部分，一是运行时库的GC算法，二是内核的交换系统（swapping system），不需要对应用进行任何修改。目前论文聚焦于OpenJDK JVM，而算法原理同样适用于其他高级语言，同时已有的交换算法如InfiniSwap和FastSwap仍可以用于优化MemLiner因为其并未对内核机制进行修改，即与远端内存访问具体实现和软硬件支持无关。

4.1 Application and GC Coordination

为了对齐内存访问请求，应用线程需要主动通知GC线程其正在访问的对象，使得GC可以立即追踪这些对象。为了实现这一通信，论文需要监控每次堆读写指令以获取指针解引用并发送对象指针给GC，因此需要一个线程内的生产者-消费者队列（PQ，producer-consumer queue）以存储所有的诸如a=b.f、a=b[i]、b.f=a和b[i]=a的对象指针操作所对应对象。为了优化性能减少维护开销，PQ采用非阻塞ring buffer实现，所有的指令实现在OpenJDK提供的读写屏障实现内部，以保证解引用的正确性。由于通常应用线程数远大于GC线程数，因而PQ的访问争用是较少的。
Ring buffer中生产者和消费者是完全不同步的，并且即使队列满了也不会阻塞生产者（应用线程）写入（将覆盖旧的条目），这并不会影响GC的正确性，因为这些主动通知的调用表明其具有更高的优先级，即使未通知也会在最终GC的调用图中被遍历到，而这种机制可以消除应用线程写PQ的阻塞。
另外，在具体的程序实现中，并不会严格按照访问负载入队，比如连续的访问同一对象，因为在每次入队前会先检查全局活跃位图（global live bitmap）中该对象是否已标记为活跃，并滤去已标记的那些对象。

4.2 MemLiner Tracing Algorithm

4.2.1 Design overview
GC并不能仅依靠应用程序访问的对象来确定回收范围，而是需要完成所有活动对象闭包的计算。因而关键问题是如何在不显著增大应用无关工作集的前提下快速进行闭包计算（closure computation）。一方面，算法期望尽快追踪尽可能多的活跃对象，即使其不在PQ中；另一方面，GC又不能追踪过多的对象，尽量不追踪不在本地内存中的对象，以减少缺页错误和不必要的内存交换。MemLiner必须解决这两者看似矛盾的目标。

对可达对象进行分类：
论文将所有的活跃对象分为三类，如Figure 4所示。（1）已在本地内存中的对象（如：数据缓存）：这类对象为应用程序已经访问过但还没淘汰的，追踪这些对象显然不会产生缺页错误，大多数此类对象会进入PQ中。（2）在远程内存中且近期会被应用访问：这些对象一般出现在当前执行代码的未来几次调用处，尽管其目前不在本地，但GC访问产生的缺页错误并不影响，因为应用仍需使用它们。（3）在远程内存中且近期不被访问：这些往往是从本地内存淘汰到远端内存中的，且在最终的GC中仍需要被再次访问，但是立即追踪这些是不必要的，因为这会带来不必要的交换开销。

GC如何按分类处理对象：
MemLiner的主要设计为让GC尽可能追踪前两类对象，同时避免提前追踪第三类以减少干扰。在具体实现中，MemLiner会对已在PC中的对象（图中红色圆）再向前追踪MAX_Depth级对象（图中蓝波浪线圆），以尽可能快的对前两类对象进行处理而避免访问第三类。并行追踪线程会在如下两个模式间进行切换：（1）当PQ非空时，追踪PQ内的对象和其未来的引用；（2）当PQ空时，同传统GC一样从根对象开始遍历对象图。

4.2.2 对象位置估计
MemLiner GC需要知道一个对象是否位于本地内存中，但直接查询页表的开销过大，因此需要设计估计算法。具体来说，作者将所有对象访问的分割抽象为轮次（epoch），每次访问时同时带上此轮的id（下称epoch ID），GC可以使用epoch ID估计对象是否在本地内存中。
MemLiner监测内核交换频率，并在交换的JVM页面大于规定阈值时，认为新轮次开始，此时全局轮次计数器加1。而在64位JVM的实现中，对象引用对应的虚拟地址指针低42位（注：OpenJDK 15已支持根据堆大小动态设置为42-44位）具体的指针地址，高22位则保留给各GC算法。MemLiner则设置了4位时间戳（timestamp）和4位GC以维护数据结构，其中4位时间戳则存储了最近一次解引用时的轮次。如果下次访问的轮次和记录的时间戳相差小于给定的阈值δ，则说明该对象大概率还停留在本地内存之中。

4.2.3 MemLiner Tracing Algorithm
该小节详细叙述了前文设计总览的算法实现，并提供了追踪算法的伪代码。追踪线程的主要逻辑为：
（1）检查PQ是否空，若非空，则先将队列中的元素和其后MAX_Depth级对象推入追踪队列（TQ，tracing queue）；
（2）依次取出TQ的元素（类似于传统图遍历），并判断其时间戳与当前epoch ID是否相差δ以内，如果相差过大则推迟处理，并将其延迟计数器（delay limit）加1，如果延迟计数器大于阈值MAX_DL则说明需要立即处理，否则重新插入TQ；
（3）如果该TQ中取出的对象未被标记，则进行标记（bitmap置1），并将该对象直接引用对象推入TQ中。

自适应调节MAX_DL：
基本思路为：如果堆越满，说明越需要尽快执行完整的GC，因而需要小的MAX_DL以减少延迟追踪。MemLiner设置了两个阈值：15%和50%，当可用堆内存小于15%时（红区）MAX_DL为0，当可用堆内存在15%至50%之间时（黄区）MAX_DL为2，更多空间（绿区）则MAX_DL为4，这些值的选取源自实际测试负载的表现。

4.3 Discussion

MemLiner一方面可根据内存交换行为自适应设置时间戳（即访问轮次），一方面可以根据堆空闲自适应设置MAX_DL。前者辅助预测对象是否在本地内存中，而不必查询页表减少开销，后者则动态调整了第三类对象追踪的延迟程度，有助于在不同堆可用内存时调整GC策略。本节基本就是前文已有内容的展开讨论，因此不再赘述。

5 特定GC的优化

MemLiner实现在两个具有代表性的GC上，G1 GC和Shenandoah GC。G1 GC主要针对GC吞吐量进行优化设计，因而对内存进行分代处理而时序上则仅采用STW。Shenandoah GC主要针对线程暂停进行优化设计，因而引入了并发追踪和SATB机制。如果简单的将MemLiner算法实现在读写屏障中，则会带来巨大的运行时开销，因而需要针对GC进行优化。经过优化，在纯本地内存的测试中，仅相对于Shenandoah和G1原始算法带来2%和5%的额外开销。

• 优化1：MemLiner进队操作的读屏障仅启用于并发追踪时，当未启用并发追踪时，PQ并不会插入对象。
• 优化2：G1 GC的并发追踪仅扫描老至老（old-to-old）引用，而新生代并不被并发追踪访问，因此读屏障也不对新生代对象启用。
• 优化3：当对象的时间戳与当前epoch ID相同时，不需要更新时间戳。当本地内存越大时，代数的更新越慢，该优化的效果也越明显。

6 限制

MemLiner的设计依赖于成熟的运行时库，因而对C/C++等原生应用无效。MemLiner使得并发追踪更高效，减少对应用程序的干扰，同时显著减少full-heap GC的频率，但提高了每次GC的暂停时间。MemLiner主要对齐的是追踪线程，但发生内存回收时仍会对应用程序带来干扰，MemLiner无法优化该干扰。

7 实验评估

7.1 Experiment Setup

...
具体负载见Table 1，按照内存访问特性可将所有负载分为3类：顺序访问为主（Spark）、随机访问为主（QuickCached、DayTrader）、混合访问模式（Cassandra、Neo4j）。本地内存使用cgroup配置为堆大小（32GB）的25%和13%。

7.2 Performance with G1 GC

对于25%的内存配置，相较于JVM基线的运行时间平均加速1.48倍，13%配置为1.51倍。MemLiner可减少81%的按需交换和56%的全部交换，相对于远端内存交换带来2.17和3.73倍的减速（25%和13%内存配置），MemLiner将其缩小至1.47和2.48倍。部分负载在13%内存配置时默认JVM的性能远低于25%配置，这说明小本地内存会带来巨大的内存缺失，MemLiner对这类负载的优化明显。并具体分析了Cassandra负载下的表现。以SKM和STC（两个Spark负载）为例，分析了不同本地内存大小下运行时间的变化趋势，当本地内存比例小于50%时，越小的内存MemLiner优化越明显，当大于50%时MemLiner和基准相差无几。

7.3 Performance with Shenandoah GC

...

7.4 Comparisons with Other Systems

Leap：Leap是一个高级的系统级预取器，其能更激进地预取连续页面，但是对于部分负载的GC指针追逐（pointer-chasing）场景，这种连续的预取可能无法发挥效果。论文使用Spark和Neo4j负载验证了MemLiner可用辅助Leap等系统级预取器以获得更好的性能，实验表面，相对于原JVM和Leap，MemLiner可提升平均1.6倍的性能，减少58%的按需交换和53%的总交换，且Leap的预取准确度和覆盖率对得到显著提高。

Semeru：Semeru提供了分离式内存运行时环境，其重新设计了JVM使其GC工作由CPU服务器卸载到物理内存所在的内存服务器。同样测试了Spark和Neo4j，但后者运行在Semeru上全部崩溃因此没有结果。Spark的三类负载测试结果都为MemLiner+FastSwap优于MemLiner+Semeru swap优于Semeru，这说明MemLiner可用很好地优化远端内存系统下的GC性能。

AIFM：简要说明了MemLiner无法与AIFM等针对原生语言的算法对比，但作者仍相信MemLiner的思路可用优化原生语言的页交换表现。

7.5 More Detailed Results

...

8 相关工作

Far memory：介绍了近年来的研究发现严重的“内存容量墙”（memory capacity wall），因而一些研究提出了远程内存访问机制，其中主流方案是基于RDMA和内存交换机制。随后介绍了一些优化RDMA访问远程内存的方案，如AIFM。

Modern GC：列举了一些常见的现代GC，如G1 GC、Shenandoah GC、Azul pauseless GC、C4等，随后介绍了大数据背景下基于NUMA特性、分类内存特性等设计的新GC算法，如Semeru、Mako等。然而这些GC算法都与MemLiner方向不同。

9 结论

本文介绍了运行时技术MemLiner，它可通过对齐应用程序和跟踪线程的内存访问来减少GC应用干扰。论文将内存可达（活跃）对象分为三类，并以不同的方式处理各类别对象，以实现两个看似冲突的目标。基于两个已有GC的实验结果表明，MemLiner非常适用于当今的（远端内存）数据中心。