一.Golang 垃圾回收
回收算法：三色标记+混合写屏障
1.回收算法演变
Golang中的垃圾回收主要应用三色标记法，GC过程和其他用户goroutine可并发运行，但需要一定时间的**STW(stop the world)**，STW的过程中，CPU不执行用户代码，全部用于垃圾回收，这个过程的影响很大，Golang进行了多次的迭代优化来解决这个问题
(1).Go V1.3之前的标记-清除(mark and sweep)算法
缺点： STW，stop the world；让程序暂停，程序出现卡顿 (重要问题)。
标记需要扫描整个heap
清除数据会产生heap碎片
(2).Go V1.5的三色并发标记法
缺点： 以下两个条件同时满足时, 就会出现对象丢失现象
- 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
---->屏障机制(插入写屏障,删除写屏障)
屏障机制问题：
- 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
- 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
(3).Go V1.8的混合写屏障(hybrid write barrier)机制
2.Go V1.3之前的标记-清除(mark and sweep)算法
此算法主要有两个主要的步骤：
- 标记(Mark phase)
- 清除(Sweep phase)
第一步，暂停程序业务逻辑, 找出不可达的对象，然后做上标记。第二步，回收标记好的对象。
操作非常简单，但是有一点需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即 STW(stop the world)。也就是说，这段时间程序会卡在哪儿。
第二步, 开始标记，程序找出它所有可达的对象，并做上标记。
第三步, 标记完了之后，然后开始清除未标记的对象.
第四步, 停止暂停，让程序继续跑。然后循环重复这个过程，直到process程序生命周期结束。
3.Go V1.5的三色并发标记法
(1).原理
首先看一张图，大概就会对 三色标记法 有一个大致的了解：
- 首先把所有的对象都放到白色的集合中
- 从根节点开始遍历对象，遍历到的白色对象从白色集合中放到灰色集合中
- 遍历灰色集合中的对象，把灰色对象引用的白色集合的对象放入到灰色集合中，同时把遍历过的灰色集合中的对象放到黑色的集合中
- 循环步骤3，知道灰色集合中没有对象
- 步骤4结束后，白色集合中的对象就是不可达对象，也就是垃圾，进行回收
(2).问题
上述的三色并发标记法一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。
有两个问题, 在三色标记法中,是不希望被发生的
- 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
当以上两个条件同时满足时, 就会出现对象丢失现象!
(3).解决思路
为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是**STW的过程有明显的资源浪费，对所有的用户程序都有很大影响**，如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？
答案就是, 使用一个机制,来破坏上面的两个条件.
(4).屏障机制
让GC回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式.
1) “强-弱” 三色不变式
- 强三色不变式
不存在黑色对象引用到白色对象的指针。
强三色不变色实际上是强制性的不允许黑色对象引用白色对象，这样就不会出现有白色对象被误删的情况。
- 弱三色不变式
所有被黑色对象引用的白色对象都处于灰色保护状态。
弱三色不变式强调，黑色对象可以引用白色对象，但是这个白色对象必须存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。 这样实则是黑色对象引用白色对象，白色对象处于一个危险被删除的状态，但是上游灰色对象的引用，可以保护该白色对象，使其安全。
为了遵循上述的两个方式，GC 算法演进到两种屏障方式，他们 “插入屏障”, “删除屏障”。
2).插入屏障
具体操作: 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)
满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)
栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中.
如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况. 所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束.最后将栈和堆空间 扫描剩余的全部 白色节点清除. 这次STW大约的时间10~100ms间.
3).删除屏障
具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)
这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。
4.Go V1.8的混合写屏障(hybrid write barrier)机制
插入写屏障和删除写屏障的短板：
- 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
- 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。
(1).混合写屏障规则
具体操作:
1、GC开始将栈上的对象全部扫描并将可达对象全部标记为黑色(之后不再进行第二次重复扫描，无需STW)，
2、GC期间，任何在栈上创建的新对象，均为黑色。
3、被删除的对象标记为灰色。
4、被添加的对象标记为灰色。
满足: 变形的弱三色不变式.
这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。
(2).混合写屏障的具体场景分析
注意:混合写屏障是Gc的一种屏障机制，所以只是当程序执行GC的时候，才会触发这种机制。
场景一： 对象被一个堆对象删除引用，成为栈对象的下游
场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游
场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游
场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游
Golang中的混合写屏障满足`弱三色不变式`，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间。
5.注意
三色标记是触发GC才开始进行扫描标记，不是在对象创建时同步进行；
Go GC清理不可达对象时，并没有stw,且不会产生误删的情况；
6.总结
GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低。
GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通
GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。
参考：
https://zhuanlan.zhihu.com/p/334999060
Golang 垃圾回收原理分析