00 · 设计推演：从零造一个 GC

“GC 的每一条规则背后，都躺着一个’如果不这样就会漏标/错标’的失败案例。“

---

开场：先承认手动管理会出事

老陈：需求：自动回收不再使用的内存。

先说为什么需要它。手动管理有几个经典错误？

小林：悬垂指针、内存泄漏、double free……

老陈：还有野指针、忘记初始化。C/C++ 程序的 bug 里有相当大比例是内存问题。

那我们来做自动回收。不许说”用三色标记”，你来设计。

小林：……最简单的是引用计数？

---

v0：引用计数

思路：每个对象记一个数，有人引用就 +1，没人引用就 -1，归零就释放。

type Object struct {
	refCount int
	fields   []*Object
}
 
func (o *Object) Retain()  { o.refCount++ }
func (o *Object) Release() {
	o.refCount--
	if o.refCount == 0 {
		for _, f := range o.fields {
			f.Release()   // ★ 递归释放它引用的对象
		}
		free(o)
	}
}

优点：

• 即时回收（引用归零立刻释放）
• 无停顿（释放分摊在每次赋值里）
• 实现简单（Python、Objective-C、Swift 都用它）

★ 致命失败：循环引用

type Node struct {
	next *Node
}
 
a := &Node{}
b := &Node{}
a.next = b   // b.refCount = 1
b.next = a   // a.refCount = 1
 
// 现在 a、b 都不可达了（没有任何外部引用）
// 但 a.refCount = 1, b.refCount = 1
// ★ 永远不会被释放！内存泄漏

解法尝试：弱引用（weak reference）——打破环。

代价: 程序员必须自己识别哪里可能成环，手动指定弱引用
     → 又变成了手动管理的一部分

老陈：引用计数的根本问题是：它只能判断”有没有人指向我”，不能判断”我从根上还可达吗”。

前者是局部信息，后者是全局信息。

这是 GC 的第一个分水岭：

• 引用计数 = 局部判断（快，但不准确，漏掉循环垃圾）
• 追踪式 GC = 全局判断（准确，但要遍历）

现代语言的做法：

• Python: 引用计数 + 一个循环检测兜底
• Swift: 引用计数 + 要求程序员用 weak/unowned
• Go/Java: 纯追踪式

---

v1：标记-清除（Mark-Sweep）

思路转变：从根（全局变量、栈）出发，遍历所有可达对象，标记它们。没被标记的就是垃圾。

func (g *GC) Collect() {
	// ① STW: 暂停所有用户 goroutine
	stopTheWorld()
 
	// ② 标记：从 roots 出发，递归标记
	worklist := g.roots
	for len(worklist) > 0 {
		obj := pop(&worklist)
		if obj.marked { continue }
		obj.marked = true
		for _, child := range obj.fields {
			worklist = append(worklist, child)
		}
	}
 
	// ③ 清除：遍历整个堆，回收未标记的
	for obj := range g.heap {
		if obj.marked {
			obj.marked = false   // 为下次 GC 准备
		} else {
			g.free(obj)
		}
	}
 
	startTheWorld()
}

改进：循环引用问题解决了——因为它们从根不可达，不会被标记。

失败：

#	问题	后果
1	★ STW 停顿长	堆越大，标记越久。几十 GB 堆可能停几秒
2	内存碎片	不整理，堆会逐渐碎片化
3	清除要遍历整个堆	O(堆大小)，即使存活对象很少

---

v2：标记-整理（Mark-Compact）

针对碎片问题：标记后，把存活对象”压缩”到堆的一端。

整理前:  [A][垃圾][B][垃圾][C][垃圾][D]
整理后:  [A][B][C][D][        空闲      ]

改进：无碎片，分配变成简单的指针碰撞（bump pointer）。

失败：

#	问题	说明
1	移动对象开销大	要拷贝所有存活对象
2	★ 要更新所有引用	对象地址变了，所有指向它的指针都要改
3	停顿更长	标记 + 整理都要 STW
4	★ 破坏指针语义	见下

问题 4 是 Go 不能接受的：

如果对象会移动:
  · C 代码持有的 Go 指针会失效（cgo！）
  · 需要额外的间接层（句柄）或者读屏障
  
★ Go 必须支持 cgo（标准库的 net、os/user 都用）
  → 所以 Go 的 GC 不能移动堆对象

老陈：这是一个”外部约束决定内部设计”的典型例子。

Java 可以移动对象，因为 JNI 对长期持有对象引用有严格限制。 Go 不行，因为 Go 把 cgo 兼容性放在了很高的优先级。

代价：Go 接受了碎片化，靠 size class 缓解（第 1 章第 04 节）。

---

v3：复制式 GC（Copying / Cheney）

换个思路：不整理，而是把存活对象复制到另一半空间。

From 空间:  [A][垃圾][B][垃圾][C]
                ↓ 复制存活的
To 空间:    [A][B][C][      空闲    ]
                ★ 然后整个清空 From

改进：

• 无碎片
• 分配是 bump pointer（极快）
• 只处理存活对象（如果大部分是垃圾，很快）

★ 关键性质：代价与存活对象成正比，与堆大小无关。

失败：

#	问题
1	浪费一半内存
2	还是要移动对象

老陈：但注意性质：如果存活率很低（比如 5%），复制式 GC 非常划算。

这就引出了下一个版本——分代。

---

v4：分代 GC（Generational）

核心洞察：Weak Generational Hypothesis（弱分代假说）

绝大多数对象”朝生夕死”——分配后很快就变成垃圾。

实测：Java 程序中 70-98% 的对象在下一次 GC 前就死了。

设计：

• 堆分成新生代（Young）和老年代（Old）
• 新生代用复制算法（存活少，复制便宜，且只占一小部分内存，浪费可接受）
• 老年代用标记-清除（存活多，复制不划算）

┌────────────────┬─────────────────────┐
│  Young (1/3)   │     Old (2/3)       │
│  ┌────┬───┬───┐│                     │
│  │Eden│S0 │S1 ││   长期存活的对象      │
│  └────┴───┴───┘│                     │
└────────────────┴─────────────────────┘

Minor GC: 只回收新生代（频繁，但快）
Major GC: 回收整个堆（少，但慢）

Java 的实测收益：Minor GC 通常只要几毫秒。

★ 但 Go 没有分代。为什么？

理由 1: Go 大量使用栈分配
  逃逸分析把短命对象放在栈上
  → 堆上的对象，平均生命周期比 Java 长得多
  → 分代假说的收益变小

理由 2: 编译器和 runtime 的协作
  Go 的对象没有 header（类型信息在类型描述符里）
  GC bitmap 让扫描很精确很快
  → 并发标记的成本已经够低

理由 3: ★ 明确的取舍
  分代需要写屏障记录跨代引用（Card Table）
  分代会让 Full GC 停顿更长
  ★ Go 选择"放弃吞吐率优势，换可预测的短停顿"

老陈：这不是”Go 做不到”，是”Go 认为不值得”。

但这个判断是有条件的。如果 Go 进入大数据 / AI 场景（堆几十上百 GB），分代可能就值得了。

又一次印证：设计被使用场景塑造。场景迁移，当年的决策就变成包袱。

---

v5：并发标记（三色标记）

回到 v1 的失败 1：STW 停顿长。

思路：能不能让标记和用户代码同时跑？

三色抽象：

颜色	含义
白	未访问（候选垃圾）
灰	已访问，但引用的对象还没扫完（在工作队列里）
黑	已访问，且引用的对象都扫完了（确定存活）

标记过程 = 灰色集合从 0 扩张，再收缩回 0

初始:   全是白，roots 涂灰
          ○ ○ ○ ●(root)

扫描:   灰变黑，它引用的白变灰
          ●(root) → ◐ ○ ○

结束:   灰色为空，剩下的白就是垃圾
          ● → ● → ●   ○(垃圾)

★ 但并发会出问题——漏标

时刻 1:  A(黑) → B(白)，C(灰) → B
         （B 通过 C 可达，安全）

时刻 2:  用户执行 A.ref = B
         ★ A 已经是黑色，不会再被扫描！

时刻 3:  用户执行 C.ref = nil
         （C 是灰色，会扫描，但它的引用已经变了）

结果:    B 是白色，被回收
         但 A 还引用着 B！
         → ★ 悬垂指针，程序崩溃

失败原因精确归因：漏标需要同时满足两个条件：

① 黑色对象新增了指向白色对象的引用
② 所有从灰色对象到该白色对象的路径都被删除了

老陈：这个”同时满足两个条件”的归因是设计的关键。

因为要破坏它，只需要破坏其中任意一个——这就直接给出了两种写屏障。

---

v6：写屏障（Write Barrier）

思路：在”写指针”这个动作上加钩子，破坏漏标的两个条件之一。

方案 A：Dijkstra 插入屏障（破坏条件 ①）

func writePointer(slot *Object, ptr *Object) {
	shade(ptr)   // ★ 把新值涂灰（如果是白色）
	*slot = ptr
}

维持强三色不变式：黑色对象不能直接指向白色对象。

失败：

★ 栈上的写不加屏障（栈写太频繁，加屏障开销大）
  → 栈上的 A.ref = B 不会被捕获
  → 可能漏标
  → ★ 必须在标记结束前 STW，重新扫描所有栈

代价: 栈越多（goroutine 越多），STW 越长
     10 万 goroutine 的服务，重扫栈可能要几十 ms

方案 B：Yuasa 删除屏障（破坏条件 ②）

func writePointer(slot *Object, ptr *Object) {
	shade(*slot)   // ★ 把旧值涂灰
	*slot = ptr
}

维持弱三色不变式：被删除引用的对象被涂灰，会重新扫描。

优点：不需要重扫栈。 失败：更保守（更多浮动垃圾），且需要 SATB 快照。

---

v7：混合写屏障（Go 1.8+ 的选择）

Go 的两个约束：

1. GC 要并发，STW 要极短（< 1ms）
2. 栈上的写不加屏障（性能）

单独用任何一种都不行。所以混合：

func writePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
	// 1. 删除屏障（Yuasa）：旧值涂灰
	shade(*slot)
 
	// 2. 插入屏障（Dijkstra）：新值涂灰
	if currentStackIsBlack() {
		shade(ptr)
	}
 
	*slot = ptr
}

★ 为什么这样就够了（推导）：

① GC 开始时 STW，扫描所有栈，把栈上可达的对象全部涂黑
   之后栈被标记为"黑色"

② 并发标记期间，堆上的所有写都被屏障保护
   → 破坏条件 ①（插入屏障）
   → 破坏条件 ②（删除屏障）

③ 栈上的写不加屏障，但：
   · 标记期间新分配的对象直接标黑（不会新增白色对象）
   · 栈删除引用时，旧值要么还在别处可达，要么已被删除屏障涂灰

★ 净效果：不需要重新扫描栈，STW 只有两个极短的（各 <100μs）

老陈：这个设计的精髓：

不是”两种屏障取并集更保险”，而是—— “栈不加屏障”这个约束，逼出了一个必须同时用两种屏障的解。

这不是创新，是求解。先写下约束，然后推导出唯一可行方案。

第 4 章推导 B+Tree 时你见过同样的思路：先写下”磁盘 IO 单位是页”这个约束，B+Tree 几乎是唯一解。

---

v8：还差什么

到这里，Go 的 GC 基本成型了。剩下的是工程细节：

机制	解决的问题
gcAssist	用户分配太快，标记跟不上 → 让分配者帮忙标记（负反馈）
Pacer	决定什么时候开始下一轮 GC（平衡 CPU 和内存）
Scavenger	把空闲的物理页还给 OS
MemoryLimit	Go 1.19+ 的软内存上限（容器环境必备）

---

★ 这一节真正的收获

需求: 自动回收垃圾内存
  │
  ├─ v0 引用计数
  │    失败: ★ 循环引用（局部信息判断不了全局可达性）
  ↓
  ├─ v1 标记-清除               ← 改用全局追踪
  │    失败: STW 长；碎片；清扫 O(堆)
  ↓
  ├─ v2 标记-整理               ← 解决碎片
  │    失败: 移动对象 → cgo 不兼容；停顿更长
  ↓
  ├─ v3 复制式                  ← 只处理存活对象
  │    失败: 浪费一半内存
  ↓
  ├─ v4 分代                    ← 利用"朝生夕死"假说
  │    Go 没选: 逃逸分析让堆对象长寿，收益不足；且需要 Card Table
  ↓
  ├─ v5 并发三色标记            ← 解决 STW
  │    失败: ★ 漏标（归因：黑→白新增 + 灰→白删除，需同时满足）
  ↓
  ├─ v6 写屏障
  │    Dijkstra: 不重扫栈不行
  │    Yuasa:   精度低
  ↓
  └─ v7 混合写屏障              ← "栈不加屏障"逼出的唯一解

五个可以迁移的思维模式

① 局部信息 vs 全局信息

引用计数（局部）判断不了循环垃圾；追踪式 GC（全局）可以。 当你发现”局部最优”导致错误时，问：是不是缺了全局信息？

② 精确归因是设计的前提

漏标归因成”两个条件同时满足” → 直接给出两种屏障（各破坏一个）。 归因不精确，就找不到下手点。

③ 约束逼出唯一解

“栈不加屏障” + “要并发” → 必须混合屏障。 先写下所有约束，答案往往是唯一确定的。

④ 用负反馈代替硬限制

gcAssist 不是”限制分配速率”，而是”让制造垃圾的人承担清理成本”。 同样的思路：TCP 拥塞控制、背压、熔断。

⑤ 接受”有条件的正确”

Go 不分代是基于当前场景的判断。场景变了，结论可能反转。 对每个设计决策，问：“这个结论依赖什么前提？前提变了会怎样？“

---

现在，轮到你了

练习：Go 的 GC 有个特点——不移动堆对象。

如果让你设计一个”可以整理碎片”的 Go GC（即移动对象），你会遇到什么问题？

提示（不要用，先自己想）：

• cgo 持有的 Go 指针怎么办？
• unsafe.Pointer 存的数值（不是真指针）怎么办？（这是保守式 GC 的难题）
• 移动时 STW 多久？
• 有没有办法并发移动？（想想 ZGC 的”颜色指针”和 Shenandoah 的”Brooks 指针”）
• Go 有精确的类型信息（GC bitmap），这对移动对象有什么帮助？

老陈：答案是：Go 有精确类型信息，理论上可以移动对象。

难点在 cgo 和 unsafe.Pointer。

Go 团队的选择是：不移动，用 size class 缓解碎片。

但如果你在做自己的 runtime（比如 TinyGo 或某个嵌入式场景），这个权衡可能不一样。

这就是”设计”——没有标准答案，只有针对约束的判断。

---

下一节

01 · 运行时解剖：JVM · V8 · Go 三方对照

这一节我们推导了 Go 为什么这么做，下一节看看别人（JVM、V8）在同一个问题上的不同选择，以及各自的理由。

带着这个问题去读：如果 Go 当初没有 cgo 兼容的包袱，它的 GC 会是什么样？