传统GC

.NET 、Java等，采用可达性分析、标记、整理、分代优化等手段。
具体步骤如下：

• 将所有对象标记为待删除
• 可达性分析，从GC Root出发，遍历所有可达对象，并标记为活跃
• 将所有活跃对象进行整理（移动位置，使其连续），使其在内存中更紧凑，减少内存碎片
• 在第一轮存活下来的所有对象，会被全部从第0代提升到第1代。新的对象会继续分配在第0代。每一代的GC是独立的，只有在每一代的内存达到预算的时候触发。

Golang GC

Golang 早期1.3之前也采用标记清除算法，其存在较多问题，为了改进GC，Golang用许多版本进行演化。

三色标记法

为了解决STW的问题，Golang将一次GC过程进行拆分，分为不同的阶段标记为三种颜色。
分别为：

• 白色 所有对象GC开始的初始状态，如果对象从可达，那么由白色转变为其他颜色，否则保持白色，最终GC结束时，所有白色会被回收。
• 灰色 属于一个中间状态，处于该颜色的对象，是可达的，但是其直接下游对象是否可达是未知的。当其所有直接下游对象都被Check过后，会变为黑色对象。
• 黑色 为GC生命周期的最终形态，该颜色的对象不会被回收。直到所有的灰色对象，都变为黑色对象时，GC结束。

通过这种方式，遍历不是DFS，而是变成了BFS，GC会找到当前层次的所有对象。这种一层一层的遍历会导致额外的问题。

存在的问题

上述三色标记看起来和标记整理不同，但是却并不能解决STW的问题。

被延迟的回收

在下图的场景中，对象A已经完成了扫描，变成了黑色，但是由于某个coroutine正在运行，对象A突然删除了对象C的引用，但是对象C和D却任然能够在本轮中幸存（当然，在下一次GC它肯定会被收拾干净），这会导致垃圾回收的精确度下降，当然这并不是致命的问题，这可能只会在用户内存空间非常缺乏的时候导致OOM。

真正的致命点：错误的回收

在关闭STW的情况下，一个coroutine在运行时，new了一个新的对象B，此时这个新对象是白色的（由于GC并不会对这个新对象进行到达分析，所以它将保持黑色），并且这个新对象被黑色对象A引用。那么在GC结束时，B会被回收，此时程序就会出现问题。

此时对象A引用了对象B，对象B却会在GC结束时被回收。

三色不变性

Google的工程师通过分析上述过程，提出了强三色不变性和弱三色不变性,
以下两个不变性条件，只需要满足任意其中一个，即可解决上面的STW问题。

强三色不变性

上面的情况中，黑色对象突然持有了一个白色对象的引用。由于不会再对黑色的直接引用对象进行扫描，所以这个被持有的白色，会被当做垃圾，如果能阻止这种情况发生，就能避免产生上述”悲剧“

所以，如果能保证黑色对象不直接持有白色对象的引用，即可解决问题。

弱三色不变性

除了黑色对象突然持有一个白色对象的引用外，如果一个白色对象的上游的所有灰色节点都被删除，那么也可能会造成意外情况。

下图中，原本的正常GC流程中，对象C为灰色，此时即将扫描C的下游节点对象D，但是C对D的引用被删除了，并且对象A引用了对象D

如果我们能保证不应该被回收的白色对象的上游路径中存在灰色对象，那么这个白色对象就一定会最终变为黑色对象而存活下来。

插入写屏障

在上面提到，黑色对象突然持有了白色对象的引用，这会导致这个被引用的白色对象在GC中被回收。为了破坏这个条件，可以在进行对象引用赋值的时候，将白色对象直接设置为灰色对象。

即将进行引用赋值操作

赋值后，直接将B设置为灰色对象。

插入写屏障，核心思想是通过hook，对堆上的赋值操作进行拦截。但是对于在栈上的写赋值操作，这么做无疑会增加大量的性能开销。所以栈上是不会启用插入写屏障的。

那么加入栈上出现了上面的黑色对象A，直接引用了一个白色对象B，就只能通过STW，来对栈上进行一个扫描了。整个STW时间大约为10-100ms，与coroutine的数量有关。

删除写屏障

Golang没有直接实现过删除写屏障，但是后续的优化，用到了其中的思想。

在对象A删除对象B的引用时候，如果对象B不为黑色，那么将对象B染为灰色。

回到前面的一个场景，黑色对象A引用对象D的同时，灰色对象C删除了对D的引用。
如果不加任何处理的话，那么D最终会一直保持白色，从而被GC掉。

而如果对D进行了染色，那么就可以保证D的存活，也就可以保证正确性了。

这样的做法，必须在GC开始阶段进行STW，对栈进行一次扫描，形成一个快照。否则会有问题：

协程1上有一个黑色对象A在栈上，有一个对象C在堆上，协程2栈上的灰色对象B引用了对象C和对象D

协程2此时进行操作，使得对象C引用了对象D，同时对象B删除了对象D的引用。

那么又会回到最开始的问题，对象C被错误的回收了。

为什么明明已经加了删除写屏障，还是会出问题呢？

1. 首先，A引用C这个操作，如果是在插入屏障，那么C是会变成灰色的。如果是这样，那么C不会被回收。
2. 对于删除写屏障，在对象B删除对象C引用的时候，也是不会生效的，因为B处于栈上。

所以，必须要在GC开始的时候，进行一次STW，并生成一个快照，在这个快照中，栈上对象的颜色全部都标记为黑色。此时，黑色对象的下一级对象就变成了灰色。

这个时候，对象C引用对象E，对象D在删除对象E的引用时，会触发删除屏障，那么就可以让对象E变为灰色，从而确保三色不变性

回收精度低

只要进行了删除操作，就会标记为灰色，这样做无疑会造成本应该被立即删除的对象，却在本轮GC中存活下来的问题。

混合写屏障

Golang在1.8之后，结合了上述的两种思想，通过混合写屏障 再次对GC进行了优化。

前面提到了插入写屏障的问题，在GC完毕后，还需要对栈进行STW，然后将栈上的对象扫描一遍。
而对于删除写入屏障，需要STW并扫描所有的栈，并生成快照。并且可能导致延迟回收。

而分析比较两者，可以发现，在插入写屏障的时候，需要后续对栈进行STW，而删除写屏障，由于快照，直接将栈上的对象标记为了黑色，从而无需进行STW。
而在删除之所以需要STW生成快照，由于前面提到的情况，如果不开启STW，那么就可能黑色对象形成对白色对象的唯一引用，此时假如同时也存在插入写屏障那么就可以很好的保证正确性。这就是混合屏障的优化思路。

其操作如下：

• GC开始时，将栈上的所有对象以及可达对象标记为黑色（无需STW）
• GC持续的期间，在栈上创建的新对象，都是黑色
• 被删除的对象，会被标记为灰色
• 被引用的对象，会被标记为灰色

其好处如下

• 可以避免插入屏障后续对栈的扫描，因为GC开始的时候，栈上的全部可达对象已经标记为黑色。
• 相比较于删除屏障，在扫描栈的时候，无需STW，而是一个栈一个栈的暂停。

以上两点，就是达到了全程无STW的效果。注意，虽然没有STW，但是并不代表没有暂停，扫描每一个栈的时候，仍需要将其block。