激荡60年——垃圾回收与Go的选择
什么是垃圾回收
在计算机科学中，垃圾回收（GC garbage collection）是自动内存管理的一种形式。通常由垃圾收集器收集并适时回收或重用不再被对象占用的内存。垃圾回收作为内存管理的一部分，其包含了3个重要的功能：如何分配和管理新对象、如何识别正在使用中的对象、如何清除不再使用的对象。垃圾回收让开发变得更加简单，屏蔽了复杂而且容易犯错的操作。现代的高级语言几乎都具有垃圾回收的功能，例如Python、java、C#、当然也包括了Go语言。
为什么需要垃圾回收
减少错误和复杂性
传统的没有垃圾回收的语言，例如C、C++ 需要手动分配、释放内存。不管是“内存泄漏” 还是野指针都是让开发者非常头疼的问题。虽然垃圾回收不保证完全不产生内存泄漏，但是其提供了重要的保证，即不再被引用的对象将最终被收集。这种设定同样也避免了悬空指针、多次释放等手动管理内存时出现的问题。具有垃圾收集的语言屏蔽了内存管理的复杂性，开发者可以更好的关注核心的业务逻辑。
解耦
现代软件工程设计的核心思想之一是模块化的方式进行组合，而模块与模块之间只提供少量的接口进行交互。减少模块之间的耦合意味着一个模块的行为不依赖于另一个模块的实现。当两个模块中同时维护了同一内存时，释放内存将会变得非常小心。这种手动分配的困难在于，难以在本地模块内做出全局的决定。而具有垃圾回收的语言，将垃圾收集的工作托管给了具有全局视野的运行时代码。开发者书写的业务模块将真正的实现解耦，从而有利于开发、调试并开发出更大规模、高并发项目。
但是垃圾回收并不是在任何场景下都适用的，因为垃圾回收带来了额外的成本，需要保存内存的状态信息（例如是否使用，是否包含指针）并扫描内存，在很多时候，还需要中断整个程序来处理垃圾回收。因此，在要求极致的速度和内存要求极小的场景（例如嵌入式、系统级程序）时并不适用。但是却是开发大规模、分布式、微服务应用程序的极佳选择。
内存管理与垃圾回收是Go语言最复杂的模块之一。永远都不可能有最好的垃圾回收算法，因为每一个应用程序所在的硬件条件、工作负载、性能要求都是不同的。理论上来讲，可以为单独应用程序设计最佳的内存分配方案，但这是不显示。通用的垃圾回收语言会提供通用的垃圾回收策略，并且每一种语言侧重的垃圾回收目标会不尽相同。垃圾回收的常见指标包括了程序暂停时间、空间开销、回收的及时性等，根据侧重于不同的设计目标会产生不同的垃圾回收策略。
垃圾回收的5种经典策略
标记-清扫(Mark-sweep)
标记-清扫算法是历史最悠久的垃圾回收策略。其最远可以追溯到1960年，由约翰·麦卡锡（John McCarthy）提出，用于LISP语言的自动内存管理。标记-清扫策略顾名思义分为了2个主要的阶段。第一阶段是扫描并标记当前活着的对象，第二阶段是清扫没有被标记的垃圾对象。因此，标记-清扫算法是一种间接的垃圾回收算法，其不是直接查找垃圾对象，而是通过活着的对象倒推出垃圾对象。
扫描的过程一般是从栈上的根对象开始， 只要对象引用了其他的堆对象，就会一直往下扫描。因此搜索方式可以采取深度优先搜索或者广度优先搜索的方式。
在扫描阶段，为了有效管理扫描对象的状态，可以通过颜色来对对象的状态进行抽象，比较经典的抽象方式是Dijkstra提出的三色抽象[Dijkstra et al, 1976, 1978]，其通过将被标记的对象标记为黑色(已经被扫描)、 灰色（灰色对象暂时还没有被扫描，扫描之后会转换为黑色）、白色（暂时还没有被扫描，可能有垃圾对象，如果被灰色对象扫描引用并扫描到会标记为灰色）来对对象进行区分。
有些垃圾算法将对象对象进行了更多颜色的抽象，后面会看到，在Go语言中，使用了经典的三色抽象标记算法。
标记-清扫算法主要的缺点在于，可能会产生内存碎片或空洞。这会导致由于没有连续的内存而使新对象分配失败。想象一下中间的区域被垃圾回收，留下了两端的20M的内存空间。现在该程序将由于没有连续的区域而不能够分配30M的内存。或者有连续的内存但是增加了分配查找的时间。
标记-清扫算法的另一个缺点在于一般需要在标记阶段，暂停所有的程序运行。否则可能会破坏标记的结果。想象一下，在标记阶段，假设一个对象R一开始只引用了A，并完成了扫描。
与此同时，工作线程执行操作将R对象引用了B。但是由于R对象已经不再被扫描，所以最后B会被当做垃圾对象清扫掉，这是危险的操作。
后面会看到，可以通过强弱三色标记策略规避这种难题从而实现并发的垃圾收集策略。
标记-压缩(Mark-compact)
标记-压缩通过将分散、活着的对象移动到更紧密的空间从而解决内存碎片的问题。标记-压缩策略仍然分为了标记与压缩两个阶段。标记过程和标记-清扫类似，在压缩阶段，需要扫描活着的对象压缩到空闲的区域。
标记-压缩策略的缺点在于，内存对象在内存的位置是随机可变的。这常常会破坏缓存的局部性。并且，时常需要一些额外的空间来标记当前一个对象已经移动到了其他地方。在压缩阶段，如果B对象发生了转移，必须要更新所有引用了B对象的A对象的指针，这无疑增加了实现的复杂性。
半空间复制（Semispace copy）
半空间复制是一种用空间换时间的策略。经典的半空间复制策略只能使用一半的虚拟内存空间，并保留另一半的空间用于快速的压缩内存，因此得名。
半空间复制由于其压缩性，因此消除了内存碎片问题。同时其压缩时间比标记-压缩算法更快。半空间复制不分为多个阶段也没有标记阶段，其在从根对象扫描的时候就可以直接进行压缩。每一个扫描到的对象都会从fromspace的空间复制到tospace的空间。因此，一旦扫描完成，就得到了一个压缩后的副本。
引用计数（reference counting）
一种直接简单的识别垃圾对象的方式是引用计数。每一个对象都包含了一个引用计数。每当一个对象引用了此对象时，引用计数就会增加。反之取消引用后，引用计数就会减少。一旦引用计数为0时，表明该对象为垃圾对象，需要被回收。引用计数策略简单高效，垃圾回收阶段不需要额外暂用大量内存，即便垃圾回收系统一部分出现异常的情况，也能有一部分对象正常的回收。但这种朴素的策略也有一些致命的缺点。一些没有破坏性的操作，例如只读操作、循环迭代操作也需要跟新引用计数。栈上的内存操作或寄存器操作也需要跟新引用计数是难以接受的。同时，引用计数必须要原子的更新引用计数，因为可能会并发的操作同一个对象。另外，引用计数也无法处理自引用的对象
分代GC
分代GC指的是将按照对象存活时间进行划分，这种策略的重要前提是：死去的一般都是新创建不久的对象。因此，完全没有必要反复的扫描旧对象。这大概率会加快垃圾回收的速度，提高处理能力和吞吐量，减少程序暂停的时间。但是分代GC也不是没有成本的，一方面，这种策略没有办法及时回收老一代的对象，并且需要额外开销引用和区分新老对象，特别是有多代的时候。
注意，上面每一种策略在实践中都有许多微妙的变化，例如分代GC可以不止有两代，而有多代。如何去定义老对象等等。并且这些策略一旦混合起来使用，并且考虑到并发或并行时的场景会更加的复杂。
Go语言中的垃圾回收
Go语言采用了并发三色标记算法来进行垃圾回收。三色标记本身是最简单的一种垃圾回收策略，实现也很简单。引用计数由于固有的缺陷，在并发时不可扩展的特性很少被使用，不适合Go这样高并发的语言。真正值得探讨的是压缩GC 与 分代GC。
为什么不选择压缩GC？
压缩算法的主要优势是减少碎片、并且分配快速。在Go语言中，使用了现代内存分配算法TCmalloc、虽然没有压缩算法那样极致，但是已经很好的解决了内存碎片的问题。并且，由于需要加锁、压缩算法并不适合在并发程序的使用。最后在Go语言的设计初期由于紧迫的时间计划，放弃了考虑更加复杂的压缩实现算法，转而使用了更简单的三色标记[1].
为什么不选择分代GC？
Go语言并不是没有尝试过分代GC。分代GC的主要假定是大部分变成垃圾的对象都是新创建的对象。但是在Go语言中由于编译器的优化，通过内存逃逸的机制，将会继续使用的对象转移到了堆中。大部分新创建的对象很快变为垃圾的对象会在栈中分配。这和其他使用隔代GC的编程语言有显著的不同，这减弱了使用隔代GC的优势。同时， 隔代GC需要额外的写屏障来保护并发垃圾回收时对象的隔代性，这会减慢GC的速度。因此，隔代GC是被尝试过并抛弃的方案。[1]
在后面的小节中，首先围绕垃圾回收最重要的两个问题展开：何时进行垃圾收集 以及如何进行垃圾收集。