Golang 三色标记 + 混合写屏障 GC 模式全分析
视频版:
垃圾回收(Garbage Collection，简称 GC)是编程语言中提供的自动的内存管理机制，自动释放不需要的对象，让出存储器资源，无需程序员手动执行。
Golang 中的垃圾回收主要应用三色标记法，GC 过程和其他用户 goroutine 可并发运行，但需要一定时间的 STW(stop the world) ，STW 的过程中，CPU 不执行用户代码，全部用于垃圾回收，这个过程的影响很大，Golang 进行了多次的迭代优化来解决这个问题。
一、Go V1.3 之前的标记-清除(mark and sweep)算法
此算法主要有两个主要的步骤：
- 标记(Mark phase)
- 清除(Sweep phase)
第一步 ，暂停程序业务逻辑, 找出不可达的对象，然后做上标记。第二步，回收标记好的对象。
操作非常简单，但是有一点需要额外注意：mark and sweep 算法在执行的时候，需要程序暂停！即 STW(stop the world)。也就是说，这段时间程序会卡在哪儿。 
第二步 , 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示： 
第三步 , 标记完了之后，然后开始清除未标记的对象. 结果如下. 
第四步 , 停止暂停，让程序继续跑。然后循环重复这个过程，直到 process 程序生命周期结束。
二、标记-清扫(mark and sweep)的缺点
- STW，stop the world；让程序暂停，程序出现卡顿(重要问题) 。
- 标记需要扫描整个 heap
- 清除数据会产生 heap 碎片
所以 Go V1.3 版本之前就是以上来实施的, 流程是
Go V1.3 做了简单的优化,将 STW 提前, 减少 STW 暂停的时间范围.如下所示
这里面最重要的问题就是：mark-and-sweep 算法会暂停整个程序 。
Go 是如何面对并这个问题的呢？接下来 G V1.5 版本 就用三色并发标记法 来优化这个问题.
三、Go V1.5 的三色并发标记法
三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些. 我们来看一下具体的过程.
第一步 , 就是只要是新创建的对象,默认的颜色都是标记为“白色”.
这里面需要注意的是, 所谓“程序”, 则是一些对象的跟节点集合. 
所以上图,可以转换如下的方式来表示.
第二步 , 每次 GC 回收开始, 然后从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合。
第三步 , 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合
第四步 , 重复第三步 , 直到灰色中无任何对象. 
第五步 : 回收所有的白色标记表的对象. 也就是回收垃圾. 
以上便是 三色并发标记法, 不难看出,我们上面已经清楚的体现 三色 的特性, 那么又是如何实现并行的呢?
Go 是如何解决标记-清除(mark and sweep)算法中的卡顿(stw，stop the world)问题的呢？
四、没有 STW 的三色标记法
我们还是基于上述的三色并发标记法来说, 他是一定要依赖 STW 的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。我们举一个场景.
如果三色标记法, 标记过程不使用 STW 将会发生什么事情?
可以看出，有两个问题, 在三色标记法中,是不希望被发生的
- 条件 1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件 2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
当以上两个条件同时满足时, 就会出现对象丢失现象!
当然, 如果上述中的白色对象 3, 如果他还有很多下游对象的话, 也会一并都清理掉.
为了防止这种现象的发生，最简单的方式就是 STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是 STW 的过程有明显的资源浪费，对所有的用户程序都有很大影响 ，如何能在保证对象不丢失的情况下合理的尽可能的提高 GC 效率，减少 STW 时间呢？
答案就是, 那么我们只要使用一个机制,来破坏上面的两个条件就可以了.
五、屏障机制
我们让 GC 回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式.
(1) “强-弱” 三色不变式
- 强三色不变式
不存在黑色对象引用到白色对象的指针。
- 弱三色不变式
所有被黑色对象引用的白色对象都处于灰色保护状态.
为了遵循上述的两个方式,Golang 团队初步得到了如下具体的两种屏障方式“插入屏障”, “删除屏障”.
(2) 插入屏障
具体操作: 在 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 间.
(3) 删除屏障
具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足: 弱三色不变式 . (保护灰色对象到白色对象的路径不会断)
伪代码：
添加下游对象(当前下游对象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 中被清理掉。
六、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、被添加的对象标记为灰色。
满足: 变形的弱三色不变式 .
伪代码：
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(当前下游对象slot) //只要当前下游对象被移走，就标记灰色
//2
标记灰色(新下游对象ptr)
//3
当前下游对象slot = 新下游对象ptr
}
这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。
(2) 混合写屏障的具体场景分析
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
注意混合写屏障是 Gc 的一种屏障机制，所以只是当程序执行 GC 的时候，才会触发这种机制。
GC 开始：扫描栈区，将可达对象全部标记为黑
场景一： 对象被一个堆对象删除引用，成为栈对象的下游
伪代码
//前提：堆对象4->对象7 = 对象7； //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7； //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游
伪代码
new 栈对象9；
对象8->对象3 = 对象3； //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null； //对象2 删除引用 对象3
场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
Golang 中的混合写屏障满足 弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个 goroutine 的栈，使其变黑并一直保持，这个过程不需要 STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行 re-scan 操作了，减少了 STW 的时间。
七、总结
以上便是 Golang 的 GC 全部的标记-清除逻辑及场景演示全过程。
GoV1.3- 普通标记清除法，整体过程需要启动 STW，效率极低。
GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要 STW)，效率普通
GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要 STW，效率较高。
Golang