Theory · Golang · Runtime
三色标记与混合写屏障
Go 并发 GC 的正确性基石 —— 弱三色不变式 + 混合写屏障,如何把最坏 STW 从百毫秒压到微秒级
三色抽象
白→灰→黑单调推进;Go 满足弱不变式:黑指向的白必须 grey-protected
混合写屏障(Go 1.8)
Yuasa 删除 + Dijkstra 插入二合一;每栈并发扫一次、永久黑,栈重扫被删除
微秒级 STW
官方口径:GC 暂停通常 <100µs,常低至 10µs(Go 1.8 Release Notes)
这份 deck 按"为什么需要屏障 → 三色抽象 → 强弱不变式 → 两种经典屏障 → 混合写屏障 → 栈只扫一次的论证 → 真实实现 → 全流程与演进 → QA"组织,所有结论都对照 Go 官方设计文档 #17503 与 runtime 源码(mbarrier.go / mwbbuf.go / mgc.go / mgcmark.go)验证过。
The Problem
并发标记的核心矛盾:漏标 = use-after-free
漏标 ⟺ 两个条件同时成立
1黑对象新增指向白对象的引用(插入)——黑不再被扫,这条边没人看见
2灰对象到该白对象的路径被删除(删除)——原计划的扫描再也到不了它
mutator 与 collector 并发运行,对象图随时在变,上述交叠完全可能发生。
屏障的本质
写屏障 = 让两个条件无法同时成立——插入屏障管条件①,删除屏障管条件②(下一页起展开)。
先立住"为什么需要屏障":并发标记下漏标是正确性灾难。两个条件(黑→白新增、灰→白删除)是后面所有屏障设计的锚点:Dijkstra 破坏条件①,Yuasa 破坏条件②,混合屏障两个都管。
Tricolor Abstraction
三色抽象:白 / 灰 / 黑
标记循环(Dijkstra '78)
1周期开始:所有对象白;把根(栈、全局变量)标灰入队
2循环:取一个灰对象 → 扫描它的引用 → 被指的子对象标灰 → 自身变黑
3灰色队列为空 → 标记结束:黑 = 存活,白 = 垃圾 → 并发清扫
三色速记
- 白 = 未访问(候选垃圾)
- 灰 = 已标、子未扫(待办队列)
- 黑 = 存活、办结(永不再看)
白→灰→黑单调推进,总工作量有界、保证终止——"屏障设计题"就是:mutator 并发改图时,如何保证没有可达对象停在白色。
三色是并发 GC 的通用抽象,Dijkstra 1978 提出。Go 的 GC 是非分代、非整理、并发标记清除。讲这页时强调"灰队列":灰=待办事项,黑=已办结,白=候选垃圾。
Invariants
强不变式 vs 弱不变式:Go 选了弱
强三色不变式(Strong)
不允许 黑 → 白 指针存在。Dijkstra 插入屏障直接维护它——代价是栈很难处理(下一页)。
弱三色不变式(Weak)· Go 采用
黑指向的白对象,必须能从某个灰对象经一条白色指针链到达(Pirinen '98 称 grey-protected)——只要 GC 迟早会扫到它就不算漏。
混合写屏障不满足强不变式(黑 G 可以把白指针写进黑对象而不标灰),但满足弱不变式。Go 的证明还把"灰保护者"加强为堆对象,便于归纳(design doc 附录给出完整证明 + 随机化模型验证)。
这页是全 deck 的理论核心:Go 的混合写屏障允许黑→白边存在,靠弱不变式兜底。"grey-protected 必须是堆对象"这个细节来自 design doc 附录的 modified tricolor invariant,面试能说出来就是加分项。
Barrier 1/2 · Go 1.5–1.7 采用
Dijkstra 插入屏障:保护新值,管不住栈
// coarsened Dijkstra barrier(破坏条件①)
writePointer(slot, ptr):
shade(ptr) // 新值入堆前先标灰
*slot = ptr
优点
① 只拦写、无读屏障——指针读比写多一个数量级以上;② 颜色单调白→灰→黑,标记工作量有界、保证前进。
致命缺陷:栈是盲区
屏障拦不住栈上的指针写(逐条加屏障成本不可接受)。扫过的栈只要 goroutine 继续执行,就可能藏进白指针 → 只能把栈视为永久灰(permagrey) → 周期末必须 STW 重扫所有栈。design doc 原文:大量 goroutine 时重扫耗时 10~100ms。
Go 1.5–1.7 的写屏障就是这版。permagrey 循环是重点:栈写加屏障太贵,所以栈扫完转黑后一旦执行就得当回灰色处理,最终 10-100ms 的 STW 都花在重扫栈上——这就是 #17503 要解决的问题。
Barrier 2/2 · SATB(Snapshot-At-The-Beginning)
Yuasa 删除屏障:保护旧值,起点要快照
// Yuasa deletion barrier(破坏条件②)
writePointer(slot, ptr):
shade(*slot) // 旧值被覆盖前先标灰
*slot = ptr
语义:删除即保护(快照)
周期起点可达的对象(快照)全部存活:任何"摘除引用"的动作都会先把旧目标标灰。不再需要期末重扫。
致命缺陷:快照必须包含所有栈
栈也是根,栈上指针写无屏障 → 快照前所有栈必须"处理完":方案 A 起始 STW 扫全部栈——Go 动辄成千上万栈(Yuasa 原方案是单线程小栈时代产物);方案 B "全栈变黑才开始扫堆"——栈可并发扫,但堆标记被栈扫描卡成瓶颈,还拖累 goroutine 可用性(分配节奏与标记进度联动)。代价:快照内的死对象全部活到下轮(浮动垃圾)。
Yuasa 的快照语义讲清楚:起点可达=存活。两种落地方案各有硬伤,这是 design doc "Alternative barrier approaches" 一节的分析。JVM G1 用的 SATB 就是 Yuasa 思想。
The Hybrid Write Barrier · Go 1.8(design doc #17503)
混合写屏障:两个 shade 各堵一个"藏匿"洞
writePointer(slot, ptr):
shade(*slot) // Yuasa 删除半:覆盖前标灰旧值 —— 堵"堆→栈"藏匿
if current stack is grey: // Dijkstra 插入半:本 G 的栈还没扫过才需要
shade(ptr) // —— 堵"栈→黑堆对象"藏匿
*slot = ptr
混合屏障 = Yuasa + Dijkstra 的三个构件协同:shade旧值堵堆→栈,shade新值堵栈→黑堆对象,if条件让栈变黑后省掉第二次shade。核心收益:栈扫一次即永久黑,栈重扫、stack barrier、re-scan list 全部删除。
Why One Scan Suffices
栈为什么只需扫一次:指针来源的归纳论证
这是 design doc "Reasoning" 三点论证 + 附录归纳证明的直觉版:进栈指针的来源要么被本次扫描覆盖,要么来源处已被 shade,跨栈传递由归纳兜住;channel 和 go 语句两个跨栈拷贝的特例由屏障兜底。所以每栈扫一次即可。
Implementation · Go master
真实实现:插入点 · 无条件双 shade · wbBuf
编译器 / runtime 在哪里插屏障
- 堆对象指针字段写;全局变量写同样拦——否则 mark termination 就得重扫全局(mgc.go:rely on write barriers for writes to globals)
- 批量操作
typedmemmove / typedmemclr / wbZero / wbMove —— channel 收发、map 写入、slice/扩容拷贝都走这里(也覆盖跨栈拷贝特例)
- 当前帧的栈写省略屏障;经不确定指针(如参数)写则保留
- pre-publication:屏障先于
*slot = ptr 执行
- 1.8 起 nil 写不能省屏障(shade(*slot) 仍需执行);能同时证明"旧值与新值都永黑"(nil / 全局 / 静态数据 / 零值新对象)才可省 → 二进制略大
伪代码有 if 条件,实现是无条件双 shade
- 按 slot 所属对象颜色做条件 → 需要内存屏障才能看清并发变色(经典的 load/store 重排问题),成本更高,runtime 放弃
- 按"当前栈是否灰"做条件 → buffer 化之后难以追踪(
wbBufFlush1 的 TODO 原文承认未做)
- 落地即设计文档中的"无条件变体":
p[0], p[1] = old, new,flush 时统一 shade —— 正确性更好推理,成本用缓冲摊薄
- wbBuf(Go 1.10):per-P 512 槽缓冲;汇编快路径
gcWriteBarrier1..8 不破坏通用寄存器;满则 flush 进 gcWork(过滤 nil、已黑跳过)
512per-P wbBuf 槽位数(wbBufEntries)
old + new每次指针写入缓冲的指针对
Go 1.10官方:GC 激活时分配延迟与开销显著降低
这页回答"伪代码和源码差在哪":mbarrier.go 说插入半只在栈灰时必要,但实现按 slot 颜色做条件要内存屏障、按栈条件在 buffer 化后难追踪,所以是无条件 shade(old)+shade(new),即设计文档里更易推理的变体;wbBuf 把高频写的成本摊薄。
GC Cycle · mgc.go
GC 全流程:两段 STW + 两个并发阶段
四阶段来自 mgc.go 头部注释:sweep termination STW、并发 mark、mark termination STW、并发 sweep。25% 后台标记 CPU 出自 mgcpacer.go 的 gcBackgroundUtilization=0.25,差额由分配 assist 补。重点:1.8 后两段 STW 都不再有扫描工作。
Evolution
最坏 STW 的十年演进:百毫秒 → 微秒
时间线答题素材:1.5 并发化(Dijkstra 屏障),1.7 的痛点是栈重扫 10-100ms,1.8 混合屏障后官方口径通常低于 100 微秒、常低至 10 微秒,1.10 wbBuf 摊薄屏障开销。pacer 和 GOMEMLIMIT 属于调优知识,另行沉淀。
Comparison
三种屏障对比
| Dijkstra 插入屏障 | Yuasa 删除屏障 | Go 混合写屏障(1.8+) |
| shade 什么 | 新值 ptr(装入前标灰) | 旧值 *slot(覆盖前标灰) | 旧值 *slot +(栈灰时)新值 ptr;实现为无条件双 shade |
| 满足不变式 | 强(禁止黑→白) | 弱(SATB 快照语义) | 弱(灰保护者须为堆对象) |
| 栈怎么处理 | permagrey:期末 STW 重扫 | 起点快照全部栈 | 每栈并发扫一次,永久黑 |
| STW 位置 | 期末重扫,1.5–1.7 实测 10–100ms | 起点(栈越多越长) | 两段均为微秒级 |
| 读屏障 | 不需要 | 不需要 | 不需要(读多写少,读屏障一律不考虑) |
| 浮动垃圾 | 有 | 快照内死对象全保留 | 较多(推迟回收,不是泄漏) |
| 代表 | JVM CMS(增量更新) | JVM G1(SATB) | Go 1.8+(IBM 实时 Java 的 double barrier 同源) |
对比表是面试白板题的标准收尾。CMS=增量更新(Dijkstra 思想)、G1=SATB(Yuasa 思想)这个对应关系常被问到;Go 的混合屏障与 IBM 实时 Java 的 double write barrier 同源(design doc 引 Auerbach '07)。
Floating Garbage
浮动垃圾:微秒级 STW 的代价
是什么
本轮标记中实际已不可达、却被保留的对象。回收只是被推迟到下一轮,不是内存泄漏;但堆会显得偏大。
混合屏障的两个来源
- Yuasa 半:标记期间任一时刻从根(除栈外)可达者全部保留(Rationale 原文)
- 标记期新分配对象直接标黑 → 本轮必不回收
为什么可接受
换来两段微秒级 STW。官方也补了一句:实践中 Dijkstra 屏障保留的浮动垃圾"几乎一样多"。堆偏大时用 GOGC 调低 / GOMEMLIMIT 上限对冲。
一句话辨析(易混)
漏标 = 活的没标到 → 被错误回收 → 正确性事故;浮动垃圾 = 死的被多标 → 活到下轮 → 只是延迟回收。误标浮动垃圾永远安全,漏标永远危险——屏障的所有取舍都在"宁可多留,不可漏标"这一侧。
浮动垃圾是混合屏障最主要的缺点(design doc Rationale 承认 may result in more floating garbage,但也说实践中 Dijkstra 差不多)。另一缺点:nil 写不能省屏障,二进制略大。辨析那句话是面试收尾金句。
Hands-on
实战观察:GODEBUG=gctrace=1
$ GODEBUG=gctrace=1 ./app
gc 21 @12.804s 1%: 0.018+1.6+0.031 ms clock, 0.14+0.28/1.2/0.075+0.25 ms cpu, 16->17->8 MB, 17 MB goal, 0 MB stacks, 0 MB globals, 8 P
// 示例行;字段格式见 runtime/extern.go(官方注明 subject to change,随版本可能增减)
clock 三段 = 墙钟:两段 STW 夹一段并发
0.018 ms STW sweep termination(开屏障 + 扫尾)
1.6 ms 并发标记(不暂停世界)
0.031 ms STW mark termination(收尾)
- 两段 STW 都是微秒级——这页就是写屏障成果的直接观测窗口
cpu 与堆字段
0.28/1.2/0.075 = assist(分配助攻)/ background(25% worker)/ idle
16->17->8 MB = 标记开始堆 → 结束堆 → 存活堆
17 MB goal = 下轮目标 ≈ 2×存活(GOGC=100)
stacks / globals = 可扫描栈 / 全局体积;行尾 (forced) = runtime.GC() 触发
gctrace 是把前文机制对应到生产的入口:clock 三段对应四阶段里的两段 STW 和并发标记;cpu 分解对应 assist/background/idle;16->17->8 的第三个数是存活堆,goal 由 GOGC 推出。示例数字仅演示格式。
Interview QA · 1/3
高频 QA(上)· 三色与屏障原理
Q1 · 三色标记法是什么?基本流程?
白=未访问灰=子未扫黑=存活无灰即完成
并发标记的抽象模型:起始全白,根(栈、全局)标灰入队;循环取灰对象、扫描引用把子标灰、自身转黑;灰队列空则黑=存活、白=垃圾,进入并发清扫。颜色白→灰→黑单调推进,总工作量有界、保证终止。
Q2 · 并发标记为什么会"丢对象"?
黑→白新增灰→白删除use-after-free
漏标当且仅当两个条件同时成立:①黑对象新增指向白对象的引用(黑不再被扫,没人看见这条边);②灰对象到该白对象的路径被删除(原计划扫描到不了它)。结果活对象被当垃圾回收、指针悬垂——正确性灾难。屏障的本质就是让两条件无法同时成立。
Q3 · 强 / 弱三色不变式的区别?Go 满足哪个?
强=禁黑→白弱=grey-protectedGo=弱
强不变式不允许任何黑→白边;弱不变式(Pirinen '98)允许黑→白,但该白对象必须能从某个灰对象经白链到达(grey-protected),GC 迟早标到它。Go 混合写屏障不满足强、满足弱;design doc 附录还把灰保护者加强为"堆对象"并给出完整归纳证明 + 随机化模型验证。
Q4 · 插入屏障和删除屏障的原理与缺陷?
shade(ptr)shade(*slot)permagrey起点快照
插入(Dijkstra):写入前 shade 新值,保强不变式;缺陷是管不住栈——栈写加屏障太贵,栈只能 permagrey,期末 STW 重扫 10–100ms(Go 1.5–1.7)。删除(Yuasa):覆盖前 shade 旧值,快照语义保弱不变式;缺陷是快照必须含全部栈——起始 STW 扫栈或让堆标记等全栈变黑(瓶颈),且浮动垃圾更多。
QA 按"概念 → 问题 → 不变式 → 两屏障"排。Q2 的两条件是整套屏障设计的锚点,Q4 答缺陷时各带一个数字(10-100ms、成千上万栈)。
Interview QA · 2/3
高频 QA(中)· 混合写屏障
Q5 · 混合写屏障伪代码?两个 shade 各堵什么洞?
shade(*slot)栈灰才 shade(ptr)堵两个藏匿方向
shade(*slot)(Yuasa 半)堵"堆→栈":想把堆上唯一引用搬进栈,摘除瞬间旧值已被标灰;shade(ptr)(Dijkstra 半,仅当前 G 栈未扫时)堵"栈→黑堆对象":想把栈里藏的白指针装进黑对象,装入前已被标灰。栈变黑后 shade(ptr) 冗余——刚扫完的栈只指向已 shade 对象。实现为无条件双 shade。
Q6 · 为什么栈只需扫一次、扫完永久黑?
三来源已 shade归纳跨栈拷贝走屏障
进入已扫栈的指针只有三种来源:①周期起点就在栈里——该次扫描覆盖;②从堆读入——对象扫描时子已标灰、删除时被 shade(*slot) 保护,进栈的必是已 shade 的;③从其他栈传入——归纳成立。特例 channel send / go 语句会把值直接栈拷栈,必须走 typedmemmove 屏障。新栈为空即黑、新对象直接黑,归纳闭环。
Q7 · 栈实际什么时候被扫描?G 要处于什么状态?
并发标记期安全点异步抢占→保守扫顺带 shrinkstack
并发标记阶段逐个进行:markroot 处理栈根时,G 必须已停在安全点(runnable/syscall/waiting,或被异步抢占打断),运行中的 G 直接 throw。异步安全点会额外保守扫描扩展寄存器;sched.ctxt、defer/panic 记录也在此扫;顺手 shrinkstack 收缩多余栈空间。扫完栈上指针全部入灰队列,栈转黑。
Q8 · Go 的屏障是读屏障还是写屏障?插在哪?
写屏障pre-publication全局写也有nil 写不可省
纯写屏障(读比写多一个数量级,读屏障一律不考虑)。编译器插在:堆对象指针字段写、全局变量写、批量拷贝 typedmemmove/wbZero/wbMove;当前帧栈写省略,经不确定指针写保留。pre-publication:先屏障后赋值。1.8 起 nil 写不可省(shade(*slot) 仍要执行),仅"新旧值都永黑"可省——二进制因此略大。
这页聚焦混合屏障本体。Q7 是源码细节题(scanstack 的状态要求、异步安全点保守扫寄存器),Q8 的 pre-publication 和"全局写也要屏障"是容易被追问的点。
Interview QA · 3/3
高频 QA(下)· 细节与实战
Q9 · 标记期新分配的对象是什么颜色?
allocate-black与混合屏障配套本轮不回收
直接标黑(mallocgc 在标记期对新对象置位)。原因:混合屏障与 allocate-white 不兼容(design doc 明说);新对象无历史引用,标黑不会破坏弱不变式,还省去扫它。代价:标记期分配的对象本轮必不回收,是浮动垃圾来源之一。新栈为空,天然等价黑色。
Q10 · 什么是浮动垃圾?为什么可接受?
死的被多留推迟≠泄漏GOGC / GOMEMLIMIT 对冲
本轮标记中已不可达却被保留的对象。混合屏障两个来源:Yuasa 半保留"标记期任一时刻从根(除栈外)可达者";标记期新分配对象直接黑。design doc 承认可能比 Dijkstra 更多,但实践中"几乎一样多";换的是微秒级 STW。误标永远安全、漏标永远危险——取舍都在"宁可多留"一侧。
Q11 · 两次 STW 各做什么?为何能到微秒级?
STW①开屏障STW②收尾零扫描工作
STW① sweep termination:全局内存栅栏确保屏障开启前的指针写可见、清扫上轮剩余 span、切 _GCmark;STW② mark termination:切 _GCmarktermination、flush wbBuf / mcache、统计,无任何扫描。微秒级的根因:1.8 起栈只扫一次且在并发期完成,两段 STW 里没有任何与堆、goroutine 数量相关的工作。
Q12 · 写屏障的开销怎么被优化?
wbBuf 512 槽汇编快路径编译器省略flush 过滤
热路径:汇编 gcWriteBarrier1..8 把 (old,new) 写进 per-P 512 槽 wbBuf,不破坏通用寄存器、不进 Go 调用约定;缓冲满才 wbBufFlush,统一 shade 进 gcWork(过滤 nil、已标黑跳过)。Go 1.10 上线,官方口径 GC 激活时分配延迟与总体开销显著降低。冷路径由编译器省略兜底:新旧值都永黑时整段省略。
Q11 是收束题:把混合屏障和 STW 数字串起来。Q12 强调"缓冲摊薄"思路——单次屏障不可能免费,但可以让 99% 的调用只花一次内存写。扩展追问 cgo:C 覆盖 Go 指针需遵守 cgo 指针传递规则,cgocheck=1 默认兜底。
References
参考来源 & 相关知识点
相关知识点(点击跳转 · 待沉淀项以虚线标注)
- GMP 调度模型 — STW 如何停住所有 P;gcBgMarkWorker 的调度
- channel 底层实现 — 跨栈拷贝的屏障特例(typedmemmove)
- map 底层实现 — 堆指针写经过写屏障的容器
- Go 内存分配器 — allocate-black 与 mcache
- GC pacer 与调优 待沉淀 — GOGC / GOMEMLIMIT / 1.18 pacer
键盘操作:←→ 翻页 · T 换主题 · S 演讲者模式 · O 总览。
所有结论都对照 design doc #17503 与 Go master 源码验证过,版本敏感结论(1.5/1.8/1.10)都标注了出处。相关知识点里 memory-allocator 已沉淀成独立 deck,gc-pacer-tuning 待沉淀。