背景知识
什么是标记与清理, 什么是三色标记
我们从根数据出发(学名叫RootSet):
- 向前走第一轮, 得到如下结果: 直接引用根数据的变量包含有(A,F). 第一轮结束, 将ABC三个变量标记成灰色.
- 开始第二轮, 我们从A出发, 首先我们将A标记成黑色, 然后发现引用了A的有(B,C,D)两个变量, 这两个变量通过A间接引用了根数据, 因此也是有效的, 我们将DB标记成灰色; 我们使用同样的办法在刚刚的(F)变量上, 第二轮结束, 我们得到了(B,C,D)变量是有效的, 截止目前, 一共有(A,B,C,D,F)是有效变量
- 不停重复上面的操作: 从灰色的点出发, 将自己标记成黑色, 将自己能到达的点标记成灰色, 然后再下一轮, 再从灰色的点出发
- 到最后所有的点只能是黑色+白色两类, 黑色的是有效的, 白色的就代表"无论如何也不可能到达"的, 无效的点, 在上面的图中, (E,H,G)就会被划归成白点, 这些点就会被清理(上面这种有向图检索其实也叫迪杰斯特拉检索)
我们的主要矛盾是什么
我们希望垃圾清理的过程最好最好, 能够按照Goroutine那样并发的进行, 不要耽误主进程的工作. 如果以上操作被并发的执行了, 会发生什么?
我们的整理工作是按照"轮"进行的, 第一轮第二轮最后一轮这样的, 假设现在存在一个灰色的点链接着一个白色的点, 那么按照上面的步骤, 下一轮这个白色的点也将被标记成灰色的点, 从而被保留下来.
但是就在这个时候, 这个链接突然断开了, 随后这个白色点被连上了一个黑色的点. 按照"轮数"的操作方法, 我们只会再"造访"灰色的点, 黑色的点是永远不可能再到访了. 那也就是说这个白色点, 就算有在引用黑点,就算是有效的, 同样会被清理. 等到黑点想要用这个白点的时候会造成数据丢失.
虽然很恶心, 但如果你允许用户一边运行程序, 一边运行GC, 那就完全有可能发生这种事. 所以Go在1.3之前都是停止所有工作来做标记/清理工作的.
Dijkstra策略 - 插入屏障(Go1.5)
针对黑白相连的问题,Dijkstra(下面简称dij)策略是这样理解的: 如果我不让你黑白相连呢? → 对于任何尝试黑白相连的操作, 直接把白点置灰就完事了.
这样是不是就能完成goroutine式的"并发垃圾回收"? 可惜dij也有自己的问题, 它的问题在于栈上的操作管不到, 只能管到堆, 也就是说, 就算栈上黑白相连了, 也管不到, 所以dij需要在结束的时候, STW一下, 专门去清理一下栈.
Yuasa策略 - 删除屏障
同样的问题, Yuasa是这么理解的: 问题的源头来自灰白断连的那一下子, 如果不是因为灰白断连后又来一个黑白相连, 那一切都不会出问题. 那就禁止一切灰白断连好了 → 灰白断连, 无论你接下来是不是会出现黑白相连, 我都直接将白点置灰. Yuasa策略就是相信灰白断连之后, 一定会发生黑白相连, 因此直接将白点置灰. 但是, 即使接下来并没有发生黑白相连, 这个野灰点, 因为实质上也并没有指向任何数据, 同样活不过下一轮GC
同样, 这样能不能说走并发垃圾回收? 不能, 因为Yuasa需要在一开始就STW为堆+栈做快照, 随后并发的, 按照上面的方法来分析变量.
混合策略(Go1.8)
Yuasa的删除屏障发挥作用
如果已知操作对象分别是一灰一白, 现在又在执行删除操作. 直接将白色置灰(Yuasa/删除写屏障) 如果已知栈是黑色的 针对这种操作, 你不需要知道后续步骤, 因为在删除写屏障下, 任何灰白删除都会触发yuasa策略发挥作用.
Dij的插入屏障发挥作用
如果现在又再将栈上的黑色对象引用一个白色对象, 那么直接将白色对象置灰. 针对这种情况, 你同样不需要知道这个白色对象是从哪儿来的, 你也不需要知道这个白色对象之前是否经历过Yuasa策略, 可能甚至是一个野白点, 但是只要你尝试黑栈+白点, 就会触发白点置灰的操作
为什么要这么做, 为什么安全
我们就是这样的将两个策略混合起来使用. 思考一下, 我们拒绝Dij策略的原因就是这个策略无法保证栈的安全. 但是,如果,我们能保证栈的安全, 这种情况下使用Dij策略那就是没问题的. 那就可以按照预期的那样goroutine并发伴行. 那这种"保证"是从哪儿来的? Dij的死角在于栈上的黑白相连管不到, 对付这个死角, 我们同时运行着Yuasa, 只要灰白断连, 就白点置灰, 这样就绝对不可能出现栈上的黑白相连. ok , 现在我们只需要创造Yuasa的运行环境即可: 开头的时候STW, 但是只扫描栈就够了, 这种情况下, yuasa策略在栈上就是有效的, 也就是说hybrid运行结束栈就是安全的.
有疑问加站长微信联系（非本文作者）
