本文将介绍 Ruby 2.2 引入的增量垃圾收器（GC）。我们称该算法为 RincGC。与 Ruby 2.1 相比缩短了GC中断时间。

关于作者：?Koichi Sasada?，供职于 Heroku ，还在 Nobu 和 Matz 开发 C Ruby 内核。此前他写了YARV Ruby 的虚拟机，并且将分代垃圾收集?(RgenGC) 引入到 Ruby 2.1。Koichi 为 Ruby 2.2 写了增量垃圾收集器和本文。?

Ruby 使用 GC 自动收集不再使用的对象。感谢 GC，Ruby 程序员不用手动释放对象，而且不需要关心对象释放引起的bug。

Ruby 在第一个版本就已经有了 GC，使用的算法是?mark and sweep (M&S)。从两个层面上讲 M&S是最简单的 GC 之一：

(1) 标记: 遍历所有活动的类，标记为“活动类”。 (2) 清理: 未标记且不再使用的类将被当作垃圾收集。

M&S 基于一种假定：可被访问的活动类才是活动类。?M&S 算法简单且有效。

图：标记和清除，GC 算法

这种简单且有效的算法（它是一种保守的垃圾收集算法）因为允许使用 C 扩展，所以算法比较容易扩展。因此 Ruby 获得许多有用的扩展库。同时也是因为这种算法，导致迁移到类似?compaction and copying 算法时很困难。

今天，因为我们可以使用 FFI (外部功能接口)，所以 C 扩展已经不那么重要。然而在起初拥有大量的扩展库，提供丰富的功能是 Ruby的一大特色，并因此而流行开来。

尽管 M&S 算法简且好用，但仍然存在一些问题。最重要的问题就是“吞吐量”和“暂停时间”。GC过载时会拖慢你的 Ruby程序。换句话说，低吞量增加你程序的执行时间。每一次垃圾收集都要中断你的 Ruby 应用程序。长时间的中断影响 web 应用程序的 UI/UX 效果。?

Ruby 2.1 引入分代 GC 克服“吞吐量”问题。分代 GC将堆空间分割为若干个空间，称为代（Ruby 将堆空间分成两个空间，一个是“young",一个是“old"）。新创建的对象放在“young”，标记为 "young object"，GC 处理过几次（Ruby 2.2 是 3 次）之后，"young object" 将标记为“old object"并且放在 "old" 空间。在面向对象编程中，我们知道大部分对象是在“young” 时期生命周期就结束了，基于此我们只需要在“young space”运行 GC，如果在“young”没有足够的空间创建新对象，我们才在“old space”运行GC。我们把运行在“young space”的 GC 称为“Minor GC”，把运行在两个空间的 GC 称为“Major GC"，我们定制实现分代GC算法，我们称之为?"RGenGC"。了解更多请点击?RGenGC at my talk at EuRuKo?和?slides。

RGenGC戏剧性地提升了 GC 的吞量，因为 minor GC 非常快。但是 major GC 必须中断较长时间，相当于 Ruby 2.0 及之前版本。大多数 GC 是 minor GC，但是少数 major GC 会中断你的 Ruby 较长时间。

图：Major GC 和 minor GC 中断时间

增量 GC 算法是一个知名算法用来解决长时间中断问题。

增量垃圾收集器的基本思路

增量 GC 算法将执进程分为几个细粒度的进程和交错 GC 进程和 Ruby 进程。在一段时间内，增量垃圾收集器使用多次短的中断，而不是一次长的中断。与后者相比，虽然总的中断时长是一样的（也可能因为增量 GC 的开销而更长一些），但每次中断时间很短暂。这使得性能更稳定。

Ruby 1.9.3 引入了“延迟清理”GC，在清理阶段可以减少中断时间。延迟清理的思路是清理不是一次性的，而是分步的。延迟清理将增量垃圾算法的单次清理次数降低一半。现在我们需要将 major GC 标记为阶段增长。

让我们通过三个术语来解决增量标记：“白对象”是没有被标记的对象，“灰对象”是已经标记的对象，而且可能引用了一个白对象，“黑对象”是被标记的对象，但它不指向任何白对象。

使用这三种颜色，我们可以解释标记和清理算法，如下：

(1)所有存在的类标记为白色 (2) 清理栈中标记为灰色的类(3) 选择一个灰色类，访问该类引用 的每一个类，并标记为灰色。将先前的类标记为黑色。重复操作直到没有灰色类，只剩下黑色类和折色类。?(4) 清理白色类，因为所有活动的类已经标记为黑色。

为了使这一过程是增量的，我们必须让 (3)是增量的。 我们这样来做，选择一些灰色类并将他人的引用标记为灰色，然后返回 Ruby 执行过程，再继续增量标记，不断重复这一过程。?

图：普通标记?(STW: 停止整个应用) vs. 增量标记

增量标记存在一个问题。在 Ruby 执行过程中黑色类会引用白色类。引起该问题的原因是我们把黑色类定义为没有引用白色类的类。为了阻止这种情况，我们需要"write-barrier“，在创建过程中发现引用白色类的黑色类。

假如，一个数组对象已经被标记为”黑色“。

ary = []
# GC runs, it is marked black

现在，创建一个新对象 object obj = Object.new 是白色的，如果我们运行以下代码

现在一个黑色类指向了一个白色类。如果没有灰色类指向 obj，obj 在标记阶段结束时是白色，这将产生一个错误。清理时会产生重大 bug，我们要避免这个错误。

一个类指向一个新类时，write-barrier 将被调用。write-barrier 会检测到一个黑色类指向了一个白色类。当该事件发生时，黑色类将被标记为灰色（或者将白色类标记为灰色），write-barrier 彻底解决了GC 的这人灾难性 bug。

如你所见，增量 GC 算法的基本思路并不困难，或许你会问：“为什么 Ruby 还没有使用这种简单的 GC 算法”。

Ruby 2.2 的增量 GC

在 Ruby 解释器里实现增量标记有一个大问题。 (CRuby)：缺少write-barriers。Ruby 没有足够的write-barriers。?

在 2.1 上实现的分代 GC 也需要write-barriers。为了引入分代 GC，我们发明了一种新技术叫做”write barrier unprotected objects“。这意味着我们将所有类分成“write barrier protected objects”（保护类）和”write barrier protecte objects“（非保护类）我们可以保障所有保护类的引用都是被管理的。我们不能控制非保护类的引用。引用”非保护类“我们可以为 Ruby2.1 实现分代 GC。

使用非保护类，我们也可以做增量GC：

（1）将所有活动对象置为白色。
（2）将确定活动的类置为灰色，包括栈里的类。
（3）选择一个灰色类，访问类的每一个引用，并置为灰色。将我们最初选择的类置为黑色。
重复以上过程，直到没有灰色类，只剩下白色类和黑色类。这一步是增量实现。
（4）将可以指向白色的非保护类置为黑色，这样所有非保护的黑色类只需一次扫描。
（5）收集所有白色类，因为所有活动类已经被置为黑色。
引入（4）可以保证没有非活动的白色类。

图：在标记结束时重新扫描写屏障的非保护类。

不幸的是引入步骤（4）会引起我们希望避免的长中断次数。
中断时间和写屏障的非保护类的数量有关。在Ruby语言中，大部分对象是String,Array,Hash和用户定义类，它们都是有写屏障的保护类。所有写屏障非保护类引起的长中断在大多实际运行中并不会产生什么问题。