Go GC 的演化过程

版本	方式	STW 时间
v1.3 及之前	标记清除(Mark&Sweep)	» 100ms
v1.5	三色标记+插入写屏障	10~100ms
v1.8	三色标记+混合写屏障	< 2ms

相关名词：
- STW(Stop The World) 将整个程序执行过程”冻结”起来，然后执行扫描，这个过程程序功能是完全暂停的，STW 时间越短越好。
- Object(对象) 在栈上或堆上创建的变量、对象，通常由指针关联起来，形成树状或网状结构
- Root(根) 上面树状结构的根节点就是根，根可以是 main 函数中的变量，也可以是函数调用栈上的变量，或者全局变量
- Reachable(可达) 如果某个对象可以从根遍历到，则说这个对象”可达”
- 波面将整个遍历过程想象成一个水波从中心(根)扩散的过程，则正在进行可达判断的(由不同线程操作)一组对象被称为”波面”
- 起始快照 在三色标记法中，刚开始要 STW 锁定，然后将所有 goroutine 的栈上对象都置灰，作为起始迭代。这个过程耗时较长

Mark and Sweep(标记清除法)

流程：
1. 达到某种条件开始执行 GC，进入 STW 状态
2. 从 main 函数为根开始对所有对象进行迭代遍历
3. 删除所有不可达的对象
4. GC 结束，退出 STW 状态
缺点：
- STW 程序暂时时间较长，无法满足低延迟要求
- 扫描要遍历整个 Heap，时间复杂度较高
- 清除对象会产生 Heap 碎片
优化思路：
- 如果把”删除不可达对象”操作放在”退出 STW”之后再执行，可以节省一些时间
  - mark 过程占大头，优化效果不明显

三色标记法

将对象节点分为三个集合：
- White(白色) 白色表示节点的默认状态，表示未被可达性扫描的节点
- Black(黑色) 黑色表示已被确认可达的(要保留)的节点
- Gray(灰色) 灰色表示下次扫描迭代就会处理的节点
基本流程：
1. 将所有节点放入白色集合
2. 遍历 main 函数及调用栈将栈变量变为灰色，做为开始迭代的起始集合
3. 遍历灰色集合，将下一层可达对象变为新一代灰色，然后将上一代灰色变为黑色
4. 持续执行 3，直到所有可达节点变为黑色，剩下的白色不可达
5. 清理不可达白色对象，GC 结束

问题：

上面的三色标记法处理过程必须全程 STW，所以相对Mark and Sweep没有优势。假设不进行 STW，而程序是多线程运行的，可能造成下面问题：

在某次迭代处理中三个节点：B1(1 号节点是黑色节点)、G2->W3(2 号节点是灰色节点，它有有指向 3 号节点的指针，3 号节点是白色节点)
在线程 A，B1添加对W3的引用；在线程 B，G2删除对W3的引用
2 的执行结果为：B1->W3、G2
由于只有 G(灰色)节点会执行迭代，所以后面的迭代W3不再参与，最终W3被错误的清除了(实际上还被B1引用)

无 STW 导致对象被误删的条件：
1. 一个白色对象被黑色对象引用(对象被实际使用)
2. 灰色对象与可达的白色对象之间引用关联被破坏(失去了被扫描的机会)
  - 这个白色对象可能不是与灰色对象直接关联，间接关联也可能被破坏

方案：

当上面两个条件同时满足时，白色对象就会被丢失。可以想办法破坏上面其中一个条件，避免错误发生。谷歌提出两种应对方式：

强三色不变式——破坏条件 1 黑色可以引用灰色，黑色不能引用白色
弱三色不变式——破坏条件 2 黑色增加新的到白色的指针时，要保证白色被灰色(直接/间接)引用

用屏障机制可以实现上面的不变式。所谓写屏障就是一种 Hook 函数，在引用发生变化(插入/删除)的时候被自动调用，意为通过一个屏障阻止引用变化时发生错误。

插入屏障(Dijkstra 屏障 Go1.5 采用)

当一个新的引用建立时触发 Hook 函数。

黑色对象上增加白色对象时，要把白色变为灰色。这样保证了强三色不变式
插入写屏障要覆盖所有对象太多，所以只在堆上对象应用
由于在栈上对寄存器对象的写操作(赋值/删除)无法实现 Hook(太复杂，例如函数压栈)，所以不能对栈上对象的赋值实现插入屏障。这导致栈上的黑色对象可能指向堆上的白色对象，无法在迭代时保证强三色不变性
流程：
1. 同过原子开关，将所有栈上对象置为灰，作为起始迭代集合
2. 逐步迭代，如果是堆上黑色对象插入/更新下游对象为白色，则将下游白对象变为灰色
3. 最后成一遍迭代。这时由于栈上对象没有执行插入屏障，所以可能存在未标记白对象
4. 最后要 STW 锁住栈，把栈重新遍历一遍，专门处理黑色栈对象指向下一层白色堆对象的问题，然后 STW 解锁。
5. 最后将不可达白色对象删除

// 插入屏障伪码
// 操作主体是"黑色"，nextSlot 是 nil，表示插入新对象引用
func SetNext(nextSlot, nextPtr) {
    markGray(nextPtr)
    nextSlot = nextPtr
}
// 两种用法：
// b.SetNext(nil, w)  下游插入一个新的白色节点
// b.SetNext(old, w)  将下游节点替换为一个新的白色节点

残留问题：相比之前 STW 完全锁住，写屏障已经好了很多，Go1.3 就用这种方式实现了 GC。但是由于对栈上对象遍历、迭代，浪费了时间，10~100ms 还是无法满足低延迟的业务需求

删除屏障(Yuasa 屏障)

当一个引用被删除时触发 Hook 函数。

被删除的对象，如果自身为灰色或白色，那么标记为灰色
这样可以满足弱三色不变式，保证灰色对象到白色对象的路径不会断
删除写屏障，可能导致本轮原本应该被删除的对象被保留下来，只能等到下轮删除
流程：
1. STW 锁定，遍历所有 goroutine 的栈上对象变为黑色，并将第一层堆上对象变为灰色，保证堆上所有对象都在灰色保护下，STW 解锁
2. 逐步迭代，如果某个对象被删除，并且自身是白色或灰色，则置灰
3. 最后将不可达的白色对象删除

// 删除屏障伪码
// nextSlot 是原指针
func SetNext(nextSlot, nextPtr) {
    if isGray(nextSlot) || isWhite(nextSlot) {
      markGray(nextSlot)
    }
    nextSlot = nextPtr
}
// 两种用法：
// x.SetNext(old, nil)  删除下游节点
// x.SetNext(old, new)  替换下游节点

残留问题：
- STW 时间不可控由于起始快照处理，刚开始要扫描所有 goroutine 的栈上对象，对于线上服务往往栈都很大，所以耗时较长。 (比较适合嵌入式、物联网这种小内存的处理)
- 回收精度较低可能有对象残留，要下一轮才能被删掉；删除写屏障会导致波面后退，有些已删除元素也会被扫描到；

思考

上面删除写屏障已经将 STW 时间减少了很多，但是能不能每个 goroutine 单独进行起始快照处理呢？如果能实现的话，那么 STW 就能再减少一个数量级。

假设有四个对象 1 2 3 4，其中B1->B2对象在携程1的控制下，B 表示节点已经经过扫描变为黑色。W3->W4对象在携程2的控制下，W 表示还没有进行过扫描。 B1、W3分别在链路的开头，表示该节点是携程的栈上对象。

如果发生B2插入W4同时W3删除W4，那么最终状态是： B1->B2->W4+W3。由于携程1中B2已经是黑色的，所以不会再迭代，最后W4被误删。

由于B2是堆上对象，如果B2插入W4时利用写屏障将 4 改为G4，则可以打破条件 1

混合写屏障(Go1.8 采用)

GC 开始，为每个 P 创建一个 GC 协程，STW，设置全局写屏障标记
用 groutine 并发的方式将栈上的对象全部扫描并标记为黑色，同时设置第一层堆上对象为灰色(之后不再进行第二次重复扫描，无需全局 STW) 第一次灰色标记时，只扫描栈、全局变量中是指针或含有指针成员的类型的对象。
GC 期间，任何在栈上创建的新对象，均为黑色
被(从堆上对象)删除的对象标记为灰色
被添加(到堆上对象)的对象标记为灰色
最后 STW，开始逐步清除所有未标记的白色对象

通过对单个 groutine 的初始快照扫描，将第一层堆对象变为灰色，保证以后堆对象可以执行迭代
上面操作满足了变形后的弱三色不变式，保证对白色的可达连接不断开，也避免对栈上对象重复扫描

// 混合写屏障伪码
// 操作主体是"黑色"，nextSlot 是主体的下游对象指针成员
func SetNext(nextSlot, nextPtr) {
    markGray(nextSlot)
    markGray(nextPtr)
    nextSlot = nextPtr
}
// 用法：这里 x 是堆上对象
// x.SetNext(nil, w)  下游插入一个新的白色节点
// x.SetNext(old, w)  将下游节点替换为一个新的白色节点
// x.SetNext(old, nil)  删除下游节点

问题场景

前提：
1. 每个 goroutine 有自己的栈，栈上对象只能属于一个 goroutine
2. 单个 goroutine 的代码是顺序执行的，不可能并行执行
3. 每个 goroutine 有自己内存管理，创建堆对象时，如果是 GC 期，则自动申请到灰色对象
4. 混合屏障在堆上对象起作用
场景:
- 有携程1->B1+携程2->W2->W3，其中通过颜色可以看出携程 1 已经 GC 开始，所以栈上对象是黑色
- 如果将W3插入到B1同时从W2删除，则会出现：携程1->B1->W3+携程2->W2，这种情况下W3会被错误的删除
分析：
- 上面的场景是不存在的，携程1想将W3赋值到B1必须先”持有”，而持有只有下面五种方式：
  1. 携程1持有W2，然后操作W2把W3赋值给B1
    - 这种不可能，因为W2是携程2的栈上对象，是独占的。如果W2可能被多个携程操作，则编译期会自动逃逸分析，设为堆上对象，这与假设不符
  2. 携程1通过自己的某个栈上对象持有W3
    - 这种也不可能，否则 GC 初期就应该变为灰色了
  3. 携程1间接通过堆上对象Wx持有W3，然后赋值给B1
    - 这种正好符合了删除屏障规则，W3会自动变为G3，不会被误删
  4. 携程2直接把W3赋值给B1
    - 和 1 的原因相同，操作前必须持有，而B1是携程1独占的栈上对象
  5. 携程1在堆上创建一个W3，同时赋值给B1
    - 由于对象创建是由 groutine 自己的内存管理控制着，所以 GC 时申请到的新堆上对象自动就是灰色的

其他细节

如果白色对象已经无法可达，那是怎么被删除的？(操作删除这样的对象也需要指针可达吧？) Go Runtime 实现了一套多级内存池系统。每个 goroutine 有一个 ThreadCache，所有的堆上对象都是从里面分配的并且有一个指针指向对象。由于这个隐形指针的存在，白色对象是可以清除的。每个对象在内存池都有一个唯一的 bit 位与之对应，这样就能快速直到该对象是否被标记
删除频繁删除小堆上对象，产生内存碎片怎么办？在可用内存池freelist中区分不通大小管理内存，不容易产生内存碎片
写屏障具体是怎么实现的？
- 写屏障就是 Hook 函数，在赋值函数上适配一层函数，在 GC 期这个函数对所有堆上对象开始起作用
- 写屏障的代码在编译期间生成好，之后不会再变化
- 堆上对象赋值才会触发写屏障，栈上对象赋值不会
- 哪些对象分配在栈上，哪些分配在堆上？也是编译期间由编译器决定，这个过程叫做”逃逸分析”
单个 groutine 的初始快照 对于某个 groutine 的栈上对象，在 GC 过程中，要么全灰、要么全黑，所以可以用一个标识位原子操作实现，这样进一步省去了 STW 时间
GC 的时机
- 2min 自动执行
- 触发阈值，默认 10MB，每次触及内存翻倍时触发
- 主动执行runtime.GC()
利用sync.Pool增加堆上对象的重用，避免 GC 太大带来性能问题
在大并发下可能产生很多生命周期很短的 goroutine，这些 goroutine 的执行时间很短，主要时间花在了创建、调度、析构上，而这个过程会使 GC 压力过大。这种情况可以利用携程池重用携程解决