垃圾是指程序向堆栈申请的内存空间，随着程序的运行已经不再使用这些内存空间，这时如果不释放他们就会造成垃圾也就是内存泄漏。

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

1、标记-清除 (mark and sweep) 算法

Go 在 V1.3 之前使用 标记-清除算法

1. 进行 STW（Stop The World，暂停程序业务逻辑），然后从 main 函数开始，找到不可达的内存占用和可达的内存占用
2. 开始标记，程序找出可达内存占用并做标记

开始标记

3. 标记结束，清除未标记的内存占用
4. 结束 STW，让程序继续运行，循环该过程直到 main 生命周期结束

清除

标记清除算法明了，过程鲜明干脆，但是也有非常严重的问题。就是需要程序暂停，STW 的过程中，CPU 不执行用户代码，全部用于垃圾回收，这个过程的影响很大，所以 STW 也是一些回收机制最大的难题和希望优化的点。

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

全部的 GC 时间内都是 STW。所以Go V1.3 做了简单的优化,将 STW 的步骤提前，减少 STW 暂停的时间范围。

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

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

接下来 G V1.5 版本 就用三色并发标记法来优化这个问题。

2、三色标记法

Golang 中的垃圾回收主要应用三色标记法，GC 过程和其他用户 goroutine 可并发运行，但需要一定时间的 STW，所谓三色标记法实际上就是通过三个阶段的标记来确定对象都有哪些。

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

白色对象表示暂无对象引用的潜在垃圾，其内存可能会被垃圾收集器回收。

黑色对象表示活跃的对象，包括不存在引用外部指针的对象以及从根对象可达的对象。

灰色对象表示活跃的对象，黑色到白色的中间状态，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象。

第一步：每次新创建的对象，默认的颜色都是标记为“白色”。

第二步：从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合。

本次遍历非递归的，是从程序根节点出发，可抵达的对象遍历一层，当前可抵达的对象是 对象1 和 对象4，那么自然本轮遍历结束，对象1 和 对象4 就会被标记为灰色。

第三步：遍历灰色集合，将灰色对象引用的对象从 白色集合 放入 灰色集合，之后将此灰色对象放入黑色集合。

第四步：重复第三步，直到灰色中无任何对象。

当全部的可达对象都遍历完后，将不再存在灰色对象，目前全部内存的数据只有两种颜色，黑色和白色。

黑色对象就是可达对象，这些是程序正常运行的数据，不可删除。白色的对象全部不可达对象，是内存中目前的垃圾数据，需要被清除。

第五步：回收所有的白色标记表的对象，剩下的就是全部依赖的黑色对象。

以上便是三色标记法，上面已经体现三色的特性。上述的三色标记法是一定依赖 STW 的。因为如果不暂停程序，程序的逻辑改变对象引用关系，这种动作如果在标记阶段做了修改，会影响标记结果的正确性。举一个场景。

假设把初始状态设置为已经经历了第一轮扫描。

现在如何三色标记过程不启动 STW，那么在 GC 扫描过程中，任意的对象均可能发生读写操作。如下图，若 对象2 断开了 对象3 的引用，对象4 增加 对象3 的引用。

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

那么就执行了三色标记的最后一步，将所有白色对象当做垃圾进行回收，本来是 对象4 合法引用的 对象3，却被 GC 回收掉了。

分析根源所在，主要是因为程序在运行过程中出现了俩种情况：

1. 一个 白色对象 被 黑色对象 引用
2. 灰色对象 与它之间的可达关系的 白色对象 遭到破坏

如果当以上两个条件同时满足时，就会出现对象丢失现象。并且，如果示例中的 白色对象3 还有下游对象的话，也会一并都清理掉。

为了防止上述现象的发生，最简单的方式就是 STW，直接禁止其他用户程序对对象引用关系的干扰，但是 STW 的过程对所有的用户程序都有很大影响。

是否可以在保证对象不丢失的情况下，合理的尽可能的提高 GC 效率，减少 STW 时间呢？答案是可以的，只要使用一种机制，尝试去破坏上面的两个条件就可以了。

3、屏障机制

为了破坏上述 2 种情况，从而引出了屏障机制，即在程序的执行过程中加一个判断机制，满足判断机制则执行回调函数。

根据操作类型的不同，可以分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。

Go 语言中使用的两种写屏障技术，分别为 插入写屏障 和 删除写屏障。插入写屏障 实现的是 强三色不变式；删除写屏障 则实现了 弱三色不变式。

3.1、插入写屏障

插入写屏障：对象被引用时触发的机制。当 白色对象 被 黑色对象 引用时，白色对象 被标记为 灰色。实际上是强制性的不允许 黑色对象 引用 白色对象，这样就不会出现有 白色对象 被误删的情况，破坏上述情况1。

需要注意的是，对象的内存分为 栈 和 堆。栈空间调用更加频繁，且更加快速，如果每次插入的时候都使用屏障，会让栈的速度变慢，这里为了性能，不进行插入屏障，而是在最后再重新扫描一次。所以 插入屏障 在栈空间的对象操作中不使用，而仅使用在堆空间对象的操作中。

遍历 root set 得到灰色节点。

遍历灰色节点，将可达对象从 白色 变为 灰色，并且自身变为 黑色。

由于并发特性，此时 对象4 --> 对象8，对象1 --> 对象9。
对象4 在堆区，将触发插入屏障，对象1 在栈区，不触发。

由于插入屏障（黑色对象 添加 白色对象，将 白色对象 变为 灰色对象），对象8 变灰色，对象9 依然为白色。

继续上述流程，直到没有灰色对象。

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

将栈中的对象进行三色标记，直到没有灰色。

停止 STW

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

3.2、删除屏障

删除屏障：对象被删除时触发的机制。如果灰色对象引用的白色对象被删除时，那么白色对象会被标记为灰色。

黑色对象 可以引用 白色对象，但是这个 白色对象 必须存在其他 灰色对象 对它的引用，或者可达它的链路上游存在 灰色对象。 这样实则是 黑色对象 引用 白色对象，白色对象 处于一个危险被删除的状态，但若上游有 灰色对象 的引用，可以保护该 白色对象，使其安全（实际上就是破坏上述情况2）。

遍历 root set 得到灰色节点。

对象1 断开 对象5 的引用。

触发删除屏障，对象5 变为 灰色。

继续三色法，可达对象从 白色 变为 灰色，灰色对象 变为 黑色对象。

直到没有灰色对象。

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

4、并发三色垃圾收集

Go 语言在 v1.5 中引入了并发的垃圾收集器，该垃圾收集器使用了 三色技术 和 写屏障技术 保证垃圾收集器并发执行的正确性。

首先，并发垃圾收集器必须在合适的时间点触发垃圾收集循环，在垃圾收集开始后，收集器会启计算资源在后台来扫描并标记内存中的对象。

Go 语言的并发垃圾收集器会在扫描对象之前暂停程序做一些标记对象的准备工作，其中包括 启动后台标记的垃圾收集器 以及 开启写屏障，如果在后台执行的垃圾收集器不够快，应用程序申请内存的速度超过预期，运行时会让申请内存的应用程序辅助完成垃圾收集的扫描阶段，在标记和标记终止阶段结束之后就会进入异步的清理阶段，将不用的内存回收。

因为并发垃圾收集器会与程序一起运行，所以它无法准确的控制堆内存的大小，并发收集器需要在达到目标前触发垃圾收集，这样才能够保证内存大小的可控，并发收集器需要尽可能保证垃圾收集结束时的堆内存与用户配置的 GOGC 一致。

4、混合写屏障

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

• 插入写屏障：结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；
• 删除写屏障：回收精度低

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

具体操作:

1. GC 开始时将栈上可达对象全部标记为黑色（之后不需要二次扫描，无需 STW）
2. GC 期间，栈上创建的新对象均为黑色
3. 被删除引用的对象标记为灰色
4. 被添加引用的对象标记为灰色

需要注意：

1. 混合写屏障也是 GC 的一种屏障机制，所以只是当程序执行 GC 的时候，才会触发这种机制。
2. 屏障技术 不应用在栈上，因为要保证栈的运行效率。
3. 混合写屏障规则第一步，还是需要 STW，不然仍会出现对象丢失的情况，所以是几乎不需要 STW，但是还是有

三色标记法，优先扫描栈对象，将可达对象均标记为黑色。

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

此时，对象1 --> 对象7，栈空间无屏障，对象7 不变色。

对象4 断开应用 对象7，由于混合屏障，对象7 变灰色。此时，回收正常。

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

对象1 删除 对象2 的引用，栈空间不启用屏障。

对象4 删除 对象7，改为对象2.

对象7 在被删除应用时，触发屏障，从白色变为灰色。

事实上，对象7 在该轮回收过程中逃脱了，只能等到下轮回收。

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

4、GC 整体流程

1、清理终止阶段
暂停程序，清扫终止阶段，为下一阶段的并发标记做准备工作；
为了打开写屏障，必须停止每个goroutine，让垃圾收集器观察并等待每个goroutine进行函数调用，

2、标记阶段
2.1、将状态切换至 _GCmark、开启写屏障、用户程序协助（Mutator Assists）并将根对象入队；
2.2、恢复执行程序，标记进程和用于协助的用户程序，开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；
2.3、依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；

3、标记终止阶段
暂停程序、将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序；

4、清理阶段
4.1、将状态切换至 _GCoff 开始清理阶段，初始化清理状态并关闭写屏障；
4.2、恢复用户程序，所有新创建的对象会标记成白色；
4.3、后台并发清理所有的内存管理单元

4、GC 什么时候会被触发

运行时，通过 runtime.gcTrigger.test 方法决定是否需要触发垃圾收集，当满足触发垃圾收集的基本条件时（允许垃圾收集、程序没有崩溃、未处于垃圾收集循环），该方法会根据三种不同方式触发进行不同的检查：

1. gcTriggerHeap — 堆内存的分配达到控制器计算的触发堆大小；
2. gcTriggerTime — 如果一定时间内没有触发，就会触发新的循环，默认为 2 分钟；
3. gcTriggerCycle — 如果当前没有开启垃圾收集，则触发新的循环；

const (
    // gcTriggerHeap indicates that a cycle should be started when
    // the heap size reaches the trigger heap size computed by the
    // controller.
    gcTriggerHeap gcTriggerKind = iota

    // gcTriggerTime indicates that a cycle should be started when
    // it's been more than forcegcperiod nanoseconds since the
    // previous GC cycle.
    gcTriggerTime

    // gcTriggerCycle indicates that a cycle should be started if
    // we have not yet started cycle number gcTrigger.n (relative
    // to work.cycles).
    gcTriggerCycle
)

func (t gcTrigger) test() bool {
    if !memstats.enablegc || panicking.Load() != 0 || gcphase != _GCoff {
        return false
    }
    switch t.kind {
    case gcTriggerHeap:
        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:
        return int32(t.n-work.cycles.Load()) > 0
    }
    return true
}

用于开启垃圾收集的方法 runtime.gcStart 会接收一个 runtime.gcTrigger 类型

// gcStart starts the GC. It transitions from _GCoff to _GCmark (if
// debug.gcstoptheworld == 0) or performs all of GC (if
// debug.gcstoptheworld != 0).
//
// This may return without performing this transition in some cases,
// such as when called on a system stack or with locks held.
func gcStart(trigger gcTrigger) {
……
}

所有出现 runtime.gcTrigger 结构体的位置都是触发垃圾收集的代码：

• runtime.sysmon 和 runtime.forcegchelper — 后台运行定时检查和垃圾收集；
• runtime.GC — 用户程序手动触发垃圾收集；
• runtime.mallocgc — 申请内存时根据堆大小触发垃圾收集；

后台触发

运行时会在应用程序启动时在后台开启一个用于强制触发垃圾收集的 Goroutine，该 Goroutine 的职责非常简单 — 调用 runtime.gcStart 尝试启动新一轮的垃圾收集：

func init() {
    go forcegchelper()
}

func forcegchelper() {
    forcegc.g = getg()
    lockInit(&forcegc.lock, lockRankForcegc)
    for {
        lock(&forcegc.lock)
        if forcegc.idle.Load() {
            throw("forcegc: phase error")
        }
        forcegc.idle.Store(true)
        goparkunlock(&forcegc.lock, waitReasonForceGCIdle, traceEvGoBlock, 1)
        // this goroutine is explicitly resumed by sysmon
        if debug.gctrace > 0 {
            println("GC forced")
        }
        // Time-triggered, fully concurrent.
        gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
    }
}

为了减少对计算资源的占用，该 Goroutine 会在循环中调用 runtime.goparkunlock 主动陷入休眠等待其他 Goroutine 的唤醒，runtime.forcegchelper 在大多数时间都是陷入休眠的

// Puts the current goroutine into a waiting state and unlocks the lock.
// The goroutine can be made runnable again by calling goready(gp).
func goparkunlock(lock *mutex, reason waitReason, traceEv byte, traceskip int) {
    gopark(parkunlock_c, unsafe.Pointer(lock), reason, traceEv, traceskip)
}

但是它会被系统监控器 runtime.sysmon 在满足垃圾收集条件时唤醒：

func sysmon() {
    ...
    for {
        ...
        // check if we need to force a GC
        if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && atomic.Load(&forcegc.idle) != 0 {
            lock(&forcegc.lock)
            forcegc.idle = 0
            var list gList
            list.push(forcegc.g)
            injectglist(&list)
            unlock(&forcegc.lock)
        }
    }
}

系统监控在每个循环中都会主动构建一个 runtime.gcTrigger 并检查垃圾收集的触发条件是否满足，如果满足条件，系统监控会将 runtime.forcegc 状态中持有的 Goroutine 加入全局队列等待调度器的调度。

手动触发

用户程序会通过 runtime.GC 函数在程序运行期间主动通知运行时执行，该方法在调用时会阻塞调用方直到当前垃圾收集循环完成，在垃圾收集期间也可能会通过 STW 暂停整个程序：

func GC() {
    n := atomic.Load(&work.cycles)
    gcWaitOnMark(n)
    gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
    gcWaitOnMark(n + 1)

    for atomic.Load(&work.cycles) == n+1 && sweepone() != ^uintptr(0) {
        sweep.nbgsweep++
        Gosched()
    }

    for atomic.Load(&work.cycles) == n+1 && atomic.Load(&mheap_.sweepers) != 0 {
        Gosched()
    }

    mp := acquirem()
    cycle := atomic.Load(&work.cycles)
    if cycle == n+1 || (gcphase == _GCmark && cycle == n+2) {
        mProf_PostSweep()
    }
    releasem(mp)
}

手动触发垃圾收集的过程不是特别常见，一般只会在运行时的测试代码中才会出现，这是一种不推荐的做法。

申请内存

最后一个可能会触发垃圾收集的就是 runtime.mallocgc 了，运行时会将堆上的对象按大小分成微对象、小对象和大对象三类，这三类对象的创建都可能会触发新的垃圾收集循环：

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    shouldhelpgc := false
    ...
    if size <= maxSmallSize {
        if noscan && size < maxTinySize {
            ...
            v := nextFreeFast(span)
            if v == 0 {
                v, _, shouldhelpgc = c.nextFree(tinySpanClass)
            }
            ...
        } else {
            ...
            v := nextFreeFast(span)
            if v == 0 {
                v, span, shouldhelpgc = c.nextFree(spc)
            }
          ...
        }
    } else {
        shouldhelpgc = true
        ...
    }
    ...
    if shouldhelpgc {
        if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
            gcStart(t)
        }
    }
    return x
}

1. 当前线程的内存管理单元中不存在空闲空间时，创建微对象和小对象需要调用 runtime.mcache.nextFree 从中心缓存或者页堆中获取新的管理单元，在这时就可能触发垃圾收集；
2. 当用户程序申请分配 32KB 以上的大对象时，一定会构建 runtime.gcTrigger 结构体尝试触发垃圾收集；

6、GC过程演示

GODEBUG=gctrace=1 go run main.go

gc 1 @0.022s 1%: 0.006+0.70+0.013 ms clock, 0.054+0.13/0.82/0.65+0.10 ms cpu, 3->4->1 MB, 4 MB goal, 0 MB stacks, 0 MB globals, 8 P
gc 2 @0.025s 1%: 0.040+1.2+0.086 ms clock, 0.32+0.37/1.0/0+0.69 ms cpu, 3->3->1 MB, 4 MB goal, 0 MB stacks, 0 MB globals, 8 P
gc 3 @0.029s 2%: 0.090+0.76+0.012 ms clock, 0.72+0.054/0.87/0+0.099 ms cpu, 3->3->1 MB, 4 MB goal, 0 MB stacks, 0 MB globals, 8 P
gc 4 @0.032s 2%: 0.026+0.68+0.016 ms clock, 0.21+0.45/0.83/0.36+0.13 ms cpu, 3->4->1 MB, 4 MB goal, 0 MB stacks, 0 MB globals, 8 P

gc 1      : 第一个GC周期
@0.005s   : 从程序开始运行到第一次GC时间为0.001 秒
1%        : 此次GC过程中 CPU 占用率

wall clock
0.006+0.70+0.013 ms clock
0.006 ms  : STW，Marking Start, 开启写屏障
0.70 ms   : Marking阶段
0.013 ms  : STW，Marking终止，关闭写屏障

CPU time
0.054+0.13/0.82/0.65+0.10 ms cpu
0.054 ms   : STW，Marking Start
0.13 ms  : 辅助标记时间
0.82 ms  : 并发标记时间
0.65 ms   : GC 空闲时间
0.10 ms   : Mark 终止时间

3->4->1 MB， 4 MB goal
3 MB      ：标记开始时，堆大小实际值
4 MB      ：标记结束时，堆大小实际值
1 MB      ：标记结束时，标记为存活对象大小
4 MB      ：标记结束时，堆大小预测值

8 P
8P       ：本次GC过程中使用的goroutine 数量

7、总结

Golang 在 GC 的演进过程中也经历了很多次变革

• Go V1.3 之前的标记-清除 (mark and sweep) 算法及其缺点
• Go V1.5 的三色并发标记法
• Go V1.5 的三色标记为什么需要 STW
• Go V1.5 的三色标记为什么需要屏障机制 (“强-弱” 三色不变式、插入屏障、删除屏障 )
• Go V1.8 混合写屏障机制
• 垃圾回收出发的时机（后台触发、手动出发、内存申请）