STW
STW 的全称是: Stop the World, 即在 GC 过程中的一些时刻我们需要停下所有应用程序的运行来确定引用关系.
Go 的 GC 原理图解
如果你想了解 Go 是如何进行 GC (garbage collection), 即垃圾回收的. 又在网上看了很多关于"三色标记法", 但是觉得说的非常复杂不够简单的. 那么这篇文章是你对于 Go 的 GC 机制非常好的入门参考.
这个问题是每个 Go 语言程序员在深入到一定程度后都需要了解的问题. 网上关于这个问题的文章虽多, 但是多是相互抄袭, 并且很多关键点解释含糊. 外网上有写的好的文章, 但是我想很多人无法翻墙而且阅读英文一定没有中文便于理解, 故写文档记录自己的学习笔记. 我参考过的外文资料会列在文章的最后.
什么是 GC ?
GC 是 garbage collection 的缩写, 意思是: 垃圾收集器. 在编写代码的过程中程序员写了许多 new 关键词来开创新的对象或者使用到了许多临时变量, 这些都在不断占用操作系统的内存空间. 当程序不再需要这些变量的时候(例如变量的生命周期结束时), 需要将这些内存空间重新释放出来, 以便重新分配给新的程序.
主流的高级编程语言的垃圾回收机制分为两类:
- 手动 : 比如 C++. 需要程序员手动释放自己申请的内存.
- 自动 : 比如 Java, Python, Go 等. 程序运行过程中由内存管理系统自动回收.
主流的自动回收机制又有以下两种:
- 引用计数法.
- 跟踪式垃圾回收.
Go 使用的 三色标记法 其实就属于跟踪式垃圾回收的一种. 那么 Go 是如何做到这个回收的呢? 在回收的过程中是如何保障不会错误地回收一些正在使用的对象或者变量呢? 这就是我们接下来要介绍的.
我将以下面的顺序对 GC 进行介绍:
- Mark & Sweep(标记&清扫): 基础的算法思想.
- Tri-color Mark & Sweep(三色标记&清扫): 在 Mark & Sweep 的改良, 现在 Go 正在使用的核心算法.
- Write Barrier(写屏障): 对算法正确性的保证.
- Stop the World(STW): 算法优化的核心.
现在看不懂上面的词汇是什么意思没有关系, 列出来主要是为了有一个初步的印象.
Mark & Sweep
Mark & Sweep 是 Go 语言三色标记法的一个基础, 中文又叫做: 标记-清扫. 我们先来了解一下 Mark & Sweep 的一些基础概念.
这是 GC 的算法优化的重点, 因为应用程序停止的时间越长, 意味着该语言的性能越不好.
根对象(Root)
根对象是指不需要通过其他对象就可以直接访问到的对象. 主要包括以下三种:
- 全局对象.
- 栈中对象.
- 堆中对象.
整个进程空间里申请每个对象占据的内存可以视为一个树, 对象之间的引用被视为树中节点之间的关联, 而这颗树的根节点即我们此处说的根对象. 三色标记法就是根对象出发, 通过对象的引用和指针, 深度优先地遍历这颗引用树, 不断追踪其他的存活对象的. 在下面会有具体的讲解.
在了解完基础概念之后, 我们回头来看一下这个 Mark & Sweep 是如何实现的.
- Stop the World.
- Mark: 通过 Root 不断递归寻找可达的对象并标记为活跃.
- Sweep: 对对象迭代, 将Mark阶段未标记的对象(即不活跃的对象)加入 freelist, 可用于再一次分配.
- Start the World.
注意
非常明显, 算法最大的问题就是 GC 期间要把整个程序完全暂停. 在 Go 1.1版本中, STW 的时间可能达到秒级, 对于有高并发和吞吐量需求的系统是不能容忍的.
但是标记过程需要 STW 是因为, 如果在标记对象是否活跃期间如果程序未停止仍在运行, 则可能会出现引用关系在标记阶段做了修改的情况, 导致标记结果的不正确.
Go 中 GC 的演变
- 1.3 以前的版本使用标记-清扫方式, 整个过程都需要 STW.
- 1.3 版本中分离了标记和清扫的操作, 仅仅标记的过程 STW, 而清扫的过程使用并发执行.
- 1.5 版本在标记过程使用三色标记法, 标记和清扫都并发执行. 但是标记阶段的前后需要 STW 一定的时间来做 GC 的准备工作和栈的 re-scan.
Tri-color Mark & Sweep
在理解了 Mark & Sweep 算法的基础上, 现在我们来看一下整个 Go 的 GC 机制的核心算法: 三色标记法.
三色 是指将对象标记为以下三种颜色来进行区分:
- 白色 : 潜在垃圾.
- 黑色 : 活跃的对象, 包括不存在任何外部指针的对象和从根节点可达的对象.
- 灰色: 活跃对象, 但是存在指向白色对象的外部指针.
算法的初始将会把所有的对象都视为白色, 在迭代的过程中逐渐对对象进行"染色". 在标记算法结束时, 只会存在黑色节点和白色节点, 而 Go 将会回收所有的白色对象.
我们可以将算法归结为以下三个步骤:
步骤一
从灰色对象的集合中选择一个灰色对象并将其标记成黑色
步骤二
将黑色对象指向的所有对象都标记成灰色, 保证该对象和被该对象引用的对象都不会被回收
步骤三
重复上述两个步骤直到对象图中不存在灰色对象
算法的伪代码如下:
# 维护黑白灰三个集合来存储不同颜色的对象
whiteSet = {A,B,C,D,E,F,G,H}
greySet = {}
blackSet = {}
# 将根节点可访问到的对象从白色变为灰色. 注意: 此步骤不会递归执行.
whiteSet.remove(root.reference)
greySet.add(root.reference)
while True:
for greyObject in greySet:
# 如果灰色节点有指向其他对象的指针的话
if greyObject.reference:
# 将当前的灰色对象染成黑色
greySet.remove(greyObject)
blackSet.add(greyObject)
# 将灰色节点指向的白色对象染成灰色
whiteSet.remove(greyObject.reference)
greySet.add(greyObject.reference)
# 当全局所有对象都遍历过时, 算法结束
if greySet is empty:
break伪代码可以配合下面的这个例子来看, 下图展示了算法在执行过程中的 4 次迭代的结果:
- 根据步骤一: 因为从栈上的根节点可以访问到
A对象, 从堆上的根节点可以访问到F对象, 则将A和F置灰. - 根据步骤二: 从所有的灰色对象集合中选择一个灰色对象并将其标记成黑色, 即将
A置为黑色并将其引用的对象B置为灰色. - 根据重复上面的步骤二, 把
B置为黑色并将其引用的对象C和E置为灰色.
最后整个从栈和堆的根结点上建立的这颗引用树上的所有节点都被遍历到后, 会被标记成下面这个样子:
在 Go 1.5 版本中标记和清扫是并发执行的, 也就是多个应用程序和标记并发执行. 想要在并发中保证标记的正确性, 我们需要达到以下两种 三色不变性(Tri-color invariant) 中的任意一种:
- 强三色不变性 : 黑色对象不会指向白色对象, 只会指向灰色对象或灰色对象.
- 弱三色不变性 : 黑色对象指向白色对象必须包含一条从灰色对象经由多个白色对象到达的路线.
为了更好地理解这两种三色不变性, 我们来看下面这个例子:
在左侧的图体现了强三色不变性, 在右侧的图体现了弱三色不变性.
我们先来看左侧的强三色不变性. 考虑这样一种情况: 如果我们在Mark阶段不进行 STW, 则可能在标记的过程中程序运行时添加了一条 的指针( 注意: 这次指针的添加破坏了强三色不变性 ). 但是此时 A 已经被执行 Mark 任务的 goroutine 所访问过并且已经标记成黑色, 按照三色标记的算法, 每次只会从灰色节点出发对灰色节点的引用进行访问和染色, 则意味着 D 不会被访问且在算法结束时 D 仍然会保持白色. 此时就会出现活跃对象 A 直接引用了 D, 但是 D 却被误认为了垃圾而被回收. 回收了仍然在被使用的对象会导致程序的致命错误, 是 GC 所不能接受的. 那么强三色不变性的意义就在于: 通过保证活跃节点(即黑色节点)到可能未访问的节点(即白色节点)的直接路径的有效性, 我们可以避免上述情况的发生.
我们再来看右侧的弱三色不变性. 考虑这样一种情况: 我们在Mark阶段不进行 STW, 则可能在标记的过程中程序运行时添加了一条 的指针. 虽然打破了强三色不变性, 我们从黑色节点 A 无法访问到 D. 但是由于有一条从灰色 B 通往 D 的路线 , 节点 D 仍然会被访问并染色, 不会造成 D 的错误回收. 所以弱三色不变性的意义在于: 通过保证黑色节点到白色节点的间接路径来保证 Mark 的正确性.
通过上面的两个例子我们看到, 遵循上述两个不变性中的任意一个都可以保证垃圾回收算法在不进行 STW, 也就是并发执行的场景下的正确性. 那么如果保证这两种不变性中的任意一种呢? 这就要涉及到接下来的一种技术: Write Barrier - 写屏障.
Write Barrier
在这里我将介绍两种写屏障技术, 分别是 Dijkstra 提出的 插入写屏障 和 Yuasa 提出的 删除写屏障. 这两种写屏障技术分别保证了强三色不变性和弱三色不变性.
插入写屏障
Dijkstra 在 1978 年提出了插入写屏障, 能够保证用户程序和垃圾收集器在交替工作的情况下保证程序执行的正确性. 以下是其伪代码:
writePointer(slot, ptr):
shade(ptr)
*slot = ptr该段代码像是一个钩子方法, 在每次用户程序更新对象指针时都会被执行. 伪代码中的两个参数 slot 和 ptr 分别标识当前的变量和指针需要指向的变量. shade() 函数表示染色. 意味着每当我们执行类似 *slot = ptr 的表达式来更新对象指针时, 写屏障会通过 shade 函数来尝试改变指针的颜色. 如果新指针 ptr 是白色的, 会将其染成灰色. 下图很好地表示了这个过程, 当增加一条 的指针时, 写屏障将白色的 C 染成了灰色.
- 垃圾收集器将根对象指向
A对象标记成黑色并将A对象指向的对象B标记成灰色. - 用户程序修改
A对象的指针, 将原本指向B对象的指针指向C对象, 这时触发写屏障将C对象标记成灰色. - 垃圾收集器依次遍历程序中的其他灰色对象, 将它们分别标记成黑色.
Dijkstra 的插入写屏障是一种相对保守的屏障技术, 它会将有存活可能的对象都标记成灰色以满足强三色不变性. 但是缺点也是非常明显的.
插入写屏障的缺点
- 复杂度高. 流程代码会比较复杂.
- 性能较低. 栈上的对象由于局部性原则短时间内会多次访问或更改指针, 会频繁出发写屏障.
为了弥补性能低的问题, Go 选择仅仅对堆上的指针插入写屏障(因为堆上一般放置的是大型对象、全局变量或者静态变量, 变动不频繁. 而栈上一般存放的是局部变量或参数, 会频繁变动). 但是这样会导致扫描结束后栈上仍然存在引用白色对象的现象. 所以为了保证算法的正确性, 此时进行 STW 然后重新扫描栈使其变黑. 这个过程就叫做 re-scan. 此时整个算法的过程会变成:
- 初始化 GC 任务: 包括开启写屏障和开启辅助 GC , 统计 root 对象的任务数量等. 此过程 STW.
- 扫描所有 root 对象, 包括全局指针和 goroutine 栈上的指针(扫描某个 goroutine 时该 goroutine 停止), 将其加入灰色队列, 并循环灰色队列直至其为空. 此过程后台并行执行.
- 重新扫描全局指针和栈(re-scan). 此过程 STW.
- 按照标记回收所有白色对象. 此过程后台并行执行.
删除写屏障
Yuasa 在 1990 年提出了删除写屏障. 伪代码如下:
writePointer(slot, ptr)
if (isGrey(slot) || isWhite(slot))
shade(*slot)
*slot = ptr上述代码会在老对象的引用被删除时, 将白色的老对象涂成灰色, 以保证弱三色不变性.
- 将根对象
A标记为黑色, 将A指向的对象B标记为灰色. - 用户程序将
A原本指向B的指针改为指向C, 即删除了一个指针又新增了一个指针. 此时 触发删除写屏障, 但是因为B本身是灰色所以不做任何改变. - 用户程序将原本
B指向C的指针删除. 此时 触发删除写屏障, 白色的C被涂成灰色. - 垃圾收集器遍历其他对象并分别标记成黑色, 算法结束.
删除写屏障的缺点
- 精度不高. 一个对象即使被删除了最后一个指向它的指针依旧可以活过本次循环, 只能在下一轮循环中被 GC 清理掉.
混合写屏障
插入屏障和删除屏障都各有优缺点. 插入写屏障在开始时无需 STW, 但是结束时需要 STW 来 re-scan. 删除写屏障需要在开始时 STW 扫描栈来记录初始快照, 但是结束时无需 STW. 而混合写屏障则是结合了这两种方法的特点, 满足的是变形的弱三色不变性: 允许黑色对象引用白色对象, 白色对象处于灰色保护状态, 但是只由堆上的灰色对象保护. 伪代码如下:
writePointer(slot, ptr):
shade(*slot)
if current stack is grey:
shade(ptr)
*slot = ptr混合屏障只需要在开始时并发扫描各个 goroutine 的栈, 使其变黑并一直保持(该过程无需 STW). 而标记结束后, 因为栈一直是黑色的, 所以也无需 STW 进行 re-scan. 这样大大减少了 STW 的时间. 但是标记阶段的前后需要 STW 一定的时间来做 GC 的准备工作.
Sweep
Sweep 是清扫阶段, 会让 Go 知道哪些内存可以重新分配使用.
在 Sweep 过程中并不会去真正将内存清零(zeroing the memory), 而是在分配重新使用的时候重新 reset bit. GC 会使用位图 gcmarkBits 来跟踪正在使用的内存(1:存活; 2:回收), Sweep 只是对位图进行置 1 或置 0.
Go 提供两种策略:
- 后台启动一个专门的worker等待清理内存.
- 当申请分配内存时lazy触发.
STW
Stop the World 是 GC 机制中一个重要的阶段, 当前运行的所有程序被暂停, 扫描内存的 root 节点并添加写屏障.
所有的处理器P都会被标记成停止状态(stopped), 不再运行任何代码. 调度器会把每个处理器M从各自队形的处理器P中分离出来放入 idle 列表中去.
Pacing
这是一个可配置的关于 GC 的参数. 表示下一次垃圾手机必须启动之前可以分配多少新内存的比例. 默认情况下为 100, 即下一次 GC 前可以分配 100% 的内存.
当然, 这个参数只能一定程度上影响 GC. 如果超过2分钟没有触发, Go 会强制触发 GC.
