STW
STW 的全称是: Stop the World, 即在 GC 过程中的一些时刻我们需要停下所有应用程序的运行来确定引用关系.
如果你想了解 Go 是如何进行 GC (garbage collection), 即垃圾回收的. 又在网上看了很多关于"三色标记法", 但是觉得说的非常复杂不够简单的. 那么这篇文章是你对于 Go 的 GC 机制非常好的入门参考.
这个问题是每个 Go 语言程序员在深入到一定程度后都需要了解的问题. 网上关于这个问题的文章虽多, 但是多是相互抄袭, 并且很多关键点解释含糊. 外网上有写的好的文章, 但是我想很多人无法翻墙而且阅读英文一定没有中文便于理解, 故写文档记录自己的学习笔记. 我参考过的外文资料会列在文章的最后.
GC 是 garbage collection 的缩写, 意思是: 垃圾收集器. 在编写代码的过程中程序员写了许多 new
关键词来开创新的对象或者使用到了许多临时变量, 这些都在不断占用操作系统的内存空间. 当程序不再需要这些变量的时候(例如变量的生命周期结束时), 需要将这些内存空间重新释放出来, 以便重新分配给新的程序.
主流的高级编程语言的垃圾回收机制分为两类:
主流的自动回收机制又有以下两种:
Go 使用的 三色标记法 其实就属于跟踪式垃圾回收的一种. 那么 Go 是如何做到这个回收的呢? 在回收的过程中是如何保障不会错误地回收一些正在使用的对象或者变量呢? 这就是我们接下来要介绍的.
我将以下面的顺序对 GC 进行介绍:
现在看不懂上面的词汇是什么意思没有关系, 列出来主要是为了有一个初步的印象.
Mark & Sweep 是 Go 语言三色标记法的一个基础, 中文又叫做: 标记-清扫. 我们先来了解一下 Mark & Sweep 的一些基础概念.
STW
STW 的全称是: Stop the World, 即在 GC 过程中的一些时刻我们需要停下所有应用程序的运行来确定引用关系.
这是 GC 的算法优化的重点, 因为应用程序停止的时间越长, 意味着该语言的性能越不好.
根对象(Root)
根对象是指不需要通过其他对象就可以直接访问到的对象. 主要包括以下三种:
整个进程空间里申请每个对象占据的内存可以视为一个树, 对象之间的引用被视为树中节点之间的关联, 而这颗树的根节点即我们此处说的根对象. 三色标记法就是根对象出发, 通过对象的引用和指针, 深度优先地遍历这颗引用树, 不断追踪其他的存活对象的. 在下面会有具体的讲解.
在了解完基础概念之后, 我们回头来看一下这个 Mark & Sweep 是如何实现的.
注意
非常明显, 算法最大的问题就是 GC 期间要把整个程序完全暂停. 在 Go 1.1 版本中, STW 的时间可能达到秒级, 对于有高并发和吞吐量需求的系统是不能容忍的.
但是标记过程需要 STW 是因为, 如果在标记对象是否活跃期间如果程序未停止仍在运行, 则可能会出现引用关系在标记阶段做了修改的情况, 导致标记结果的不正确.
在理解了 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→D 的指针( 注意: 这次指针的添加破坏了强三色不变性 ). 但是此时 A
已经被执行 Mark 任务的 goroutine 所访问过并且已经标记成黑色. 按照三色标记的算法, 每次只会从灰色节点出发对灰色节点的引用进行访问和染色, 则意味着 D
不会被访问且在算法结束时 D
仍然会保持白色. 此时就会出现活跃对象 A
直接引用了 D
, 但是 D
却被误认为了垃圾而被回收. 回收了仍然在被使用的对象会导致程序的致命错误, 是 GC 所不能接受的. 那么强三色不变性的意义就在于: 通过保证活跃节点(即黑色节点)到可能未访问的节点(即白色节点)的直接路径的有效性, 我们可以避免上述情况的发生.
我们再来看右侧的弱三色不变性. 考虑这样一种情况: 我们在 Mark 阶段不进行 STW, 则可能在标记的过程中程序运行时添加了一条 A→D 的指针. 虽然打破了强三色不变性, 我们从黑色节点 A
无法访问到 D
. 但是由于有一条从灰色 B
通往 D
的路线 B→E→D, 节点 D
仍然会被访问并染色, 不会造成 D
的错误回收. 所以弱三色不变性的意义在于: 通过保证黑色节点到白色节点的间接路径来保证 Mark 的正确性.
通过上面的两个例子我们看到, 遵循上述两个不变性中的任意一个都可以保证垃圾回收算法在不进行 STW, 也就是并发执行的场景下的正确性. 那么如果保证这两种不变性中的任意一种呢? 这就要涉及到接下来的一种技术: Write Barrier - 写屏障.
在这里我将介绍两种写屏障技术, 分别是 Dijkstra 提出的 插入写屏障 和 Yuasa 提出的 删除写屏障. 这两种写屏障技术分别保证了强三色不变性和弱三色不变性.
Dijkstra 在 1978 年提出了插入写屏障, 能够保证用户程序和垃圾收集器在交替工作的情况下保证程序执行的正确性. 以下是其伪代码:
writePointer(slot, ptr):
shade(ptr)
*slot = ptr
该段代码像是一个钩子方法, 在每次用户程序更新对象指针时都会被执行. 伪代码中的两个参数 slot
和 ptr
分别标识当前的变量和指针需要指向的变量. shade()
函数表示染色. 意味着每当我们执行类似 *slot = ptr
的表达式来更新对象指针时, 写屏障会通过 shade
函数来尝试改变指针的颜色. 如果新指针 ptr
是白色的, 会将其染成灰色. 下图很好地表示了这个过程, 当增加一条 A→C 的指针时, 写屏障将白色的 C
染成了灰色.
A
对象标记成黑色并将 A
对象指向的对象 B
标记成灰色.A
对象的指针, 将原本指向 B
对象的指针指向 C
对象, 这时触发写屏障将 C
对象标记成灰色.Dijkstra 的插入写屏障是一种相对保守的屏障技术, 它会将有存活可能的对象都标记成灰色以满足强三色不变性. 但是缺点也是非常明显的.
插入写屏障的缺点
为了弥补性能低的问题, Go 选择仅仅对堆上的指针插入写屏障(因为堆上一般放置的是大型对象、全局变量或者静态变量, 变动不频繁. 而栈上一般存放的是局部变量或参数, 会频繁变动). 但是这样会导致扫描结束后栈上仍然存在引用白色对象的现象. 所以为了保证算法的正确性, 此时进行 STW 然后重新扫描栈使其变黑. 这个过程就叫做 re-scan. 此时整个算法的过程会变成:
Yuasa 在 1990 年提出了删除写屏障. 伪代码如下:
writePointer(slot, ptr)
if (isGrey(slot) || isWhite(slot))
shade(*slot)
*slot = ptr
上述代码会在老对象的引用被删除时, 将白色的老对象涂成灰色, 以保证弱三色不变性.
A
标记为黑色, 将 A
指向的对象 B
标记为灰色.A
原本指向 B
的指针改为指向 C
, 即删除了一个指针又新增了一个指针. 此时 触发删除写屏障, 但是因为 B
本身是灰色所以不做任何改变.B
指向 C
的指针删除. 此时 触发删除写屏障, 白色的 C
被涂成灰色.删除写屏障的缺点
插入屏障和删除屏障都各有优缺点. 插入写屏障在开始时无需 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 是清扫阶段, 会让 Go 知道哪些内存可以重新分配使用.
在 Sweep 过程中并不会去真正将内存清零(zeroing the memory), 而是在分配重新使用的时候重新 reset bit. GC 会使用位图 gcmarkBits 来跟踪正在使用的内存(1:存活; 2:回收), Sweep 只是对位图进行置 1 或置 0.
Go 提供两种策略:
Stop the World 是 GC 机制中一个重要的阶段, 当前运行的所有程序被暂停, 扫描内存的 root 节点并添加写屏障.
所有的处理器 P 都会被标记成停止状态(stopped), 不再运行任何代码. 调度器会把每个处理器 M 从各自队形的处理器 P 中分离出来放入 idle 列表中去.
这是一个可配置的关于 GC 的参数. 表示下一次垃圾手机必须启动之前可以分配多少新内存的比例. 默认情况下为 100, 即下一次 GC 前可以分配 100% 的内存.
当然, 这个参数只能一定程度上影响 GC. 如果超过2分钟没有触发, Go 会强制触发 GC.
docs: update docs
于 2024/12/2docs: update docs
于 2024/11/19整理图片和文章
于 2024/11/7整理文章格式
于 2024/10/29整理文章格式
于 2024/10/25整理文章格式
于 2024/10/25升级主题+新增文章+修改格式
于 2024/10/14升级版本+规整文档中的格式
于 2024/10/11整理图片格式和名称(not finished)
于 2024/9/30增加头图配置并为首页features增加link
于 2024/9/29给予文件夹顺序
于 2024/9/24调整博客分类+修改about-me.md
于 2024/9/24first commit
于 2024/9/20