封面《pieces/渡り鳥のソムニウム》
GO V1.3 标记-清除算法
此算法主要有两个主要的步骤：
- 标记(Mark phase)
- 清除(Sweep phase)
- STW(stop the world), 找出不可达的对象，然后做上标记。
- 开始标记，程序找出它所有可达的对象，并做上标记。
- 标记完了之后，然后开始清除未标记的对象。
- 停止暂停，让程序继续跑。然后循环重复这个过程，直到process程序生命周期结束。
所以Go V1.3版本之前就是以上来实施的,在执行GC的基本流程就是首先启动STW暂停，然后执行标记，再执行数据回收，最后停止STW
Go V1.3 做了简单的优化,将STW提前, 减少STW暂停的时间范围。将STW的步骤提前了一步，因为在Sweep清除的时候，可以不需要STW停止，因为这些对象已经是不可达对象了，不会出现回收写冲突等问题。
缺点：
- STW，stop the world；让程序暂停，程序出现卡顿(重要问题)
- 标记需要扫描整个heap
- 清除数据会产生heap碎片
无论如何mark-sweep都会暂停整个程序，为了解决这个问题在GOv1.5版本引入了三色并发标记法来优化
GO v1.5 三色标记法
Golang中的垃圾回收主要应用三色标记法，GC过程和其他用户goroutine可并发运行，但需要一定时间的STW(stop the world)
定义
- 黑色：检测到有被引用，并且已经遍历完它所有直接引用的对象或者属性
- 白色：还没检测到有引用的对象（检测开始前，所有对象都是白色，检测结束后，没有被引用的对象都是白色，会被清查掉）
- 灰色：检测到有被引用，但是他的属性还没有被遍历完，等遍历完后也会变成黑色
如果不使用STW，这种方式会造成标记不准确的问题，下面两种情况是不希望发生的
- 一个白色对象被黑色对象引用
- 白色对象又被某个灰色（或者上级有灰色对象）对象取消引用。
为了防止上面的现象发生，最简单的方式就是使用STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响。因此Go的方法是使用插入屏障和删除屏障
屏障机制
”强-弱“三色不等式
- 强三色不等式
不存在黑色对象引用到白色对象的指针
强三色不变色实际上是强制性的不允许黑色对象引用白色对象，这样就不会出现有白色对象被误删的情况
- 弱三色不等式
所有被黑色对象引用的白色对象都处于灰色保护状态
弱三色不变式强调，黑色对象可以引用白色对象，但是这个白色对象必须存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。
插入屏障
具体操作： 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)
满足： 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)
色对象的内存槽有两种位置, 栈和堆. 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中
对于栈的部分使用STW保护
删除屏障
具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)
这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。
GO v1.8 混合写屏障(hybrid write barrier)机制
插入写屏障和删除写屏障的缺点
- 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
- 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。
混合写屏障
具体操作：
- GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，
- GC期间，任何在栈上创建的新对象，均为黑色。
- 被删除的对象标记为灰色。
- 被添加的对象标记为灰色。
需要注意屏障技术是不在栈上应用的，因为要保证栈的运行效率
混合写屏障是GC的一种屏障机制，所以只是当程序执行GC的时候，才会触发这种机制。
Golang中的混合写屏障满足弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间
总结
GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低。
GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通
GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。