关于作者： 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) 清理白色类，因为所有活动的类已经标记为黑色。