分布式计算系统中的 GC 问题 | Yak (OSDI 2016) 学习笔记

最近一直在关注 OSDI 2016,发现了这篇关于分布式计算系统内存管理的论文:Yak: A High-Performance Big-Data-Friendly. Garbage Collector,感觉比较有趣,拿来总结总结~

Yak 是一个 JVM 平台上的针对大数据场景(分布式计算框架)设计、优化的 Garbage Collector。

背景

在传统的基于分代模型的垃圾回收算法中,小对象首先被划分到 Young Generation(新生代);如果对象经历过一定阈值的 GC 还会存活后,它就会被晋升至 Old Generation(老年代);大对象可以直接进入老年代。

对于分布式计算框架而言,这样的模型有一定的弊端:没有考虑分布式计算情景下对象的生命周期。分布式计算中控制过程(Control Path)与数据处理过程(Data Path)界限明显,如果全都用统一的 GC 模型的话,会导致频繁请求 GC 数据,扫描全堆,最后实际回收的很少,导致 Full GC (STW)。因此,像 Apache Spark 在 1.5 版本以后已经放弃使用 JVM 的 GC 进行内存管理,而是直接利用 unsafe 包进行内存管理。这样十分麻烦还容易出错。

Yak 就是为了解决这样的问题而诞生的。既然分布式计算过程中控制过程与数据处理过程界限明显,Yak 针对这两种过程中的数据划分了两种不同的空间(space):

  • Control Space (CS)
  • Data Space (DS)

对于控制过程(比如任务的调度、日志记录等),其内存布局与传统的一致,GC 还是采用分代模型,分 YoungGen/OldGen/Metaspace。控制过程产生的对象小、生命周期短暂,符合分代假设。

而对于数据处理过程,其中的对象通常都是很大的、在计算周期中一直需要访问的,因此 Yak 提出了 Epoch Region,数据对象的生命周期依赖于每个 epoch。每个 epoch 的 start 与 end 需要用户来设置(但是很简单)。

时域抽象

Epoch hypothesis: many data-path objects have the same life span and can be reclaimed together at the end of an epoch.

时域抽象(Epoch Region): 抽象成 semilattice(半格),用于描述 nested epoches 之间的偏序关系。见论文 Figure 5。(Order Theory在这里非常有用)

如何正确地回收某个特定的 Region

如果有的对象生命周期超出此 epoch,如何将其迁移至“安全地带”?

  • 思考点1:标记 escaping objects
  • 思考点2:决定 escaping objects 的迁移终点并且执行复制

对于标记的过程,可以以 cross-region/space references 为根节点来遍历对象图并且标记其中的 escaping objects(传递闭包)

对于决定其 destination 的过程,需要计算出对象 O 的引用 region 的上确界(via semilattice)。

如果对应的 region 具有继承关系,则应选择最上面的(上确界)。如果是不同线程执行的,那么对应的上确界则为 CS。

TODO: 待详细总结

文章目录
  1. 1. 背景
  2. 2. 时域抽象