Go GC 垃圾回收
垃圾回收（Garbage Collection，GC）是编程语言中提供的自动的内存管理机制，自动释放不需要的内存对象，让出存储器资源。GC 过程中无需程序员手动执行。
GC 机制在现代很多编程语言都支持，GC 能力的性能与优劣也是不同语言之间对比度指标之一。
1 GC 变革
// TODO
2 堆和栈
栈：由操作系统自动分配释放，存放函数的参数值，局部变量的值等。
堆：一般由程序员分配和释放，若程序员不释放，程序结束时可能由 OS 回收。
栈使用的是一级缓存，他们通常都是被调用时处于存储空间中，调用完毕立即释放。
堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定，但并不是一旦成为孤儿对象就能被回收。
申请到栈内存好处：函数返回直接释放，不会引起垃圾回收，对性能没有影响。
3 标记清除算法
Go V1.3 之前使用普通的标记-清除算法，主要有两个主要的步骤：
-
标记(Mark phase)，找出不可达的对象，然后做上标记。
-
清除(Sweep phase)，回收标记好的对象。
3.1 第一步
暂停程序业务逻辑， 分类出可达和不可达的对象，然后做上标记。
👆图中表示是程序与对象的可达关系，目前程序的可达对象有对象 1-2-3，对象 4-7 等五个对象。
3.2 第二步
开始标记，程序找出它所有可达的对象，并做上标记👇。
对象 1-2-3 、对象 4-7 等五个对象被做上标记。
3.3 第三步
标记完了之后，然后开始清除未标记的对象。
对象 5，6 不可达，被 GC 清除。
操作简单，但是 mark and sweep 算法在执行的时候，需要程序暂停！即 STW，STW 的过程中，CPU 不执行用户代码，全部用于垃圾回收，这个过程的影响很大，所以 STW 也是一些回收机制最大的难题和希望优化的点。
在执行第三步的这段时间，程序会暂定停止任何工作，卡在那等待回收执行完毕。
3.4 第四步
停止暂停，让程序继续执行。然后循环重复这个过程，直到 process 程序生命周期结束。
3.5 缺点与优化
标记清除算法明了，过程鲜明干脆，但是也有非常严重的问题，就是 STW，让程序暂停，程序出现卡顿。
Go V1.3 版本之前就是用这种方式来实施的。执行 GC 的基本流程就是首先启动 STW 暂停，然后执行标记，再执行数据回收，最后停止 STW ，如下图👇
从👆来看，全部的 GC 时间都是包裹在 STW 范围之内的，这样貌似程序暂停的时间过长，影响程序的运行性能。所以Go V1.3 做了简单的优化，将 STW 的步骤提前，减少 STW 暂停的时间范围 👇
主要是将 STW 的步骤提前了一步，因为在 Sweep 清除的时候，可以不需要 STW 停止，因为这些对象已经是不可达对象了，不会出现回收写冲突等问题，清除操作和用户逻辑可以并发。
但是无论怎么优化，Go v1.3 都面临这个一个重要问题，就是 mark-and-sweep 算法会暂停整个程序 。
4 有STW的三色标记法
Go 中的垃圾回收主要应用三色标记法，GC 过程和其他用户 goroutine 可并发运行，但需要一定时间的 STW。
所谓三色标记法实际上就是通过三个阶段的标记来确定需要清除的对象有哪些。
4.1 第一步
每次新创建的对象，默认的颜色都是标记为 “白色”👇
上图所示，我们的程序可抵达的内存对象关系如左图所示，右边的标记表是用来记录目前每个对象的标记颜色分类。这里所谓 “程序”，是一些对象的根节点集合。如果我们将 “程序” 展开，会得到类似如下的表现形式：
4.2 第二步
每次 GC 回收开始， 会从根节点开始遍历所有对象，把遍历到的对象从白色集合放入 “灰色” 集合：
本次遍历是一次遍历，非递归形式，是从程序初次可抵达的对象遍历一层，如上图所示，当前可抵达的对象是对象1和对象4，那么自然本轮遍历结束，对象1和对象4就会被标记为灰色，灰色标记表就会多出这两个对象。
4.3 第三步
遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合：
这一次遍历是只扫描灰色对象，将灰色对象的第一层遍历可抵达的对象由白色变为灰色，如：对象2、对象7。 而之前的灰色对象1 和对象4 则会被标记为黑色，同时由灰色标记表移动到黑色标记表中。
4.4 第四步
重复第三步， 直到灰色中无任何对象，如图👇所示：
当我们全部的可达对象都遍历完后，灰色标记表将不再存在灰色对象。
目前全部内存的数据只有两种颜色，黑色和白色。那么，黑色对象就是我们程序逻辑可达（需要的）对象，这些数据是目前支撑程序正常业务运行的，是合法的有用数据，不可删除。白色的对象是全部不可达对象，目前程序逻辑并不依赖他们，那么白色对象就是内存中目前的垃圾数据，需要被清除。
4.5 第五步
回收所有的白色标记表的对象，也就是回收垃圾，如图所示👇
将全部的白色对象进行删除回收，剩下的就是全部依赖的黑色对象。
这里面可能会有很多并发流程均会被扫描，执行并发流程的内存可能相互依赖，为了在 GC 过程中保证数据的安全，在开始三色标记之前就会加上 STW，在扫描确定黑白对象之后再放开 STW。但是很明显这样的 GC 扫描的性能实在是太低了。
所以现在的三色标记法还是会 STW。
5 没有STW的三色标记法
如果没有 STW，那么也就不会再存在性能上的问题，那么假设如果三色标记法不加入 STW 会发生什么事情❓
还是基于上述的三色标记法来分析，他是一定要依赖 STW 的，因为如果不暂停程序，程序的逻辑可能会改变对象的引用关系，这种动作如果在标记阶段做了修改，会影响标记结果的正确性。
来看看一个场景，如果三色标记法，标记过程不使用 STW 将会发生什么事情❓
我们把初始状态设置为已经经历了第一轮扫描，目前黑色的有对象 1 和对象 4，灰色的有对象 2 和对象 7，其他的为白色对象，且对象 2 是通过指针 p 指向对象 3 的，如下图所示。
现在如果三色标记过程不启动 STW，那么在 GC 扫描过程中，任意的对象均可能发生读写操作 ，如下图所示，在还没有扫描到对象 2 的时候，已经标记为黑色的对象 4，此时创建指针 q，并且指向白色的对象 3。
与此同时灰色的对象 2 将指针 p 移除，那么白色的对象 3 实则是被挂在了已经扫描完成的黑色的对象 4 下，如下图所示。
然后我们正常执行三色标记的算法逻辑，将所有灰色的对象标记为黑色，那么对象 2 和对象 7 就被标记成了黑色，如下图所示。
那么就执行了三色标记的最后一步，将所有白色对象当做垃圾进行回收，如图所示。
最后我们发现，本来是对象4合法引用的对象 3，却被GC给“误杀”回收掉了。
可以看出，有两种情况，在三色标记法中是不希望被发生的。
- 👉 一个白色对象被黑色对象引用 （白色被挂在黑色下）
- 👉 灰色对象与它之间可达关系的白色对象遭到破坏 （灰色同时丢了该白色）
如果当以上两个条件同时满足时，就会出现对象丢失现象！
并且，上面所示的场景中，如果示例中的白色对象3还有很多下游对象的话，也会一并都清理掉。
为了防止这种现象的发生，最简单的方式就是 STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响。
那么是否可以在保证对象不丢失的情况下合理的尽可能的提高 GC 效率，减少 STW 时间呢❓
答案是可以的，我们只要使用一种机制，尝试去破坏上面的两个必要条件就可以了。
6 屏障机制
如果让 GC 回收器，满足下面两种情况之一时，即可保证对象不丢失。这两种方式就是强三色不变式和弱三色不变式。
6.1 强三色不变式
强三色不变式实际上是强制性的不允许黑色对象引用白色对象，这样就不会出现有白色对象被误删的情况。
6.2 弱三色不变式
所有被黑色对象引用的白色对象都处于灰色保护状态。
弱三色不变式强调，黑色对象可以引用白色对象，但是这个白色对象必须存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。这样实则是黑色对象引用白色对象，白色对象处于一个危险被删除的状态，但是由于上游灰色对象的引用，可以保护该白色对象，使其安全。
为了遵循上述的两个方式，GC 算法演进到两种屏障方式，分别是插入屏障和删除屏障。
6.3 插入屏障
具体操作： 在 A 对象引用 B 对象的时候，B 对象被标记为灰色。将 B 挂在 A 下游，B 必须被标记为灰色。
满足：强三色不变式。不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色。
伪代码如下：
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(新下游对象ptr)
//2
当前下游对象slot = 新下游对象ptr
}场景：
A.添加下游对象(nil, B) //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B) //A 将下游对象C 更换为B， B被标记为灰色这段伪代码逻辑就是写屏障，但是这里有个性能损耗的地方就是每次添加好插入对象都要去判断。
黑色对象的内存槽有两种位置，栈和堆。 栈空间的特点是容量小，但是要求响应速度快，因为函数调用弹出频繁使用，所以插入屏障机制，在栈空间的对象操作中不使用，而仅仅使用在堆空间对象的操作中。
接下来，我们用几张图，来模拟一下整个详细的过程，希望能更可观的看清整体流程。
但是如果栈不添加，当全部三色标记扫描之后，栈上有可能依然存在白色对象被引用的情况（如上图的对象9）。所以要对栈重新进行三色标记扫描，但这次为了对象不丢失，要对本次标记扫描启动 STW 暂停，直到栈空间的三色标记结束。
最后将栈和堆空间扫描剩余的全部白色节点清除，这次 STW 大约的时间在 10~100ms 间。这也是插入写屏障的不足，因为还是需要 STW，虽然时间很短。
6.4 删除屏障
具体操作：被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足：弱三色不变式，保护灰色对象到白色对象的路径不会断。
伪代码：
添加下游对象(当前下游对象slot， 新下游对象ptr) {
//1
if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
标记灰色(当前下游对象slot) //slot为被删除对象， 标记为灰色
}
//2
当前下游对象slot = 新下游对象ptr
}场景：
A.添加下游对象(B, nil) //A对象，删除B对象的引用。 B被A删除，被标记为灰(如果B之前为白)
A.添加下游对象(B, C) //A对象，更换下游B变成C。 B被A删除，被标记为灰(如果B之前为白)接下来，我们用几张图，来模拟一个详细的过程，希望能够更可观的看清楚整体流程。
这种方式的不足是回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮 GC 中被清理掉。
7 混合写屏障
插入写屏障和删除写屏障的短板：
- 插入写屏障：结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活，大约需要 10-100ms。
- 删除写屏障：回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮 GC 中被清理掉。GC 开始时 STW 扫描堆栈来记录初始快照（监控对象的内存修改，判断对象是否删除），这个过程会保护开始时刻的所有存活对象。
Go v1.8 版本引入了混合写屏障机制，避免了对栈 re-scan 的过程，极大的减少了 STW 的时间，结合了两者的优点。
7.1 规则
具体操作：
- GC 开始将栈上的对象全部扫描并标记为黑色（之后不再进行第二次重复扫描，无需 STW ）。
- GC 期间，任何在栈上创建的新对象，均为黑色。
- 被删除的对象标记为灰色。
- 被添加的对象标记为灰色。
满足：变形的弱三色不变式。
伪代码：
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(当前下游对象slot) //只要当前下游对象被移走，就标记灰色
//2
标记灰色(新下游对象ptr)
//3
当前下游对象slot = 新下游对象ptr
}屏障技术是不在栈上应用的，因为要保证栈的运行效率。
7.2 具体场景
我们用几张图，来模拟一个详细的过程，希望能够更可观的看清楚整体流程。
混合写屏障是 GC 的一种屏障机制，所以只是当程序执行 GC 的时候，才会触发这种机制。
GC开始：优先扫描栈区，将可达对象全部标记为黑
7.2.1 场景一
对象被一个堆对象删除引用，成为栈对象的下游。
伪代码
//前提：堆对象4->对象7 = 对象7； //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7； //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
7.2.2 场景二
对象被一个栈对象删除引用，成为另一个栈对象的下游。
伪代码：
new 栈对象9；
对象8->对象3 = 对象3； //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null； //对象2 删除引用 对象3
7.2.3 场景三
对象被一个堆对象删除引用，成为另一个堆对象的下游。
伪代码：
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
7.2.4 场景四
对象从一个栈对象删除引用，成为另一个堆对象的下游。
伪代码：
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
Go 中的混合写屏障满足弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个 goroutine 的栈，使其变黑并一直保持，这个过程不需要 STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行 re-scan 操作了，减少了 STW 的时间。
8 总结
GoV1.3：普通标记清除法，整体过程需要启动 STW，效率极低。
GoV1.5：三色标记法，堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要 STW )，效率普通。
GoV1.8：三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。