原文链接 ：[典藏版]Golang三色标记、混合写屏障GC模式图文全分析
转载该文章，只为了分享和总结，也谢谢大佬的分享，看完之后收获很多。
在深入了解GO垃圾回收机制之前，我们先回顾下垃圾回收相关的基础概念
什么是垃圾回收？
曾几何时，内存管理是程序员开发应用的一大难题。传统的系统级编程语言（主要指C/C++）中，程序员必须对内存小心的进行管理操作，控制内存的申请及释放。稍有不慎，就可能产生内存泄露问题，这种问题不易发现并且难以定位，一直成为困扰开发者的噩梦。如何解决这个头疼的问题呢？过去一般采用两种办法：
- 内存泄露检测工具。这种工具的原理一般是静态代码扫描，通过扫描程序检测可能出现内存泄露的代码段。然而检测工具难免有疏漏和不足，只能起到辅助作用。
- 智能指针。这是 c++ 中引入的自动内存管理方法，通过拥有自动内存管理功能的指针对象来引用对象，是程序员不用太关注内存的释放，而达到内存自动释放的目的。这种方法是采用最广泛的做法，但是对程序员有一定的学习成本（并非语言层面的原生支持），而且一旦有忘记使用的场景依然无法避免内存泄露。
为了解决这个问题，后来开发出来的几乎所有新语言（java，python，php等等）都引入了语言层面的自动内存管理 – 也就是语言的使用者只用关注内存的申请而不必关心内存的释放，内存释放由虚拟机（virtual machine）或编程语言中提供的自动的内存管理机制。这种对不再使用的内存资源进行自动回收的行为就被称为垃圾回收。
常见的垃圾回收方法
引用计数（reference counting）
引用计数的思想非常简单：每个单元维护一个域，保存其它单元指向它的引用数量（类似有向图的入度）。当引用数量为 0 时，将其回收。引用计数是渐进式的，能够将内存管理的开销分布到整个程序之中。
优点：
- 算法易于实现。
- 渐进式。内存管理与用户程序的执行交织在一起，将 GC 的代价分散到整个程序。不像标记-清扫算法需要 STW (Stop The World，GC 的时候挂起用户程序)。
- 内存单元能够很快被回收。相比于其他垃圾回收算法，堆被耗尽或者达到某个阈值才会进行垃圾回收。
缺点：
- 原始的引用计数不能处理循环引用。大概这是被诟病最多的缺点了。不过针对这个问题，也除了很多解决方案，比如强引用等。
- 维护引用计数降低运行效率。内存单元的更新删除等都需要维护相关的内存单元的引用计数，相比于一些追踪式的垃圾回收算法并不需要这些代价。
标记-清除（mark and sweep）
标记-清扫算法是基于追踪的垃圾收集算法。内存单元并不会在变成垃圾立刻回收，而是保持不可达状态，直到到达某个阈值或者固定时间长度。这个时候系统会挂起用户程序，也就是 STW，转而执行垃圾回收程序。垃圾回收程序对所有的存活单元进行一次全局遍历确定哪些单元可以回收。算法分两个部分：标记（mark）和清扫（sweep）。标记阶段表明所有的存活单元，清扫阶段将垃圾单元回收。
标记-清扫算法的优点也就是基于追踪的垃圾回收算法具有的优点：避免了引用计数算法的缺点（不能处理循环引用，需要维护指针）。缺点也很明显，需要 STW。
节点复制（Copying Garbage Collection）
节点复制也是基于追踪的算法。其将整个堆等分为两个半区（semi-space），一个包含现有数据，另一个包含已被废弃的数据。节点复制式垃圾收集从切换（flip）两个半区的角色开始，然后收集器在老的半区，也就是 From半区中遍历存活的数据结构，在第一次访问某个单元时把它复制到To半区中去。在 From半区中所有存活单元都被访问过之后，收集器在 To半区 中建立一个存活数据结构的副本，用户程序可以重新开始运行了。
优点：
- 所有存活的数据结构都缩并地排列在 To半区的底部，这样就不会存在内存碎片的问题。
- 获取新内存可以简单地通过递增自由空间指针来实现。
缺点：
- 内存得不到充分利用，总有一半的内存空间处于浪费状态。
分代收集（generation）
基于追踪的垃圾回收算法（标记-清扫、节点复制）一个主要问题是在生命周期较长的对象上浪费时间（长生命周期的对象是不需要频繁扫描的）。同时，内存分配存在这么一个事实 “most object die young”。基于这两点，分代垃圾回收算法将对象按生命周期长短存放到堆上的两个（或者更多）区域，这些区域就是分代（generation）。对于新生代的区域的垃圾回收频率要明显高于老年代区域。
分配对象的时候从新生代里面分配，如果后面发现对象的生命周期较长，则将其移到老年代，这个过程叫做 promote。随着不断 promote，最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高，STW 时间也会更短。
优点:
- 性能更优。
缺点:
- 实现复杂
Golang垃圾回收机制内容提纲
本文将系统的详细介绍Golang中GC的全分析过程，包括垃圾回收的方式递进。
内容包括：
- G0 V1.3之前的标记-清除(mark and sweep)算法
- Go V1.3之前的标记-清扫(mark and sweep)的缺点
- Go V1.5的三色并发标记法
- Go V1.5的三色标记为什么需要STW
- Go V1.5的三色标记为什么需要屏障机制(“强-弱” 三色不变式、插入屏障、删除屏障 )
- Go V1.8混合写屏障机制
- Go V1.8混合写屏障机制的全场景分析
文章约近50张图文解析、4000+文字、推荐分阶段学习及消化
一、Go V1.3之前的标记-清除(mark and sweep)算法
此算法主要有两个主要的步骤：
- 标记(Mark phase)
- 清除(Sweep phase)
第一步，暂停程序业务逻辑, 找出不可达的对象，然后做上标记。第二步，回收标记好的对象。
操作非常简单，但是有一点需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即 STW(stop the world)，STW期间，程序无法响应请求。
第二步, 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示：
第三步, 标记完了之后，然后开始清除未标记的对象. 结果如下.
第四步, 停止暂停，让程序继续跑。然后循环重复这个过程，直到process程序生命周期结束。
二、标记-清扫(mark and sweep)的缺点
- STW，stop the world；让程序暂停，程序出现卡顿 (重要问题)。
- 标记需要扫描整个heap
- 清除数据会产生heap碎片
所以Go V1.3版本之前就是以上来实施的, 流程是
Go V1.3 做了简单的优化,将STW提前, 减少STW暂停的时间范围,Sweep阶段不再STW，可以和程序并发运行。如下所示
这里面最重要的问题就是：mark-and-sweep 算法会暂停整个程序 。
Go是如何面对并这个问题的呢？接下来G V1.5版本 就用三色并发标记法来优化这个问题.
三、Go V1.5的三色并发标记法
三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些. 我们来看一下具体的过程.
- GC 开始时，认为所有对象都是白色，即垃圾。
- 从 root 区开始遍历，被触达的对象置成灰色。
- 遍历所有灰色对象，将他们内部的引用变量置成 灰色，自身置成 黑色
- 循环第 3 步，直到没有灰色对象了，只剩下了黑白两种，白色的都是垃圾
- 回收所有的白色标记表的对象. 也就是回收垃圾。
PS：
对于黑色对象，如果在标记期间发生了写操作，写屏障会在真正赋值前将新对象标记为灰色。
标记过程中，新分配的对象，会先被标记成黑色再返回。
第一步 , 就是只要是新创建的对象,默认的颜色都是标记为“白色”.
这里面需要注意的是, 所谓“程序”, 则是一些对象的跟节点集合.
所以上图,可以转换如下的方式来表示.
第二步, 每次GC回收开始, 然后从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合。
第三步, 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合
第四步, 重复第三步, 直到灰色中无任何对象.
第五步: 回收所有的白色标记表的对象. 也就是回收垃圾.
以上便是三色并发标记法, 不难看出,我们上面已经清楚的体现三色的特性, 那么又是如何实现并行的呢?
Go是如何解决标记-清除(mark and sweep)算法中的卡顿(stw，stop the world)问题的呢？
四、没有STW的三色标记法
我们还是基于上述的三色并发标记法来说, 他是一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。我们举一个场景.
如果三色标记法, 标记过程不使用STW将会发生什么事情?
可以看出，有两个问题, 在三色标记法中,是不希望被发生的
- 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
当以上两个条件同时满足时, 就会出现对象丢失现象!
当然, 如果上述中的白色对象3, 如果他还有很多下游对象的话, 也会一并都清理掉.
为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？
答案就是, 那么我们只要使用一个机制,来破坏上面的两个条件就可以了.
五、屏障机制
我们让GC回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式.
(1) “强-弱” 三色不变式
- 强三色不变式
不存在黑色对象引用到白色对象的指针。
- 弱三色不变式
所有被黑色对象引用的白色对象都处于灰色保护状态.
为了遵循上述的两个方式,Golang团队初步得到了如下具体的两种屏障方式“插入屏障”, “删除屏障”.
(2) 插入屏障
具体操作: 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)
满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)
伪码如下:
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(新下游对象ptr)
//2
当前下游对象slot = 新下游对象ptr
}
场景：
A.添加下游对象(nil, B) //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B) //A 将下游对象C 更换为B， B被标记为灰色
这段伪码逻辑就是写屏障,. 我们知道,黑色对象的内存槽有两种位置, 栈和堆. 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中.
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
但是如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况(如上图的对象9). 所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束.
最后将栈和堆空间 扫描剩余的全部 白色节点清除. 这次STW大约的时间在10~100ms间.
(3) 删除屏障
具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)
伪代码：
添加下游对象(当前下游对象slot， 新下游对象ptr) {
//1
if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
标记灰色(当前下游对象slot) //slot为被删除对象， 标记为灰色
}
//2
当前下游对象slot = 新下游对象ptr
}
场景：
A.添加下游对象(B, nil) //A对象，删除B对象的引用。 B被A删除，被标记为灰(如果B之前为白)
A.添加下游对象(B, C) //A对象，更换下游B变成C。 B被A删除，被标记为灰(如果B之前为白)
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。
六、Go V1.8的混合写屏障(hybrid write barrier)机制
插入写屏障和删除写屏障的短板：
-
插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
-
删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。
(1) 混合写屏障规则和特点
具体操作
1、GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，
2、GC期间，任何在栈上创建的新对象，均为黑色。
3、被删除的对象标记为灰色。
4、被添加的对象标记为灰色。
满足: 变形的弱三色不变式.
混合写屏障特点
- 混合写屏障继承了插入写屏障的优点，起始无需 STW 打快照，直接并发扫描垃圾即可；
- 混合写屏障继承了删除写屏障的优点，赋值器是黑色赋值器，扫描过一次就不需要扫描了，这样就消除了插入写屏障时期最后 STW 的重新扫描栈；
- 混合写屏障扫描精度继承了删除写屏障，比插入写屏障更低，随着带来的是 GC 过程全程无 STW；
- 混合写屏障扫描栈虽然没有 STW，但是扫描某一个具体的栈的时候，还是要停止这个 goroutine 赋值器的工作的（针对一个 goroutine 栈来说，是暂停扫的，要么全灰，要么全黑，原子状态切换）
伪代码：
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(当前下游对象slot) //只要当前下游对象被移走，就标记灰色
//2
标记灰色(新下游对象ptr)
//3
当前下游对象slot = 新下游对象ptr
}
这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。
(2) 混合写屏障的具体场景分析
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
注意混合写屏障是Gc的一种屏障机制，所以只是当程序执行GC的时候，才会触发这种机制。
GC开始：扫描栈区，将可达对象全部标记为黑
证明：对于内存对象的操作主要包括四种基本情况，所以我们只要能在上述四种情况下，保障弱三原色约束，就能证明该写屏障是可靠的。
- 栈指针重指向到了另一个堆指针对象；
- 栈指针重指向到了另一个栈指针对象；
- 堆指针重指向到了另一个堆指针对象；
- 堆指针重指向到了另一个栈指针对象；
场景一： 对象被一个堆对象删除引用，成为栈对象的下游
伪代码
//前提：堆对象4->对象7 = 对象7； //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7； //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游
伪代码
new 栈对象9；
对象8->对象3 = 对象3； //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null； //对象2 删除引用 对象3
场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
Golang中的混合写屏障满足弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间。
七、总结
以上便是Golang的GC全部的标记-清除逻辑及场景演示全过程。
GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低
GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通
GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。
参考文献:
https://www.cnblogs.com/wangyiyang/p/12191591.html
https://www.jianshu.com/p/eb6b3aff9ca5
https://zhuanlan.zhihu.com/p/74853110
网友评论