Levon's Blog

微信: L6241425

0%

golang的GC垃圾回收

发表于 更新于 分类于 ， ， 阅读次数： Valine：
本文字数： 5k 阅读时长 ≈ 5 分钟

1. 常见的GC算法

GC 是一种自动管理内存的技术，用来回收（释放） heap 中不再使用的对象。GC 过程中涉及到两个阶段：

  1. 区分活对象（live object）与垃圾对象（garbage）
  2. 回收垃圾对象的内存，使得程序可以重复使用这些内存

1.1 引用计数（Reference counting）

根据对象自身的引用计数来回收，当引用计数归零时进行回收，但是计数频繁更新会带来更多开销，且无法解决循环引用的问题。

  • 优点：简单直接，回收速度快
  • 缺点：需要额外的空间存放计数，无法处理循环引用的情况；

1.2 追踪技术（Tracing）

这是目前使用范围最广的技术，一般我们提到 GC 都是指这类。

这类 GC 从某些被称为 root 的对象开始，不断追踪可以被引用到的对象，这些对象被称为可到达的（reachable），其他剩余的对象就被称为 garbage，并且会被释放。

1. 标记清除

标记出所有不需要回收的对象，在标记完成后统一回收掉所有未被标记的对象。

  • 优点：简单直接，速度快，适合可回收对象不多的场景。
  • 缺点：每次启动垃圾回收都会暂停当前所有的正常代码执行，回收是系统响应能力大大降低。标记需要扫描整个heap，清除数据会产生heap碎片。
2. 复制收集

复制法将内存分为大小相同的两块，每次使用其中的一块，当这一块的内存使用完后，将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉。

  • 优点：解决了内存碎片的问题，每次清除针对的都是整块内存，但是因为移动对象需要耗费时间，效率低于标记清除法；
  • 缺点：有部分内存总是利用不到，资源浪费，移动存活对象比较耗时，并且如果存活对象较多的时候，需要担保机制确保复制区有足够的空间可完成复制；
3. 标记整理

标记过程同标记清除法，结束后将存活对象压缩至一端，然后清除边界外的内容。

  • 优点：解决了内存碎片的问题。
  • 缺点：性能低，因为在移动对象的时候不仅需要移动对象还要维护对象的引用地址，可能需要对内存经过几次扫描才能完成；
4. 分代式

将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。

分配对象的时候从新生代里面分配，如果后面发现对象的生命周期较长，则将其移到老年代，这个过程叫做 promote。随着不断 promote，最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高，STW 时间也会更短。

2. Golang的GC

2.1 版本演变

GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低。

GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通。

GoV1.8- 三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。

2.2 Go V1.3 的标记清除

1. 具体步骤

第一步，暂停程序业务逻辑，分类出可达和不可达的对象，然后做上标记。目前程序的可达对象有对象 1-2-3，对象 4-7 等五个对象。

img

第二步 , 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示：

img

第三步 , 标记完了之后，然后开始清除未标记的对象。结果如下。

img

操作非常简单，但是有一点需要额外注意：mark and sweep 算法在执行的时候，需要程序暂停！即 STW(stop the world)，STW 的过程中，CPU 不执行用户代码，全部用于垃圾回收，这个过程的影响很大，所以 STW 也是一些回收机制最大的难题和希望优化的点。所以在执行第三步的这段时间，程序会暂定停止任何工作，卡在那等待回收执行完毕。

第四步 , 停止暂停，让程序继续跑。然后循环重复这个过程，直到 process 程序生命周期结束。

2. 缺点
  • STW，stop the world；让程序暂停，程序出现卡顿 (重要问题)；
  • 标记需要扫描整个 heap；
  • 清除数据会产生 heap 碎片。
img

Go V1.3 做了简单的优化，将 STW 的步骤提前，减少 STW 暂停的时间范围。如下所示

img

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

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

2.3 Go V1.5 的三色标记

Golang 中的垃圾回收主要应用三色标记法，GC 过程和其他用户 goroutine 可并发运行，但需要一定时间的 STW(stop the world)。

1. 具体步骤
  • 第一步 , 每次新创建的对象，默认的颜色都是标记为 “白色”，如图所示。
img

我们的程序可抵达的内存对象关系如左图所示，右边的标记表，是用来记录目前每个对象的标记颜色分类。这里面需要注意的是，所谓 “程序”，则是一些对象的跟节点集合。所以我们如果将 “程序” 展开，会得到类似如下的表现形式，如下图所示。

img
  • 第二步, 每次 GC 回收开始，会从根节点开始遍历所有对象，把遍历到的对象从白色集合放入 “灰色” 集合如图所示。
img

这里 要注意的是，本次遍历是一次遍历，非递归形式，是从程序抽次可抵达的对象遍历一层，如上图所示，当前可抵达的对象是对象 1 和对象 4，那么自然本轮遍历结束，对象 1 和对象 4 就会被标记为灰色，灰色标记表就会多出这两个对象。

  • 第三步 , 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象变黑放入黑色集合，如图所示。
img

这一次遍历是只扫描灰色对象，将灰色对象的第一层遍历可抵达的对象由白色变为灰色，如：对象 2、对象 7. 而之前的灰色对象 1 和对象 4 则会被标记为黑色，同时由灰色标记表移动到黑色标记表中。

  • 第四步 , 重复第三步 , 直到灰色中无任何对象，如图所示。
img img

当我们全部的可达对象都遍历完后，灰色标记表将不再存在灰色对象，目前全部内存的数据只有两种颜色，黑色和白色。那么黑色对象就是我们程序逻辑可达（需要的）对象，这些数据是目前支撑程序正常业务运行的，是合法的有用数据，不可删除，白色的对象是全部不可达对象，目前程序逻辑并不依赖他们，那么白色对象就是内存中目前的垃圾数据，需要被清除。

  • 第五步: 回收所有的白色标记表的对象。也就是回收垃圾，如图所示。

以上我们将全部的白色对象进行删除回收。

img

剩下的就是全部依赖的黑色对象。

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

如果不进行 STW，如下并发情况下，会误删白色对象。

  • 条件 1: 一个白色对象被黑色对象引用 (白色被挂在黑色下)
  • 条件 2: 灰色对象与它之间的可达关系的白色对象遭到破坏 (灰色同时丢了该白色)

3. 屏障机制介绍

我们让 GC 回收器，满足下面两种情况之一时，即可保对象不丢失。 这两种方式就是 “强三色不变式” 和 “弱三色不变式”。

3.1 不变式

1. 强三色不变式

强三色不变色实际上是强制性的不允许黑色对象引用白色对象，这样就不会出现有白色对象被误删的情况。

img
2. 弱三色不变式

弱三色不变式强调，黑色对象可以引用白色对象，但是这个白色对象必须存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。 这样实则是黑色对象引用白色对象，白色对象处于一个危险被删除的状态，但是上游灰色对象的引用，可以保护该白色对象，使其安全。

为了遵循上述的两个方式，GC 算法演进到两种屏障方式，他们 “插入屏障”, “删除屏障”。

img

3.2 写屏障

1. 插入写屏障（插入变灰）
  • 在 A 对象引用 B 对象的时候，B 对象被标记为灰色。(将 B 挂在 A 下游，B 必须被标记为灰色)
  • 满足强三色不变式。 (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)

栈空间的特点是容量小，但是要求相应速度快，因为函数调用弹出频繁使用，所以 “插入屏障” 机制，在栈空间的对象操作中不使用， 而仅仅使用在堆空间对象的操作中。

img img img img img img

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

img img img

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

img
2. 删除写屏障（删除变灰）
  • 被删除的对象，如果自身为白色或灰色，那么被标记为灰色。
  • 满足弱三色不变式。(保护灰色对象到白色对象的路径不会断)
img img img img img img img

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

3.3 Go V1.8 的混合写屏障机制

1. 插入写屏障和删除写屏障的短板
  • 插入写屏障：结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；
  • 删除写屏障：回收精度低，GC 开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

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

2. 混合写屏障规则

1、GC 开始将栈上的对象全部扫描，可达的标记为黑色 (之后不再进行第二次重复扫描，无需 STW)

2、GC 期间，任何在栈上创建的新对象，均为黑色。

3、堆空间被删除的对象标记为灰色。

4、堆空间被添加的对象标记为灰色。

有人，栈上一直是黑色的对象，那么不就永远清除不掉了么。这里强调一下，标记为黑色的是可达对象，不可达的对象一直会是白色，直到最后被回收。

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

混合写屏障是 GC 的一种屏障机制，所以只是当程序执行 GC 的时候，才会触发这种机制。

4. 何时触发 GC

  • 主动触发：调用 runtime.GC()，这是阻塞式的。

  • 百分比被动触发：在堆上分配大于 32K byte 对象的时候，检测此时是否满足垃圾回收条件，如果满足则进行垃圾回收。默认情况下为 100，即堆内存相比上次垃圾收集增长 100% 时应该触发 GC

  • 定时被动触发： 如果超过两分钟没有 GC，则触发 GC。监控函数是 sysmon()，在主 goroutine 中启动。

5. 头脑风暴

  • golang1.3之前是标记清扫，先标记再清扫，会STW，程序停止影响效率。
  • golang1.5加入三色标记和堆的写屏障，gc和gorutine可以并发，但是会堆栈标记进行STW。三色是先白，变灰，后黑。
  • 首先默认全是白色，根节点扫到就变灰。只扫一层不是递归的扫，然后开始扫灰色，把扫到的也变灰，自己变黑。流程一直循环，直到全部变黑。白色的被清理。（缺点是扫的时候需要STW，扫完后再解除）
  • 插入写屏障：在GC过程中，堆空间新创建的直接灰色。
  • 删除写屏障：在GC过程中，删除的如果是白色直接变灰。
  • 混合写屏障: GC刚开始，堆空间删除变灰，添加也变灰。栈上全部黑色，添加全是黑色(栈其实没启用屏障)。
  • 何时触发GC: 1: 主动触发，runtime.GC 2：被动触发: 在堆上分配32KB的时候就检查上次超过100% 3: 两分钟一次GC。

6. 参考资料

可以加首页作者微信，咨询相关问题！