本文将介绍 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“，在创建过程中发现引用白色类的黑色类。

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

现在，创建一个新对象 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和用户定义类，它们都是有写屏障的保护类。所有写屏障非保护类引起的长中断在大多实际运行中并不会产生什么问题。

我们只在major GC引入了增量标记，因为没有抱怨minor GC的中断时间。增量垃圾收集器的最大中断时间要小于minor GC的中断时间。如果你在minior GC不存在中断时间问题，就不用担心major GC的中断时间。

我还介绍过为Ruby实现增量垃圾收集器的一人小技巧。我们得到一系列“黑色非保护”类。为了快速执行垃圾清理，我们准备了一个非保护的bitmap代表非保护类，一个独立的已标记bitmap代表已标记类。使用两个bitmaps的逻辑可以获取“黑色非保护”类。

增量垃圾收集器中断时间评测
 

为了计量垃圾收集器产生在的中断时间，让我们使用 gc_tracergem. gc_tracer gem引用了 GC::Tracer模块在垃圾收集事件中获取相关参数。gc_tracergem将每个参数都保存在文件中。

垃圾收集事件包括以下事件：

• 开始

• 标记结束

• 清理结束

• 创建对象

• 释放对象

• 进入

• 离开

如我前面所解释，Ruby的垃圾收集包含两个阶段：“标记附件”和“清理”阶段。“开始“是”开始标记附件“事件，”标记结束“是”标记附件结束“事件，”标记结束“也现时意味着”开始清理阶段",当然“清理结束”代表”清理阶段“结束，也意味着垃圾清理过程的结束。

”创建对象“和”释放对象”很容易理解：对象分配和对象释放事件。

我们通过“进入”和“离开”事件计量中断时间。增量垃圾收集（增量标记和延迟清理）引入中断标记和清理阶段。“进入“是”进入垃圾清理“事件，”离开“是”离开垃圾清理“事件。

下图显示了当前增量垃圾收集器的事件时间。

垃圾收集器事件

我们可以计量每一个事件的当前时间（在 Linux 上当前时间是通过 gettimeofday() 获得）。所以我们可以通过“进入”和“离开”事件计量垃圾收集器的中断时间。

我使用 ko1-test-app 做为我们中断时间的基准。ko1-test-app 是我们的一个英雄“Aaron Patterson"为我写的一个小的 rails app

为了使用 gc_tracer，我添加了一条命名为“test_gc_tracer”的规则，如下：

运行 bundle exec rake test_gc_tracer KO1TEST_CNT=30000。我们通过数值“30000”指定模拟30,000个请求。我们可以在文件“log.xxxx”里得到结果（xxxx是程序的进程ID）。文件如下

在我的环境下，这里有 1,142,907 行。

“type”列是事件类型，tick 是当前时间（gettimeofday（）的输出结果，epoc总时间，单位是毫秒）。通过这些信息我们可以获取垃圾收集器的中断时间。通过前两行我们可以计算出中断时间为10 微秒 （1419489706840157 - 1419489706840147）。

以下小脚本显示每次中断时间。

这里有很多行，这个脚本打印了 100 微秒内的中断次数。

下图显示了统计结果

Measured GC pause times (over 100us)

在分代垃圾收集器中产生了7个较大的中断时间，他们应该是由“major GC”产生的。最大中断时间大概15毫秒（15Kus），不管怎样，增量垃圾收集器减少了最大中断时间（差不多2ms(2Kus))，太好了。

总结
 

Ruby 2.2 通过引入增量垃圾收集算法缩短了垃圾收集的中断时间。

请注意，增量垃圾收集器不是一个银弹。我曾解释过增量垃圾收集并不改善“吞吐量”，这意味着如果请求很长并产生多个 major GC，反应时间并不会得到有效改善。使用增量垃圾收集器并不会缩短总的中断时间。

请在 Heroku 尝试你的应用，期待你的挑战！