编程语言通常会使用手动和自动两种方式管理内存，C、C++ 以及 Rust 等编程语言使用手动的方式管理内存，工程师需要主动申请或者释放内存；而 Python、Ruby、Java 和 Go 等语言使用自动的 垃圾回收 （Garbage Collection）机制，简称 GC，GC 会自动检测程序运行过程中的垃圾并回收它。
优点：自动回收内存，避免忘记释放内存空间而发生的内存泄露和“悬垂指针”导致严重的无法预期的 BUG。程序员就不用再去担心因为忘了释放内存，从而大大减轻了负担。也不用再去头疼费事的内存管理，让程序员告别恼人的内存管理，把精力集中在更本质的编程工作上。
缺点：程序运行垃圾收集回收系统总是消耗一定的资源，不管怎么优化，对程序性能还是有一定的影响，包括：暂停程序、额外的存储开销、额外的计算开销、内存读写速度下降等等。

一、基本算法

1960 年首次发布了 GC 算法，直到现在为止，垃圾回收算法都是基于以下三种算法的组合或应用。

1、标记清除

标记清除算法由 标记 阶段和 清除 阶段构成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段，通过这两个阶段，就可以令不能利用的内存空间重新得到利用。标记阶段需要暂停程序（Stop the world，STW），扫描所有的对象，如果对象很多，暂停程序时间就很长，但是实现简单，搭配其他一些算法可以实现高效的 GC 算法。

• 标记阶段：从根对象（全局对象和栈对象）出发查找并标记堆中所有存活的对象；
• 清除阶段：遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表；

2、引用计数

给每个对象添加一个引用计数属性，新增一个引用时计数加 1，引用释放时计数减 1，当被引用数的值为 0 时，对象马上就会把自己作为空闲空间连接到空闲链表。也就是说，各个对象在变成垃圾的同时就会立刻被回收。内存管理的开销分布于整个应用程序运行期间，无需挂起应用程序的运行来做垃圾回收。虽然优点佷明显，但是局限性很多，包括：

• 频繁的更新计数，每一个对象的操作都可能增加或减少计数，然而程序中对象操作很多
• 计数器需要占用很多位，如果是 64 位系统，地址数量即最大的对象数量是 2^64，就需要一个 64 位的存储空间
• 算法简单但是实现复杂，每一个对象都要插入计数器，且无法处理循环引用

3、复制算法

只把某个空间里的活动对象复制到其他空间，把原空间里的所有对象都回收掉。复制活动对象的原空间称为 From 空间，将粘贴活动对象的新空间称为 To 空间。GC 复制算法是利用 From 空间进行分配的。当 From 空间被完全占满时，GC 会将活动对象全部复制到 To 空间。当复制完成后，该算法会把 From 空间和 To 空间互换，GC 也就结束了。From 空间和 To 空间大小必须一致。这是为了保证能把 From 空间中的所有活动对象都收纳到 To 空间里。可实现内存高速分配且不会产生碎片化，但只能利用一半的内存空间，如果使用递归调用的方式复制对象则可能存在栈溢出的情况，迭代复制更高效而且不存在栈溢出，只是需要一点额外的内存作为迭代缓存。

二、优化算法

传统的垃圾收集算法会在垃圾收集的执行期间暂停应用程序，一旦触发垃圾收集，垃圾收集器就会抢占 CPU 的使用权占据大量的计算资源以完成标记和清除工作，然而很多追求实时的应用程序无法接受长时间的 STW。垃圾收集器一旦开始执行就会浪费大量的计算资源，为了减少应用程序暂停的最长时间和垃圾收集的总暂停时间，我们会使用下面的策略优化现代的垃圾收集器：

• 增量垃圾收集：增量地标记和清除垃圾，降低应用程序暂停的最长时间；
• 并发垃圾收集：利用多核的计算资源，在用户程序执行时并发标记和清除垃圾；
  因为增量和并发两种方式都可以与用户程序交替运行，所以需要使用 屏障技术 保证垃圾收集的正确性；与此同时，应用程序也不能等到内存溢出时触发垃圾收集，因为当内存不足时，应用程序已经无法分配内存，这与直接暂停程序没有什么区别，增量和并发的垃圾收集需要提前触发并在内存不足前完成整个循环，避免程序的长时间暂停。
  增量式 （Incremental）的垃圾收集是减少程序最长暂停时间的一种方案，它可以将原本时间较长的暂停时间切分成多个更小的 GC 时间片，虽然从垃圾收集开始到结束的时间更长了，但是这也减少了应用程序暂停的最大时间。增量式的垃圾收集需要与 三色标记法 一起使用，为了保证垃圾收集的正确性，我们需要在垃圾收集开始前打开 写屏障 ，这样用户程序对内存的修改都会先经过写屏障的处理，保证了堆内存中对象关系的强三色不变性或者弱三色不变性。虽然增量式的垃圾收集能够减少最大的程序暂停时间，但是增量式收集也会增加一次 GC 循环的总时间。
  并发式 （Concurrent）的垃圾收集不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启 读写屏障 、利用多核优势与用户程序 并行执行 ，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响。虽然并发收集器能够与用户程序一起运行，但是并不是所有阶段都可以与用户程序一起运行，部分阶段还是需要暂停用户程序的，不过与传统的算法相比，并发的垃圾收集可以将能够并发执行的工作尽量并发执行。

1、三色标记

将程序中的对象分为以下三类：

• 白色：还未搜索过的对象
• 灰色：正在搜索的对象
• 黑色：搜索完成的对象
  GC 开始运行前所有的对象都是白色。GC 一开始运行，所有从根能到达的对象（全局对象和栈对象）都会被标记，然后被堆到栈里。GC 只是发现了这样的对象，但还没有搜索完它们，所以这些对象就成了灰色对象。灰色对象会被依次从栈中取出，其子对象也会被涂成灰色。当其所有的子对象都被涂成灰色时，对象就会被涂成黑色。当 GC 结束时已经不存在灰色对象了，活动对象全部为黑色，垃圾则为白色。
  当 STW 时，对象间的引用是不会发生变化的，可以轻松完成标记。而当需要支持并发标记时，即标记期间应用线程还在继续运行，对象间的引用可能发生变化，多标 和漏标 的情况就有可能发生。

假设已经遍历到 E（变为灰色了），此时应用执行了 objD.fieldE = null，此刻之后，对象 E /F/ G 是“应该”被回收的。然而因为 E 已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮 GC 不会回收这部分内存。这部分本应该回收但是没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响垃圾回收的正确性，只是需要等到下一轮垃圾回收中才被清除。

假设 GC 线程已经遍历到 E（变为灰色了），此时应用线程执行了：

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 断开引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

此时 GC 继续执行，因为 E 已经没有对 G 的引用了，所以不会将 G 放到灰色集合；尽管因为 D 重新引用了 G，但因为 D 已经是黑色了，不会再重新做遍历处理。最终导致的结果是：G 会一直停留在白色集合中，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性，是不可接受的。不难分析，漏标只有同时满足以下两个条件时才会发生：

• 条件一：灰色对象断开了白色对象的引用；即灰色对象原来成员变量的引用发生了变化。
• 条件二：黑色对象重新引用了该白色对象；即黑色对象成员变量增加了新的引用。

2、屏障技术

因为用户程序可能在标记执行的过程中修改对象的指针，所以三色标记清除算法本身是不可以并发或者增量执行的，它仍然需要 STW，想要并发或者增量地标记对象还是需要使用 屏障技术 。想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性（Tri-color invariant）中的任意一种：

• 强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；
• 弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径；

遵循上述两个不变性中的任意一个，我们都能保证垃圾收集算法的正确性，而屏障技术就是 在并发或者增量标记过程中，给新添加的和被修改的对象实时上色，保证对象不会被意外清理掉（即使多标也没有关系，下一次 GC 会清理的）。屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成 读屏障 （Read barrier）和 写屏障 （Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。

插入写屏障：每当我们执行类似*slot = ptr的表达式时，我们会执行写屏障尝试改变指针的颜色。如果 ptr 指针是白色的，那么该函数会将该对象设置成灰色，其他情况则保持不变。它是一种相对保守的屏障技术，它会将有存活可能的对象都标记成灰色以满足强三色不变性。
删除写屏障 ：白色对象的引用被删除时，将对象涂成灰色，这样删除写屏障就可以保证弱三色不变性，对象引用的下游对象一定可以被灰色对象引用。删除写屏障通过对对象的着色，保证了对象和下游的对象能够在这一次垃圾收集的循环中存活。避免发生悬挂指针以保证用户程序的正确性。

三、Go 垃圾收集器

Go 语言的垃圾收集器从诞生的第一天起就一直在演进，除了少数几个版本没有大更新之外，几乎每次发布的小版本都会提升垃圾收集的性能，而与性能一同提升的还有垃圾收集器代码的复杂度。

• v1.0：完全串行的标记和清除过程，需要暂停整个程序；
• v1.1：在多核主机并行执行垃圾收集的标记和清除阶段；
• v1.3：运行时基于只有指针类型的值包含指针的假设增加了对栈内存的精确扫描支持，实现了真正精确的垃圾收集；将 unsafe.Pointer 类型转换成整数类型的值认定为不合法的，可能会造成悬挂指针等严重问题；
• v1.5：实现了基于三色标记清扫的并发垃圾收集器；大幅度降低垃圾收集的延迟从几百 ms 降低至 10ms 以下；计算垃圾收集启动的合适时间并通过并发加速垃圾收集的过程；
• v1.6：实现了去中心化的垃圾收集协调器；基于显式的状态机使得任意 Goroutine 都能触发垃圾收集的状态迁移；使用密集的位图替代空闲链表表示的堆内存，降低清除阶段的 CPU 占用；
• v1.7：通过并行栈收缩将垃圾收集的时间缩短至 2ms 以内；
• v1.8：使用混合写屏障将垃圾收集的时间缩短至 0.5ms 以内；
• v1.9：彻底移除暂停程序的重新扫描栈的过程；
• v1.10：更新了垃圾收集调频器的实现，分离软硬堆大小的目标；
• v1.12：使用新的标记终止算法简化垃圾收集器的几个阶段；
• v1.13：通过新的 Scavenger 解决瞬时内存占用过高的应用程序向操作系统归还内存的问题；
• v1.14：使用全新的页分配器优化内存分配的速度；
  从 Go 语言垃圾收集器的演进能够看到该组件的的实现和算法变得越来越复杂，最开始的垃圾收集器还是不精确的单线程 STW 收集器，但是最新版本的垃圾收集器却支持并发垃圾收集、去中心化协调等特性。

1、并发垃圾收集

Go 语言在 v1.5 中引入了并发的垃圾收集器，该垃圾收集器使用了我们上面提到的三色抽象和写屏障技术保证垃圾收集器执行的正确性。
并发垃圾收集器会在扫描对象之前暂停程序做一些标记对象的准备工作，其中包括启动后台标记的垃圾收集器以及开启写屏障，如果在后台执行的垃圾收集器不够快，应用程序申请内存的速度超过预期，运行时就会让申请内存的应用程序辅助完成垃圾收集的扫描阶段，在标记和标记终止阶段结束之后就会进入异步的清理阶段，将不用的内存增量回收。
v1.5 版本实现的并发垃圾收集策略由专门的 Goroutine 负责在处理器之间同步和协调垃圾收集的状态。当其他的 Goroutine 发现需要触发垃圾收集时，它们需要将该信息通知给负责修改状态的主 Goroutine，然而这个通知的过程会带来一定的延迟，这个延迟的时间窗口很可能是不可控的，用户程序会在这段时间分配界面很多内存空间。
v1.6 引入了去中心化的垃圾收集协调机制，将垃圾收集器变成一个显式的状态机，任意的 Goroutine 都可以调用方法触发状态的迁移。

2、回收堆目标

STW 的垃圾收集器虽然需要暂停程序，但是它能够有效地控制堆内存的大小，Go 语言运行时的默认配置会在堆内存达到上一次垃圾收集的 2 倍时，触发新一轮的垃圾收集，这个行为可以通过环境变量 GOGC 调整，在默认情况下它的值为 100，即增长 100% 的堆内存才会触发 GC。因为并发垃圾收集器会与程序一起运行，所以它无法准确的控制堆内存的大小，并发收集器需要在达到目标前触发垃圾收集，这样才能够保证内存大小的可控，并发收集器需要尽可能保证垃圾收集结束时的堆内存与用户配置的 GOGC 一致。
Go 语言 v1.5 引入并发垃圾收集器的同时使用垃圾收集调步（Pacing）算法计算触发的垃圾收集的最佳时间，确保触发的时间既不会浪费计算资源，也不会超出预期的堆大小。优化堆的增长速度和垃圾收集器的 CPU 利用率。

3、混合写屏障

在 Go 语言 v1.7 版本之前，运行时会使用插入写屏障保证强三色不变性，但是运行时并没有在所有的垃圾收集根对象上开启插入写屏障。因为 Go 语言的应用程序可能包含成百上千的 Goroutine，而垃圾收集的根对象一般包括全局变量和栈对象，如果运行时需要在几百个 Goroutine 的栈上都开启写屏障，会带来巨大的额外开销，所以 Go 团队在实现上选择了在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描，在活跃 Goroutine 非常多的程序中，重新扫描的过程需要占用 10 ~ 100ms 的时间。
Go 语言在 v1.8 组合插入写屏障和删除写屏障构成了 混合写屏障 ，该屏障会将被覆盖的对象标记成灰色和新对象也标记成灰色，为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，还需要将 栈上创建的所有新对象都标记成黑色 ，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。

4、回收过程

Go 语言的垃圾收集可以分成 清除终止 、 标记 、 标记终止 和清除 四个不同阶段，它们分别完成了不同的工作。

• 清理终止阶段；

  • 暂停程序，所有的处理器在这时会进入安全点（Safe point）；
  • 如果当前垃圾收集循环是强制触发的，我们还需要处理还未被清理的内存管理单元；

• 标记阶段；

  • 将状态切换至_GCmark、开启写屏障、用户程序协助并将根对象入队；
  • 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；
  • 开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器；
  • 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；
  • 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段；

• 标记终止阶段；

  • 暂停程序、将状态切换至_GCmarktermination 并关闭辅助标记的用户程序；
  • 清理处理器上的线程缓存；

• 清理阶段；

  • 将状态切换至_GCoff 开始清理阶段，初始化清理状态并关闭写屏障；
  • 恢复用户程序，所有新创建的对象会标记成白色；
  • 后台并发清理所有的内存管理单元，当 Goroutine 申请新的内存管理单元时就会触发清理；