GO的垃圾回收

Posted on Edited on In Word count in article: 10k Reading time ≈ 9 mins.
解析go语言，go的垃圾回收

垃圾回收GC

定义

程序创建对象等引用类型实体时会在虚拟内存中分配给它们一块内存空间，如果该内存空间不再被任何引用变量引用时就成为需要被回收的垃圾

对于一个运行较长时间的程序，如果使用完内存资源后没有及时释放就会造成内存泄漏甚至系统错误

如果我们在不该释放内存的时候释放内存，那么仍然在使用这块内存的指针就会变成野指针wild pointer，使用该指针对内存进行读写是未定义的行为

GC性能指标

吞吐量

是指单位时间内是有多少时间是用来运行用户代码的。GC占用的时间过多，就会导致吞吐量较低

最大暂停时间STW

STW stop the world 暂停所有赋值线程

基本上所有的垃圾回收算法，都会在执行GC的过程中，暂停用户代码。如果暂停时间过长，必然会影响用户体验，尤其是那些交互性较强的应用

访问局部性

具有引用关系的对象之间很可能存在连续访问的情况。因此，把具有引用关系的对象安排在堆中较劲的位置，可以充分利用内存访问局部性。有的GC算法会根据引用关系重排对象，比如复制算法。

堆使用效率

影响堆使用效率的主要有两个因素，一个是对象头部大小，一个是堆的用法。

1.一般来说，堆的头部越大，存储的信息越多，那么GC的效率就会越高，吞吐量什么的也会有更佳的表现。但是，我们必须明白，对象头越小越好

2.不同的算法对于堆的不同用法，也会导致堆使用效率差距非常大。比如复制算法，用户应用只能使用一般的堆大小

目标

1.无内存泄漏：垃圾回收器最基本的目标就是减少防止程序员未及时释放导致的内存泄漏，垃圾回收器会识别并清理内存中的垃圾

2.自动回收无用内存：垃圾回收器作为独立的子任务，不需要程序员显式调用即可自动清理内存垃圾

3.内存整理：如果只是简单回收无用内存，那么堆上的内存空间会存在较多碎片而无法满足分配较大对象的需求，因此垃圾回收器需要重整内存空间，提高内存利用率

GC常见算法

引用计数

引用计数Reference counting
会为每个对象维护一个计数器，当该对象被其他对象引用时加一，引用失效时减一，当引用次数归零后即可回收对象

python就是引用计数

1
2
3
4
typedef struct_object {
    int ob_refcnt;
    struct_typeobject *ob_type;
}PyObject;

ob_refcnt为引用计数器

优点：
1.原理和实现都比较简单

2.回收的即时性：当对象的引用计数为0时立即回收，不像其他GC机制需要等待特定时机再回收，提高了内存的利用率

3.不需要暂停应用即可完成回收

缺点：

1.无法解决循环引用的回收问题：当ObjA引用了ObjB，ObjB也引用ObjA时，这两个对象的引用次数使用大于0，从而占用的内存无法被回收

2.时间和空间成本较高：一方面是因为每个对象需要额外的空间存储引用计数器变量，另一方面是在栈上的赋值时修改引用次数时间成本较高（原本只需要修改寄存器中的值，现在计数器需要不断更新因此不是只读的，需要额外的原子操作来保证线程安全

3.引用计数是一种摊销算法，会将内存的回收分摊到整个程序的运行过程，但是当销毁一个很大的树形结构时无法保证响应时间

改进：延迟引用计数

在延迟引用计数法中使用ZCT（Zero Count Table）。ZCT 是一个表，它会事先
记录下计数器值在dec_ref_cnt() 函数的作用下变为0 的对象， 因为计数器值为0 的对象不一定都是垃圾，所以暂时先将这些对象保留

在延迟引用计数法中，程序延迟了根引用的计数，将垃圾一并回收。通过延迟，减轻了
因根引用频繁发生变化而导致的计数器增减所带来的额外负担。当然也失去量垃圾即可回收的特点

追踪回收式

判断哪些对象存活，然后将其余的所有对象作为垃圾进行回收。追踪回收本身包括
标记-清除 Mark-Sweep
标记-复制 Mark-Copy
标记-整理 Mark-Compact
三种回收算法

同引用计数法相比
优点：

1.解决了循环引用对象的回收问题

2.占用空间更少

缺点：

1.同引用计数相比无法立刻识别出垃圾对象，需要依赖GC线程

2.算法在标记时必须暂停整个程序，即Stop The World, STW，否则其他线程的代码会修改对象状态从而回收不该回收的对象

可达性分析算法

上面说的三种算法都是通过可达性分析算法，先进行可达性标记，标记对象是否可达

GC ROOT： 当前时刻存活的对象
GC会收集那些不是GC Roots且没有被GC Roots引用的对象
包括：

1.全局对象、栈上的对象（函数参数与内部变量）

2.与上面对象通过引用链相连的对象

对于“不可达”的对象，我们可以认为该对象为垃圾对象并回收对应的内存空间

1

标记-清除 Mark-Sweep

标记：记录需要回收的垃圾对象

清除：在标记完成后回收垃圾对象的内存空间

2

优点：

1.算法吞吐量高：用户代码时间/总时间高

2.空间利用率：同标记-复制相比不需要额外空间复制对象，也不需要像引用计数算法为每个对象设置引用计数器

缺点：

1.清除后会产生大量的内存碎片空间，导致程序在运行时可能没法为较大的对象分配内存空间，导致提前GC

标记-复制 Mark-Copy

将内存分成大小相同的两块，当某一块的内存使用完了之后就将使用中的对象挨个复制到另一块内存中，最后将当前内存恢复未使用的状态

3

优点：

1.标记-清除法需要在清除阶段对大量垃圾对象进行扫描，标记-复制则只需要从GC Root对象出发，将“可到达”的对象复制到另一块内存后直接清理当前这块的内存，因此提升了垃圾回收的效率

PS：清除，是扫描所有垃圾，标记垃圾，回收，复制是只扫描GC ROOT对象

2.解决了内存碎片化的问题，防止分配较大连续空间时的提前GC问题

缺点：

1.同标记-清除法相比，在“可达”对象占比较高的情况下有复制对象的开销

2.内存利用率较低，相当于可利用的内存仅有一半

标记-整理 Mark-Compact

标记出所有“可达”的对象，然后将存活的对象移动到内存空间的一端，最后清理掉端边界以外的内存

4

优点：

1.避免了内存碎片化的问题

2.在对象存活率较高的情况下，标记-整理算法由于不需要复制对象效率更高，因此更加适合老年代算法

缺点：

1.整理过程较为复杂，需要多次遍历内存导致STW时间比标记-清除算法更长

三色标记法

三色标记法是对“标记”阶段的改进，在不暂停程序的情况下即可完成对象的可达性分析。GC线程将所有对象分为三类

1.白色：未搜索对象，回收周期开始时，所有对象都是白色，回收周期结束后，所有白色都是垃圾对象

2.灰色：正在搜索的对象，对象身上还有一个或多个引用没有扫描

3.黑色：已搜索完的对象，所有引用已被扫描完

属于增量式GC算法，回收器将所有对象着白色，从GC ROOT出发，逐步把所有可达对象变成灰色再到黑色

最终所有的白色对象即是不可达对象

流程：

1.所有对象都是白色对象

2.从GC Root对象出发，扫描所有可达对象并标记为灰色，放入待处理队列

3.从队列取出一个灰色对象并标记为黑色，将其引用对象标记为灰色放入队列

4.重复上一步骤，直到灰色对象队列为空

5.此时所有剩下的白色对象就是垃圾对象

优点：

1.不需要暂停整个程序进行GC

缺点：

1.如果程序垃圾对象的产生速度大于垃圾对象的回收速度时，可能导致程序中的垃圾对象越来越多而无法及时收集

2.线程切换和上下文转换的消耗会使得垃圾回收的总体成本上升，从而降低系统吞吐量

三色标记法的并发性问题

5

如图所示，三色标记法GC与用户程序同时并发执行，用户在标记执行过程中建立了从A对象到D对象的引用，A为黑色，D不会再被扫描为白色，会被错误回收，导致后续对D的访问出错。这种没有指向合法地址的指针一般被称为“野指针”，会造成严重的程序错误

问题原因及解决

三色标记法和用户程序并发执行，那么下列两个条件同时满足就可能出现错误回收非垃圾对象的问题：

1.某一黑色对象引用白色对象

2.对于某个白色对象，所有和它存在可达关系的灰色对象丢失了访问它的可达路径

最简单解决三色标记并发问题的方法是停止所有的赋值器线程，保证标记过程不受干扰，即垃圾回收器中常提到的STW, stop the world方法。另外一种思路就是使用赋值器屏障技术使得赋值器在进行指针写操作时同步垃圾回收器

读写屏障技术

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

1.强三色不变性：黑色对象永远不会指向白色对象

2.弱三色不变性：黑色对象指向的白色对象至少包含一条由灰色对象经过白色对象的可达路径

GC中使用的内存读写屏障技术指的是编译器会在编译期间生成一段代码，该代码在运行期间用户读取、创建或更新对象指针时会拦截内存读写操作，相当于一个hook调用，

根据hook时机不同可分为不同的屏障技术。

由于读屏障Read barrier技术需要在读操作中插入代码片段从而影响用户程序性能，所以一般使用写屏障技术来保证三色标记的稳健性

内存屏障技术解决了三色标记法的STW缺点，并不是指消除了所有的赋值器挂起问题。

需要分清楚STW方法是全局性的赋值器挂起而内存屏障技术是局部的赋值器挂起

Dijkstra插入写屏障

Dijkstra插入写屏障避免了前面提到的条件1，即防止黑色对象指向白色对象

一个对象可以存储在内存中的“栈”或者“堆”，由于“栈”空间容量小且要求相应速度较高，因此“插入写屏障”不适合用于“栈”空间

流程：
1.垃圾回收之前将所有的对象标记为白色
6

2.遍历GC Root Set，将可达对象标记为灰色
7

3.遍历灰色对象列表，将可达的对象从白色标记为灰色；将遍历完的灰色对象标记为黑色
8

4.在三色标记过程中用户程序令栈区对象A指向对象H，令堆区对象E指向对象I，由于对象E在堆区从而触发插入写屏障并将黑色对象E指向的白色对象I标记为灰色，栈区对象A不触发
9

5.继续三色标记直至灰色对象队列为空
10

6.垃圾回收之前将所有的对象标记为白色由于栈区对象没有启动插入写屏障，因此栈上可能存在白色对象被引用的情况（上图中对应对象H），因此在回收白色对象前在STW保护下重新扫描一次栈空间
11

7.在STW保护下对栈空间一次性进行三色标记，直到灰色对象队列为空
12

8.结束STW
13

9.最后将栈空间和堆空间的白色垃圾对象进行回收
14

缺点：

1.一方面它是一种比较保守的垃圾回收方法，把有可能存活的对象都标记成灰色了以满足“强三色不变性”，在修改用户修改引用的时候，会被修改后的本该回收的标记为灰色从而漏掉回收

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

Yuasa删除写屏障

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

流程：
1.将所有对象标记为白色
15

2.遍历GC Root Set将可达对象设为灰色
16

3.如果用户程序令灰色对象A删除了对白色对象D的引用，如果这时候不触发删除写屏障，那么对象D、B和C直到本轮垃圾回收结束都会是白色对象。因此需要触发删除写屏障，将对象D标记为灰色
17

4.遍历灰色对象队列，将可达的白色对象标记为灰色，遍历完的灰色对象标记为黑色
18

5.继续进行三色标记，直到灰色对象队列为空
19

6.清除所有的白色对象
20

优点：

1.不需要在一轮三色标记后对栈空间上的对象进行重新扫描

缺点：

1.Collector会悲观地认为所有被删除的对象都可能被黑色对象引用
比如上图中，删除了A到D的指针，D根据删除屏障，会被标记为灰色，如果此时还有一个单独的对象H指向D，那么本该被删除的对象H却可以在本轮垃圾回收中存活

混合写屏障

使用混合写屏障的原因

go1.8引入混合写屏障

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

之前的做法是是Mark阶段（golang垃圾回收使用的是标记-清除法）结束后暂停整个程序，对栈上对象重新进行三色标记法

PS：如果Goroutine较多的话，对栈对象re-scan这一步需要耗费10 ~ 100 ms

以上两种屏障的劣势：

Dijkstra插入写屏障：一轮标记结束后需要STW重新扫描栈上对象

Yuasa删除写屏障：回收精度低

实现

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

1.GC开始时将栈上所有对象标记为黑色，无须STW

2.GC期间在栈上创建的新对象均标记为黑色
21

3.将被删除的下游对象标记为灰色

4.将被添加的下游对象标记为灰色

场景一：某个对象从堆对象的下游变成栈对象的下游，这种情况下标记该对象为灰色，该对象就不会被错误地回收
22

场景二：某个对象从一个栈对象的下游变成另一个对象的下游，由于对象全都在栈空间对象的可达对象中，因此混合写屏障不会对这些对象着色。
23

场景三：某个对象从一个堆对象的下游变成另一个堆对象的下游，比如下图中对象G从F的下游移动到Y的下游，为了避免对象G被错误回收，我们需要将其标记为灰色
24

场景四：某个对象从栈对象的下游变成堆对象的下游，对于栈空间对象不触发写屏障，但是对于被删除的堆空间对象G需要标记成灰色以保护它和它的下游对象不被错误删除
25

分代收集算法

追踪式回收有一个问题是会频繁扫描生命周期较长的对象，大部分生命周期都很短，因此有必要将对象按照生命周期的长度划分到堆heap上的两个甚至多个区域。对于新生代区域的扫描频率应该高于老年代区域

区域划分：新生代，老年代

1.新生代，老年代分为young，old区域
2.新生代中的对象生命周期较短（每次回收约98%的对象是垃圾对象）
3.新生代采用标记-复制法需要两块内存交替使用
4.Young区为了节省复制算法的内存代价又划分成Eden、Survivor0和Survivor1三个分区（内存分配比例为8:1:1）。

26

新生代回收：Minor GC
老年代回收：Major GC

分配策略与流程

1.对象优先在Yonug上的Eden区域分配（大对象直接进入Old区）

2.Eden区满了之后开始进行Minor GC，将Eden中存活的对象移动到Survivor0区，直接清空Eden区

3.Eden区第二次满了之后进行Minor GC，将Eden和Survivor0中存活的对象复制到Survivor1区，清空Eden和Survivor0区

4.若干轮Minor GC过后，此时新生代中生命周期较长的对象熬过了一定次数的Minor GC晋升成老年代移动到Old区，某轮Minor GC存活率较高Survivor区空间不足时也会将存活对象放到Old区

5.当Old区满了之后进行Major GC

增量和并发式垃圾回收

传统的垃圾回收算法都有STW的弊端，即需要在执行垃圾回收过程中需要抢占CPU，这会暂停所有的用户程序

1.通常GC任务都比较繁重，长时间暂停用户程序会影响程序的响应速度，这对于实时性要求较高的程序是致命的缺点
2.对于多核计算机而言，抢占CPU进行垃圾回收会造成计算资源浪费

增量式垃圾回收和并发式垃圾回收都是基于三色标记法和读写屏障技术的

增量式

27

增量式垃圾回收过程图如上所示，同STW垃圾回收过程相比：

优点：

1.将垃圾回收时间分摊开，避免了程序的长时间暂停，防止影响程序的实时性
缺点：

1.一方面引入了内存写屏障技术，需要额外的计算开销；另一方面由于写屏障技术的保守性导致有一些垃圾对象没有被回收，会增加一轮垃圾回收的总时长

并发式

28

同时执行

在一定程序上利用了多核计算机的优势并减少了对用户程序的干扰，不过依然无法摆脱读写屏障的额外计算开销和增加一轮垃圾回收总时长的问题

GO的GC

发展史

go v1.1：标记-清除法，整个过程都需要STW

go v1.3：标记-清除法，标记过程仍然需要STW但清除过程并行化，gc pause约几百ms

go v1.5：引入插入写屏障技术的三色标记法，仅在堆空间启动插入写屏障，全部扫描后需要STW重新扫描栈空间，gc pause耗时降到10ms以下

go v1.8：引入混合写屏障技术的三色标记法，仅在堆空间启动混合写屏障，不需要在GC结束后对栈空间重新扫描，gc pause时间降低至0.5ms以下

go v1.14：引入新的页分配器用于优化内存分配的速度

PS：gc pause时间的缩短也就意味着程序的响应速度更快

GC扫描对象

编译阶段

对静态类型做好标记准备

GO的结构体对齐规则
长度对齐

结构体的长度至少是内部最长的基础字段的整数倍

1
2
3
4
5
   type TestStruct struct {
  ptr   uintptr  // 8字节
  int1  uint32   // 4字节
  int2  uint8    // 1字节
}

这个结构体内存占用为16个字节

地址对齐

字段的地址偏移是自身长度的整数倍

1
2
3
4
5
6
7
8
9
   // 假设new一个TestStruct结构体的地址是x, 则各字段的地址如下
// ptr: a + 0
// int1: a + 8
// int2: a + 8 + 4
type TestStruct struct {
  ptr   uintptr  // 8字节
  int1  uint8    // 1字节
  int2  uint32   // 4字节
}

int1和int2之间填充了一些没使用到的内存空间，进而实现了地址对齐

指针位标记

GO的所有类型都对应一个_type结构：

1
2
3
4
5
6
7
8
type TestStruct struct {
  ptr   uintptr  // 8
  int1  uint8    // 1
  pint1 *uint8
  int2  uint32   // 4
  pint2 *uint64
  int3  uint64   // 8
}

比如上面这个结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Needs to be in sync with ../cmd/link/internal/ld/decodesym.go:/^func.commonsize,
// ../cmd/compile/internal/gc/reflect.go:/^func.dcommontype and
// ../reflect/type.go:/^type.rtype.
type _type struct {
    size       uintptr  // 类型长度，上面这个结构体的长度48个字节
    ptrdata    uintptr // 指针截止的长度位置，由于最后一个指针是pint2，因此包含指针的字段截止到40字节的位置
    hash       uint32
    tflag      tflag
    align      uint8
    fieldalign uint8
    kind       uint8  // 类型，自定义struct类型的kind为25
    alg        *typeAlg
    // gcdata stores the GC type data for the garbage collector.
    // If the KindGCProg bit is set in kind, gcdata is a GC program.
    // Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    gcdata    *byte // byte数组（*byte类型），表示指针的bitmap。比如当gcdata等于20（二进制00010100，从低位到高位就是00101000，其中每个bit表示一个指针大小（8字节）的内存，第3个bit和第5个bit为1表示第三个和第五个字段是指针类型）
    str       nameOff
    ptrToThis typeOff
}

运行阶段

golang在运行分配完内存后会调用函数heapBitsSetType，主要逻辑是根据编译期间对每个struct生成的type结构，用一个bitmap记录下来分配的内存块中哪些位置是指针

扫描阶段

1.扫描阶段从markroot开始，以栈对象、全局变量和寄存器对象作为gc root，创建一个有向引用图并将根对象添加到队列中
2.新起一个异步goroutine执行gcDrain函数，从队列里消费并扫描对象

GC实现

基于三色标记法实现的垃圾回收机制，从而将长时间的STW分隔成多段较短时间的STW的并发式回收

1.GC开始前将所有对象标记为白色

2.将GC Root对象（golang中是栈对象和全局变量的指针）加入灰色对象队列

3.使用并发的goroutine扫描队列中的指针，如果指针还引用了其他指针，那么将被引用的加入灰色对象队列，被扫描的对象标记为黑色

四个阶段

清除终止Sweep Termination

1.暂停程序

2.清扫未被回收的内存管理单元span，当上一轮GC的清扫工作完成后才可以开始新一轮的GC

标记Mark

1.切换至_GCmark，开启写屏障和用户程序协助Mutator Assiste并将根对象添加到三色标记法队列

2.恢复程序，标记进程和Mutator Assiste进程会开始并发标记内存中的对象，
混合写屏障将被删除的指针和新加入的指针都标记成灰色，新创建的对象标记成黑色

3.扫描根对象（包括所有goroutine的栈、全局对象以及不在堆中的运行时数据结构），扫描goroutine栈期间会暂停当前处理器
依次处理三色标记法队列，将扫描过的对象标记为黑色并将它们指向的对象标记成灰色

4.使用分布式终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段

标记终止Mark Termination

1.暂停程序，切换至_GCmarktermination并关闭辅助标记的用户程序

2.清理处理器上的线程缓存

清除Sweep

1.将状态切换至_GCoff，关闭混合写屏障

2.恢复用户程序，所有新创建的对象标记为白色

3.后台并发清理所有的内存管理单元span，当goroutine申请新的内存管理单元时就会触发清理

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

辅助GC

由于Golang使用了并发式的垃圾回收，将原本需要STW较长时间的GC过程分散到多次小规模的GC

当用户分配内存的速度超过GC回收速度时，Golang会通过辅助GC暂停用户程序进行垃圾回收，防止内存因分配对象速度过快消耗殆尽的问题

GC触发时机

三个前提条件：

1.允许垃圾回收

2.没有panic

3.处于Gcoff阶段

触发机制：

1.gcTriggerHeap：堆内存大小达到阈值

2.gcTriggerTime：距离上一次垃圾回收超过一定阈值时

3.gcTriggerCycle：如果当前没有启动GC则开始新一轮的GC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 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 != 0 || gcphase != _GCoff {
        return false
    }
    // 触发机制
    switch t.kind {
    case gcTriggerHeap:
        // Non-atomic access to heap_live for performance. If
        // we are going to trigger on this, this thread just
        // atomically wrote heap_live anyway and we'll see our
        // own write.
        return memstats.heap_live >= memstats.gc_trigger
    case gcTriggerTime:
        if gcpercent < 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) > 0
    }
    return true
}

GC调优

1.尽量使用小数据类型，比如使用int8代替int

2.少使用+连接string：go语言中string是一个只读类型，针对string的每一个操作都会创建一个新的string。大量小文本拼接时优先使用strings.Join，大量大文本拼接时使用bytes.Buffer