现代垃圾收集策略 —— Go 的 GC 策略

 在 [Hacker News](https://news.ycombinator.com/item?id=13218550) 和 [Reddit](https://www.reddit.com/r/golang/comments/5j7phw/modern_garbage_collection/) 你可以找到相关讨论 我最近看过很多文章，它们以令我困扰的方式推广 Go 语言最新的垃圾收集器。其中一些文章来自 Go 官方项目本身。他们声称这意味着 GC 技术已经有根本性的突破。 [这是新版本（Go 1.5）垃圾收集器的首次公告](https://blog.golang.org/go15gc): > Go 正在构建一个垃圾收集器（GC），不止适用于 2015 年，甚至适用于 2025 年，甚至更长时间 ... go 1.5 及以后的版本，重点解决 gc 中 stop-the-world 问题不再是安全可靠语言的障碍。未来应用程序可以毫不费力地随硬件一起扩展，随着硬件变得越来越强大，GC 不再是成为更好、更具可扩展性的软件的障碍。适用于未来十年甚至更久。 Go 官方团队声称不仅解决了 GC 暂停的问题，而且还让整个事情变得无脑： <!-- TODO: GC 旋钮 GC knobs怎么翻译？ 先 旋钮（knob） --> <!-- Turner Employment Act ？？就业法案？ --> > 在更高的层次上，解决性能问题的一种方法是添加 GC 旋钮（knob），每个性能问题添加一个。然后，程序员可以旋转旋钮（knob）以搜索适合其应用的设置。不利的一面是，每年使用一个或两个新旋钮（knob），十年之后，你最终会得到 GC 旋钮（knob）特纳就业法案（Turner Employment Act 应该的意思是：需要详细的文档描述说明各个 knob 的详细信息）。Go 不会走那条路。相反，我们只提供了一个叫做 GOGC 的旋钮（knob）。 > > 此外，没有持续支持数十个旋钮（knob）的影响，负责运行时开发、优化工作的团队可以专注于根据真实客户应用程序的反馈改进提高运行时系统性能。 我毫不怀疑许多 Go 用户对新 GC 的运行时间非常满意。但是我对这些说法有所质疑——在我看来，这就像是一种误导性的营销方式。随着这些声明在博客圈中重复出现，现在是时候深入了解它们了。 事实上，Go 的 GC 并没有真正实现任何新办法或者新的研究进展。正如他们的公告所承认的那样，它是基于 20 世纪 70 年代的方法，是一个直接的并发 **标记/清除** 收集器。值得注意的只是因为它的设计目的是优化暂停时间，但代价却是牺牲 GC 中所有其他期望的的特性。Go 的[技术讲座](https://talks.golang.org/2015/go-gc.pdf)和营销材料似乎没有提及任何这些平衡，让不熟悉垃圾收集技术的开发人员认为不存在这样的平衡，并且暗示，Go 的竞争对手只是糟糕的垃圾堆。而 Go 鼓励这种看法： > 为了创造适用于未来十年的垃圾收集器，我们转向了几十年前的算法。Go 新的垃圾收集器是一个**并发的，三色，标记-清除收集器**，这个想法被 [Dijkstra](http://dl.acm.org/citation.cfm?id=359655) 于 1978 年率先提出。这与当今大多数“企业级”垃圾收集器的不同，但我们认为它非常适合现代硬件的属性和现代软件的延迟要求。 阅读上述公告，如果你认为企业级” GC 在过去 40 年的研究根本没有取得任何成果，是可以被原谅的； ## GC 理论入门 设计垃圾收集算法时，需要考虑以下不同的因素： * **程序吞吐量**：您的算法减慢了多少程序？这有时表示为垃圾收集与有用工作所花费的 CPU 时间的百分比。 * **GC 吞吐量**：在给定固定的 CPU 时间量的情况下，收集器可以清除多少垃圾？ * **堆开销**：收集器理论上至少需要多少额外内存？如果你的算法在收集时分配临时结构，是否会使你的程序的内存使用非常紧张？ * **暂停时间**：你的收集器停止一次的时间有多长？ * **暂停频率**：您的收集器多久停止一次？ * **暂停分布**：您喜欢多数情况都是短暂的暂停，偶尔很长的暂停时间？还是时间更长但是更稳定的暂停时间？ * **分配性能**：新内存分配是快？是慢？还是不可预测？ * **紧凑**：在有足够的可用空间来满足需求情况下，是否会因为该空间已经分散在堆中的小块中，您的收集器是否会报告内存不足（OOM）错误？如果没有，你可能会发现你的程序变慢并最终死亡，即使它实际上有足够的内存。 * **并发**：您的收集器在多核机器的表现如何？ * **伸缩性**：对大小规模不等的 heap ，gc 表现怎么样 * **配置**：收集器的配置很复杂吗？是否可以开箱即用并获得最佳性能？ * **预热时间**：您的算法是否根据行为进行自我调整？如果是，需要多长时间才能达到最佳状态？ * **内存页释放**：您的算法是否会将未使用的内存释放回操作系统？如果是的话，何时？ * **可移植性**：您的 GC 是否在 CPU 体系结构上工作，提供比 x86 更弱的内存一致性保证？ * **兼容性**：您的收集器使用哪些语言和编译器？是否可以使用非 GC 设计的语言运行，比如 C ++？它需要编译器修改吗？如果是这样，更改 GC 算法是否需要重新编译所有程序和依赖项？ 你可以发现，设计垃圾收集器需要考虑很多不同的影响因素，其中一些因素会影响您平台周围更广泛的生态系统的设计。我不确定是否列出了所有的因素。 由于设计影响因素太多，必然复杂，垃圾收集是计算机科学研究论文中的一个子领域。学术界和工业界都在以稳定的速度提出并实施新算法。不幸的是，还没有人找到适合所有情况的单一算法。 ## 平衡，平衡各种因素 下边让我们更具体一点。 第一个垃圾收集算法是为单处理器机器和具有小堆的程序设计的。当时，CPU 和 RAM 价格昂贵，而且用户要求不高，所以可见暂停是允许的。因此，设计的算法优先考虑最小化收集器的 CPU 和堆开销。这意味着： 内存分配完了才让 GC 工作。然后程序将暂停，并对堆进行一次完整的 标记/清除，以尽可能快地标记空闲部分 这些类型的收集器虽古老，但仍然具有一些优点——简单，不收集程序时不会减慢速度，也不会增加任何内存开销。对于像 [Boehm GC](http://www.hboehm.info/gc/) 这样古老的收集器，他们甚至不需要更改编译器或编程语言！这通常可以使它们适用于具有小堆的桌面应用程序，包括 [3A 视频游戏](https://wiki.unrealengine.com/Garbage_Collection_Overview)，其中大部分 RAM 由不需要清除的数据文件占据。 Stop-the-world（STW）标记/清除是本科计算机科学课程中最常用的 GC 算法。在做面试时我有时候会让候选人谈谈 GC，而且几乎总是，他们要么把 GC 视为一个黑盒而根本不知道它，或者认为它现在仍然使用这个非常古老的技术。 <!-- heaps/allocation rates 堆分配速率 --> 问题是简单的 STW 标记/清除伸缩性非常差。随着 cpu 核数增加、堆分配速率更大，此算法将无法正常运行。但是，有时你确实有一个小堆，并且来自上述简单 GC 的暂停时间也足够好！在这种情况下，也许您仍然希望使用这种方法将内存开销保持在较低水平。 另一方面，也许你在拥有数十个内核的机器上使用数百 GB 的堆。也许您的服务器正在进行金融市场交易或运行搜索引擎，因此低停顿时间对您来说非常重要。在这些情况下，您可能愿意使用一种算法，该算法为实现在后台以低暂停时间进行垃圾回收，会降低程序速度。 这并非简单的堆大小问题。在更高维度，你可能有大量的批处理作业（job）。由于他们是非交互式程序，暂停时间并不重要，仅关心垃圾回收总时间。在这种情况下，您最好使用一种将吞吐量最大化的算法，即所做的有用工作与用于收集的时间之比。 <!-- GC tuning --> 问题在于没有一种算法在所有方面都是完美的。语言运行时也不能知道您的程序是批处理作业还是交互式延迟敏感程序。这就是“GC tuning(性能调优)”存在的起因——这不是因为运行时工程师是愚蠢的。它反映了我们计算机科学能力的基本限制。 ## 代际假说（The Generational Hypothesis） <!-- PL 具体指什么？ --> [自 1984 年以来，人们就知道大多数分配内存“早夭”](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.4295&rep=rep1&type=pdf)，即内存分配后很快就会变成垃圾。这种现象被称为代际假说（The Generational Hypothesis），是整个 PL 工程领域中最强大的经验之一。在不同类型的编程语言和软件行业数十年的变革中，无论对于函数式语言，命令式语言，以及动态语言、静态语言，它都如此。 这个发现很有用，因为它意味着可以利用它设计 GC 算法。这些新一代 GC 在旧 STW 风格上有很多改进： * **GC 吞吐量**：他们可以更快地收集更多垃圾。 * **分配性能**：分配新内存不再需要在堆中搜索以寻找空闲时隙，因此分配实际上是免费的。 * **程序吞吐量**：分配整齐地排布在彼此相邻的空间中，从而显着提高了缓存利用率。分代收集器确实要求程序在运行时执行一些额外的工作，但从经验上看，他被提升的缓存效果所击败 * **暂停时间**：大多数（但不是全部）暂停时间变得更短。 他们还介绍了一些缺点： * **兼容性**：实现分代收集器需要能够在内存中移动内容，并在程序在某些情况下写入指针时执行额外的工作。这意味着 GC 必须与编译器紧密集成。C ++没有分代 GC 。 <!-- * remember set？ --> * **堆开销**：这些收集器通过在各种“空间”之间来回复制分配来工作。因为必须有空间可以复制到，所以这些收集器会产生一些堆开销。此外，它们需要维护各种指针映射（记住的集合），这进一步增加了开销。 * **暂停分布**：虽然许多 GC 暂停现在非常快，但仍有一些需要在整个堆上进行完整的 标记/清除。 * **调优（tuning）**：分代 GC 引入了“年轻一代”或“伊甸园空间”的概念，程序性能变得对这个空间的大小非常敏感。 * **预热时间**：为了响应调优问题，一些收集器通过观察程序在实践中如何运行来动态调整年轻代的大小，但现在暂停时间取决于程序运行的时间长短。实际上，这在基准测试之外很少有用。 然而，好处是如此巨大，基本上所有现代 GC 算法都是 **分代收集** 的。如果你（可）能负担得起，你就会想要。分代收集器增强各种其他特性，典型的现代 GC 将支持 并发，并行，压缩等所有特性。 ## Go 并发收集器 <!-- 很别扭，找不到主语 --> 由于 Go 是一种具有值类型的相对普通的命令式语言，其内存访问模式可能与 C＃ 相当，其中分代假设当然成立，因此 .NET 使用分代收集器。 事实上，Go 程序通常是 请求/响应 处理，如 HTTP 服务器，这意味着 Go 程序表现出强烈的分代收集行为，而 Go 团队正在探索未来可能使用的——称为[“面向请求的收集器”](https://docs.google.com/document/d/1gCsFxXamW8RRvOe5hECz98Ftk-tcRRJcDFANj2VwCB0/edit)的东西。[现在看来，这实际上是一个重新命名的分代 GC，具有调整任期策略功能](https://news.ycombinator.com/item?id=11969740)。这个 GC 可以在 请求/响应 处理的其他运行时中进行模拟，方法是确保年轻的一代足够大，能够容纳处理请求生成的所有垃圾。 尽管如此，Go 目前的 GC 还不是分代收集的。它只是在后台运行一个普通的古老的 标记/清除。 这样做有一个好处——你可以获得非常短的暂停时间——但几乎所有其他方面都变得更糟。难道就像这样吗？那么，从上面的基本理论我们可以看到： * **GC 吞吐量**：清除堆所需的时间与堆的大小成比例。简单来说，程序使用的内存越多，释放内存的速度就越慢，相对处理有效工作时间，计算机用于收集垃圾时间也就越多。如果您的程序根本不并行化，但是您可以无限制地继续向 GC 添加核心数，是唯一不好的地方。 * **紧凑**：由于没有压缩，程序最终会将堆碎片化。我将在下面详细讨论堆碎片。在缓存中整齐排列也不会带来收益。 * **程序吞吐量**：由于在每一轮循环中 gc 都需要做大量的工作，其将从 应用程序本身偷取 cpu 时间，并使其变慢 * **暂停分布**：任何与程序并发运行的垃圾收集器都可能遇到 Java 世界所称的并发模式故障:程序创建垃圾的速度比 GC 线程清理垃圾的速度还快。在这种情况下，运行时别无选择，只能完全停止程序，等待 GC 循环完成。因此，当 Go 声明 GC 暂停时间很短时，这种声明只适用于 GC 有足够的 CPU 时间和内存空间超过主程序（分配内存的速度快过主程序）时。另外，go 编译器不支持稳定停下线程的特性，也就是说，暂停时间的长短很大程度上取决于你的程序什么时候运行，例如：在单一线程上解码一个巨大的 base64 会使暂停时间升高。 * **堆开销**：因为通过 标记/清除 收集堆非常慢，所以需要大量空闲空间来确保不会出现“并发模式故障”。Go 默认的堆开销为 100%，它将使程序所需的内存增加一倍。 我们可以在[golang-dev 的帖子](https://groups.google.com/d/msg/golang-dev/Ab1sFeoZg_8/pv0Yg7tkAwAJ)中看到这些平衡，如下所示： > 服务 1 分配的数量超过服务 2，因此 服务 1 STW 暂停值更高。但是 STW 暂停持续时间在两种服务上都下降了一个数量级。在切换两种服务后，我们看到在 GC 中花费的 CPU 使用率增加了约 20%。 所以在这个特定的例子中，Go 在暂停时间上获得了一个数量级的下降，但代价是一个更慢的收集器。这是一个很好的平衡吗？还是暂停时间已经足够低了?海报上没有说。 但有一点，需要更多硬件才能获得更低的暂停时间不再有意义。如果您的服务器暂停时间从 10 毫秒到 1 毫秒，您的用户是否真的会注意到这一点？如果你不得不使你的机器数量加倍来实现它？ go 以吞吐量为代价来优化暂停时间。以至于它似乎愿意将程序的速度降低几乎任何程度，以获得稍微短一点的暂停时间。 ## 与 Java 相比 HotSpot JVM 有几种 GC 算法，您可以在命令行中选择。Java 没有像 Go 这样短的暂停时间，因为它们更看重其他因素。有必要对比一下，可以了解他们是怎么平衡这些因素的。 因为在程序运行时进行编译，只需重新启动程序就可以在 GC 之间切换，可以根据需要和问题编译和优化不同算法。 所有现代计算机上的默认都是吞吐量收集器。这是为批处理作业设计的，默认情况下没有任何暂停时间目标（可以在命令行上给出一个）。 <!-- 前后矛盾，前糟糕；后都是优势？ --> 人们倾向于认为，这种默认选择是 java gc 必然有些糟糕的原因： 开箱即用，Java 试图让你的应用程序尽可能快地运行，尽可能减少内存开销，但却有该死的暂停时间。 如果暂停时间对您更重要，那么您可能会切换到并发标记/清除收集器（CMS）。这是最接近 Go 的算法。但它也是分代的，这就是为什么它的暂停时间比 Go 长：年轻一代被压缩而应用暂停，因为它涉及移动对象。CMS 中有两种类型的暂停：第一种速度更快，可能持续约 25 毫秒。第二种可能更接近 20 毫秒。CMS 是自适应的:因为它是并发的，所以它必须预测什么时候开始运行(就像 Go 一样)。Go 要求您配置堆开销来优化它，而 CMS 将在运行时自我调整，以尝试并避免发模式失败。由于堆的大部分是普通的标记/清除，因此可能会出现堆碎片导致的问题和速度下降。 最新一代 Java GC 被称为“垃圾优先”（“G1”）。Java 8 中没有预置，而是在 Java 9 中。它旨在成为通用的“一刀切”算法，或者尽可能接近现在的样子。它主要是整个堆的并发，生成和压缩。它也在很大程度上是自我调整，但是因为（像所有的 GC 算法一样）它无法知道你真正想要的东西，它允许你指定你喜欢的平衡：只需告诉它你将允许它使用的最大 RAM 量和暂停时间目标（以毫秒为单位），当应用程序运行以尝试满足暂停时间目标时，它将调整其他所有内容。默认暂停时间目标大约为 100 毫秒，因此除非您指定不同的结果，否则您不应该期望看到更好的结果：G1 会偏向于应用运行得比暂停时更快。暂停并不完全一致——大多数都非常快（< 1 ms），而一些在压缩堆时会更慢（更像是 50ms）。G1 非常好。有报道称人们使用 TB 级大小的堆。它还有一些简洁的功能，比如对堆中的字符串去重。 最后，开发了一种名为 Shenandoah 的新 GC 算法。它用于 OpenJDK ，但仅能在使用 Red Hat（赞助项目）的特殊 Java 时构建，而不能 Java 9 中使用。无论堆大小如何，它都可以提供非常低的暂停时间，同时也可以进行压缩。成本是额外的堆开销和更多障碍：在应用程序仍在运行时移动对象需要指针读写，以便与 GC 交互。在这个意义上，它类似于 Azul 的“无暂停（pauseless）” GC 。 ## 结论 本文的重点不是说服您使用不同的编程语言或工具。 **你从这篇文章中可以学到的一点：垃圾收集是一个非常非常难的问题，几十年来，计算机科学家一直在研究。所以要经常质疑别人是否做出了所谓的突破。别人宣称的“突破”更有可能只是伪装下的奇怪的、不同寻常的平衡，而其他人（Java）只是出于某些原因而避免这样做，这些原因可能要到后来才会显现出来。** 但是，如果您希望以牺牲其他所有特性为代价来最小化暂停时间，那么请务必查看 Go GC。