玻尔百科在计算世界中，内存管理是一项基础而持久的挑战。程序在运行时会创建和丢弃大量的数据对象，如果未能清理过时的对象，将导致内存泄漏并最终导致系统故障。自动垃圾回收 (GC) 是针对此问题的优雅解决方案，而标记-清除算法是其最古老、最基础的技术之一。尽管它通常被介绍为一种整理计算机内存的简单工具，但其核心哲学——识别要保留什么，而非要丢弃什么——是一项影响深远的深刻原则。
本文不仅将标记-清除算法作为一种技术机制来探讨，更将其视为一种思考相互关联系统的强大方式。它旨在弥合将 GC 视为小众实现细节与将其理解为一种关于依赖和存活性的通用模式之间的差距。读完本文，您将对这一优雅的算法及其更广泛的意义有全面的理解。“原理与机制”一节将算法解构为其核心组成部分，解释了标记和清除阶段、优美的三色抽象以及所涉及的现实世界中的权衡。随后，“应用与跨学科联系”一节揭示了同样的可达性逻辑如何无处不在，从优化软件、管理分布式系统，到模拟生物生态系统和保护区块链安全。
为了理解标记-清除算法，我们不从代码或复杂的图表开始，而是从一个简单的类比入手。想象一个巨大而杂乱的工作室。在中央工作台——你主要的接触点——上，放着几件必备工具。从这些工具上，延伸出各种长度和颜色的绳子，连接到其他工具，而这些工具又通过绳子连接到更多的工具。周围散落着无数其他物品，有些是被遗忘项目的一部分，有些只是碎片。你的任务是清理，扔掉所有无用的东西。但你如何知道什么是无用的呢？你不可能有一份列出所有无用碎片的清单。
其洞见在于：与其识别垃圾，不如识别什么不是垃圾。你声明，任何从工作台出发，沿着绳子可以到达的工具都是“存活的”，必须保留。其他所有东西，根据定义，都是垃圾。这个可达性 (reachability) 原理，就是标记-清除算法的哲学核心。
在计算机程序中，工作室就是内存，工具是“对象”，工作台是一组“根”（直接、活跃的引用，如全局变量或当前运行函数中的变量），而绳子是连接对象之间的“指针”。我们清理的第一阶段，即标记阶段 (mark phase)，是一次系统性的探索，以找到每一个存活的对象。
这个过程是一次经典的图遍历。我们首先创建一个“待办事项”列表，即我们的工作列表 (worklist)，并将所有根对象放入其中。然后，我们进入一个简单的循环：
当列表为空时，我们的旅程就完成了。现在，从根可达的每个对象都有一个标记。这次探索可以有不同的方式。如果我们的待办事项列表是一个“后进先出” (LIFO) 的栈，我们的旅程将是一次深度探索，沿着一条指针链走到尽头再回溯；这是一种深度优先搜索 (DFS)。如果它是一个“先进先出” (FIFO) 的队列，我们将逐层探索，就像石头投入池塘中扩散开的涟漪；这是一种广度优先搜索 (BFS)。
但如果工作室里的绳子缠结在一起怎么办？如果从对象 A 的指针指向 B，而 B 又指回 A 怎么办？这就形成了一个环 (cycle)。一个天真的探索者可能会陷入无限循环，永远在 A 和 B 之间来回。这里就体现了“标记”的简单天才之处：当我们从待办事项列表中取出一个对象时，我们首先检查它是否已经被标记。如果是，我们就简单地忽略它，继续前进。我们已经来过这里了。这一个检查确保我们对每个存活对象只访问一次，并保证算法能够正确终止，无论对象网络多么复杂或存在循环。
这个标记过程可以通过三色抽象 (tricolor abstraction) 以一种更强大、更优美的方式来可视化。想象一下，我们不用“已标记”和“未标记”，而是用三种颜色的颜料来涂抹我们的对象：
现在，标记阶段变成了一个优雅地为对象图上色的过程。它始于所有对象都是白色。
这个抽象不仅仅是为了美观；它揭示了算法背后一个深刻的、根本性的真理，一个至关重要的循环不变量 (loop invariant)：黑色对象永远不会直接指向白色对象。想一想：要让一个对象变成黑色，我们必须先检查它所有的指针。如果其中任何指针指向一个白色对象，那个白色对象就会被涂成灰色。因此，当一个对象变为黑色时，它只能指向其他灰色或黑色的对象。这个简单而牢不可破的规则是算法正确性的基石，而且，正如我们将看到的，是将它扩展到更复杂场景的关键。
一旦标记完成——即灰色集合为空时——第二阶段开始：清除阶段 (sweep phase)。这部分简单粗暴。垃圾回收器对整个内存进行一次线性扫描。它逐个检查每个对象：
在理想化的工作室里，故事到此结束。但在现实世界的计算机中，简单的标记-清除算法引入了其自身一系列有趣而复杂的挑战。
清除阶段会在死对象曾经占据的地方留下内存空洞。虽然回收器可以尝试合并 (coalesce) 相邻的空闲洞以形成更大的空闲块，但内存景观常常变得像瑞士奶酪一样。我们可能有很多总的空闲空间，但如果它们都以微小的、不连续的块形式存在，我们就无法分配一个新的大对象。这个问题被称为外部碎片 (external fragmentation)。像固定对象 (pinned objects) 这样的东西会加剧这个问题——这些是不能被移动的特殊对象，也许因为它们与硬件设备绑定以进行 I/O 操作。一个单独的、小的固定对象就像一个楔子，可以阻止两个大的空闲块合并，从而极大地增加碎片化并浪费内存。
这个缺点是其他类型垃圾回收器的主要动因。例如，复制回收器 (copying collector) 通过将所有存活对象移动到一个新的、紧凑的内存区域来完全避免碎片化。然而，这是有代价的。复制回收器的成本与它必须复制的存活对象的数量成正比，而标记-清除的成本与整个堆的大小（对于清除阶段）和存活对象的数量（对于标记阶段）成正比。权衡变得清晰：如果你的大多数对象都是存活的，标记-清除可能比代价高昂的大规模迁移更便宜。如果大多数对象是死的，一个只需要移动少数幸存者的复制回收器会快得多。在内存管理中没有免费的午餐。
即使在标记-清除算法内部，细微的选择也会产生重大的后果。考虑标记阶段的遍历顺序。BFS 遍历（使用 FIFO 队列）通常会在内存中跳跃，访问一个区域的对象，然后是另一个区域，然后再回来。这种随机性对现代 CPU 缓存可能是灾难性的，因为缓存依赖于可预测的、局部化的内存访问。每次跳跃都可能导致缓存未命中 (cache miss)，迫使从主存进行缓慢的读取。相比之下，DFS 遍历（使用 LIFO 栈）倾向于沿着指针链进行，这些指针链通常对应于差不多同一时间创建且在内存中位置相近的对象。这改善了空间局部性 (spatial locality)，并可以带来显著更好的缓存性能和更快的回收周期。这展示了一个优美的原则：高性能算法不仅仅是抽象思想；它们与所运行硬件的物理现实紧密相连。
也许最大的挑战是：你如何在主程序——即“修改器 (mutator)”——仍在运行并改变指针的同时收集垃圾？为一个完整的垃圾回收周期而暂停整个世界 (stopping the world) 可能会在应用程序中引起可感知的停顿，这对于流畅的用户界面或实时系统来说是不可接受的。
这就是三色不变量的力量真正闪耀的地方。想象一下，回收器刚刚扫描完对象 X，将其染成黑色。就在那一刻，修改器偷偷地在 X 和一个白色对象 Y 之间创建了一个新指针。回收器认为它对 X 的工作已经完成，将永远不会看到这个新指针。Y 将保持白色，并被错误地清除掉，尽管它现在是存活的。这就是臭名昭著的“丢失对象”问题。
解决方案是写屏障 (write barrier)。它是一个由编译器插入的微小检查，每次修改器写入指针时都会运行。这个屏障的工作就是维护三色不变量。如果它检测到一个将创建被禁止的黑到白指针的写入操作，它会立即采取行动。一个常见的策略是简单地将目标白色对象 Y 涂成灰色。这个动作提醒回收器：“你的工作还没完！这里有一个新的前沿需要探索。”灰色集合不再为空，标记继续进行，Y 就被保存下来了。这个机制必须是健壮的；一个未能捕获写入操作的不完美写屏障，结合回收器端的读屏障，通常不足以防止错误，因为回收器可能没有任何理由去重新读取被修改的字段。
从一个寻找可达对象的简单想法出发，我们构建了一个不仅对复杂数据结构具有鲁棒性，而且可以通过优雅的三色抽象进行调整，以解决在并发世界中管理内存这一深刻挑战的框架。从一个简单的清理计划到一个复杂的并发算法的这段旅程，揭示了计算机科学核心原则内在的美和统一性。
在理解了标记-清除的工作原理之后，你可能会想把它当作管理计算机内存的一个巧妙技巧而束之高阁。但这样做就只见树木，不见森林了。标记-清除算法不仅仅是整理程序内存的工具；它是一个深刻而普适原则的体现，一个自然界和人类系统反复发现的模式。它是通过可达性判断存活性的基本法则。当我们学会处处看到这种模式时，真正的魔力才开始显现。
其核心思想很简单：如果你有一个由相互关联的事物（对象、数据、物品、物种）组成的系统，并且其中一些事物被定义为本质上是重要的（即根），那么从这些根出发，通过连接可以到达的任何东西也都是重要的。其他所有东西，在某种意义上，都与系统的目的脱节。它们是“垃圾”。让我们踏上一段旅程，看看这个优雅的思想如何在各种令人惊讶的领域中回响。
我们可以从自家后院——软件世界本身——开始我们的旅程，但眼光要超越简单的内存管理。
想象你是一个编译器，将人类编写的代码翻译成机器的本地语言。你的工作是要高效。你看到一个计算，其结果从未被用来产生程序的最终输出。你应该浪费时间去计算它吗？当然不！但你如何知道哪些计算是无用的？你可以从程序的必要输出（如打印到屏幕或写入文件）开始反向工作。这些输出就是你的根。任何作为根计算的“原料”的数据都是“存活的”。任何作为那个原料的原料的数据也是存活的。通过反向追踪这些依赖关系，你正在执行一次存活性分析。这不过是伪装的标记-清除，其中“清除”阶段只是删除“死代码”——那些未被标记为存活的指令。这种优化是现代高效软件如何创建的基础。
让我们从单个程序放大到整个软件项目。一个现代应用程序由成百上千个源文件、库和其他资产构建而成。当开发者更改单个源文件时，哪些其他文件需要重新编译？构建系统通过将项目视为一个依赖图来解决这个问题。最终的可执行文件是根。它们“依赖于”某些目标文件，而这些目标文件又“依赖于”源文件。当一个源文件发生变化时，构建系统可以追踪依赖关系，以查看哪些构件现在已经过时，需要重新构建。反过来，同一个图也可以用于清理。如果一个功能被移除，曾经为其所需的源文件可能从任何最终的可执行文件都变得不可达。一个“垃圾回收式”的构建系统可以识别这些孤立的文件并建议删除它们，从而保持项目的整洁和可管理性。
这一原则的规模是巨大的。考虑一个像 HDFS 所建模的分布式文件系统，它可能在数千台机器上存储 EB 级的数据。数据以块的形式存储，而文件本质上是按顺序读取哪些块的列表。“存活”的文件是根。任何不属于任何文件列表的数据块都是孤立的——它是机器中的一个幽灵，消耗着宝贵的空间。一个在整个集群上运行的标记-清除过程可以识别这些未被引用的块并回收它们的存储空间。我们甚至可以添加更复杂的规则，例如确保每个“存活”块都有一定数量的副本（复制因子）以确保安全，并使用清除阶段来删除任何多余的副本。
代码不是静态的；它在不断演化。标记-清除模式对于管理这种演化非常有价值。许多大型软件项目使用“功能标志 (feature flags)”来开启或关闭功能，而无需重新部署代码。一个标志可能依赖于其他标志。根是当前代码库中被主动检查的标志。随着时间的推移，当功能发布、旧代码被删除后，一些标志可能会变得“不可达”——不再在任何地方被引用。通过将标志建模为一个图，自动化系统可以运行一个垃圾回收器来识别这些过时的标志，并创建一个请求来移除它们，防止系统累积技术债。
这种动态性带来了引人入胜的挑战。考虑一个现代网站。它的外观由数千条 CSS 规则控制。页面上“存活”的 DOM 元素是根，它们“指向”为它们设置样式的 CSS 规则。我们可以对页面的快照运行标记-清除分析，以找到没有为任何元素设置样式的 CSS 规则，这些规则因此看起来是“垃圾”。但如果 JavaScript 响应用户的点击，向一个元素添加了一个类，使得一个之前“死”的 CSS 规则突然变得“存活”了呢？这揭示了一个深刻的局限性：在某个时间点的静态分析无法完美预测一个动态系统的未来行为。在这样的环境中，任何对未使用代码的“垃圾回收”都必须小心进行，否则就有可能破坏未来的交互。理解这一点是构建健壮分析工具的关键。
有时，挑战不在于分析一个现代系统，而在于改造一个旧系统。像 C++ 这样的语言没有内置的垃圾回收。程序员必须手动管理内存，一个常见的错误是“内存泄漏”，即内存被分配但从未释放，变得不可达。我们如何构建一个泄漏检测器呢？我们可以保守地应用标记-清除原则。我们可以暂停程序并扫描所有内存——栈、全局变量。任何看起来像指向我们已分配内存块的指针都被视为一个引用。然后我们标记所有可达的块，并将任何未标记的块报告为潜在的泄漏。这种“保守回收 (conservative collection)”可能无法识别某些垃圾（一个整数可能偶然与一个内存地址具有相同的位模式），但它保证没有假阳性——它永远不会将一个真正存活的对象报告为泄漏。这是一个绝佳的例子，展示了如何通过工程上的权衡，将 GC 的强大功能引入到那些并非为此设计的系统中。
标记-清除原则的真正美妙之处在于，它根本不关乎计算机。它关乎依赖。
想象一个全球供应链。客户订单是根——它们是所有需求的来源。零售店对一个产品的订单使得该库存“存活”。为了补充库存，零售商向分销中心下订单，使该中心的库存存活。分销中心再向工厂订购。我们有了一个依赖图。现在，假设发生了中断，或者一个订单被取消了。仓库中某个库存池如果不再处于任何能够满足客户订单的可行路径上，它就成了“孤儿”。这是没有目的而被占用的资本。通过应用标记-清除逻辑，供应链经理可以识别这些不可达的库存，并决定如何收回其价值。
这个类比甚至可以扩展到我们所知的最宏大的系统：生命之网。考虑一个生态系统的食物网。初级生产者——从太阳获取能量的植物和藻类——是根。能量从猎物到捕食者的流动构成了图的有向边。任何不属于追溯到初级生产者的食物链一部分的物种，在某种意义上是不可存续的。我们可以用这个模型来提出更深层次的问题。如果我们移除一个节点会发生什么？如果移除一个物种只导致其自身灭绝，影响是最小的。但如果它的移除导致依赖于它的其他物种也变得不可达并灭绝，我们就看到了一个营养级联 (trophic cascade)。标记-清除逻辑使我们能够识别这些关键的“关键物种 (keystone species)”，它们的移除会导致“存活”物种的集合急剧缩小。
最后，让我们看看计算机科学最现代、最抽象的创造之一：像比特币 (Bitcoin) 这样的区块链。系统必须追踪所有“未花费的交易输出” (UTXOs)，它们就像数字硬币。这些是存活的对象。当一个硬币被花费时，它就变得“死亡”。一个天真的方法是运行一个简单的标记-清除，其中根集就是当前的 UTXO。但区块链很奇怪；它们可能发生“重组 (reorganizations)”，即最后几个区块被替换掉。一个被认为是最终的交易可能会从历史中被抹去。如果我们已经垃圾回收了它所花费的硬币记录，我们就无法正确地恢复状态！解决方案是重新定义我们的根集。根不仅仅是当前的 UTXO，还包括在过去 D 个区块中花费的所有硬币，其中 D 是重组的最大深度。这确保了我们总能安全地回滚状态。这是一个强有力的教训：标记-清除模式是普适的，但其正确应用需要对“根”的含义有深刻的、特定领域的理解。
从清理代码到管理全球物流，从检测内存泄漏到模拟生态系统，模式都是相同的。识别根——目的的源头。追踪连接。并理解任何未被标记的东西都与那个目的脱节了。这不仅仅是一种算法；它是一种看待系统相互关联性的方式，也是一个管理其复杂性的强大而优雅的工具。