Go 垃圾回收

垃圾回收器

GC，全称 Garbage Collection，即垃圾回收，是一种自动内存管理的机制。

通常，垃圾回收器的执行过程被划分为两个半独立的组件：

• 赋值器（Mutator）：这一名称本质上是在指代用户态的代码。因为对垃圾回收器而言，用户态的代码仅仅只是在修改对象之间的引用关系，也就是在对象图（对象之间引用关系的一个有向图）上进行操作。
• 回收器（Collector）：负责执行垃圾回收的代码。

垃圾回收器在标记过程时最先检查的对象（根对象）如下：

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

Go 垃圾回收实现方式

常见垃圾回收算法包括：

• 追踪式：从根对象出发，根据对象之间的引用信息，一步步推进直到扫描完毕整个堆并确定需要保留的对象，从而回收所有可回收的对象。Go、 Java、V8 对 JavaScript 的实现等均为追踪式 GC。

  • 标记清扫：从根对象出发，将确定存活的对象进行标记，并清扫可以回收的对象。
  • 标记整理：为了解决内存碎片问题而提出，在标记过程中，将对象尽可能整理到一块连续的内存上。
  • 增量式：将标记与清扫的过程分批执行，每次执行很小的部分，从而增量的推进垃圾回收，达到近似实时、几乎无停顿的目的。
  • 增量整理：在增量式的基础上，增加对对象的整理过程。
  • 分代式：将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。

• 引用计数：每个对象自身包含一个被引用的计数器，当计数器归零时自动得到回收。因为此方法缺陷较多，在追求高性能时通常不被应用。Python、Objective-C 等均为引用计数式 GC。

对于 Go 而言，Go 的 GC 目前使用的是无分代（对象没有代际之分）、不整理（回收过程中不对对象进行移动与整理）、并发（与用户代码并发执行）的三色标记清扫算法。原因在于：

• 对象整理的优势是解决内存碎片问题以及’允许’使用顺序内存分配器。但 Go 运行时的分配算法基于 tcmalloc，基本上没有碎片问题。 并且顺序内存分配器在多线程的场景下并不适用。Go 使用的是基于 tcmalloc 的现代内存分配算法，对对象进行整理不会带来实质性的性能提升。
• 分代 GC 依赖分代假设，即 GC 将主要的回收目标放在新创建的对象上（存活时间短，更倾向于被回收），而非频繁检查所有对象。但 Go 的编译器会通过逃逸分析将大部分新生对象存储在栈上（栈直接被回收），只有那些需要长期存在的对象才会被分配到需要进行垃圾回收的堆中。也就是说，分代 GC 回收的那些存活时间短的对象在 Go 中是直接被分配到栈上，当 goroutine 死亡后栈也会被直接回收，不需要 GC 的参与，进而分代假设并没有带来直接优势。并且 Go 的垃圾回收器与用户代码并发执行，使得 STW 的时间与对象的代际、对象的 size 没有关系。Go 团队更关注于如何更好地让 GC 与用户代码并发执行（使用适当的 CPU 来执行垃圾回收），而非减少停顿时间这一单一目标上。

三色标记法

三色标记法将对象标记为黑、白、灰三种颜色，黑色对象为可达对象，应该保留，白色对象为不可达对象，应该被清除，灰色作为中间过度态。

下面以链表为例，介绍三色标记-清除法的过程。

1.假设我们新建了三个结点 A、B、C，其中，A和B是头结点，C 是B 的下一个节点，一般头结点都是可达的。由于 GC 周期还没开始，所以这三个对象都属于白色集合。

2.新建节点D，并作为A的下一个节点。有这样一条规则：当一个指针域变化时，则该指针指向的对象需要变色。因为所有新建对象都需要将其地址赋值给一个引用，所以它们会立即变成灰色。所以D将被放置在灰色集合中。

3.在 Go 中，GC 进程和正常程序进程是并行的，它们在计算机中交替运行。此时 GC 过程开始运行，根对象A、B都被移到灰色集合中。

4.扫描内存对象，GC收集器会扫描灰色集合的对象，将扫描到的对象标记为黑色，并将其子对象标记为灰色。无论哪个阶段，GC 都可以计算出剩余对象的移动次数为 2×[白色集合对象数]+[灰色集合对象数],因为白色对象要先移到灰色集合中, 灰色对象最后要全部移到黑色集合中，这就是系数2的由来。每次GC扫描都至少要进行一次移动，直到灰色集合中对象数为0，也就是剩余对象移动次数为0才罢休。

5.我们又新建了对象E，并作为对象C的下一个节点，同样对象E也会被分配到灰色集合。这一步增加了 GC 阶段数，也就是 GC 扫描的次数，因此会导致 GC 清除阶段的推迟。

6.此时我们让B指向E，这样一来，对象C将变得不可达。按照第4步GC收集器扫描内存对象的过程，由于灰色集合中没有对象指向 C，因此，对象 C 将永远残留在白色集合中，最后被GC收集器回收掉。

7.GC扫描继续进行，这一次扫描对象D。将对象D移到黑色集合中，但是D没有子对象了，所以直接将D移入黑色集合中就行了。

8.我们将对象B的next指针置空，断开B与E的关联。按道理E也变为不可达了，应该被清除掉，但是E却在灰色集合中，下一次 GC 扫描就会被移入黑色集合，不会回到白色集合中，也就不能被回收了。确实是这样，这一轮的 GC 的确不能将E回收，但是没关系，下一轮的 GC 就可以将E回收了。

9.GC 扫描继续运行，这一次扫描对象E，它也没有子对象，直接将它移入黑色集合就好。注意，这里并不会将对象 C 移入黑色集合，因为C是E的上层对象，而不是下层对象，简单的说，E的指针并没有指向 C。

10.GC 收集器扫描对象B，也是孤家寡人一个，直接移入黑色集合完事儿。

11.此时灰色集合已经空了，可以进行 GC 清除了。

12.重置 GC，这一轮的 GC 清除已经完成了，需要为下一轮的 GC 做好准备。这个准备就是把黑色集合的对象全部再移回白色集合。但实际上并不需要移动，只需要把黑色集合变成白色集合，把白色集合变成黑色集合就行了，也就是把这两个集合的颜色互换一下，不用移动对象。这样一来，对象E就在白色集合中了，并且在下一次GC扫描的时候不会再被移走，将一直残留在白色集合中等着被清除。

以上就是三色标记-清扫算法的全部过程了。

三色标记法问题

并发标记清除中面临的一个根本问题就是如何保证标记与清除过程的正确性。
在没有用户态代码并发修改三色抽象的情况下，回收可以正常结束。但是并发回收的根本问题在于，用户态代码在回收过程中会并发地更新对象图，从而造成赋值器和回收器可能对对象图的结构产生不同的认知。这时以一个固定的三色波面作为回收过程前进的边界则不再合理。

• 初始状态：假设某个黑色对象 C 指向某个灰色对象 A ，而 A 指向白色对象 B；
• C.ref3 = C.ref2.ref1：赋值器并发地将黑色对象 C 指向（ref3）了白色对象 B；
• A.ref1 = nil：移除灰色对象 A 对白色对象 B 的引用（ref2）；
• 最终状态：在继续扫描的过程中，白色对象 B 永远不会被标记为黑色对象了（回收器不会重新扫描黑色对象），进而对象 B 被错误地回收。

当以下两个条件同时满足时会破坏垃圾回收器的正确性：

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

只要能够避免其中任何一个条件，则不会出现对象丢失的情况，因为：

• 如果条件 1 被避免，则所有白色对象均被灰色对象引用，没有白色对象会被遗漏；
• 如果条件 2 被避免，即便白色对象的指针被写入到黑色对象中，但从灰色对象出发，总存在一条没有访问过的路径，从而找到到达白色对象的路径，白色对象最终不会被遗漏。

三色不变性

我们不妨将三色不变性所定义的波面根据这两个条件进行削弱：

• 当满足原有的三色不变性定义（或上面的两个条件都不满足时）的情况称为强三色不变性（strong tricolor invariant）
• 当赋值器令黑色对象引用白色对象时（满足条件 1 时）的情况称为弱三色不变性（weak tricolor invariant）

赋值器的颜色

如果我们考虑并发的用户态代码，回收器不允许同时停止所有赋值器，就是涉及了存在的多个不同状态的赋值器。
为了对概念加以明确，还需要换一个角度，把回收器视为对象，把赋值器视为影响回收器这一对象的实际行为（即影响 GC 周期的长短），从而引入赋值器的颜色：

• 黑色赋值器：已经由回收器扫描过，不会再次对其进行扫描。
• 灰色赋值器：尚未被回收器扫描过，或尽管已经扫描过但仍需要重新扫描。

赋值器的颜色对回收周期的结束产生影响：

• 如果某种并发回收器允许灰色赋值器的存在，则必须在回收结束之前重新扫描对象图。
• 如果重新扫描过程中发现了新的灰色或白色对象，回收器还需要对新发现的对象进行追踪，但是在新追踪的过程中，赋值器仍然可能在其根中插入新的非黑色的引用，如此往复，直到重新扫描过程中没有发现新的白色或灰色对象。

于是，在允许灰色赋值器存在的算法，最坏的情况下，回收器只能将所有赋值器线程停止才能完成其跟对象的完整扫描，也就是我们所说的 STW。

写屏障

写屏障是一个在并发垃圾回收器中才会出现的概念，垃圾回收器的正确性体现在：不应出现对象的丢失，也不应错误的回收还不需要回收的对象。

有两种非常经典的写屏障：Dijkstra 插入屏障和 Yuasa 删除屏障。

Dijkstra 插入屏障

基本思想是避免满足条件 1.

为了防止黑色对象指向白色对象，应该假设 *slot 可能会变为黑色，为了确保 ptr 不会在被赋值到 *slot 前变为白色，shade(ptr) 会先将指针 ptr 标记为灰色，进而避免了条件 1。

// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)
    *slot = ptr
}

Yuasa 删除屏障

其基本思想是避免满足条件 2.

防止丢失从灰色对象到白色对象的路径，应该假设 *slot 可能会变为黑色，为了确保 ptr 不会在被赋值到 *slot 前变为白色，shade(*slot) 会先将 *slot 标记为灰色，进而该写操作总是创造了一条灰色到灰色或者灰色到白色对象的路径，进而避免了条件 2。

// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot)
    *slot = ptr
}

混合写屏障

Go 在 1.8 的时候为了简化 GC 的流程，同时减少标记终止阶段的重扫成本，将 Dijkstra 插入屏障和 Yuasa 删除屏障进行混合，形成混合写屏障。该屏障提出时的基本思想是：对正在被覆盖的对象进行着色，且如果当前栈未扫描完成，则同样对指针进行着色。

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

SWT （stop the world）

STW 在垃圾回收过程中为了保证实现的正确性、防止无止境的内存增长等问题而不可避免的需要停止赋值器进一步操作对象图的一段过程。
在这个过程中整个用户代码被停止或者放缓执行， STW 越长，对用户代码造成的影响（例如延迟）就越大，早期 Go 对垃圾回收器的实现中 STW 长达几百毫秒，对时间敏感的实时通信等应用程序会造成巨大的影响。
我们来看一个例子：

package main

import (
	"runtime"
	"time"
)

func main() {
	go func() {
		for {
		}
	}()

	time.Sleep(time.Millisecond)
	runtime.GC()
	println("OK")
}

上面的这个程序在 Go 1.14 以前永远都不会输出 OK，其罪魁祸首是进入 STW 这一操作的执行无限制的被延长。
这个程序被卡死原因是由于需要进入 STW 导致的。原因在于，GC 在需要进入 STW 时，需要通知并让所有的用户态代码停止，但是 for {} 所在的 goroutine 永远都不会被中断，从而始终无法进入 STW 阶段。
自 Go 1.14 之后，这类 goroutine 能够被异步地抢占，从而使得进入 STW 的时间不会超过抢占信号触发的周期，程序也不会因为仅仅等待一个 goroutine 的停止而停顿在进入 STW 之前的操作上。
目前Go 团队宣称 STW 停顿时间得以优化到 100 微秒级别。

GC 的时机

可以将 GC 划分为五个阶段：

阶段	说明	赋值器状态
SweepTermination	清扫终止阶段，为下一个阶段的并发标记做准备工作，启动写屏障	STW
Mark	扫描标记阶段，与赋值器并发执行，写屏障开启	并发
MarkTermination	标记终止阶段，保证一个周期内标记任务完成，停止写屏障	STW
GCoff	内存清扫阶段，将需要回收的内存归还到堆中，写屏障关闭	并发
GCoff	内存归还阶段，将过多的内存归还给操作系统，写屏障关闭	并发

Go 语言中对 GC 的触发时机存在两种形式：

• 主动触发，通过调用 runtime.GC 来触发 GC，此调用阻塞式地等待当前 GC 运行完毕。
• 被动触发，分为两种方式：
  • 使用系统监控，当超过两分钟没有产生任何 GC 时，强制触发 GC。
  • 使用步调（Pacing）算法，其核心思想是控制内存增长的比例。

内存泄露

在一个具有 GC 的语言中，我们常说的内存泄漏，用严谨的话来说应该是：预期的能很快被释放的内存由于附着在了长期存活的内存上、或生命期意外地被延长，导致预计能够立即回收的内存而长时间得不到回收。

在 Go 中，由于 goroutine 的存在，所谓的内存泄漏除了附着在长期对象上之外，还存在多种不同的形式。

预期能被快速释放的内存因被根对象引用而没有得到迅速释放

当有一个全局对象时，可能不经意间将某个变量附着在其上，且忽略的将其进行释放，则该内存永远不会得到释放。例如：

var cache = map[interface{}]interface{}{}

func keepalloc() {
	for i := 0; i < 10000; i++ {
		m := make([]byte, 1<<10)
		cache[i] = m
	}
}

goroutine 泄漏

Goroutine 作为一种逻辑上理解的轻量级线程，需要维护执行用户代码的上下文信息。在运行过程中也需要消耗一定的内存来保存这类信息，而这些内存在目前版本的 Go 中是不会被释放的。
因此，如果一个程序持续不断地产生新的 goroutine、且不结束已经创建的 goroutine 并复用这部分内存,直到程序结束,此goroutine才退出，就会造成内存泄漏的现象，例如：

goroutine 泄露的场景

1. 从 channel 里读，但是没有写

   func leak() {
        ch := make(chan int)
   
        go func() {
           val := <-ch
           fmt.Println("We received a value:", val)
       }()
   }
   
   // leak 是一个有 bug 程序。它启动了一个 goroutine 阻塞接收 channel。
   // 当 Goroutine 正在等待时，leak 函数会结束返回。
   // 此时，程序的其他任何部分都不能通过 channel 发送数据，那个 channel 永远不会关闭，fmt.Println 调用永远不会发生， 那个 goroutine 会被永远锁死

2. 向 unbuffered channel 写，但是没有读

   // 一个复杂一点的例子
   func sendMsg(msg, addr string) error {
       conn, err := net.Dial("tcp", addr)
       if err != nil {
           return err
       }
       defer conn.Close()
       _, err = fmt.Fprint(conn, msg)
       return err
   } 
   
   func broadcastMsg(msg string, addrs []string) error {
       errc := make(chan error)
       for _, addr := range addrs {
           go func(addr string) {
               errc <- sendMsg(msg, addr)
               fmt.Println("done")
           }(addr)
       }
   
       for _ = range addrs {
           if err := <-errc; err != nil {
               return err
           }
       }
       return nil
   }
   
   func main() {
       addr := []string{"localhost:8080", "http://google.com"}
       err := broadcastMsg("hi", addr)
   
       if err != nil {
           fmt.Println(err)
           return
       }
       fmt.Println("everything went fine")
   }

   当遇到 第一条不为 nil 的 err，broadcastMsg就返回了，那么从第二个调用 sendMsg 后返回值 err 不为 nil 的 goroutine 在errc <- sendMsg(msg, addr)这里都将阻塞而造成这些 goroutine 不能退出。

3. 向已满的 buffered channel 写，但是没有读
   和第二种情况比较类似。

       tick := time.Tick(1 * time.Second)
       for countdown := 10; countdown > 0; countdown-- {
           fmt.Println(countdown)
           select {
           case <-tick:
               // Do nothing.
           case <-abort:
               fmt.Println("aborted!")
               return
           }
       }
   // 当 for 循环结束后，tick 将不再有接收者，time.Tick 启动的 goroutine 将产生泄露。

4. select 操作在所有 case 上阻塞
   实现一个 fibonacci 数列生成器，并在独立的 goroutine 中运行，在读取完需要长度的数列后，如果 用于 退出生成器的 quit 忘了被 close (或写入数据)，select 将一直被阻塞造成 该 goroutine 泄露。

   func fibonacci(c, quit chan int)  {
       x, y := 0, 1
       for{
           select {
           case c <- x:
               x, y = y, x+y
           case <-quit:
               fmt.Println("quit")
               return
           }
       }
   }
   
   func main() {
       c := make(chan int)
       quit := make(chan int)
   
       go fibonacci(c, quit)
   
       for i := 0; i < 10; i++{
           fmt.Println(<- c)
       }
       
     // close(quit)
   }

5. goroutine进入死循环中，导致资源一直无法释放

   // 粗暴的示例
   func foo() {
     for{
       fmt.Println("fooo")
     }
   }

GC 调优

Go 的 GC 被设计为极致简洁，与较为成熟的 Java GC 的数十个可控参数相比，严格意义上来讲，Go 可供用户调整的参数只有 Go GC 环境变量。
当我们谈论 GC 调优时，通常是指减少用户代码对 GC 产生的压力，这一方面包含了减少用户代码分配内存的数量（即对程序的代码行为进行调优），另一方面包含了最小化 Go 的 GC 对 CPU 的使用率（即调整 GOGC）。
只有那些对执行延迟非常敏感、 当 GC 的开销成为程序性能瓶颈的程序，才需要针对 GC 进行性能调优，几乎不存在于实际开发中 99% 的情况。 除此之外，Go 的 GC 也仍然有一定的可改进的空间，也有部分 GC 造成的问题，目前仍属于 Open Problem。

总的来说，我们可以在现在的开发中处理的有以下几种情况：

• 对停顿敏感：GC 过程中产生的长时间停顿、或由于需要执行 GC 而没有执行用户代码，导致需要立即执行的用户代码执行滞后。
• 对资源消耗敏感：对于频繁分配内存的应用而言，频繁分配内存增加 GC 的工作量，原本可以充分利用 CPU 的应用不得不频繁地执行垃圾回收，影响用户代码对 CPU 的利用率，进而影响用户代码的执行效率。

参考

• https://blog.csdn.net/puss0/article/details/113810394
• https://golang.design/go-questions/memgc/principal/