复盘 GC 算法的发展历程及现状

最近，我读到一些大肆宣传 Go 语言最新垃圾回收器的文章，这些文章对垃圾回收器的描述让我感到有些厌烦。这些文章有些是来自 Go 项目。他们宣称 GC 技术正迎来巨大突破。

下面 Go 团队在 2015 年 8 月发布的新垃圾回收器的启动声明：

Go 正在构建一个划时代垃圾回收器，2015 年，甚至到 2025 年，或者更久……Go 1.5 的 GC 把我们带入了一个新时代，垃圾回收停顿不再成为使用新语言的障碍。应用程序可以很容易地随着硬件进行伸缩，而且随着硬件越来越强大，GC 不再是构建可伸缩软件的阻碍。一个新的时代正在开启。

Go 团队不仅宣称他们已经解决了 GC 停顿问题，而且让整件事情变得更加“傻瓜”化：

从更高层面解决性能问题的方式之一是增加 GC 选项（也就是 GC 配置参数），每个性能问题使用一个选项。程序员可以通过选项为他们的应用程序找到合适的设置。不过，这种方式的不足之处在于，选项数量会不断增加，到最后很可能会需要一部“GC 选项操作者就业草案”。Go 不想继续走这条路。相反，我们只提供了一个选项，也就是 GOGC。

而且，因为不需要支持太多的选项，运行时团队可以集中精力根据真实的用户反馈来改进运行时。

我相信很多 Go 语言用户对新的运行时还是很满意的。不过我对之前的那些观点有异议，对于我来说，它们是对市场的误导。这些观点在博客圈内重复出现，我想是时候对它们进行深入分析了。

事实上，Go 的 GC 并没有真正实现任何新的想法或做出任何有价值的研究。他们在声明里也承认，他们的回收器是一种并发的标记并清除回收器，而这种想法在 70 年代就有了。他们的回收器之所以还值得一提，完全是因为它对停顿时间进行了改进，而这是以牺牲 GC 其它方面的特性为代价的。Go 相关的技术讨论和发行材料并没有提到他们在这个问题上所做出的折衷，让那些不熟悉垃圾回收技术的开发人员不知道这些问题的存在，还暗示 Go 的其它竞争者制造的都是垃圾。而 Go 也在强化这种误导：

为了创建划时代的垃圾回收器，我们在很多年前就采用了一种算法。Go 的新回收器是一种并发的、三基色的、标记并清除回收器，它的设计想法是由 Dijkstra 在 1978 年提出的。它有别于现今大多数“企业”级垃圾回收器，而且我们相信它跟现代硬件的属性和现代软件的低延迟需求非常匹配。

读完这段声明，你会感觉过去 40 年的“企业”级 GC 研究没有任何进展。

GC 理论基础

下面列出了在设计垃圾回收算法时要考虑的一些因素：

• 程序吞吐量：回收算法会在多大程度上拖慢程序？有时候，这个是通过回收占用的 CPU 时间与其它 CPU 时间的百分比来描述的。
• GC 吞吐量：在给定的 CPU 时间内，回收器可以回收多少垃圾？
• 堆内存开销：回收器最少需要多少额外的内存开销？如果回收器在回收垃圾时需要分配临时的内存，对于程序的内存使用是否会有严重影响？
• 停顿时间：回收器会造成多长时间的停顿？
• 停顿频率：回收器造成的停顿频率是怎样的？
• 停顿分布：停顿有时候很短暂，有时候很长？还是选择长一点但保持一致的停顿时间？
• 分配性能：新内存的分配是快、慢还是无法预测？
• 压缩：当堆内存里还有小块碎片化的内存可用时，回收器是否仍然抛出内存不足（OOM）的错误？如果不是，那么你是否发现程序越来越慢，并最终死掉，尽管仍然还有足够的内存可用？
• 并发：回收器是如何利用多核机器的？
• 伸缩：当堆内存变大时，回收器该如何工作？
• 调优：回收器的默认使用或在进行调优时，它的配置有多复杂？
• 预热时间：回收算法是否会根据已发生的行为进行自我调节？如果是，需要多长时间？
• 页释放：回收算法会把未使用的内存释放回给操作系统吗？如果会，会在什么时候发生？
• 可移植性：回收器是否能够在提供了较弱内存一致性保证的 CPU 架构上运行？
• 兼容性：回收器可以跟哪些编程语言和编译器一起工作？它可以跟那些并非为 GC 设计的编程语言一起工作吗，比如 C++？它要求对编译器作出改动吗？如果是，那么是否意味着改变 GC 算法就需要对程序和依赖项进行重新编译？

可见，在设计垃圾回收器时需要考虑很多不同的因素，而且它们中有些还会影响到平台生态系统的设计。我甚至都不敢确定以上给出的列表是否包含了所有因素。

设计领域的工作相当复杂，垃圾回收作为计算机科学的一个子领域，人们对它有着广泛的理论研究。学院派和软件行业会时不时地提出新的算法和它们的实现。不过，目前还没有人可以找出一种可以应付所有场景的算法。

折衷无处不在

让我们说得更具体一点。

第一批垃圾回收算法是为单核机器和小内存程序而设计的。那个时候，CPU 和内存价格昂贵，而且用户没有太多的要求，即使有明显的停顿也没有关系。这个时期的算法设计更注重最小化回收器对 CPU 和堆内存的开销。也就是说，除非内存不足，否则 GC 什么事也不做。而当内存不足时，程序会被暂停，堆空间会被标记并清除，部分内存会被尽快释放出来。

这类回收器很古老，不过它们也有一些优势——它们很简单，而且在空闲时不会拖慢你的程序，也不会造成额外的内存开销。像 Boehm GC 这种守旧的回收器，它甚至不要求你对编译器和编程语言做任何改动！这种回收器很适合用在桌面应用里，因为桌面应用的堆内存一般不会很大。比如虚幻游戏引擎，它会在内存里存放数据文件，但不会被扫描到。

计算机专业课程经常把会造成停顿（STW）的标记并清除GC 算法作为授课内容。在工作面试时，有时候我会问候选人一些GC 相关的问题，他们要么把GC 看成一个黑盒，要么对GC 一窍不通，要么认为现今仍然在使用这种老旧的技术。

标记并清除算法存在的最大问题是它的伸缩性很差。在增加CPU 核数并加大堆空间之后，这种算法几乎无法工作。不过有时候你的堆空间不会很大，而且停顿时间可以接受。那么在这种情况下，你或许可以继续使用这种算法，毕竟它不会造成额外的开销。

反过来说，或许你的一台机器就有数百G 的堆空间和几十核的CPU，这些服务器可能被用来处理金融市场的交易，或者运行搜索引擎，停顿时间对于你来说很敏感。在这种情况下，你或许希望使用一种能够在后台进行垃圾回收，并带来更短停顿时间的算法，尽管它会拖慢你的程序。

不过事情并不会像看上去的那么简单！在这种配置高端的服务器上可能运行着大批量的作业，因为它们是非交互性的，所以停顿时间对于你来说无关紧要，你只关心它们总的运行时间。在这种情况下，你最好使用一种可以最大化吞吐量的算法，尽量提高有效工作时间和回收时间之间的比率。

问题是，根本不存在十全十美的算法。没有任何一个语言运行时能够知道你的程序到底是一个批处理作业系统还是一个对延迟敏感的交互型应用。这也就是为什么会存在“GC 调优”——并不是我们的运行时工程师无所作为。这也反映了我们在计算机科学领域的能力是有限的。

分代理论假说

从 1984 年以来，人们就已知道大部分的内存对象“朝生夕灭”，它们在分配到内存不久之后就被作为垃圾回收。这就是分代理论假说的基础，它是整个软件产品线领域最贴合实际的发现。数十年来，在软件行业，这个现象在各种编程语言上表现出惊人的一致性，不管是函数式编程语言、命令式编程语言、没有值类型的编程语言，还是有值类型的编程语言。

这个现象的发现是很有意义的，我们可以基于这个现象改进 GC 算法的设计。新的分代回收器比旧的标记并清除回收器有很多改进：

• GC 吞吐量：它们可以更快地回收更多的垃圾。
• 分配内存的性能：分配新内存时不再需要从堆里搜索可用空间，因此内存分配变得很自由。
• 程序的吞吐量：分配的内存空间几乎相互邻接，对缓存的利用有显著的改进。分代回收器要求程序在运行时要做一些额外的工作，不过这点开销完全可以被缓存的改进所带来的好处抵消掉。
• 停顿时间：大多数时候（不是所有）停顿时间变得更短。

不过分代回收器也引入了一些缺点：

• 兼容性：分代回收器需要在内存里移动对象，在某些情况下，当程序对指针进行写入时还需要做一些额外的工作。也就是说，GC 必须跟编译器紧紧地绑定在一起，这也就是为什么 C++ 里没有分代回收器。
• 堆内存开销：分代回收器通过在内存空间里移动对象实现垃圾回收。这个要求有额外的空间用来拷贝对象，所以这些回收器会带来一些堆内存开销。另外，它们需要维护指针映射表，从而带来更大的开销。
• 停顿时间分布：尽管大部分 GC 停顿时间都很短，不过有一些仍然要求在整个堆内进行彻底的标记并清除操作。
• 调优：分代回收器引入了“年轻代”，或者叫“eden 空间”，程序性能对这块区域的大小非常敏感。
• 预热时间：为了解决上述的调优问题，有一些回收器根据程序的运行情况来决定年轻代的大小，而如果是这样的话，那么 GC 的停顿时间就取决于程序的运行时间长短。在实际当中，只要不是作为基准，这个算不上什么大问题。

因为分代算法的优点，现代垃圾回收器基本上都是基于分代算法。如果你能承受得起，就会想用它们，而一般来说你很可能会这样。分代回收器可以加入其它各种特性，一个现代回收器将会集并发、并行、压缩和分代于一身。

Go 的并发回收器

Go 是一种命令式的值类型编程语言，它的内存访问模式跟 C#类似。C#是基于分代理论假说的，所以很自然地，.NET 使用的是分代回收器。

实际上，Go 程序经常被用来处理请求和响应，就像 HTTP 服务器一样。也就是说，Go 程序表现出了十足的分代行为。Go 团队正在发掘一种他们称之为“面向请求的回收器”的东西。据悉，它很可能是一种重新命名过的分代回收器，只不过加入了经过调整的分代策略。

在其它语言运行时上可以模拟这种回收器，特别是那些请求和响应类型的处理器，只要确保年轻代大到可以容下请求所生成的垃圾。

不过，目前Go 的回收器并不是分代的，它在后台运行的仍然是老旧的标记并清除回收器。

Go 这样做有一个好处——它的停顿时间非常短，不过除此之外，其它方面会变得很糟糕。比如说呢？

• GC 吞吐量：清理堆内存垃圾所需要的时间随着堆的大小而伸缩。简单地说，程序使用越多的内存，内存就释放得越慢，你的电脑因此需要花更多的时间在垃圾回收上。除非你的程序完全不进行并行处理，你的 CPU 核数可以无限制地让给 GC 使用。
• 压缩：因为没有压缩，堆空间最终会发生碎片化。后面我会讲到堆的碎片化问题。因为碎片化，你将无法从缓存使用中获得任何好处。
• 程序吞吐量：因为 GC 每次需要做很多工作，会抢占程序的 CPU 时间，从而拖慢程序。
• 停顿时间分布：任何并发的垃圾回收器都会遇到 Java 世界的“并发模式故障”问题：程序制造垃圾的速度超过了 GC 线程清理垃圾的速度。在这种情况下，运行时只能暂停程序，等待当前 GC 结束。所以说，Go 虽然宣称它们的 GC 停顿时间很短暂，但这个说法只有在 GC 有足够 CPU 时间的情况下才能成立。另外，Go 的编译器不具备可靠暂停线程的特性，这意味着停顿时间的长短很大程度上取决于程序的代码（例如，在 Go 子程序里对大型二进制对象进行 BASE64 解码会让停顿时间变长）。
• 堆内存开销：通过标记并清除的方式来回收堆空间速度很慢，所以你需要额外的空间来确保不会出现“并发模式故障”问题。Go 默认使用 100% 的堆内存开销……也就是说，你的程序需要双倍的内存来运行。

我们可以从 golang-dev 上的一些帖子中看到 Go 在这方面做出的折衷，比如：

Service 1 比 Service 2 分配了更多的内存，所以停顿更加频繁。不过两个服务每次停顿的时间下降了一个数量级。我们可以看到，在对两个服务进行切换以后，CPU 的使用增长了大约 20%。

Go 让停顿时间下降了一个数量级，但却是以更慢的垃圾回收为代价。这是一种更好的折衷吗？或者说停顿时间已经足够好了吗？这些问题在帖子里并没有得到回答。

不过在这种情况下，通过增加更多的硬件换取更短的停顿时间已经毫无意义。如果你的服务器停顿时间从 10 毫秒下降到 1 毫秒，你的用户会感觉得到吗？如果你需要为此投入双倍的机器，你还会这么做吗？

Go 不断优化停顿时间以便保证 GC 的吞吐量，它似乎不惜以拖慢程序的速度为代价，哪怕可以缩短一点点的停顿时间。

与 Java 的比较

HotSpot 虚拟机提供了几种 GC 算法，可以通过命令行来选择使用哪一种算法。这些算法的停顿时间不像 Go 所宣称的那么短，毕竟它们要在各个因素间做出平衡。通过比较不同的算法可以对它们有一个直观的感受。重启程序可以切换 GC 算法，因为编译工作在程序运行之时就已完成，不同算法所需要的各种屏障可以根据具体需要被添加到编译的代码里。

现代计算机使用的默认算法是吞吐量回收算法。这种算法是为批处理作业而设计的，默认情况下不对停顿时间做任何限制（不过可以通过命令行指定）。跟这种默认行为相比较，人们会觉得 Java 的 GC 简直有点糟糕了：默认情况下，Java 试图让你的程序运行尽可能的快，使用尽可能少的内存，但停顿时间却很长。

如果你很在意停顿时间，或许可以使用并发标记并清除回收器（CMS）。这种回收器跟 Go 的回收器最为接近。不过 CMS 也是分代回收器，所以它的停顿时间仍然会比 Go 的要长一些：在年轻代被压缩时，程序会被暂停，因为回收器需要移动对象。CMS 里有两种停顿，第一种是快速的停顿，可能会持续 2 到 5 毫秒，第二种可能会超过 20 毫秒。CMS 是自适应的，因为它的并发性，它需要预测何时需要启动垃圾回收（类似 Go）。你需要对 Go 的堆内存开销进行配置，而 CMS 会在运行时自适应调整，避免发生并发模式故障。不过 CMS 仍然使用标记并清除策略，堆内存仍然会出现碎片化，所以还是会出现问题，程序还是会被拖慢。

最新的 Java 回收器叫作“G1”（Garbage First）。在 Java 8 里 G1 不是默认的回收器，不过在 Java 9 里它将会是默认的回收器。它是一种“一刀切”的回收算法，它会尽量满足我们的各种需求。它几乎集并发、分代和堆空间压缩于一身。它在很大程度上可以自我调节，不过因为它无法知道你的真正需求（这个跟其它所有的回收器一样），所以你仍然可以对它做出折衷：告诉它可用的最大内存和预期的停顿时间（以毫秒为单位），它会通过自我调节来达到预期的停顿时间。默认的预期停顿时间是 100 毫秒，只有指定了更低的预期停顿时间才能看到更好的效果：G1 会优先考虑程序的运行速度，而不是停顿时间。不过停顿时间并非一直保持一致，大部分情况下都非常短（少于 1 毫秒），在压缩堆空间时停顿会长一些（超过 50 毫秒）。G1 具有良好的伸缩性，有人在 TB 级别的堆上使用过 G1。G1 还有一些很有意思的特性，比如堆内字符串去重。

Red Hat 开发了一种新的算法 Shenandoah，并把它贡献给 OpenJDK，不过它并不会被用在 Java 9 里，除非自己从 Red Hat 编译一个特别版的 Java。不管堆有多大，该算法都会保证很短的停顿时间，同时可以对堆空间进行压缩。

这种算法会使用额外的堆内存和更多的屏障：在程序运行的同时在堆内移动对象，并维护指针的读写操作。在这方面，它跟 Azul 的“无停顿”回收器有点类似。

结论

这篇文章的目的并不在于说服你使用某种语言或工具。只是希望你能意识到，垃圾回收是一个很复杂的问题，而且相当复杂，一大堆计算机科学家已经为此研究了数十年。如果有任何所谓的突破性进展，一定要谨慎看待。它们可能看起来很奇怪，或者更像是对折衷的伪装，到最后只会暴露无遗。

不过如果你愿意牺牲其它方面来获得最小化的停顿时间，那么可以看看 Go 的 GC。

本文已获得原作者翻译授权，阅读英文原文： Modern garbage collection

感谢郭蕾对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们。