增量垃圾回收

在我们这个时刻保持连接的数字世界里，响应性至关重要。从流畅的视频游戏到实时的金融交易，用户期望应用程序能够无中断地工作。然而，许多现代编程语言中的一个基本过程——垃圾回收（即内存的自动回收）——常常与这一需求相冲突。传统的“stop-the-world”回收器会引入令人不快的停顿，可能使应用程序完全中断，在自动化内存管理的需求与无缝性能的要求之间造成了巨大的认知鸿沟。本文旨在通过深入探讨增量垃圾回收这一优雅的解决方案来弥合这一差距。首先，我们将探讨其核心的“原理与机制”，揭示三色抽象和写屏障等概念的神秘面紗，正是这些概念使得并发回收成为可能。然后，我们将拓宽视野，审视其广泛的“应用与跨学科联系”，探索这些原理如何确保从网页浏览器到嵌入式系统，乃至网络安全等各个领域的流畅性和安全性。

想象一下，你正试图整理一个繁忙的车间。传统的垃圾回收方法是喊一声：“所有人不许动！”，然后开始一丝不苟地分类所有工具和废料，决定哪些有用，哪些是垃圾。这就是“stop-the-world”（STW）模型。它很彻底，也易于理解，但它会让所有生产性工作都陷入停顿。对于一个现代应用程序，如高频交易平台、流畅的视频游戏，甚至只是一个响应迅速的用户界面来说，这些暂停是不可接受的。世界根本不会为我们停下来。

所以，我们必须更聪明一些。我们不能停止世界，而是必须学会在工人们旁边进行清理，将我们的整理工作与他们的任务交错进行。这就是​​增量垃圾回收​​的核心哲学：将庞大的清理任务分解成微小的、可处理的片段，每个片段只会导致微不足道的、常常难以察觉的暂停。但是，当工人们不断地移动物品时，我们怎么可能追踪什么是什么呢？答案在于一个极其简单而强大的心智模型：三色抽象。

让我们把计算机内存中的每个对象都想象成一个巨大、相互连接的网络中的一个节点。应用程序持有少数几个“根”对象——比如全局变量或当前运行代码的局部变量——其他所有对象都是通过追踪这些根的指针来访问的。为了进行清理，我们可以把自己想象成拥有三种颜色调色板的画家：

• ​​白色​​：这些是我们尚未访问过的对象。在被证明存活之前，它们被假定为垃圾。在一个回收周期开始时，除了根对象，一切都是白色的。
• ​​灰色​​：这些是我们已经发现但尚未处理完毕的对象。它们是我们的“待办事项”列表，是我们探索的前沿。它们肯定不是垃圾，但我们仍需要检查它们所指向的东西。
• ​​黑色​​：这些是我们已经完全处理过的对象。我们访问了它们，并且也访问了它们所指向的一切。它们是可验证的存活对象。

回收过程变成了一场优雅的着色游戏。我们首先将根对象涂成​​灰色​​。然后，我们重复一个简单的过程：从我们的待办列表中取出一个​​灰色​​对象，扫描它的所有指针，对于它指向的每一个​​白色​​对象，将其涂成​​灰色​​并添加到我们的列表中。一旦我们扫描完所选对象的所有指针，我们就完成了对它的处理，并将其涂成​​黑色​​。

我们继续这个过程，直到我们的灰色待办列表为空。那一刻，一个深刻的真理被揭示：任何仍然是​​白色​​的对象都是不可达的。它是垃圾，我们可以安全地将其清除以回收其内存。总工作量仅仅与我们需要在存活对象网络中追踪的连接数量成正比。

如果世界静止不动，这个三色之舞是完全合理的。但我们的目标是与应用程序——即“mutator”（突变器），因其会改变对象图而得名——并发工作。而麻烦也由此开始。

想象一下，你刚刚扫描完一个对象，比如你的 userProfile，并将其涂成了​​黑色​​。与此同时，应用程序正在运行。它决定将一个新创建的​​白色​​对象——我们称之为 lastLoginAttempt——赋值给 userProfile 内的一个字段。同时，它移除了可能存在于某个​​灰色​​对象中对 lastLogin "LoginAttempt" 的唯一其他引用。

一场灾难发生了。现在，我们有了一个从​​黑色​​对象（userProfile）指向​​白色​​对象（lastLoginAttempt）的指针。由于我们的规则是从不重新访问黑色对象，我们的回收器将永远不会发现这个新指针。lastLoginAttempt 对象将保持白色，在周期结束时，它将被错误地当作垃圾清除掉，尽管它实际上是存活且可达的。这几乎肯定会导致应用程序崩溃。

为了防止这场灾难，我们必须强制执行一条单一的、不可侵犯的规则：​​三色不变性​​。它规定，在任何时候，都不允许存在从黑色对象到白色对象的指针。这个不变性是增量垃圾回收正确性的基石。

我们如何在一个一心要破坏规则的应用程序上强制执行规则呢？我们不能依赖程序员小心谨慎。相反，我们必须建立一个自动的、无法逃脱的藩篱。这个藩篱被称为​​写屏障​​（write barrier）：一段由编译器在程序中每次指针写入操作前插入的微小代码片段，它会检查这次写入是否即将违反我们的不变性，并立即采取纠正措施。

让我们通过一个经典的编程任务——反转链表——来看看它的实际作用。标准算法通过一个涉及 prev、curr 和 next 节点的精妙舞蹈来移动指针。当 curr.next 指针被更新时，对象图的结构发生了变化。现在，想象一下我们的垃圾回收器已经运行了一段时间，并将列表的前几个节点标记为​​黑色​​。当反转算法到达其中一个黑色节点并重写其 next 指针时，写屏障立刻启动。它检测到一个​​黑色​​对象上的指针正在被改变。为了安全起见，它立即将该节点重新着色为​​灰色​​，并将其放回回收器的待办列表中。通过强制重新扫描被修改的节点，我们保证它建立的任何新连接都将被正确探索，从而维护了三色不变性。

这个机制是我们的保障。但屏障究竟应该做什么呢？这个问题引出了两种根本不同的保留哲学。

核心问题是 $B \to W$ 指针的创建。我们可以从指针的目标（白色对象）或源头（黑色对象）的角度来解决这个问题。

哲学 1：增量更新

这种方法，通常被称为​​Dijkstra式插入屏障​​，关注的是正在创建的新指针。当突变器试图将一个指向白色对象 $W$ 的指针存入黑色对象 $B$ 的字段时，写屏障会介入并说：“停！你不能这样做。”它通过将目标对象 $W$ 染成灰色来立即“修复”这个问题。被禁止的 $B \to W$ 边变成了允许的 $B \to G$ 边。不变性得以维持。

这看起来简单直接。然而，它有一个被称为​​终止问题​​的微妙但严重的缺陷。突变器可以自由地继续创建指向白色对象的新指针，每次这样做，它都会为回收器创造更多的工作。如果突变器特别“激进”，它创造工作的速度可能比回收器处理的速度还快。回收器的待办列表可能会无限增长，标记阶段将永远无法自行完成。为了保证完成，这样的系统通常需要退回到一个最终的“stop-the-world”阶段来清理剩余的工作，这在某种程度上违背了增量回收的初衷。

哲学 2：初始快照（SATB）

第二种哲学采用了一种截然不同却非常优雅的方法。它不担心新指针的创建，而是担心旧指针被销毁。其目标是保护在回收周期开始那一刻所有可达对象的“快照”的完整性。

SATB写屏障，通常被称为​​删除屏障​​，在指针字段被覆盖之前触发。它会查看被丢弃的值——旧的对象指针——然后说：“等等，在你扔掉它之前，我需要确保回收器已经看到了它。”如果它所指向的旧对象是原始快照的一部分，屏障就会将该对象标记为灰色，确保它以及从它可达的所有东西都将被访问。

这种方法的优雅之处是深远的。突变器再也无法为回收器创造无限量的新工作。它通过触发屏障为回收器产生的任何工作，只是揭示了在周期开始时已经存在的对象图的一部分。总工作量是有限的，并受限于那个初始快照。这意味着并发标记阶段​​保证能够终止​​，而无需第二次 STW 暂停。正是这个保证使得 SATB 风格的回收器对于需要硬实时暂停时间限制的系统如此具有吸引力。

当然，编译器可以更聪明。它可以使用复杂的逃逸分析等技术来证明某些写入，例如初始化一个回收器尚未见过的新对象，不可能违反不变性。在这些情况下，可以安全地省略写屏障，从而减少开销。

拥有正确的机制只是成功的一半。另一半是调度：回收器应该做多少工作，以及何时做？回收器与突变器 sürekli进行着一场竞赛，面临着两种不同的压力。

首先是​​截止时间压力​​。在一个周期开始时，有固定数量的空闲内存。回收器必须在突变器分配完所有这些空闲空间之前完成其整个标记阶段。耗尽时间就是空闲内存量除以突aproximador的分配率。

其次是​​跟进压力​​。随着突变器的运行，它会分配新对象，其中一部分将存活下来，成为长期存活集合的一部分。平均而言，回收器标记这些新生幸存对象的速度必须至少与突变器创建它们的速度一样快。

为了在遵守最大暂停时间 $T_{max}$ 的同时满足这些压力，回收器必须在每个小增量中执行精确计算的工作量。这项工作必须根据最坏情况下的执行时间来预算，因为使用平均值可能导致意想不到的长暂停。回收器为突变器分配的每字节内存必须执行的最小标记工作量可以用一个简单而优美的公式来表示。如果 $\rho$ 是堆中被存活数据占据的比例，那么每分配一字节内存，回收器至少需要执行 $c = \frac{\rho}{1-\rho}$ 字节的标记工作。这表明，你的堆越“满”，回收器就必须越努力地工作才能跟上。

增量回收使我们摆脱了长时间的、干扰性的暂停，但这种自由是有代价的。这些系统是工程上的奇迹，但它们必须遵守权衡的基本法则。

优雅的 SATB 方法的一个显著代价是​​浮动垃圾​​。因为这种方法保证保留周期开始时所有存活的对象，任何在标记阶段期间死亡的对象都不能被回收。它会“浮动”着，无用地占用内存，直到下一个周期完成。这种浮动垃圾的数量与标记周期所需的时间以及突变器丢弃对象的频率成正比。这种额外的内存压力可能会迫使回收器更频繁地运行，从而降低应用程序的整体吞吐量。

另一个挑战是​​碎片化​​。就像我们将标记阶段增量化一样，我们也可以将清理阶段增量化。然而，如果我们分块清理堆，尚未被清理的块中的空闲空间仍然无法使用。这与每个块内留下的小的、无法分配的间隙相结合，导致了碎片化。然而，一个简单的模型再次揭示了一种优美的平衡：存在一个最佳的清理块大小，它与总堆大小的平方根成正比，能够最小化这种碎片化。

从一个简单的“stop-the-world”清理器到一个复杂的、并发的、增量工作的系统的演进，是计算机科学之美的一个完美例子。这是一个识别根本冲突——清理的需求与工作的需求——并用优雅的抽象、精心执行的不变性，以及对正确性、响应性和整体效率之间微妙权衡的深刻理解来解决它的故事。

在深入了解了增量垃圾回收的内部工作原理，探索了它对三色不变性和写屏障精妙配合的依赖之后，我们可能会倾向于将其视为一项巧妙但小众的计算机工程技术，一个为语言设计者解决问题的方案。但这样做就只见树木，不见森林了。因为在科学中，最美的思想往往是影响最深远的，它们的回声会出现在最意想不到的地方。增量回收的原理不仅关乎内存管理，它们关乎在动态世界中管理复杂性、时间和资源。它们是我们在一些最复杂的系统中实现响应性、可靠性甚至安全性的关键。

现在，让我们退后一步，欣赏一下这幅全景。这个想法将我们引向何方？

从本质上讲，增量垃圾回收是与用户达成的一个契约。它用持续的、低强度的后台活动，换掉了突兀的、不可预测的“stop-the-world”暂停。完成的总工作量稍多一些，但它被如此均匀地分散在时间中，以至于变得难以察觉。这个简单的权衡是我们认为理所当然的每一个流畅、响应迅速的数字体验的基石。

以一个现代视频游戏为例。引擎在与时间赛跑，努力在不到 $16.67$ 毫秒内渲染每一帧，以保持流畅的每秒60帧。一次突然的、20毫秒的垃圾回收暂停，不仅仅是一个小小的中断；它是一次掉帧，一个可见的“卡顿”，打破了沉浸感。然而，一个增量回收器可以完美地融入这场竞赛。回收器的工作被分解成微小的片段，也许一两毫秒，在每帧结束时，主要游戏逻辑和渲染完成后剩下的小段空闲时间内执行。通过仔细预算这段时间，系统可以保证在不影响帧率目标的情况下逐步完成其总GC工作量，从而确保完美的流畅体验。

同样的原则也是现代网页浏览器的命脉。当你流畅地滚动一个复杂的网页或观看流畅的动画时，你正在见证一个错综复杂的任务流水线：HTML解析、JavaScript执行、样式与布局计算，最后是将像素绘制到屏幕上。在一个复杂的浏览器架构中，这些任务在不同的线程上并行运行以加快速度。但如果修改页面内容的线程被一个“stop-the-world”GC冻结了会怎么样？流水线会嘎然而止，下一帧被延迟，用户就会看到“卡顿”（jank）。通过采用增量回收器，修改页面的线程永远不会被真正冻结。它们在每一帧中将一小部分时间让给回收器，从而使整个渲染流水线能够不间断地流动，可靠地达到关键的60 FPS目标。

对响应性的追求甚至延伸到了编程语言本身的设计中。具有*惰性求值*特性的语言会将计算推迟到其结果绝对需要时才进行。这可能导致在第一次请求某个值时触发一连串的计算。如果一个长的GC暂停恰好在那个时刻发生，程序就会变得没有响应。增量GC驯服了这种不可预测性，确保任何单一操作的最大延迟——比如强制一个“thunk”来获取其值——即使在回收周期活跃时，也能保持有界且很小。

在交互式系统中，错过一个截止时间会让人烦恼。但在一个实时系统——一个心脏起搏器、一个汽车制动控制器、一个工厂机器人——中，这可能是一场灾难。在这里，正确性不仅在于得到正确的答案，还在于在正确的时间得到它。对于这些系统，“可预测性”是最高的德性，而传统垃圾回收器的长时间、无限制的暂停是绝对不能容忍的。

这正是增量GC真正大放异彩的地方，它从一个追求“流畅性”的工具转变为一个保障“安全性”的工具。我们可以将增量回收器的工作数学地建模为系统中另一个高优先级的周期性任务。使用一种称为响应时间分析（Response Time Analysis）的技术，我们可以计算出GC将对所有其他任务施加的最坏情况干扰。这使得工程师能够确定可以周期性执行的最大GC片段大小，同时仍然能够以数学上的确定性证明系统中的每个关键任务都将满足其硬性截止时间。增量方法将内存管理从一个充满危险不可预测性的源头，转变为一个行为良好、可分析的关键任务系统组件。

嵌入式世界的约束不仅限于时间。在手机或物联网（IoT）传感器上，能量和内存是宝贵而有限的资源。每个CPU周期都会消耗一小口电池电量。写屏障，我们增量回收器不可或缺的工具，并非没有成本；它拦截的每一次指针写入都会增加时间和能量上的少量开销。编译器设计者不懈地发明巧妙的优化，利用静态分析来证明某些写入不可能违反三色不变性，从而安全地消除屏ip障，节省宝贵的能量。嵌入式设备的系统设计者必须进行微妙的权衡，选择一个足够小的GC片段大小，以适应每个片段的时间和能量预算，但又要足够大，以确保回收器取得足够的进展，从而跑赢应用程序的内存分配率，避免内存耗尽。增量GC提供了所需的旋钮和刻度盘，以驾驭时间、能量和内存之间复杂的多维权衡。

现代编程语言的运行时是一个由复杂、相互作用的部分组成的交响乐：内存管理器、编译器和虚拟机。增量GC不是一个独奏者，而是乐团中的重要一员，其实现揭示了美妙的协作。

考虑一个需要调用“原生”代码的运行时，比如用C或C++编写的库。原生代码对我们精心管理的堆一无所知；它处理的是原始内存地址。如果我们的GC决定为了紧凑化而将一个对象移动到新位置，原生代码持有的任何原始指针都将变成悬空指针，立即导致灾难。为了防止这种情况，运行时必须“钉住”（pin）该对象，禁止GC移动它。增量回收器必须意识到这一点，认识到这些被钉住的对象暂时是禁止移动的，并相应地调整其“待完成工作”的概念。

与即时（Just-In-Time, JIT）编译器的相互作用甚至更为深刻。这些编译器动态生成高度优化的机器码。有时，为了达到最高速度，JIT编译器会将指向对象的原始指针直接嵌入到可执行的机器码本身。这对一个移动式的增量GC提出了一个可怕的难题。当GC重定位一个对象时，它如何找到并更新隐藏在编译后代码中的这些指针？两种同样优雅的解决方案应运而生。一种是将编译后的代码视为一种特殊的“根”，教会GC如何在对象移动后扫描它并“修补”嵌入的指针。另一种是使用一层间接：代码嵌入一个指向稳定的“句柄”的指针，当对象移动时，GC只需要更新这个句柄内的指针即可。两种策略都解决了问题，揭示了实现高性能托管语言所需深刻而复杂的协同设计。

在这里，我们迈出最后一步，看到这个核心思想真正抽象的美。三色标记算法本质上是一种遍历图以找到从一个根集合可达的所有节点的通用方法，而图本身正在被修改。内存管理只是这个强大概念的一个应用。

想象一个软件构建系统，比如用来编译大型应用程序的系统。任务（编译文件、链接库）形成了一个依赖图。当一个源文件改变时，它变成了一个“根”，我们必须找到依赖图中从它可达的所有任务——这些是需要重新构建的任务。这正是一个图遍历问题。现在，如果依赖关系是在构建过程中动态发现的呢？一条新的边被添加到了图中。这与程序的突变器在对象之间创建新指针完全相同！为确保我们不会漏掉一个需要重新构建的任务，构建系统可以实现完全相同的三色算法。一个“黑色”任务是已完全扫描完依赖关系的任务。一个“白色”任务是尚未发现的任务。从黑色任务到白色任务的边插入威胁到“丢失”白色任务。解决方案是什么？一个“写屏障”，它检测到这一点并将白色任务染成“灰色”，将其添加到工作列表中。垃圾回收的抽象算法为一个健壮的、增量的构建系统提供了可证明正确的蓝图。

也许最令人惊讶的联系在于网络安全领域。写屏障，这个为帮助垃圾回收器而发明的机制，实际上是一个完美的监视工具。它是在程序执行的每一次指针写入操作时都会执行的钩子。我们能否将这个钩子用于着色对象之外的其他事情？

确实可以。安全研究人员意识到这个工具可以用于实时入侵检测。一种常见的攻击技术称为“指针喷射”（pointer spraying），它涉及将指向恶意载荷的指针迅速写入堆上的大量位置，希望能获得程序的控制权。通过增强写屏ר，我们能做的不仅仅是更新一个记忆集。在每次写入时，我们可以将目标对象的地址输入到一个像Count-Min Sketch这样的概率性数据结构中。这种结构可以用接近恒定的时间和极小的内存占用，维护对每个对象的写入次数的近似计数。如果任何对象的计数值突然飙升，超过一个阈值，系统就可以实时发出警报，在攻击发生时就检测到它。卑微的写屏障，源于内存管理的需求，转变成了一个沉默的哨兵，守护着系统免受恶意行为的侵害 [@problemid:3236444]。

从你手机上的流畅滚动到汽车控制系统的安全，从编译器的优雅到网络安全的前沿，增量垃圾回收的原理回响不绝。它证明了计算机科学思想的深刻统一性，即一个针对某个问题的优美解决方案，可以解开我们尚未想到去问的十几个其他问题的答案。