前言
Go垃圾回收采用的是Mark&Sweep（标记清除算法），从v1.1开始Go就不断对它的垃圾回收算法进行优化，下面是具有里程碑意义的算法迭代过程
- v1.0 整个过程STW（stop the world，即停止整个程序的运行）
- v1.3 分离Mark和Sweep，Mark阶段STW，Sweep阶段并发
- v1.5 三色标记法，Mark阶段可以部分并发，大幅度降低垃圾收集延迟从几百ms降低至10ms以下；
- v1.8 混合写屏障（hybrid write barrier），移除栈的重扫描过程，垃圾收集的时间缩短至0.5ms以内
本文先介绍标记清除算法，在标记清除算法基础上引入三色标记法，在讲述三色标记法的过程中我们思考三个问题，由这三个问题分别引入写屏障、并发Sweep和辅助GC的概念，最后我们展望一下Go垃圾回收未来的演进方向。
标记清除
根对象
垃圾回收是针对堆内存进行回收，根对象就是指在堆的外部并且能被我们访问到的对象，Go里主要包括全局变量和Goroutine栈上的变量
过程
过程比较简单，分为Mark阶段和Sweep阶段，Mark阶段就是从根对象开始广度优先或者深度优先遍历，遍历结束后那些不可达的对象就被认为是垃圾对象，Sweep阶段就是扫描整个堆内存，删除那些不可达的垃圾对象
优缺点
优点是实现简单快糙猛，缺点是STW，在很多场景下是无法忍受的，Go的后续优化思路都是在标记清除算法的基础上尽量去降低STW的占比
三色标记法
三色标记法是Go1.5引入的垃圾回收算法，他是对标记清除算法的一种优化，可以降低Mark阶段的STW，它的标记操作大部分都可以并发执行
触发时机
- GC百分比
当前分配的内存达到一定阈值时触发，这个阈值可以通过GOGC这个系统环境变量来调节，默认是100表示阈值是超过上次GC后内存的一倍（100%）时触发，比如上次GC后内存占用100M，那么下次当内存占用达到200M时就会触发一次GC
- 2分钟
当一定时间（2分钟）没有执行过GC就触发GC
- 手动
程序调用runtime.GC()主动触发
回收过程
起初所有对象都是白色，从根对象出发广度优先扫描所有可达对象，标记为灰色，放入待处理队列。
从队列取出灰色对象，将其引用对象标记为灰色放入队列，自身标记为黑色，一直重复直到灰色对象队列为空，此时白色对象即为垃圾，进行回收
关键问题
针对上面三色标记法的整个过程，我们来思考三个关键的问题，后面的优化点其实都是围绕这三个问题展开的，这里敲一下黑板，后面具体解决方法其实并不重要，重要的是要知道这些方法要解决什么问题
-
问题1
Mark过程中如果发生引用变更和新对象产生怎么办？举个例子，下图最左边是在Mark过程中的一个状态，此时发生了引用变更，新增了A->C的引用f，删除了B->C的引用e，这时出现一个致命的问题，因为A是黑色表示已经走完了整个标记过程，此时C就会保持着白色状态，直到被Sweep阶段被误清除。
-
问题2
Sweep阶段是并发的，如果这时发生了引用变更和新对象产生怎么办？
-
问题3
如果应用程序申请内存的速度比Mark的速度还要快，那么Mark不就永远也无法结束了？
写屏障（write barrier）
针对上面的问题1，引入写屏障的解决方案，写屏障技术好比是一个钩子方法，在应用程序发生写操作时执行的一段代码
4.1 插入屏障
插入屏障的主要思路是如果新插入的对象是白色的，就把它主动标记为灰色（下面伪代码的shade函数），保证了这个赋值对象不会被误删。下面是Dijkstra写屏障的伪代码，ptr是新插入的对象指针，slot是引用这个新对象需要保存的地址，Go1.5使用的就是Dijkstra插入写屏障，
writePointer(slot, ptr):
shade(ptr) // 如果ptr是白色, 则直接标记为灰色
*slot = ptr
}
这里引申另外一个问题，因为栈上的操操作对效率要求非常高（函数调用弹出频繁使用），所以Go对栈上的对象并没有做写屏障（看上面那个伪代码的slot，如果slot是栈上的，Go不会插入写屏障，这里就会出现栈上黑色对象引用白色对象的情况，导致误删除）），那么最后就需要对栈上的对象重新扫描一遍，而这个过程需要STW，这个也是Go1.8以前的一个非常大的延迟来源。
4.2 删除屏障
删除屏障的主要思路是在老对象的引用被删除时，如果老对象是白色的，就把它标记为灰色，保证了这个赋值对象不会被误删，删除写屏障的优点是标记结束时不需要重新扫描。下面是Yuasa写屏障的伪代码。
writePointer(slot, ptr)
shade(*slot) // 如果slot之前是白色, 即被删除的对象, 则直接标记为灰色
*slot = ptr
但是删除屏障也有缺点，一是被删除后的对象如果是垃圾对象，它会活过这一轮，在下一轮GC中被清理掉，即回收精度低。二是为了解决栈上对象没有写屏障保护的问题，在开始标记之前，需要对栈根做一个快照，即把所有栈上的对象标记黑色，栈上引用的对象标记为灰色，这个过程是STW的，本质上是通过快照的方式可以在开始就把这些对象保护起来，这样做可以避免插入写屏障的重新扫描过程，但是会对用户时延有比较严重的影响。基于上面两个缺点Go实际并没有采用删除屏障。
上面的讲解可能不是很直观，为了方便理解，下面举个实际的例子
（1）初始栈快照状态，把所有栈上的对象标记黑色，栈上引用的对象标记为灰色。后续新创建的对象也直接标记为黑色。
（2）栈上对象赋值，因为是对栈上对象的赋值，所以这里不需要写屏障。
（3）堆上引用删除。由于删除写屏障的保护，原对象标记为灰色，避免误删除。
（4）栈上对象的引用删除
这里有同学会问，如果是删除栈上对象的引用呢，这个时候栈上没有写屏障，是怎么解决的？是因为在初始快照阶段，这个引用已经被灰色保护了，所以删除栈上对象的引用不会出现问题。所以，删除写屏障需要开始阶段对栈根进行一次快照操作，目的就在于此。
4.3 混合写屏障（hybrid write barrier）
Go1.8以后采用了混合写屏障的方法，就是结合了Dijkstra插入屏障和Yuasa删除屏障。
本质上混合写屏障是在删除写屏障基础上做了优化，主要思路是初始化栈快照时不是锁住整个进程，而是每次扫描到哪个栈时就只锁住单个栈。但这样做，其他未被扫描到的栈，由于没有快照保护，就会出问题，所以混合写屏障在这时使用了插入写屏障将新增加的引用也标记为灰色。
writePointer(slot, ptr)
// 如果slot之前是白色, 即被删除的对象, 则直接标记为灰色
shade(*slot)
// 如果当前栈没有被扫描, 则需要插入写屏障来保证正确性，
if current stack is grey:
// 如果ptr是白色, 则直接标记为灰色
shade(ptr)
*slot = ptr
为了方便理解，下面举例分情况讨论，讲解插入写屏障在这里的作用
假设有一个黑色对象A和一个白色对象B，现在要发生赋值操作，让黑色对象A引用白色对象B，但是当前栈没有被快照，会出现什么问题呢（新创建的对象都会统一标记为黑色，所以才会有当前栈没有被快照，却出现黑色对象A的缘故）？ 我们分两种情况来讨论。
（1）A在栈上
这种情况不需要任何屏障，因为在后面当前栈一定会经过初始化快照阶段，白色对象B也一定会被标记成灰色。
（2）A在堆上
这种情况就需要插入写屏障来保护，因为对于B来说，在当前栈上，它没有被快照保护，就会出现误删
讲到这可能会有同学问，如果当前栈已经被扫描过，也就是说有快照保护，就一定安全吗？如果是发生在不同的栈上会有问题吗？
这里其实没有问题的，因为只要对象B能在当前栈被引用到，说明对象B一定是在当前栈的引用链上，那么对象B也一定是在快照的保护之下的，所以无论A是在栈上还是堆上，也无论对象B是不是被其他栈引用，都不会有问题。
并发Sweep
针对上面的问题2，我们分引用变更和新对象产生两个方面来思考这个问题
- 引用变更
当并发Sweep过程中出现引用变更，会引起清除掉活跃的对象吗？其实是不会的，我们使用反证法，如果真出现活跃对象被清除，一定是有白色对象在Sweep过程中被引用到，但是在Mark阶段结束以后，白色对象在堆内存里其实是不可达的，也就是程序不可能再引用到白色对象。
- 新对象产生
Sweep阶段的清除操作是扫描整个堆内存，我们可以记下当前扫描的位置，如果新申请的对象地址是在这个位置之前，我们什么也不用做，因为它不会被误删；如果新申请的对象地址是在这个位置之后，我们可以把直接这个对象的状态标记为黑色，就可以避免被误删。
辅助GC
针对问题3，为了防止应用程序申请内存的速度比Mark的速度还要快的情况，Go采用了一种叫辅助GC也叫gcAssist的方法，它遵循一条非常简单原则，分配多少内存就需要完成多少标记任务，简单说就是在Mark阶段开始以后，就给内存的申请者提了一个要求，在给你分配内存之前，你得先帮我标记与之相当的内存出来，让应用程序辅助完成标记操作。
总结
我们再来总结三色标记垃圾回收的整个过程
- 准备阶段: 开启写屏障，打开辅助GC，这一步是STW
- 栈快照: 每次对单个栈生成快照，只锁住单个栈。
- 并发标记
- 结束标记: 关闭写屏障，关闭辅助GC，这一步是STW
- 并发清除
可以看出，采用混合写屏障以后，Go垃圾回收的STW时间已经非常短了。
未来演进的方向
其中一个方向是Java里的分代回收算法，分代回收效率比较高，但是实现比较复杂。
golang-nuts 这里解释了Go为什么没有采用内存压缩和分代回收算法，这里面提到了tcmalloc、栈内存分配和逃逸分析
