GO-GC

GO 1.3 标记清除

flowchart LR
    id1(start STW) --> Mark --> Sweep --> id2(stop SWT)

flowchart LR
    id1(start STW) --> Mark --> id2(stop SWT) --> Sweep

将清除操作置后，缩短了 SWT 时间

Go 1.5 三色标记法

flowchart LR
    id1(所有对象标记白色) --> id2(根对象标记灰色) --> id3(灰色对象标记为黑色, 灰色对象的子节点标记为灰色)
    id3 -->|还有灰色对象| id3
    id3 -->|没有灰色对象| id4(清除剩余的白色对象)

三色标记需要借助 STW，如果没有 STW，在标记过程中可能会出现：

灰色对象删除了子对象的引用(灰色丢失了白色)
黑色对象引用了被删除的子对象(白色对象被挂在黑色下)

当上述两个条件同时满足，虽然黑色对象引用着白色对象，但是白色对象最终还是会被清除。

屏障机制

该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。

想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性（Tri-color invariant）中的一种：

三色不变性

强三色不变式

黑色对象不能直接引用白色对象

弱三色不变式

被黑色对象引用的白色对象，它的上游必须有灰色对象

垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。

插入写屏障

Dijkstra 在 1978 年提出了插入写屏障，通过如下所示的写屏障，用户程序和垃圾收集器可以在交替工作的情况下保证程序执行的正确性：

1
2
3

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

上述插入写屏障的伪代码非常好理解，每当执行类似 *slot = ptr 的表达式时，我们会执行上述写屏障通过 shade 函数尝试改变指针的颜色。如果 ptr 指针是白色的，那么该函数会将该对象设置成灰色，其他情况则保持不变。

Dijkstra 的插入写屏障是一种相对保守的屏障技术，它会将有存活可能的对象都标记成灰色以满足强三色不变性。实际上不再存活的 B 对象最后没有被回收，只有在下一个循环才会被回收。

缺点

因为栈上的对象在垃圾收集中也会被认为是根对象，所以为了保证内存的安全，Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描。

这两种方法各有各的缺点，前者会大幅度增加写入指针的额外开销，后者重新扫描栈对象时需要暂停程序，垃圾收集算法的设计者需要在这两者之间做出权衡。

Go 选不在栈上开启写屏障，则会导致栈上的黑色对象可能指向白色对象(无法将后来被栈上对象所引用的白色对象变灰)，所以在标记结束后还需要对栈进行 re-scan。

删除写屏障

Yuasa 在 1990 年提出了删除写屏障，因为一旦该写屏障开始工作，它会保证开启写屏障时堆上所有对象的可达，所以也被称作快照垃圾收集（Snapshot GC）。

1
2
3

writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

上述代码会在老对象的引用被删除时，将白色的老对象涂成灰色，这样删除写屏障就可以保证弱三色不变性，老对象引用的下游对象一定可以被灰色对象引用。

缺点

如果不在栈上开启写屏障，则会导致堆上的黑色对象可能指向白色对象(无法在原先被栈上对象所引用的白色对象被删除时将其变灰)

Go 1.8 混合写屏障

在 Go 语言 v1.7 版本之前，运行时会使用 Dijkstra 插入写屏障保证强三色不变性，但是运行时并没有在所有的垃圾收集根对象上开启插入写屏障。因为应用程序可能包含成百上千的 Goroutine，而垃圾收集的根对象一般包括全局变量和栈对象，如果运行时需要在几百个 Goroutine 的栈上都开启写屏障，会带来巨大的额外开销，所以 Go 团队在实现上选择了不在栈上开启写屏障，在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描，在活跃 Goroutine 非常多的程序中，重新扫描的过程需要占用 10 ~ 100ms 的时间。

Go 语言在 v1.8 组合 Dijkstra 插入写屏障和 Yuasa 删除写屏障构成了如下所示的混合写屏障，该写屏障会将被覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色：

writePointer(slot, ptr):
    shade(*slot)
    shade(ptr)
    *slot = ptr

为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，我们还需要将创建的所有新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。

增量和并发

今天的计算机往往都是多核的处理器，垃圾收集器一旦开始执行就会浪费大量的计算资源，为了减少应用程序暂停的最长时间和垃圾收集的总暂停时间，我们会使用下面的策略优化现代的垃圾收集器：

增量垃圾收集 — 增量地标记和清除垃圾，降低应用程序暂停的最长时间；
并发垃圾收集 — 利用多核的计算资源，在用户程序执行时并发标记和清除垃圾；

因为增量和并发两种方式都可以与用户程序交替运行，所以我们需要使用屏障技术保证垃圾收集的正确性；与此同时，应用程序也不能等到内存溢出时触发垃圾收集，因为当内存不足时，应用程序已经无法分配内存，这与直接暂停程序没有什么区别，增量和并发的垃圾收集需要提前触发并在内存不足前完成整个循环，避免程序的长时间暂停。

增量

增量式的垃圾收集需要与三色标记法一起使用，为了保证垃圾收集的正确性，我们需要在垃圾收集开始前打开写屏障，这样用户程序修改内存都会先经过写屏障的处理，保证了堆内存中对象关系的强三色不变性或者弱三色不变性。虽然增量式的垃圾收集能够减少最大的程序暂停时间，但是增量式收集也会增加一次 GC 循环的总时间，在垃圾收集期间，因为写屏障的影响用户程序也需要承担额外的计算开销，所以增量式的垃圾收集也不是只带来好处的，但是总体来说还是利大于弊。

并发

并发的垃圾收集不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响：

虽然并发收集器能够与用户程序一起运行，但是并不是所有阶段都可以与用户程序一起运行，部分阶段还是需要暂停用户程序的，不过与传统的算法相比，并发的垃圾收集可以将能够并发执行的工作尽量并发执行；当然，因为读写屏障的引入，并发的垃圾收集器也一定会带来额外开销，不仅会增加垃圾收集的总时间，还会影响用户程序，这是我们在设计垃圾收集策略时必须要注意的。

GC 触发时机

内存分配时，目前触发 GC 的条件使用的是从 Go 1.5 时提出的调步（Pacing）算法，调步算法是优化并发执行时 GC 的步调，换句话说就是解决什么时候应该触发下一次 GC 的这个问题。
用户代码触发
后台定时触发

分代

分代假设并不适用于 Go 的运行栈机制，年轻代对象在栈上就已经死亡，扫描本就该回收的执行栈并没有为由于分代假设带来明显的性能提升，也成为了这一方案最终没有被采用的主要原因。

小节

并发回收的屏障技术归根结底就是在利用内存写屏障来保证强三色不变性和弱三色不变性。早期的 Go 团队实践中选择了从提出较早的 Dijkstra 插入屏障出发，不可避免的在为了保证强三色不变性的情况下，需要对栈进行重扫。而在后期的实践中，Go 团队提出了将 Dijkstra 和 Yuasa 屏障结合的混合屏障，将强三色不变性进行了弱化，从而消除了对栈的重新扫描这一硬性要求，使得在未来实现全面并发 GC 成为可能。

GoGC 在延迟和吞吐量之间选择了降低延迟(减少了 STW 的时间)

引用

[如何标记](