0.前言

GC 全称 Garbage Collection，目前主流的垃圾回收算法有两类，分别是追踪式垃圾回收算法（Tracing garbage collection）和引用计数法（ Reference counting ）。

Golang 使用的三色标记法属于追踪式垃圾回收算法的一种。

追踪式算法的核心思想是判断一个对象是否可达，因为一旦这个对象不可达就可以立刻被 GC 回收了。

1.发展史

v1.1 标记清除法，整个过程都需要 STW。gc pause 数百 ms 级。

v1.3 标记清除法，标记过程仍需要 STW，清除过程并行化。gc pause 百 ms 级。

v1.5 并发三色标记清除和写屏障。仅在堆空间启动插入写屏障，全部扫描后需要 STW 重新扫描栈空间。gc pause 10 ms 级。

v1.8 并发三色标记清除和混合写屏障。仅在堆空间启动插入写屏障，全部扫描后不需要 STW 重新扫描栈空间。gc pause 0.5 ms 级。

混合写屏障指 Dijkstra 插入写屏障和 Yuasa 删除写屏障。

2.并发三色标记清除和混合写屏障

2.1 三色标记

三色标记算法将程序中的对象分成白色、黑色和灰色。

• 白色对象（可能死亡）：未被回收器访问到的对象。在回收开始阶段，所有对象均为白色，当回收结束后，白色对象均不可达。
• 灰色对象（波面）：已被回收器访问到的对象，但回收器需要对其中的一个或多个指针进行扫描，因为他们可能还指向白色对象。
• 黑色对象（确定存活）：已被回收器访问到的对象，其中所有字段都已被扫描，黑色对象中任何一个指针都不可能直接指向白色对象。

回收器首先将所有对象标记成白色，然后从根对象集合出发，逐步把所有可达的对象变成灰色再到黑色，最终所有的白色对象都是不可达对象，即垃圾对象。

具体实现：

• 将所有对象标记为白色。
• 从根节点集合出发，将第一次遍历到的节点标记为灰色放入集合列表中。
• 遍历灰色集合，将灰色节点遍历到的白色节点标记为灰色，并把灰色节点标记为黑色。
• 重复，上一步骤，直到灰色对象队列为空。
• 剩下的所有白色对象都是垃圾对象。

根对象是垃圾回收器在标记过程最先检查的对象，包括：

• 全局变量：程序在编译期就能确定的那些存在于程序整个生命周期的变量。
• 执行栈：每个 goroutine 都包含自己的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
• 寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某些赋值器分配的堆内存。

2.2 并发标记问题

在垃圾回收过程中，标记操作与程序的执行可以同时进行，故称为并发三色标记。

并发标记可以提高程序性能，但是存在问题。

假设有三个对象，A、B 和 C，标记过程中状态如下：

赋值器并发地将黑色对象 C 指向了白色对象 B，并移除灰色对象 A 对白色对象 B 的引用。

然后继续扫描灰色对象 A，那么白色对象 B 永远不会被标记为黑色对象了（回收器不会重新扫描黑色对象），进而对象 B 被误回收。

因为漏标记导致回收了仍在使用的对象。

垃圾回收的原则是不应出现对象的丢失（内存泄漏），也不应错误地回收还不需要回收的对象（漏标记）。如果同时满足下面两个条件会破坏回收器的正确性：

• 条件 1: 赋值器修改对象，导致某一黑色对象引用白色对象。
• 条件 2: 从灰色对象出发，到达白色对象且未经访问过的路径被赋值器破坏。

上面的例子就是因为同时满足了条件 1 和条件 2 导致并发标记过程漏标了仍在使用的 B 对象。

可能的解决方法： 整个过程 STW，因为这种做法对用户程序影响较大，由此引入了屏障机制。

2.3 屏障机制

使用屏障机制可以使得用户程序和三色标记过程并发执行，我们只需要达成下列任意一种三色不变性：

• 强三色不变性：黑色对象永远不会指向白色对象。
• 弱三色不变性：黑色对象指向的白色对象至少包含一条由灰色对象经过白色对象的可达路径。

Go 使用写屏障避免漏标记对象。

这里的写屏障是指由编译器生成的一小段代码，在 GC 时对指针操作前执行的一小段代码（和 CPU 中维护内存一致性的写屏障不太一样）。

写屏障有两种：Dijkstra 插入写屏障和 Yuasa 删除写屏障。

Dijkstra 插入写屏障

Dijkstra 插入写屏障避免了前面提到的条件 1，黑色对象不会引用白色对象。

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

// Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr) // 先将新下游对象 ptr 标记为灰色
    *slot = ptr
}

尽管 Dijkstra 插入写屏障可以实现垃圾回收和用户程序的并发执行，但是它存在两个缺点。

一方面它是一种比较保守的垃圾回收方法，在一次回收过程中可能会残留一部分对象没有回收成功，只有在下一个回收过程中才会被回收。

以下图为例，用户程序 Mutator 将对象 A 原本指向 B 对象的指针改成指向 C 对象，尽管在修改后 B 对象已经是一个垃圾对象，但是它在本轮垃圾回收过程中不会被回收。

另外一个缺点在于栈上的对象也是根对象，Dijkstra 插入写屏障要么在用户程序执行内存写操作时为栈对象插入写屏障，要么在一轮三色标记完成后使用 STW 重新对栈对象进行三色标记。前者会降低栈空间的响应速度，后者会暂停用户程序。

Go 1.5 选择使用 STW 重新对栈对象进行三色标记。

Yuasa 删除写屏障

Yuasa 删除写屏障避免了前面提到的条件2，防止丢失灰色对象到白色对象的可达路径。

// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot) // 先将旧下游对象 slot 标记为灰色
    *slot = ptr
}

为了防止丢失从灰色对象到白色对象的路径，在 ptr 被赋值到 *slot 前，先将 *slot 标记为灰色。一句话解释就是当删除对象 A 指向对象 B 的指针时，将被删除的对象 B 标记为灰色。

下图简单绘制了 Yuasa 删除写屏障是如何保证用户程序 Mutator 和垃圾回收器 Collector 的并发执行的：

• 第二步中 Mutator 将对象 A 原本指向对象 B 的指针指向 C，由于对象B本身就是灰色的，因此不需要对它重新着色。
• 第三步中 Mutator 删除了对象 B 指向对象 C 的指针，删除写屏障将下游对象 C 标记为灰色。
  
  Yuasa 删除写屏障和 Dijkstra 插入写屏障相比优点在于不需要在一轮三色标记后对栈空间上的对象进行重新扫描。缺点在于Collector 会悲观地认为所有被删除的对象都可能被黑色对象引用，所以将被删除的对象置灰。

混合写屏障

在 Go 1.8 引入混合写屏障（Hybrid Write Barrier）之前，由于 GC Root 对象包括了栈对象，如果运行时在所有 GC Root 对象上开启插入写屏障意味着需要在数量庞大的 Goroutine 的栈上都开启 Dijkstra 写屏障从而严重影响用户程序的性能。

之前的做法是标记阶段结束后暂停整个程序，对栈上对象重新进行三色标记。如果 Goroutine 较多的话，对栈对象 re-scan 这一步需要耗费 10~100 ms。

Go 1.8 为了减少标记终止阶段对栈对象的重扫成本，将 Dijkstra 插入写屏障和 Yuasa 删除写屏障进行混合，形成混合写屏障。

// 混合写屏障
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
	shade(*slot)
	shade(ptr)
	*slot = ptr
}

注意：混合写屏障也是仅在堆空间启动的，防止降低栈空间的运行效率。

混合写屏障逻辑如下：

• GC 开始时将栈上所有对象标记为黑色，无须 STW
• GC 期间在栈上创建的新对象均标记为黑色
• 将被删除的下游对象标记为灰色
• 将被添加的下游对象标记为灰色

3.GC 过程

Golang GC 分为四个阶段：清除终止、标记、标记终止和清除。

（1）清除终止（Sweep Termination）

• 暂停程序，所有处理器在这时会进入安全点（Safe point）。
• 如果当前 GC 是强制触发的，还需要处理未被清理的内存管理单元。

（2）标记（Mark）

• 将状态切换至_GCmark、开启写屏障、用户程序协助（Mutator Assists）并将根对象入队。
• 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色。
• 开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器。
• 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色。
• 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段。

（3）标记终止（Mark Termination）

• 暂停程序，将状态切换至_GCmarktermination并关闭辅助标记的用户程序。
• 清理处理器上的线程缓存。

（4）清除（Sweep）

• 将状态切换至_GCoff，关闭混合写屏障。
• 恢复用户程序，所有新创建的对象标记为白色。
• 后台并发清理所有内存管理单元 span，当 Goroutine 申请新的内存管理单元时就会触发清除。

具体而言，各个阶段的触发函数分别为：

在 GC 过程中会有两种后台任务（G），包括标记任务和清除任务。可以同时执行的标记任务约是 P 数量的四分之一，即 Go 所说的 25% CPU 用于 GC 的依据。清理除任务会在程序启动后运行，清除阶段时被唤醒。

4.GC 触发时机

触发 GC 的方式有两种：手动触发和自动触发。

手动触发调用runtime.GC()函数可以强制触发 GC，该方法在调用时会阻塞调用方直到 GC 完成。在 GC 期间也可能会通过 STW 暂停整个程序。

自动触发有两种：

• 条件触发：当新分配的内存达到上次 GC 结束时存活对象占用内存的某个比例时触发 GC，该比例可以通过环境变量GOGC调整，默认值为 100，即新增 100% 的堆内存会触发 GC。
• 定时触发。使用系统监控协程 sysmon，当超过一段时间（由runtime.forcegcperiod变量控制，默认两分钟）没有产生任何 GC 时，强制触发 GC。

运行时会通过如下所示的runtime.gcTrigger.test方法决定是否需要触发 GC。

// test reports whether the trigger condition is satisfied, meaning
// that the exit condition for the _GCoff phase has been met. The exit
// condition should be tested when allocating.
func (t gcTrigger) test() bool {
	if !memstats.enablegc || panicking.Load() != 0 || gcphase != _GCoff {
		return false
	}
	switch t.kind {
	case gcTriggerHeap:
		// Non-atomic access to gcController.heapLive for performance. If
		// we are going to trigger on this, this thread just
		// atomically wrote gcController.heapLive anyway and we'll see our
		// own write.
		trigger, _ := gcController.trigger()
		return gcController.heapLive.Load() >= trigger
	case gcTriggerTime:
		if gcController.gcPercent.Load() < 0 {
			return false
		}
		lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
		return lastgc != 0 && t.now-lastgc > forcegcperiod
	case gcTriggerCycle:
		// t.n > work.cycles, but accounting for wraparound.
		return int32(t.n-work.cycles.Load()) > 0
	}
	return true
}

满足触发 GC 的基本条件：允许垃圾收集、程序没有崩溃并且 GC 处于清除阶段，即 GC 状态能为_GCoff。

// 允许垃圾回收
memstats.enablegc
// 程序没有 panic
panicking == 0
// 处于 _Gcoff 阶段
gcphase == _GCoff

对应的触发时机包括：

// 堆内存达到一定阈值
gcTriggerHeap
// 距离上一次垃圾回收超过一定时间，间隔由 runtime.forcegcperiod 变量控制，默认为 2 分钟
gcTriggerTime
// 如果当前没有启动 GC 则开始新一轮的 GC。手动调用 runtime.GC() 函数会走到该分支
gcTriggerCycle

5.哪里记录了对象的三色状态？

并没有真正的三个集合来分别装三色对象。

Go 的对象分配在 span 中，span 里有一个字段是 gcmarkBits。标记阶段里面每个 bit 代表一个 slot 已被标记。

白色对象 bit 为 0，灰色或黑色为 1。

每个 P（Processor） 都有 wbBuf 和 gcWork 以及全局的 workbuf 标记队列。队列中的指针为灰色对象，表示已标记待扫描。

从队列中出来并把其引用对象入队的为黑色对象，表示已标记已扫描。

6.如何观察 GC？

以下面的程序为例，使用四种不同的方式来介绍如何观察 GC。

package main

func allocate() {
	_ = make([]byte, 1<<20)
}

func main() {
	for n := 1; n < 1000; n++ {
		allocate()
	}
}

方式1：GODEBUG=gctrace=1

设置环境变量 GODEBUG=gctrace=1，执行程序时可以看到 GC 日志。

go build -o main
GODEBUG=gctrace=1 ./main

gc 1 @0.000s 2%: 0.009+0.23+0.004 ms clock, 0.11+0.083/0.019/0.14+0.049 ms cpu, 4->6->2 MB, 5 MB goal, 12 P
scvg: 8 KB released
scvg: inuse: 3, idle: 60, sys: 63, released: 57, consumed: 6 (MB)
gc 2 @0.001s 2%: 0.018+1.1+0.029 ms clock, 0.22+0.047/0.074/0.048+0.34 ms cpu, 4->7->3 MB, 5 MB goal, 12 P
scvg: inuse: 3, idle: 60, sys: 63, released: 56, consumed: 7 (MB)
gc 3 @0.003s 2%: 0.018+0.59+0.011 ms clock, 0.22+0.073/0.008/0.042+0.13 ms cpu, 5->6->1 MB, 6 MB goal, 12 P
scvg: 8 KB released
scvg: inuse: 2, idle: 61, sys: 63, released: 56, consumed: 7 (MB)
gc 4 @0.003s 4%: 0.019+0.70+0.054 ms clock, 0.23+0.051/0.047/0.085+0.65 ms cpu, 4->6->2 MB, 5 MB goal, 12 P
scvg: 8 KB released
scvg: inuse: 3, idle: 60, sys: 63, released: 56, consumed: 7 (MB)
scvg: 8 KB released
scvg: inuse: 4, idle: 59, sys: 63, released: 56, consumed: 7 (MB)
gc 5 @0.004s 12%: 0.021+0.26+0.49 ms clock, 0.26+0.046/0.037/0.11+5.8 ms cpu, 4->7->3 MB, 5 MB goal, 12 P
scvg: inuse: 5, idle: 58, sys: 63, released: 56, consumed: 7 (MB)
gc 6 @0.005s 12%: 0.020+0.17+0.004 ms clock, 0.25+0.080/0.070/0.053+0.051 ms cpu, 5->6->1 MB, 6 MB goal, 12 P
scvg: 8 KB released
scvg: inuse: 1, idle: 62, sys: 63, released: 56, consumed: 7 (MB)

在这个日志中可以观察到两类不同的信息：

gc 1 @0.000s 2%: 0.009+0.23+0.004 ms clock, 0.11+0.083/0.019/0.14+0.049 ms cpu, 4->6->2 MB, 5 MB goal, 12 P
gc 2 @0.001s 2%: 0.018+1.1+0.029 ms clock, 0.22+0.047/0.074/0.048+0.34 ms cpu, 4->7->3 MB, 5 MB goal, 12 P
...

以及：

scvg: 8 KB released
scvg: inuse: 3, idle: 60, sys: 63, released: 57, consumed: 6 (MB)
scvg: inuse: 3, idle: 60, sys: 63, released: 56, consumed: 7 (MB)
...

含义如下表所示：

字段	含义
gc 2	第二个 GC 周期
0.001	程序开始后的 0.001 秒
2%	该 GC 周期中 CPU 的使用率
0.018	标记开始时， STW 所花费的时间（wall clock）
1.1	标记过程中，并发标记所花费的时间（wall clock）
0.029	标记终止时， STW 所花费的时间（wall clock）
0.22	标记开始时， STW 所花费的时间（cpu time）
0.047	标记过程中，标记辅助所花费的时间（cpu time）
0.074	标记过程中，并发标记所花费的时间（cpu time）
0.048	标记过程中，GC 空闲的时间（cpu time）
0.34	标记终止时， STW 所花费的时间（cpu time）
4	标记开始时，堆的大小的实际值
7	标记结束时，堆的大小的实际值
3	标记结束时，标记为存活的对象大小
5	标记结束时，堆的大小的预测值
12	P 的数量

wall clock 是指开始执行到完成所经历的实际时间，包括其他程序和本程序所消耗的时间； cpu time 是指特定程序使用 CPU 的时间。

wall clock < cpu time: 充分利用多核
wall clock ≈ cpu time: 未并行执行
wall clock > cpu time: 多核优势不明显

对于运行时向操作系统申请内存产生的垃圾回收（向操作系统归还多余的内存）：

scvg: 8 KB released
scvg: inuse: 3, idle: 60, sys: 63, released: 57, consumed: 6 (MB)

含义由下表所示：

字段	含义
8 KB released	向操作系统归还了 8 KB 内存
3	已经分配给用户代码、正在使用的总内存大小 (MB)
60	空闲以及等待归还给操作系统的总内存大小（MB）
63	通知操作系统中保留的内存大小（MB）
57	已经归还给操作系统的（或者说还未正式申请）的内存大小（MB）
6	已经从操作系统中申请的内存大小（MB）

方式2： go tool trace

go tool trace 的主要功能是将统计而来的信息以一种可视化的方式展示给用户。要使用此工具，可以通过调用 trace API：

package main

func main() {
	f, _ := os.Create("trace.out")
	defer f.Close()
	trace.Start(f)
	defer trace.Stop()
	(...)
}

并通过如下命令启动可视化界面。

go tool trace trace.out

方式3：debug.ReadGCStats

此方式可以通过代码的方式来直接实现对感兴趣指标的监控，例如我们希望每隔一秒钟监控一次 GC 的状态：

func printGCStats() {
	t := time.NewTicker(time.Second)
	s := debug.GCStats{}
	for {
		select {
		case <-t.C:
			debug.ReadGCStats(&s)
			fmt.Printf("gc %d last@%v, PauseTotal %v\n", s.NumGC, s.LastGC, s.PauseTotal)
		}
	}
}
func main() {
	go printGCStats()
	(...)
}

我们能够看到如下输出：

go run main.go

gc 4954 last@2019-12-30 15:19:37.505575 +0100 CET, PauseTotal 29.901171ms
gc 9195 last@2019-12-30 15:19:38.50565 +0100 CET, PauseTotal 77.579622ms
gc 13502 last@2019-12-30 15:19:39.505714 +0100 CET, PauseTotal 128.022307ms
gc 17555 last@2019-12-30 15:19:40.505579 +0100 CET, PauseTotal 182.816528ms
gc 21838 last@2019-12-30 15:19:41.505595 +0100 CET, PauseTotal 246.618502ms

方式4：runtime.ReadMemStats

除了使用 debug 包提供的方法外，还可以直接通过运行时内存相关的 API 进行监控：

func printMemStats() {
	t := time.NewTicker(time.Second)
	s := runtime.MemStats{}

	for {
		select {
		case <-t.C:
			runtime.ReadMemStats(&s)
			fmt.Printf("gc %d last@%v, next_heap_size@%vMB\n", s.NumGC, time.Unix(int64(time.Duration(s.LastGC).Seconds()), 0), s.NextGC/(1<<20))
		}
	}
}
func main() {
	go printMemStats()
	(...)
}

go run main.go

gc 4887 last@2019-12-30 15:44:56 +0100 CET, next_heap_size@4MB
gc 10049 last@2019-12-30 15:44:57 +0100 CET, next_heap_size@4MB
gc 15231 last@2019-12-30 15:44:58 +0100 CET, next_heap_size@4MB
gc 20378 last@2019-12-30 15:44:59 +0100 CET, next_heap_size@6MB

当然，后两种方式能够监控的指标很多，读者可以自行查看 debug.GCStats 和 runtime.MemStats 的字段，这里不再赘述。

---

参考文献

图示Golang垃圾回收机制 - 知乎
Golang垃圾回收(GC)介绍
Golang 的 goroutine 是如何实现的？ - 知乎
Go 垃圾回收器指南 - 鸟窝
垃圾回收的认识 | Go 程序员面试笔试宝典
垃圾回收的基本想法 | Go 语言原本
垃圾收集器 | Go 语言设计与实现