go-三色标记算法

三色标记算法

在golang1.5之前，golang主要采用标记清除的方法，这样的话STW时间会很长，1.5之后采用三色标级法。
GC算法STW时间过长对于网络高并发的服务场景是一种致命缺陷，在标记清除的基础上发展起来的三色标记出现了。三色标记算法是一种基于增量思想的GC算法。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程交替执行。依次反复，直到垃圾完成。

三色标记流程

第一步：每次新创建的对象，默认的颜色都是标记为“白色”。
第二步：每次GC回收开始，会从Root Set中的根节点开始遍历所有对象（只遍历一层），把遍历到的对象从「白色集合」放入「灰色集合」。
第三步：遍历「灰色集合」，将灰色对象引用的对象从「白色集合」放入「灰色集合」，之后将此灰色对象放入「黑色集合」。
第四步：重复第三步，知道「灰色集合」中没有任何对象。
第五步：回收所有的白色对象，也就是回收垃圾。
本质上，三色标记过程就是GC Root Set的多源BFS。

没有STW的后果

没有STW的话，在GC扫描的过程中，任意的对象均可能发生读写操作。

经过第一轮灰色对象扫描后，此时对象2通过指针p指向对象5，状态如下所示：

同时应用程序将指针p移除，对象3创建指针q指向对象5，状态如下所示：

这个时候，对象5已经没有被任何灰色对象引用，在GC结束之后，依然是白色，会被回收掉，这显然是非期望结果。

强弱三色不变式

三色标记最不希望发生的事：

一个白色对象被黑色对象引用（白色被挂在黑色下）；
灰色对象与该白色对象的可达关系遭到破坏（灰色同时丢了该白色）。

强三色不变式：强制性的不允许黑色对象引用白色对象。
弱三色不变式：黑色对象可以引用白色对象，白色对象存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。

在三色标记中如果满足强/弱之一，即可保证对象不丢失。

屏障机制

插入屏障：对象被引用时触发的机制，不在栈上使用
具体操作：在A对象引用B对象，B对象被标记为灰色。（将B挂在A下游，B必须被标记为灰色）。
满足：强三色不变式，不存在黑色对象引用白色对象的情况，因为白色会强制变成灰色。
场景：

A添加下游对象：A之前没有下游，新添加一个下游对象B，B被标记为灰色；
A更换下游对象：A将下游对象C更换为B，B被标记为灰色。

在栈空间中，准备回收白色前，重新遍历扫描一次栈空间。此时加STW暂停保护栈，防止外界干扰（有新的白色被黑色添加），大约需要10~100ms。

删除屏障：对象被删除时触发的机制
具体操作：被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足：弱三色不变式，保护灰色对象到白色对象的路径不会断。

一个对象即使被删除了最后一个指向它的指针，也依旧可以活过这一轮，在下一轮GC中被清理掉。

混合写屏障

具体操作：

GC开始将栈上的对象全部扫描并标记为黑色；
GC期间，任何在栈上创建的新对象均为黑色；
被删除的对象标记为灰色；
被添加的对象标记为灰色。

满足：变形的弱三色不变式。

添加下游对象(当前下游对象slot, 新下游对象ptr) {
	// 1
	标记灰色(当前下游对象slot);
	// 2
	标记灰色(新下游对象ptr);
	// 3
	当前下游对象slot = 新下游对象ptr;
}

（1）场景1：对象被一个堆对象删除引用，成为栈对象的下游

1
2
3

// 前提：堆对象4 -> 对象7 = 对象7; // 对象7 被 对象4 引用
栈对象1 -> 对象7 = 堆对象7;        // 1. 将 堆对象7 挂在 栈对象1 下游
堆对象4 -> 对象7 = null;           // 2. 对象4 删除 对象7 的引用

第1步，将对象7添加到对象1下游，因为栈不启动写屏障，所以直接挂在下面；
第2步，因为对象4在堆区，所以触发写屏障，标记被删除对象7为灰色。
（2）场景2：对象被一个栈对象删除引用，成为另一个栈对象的下游

1
2
3

new 栈对象9
栈对象9 -> 对象3 = 对象3; // 1. 将栈对象3 挂在 栈对象9 下游
栈对象2 -> 对象3 = null;  // 2. 对象2 删除 对象3 的引用

在混合写屏障中，GC过程中任何新创建的对象均标记为黑色，即对象9为黑色。
第1步，对象9添加下游引用对象3，因为栈不启动屏障，直接添加；
第2步，对象2删除对象3的引用关系，因为栈不启动屏障，直接删除。
（3）场景3：对象被一个堆对象删除引用，成为另一个堆对象的下游

1 2	堆对象10 -> 对象7 = 堆对象7; // 1. 将堆对象7 挂在堆对象10 下游堆对象4 -> 对象7 = null; // 2. 对象4 删除对象7 的引用

考虑比较特殊的情况，堆对象10已经扫描标记为黑色。
第1步，对象10添加下游引用对象7，触发屏障机制，被添加的对象7标记为灰色；
第2步，对象4删除对象7的引用关系，触发屏障机制，被删除的对象7标记为灰色。
（4）场景4：对象从一个栈对象删除引用，称为另一个堆对象的下游

1
2
3

栈对象1 -> 对象2 = null;   // 1. 对象1 删除 对象2 的引用
堆对象4 -> 对象7 = null;   // 2. 对象4 删除 对象7 的引用
堆对象4 -> 对象2 = 栈对象2; // 3. 将栈对象2 挂在 堆对象4 下游

第1步，栈对象1删除对栈对象2的引用；
第2步，堆对象4在删除对象7的时候，触发屏障机制，被删除的对象7被标记为灰色；
第3步，堆对象4将之前的对对象7的引用关系转移至栈对象2。