Go垃圾回收原理

术语介绍

赋值器:说白了就是你写的程序代码，在程序的执行过程中，可能会改变对象的引用关系，或者创建新的引用。

回收器:垃圾回收器的责任就是去干掉那些程序中不再被引用得对象。

STW:全称是stop the word，GC期间某个阶段会停止所有的赋值器，中断你的程序逻辑，以确定引用关系。即STW停止程序运行。

root对象:根对象是指不需要通过其他对象就可以直接访问到的对象，通过root对象, 可以追踪到其他存活的对象。
常见的root对:

1. 全局变量：程序在编译期就能确定的那些存在于程序整个生命周期的变量（这些变量是可能引用堆上的对象或者是指针指向堆上的变量）。
2. 执行栈：每个 goroutine (包括main函数)都拥有自己的执行栈，这些执行栈上包含栈上的变量(这些变量本身就可能内存逃逸到堆上或者引用堆上的变量)及指向堆内存地址的指针变量。
3. 寄存器：寄存器的值可能是一个指针，而这个指针可能指向堆内存地址。

标记清除法(V1.3)

步骤

1. 开启STW，从根对象开始标记对象
2. 清除未被标记的对象，关闭STW
   

缺点

GC期间全程STW，GC和用户程序互相干扰，不能同时执行。

三色标记法

背景

基于标记清除算法的缺点，Golang团队对GC算法进行优化，减少STW以便GC和用户程序可以互不干扰，并发进行，于是就产生了三色标记法。

步骤

1. GC开始前，所有对象都，都被标记为白色
2. GC开始时，把所有根对象标记为灰色
3. GC进行时，遍历灰色对象，把灰色对象可达的对象标记为黑色，把自己标记为黑色
4. 重复第3步，直到标记完所有对象
5. GC结束时，回收白色对象

缺点

上述三色标记法仍然需要STW，因为我们的应用程序会改变对象的应用关系，从而影响标记结果的正确性。
比如：

1. 一个白色对象被灰色对象引用
2. 此时有一个黑色对象改变引用指向这个白色对象，而灰色对象到白色对象之间的引用关系又被破坏了
3. 此时这个白色对象只被一个黑色对象引用，这个白色对象不可能会标记了，因此该白色对象丢失

总结

其实总结来看，在三色标记法的过程中对象丢失，需要同时满足下面两个条件：

条件一：白色对象被黑色对象引用
条件二：灰色对象与白色对象之间的可达关系遭到破坏

看来只要把上面两个条件破坏掉一个，就可以保证对象不丢失。可以使用插入写屏障和删除写屏障来破坏上面其中一个条件。

插入写屏障

规则：当一个对象引用另外一个对象时，将另外一个对象标记为灰色。

解释：用来破坏条件一，单黑色对象引用白色对象是，白色对象就被标记成了灰色对象，就不可能出现条件一这种情况出现。

注意

插入屏障仅会在堆内存中生效，不对栈内存空间生效。这是因为go在并发运行时，大部分的操作都发生在栈上，函数调用会非常频繁。数十万goroutine的栈都进行屏障保护自然会有性能问题。

我要补充一下“生效”的具体意思：如果一个变量是在堆中如果它改变引用关系指向到另一个对象，我们把这个被指向的对象设置为灰色，如果一个变量在栈中，如果它改变引用关系指向到另一个对象，由于插入写屏障不生效，所以不用改变被引用的对象颜色为灰色

但是正是因为没有改变为灰色所以才要在GC结束时打开STW重新扫描栈如果栈和堆都使用插入写屏障，那就不用扫描重新扫描栈了，但是栈上打开STW效率太低了。

步骤

1. GC开始时，堆打开插入写屏障（栈不打开）
2. GC期间， 三色标记法进行标记
3. GC期间，堆中对象改变它的应用关系到另外一个对象，则把这个“另外对象”给标记为灰色
4. GC结束时，打开STW重新扫描栈中对象进行扫描标记
5. GC结束时，进行垃圾回收

缺点：GC结束时需要，打开STW重新扫描栈，保证引用的白色对象存活（主要保证的是堆中白色对象存活和栈中变量对逃逸到堆中的白色象，这些白色对象的产生是因为栈没开插入写屏障）。

删除写屏障

规则：在删除引用时，如果被删除引用的对象自身为灰色或者白色，那么被标记为灰色。

解释：用来破坏条件二，同过把被删除引用的对象设置为灰色，把这个被删除引用的对象自己当成可达的，那么相当于可达对象（被删除引用的这个对象）到白色对象（被删除引用的这个对象原本就能遍历/访问到的其他对象）之间的可达关系又重新建立起来来。这个被删除引用的对象和它能到达的一些对象都保护了起来，因此就破坏了条件二。

步骤

1. GC开始时，STW 扫描整个栈（所有协程的栈），保证所有堆上在用的对象都处于灰色保护下，保证的是弱三色不变式；
2. GC期间，三色标记
3. GC期间，某个对象原本引用对象A，后来改变引用到对象B，则把B对象设置为灰色
4. GC结束时，进行垃圾回收

缺点

1. 由于起始快照的原因，起始也是执行 STW，删除写屏障不适用于栈特别大的场景，栈越大，STW 扫描时间越长，对于现代服务器上的程序来说，栈地址空间都很大，所以删除写屏障都不适用，一般适用于很小的栈内存，比如嵌入式，物联网的一些程序；
2. 并且删除写屏障会导致扫描进度（波面）的后退，所以扫描精度不如插入写屏障；

注意

在上面的GC步骤1为什么要STW 扫描整个栈（所有协程的栈）？这个问题我说一点我个人的猜测吧，毕竟网上查了半天也没有一个人能说明白的（有朋友明白原因的麻烦告知一下）

首先在说删除写屏障之前时有一个大前提就是不能在栈中使用删除写屏障，只在堆中使用。

1. 当我们开启STW后把所有栈道对象都染为黑色，那么栈对象直接引用的所有堆对象都被染色成了灰色（如下图灰色部门）。
   

2. 因此所有的（不是垃圾的）堆对象都处于灰色的保护状态中（上图蓝色和绿色部分），换句话说就是，每个堆中的对象都至少被一个灰色对象直接或间接引用。

3. 当堆中的引用关系发生变化时，根据删除写屏障把被改变引用的那个堆对象变成灰色，就能一定破坏“条件二了”

我们举个反向例子，初始状态，有2个协程栈：

A 是 g1 栈的一个对象，g1栈已经扫描完了，并且 C 也是扫黑了的对象
B 是 g2 栈的对象，指向了 C 和 D，g2 完全还没扫描，B 是一个灰色对象，D 是白色对象

步骤一：g2 进行赋值变更，把 C 指向 D 对象，这个时候黑色的 C 就指向了白色的 D（由于是删除屏障，这里是不会把D染色为灰色）
步骤二：把 B 指向 D 的引用删除，由于是栈对象操作，不会触发删除写屏障(这里我们讨论的大前提是对栈是不使用删除写屏障的，即使把B到D引用关系删除了也不会把D染成灰色)；

步骤三：GC结束时，因为 C 已经是黑色对象了，所以不会再扫描，所以 D 仍然为白色，就会被错误的清理掉。

总结

那么如果我不想一次把所有的协程栈都暂停，就会产生上面例子中的问题，有什么办法可以解决上面的例子中的问题吗（在不同时暂停所有协程栈道情况下）？这个当然是有的。

解决办法就是：使用三色标记法+插入写屏障+删除写屏障

需要注意：混合写屏障扫描栈虽然没有 STW，但是扫描某一个具体的栈的时候，还是要停止这个 goroutine 赋值器的工作的哈（针对一个 goroutine 栈来说，是暂停扫的，要么全灰，要么全黑哈，原子状态切换）

我们根据上面的这幅图可以看出只要我们在目前的GC策略上再添加上插入写屏障（当前的GC策略是三色标记法+删除写屏障），在C引用D时直接把D染为灰色，就能解决所有问题了。

三色标记法+插入写屏障(V1.5)

插入写屏障机制和删除写屏障机制中任一机制均可保护对象不被丢失。在V1.5的版本中采用的是插入写机制实现。

三色标记法+混合写屏障(V1.8)

背景

从上面的分析中，我可以知道：
插入写屏障，可以做用户程序和GC同时运行，什么都好就是要在GC结束时重新扫描栈中的根对象防止堆中的变量被释放
删除写屏障，也可以做用户程序和GC同时运行，但是需要在GC开始前把所有的协程栈暂停，这对协程数量非常多的时候是不可接受的。

那么有没有一种方法，在GC开始的时候不需要STW 扫描整个栈（把整个栈中的对象标记为黑色），在程序结束时不需要再次重新扫描栈以防止对象丢失，并且GC程序可以和用户程序同时运行？

这种方法就是我们的三色标记法+混合写屏障了

步骤

1. GC开始时优先扫描将栈，将栈上可达对象标记为黑色。扫描某个 goroutine 时停止这个 goroutine 赋值器的工作。即goroutine看来是原子操作，瞬间全灰/黑。栈扫描完成后解锁。
2. GC期间栈上新建的对象都为黑色
3. 堆上被删除的对象标记为灰色
4. 堆上新添加的对象标记为灰色

注意：写屏障（插入、删除写屏障）只在堆上启用，栈上不开启写屏障

优点

1. 不用在开始时像删除写屏障那样，需要同时STW所有协程来标记根栈上的根对象
2. 不用在结束时像插入写屏障那样，需要再次打开STW重新扫描栈，保证引用的白色对象存活