Golang的垃圾回收与三色标记法
关键词: 垃圾回收 内存管理 自动释放 三色标记 STW
一 STW
STW就是Stop the world的缩写或者Start the world的缩写。指从stop到start这两个动作直接的时间间隔，即万物都静止。
STW在垃圾回收过程中保证了实现的正确性、防止了在垃圾回收过程中内存的无限增长等问题，从而停止赋值器对操作对象图的操作过程。
STW的时间会影响系统的性能，在这个过程中，用户的代码被停止运行和放缓运行。STW越长，对用户代码造成的影响越大（延迟）。
在Go1.14之前，没有异步抢占。for {} 这样的goroutine进不去STW阶段，就会造成卡机等现象。Go 1.14 之后，这类 goroutine 能够被异步地抢占，从而使得进入 STW 的时间不会超过抢占信号触发的周期，程序也不会因为仅仅等待一个 goroutine 的停止而停顿在进入 STW 之前的操作上。
二 标记-清除(-Go1.3)
标记(Mark phase)
- 暂停程序的业务逻辑；
- 从程序根节点开始遍历所有对象，并标记可达对象；
清除(Sweep phase)
- 清理未被标记的可达对象
- 停止暂停，使程序继续运行；不断循环此过程，直到进程结束；
过程
在1.3版本进行优化，将停止STW时间与Sweep清除进行交换；
标记清除的缺点
- 需要STW进行程序暂停，严重的影响程序的性能；
- 在进行标记时，需要扫描整个程序的栈和堆区；
- 在清理数据的时候会产生堆碎片；
三 三色标记法-插入写屏障/删除写屏障(Go1.5)
三色阶段
对象的三色抽象与波面(wavefront)推进，三色抽象式描述追踪式回收器的方法；波面，即黑色对象与白色对象的边界，灰色对象就是波面；可以理解为灰色对象就是在每次进行更新对象颜色的中间过程；
三色标记的处理流程
垃圾回收开始时，将程序所有对象，包括新创建的对象，全部标记为白色，并将白色对象放入到白色标记表集合中；
从根节点开始，遍历所有对象，将可达的对象，从白色集合放入到灰色集合中，并将该可达对象颜色置为灰色；
遍历灰色对象集合，将灰色对象引用的白色对象从白色集合放到灰色集合中，并将并将这些白色对象置为灰色，同时将遍历过的灰色对象放到黑色对象集合中，将这些灰色对象置为黑色；
重复步骤3，直到灰色对象集合为空；
回收白色标记表中的白色对象，该对象均不可达；
无STW三色标记出现的问题
问题解决
屏障
基于上面两种方式，得到了两种屏障机制：
并发插入写屏障
插入写屏障
在进行对象引用时，被引用的对象被标记为灰色；
满足
强三色不变式（不存在黑色对象引用白色对象，被引用的白色对象变为灰色对象）
发生区域
发送在堆区，只在堆空间对象使用该屏障机制，在栈空间的对象操作中不使用（栈内存区容量小，并且要求调用速度快，函数调用时频繁弹出使用）；
存在短暂STW
由于屏障只发生在堆区，如果存在栈区的对象引用，则会丢失，因此在三色标记扫描结束后，会对栈区重新进行三色标记扫描，启动暂时的STW，直到栈空间三色标记结束；
案例分析
程序在开始进行GC时，先将所有的对象全部标记为白色，并将白色对象放到白色标记集合中；
从根节点开始，遍历从根节点的可达对象，并将可达节点从白色集合移动到灰色集合 ，并将对象置为灰色;
紧接着从灰色标记集合中继续遍历可达对象，并将灰色集合中的对象放入到黑色集合，同时将这些灰色对象的可达节点对象，标志为灰色，从白色标记集合中移动到灰色集合；
在此同时，由于程序的并发，代码中对堆区的对象4添加对象8、给栈区的对象1添加了对象9的引用，由于插入写屏障只发生在堆区，所以，直接将对象8标记为灰色，对象9不做任何处理；
继续重复步骤3，直到灰色标记集合为空；
由于在栈区添加了对象引用，并且插入屏障不会起作用，所以对栈区启动短暂的STW，重新对栈区的全部对象，进行三色标记，从而保证了新添加的对象不丢弃；
在STW中，将栈中的对象进行一次三色标记，直到没有灰色对象；
最后将堆区与栈区的白色对象全部清除；
并发删除写屏障
删除写屏障
删除写屏障，判断的就是在删除对象时，不管是白色对象还是灰色对象，都将其置为灰色；
满足
弱三色不变性，保护了灰色对象到白色对象的路径不会断；
弊端
被删除的对象，在本次GC过程中，还是不会被清理，只有在下一轮GC才会被删除；这样的方式是一种低回收精度；
四 混合写屏障机制(Go1.8)
概述
混合写屏障，综合了1.5GC方式中插入写屏障和删除写屏障的短板:
插入写屏障: 只发生在堆区，对栈区的对象还有短暂的STW，完成对白色对象的清理；
删除写屏障: 回收精度低,GC开始时STW扫描对栈区记录初始快照，这个过程会保护开始时刻存活的对象；
混合写屏障，避免了对栈区的扫描与STW，极大了节省了STW的时间；
混合写屏障规则
GC开始时，直接将栈上的对象全部置为黑色（不需要进行第二次重复扫描，减少STW时间）
在GC期间，由于并发特性，任何在栈上产生的对象，全部置为黑色；
被删除的对象，全部置为灰色；
被添加的对象，全部置为灰色；
注意: 为了保证运行效率，所有的屏障技术都不在栈上使用
混合写屏障案例分析
五 总结
GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低。
GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通。
GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。
六 观察GC的四种方式
1 | 本文参考: |
