本章节含视频版:

---

废物收回(Garbage Collection，简称GC)是编程言语中供给的主动的内存管理机制，主动释放不需求的内存目标，让出存储器资源。GC进程中无需程序员手动履行。GC机制在现代很多编程言语都支撑，GC才能的功能与好坏也是不同言语之间对比度指标之一。

Golang在GC的演进进程中也阅历了很多次革新，Go V1.3之前的符号-铲除(mark and sweep)算法，Go V1.3之前的符号-打扫(mark and sweep)的缺陷

• Go V1.5的三色并发符号法
• Go V1.5的三色符号为什么需求STW
• Go V1.5的三色符号为什么需求屏障机制(“强-弱” 三色不变式、刺进屏障、删去屏障 )
• Go V1.8混合写屏障机制
• Go V1.8混合写屏障机制的全场景分析

一、Go V1.3之前的符号-铲除(mark and sweep)算法

接下来咱们来看一下在Golang1.3之前的时分首要用的一般的符号-铲除算法，此算法首要有两个首要的进程：

• 符号(Mark phase)
• 铲除(Sweep phase)

1 符号铲除算法的具体进程

第一步，暂停程序事务逻辑, 分类出可达和不可达的目标，然后做上符号。

图中表明是程序与目标的可达联系，现在程序的可达目标有目标1-2-3，目标4-7等五个目标。

第二步, 开端符号，程序找出它一切可达的目标，并做上符号。如下图所示：

所以目标1-2-3、目标4-7等五个目标被做上符号。

第三步, 符号完了之后，然后开端铲除未符号的目标. 结果如下。

操作十分简略，可是有一点需求额外留意：mark and sweep算法在履行的时分，需求程序暂停！即 STW(stop the world)，STW的进程中，CPU不履行用户代码，悉数用于废物收回，这个进程的影响很大，所以STW也是一些收回机制最大的难题和期望优化的点。所以在履行第三步的这段时刻，程序会暂定中止任何作业，卡在那等待收回履行完毕。

第四步, 中止暂停，让程序继续跑。然后循环重复这个进程，直到process程序生命周期完毕。

以上便是符号-铲除（mark and sweep）收回的算法。

2 符号-铲除(mark and sweep)的缺陷

符号铲除算法明了，进程明显爽性，可是也有十分严重的问题。

• STW，stop the world；让程序暂停，程序呈现卡顿 (重要问题)；
• 符号需求扫描整个heap；
• 铲除数据会产生heap碎片。

Go V1.3版别之前便是以上来实施的, 在履行GC的基本流程便是首要发动STW暂停，然后履行符号，再履行数据收回，最终中止STW，如图所示。

从上图来看，悉数的GC时刻都是包裹在STW规模之内的，这样貌似程序暂停的时刻过长，影响程序的运转功能。所以Go V1.3 做了简略的优化,将STW的进程提早, 削减STW暂停的时刻规模.如下所示

上图首要是将STW的进程提早了异步，由于在Sweep铲除的时分，可以不需求STW中止，由于这些目标现已是不可达目标了，不会呈现收回写冲突等问题。

可是无论怎样优化，Go V1.3都面对这个一个重要问题，便是mark-and-sweep 算法会暂停整个程序 。

Go是怎么面对并这个问题的呢？接下来G V1.5版别 就用三色并发符号法来优化这个问题.

三、Go V1.5的三色并发符号法

Golang中的废物收回首要使用三色符号法，GC进程和其他用户goroutine可并发运转，但需求一定时刻的STW(stop the world)，所谓三色符号法实际上便是经过三个阶段的符号来确认清楚的目标都有哪些？咱们来看一下具体的进程。

第一步 , 每次新创立的目标，默认的色彩都是符号为“白色”，如图所示。

上图所示，咱们的程序可抵达的内存目标联系如左图所示，右边的符号表，是用来记载现在每个目标的符号色彩分类。这儿面需求留意的是，所谓“程序”，则是一些目标的跟节点调集。所以咱们假如将“程序”打开，会得到相似如下的表现形式，如图所示。

第二步, 每次GC收回开端, 会从根节点开端遍历一切目标，把遍历到的目标从白色调集放入“灰色”调集如图所示。

这儿 要留意的是，本次遍历是一次遍历，非递归形式，是从程序抽次可抵达的目标遍历一层，如上图所示，当时可抵达的目标是目标1和目标4，那么天然本轮遍历完毕，目标1和目标4就会被符号为灰色，灰色符号表就会多出这两个目标。

第三步, 遍历灰色调集，将灰色目标引证的目标从白色调集放入灰色调集，之后将此灰色目标放入黑色调集，如图所示。

这一次遍历是只扫描灰色目标，将灰色目标的第一层遍历可抵达的目标由白色变为灰色，如：目标2、目标7. 而之前的灰色目标1和目标4则会被符号为黑色，一起由灰色符号表移动到黑色符号表中。

第四步, 重复第三步, 直到灰色中无任何目标，如图所示。

当咱们悉数的可达目标都遍历完后，灰色符号表将不再存在灰色目标，现在悉数内存的数据只需两种色彩，黑色和白色。那么黑色目标便是咱们程序逻辑可达（需求的）目标，这些数据是现在支撑程序正常事务运转的，是合法的有用数据，不可删去，白色的目标是悉数不可达目标，现在程序逻辑并不依靠他们，那么白色目标便是内存中现在的废物数据，需求被铲除。

第五步: 收回一切的白色符号表的目标. 也便是收回废物，如图所示。

以上咱们将悉数的白色目标进行删去收回，剩下的便是悉数依靠的黑色目标。

以上便是三色并发符号法，不难看出，咱们上面现已清楚的体现三色的特性。可是这儿面或许会有很多并发流程均会被扫描，履行并发流程的内存或许相互依靠，为了在GC进程中确保数据的安全，咱们在开端三色符号之前就会加上STW，在扫描确认黑白目标之后再放开STW。可是很明显这样的GC扫描的功能实在是太低了。

那么Go是怎么解决符号-铲除(mark and sweep)算法中的卡顿(stw，stop the world)问题的呢？

四、没有STW的三色符号法

先抛砖引玉，咱们参加假如没有STW，那么也就不会再存在功能上的问题，那么接下来咱们假定假如三色符号法不参加STW会产生什么事情？
咱们还是根据上述的三色并发符号法来说, 他是一定要依靠STW的. 由于假如不暂停程序, 程序的逻辑改动目标引证联系, 这种动作假如在符号阶段做了修改，会影响符号结果的正确性，咱们来看看一个场景，假如三色符号法, 符号进程不运用STW将会产生什么事情?

咱们把初始状况设置为现已阅历了第一轮扫描，现在黑色的有目标1和目标4， 灰色的有目标2和目标7，其他的为白色目标，且目标2是经过指针p指向目标3的，如图所示。

现在怎么三色符号进程不发动STW，那么在GC扫描进程中，任意的目标均或许产生读写操作，如图所示，在还没有扫描到目标2的时分，现已符号为黑色的目标4，此时创立指针q，而且指向白色的目标3。

与此一起灰色的目标2将指针p移除，那么白色的目标3实则便是被挂在了现已扫描完成的黑色的目标4下，如图所示。

然后咱们正常指向三色符号的算法逻辑，将一切灰色的目标符号为黑色，那么目标2和目标7就被符号成了黑色，如图所示。

那么就履行了三色符号的最终一步，将一切白色目标作为废物进行收回，如图所示。

可是最终咱们才发现，本来是目标4合法引证的目标3，却被GC给“误杀”收回掉了。

可以看出，有两种状况，在三色符号法中，是不期望被产生的。

• 条件1: 一个白色目标被黑色目标引证(白色被挂在黑色下)
• 条件2: 灰色目标与它之间的可达联系的白色目标遭到损坏(灰色一起丢了该白色)

假如当以上两个条件一起满意时，就会呈现目标丢掉现象!

而且，如图所示的场景中，假如示例中的白色目标3还有很多下流目标的话, 也会一并都整理掉。

为了防止这种现象的产生，最简略的方法便是STW，直接制止掉其他用户程序对目标引证联系的干扰，可是STW的进程有明显的资源浪费，对一切的用户程序都有很大影响。那么是否可以在确保目标不丢掉的状况下合理的尽或许的进步GC功率，削减STW时刻呢？答案是可以的，咱们只需运用一种机制，尝试去损坏上面的两个必要条件就可以了。

五、屏障机制

咱们让GC收回器，满意下面两种状况之一时，即可保目标不丢掉。 这两种方法便是“强三色不变式”和“ 式”。

(1) “强-弱” 三色不变式

• 强三色不变式

不存在黑色目标引证到白色目标的指针。

弱三色不变色实际上是强制性的不允许黑色目标引证白色目标，这样就不会呈现有白色目标被误删的状况。

• 弱三色不变式

一切被黑色目标引证的白色目标都处于灰色维护状况。

弱三色不变式强调，黑色目标可以引证白色目标，可是这个白色目标有必要存在其他灰色目标对它的引证，或许可达它的链路上游存在灰色目标。 这样实则是黑色目标引证白色目标，白色目标处于一个风险被删去的状况，可是上游灰色目标的引证，可以维护该白色目标，使其安全。

为了遵循上述的两个方法，GC算法演进到两种屏障方法，他们“刺进屏障”, “删去屏障”。

(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开端将栈上的目标悉数扫描并符号为黑色(之后不再进行第2次重复扫描，无需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，功率较高。