如果你想了解Go是如何进行GC(garbage collection), 即垃圾回收的. 又在网上看了很多关于"三色标记法", 但是觉得说的非常复杂不够简单的. 那么这篇文章是你对于Go的GC机制非常好的入门参考.

mutator: 应用程序; allocator: 分配器; collector: 垃圾回收器

这个问题是每个Go语言程序员在深入到一定程度后都需要了解的问题. 网上关于这个问题的文章虽多, 但是多是相互抄袭, 并且很多关键点解释含糊. 外网上有写的好的文章, 但是我想很多人无法翻墙而且阅读英文一定没有中文便于理解, 故写文档记录自己的学习笔记. 我参考过的外文资料会列在文章的最后.

什么是GC?

GC是 garbage collection 的缩写, 意思是: 垃圾收集器. 在编写代码的过程中程序员写了许多new关键词来开创新的对象或者使用到了许多临时变量, 这些都在不断占用操作系统的内存空间. 当程序不再需要这些变量的时候(例如变量的生命周期结束时), 需要将这些内存空间重新释放出来, 以便重新分配给新的程序.

主流的高级编程语言的垃圾回收机制分为两类

1. 手动 : 比如C++. 需要程序员手动释放自己申请的内存.
2. 自动 : 比如Java, Python, Go等. 程序运行过程中由内存管理系统自动回收.

主流的自动回收机制又有以下两种:

1. 引用计数法
2. 跟踪式垃圾回收

Go使用的 三色标记法 其实就属于跟踪式垃圾回收的一种. 那么Go是如何做到这个回收的呢? 在回收的过程中是如何保障不会错误地回收一些正在使用的对象或者变量呢? 这就是我们接下来要介绍的.

我将以下面的顺序对GC进行介绍:

1. Mark & Sweep(标记&清扫): 基础的算法思想
2. Tri-color Mark & Sweep(三色标记&清扫): 在Mark & Sweep的改良, 现在Go正在使用的核心算法
3. Write Barrier(写屏障): 对算法正确性的保证
4. Stop the World(STW): 算法优化的核心

现在看不懂上面的词汇是什么意思没有关系, 列出来主要是为了有一个初步的印象.

Mark & Sweep

Mark & Sweep是Go语言三色标记法的一个基础, 中文又叫做: 标记-清扫. 我们先来了解一下Mark & Sweep的一些基础概念.

STW

STW的全称是: Stop the World, 即在GC过程中的一些时刻我们需要停下所有应用程序的运行来确定引用关系.

这是GC的算法优化的重点, 因为应用程序停止的时间越长, 意味着该语言的性能越不好.

根对象(Root)

根对象是指不需要通过其他对象就可以直接访问到的对象. 主要包括以下三种:

1. 全局对象
2. 栈中对象
3. 堆中对象

整个进程空间里申请每个对象占据的内存可以视为一个树, 对象之间的引用被视为树中节点之间的关联, 而这颗树的根节点即我们此处说的根对象. 三色标记法就是根对象出发, 通过对象的引用和指针, 深度优先地遍历这颗引用树, 不断追踪其他的存活对象的. 在下面会有具体的讲解.

在了解完基础概念之后, 我们回头来看一下这个Mark & Sweep是如何实现的.

1. Stop the World
2. Mark: 通过Root不断递归寻找可达的对象并标记为活跃
3. Sweep: 对对象迭代, 将Mark阶段未标记的对象(即不活跃的对象)加入freelist, 可用于再一次分配
4. Start the World

注意

非常明显, 算法最大的问题就是GC期间要把整个程序完全暂停. 在Go1.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机制的核心算法: 三色标记法.

三色 是指将对象标记为以下三种颜色来进行区分:

1. 白色 : 潜在垃圾.
2. 黑色 : 活跃的对象, 包括不存在任何外部指针的对象和从根节点可达的对象.
3. 灰色: 活跃对象, 但是存在指向白色对象的外部指针.

三色对象

算法的初始将会把所有的对象都视为白色, 在迭代的过程中逐渐对对象进行"染色". 在标记算法结束时, 只会存在黑色节点和白色节点, 而Go将会回收所有的白色对象.

我们可以将算法归结为以下三个步骤:

1. 步骤一

   从灰色对象的集合中选择一个灰色对象并将其标记成黑色

2. 步骤二

   将黑色对象指向的所有对象都标记成灰色, 保证该对象和被该对象引用的对象都不会被回收

3. 步骤三

   重复上述两个步骤直到对象图中不存在灰色对象

算法的伪代码如下:

# 维护黑白灰三个集合来存储不同颜色的对象
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次迭代的结果:

三色标记清扫

1. 根据步骤一: 因为从栈上的根节点可以访问到A对象, 从堆上的根节点可以访问到F对象, 则将A和F置灰.
2. 根据步骤二: 从所有的灰色对象集合中选择一个灰色对象并将其标记成黑色, 即将A置为黑色并将其引用的对象B置为灰色
3. 根据重复上面的步骤二, 把B置为黑色并将其引用的对象C和E置为灰色

最后整个从栈和堆的根结点上建立的这颗引用树上的所有节点都被遍历到后, 会被标记成下面这个样子:

三色标记清扫后

在Go1.5版本中标记和清扫是并发执行的, 也就是多个应用程序和标记并发执行. 想要在并发中保证标记的正确性, 我们需要达到以下两种 三色不变性(Tri-color invariant) 中的任意一种:

1. 强三色不变性 : 黑色对象不会指向白色对象, 只会指向灰色对象或灰色对象.
2. 弱三色不变性 : 黑色对象指向白色对象必须包含一条从灰色对象经由多个白色对象到达的路线.

为了更好地理解这两种三色不变性, 我们来看下面这个例子:

强三色不变性

在左侧的图体现了强三色不变性, 在右侧的图体现了弱三色不变性.

我们先来看左侧的强三色不变性. 考虑这样一种情况: 如果我们在Mark阶段不进行STW, 则可能在标记的过程中程序运行时添加了一条 $A \rightarrow D$ 的指针( 注意: 这次指针的添加破坏了强三色不变性 ). 但是此时A已经被执行Mark任务的goroutine所访问过并且已经标记成黑色, 按照三色标记的算法, 每次只会从灰色节点出发对灰色节点的引用进行访问和染色, 则意味着D不会被访问且在算法结束时D仍然会保持白色. 此时就会出现活跃对象A直接引用了D, 但是D却被误认为了垃圾而被回收. 回收了仍然在被使用的对象会导致程序的致命错误, 是GC所不能接受的. 那么强三色不变性的意义就在于: 通过保证活跃节点(即黑色节点)到可能未访问的节点(即白色节点)的直接路径的有效性, 我们可以避免上述情况的发生.

我们再来看右侧的弱三色不变性. 考虑这样一种情况: 我们在Mark阶段不进行STW, 则可能在标记的过程中程序运行时添加了一条 $A \rightarrow D$ 的指针. 虽然打破了强三色不变性, 我们从黑色节点A无法访问到D. 但是由于有一条从灰色B通往D的路线 $B \rightarrow E \rightarrow 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是白色的, 会将其染成灰色. 下图很好地表示了这个过程, 当增加一条 $A \rightarrow C$ 的指针时, 写屏障将白色的C染成了灰色.

Dijkstra写屏障

1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色
2. 用户程序修改 A 对象的指针, 将原本指向 B 对象的指针指向 C对象, 这时触发写屏障将 C 对象标记成灰色
3. 垃圾收集器依次遍历程序中的其他灰色对象, 将它们分别标记成黑色

Dijkstra 的插入写屏障是一种相对保守的屏障技术, 它会将有存活可能的对象都标记成灰色以满足强三色不变性. 但是缺点也是非常明显的.

插入写屏障的缺点

1. 复杂度高. 流程代码会比较复杂.
2. 性能较低. 栈上的对象由于局部性原则短时间内会多次访问或更改指针, 会频繁出发写屏障.

为了弥补性能低的问题, Go选择仅仅对堆上的指针插入写屏障(因为堆上一般放置的是大型对象、全局变量或者静态变量, 变动不频繁. 而栈上一般存放的是局部变量或参数, 会频繁变动). 但是这样会导致扫描结束后栈上仍然存在引用白色对象的现象. 所以为了保证算法的正确性, 此时进行STW然后重新扫描栈使其变黑. 这个过程就叫做 re-scan. 此时整个算法的过程会变成:

1. 初始化GC任务: 包括开启写屏障和开启辅助GC, 统计root对象的任务数量等. 此过程STW
2. 扫描所有root对象, 包括全局指针和goroutine站上的指针(扫描某个goroutine时该goroutine停止), 将其加入灰色队列, 并循环灰色队列直至其为空. 此过程后台并行执行
3. 重新扫描全局指针和栈(re-scan). 此过程STW
4. 按照标记回收所有白色对象. 此过程后台并行执行

删除写屏障

Yuasa 在1990年提出了删除写屏障. 伪代码如下:

writePointer(slot, ptr)
    if (isGrey(slot) || isWhite(slot))
        shade(*slot)
    *slot = ptr

上述代码会在老对象的引用被删除时, 将白色的老对象涂成灰色, 以保证弱三色不变性.

yuasa删除屏障

1. 将根对象A标记为黑色, 将A指向的对象B标记为灰色
2. 用户程序将A原本指向B的指针改为指向C, 即删除了一个指针又新增了一个指针. 此时 触发删除写屏障, 但是因为B本身是灰色所以不做任何改变
3. 用户程序将原本B指向C的指针删除. 此时 触发删除写屏障, 白色的C被涂成灰色
4. 垃圾收集器遍历其他对象并分别标记成黑色, 算法结束

删除写屏障的缺点

1. 精度不高. 一个对象即使被删除了最后一个指向它的指针依旧可以活过本次循环, 只能在下一轮循环中被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提供两种策略:

1. 后台启动一个专门的worker等待清理内存
2. 当申请分配内存时lazy触发

STW

Stop the World是GC机制中一个重要的阶段, 当前运行的所有程序被暂停, 扫描内存的root节点并添加写屏障.

所有的处理器P都会被标记成停止状态(stopped), 不再运行任何代码. 调度器会把每个处理器M从各自队形的处理器P中分离出来放入idle列表中去.

Pacing

这是一个可配置的关于GC的参数. 表示下一次垃圾手机必须启动之前可以分配多少新内存的比例. 默认情况下为100, 即下一次GC前可以分配100%的内存.

当然, 这个参数只能一定程度上影响GC. 如果超过2分钟没有触发, Go会强制触发GC.

本文参考资料

1. go语言实践 Runtime GC原理
2. Go 语言设计与实现-垃圾收集器