golang笔记——GC 原理

一、GC触发

• 内存分配量达到阀值触发 GC
  每次内存分配时，都会检查当前内存分配量是否已达到阀值，如果达到阀值则立即启动 GC：
  • 阀值 = 上次 GC 内存分配量 * 内存增长率
  • 内存增长率由环境变量 GOGC 控制，默认为 100，即每当内存扩大一倍时启动 GC
• 定期触发 GC
  默认情况下，最长 2 分钟，由sysmon触发一次 GC，这个间隔在 src/runtime/proc.go:forcegcperiod 变量中被声明
• 手动触发
  程序代码中也可以使用 runtime.GC()来手动触发 GC。这主要用于 GC 性能测试和统计。

二、 v1.3 标记-清除算法

1、 v1.3 之前

整体流程图

具体步骤

1. 启动STW（Stop The World），暂停程序业务逻辑

   
   

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

   
   

3. 标记完成后，清除未标记的对象

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

缺点：

• STW让程序暂停，CPU全部用于垃圾回收，程序出现卡顿（重要问题）
• 标记需要扫描整个heap
• 清楚数据会产生heap碎片

2、 v1.3优化Mark & Sweep

由于未被标记的不可达对象，基本不会再次被引用（由于程序中没有对象拥有不可达对象的地址，所以难以再被其他对象引用）。因此，在Mark标记完成后，就停止STW，让程序恢复运行，可以减少STW的时间，同时也不会影响Sweep清除的正确性。

所以，go在v1.3版本做了简单的优化，将STW的步骤提前, 减少STW暂停的时间范围，同时并发执行Sweep清除。如下所示：

优化后的GC仍存在STW的问题，Go V1.5版本使用了三色并发标记法来继续优化这个问题。

三、v1.5 三色并发标记、插入写屏障、删除写屏障

三色标记的一个明显好处是能够让用户程序和 mark 并发的进行

“三色”只是为了叙述上方便抽象出来的一种说法，实际上对象并没有颜色之分。这里的“三色”，对应了垃圾回收过程中对象的三种状态：

• 黑色：已被回收器访问到的对象，其子对象也已被被回收器访问到
• 灰色：已被回收器访问到的对象，但其可能仍存在子对象未被回收器访问到。
• 白色：未被回收器访问到的对象（潜在的垃圾），其内存可能会被垃圾收集器回收。

1、三色并发标记--具体步骤：

1. 初始将所有内存标记为白色，将所有对象放入白色集合中

   
   

2. 然后将 roots 加入worklist(进入worklist即被视为变成灰色)

   
   

3. 从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合。
   （本次遍历只会对根节点下的子节点进行1次遍历，是非递归遍历，仅遍历1层）

   
   

4. 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合。
   （这一次遍历只扫描灰色对象，将灰色对象的第一层遍历可抵达的对象由白色变为灰色， 将灰色对象标记为黑色，并将其从灰色标记表移动到黑色标记表）

   
   

5. 重复第3步, 直到灰色标记表中无任何对象

   
   
   

6. 回收所有的白色标记表的对象.

   
   

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

2、没有STW，带来漏标问题

假设我们执行三色并发标记时，不执行STW。用户程序，有可能将1个灰色对象G下白色子对象W的引用，转移给1个黑色对象B。在GC时会误删除对象W，从而导致程序异常。详见下图：

由上图可以看出，有两种情况，在三色标记法中，是不希望被发生的：
- 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)

如果当以上两个条件同时满足时，就会出现对象丢失现象！为了防止这种现象的发生，我们只要使用一种机制，尝试去破坏上面的两个必要条件就可以了。这样也可以避免STW带来的资源浪费问题。

3、屏障机制

破坏上面的两个必要条件，有两种方式：

• 强三色不变式：不允许黑色对象引用任何白色对象
  
• 弱三色不变式：允许黑色对象引用白色对象，但该白色对象的可达路径中必须存在灰色对象
  

在GC源码中对应两种屏障机制：“Dijkstra 插入写屏障”、“Yuasa 删除写屏障”。

• Dijkstra 插入写屏障
  具体操作：在A对象引用C对象的时候，C对象被标记为灰色。(将C挂在A下游，C必须被标记为灰色)
  
  满足：强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)
  伪码如下：

// 添加下游对象
writePointer(slot, ptr):
    // 标记灰色(新下游对象ptr) 
    shade(ptr)
    // 当前下游对象slot = 新下游对象ptr
    *slot=ptr

• Yuasa 删除写屏障
  具体操作：从对象B被删除的对象C，如果对象C自身为灰色或者白色，那么对象C被标记为灰色。
  
  满足：弱三色不变式. (保护灰色对象到白色对象的路径不会断)
  伪码如下：

// 添加下游对象
writePointer(slot, ptr):
    // 如果当前对象是灰色或白色
    if ( isGrey(slot) || isWhite(slot) )
        // 标记灰色(当前下游对象ptr) 
        shade(*slot)
    // 当前下游对象slot = 新下游对象ptr
    *slot = ptr

• 插入写屏障与删除写屏障的缺点：

  • 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活。仅适用于堆（程序运行基本在栈中，存在大量变量声明、赋值及函数调用，若栈中使用插入写屏障，将极大增加复杂度、降低性能）
  • 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。仅适用于堆

• 整体流程
  

  
  1. 初始化 GC 任务，包括开启写屏障(write barrier)和开启辅助GC(mutator assist)，统计 root对象的任务数量等，这个过程需要STW。
  2. 扫描所有 root 对象（全局指针、goroutine(G) 栈上的指针(扫描对应 G栈时需停止该G)），将其加入灰色队列，并循环处理灰色队列的对象，直到灰色队列为空，该过程后台并行执行
  3. 完成标记工作，重新扫描(re-scan)全局指针和栈。因为 Mark是并行执行的，且栈中不适用插入写屏障，所以栈中可能会存在新的未扫描的对象。同时这个re-scan过程会执行STW 。
  4. 按照标记结果回收所有的白色对象，该过程后台并行执行。

四、v1.8 混合写屏障

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

1. GC开始将栈上的可达对象全部扫描并标记为黑色(当前过程无需STW)
2. GC开始执行标记操作，任何在堆\栈上创建的新对象，均为黑色。
3. 标记结束，开始STW，重新扫描全局指针，不再rescan栈，并执行其他相关操作
4. 关闭STW回收未标记对象，调整下一次GC pacing
满足：变形的弱三色不变式。
伪码如下：

// 添加下游对象
writePointer(slot, ptr):
    // 标记灰色(当前下游对象ptr) 
    shade(*slot)
    // 如果当前堆栈对象是黑色
    if current stack is grey:
        // 标记灰色(新下游对象ptr) 
        shade(ptr)
    // 当前下游对象slot = 新下游对象ptr
    *slot = ptr

通过以下场景，我们看下在v1.5和v1.8中的GC变化

	v1.5	v1.8
堆对象A --x--> 堆对象B，栈对象C ----> 堆对象B	堆中删除写屏障标记B为灰色	堆中删除写屏障标记B为灰色
堆对象A ----> 新堆对象B	堆中插入写屏障标记B为灰色	堆中创建的新对象默认均为黑色
栈对象A --x--> 栈对象B，栈对象C ----> 栈对象B	rescan后，最终标记B为黑色	GC开始时，已将B标记为黑色
栈对象A ----> 新栈对象B	rescan后，最终标记B为黑色	栈中创建的新对象默认均为黑色
栈对象A ----> 新堆对象B	rescan后，最终标记B为黑色	堆中创建的新对象默认均为黑色
栈对象A --x--> 栈对象B	rescan后，最终被清除	GC开始时，已将B标记为黑色；等待下次GC清除

五、3个版本Mark&Sweep对比

• GoV1.3 - 普通标记清除法，整体过程需要启动STW，效率极低。
• GoV1.5 - 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通
• GoV1.8 - 三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。

六、GC Sweep

Go 提供2种方式来清理内存：

1. 在后台启动一个 worker 等待清理内存，一个一个mspan 处理
   当开始运行程序时，Go 将设置一个后台运行的Worker(唯一的任务就是去清理内存)，它将进入睡眠状态并等待内存段扫描
   当GC worker未清理完内存，但新一轮GC又开始了。这时这个运行 GC 的 goroutine 就会在开始标记阶段前去协助完成剩余的清理工作
2. 当申请分配内存时候 lazy 触发
   当应用程序 goroutine 尝试在堆内存中分配新内存时，会触发该操作。清理导致的延迟和吞吐量降低被分散到每次内存分配时。
   该方式属于即时执行，由于被使用的内存段已经被分发到每一个P 的本地缓存 mcache 中，很难追踪首先清理哪些内存，因此Go 会先将所有内存段移动到mcentral，让本地缓存mcache 再次请求它们，去即时清理。即时扫描确保所有内存段都会得到清理（节省资源），同时不会阻塞程序执行

---

Referencs:
https://www.yuque.com/aceld/golang/zhzanb
https://www.cnblogs.com/zj420255586/p/14261834.html#12-%E6%A0%87%E8%AE%B0-%E6%B8%85%E9%99%A4
https://golang.design/under-the-hood/zh-cn/part2runtime/ch08gc/basic/
https://www.qycn.com/xzx/article/10803.html
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part2-semantics.html
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part3-semantics.html