垃圾回收 (Garbage Collection，简称 GC) 是编程语言中提供的自动的内存管理机制，自动释放不需要的内存对象，让出存储器资源。GC 过程中无需程序员手动执行。GC 机制在现代很多编程语言都支持，GC 能力的性能与优劣也是不同语言之间对比度指标之一。

Golang 在 GC 的演进过程中也经历了很多次变革，Go V1.3 之前的标记 - 清除 (mark and sweep) 算法，Go V1.3 之前的标记 - 清扫 (mark and sweep) 的缺点

<!--more-->

- 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. 暂停程序业务逻辑，分类出可达和不可达的对象，然后做上标记。

   ![image-20220117210535275](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117210535275.png)

   图中表示是程序与对象的可达关系，目前程序的可达对象有对象 1-2-3，对象 4-7 等五个对象。

2. 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示：

   ![image-20220117210645781](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117210645781.png)

   所以对象 1-2-3、对象 4-7 等五个对象被做上标记。

3. 标记完了之后，然后开始清除未标记的对象。结果如下。

   ![image-20220117210728045](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117210728045.png)

   操作非常简单，但是有一点需要额外注意：mark and sweep 算法在执行的时候，需要程序暂停！即 `STW(stop the world)`，STW 的过程中，CPU 不执行用户代码，全部用于垃圾回收，这个过程的影响很大，所以 STW 也是一些回收机制最大的难题和希望优化的点。所以在执行第三步的这段时间，程序会暂定停止任何工作，卡在那等待回收执行完毕。

4. 停止暂停，让程序继续跑。然后循环重复这个过程，直到 process 程序生命周期结束。

以上便是标记 - 清除（mark and sweep）回收的算法。

### 标记 - 清除 (mark and sweep) 的缺点

标记清除算法明了，过程鲜明干脆，但是也有非常严重的问题。

- STW，stop the world；让程序暂停，程序出现卡顿 **(重要问题)**；
- 标记需要扫描整个 heap；
- 清除数据会产生 heap 碎片。

Go V1.3 版本之前就是以上来实施的，在执行 GC 的基本流程就是首先启动 STW 暂停，然后执行标记，再执行数据回收，最后停止 STW，如图所示。

![image-20220117211240034](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117211240034.png)

从上图来看，全部的 GC 时间都是包裹在 STW 范围之内的，这样貌似程序暂停的时间过长，影响程序的运行性能。所以 Go V1.3 做了简单的优化，将 STW 的步骤提前，减少 STW 暂停的时间范围。如下所示

![image-20220117211306851](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117211306851.png)

上图主要是将 STW 的步骤提前了异步，因为在 Sweep 清除的时候，可以不需要 STW 停止，因为这些对象已经是不可达对象了，不会出现回收写冲突等问题。

但是无论怎么优化，Go V1.3 都面临这个一个重要问题，就是**mark-and-sweep 算法会暂停整个程序** 。

Go 是如何面对并这个问题的呢？接下来 G V1.5 版本 就用**三色并发标记法**来优化这个问题。

## Go V1.5 的三色并发标记法

Golang 中的垃圾回收主要应用三色标记法，GC 过程和其他用户 goroutine 可并发运行，但需要一定时间的**STW(stop the world)**，所谓**三色标记法**实际上就是通过三个阶段的标记来确定清楚的对象都有哪些？我们来看一下具体的过程。

1. 每次新创建的对象，默认的颜色都是标记为“白色”，如图所示。

   ![image-20220117212242391](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212242391.png)

   上图所示，我们的程序可抵达的内存对象关系如左图所示，右边的标记表，是用来记录目前每个对象的标记颜色分类。这里面需要注意的是，所谓“程序”，则是一些对象的跟节点集合。所以我们如果将“程序”展开，会得到类似如下的表现形式，如图所示。

   ![image-20220117212341484](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212341484.png)

2. 每次 GC 回收开始，会从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合如图所示。

   ![image-20220117212436917](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212436917.png)

   这里 要注意的是，本次遍历是一次遍历，非递归形式，是从程序抽次可抵达的对象遍历一层，如上图所示，当前可抵达的对象是对象 1 和对象 4，那么自然本轮遍历结束，对象 1 和对象 4 就会被标记为灰色，灰色标记表就会多出这两个对象。

3. 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合，如图所示。

   ![image-20220117212542924](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212542924.png)

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

4. 重复**第三步**, 直到灰色中无任何对象，如图所示。

   ![image-20220117212625146](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212625146.png)

   ![image-20220117212646795](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212646795.png)

   当我们全部的可达对象都遍历完后，灰色标记表将不再存在灰色对象，目前全部内存的数据只有两种颜色，黑色和白色。那么黑色对象就是我们程序逻辑可达（需要的）对象，这些数据是目前支撑程序正常业务运行的，是合法的有用数据，不可删除，白色的对象是全部不可达对象，目前程序逻辑并不依赖他们，那么白色对象就是内存中目前的垃圾数据，需要被清除。

5. 回收所有的白色标记表的对象。也就是回收垃圾，如图所示。

   ![image-20220117212728177](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117212728177.png)

   以上我们将全部的白色对象进行删除回收，剩下的就是全部依赖的黑色对象。

   以上便是`三色并发标记法`，不难看出，我们上面已经清楚的体现`三色`的特性。但是这里面可能会有很多并发流程均会被扫描，执行并发流程的内存可能相互依赖，为了在 GC 过程中保证数据的安全，我们在开始三色标记之前就会加上 STW，在扫描确定黑白对象之后再放开 STW。但是很明显这样的 GC 扫描的性能实在是太低了。

   那么 Go 是如何解决标记 - 清除 (mark and sweep) 算法中的卡顿 (stw，stop the world) 问题的呢？

## 没有 STW 的三色标记法

先抛砖引玉，我们加入如果没有 STW，那么也就不会再存在性能上的问题，那么接下来我们假设如果三色标记法不加入 STW 会发生什么事情？
我们还是基于上述的三色并发标记法来说，他是一定要依赖 STW 的。因为如果不暂停程序，程序的逻辑改变对象引用关系，这种动作如果在标记阶段做了修改，会影响标记结果的正确性，我们来看看一个场景，如果三色标记法，标记过程不使用 STW 将会发生什么事情？

我们把初始状态设置为已经经历了第一轮扫描，目前黑色的有对象 1 和对象 4，灰色的有对象 2 和对象 7，其他的为白色对象，且对象 2 是通过指针 p 指向对象 3 的，如图所示。

![image-20220117223500168](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117223500168.png)

现在如何三色标记过程不启动 STW，那么在 GC 扫描过程中，任意的对象均可能发生读写操作，如图所示，在还没有扫描到对象 2 的时候，已经标记为黑色的对象 4，此时创建指针 q，并且指向白色的对象 3。

![image-20220117223523326](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117223523326.png)

与此同时灰色的对象 2 将指针 p 移除，那么白色的对象 3 实则就是被挂在了已经扫描完成的黑色的对象 4 下，如图所示。

![image-20220117223552188](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117223552188.png)

然后我们正常指向三色标记的算法逻辑，将所有灰色的对象标记为黑色，那么对象 2 和对象 7 就被标记成了黑色，如图所示。

![image-20220117223619798](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117223619798.png)

那么就执行了三色标记的最后一步，将所有白色对象当做垃圾进行回收，如图所示。

![image-20220117223705060](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117223705060.png)

但是最后我们才发现，本来是对象 4 合法引用的对象 3，却被 GC 给“误杀”回收掉了。

可以看出，有两种情况，在三色标记法中，是不希望被发生的。

- 条件 1: 一个白色对象被黑色对象引用**(白色被挂在黑色下)**
- 条件 2: 灰色对象与它之间的可达关系的白色对象遭到破坏**(灰色同时丢了该白色)**
  如果当以上两个条件同时满足时，就会出现对象丢失现象！

并且，如图所示的场景中，如果示例中的白色对象 3 还有很多下游对象的话，也会一并都清理掉。

为了防止这种现象的发生，最简单的方式就是 STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是**STW 的过程有明显的资源浪费，对所有的用户程序都有很大影响**。那么是否可以在保证对象不丢失的情况下合理的尽可能的提高 GC 效率，减少 STW 时间呢？答案是可以的，我们只要使用一种机制，尝试去破坏上面的两个必要条件就可以了。

## 屏障机制

我们让 GC 回收器，满足下面两种情况之一时，即可保对象不丢失。这两种方式就是“强三色不变式”和“弱三色不变式”。

### 强弱三色不变式

#### 强三色不变式

不存在黑色对象引用到白色对象的指针。破坏条件 1

![image-20220117232344555](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117232344555.png)

弱三色不变色实际上是强制性的不允许黑色对象引用白色对象，这样就不会出现有白色对象被误删的情况。

#### 弱三色不变式

所有被黑色对象引用的白色对象都处于灰色保护状态。破坏条件 2

![image-20220117232437203](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220117232437203.png)

弱三色不变式强调，黑色对象可以引用白色对象，但是这个白色对象必须存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。这样实则是黑色对象引用白色对象，白色对象处于一个危险被删除的状态，但是上游灰色对象的引用，可以保护该白色对象，使其安全。

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

### 插入屏障

`具体操作`: 在 A 对象引用 B 对象的时候，B 对象被标记为灰色。(将 B 挂在 A 下游，B 必须被标记为灰色)

`满足`: **强三色不变式**. (不存在黑色对象引用白色对象的情况了，因为白色会强制变成灰色)

伪码如下：

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

场景：

> A.添加下游对象 (nil, B)   //A 之前没有下游，新添加一个下游对象 B，B 被标记为灰色
> A.添加下游对象 (C, B)     //A 将下游对象 C 更换为 B，B 被标记为灰色

 这段伪码逻辑就是写屏障，. 我们知道，黑色对象的内存槽有两种位置，`栈`和`堆`. 栈空间的特点是容量小，但是要求相应速度快，因为函数调用弹出频繁使用，所以“插入屏障”机制，在**栈空间的对象操作中不使用**. 而仅仅使用在堆空间对象的操作中。

 接下来，我们用几张图，来模拟整个一个详细的过程，希望您能够更可观的看清晰整体流程。

![image-20220118110847719](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118110847719.png)

![image-20220118110907807](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118110907807.png)

![image-20220118110927155](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118110927155.png)

![image-20220118110946799](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118110946799.png)

![image-20220118111009046](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111009046.png)

![image-20220118111052664](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111052664.png)

但是如果栈不添加，当全部三色标记扫描之后，栈上有可能依然存在白色对象被引用的情况 (如上图的对象 9). 所以要对栈重新进行三色标记扫描，但这次为了对象不丢失，要对本次标记扫描启动 STW 暂停。直到栈空间的三色标记结束。

![image-20220118111111574](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111111574.png)

![image-20220118111129525](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111129525.png)

![image-20220118111148821](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111148821.png)

最后将栈和堆空间 扫描剩余的全部 白色节点清除。这次 STW 大约的时间在 10~100ms 间。

![image-20220118111206635](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111206635.png)

### 删除屏障

`具体操作`: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。

`满足`: **弱三色不变式**. (保护灰色对象到白色对象的路径不会断)

伪代码：

```go
添加下游对象(当前下游对象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 之前为白)

接下来，我们用几张图，来模拟整个一个详细的过程，希望您能够更可观的看清晰整体流程。

![image-20220118111225425](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111225425.png)

![image-20220118111240242](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111240242.png)

![image-20220118111304756](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111304756.png)

![image-20220118111324015](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111324015.png)

![image-20220118111341188](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111341188.png)

![image-20220118111356369](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111356369.png)

![image-20220118111413768](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111413768.png)

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

## Go V1.8 的混合写屏障 (hybrid write barrier) 机制 

插入写屏障和删除写屏障的短板：

- 插入写屏障：结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；
- 删除写屏障：回收精度低，GC 开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

Go V1.8 版本引入了混合写屏障机制（hybrid write barrier），避免了对栈 re-scan 的过程，极大的减少了 STW 的时间。结合了两者的优点。

### 混合写屏障规则

`具体操作`:

1、GC 开始将栈上的对象全部扫描并标记为黑色 (之后不再进行第二次重复扫描，无需 STW)，

2、GC 期间，任何在栈上创建的新对象，均为黑色。

3、被**删除**的对象标记为灰色。

4、被**添加**的对象标记为灰色。

`满足`: 变形的**弱三色不变式**（结合了插入、删除写屏障两者的优点）

伪代码：

```go
添加下游对象(当前下游对象slot, 新下游对象ptr) {
  	//1 
	标记灰色(当前下游对象slot)    //只要当前下游对象被移走，就标记灰色
  	
  	//2 
  	标记灰色(新下游对象ptr)		// 强三色
  		
  	//3
  	当前下游对象slot = 新下游对象ptr
}
```

> 这里我们注意，屏障技术是不在栈上应用的，因为要保证栈的运行效率。

### 混合写屏障的具体场景分析

接下来，我们用几张图，来模拟整个一个详细的过程，希望您能够更可观的看清晰整体流程。

> 注意混合写屏障是 GC 的一种屏障机制，所以只是当程序执行 GC 的时候，才会触发这种机制。

GC 开始：扫描栈区，将可达对象全部标记为黑

![image-20220118111706579](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111706579.png)

栈上的全部标记为黑，就不会再次扫描了

![image-20220118111721295](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111721295.png)

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

##### 伪代码

```go
//前提：堆对象 4->对象 7 = 对象 7；  //对象 7 被 对象 4 引用
栈对象1->对象7 = 堆对象7；  //将堆对象 7 挂在 栈对象 1 下游
堆对象4->对象7 = null；    //对象 4 删除引用 对象 7
// 代码解释

heap4.Next = obj7
stack1.Next = heap7
heap4.Next = nil
```

![image-20220118111809785](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111809785.png)

对象 4 删除对象 7 的引用关系

对象 7 要被删除，对象 7 被标记为灰色

![image-20220118111824561](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111824561.png)

对象 4 就删除了对象 7 的引用，

此时对象 7 变为灰色，下一轮将被扫描，被保护

#### 场景二：对象被一个栈对象删除引用，成为另一个栈对象的下游

##### 伪代码

```go
new 栈对象9；
对象9->对象3 = 对象3；      //将栈对象 3 挂在 栈对象 9 下游
对象2->对象3 = null；      //对象 2 删除引用 对象 3
```

![image-20220118111917714](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111917714.png)

![image-20220118111932094](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111932094.png)

![image-20220118111944954](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118111944954.png)

#### 场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游

##### 伪代码

```go
堆对象10->对象7 = 堆对象7；       //将堆对象 7 挂在 堆对象 10 下游
堆对象4->对象7 = null；         //对象 4 删除引用 对象 7
```

![image-20220118112023455](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118112023455.png)

![image-20220118112037632](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118112037632.png)

![image-20220118112052003](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118112052003.png)

#### 场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游

##### 伪代码

```go
堆对象10->对象7 = 堆对象7；       //将堆对象 7 挂在 堆对象 10 下游
堆对象4->对象7 = null；         //对象 4 删除引用 对象 7
```

![image-20220118112132700](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118112132700.png)

![image-20220118112150923](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118112150923.png)

![image-20220118112209127](https://jimyag.com/posts/golanggc-golang-gc-go/index/image-20220118112209127.png)

 Golang 中的混合写屏障满足`弱三色不变式`，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个 goroutine 的栈，使其变黑并一直保持，这个过程不需要 STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行 re-scan 操作了，减少了 STW 的时间。

## 参考

[Golang 中 GC 回收机制三色标记与混合写屏障_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1wz4y1y7Kd?p=9)