1959 年，约翰·麦卡锡（John McCarthy）在为 Lisp 实现"cons cell"（基本数据结构）时，遇到了一个根本问题：程序分配的内存单元，用完了怎么处理？
让程序员手动追踪并释放每一个不再使用的内存单元，对于 Lisp 这种动态语言来说几乎不可能。麦卡锡的解决方案是：让运行时自动识别并回收不再使用的内存。他发明了垃圾回收（Garbage Collection，GC）。
这个决定影响了此后七十年的编程语言设计。
破除误解：GC 不只是"自动 free()"
C 程序员的内存管理是手动的：malloc() 分配，free() 释放。垃圾回收表面上看是"自动 free()"——但两者有根本区别。
手动内存管理的两类经典错误：
悬空指针（Dangling Pointer）：释放内存后，仍有指针指向已释放的区域，继续使用可能读取垃圾数据或引起崩溃。
内存泄漏（Memory Leak）：内存用完了但忘记释放，随着时间推移，程序消耗的内存不断增加，最终耗尽。
垃圾回收不只是"告诉运行时可以释放内存"，而是自动判断哪些内存不再可达（reachable），不需要程序员显式告知。这从根本上消除了上述两类错误。
代价是：垃圾回收需要运行时的持续介入，带来了性能开销和停顿。
破除误解：GC 不等于"不会内存泄漏"
很多人以为用了 GC 就不可能内存泄漏。这只对了一半。
研究者把内存泄漏分成两类。物理泄漏（Physical Leak）：指向一块内存的最后一个指针丢了，但内存没被释放——这就是 C/C++ 里忘记 free() 的经典泄漏。GC 确实根除了它，因为不可达的内存一定会被回收。
逻辑泄漏（Logical Leak）：内存仍被某个指针引用着，所以对 GC 来说它"可达、活着"，但程序其实再也不会用到它。GC 对逻辑泄漏无能为力——它只判断可达性，不判断"你是否真的还需要"。
常见的逻辑泄漏来源：不断增长却从不清理的缓存（cache）、注册了却忘记注销的事件监听器（listener）、把对象塞进 static 全局集合后再不取出、线程池里残留的 ThreadLocal。这些引用都挂在某个根可达的对象树上，GC 永远不会动它们，内存就这样悄悄涨上去。
换句话说，GC 把"忘记释放"的问题，换成了"忘记解除引用"的问题。
引用计数
引用计数（Reference Counting） 是最直觉的垃圾回收方式：每个对象维护一个计数器，记录当前有多少指针指向它。每次创建指针，计数器加一；指针消亡（变量离开作用域、被重新赋值），计数器减一。计数器降为零时，立即释放对象。
Python 和 Swift 的主要内存管理机制是引用计数（Python 还有辅助的 GC 处理循环引用）。
优点： - 内存回收即时，对象一旦不再被使用，立刻释放 - 回收开销分散到整个程序运行期间，没有停顿峰值 - 实现简单，可以与非 GC 代码互操作
缺点： - 循环引用（Circular Reference）：A 指向 B，B 指向 A，两者的引用计数都是 1，但没有外部引用，两者应该被回收但永远不会——引用计数无法处理循环引用。 - 并发开销：多线程环境下，引用计数的修改必须是原子操作（代价高），或者用锁保护（降低并发性）。CPython 用全局解释器锁（GIL）回避了这个问题，但限制了多线程性能。 - 内存开销：每个对象额外存储一个计数器。
朴素的引用计数其实并不快——每次指针读写都要改计数器，频繁触及内存、污染缓存。所以真实系统几乎不用教科书式的引用计数，而是用各种优化版本：CPython 用延迟引用计数配合辅助的循环 GC；Swift 的 ARC 在编译期消去大量冗余的计数操作。
苹果的选择是个有意思的真实案例。早期 Objective-C 曾提供追踪式 GC，但苹果在 2011 年 WWDC 推出 ARC（Automatic Reference Counting，自动引用计数），随后将 Objective-C 的 GC 标记为弃用，并最终在 macOS Sierra 中移除。原因正是引用计数的优点：回收时机确定、没有不可预测的 GC 停顿，在电池受限、UI 要求流畅的移动设备上更可控。
可达性分析：追踪式 GC
更强大的垃圾回收算法基于可达性（Reachability）：从一组根对象（Root，包括全局变量、栈上的局部变量、寄存器中的值）出发，遍历所有可达对象。不可达的对象就是垃圾，可以安全回收。
标记-清除（Mark-Sweep）
第一步：标记（Mark）
从根出发，递归遍历所有可达对象，打上"活跃"标记。
第二步：清除（Sweep）
扫描整个堆，回收所有未被标记的对象。
标记-清除解决了引用计数的循环引用问题——即使 A 和 B 互相指向，只要没有外部根引用 A 或 B，它们就不可达，会被回收。
缺点：标记阶段需要暂停程序（Stop-the-World），在大堆上停顿明显；清除后内存碎片化。
标记-压缩（Mark-Compact）
标记后，把所有活跃对象压缩到内存的一端，消除碎片。代价是需要更新所有指向移动对象的指针，代价更高。
复制式 GC（Copying GC）
把堆分为两个半区（Fromspace / Tospace）。每次 GC 时，把活跃对象从 From 复制到 To，然后交换两半区角色。优点是压缩了内存（自然消除碎片），分配只需移动指针（极快）；缺点是任何时刻只有一半内存可用。C. J. Cheney 在 1970 年给出的非递归复制算法——只用两个指针、把待扫描区当成隐式队列——让复制式 GC 真正实用起来，至今仍是年轻代回收的基础。
分代垃圾回收
弱分代假说（Weak Generational Hypothesis）：经过大量实测的经验规律——大多数对象在年轻时就会死亡（即被分配后很快变得不可达）。这个观察最早由 Henry Lieberman 与 Carl Hewitt 在 1983 年提出，David Ungar 1984 年的 Generation Scavenging 算法据此把它工程化，自此成为几乎所有主流运行时的标配。
分代 GC（Generational GC） 利用这个规律：把堆分为年轻代（Young Generation / Eden）和老年代（Old Generation）：
- 年轻代：新分配的对象进入这里，GC 频繁（次要 GC，Minor GC），因为大多数垃圾都在这里。使用复制式 GC，代价低。
- 老年代：在年轻代存活多次 GC 的对象被晋升到老年代，GC 不频繁（主要 GC，Major GC）。
- 完整 GC（Full GC）：回收整个堆，代价最高，尽量避免。
Java（HotSpot JVM）和 JavaScript V8 都使用分代 GC。分代 GC 大幅减少了 GC 停顿时间，使得很多实时性要求较高的场景也能使用 GC 语言。
值得强调的是，Go 刻意没有采用分代 GC。Go 团队的判断是：编译器的逃逸分析（escape analysis，在编译期推断对象生命周期）能把大量短命对象直接分配在栈上、根本不进堆，于是"年轻代对象多数很快死亡"这个前提在 Go 里被提前到了编译期消化掉，分代再带来的收益不明显。这个取舍后来在 Discord 的真实案例里付出了代价（见下文）。
并发与增量 GC
"Stop-the-World"停顿对于延迟敏感的应用（实时游戏、交易系统、交互式 UI）是不可接受的。现代 GC 算法的目标是：在程序继续运行的同时，在后台做 GC。
并发标记（Concurrent Mark）：GC 线程和应用线程同时运行，GC 线程在后台标记可达对象。需要额外的"写屏障（Write Barrier）"来处理标记过程中应用修改对象引用的情况。
增量 GC（Incremental GC）：把 GC 工作分成小块，穿插在程序执行之间，每次只做一小步，将停顿分散。
三色标记：并发 GC 的通用框架
并发标记的正确性，依赖 Dijkstra 等人 1978 年提出的三色抽象（Tricolor Marking）。它把对象染成三色：
- 白色：尚未访问；标记结束时仍为白色的就是垃圾。
- 灰色：已发现（可达），但它指向的对象还没扫完。
- 黑色：自己和直接引用的对象都已扫完。
GC 从根出发，把对象逐步从白染灰、再染黑，灰色集合清空时标记结束。关键的三色不变式是：不允许出现"一个黑色对象直接指向白色对象、而这条路径上又没有灰色中介"的情形——否则那个白色对象会被误判为垃圾而错删。
应用线程在并发标记期间会修改引用，可能破坏这个不变式，写屏障（Write Barrier） 就是用来维持它的。两大流派：Dijkstra 式的增量更新（incremental-update），把新写入的引用重新染灰；Yuasa 式的起始快照（SATB，Snapshot-At-The-Beginning），把被覆盖掉的旧引用染灰、从而保住一份"标记开始那一刻"的可达快照。Go 用混合写屏障，Java 的 G1 用 SATB。
现代低延迟回收器
Go 从 1.5 版本（2015）起改用并发三色标记清除，把大部分标记工作与应用并行；到 1.8 版本（2017）典型负载下的 STW 停顿已降到 100 微秒以下。Java 的 G1 GC（Garbage First）把堆切成等大的 Region，优先回收垃圾最多的 Region，从 JDK 9 起成为 HotSpot 的默认回收器。更激进的 ZGC（JDK 11 实验、JDK 15 转正）和 Red Hat 的 Shenandoah（JDK 12 引入）把几乎所有工作并发化，设计目标是无论堆多大、哪怕到 16TB，停顿都不超过 10ms，实测常落在 1ms 以下（约 0.1–0.5ms）。
Rust 的另一条路：所有权系统
Rust 选择了完全不同的路径：通过编译期静态分析，在不运行 GC 的情况下保证内存安全。
Rust 的所有权规则：
- 每个值有唯一的所有者（Owner）
- 所有者超出作用域，值立刻被释放（自动插入 drop）
- 借用（Borrow）允许临时访问，但有严格的生命周期限制
- 借用检查器（Borrow Checker）在编译期验证所有访问的合法性
这从根本上消除了悬空指针，也让常见的"忘记释放"泄漏几乎不会发生，同时没有 GC 的运行时开销——适合系统编程（操作系统、驱动、游戏引擎）。
需要澄清的是，Rust 并不保证"绝对不泄漏"：与引用计数同理，Rc<RefCell<…>> 形成的循环引用照样会泄漏，而且 Rust 在设计上把"泄漏内存"视为安全行为（std::mem::forget、Box::leak 都是安全 API）。Rust 真正以编译期保证根除的是内存不安全（悬空指针、释放后使用、数据竞争），而非泄漏。代价是学习曲线极陡，类型系统和借用规则约束了部分编程模式。
追踪与引用计数：其实是一枚硬币的两面
教科书常把引用计数和追踪式 GC 讲成两条对立路线，一个"算引用数"、一个"找可达性"。2004 年，David Bacon、Perry Cheng 和 V. T. Rajan 在 OOPSLA 发表《A Unified Theory of Garbage Collection》，指出二者其实是同一结构的两种对偶视角：追踪从根出发"做加法"，计算什么活着；引用计数从删除引用出发"做减法"，计算什么死了。
更耐人寻味的结论是：他们越是分别优化这两种算法，二者的行为就越像——所有高性能的 GC 实现，最终都是追踪与引用计数的某种混合体。比如分代 GC 用追踪扫年轻代，却用类似引用计数的"记忆集 / 写屏障"来追踪跨代引用。这提醒我们：GC 的设计空间不是非此即彼，而是一个连续谱。
代价与争议
GC 停顿与延迟：无论多少优化，GC 仍会在某些时刻停顿程序，这对于金融交易系统、游戏帧率等延迟敏感场景是实质性问题。低延迟系统有时不得不手动控制 GC（Java 的 System.gc()，Go 的 runtime.GC()），或使用 Rust/C++ 等无 GC 语言。
一个被反复引用的真实案例是 Discord。2020 年，他们把负责"消息已读状态"的核心服务从 Go 重写为 Rust。问题不在于 Go 产生了多少垃圾——团队已经把垃圾压到极低——而在于 Go 的运行时每 2 分钟就会强制触发一次 GC（当时这是一个硬下限），而每次回收都要扫描整个巨大的 LRU 缓存来确认对象是否仍被引用，于是每隔两分钟就准时出现一次延迟尖刺。换成没有 GC、用所有权管理内存的 Rust 之后，这种周期性尖刺消失了。这恰好印证了前面 Go 不分代的取舍：没有年轻代的快速通道，长寿的大缓存每一轮都得被完整扫一遍。
内存使用量：GC 语言为了减少 GC 频率，通常让堆比实际使用的对象大得多（如 Go 的默认目标是堆增长 100% 时触发 GC）。这导致 GC 语言的内存使用量通常比 C/C++ 高出 2-5 倍。
这个"用内存换时间"的取舍有量化证据。Matthew Hertz 与 Emery Berger 在 2005 年（OOPSLA）的实测显示：当允许 GC 使用约 5 倍于实际存活数据的物理内存时，其吞吐量能追平、甚至略胜显式的手动管理；但内存收紧到 3 倍时，GC 慢约 17%；收紧到 2 倍时，慢约 70%。换句话说，GC 的"免费"是用富裕的内存换来的，内存一紧张，代价立刻显现。
GC 调优的复杂性：JVM GC（有 G1、ZGC、Shenandoah、CMS、Serial 等多种可选）有数十个参数可以调节，需要专业知识才能在特定工作负载下调出最优表现。"JVM 调优"是一个专门的技能领域。
跨域连接
- 内存层次与缓存：回收器的真实成本不止停顿时长。标记与复制会把整片堆拉过一遍，把应用的工作集从缓存里挤出去，于是恢复期的缺失代价也要算进账——这也解释了长寿的大缓存为何对回收器格外不友好。推论是：评估回收器不能只看停顿的毫秒数，还要看吞吐要多久才恢复。
- 什么是意义：回收器判定的是"可达"这条形式关系，而"还需不需要"是意向性的，形式系统无从通达。逻辑泄漏因此不是实现缺陷，而是定义边界：忘了注销的监听器、只增不减的缓存永远可达，回收器一个字节都不会动。
- 证明：并发标记的正确性靠一条循环不变式支撑——不允许出现黑色对象直指白色对象、中间又没有灰色中介的情形，写屏障是维持它的最小干预。由此可推：任何并发回收器都必须在新增引用与删除引用两条路径里至少堵住一条。而它的开销也有明确出处：主要不在标记，而在写屏障对每一次引用写入的抽税。
- 衰老与可塑性：细胞也做标记与清除：打上降解标签，再交给蛋白酶体。衰老中的蛋白稳态失衡同样不是清除机制坏了，而是该清的没被判定为垃圾，聚集体于是缓慢累积——与逻辑泄漏是同一种失败模式。
- 机会成本：自动回收把"手动释放"的认知成本，换成了"多买内存"的资本成本。实测规律很清楚：内存宽裕时吞吐可以追平手动管理，收紧到约两倍存活数据时代价陡增。因此内存越贵的场景，越倾向引用计数或所有权模型。同理，把内存管理策略当作纯技术选择是错的，它随硬件价格与延迟要求而变。
参考文献
- McCarthy, J. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. CACM 3(4), 1960. （Lisp 论文，包含 GC 的原始描述）
- Cheney, C. J. A Nonrecursive List Compacting Algorithm. CACM 13(11), 1970. （复制式 GC 的经典算法）
- Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., Steffens, E. F. M. On-the-Fly Garbage Collection: An Exercise in Cooperation. CACM 21(11), 1978. （三色标记与并发 GC 的奠基论文）
- Lieberman, H. & Hewitt, C. A Real-Time Garbage Collector Based on the Lifetimes of Objects. CACM 26(6), 1983. （分代思想的最早提出）
- Ungar, D. Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm. ACM SIGPLAN Notices, 1984. （分代 GC 的工程化）
- Bacon, D. F., Cheng, P., Rajan, V. T. A Unified Theory of Garbage Collection. OOPSLA 2004. （追踪与引用计数的对偶性）
- Hertz, M. & Berger, E. D. Quantifying the Performance of Garbage Collection vs. Explicit Memory Management. OOPSLA 2005. （GC 与手动管理的内存/性能权衡量化）
- Jones, R., Hosking, A., Moss, E. The Garbage Collection Handbook. CRC Press, 2012. （最全面的 GC 教材）
- Wilson, P. Uniprocessor Garbage Collection Techniques. IWMM, 1992. （经典综述）
- Howarth, J. Why Discord is Switching from Go to Rust. Discord Engineering Blog, 2020. （GC 周期性停顿的真实工程案例）
延伸阅读
- Klabnik, S. & Nichols, C. The Rust Programming Language. No Starch Press, 2019. （免费在线：doc.rust-lang.org/book/）