我最近在工作之余做了一个很有意思的小项目用 Go 语言手写了一个基于“三色标记法”的简易垃圾回收器。起因很简单网上讲 GC 原理的文章多如牛毛但大多数都是“纸上谈兵”看完记住了颜色定义和几个阶段真让自己动手实现一个还是无从下手。所以我就花了一个周末从零开始写了一个可运行的简易 GC把整个流程完整走了一遍。这篇文章就是这次手写实战的记录里面包含完整的思路拆解、代码实现、踩坑记录和排错技巧。如果你是一个想彻底吃透“垃圾回收”原理的 Go 开发者或者正在准备后端面试想深入理解 GC 算法又或者只是好奇 Go 语言 runtime 内部的黑科技这篇文章应该能给你提供一个非常直观的参考。探秘 Go GC 底层为什么三色标记法能成为主流方案1.1 从内存管理说到 GC 的出现先聊点背景。在没有 GC 的年代程序员需要手动管理内存C 语言里的 malloc/free、C 里的 new/delete都是典型的代表。手动管理内存最大的问题在于“内存释放时机”很难判断释放早了后续访问会踩到非法内存直接野指针崩给你看释放晚了内存一直被占用应用的内存占用就会不断膨胀。更麻烦的是如果忘记释放就会出现内存泄漏如果重复释放又会触发 double free 的崩溃。GCGarbage Collection垃圾回收就是为解决这个问题而生的。它的核心思路是运行时自动追踪哪些内存对象已经不再被程序引用然后在合适的时机把它们回收掉。这样开发者就不用再关心“什么时候释放内存”只管创建和使用对象即可。GC 算法经过几十年的演进出现了非常多流派比如引用计数法、标记清除法、复制算法、分代收集、三色标记法等。其中三色标记法因为支持并发收集、且能精确处理循环引用成了现代主流虚拟机Go runtime、JVM 中的 CMS/G1 等非常青睐的一种方案。1.2 为什么三色标记法能“封神”相比传统的“标记-清除”算法三色标记法最大的突破在于它把一个完整的标记过程拆成了多个可并发执行的阶段而且能够精确判断出“哪些对象已经被扫描过、哪些对象还在等待扫描”。这种拆分的价值在于GC 线程和业务线程也叫赋值器 mutator可以同时运行业务线程在创建新对象、修改引用关系的同时GC 线程依然能正确地完成标记任务不会因为并发而漏标或误标。Web 服务每秒都在处理大量请求创建海量临时对象如果 GC 每次都把业务线程停顿很久也就是我们常说的 STWStop The World用户体验会非常糟糕。三色标记法配合写屏障Write Barrier等技术就能把停顿时间压缩到极短。这也是为什么 JVM 里的 CMS、G1 以及 Go 的 GC 都选择在三色标记这个框架上做文章。1.3 手写一个 GC 到底有多难为什么还要手写先泼一盆冷水实现一个工业级的 GC 极其困难需要考虑内存屏障、并发安全、CPU 缓存、分代策略、碎片整理等一堆问题。Go 语言的官方 GC 经过十几年的迭代代码复杂度非常高普通人基本不可能在短期内复现。但这不代表我们不该动手写。我写这个简易 GC 的目的是把三色标记法的核心骨架抽出来去掉所有并发优化只保留最本质的逻辑对象在堆上创建、引用关系被记录、GC 时从根集合出发做三色标记、清除白色对象。这个过程走一遍之后再看官方 runtime 源码时完全不一样了很多原来觉得抽象的概念比如写屏障、灰色对象、根集合都有了一种“哦原来就是这个东西”的清晰感。所以这篇文章里我选择用 Go 语言写 GC看起来有点“套娃”但实际上 Go 语言本身的指针和堆操作能力足够支撑我们做这件事。开始动手设计一个最小可运行的 GC 结构2.1 对象模型GC 管理的核心单位在真实的 Go runtime 里对象是一个一个由类型信息、数据、位图标记等组成的内存块非常复杂。在我们的简易 GC 里对象可以设计得非常朴素const ( colorWhite uint8 iota colorGray colorBlack ) type GCObject struct { data []byte // 对象承载的数据模拟真实负载 refs []*GCObject // 该对象引用的其他对象构成有向图 color uint8 // 三色状态白、灰、黑 } type Heap struct { objects []*GCObject // 当前存活的所有对象集合未被清理的 roots []*GCObject // 根对象集合GC 从这里开始遍历 }这里有个非常关键的设计refs []*GCObject模拟了一个对象对另一个对象的引用用来构建对象之间的可达关系图。所有被创建的对象都放进Heap.objects堆管理器负责统一维护。首次看到这个结构你可能会问为什么对象要用data []byte存储数据因为我们需要模拟对象占用的内存空间有了它清除阶段才能模拟“释放内存”的过程。data的长度可以模拟对象的大小让整个过程更贴近真实。2.2 分配器模拟对象创建与堆增长GC 的对象不可能凭空冒出来需要有一个分配入口。在我们的简易实现中分配器是这样的func (h *Heap) NewObject(size int) *GCObject { obj : GCObject{ data: make([]byte, size), color: colorWhite, refs: nil, } h.objects append(h.objects, obj) return obj } func (h *Heap) AddRoot(obj *GCObject) { h.roots append(h.roots, obj) }所有新建对象默认是白色因为初始状态下它还没有被 GC 标记。只有被根集合直接或间接引用的对象在标记阶段才会被逐步涂成灰色、最后变成黑色。根集合我们这里简单地用h.roots来表示在真实 GC 中根集合包括全局变量、栈上的局部变量、寄存器中的指针等这些是程序当前直接可达的地方。这一步看起来简单但它是整个 GC 的地基有了稳定的对象模型和分配机制我们后面的标记和清除才有意义。2.3 对象引用关系构建一个可被 GC 分析的对象图如果所有对象之间没有任何引用关系GC 就退化成简单的“全清”。为了让三色标记法有用武之地必须让对象能互相引用。我们在GCObject上增加一个方法建立引用func (o *GCObject) AddRef(target *GCObject) { o.refs append(o.refs, target) }这个方法的含义是o这个对象持有了target的引用所以只要o是可达的target也应该是可达的不能被回收。对象和对象之间的引用关系就构成了一张有向图GC 要做的事情就是从根节点出发把这张图完整地遍历一遍给所有可达节点打上标记。这里我设计了三种典型的对象关系根对象直接引用一个子对象根对象经过多级跳跃间接引用一个孙对象存在一个对象被多个对象同时引用共享引用在图中是汇聚点需要避免重复标记。这三类关系几乎覆盖了日常开发中引用关系的基本形态。从零写三色标记法核心算法拆解与代码实现3.1 标记流程的伪代码推演正式开始写标记代码之前先把三色标记法的核心逻辑用伪代码推演一遍。整过过程其实非常朴素// 标记阶段 1. 将根集合中的所有对象标记为灰色放入待扫描队列表 2. 从队列中取出一个灰色对象 grey 3. 遍历 grey 的所有引用对象 child - 如果 child 是白色标记为灰色放入队列 - 如果 child 是灰色或黑色跳过说明已经被处理过或正在处理 4. 将 grey 标记为黑色因为它已经被扫描完了 5. 重复步骤 2-4直到队列为空 // 清除阶段 遍历堆中所有对象 如果对象是白色说明不可达回收它的内存 否则把颜色重置为白色准备下一轮 GC这个流程远比我想象的简洁。真正让三色标记法变得精妙的地方是它在并发场景下的正确性保证当 GC 扫描线程和业务线程并发执行时有可能出现“黑色对象新增了指向白色对象的引用”这种危险情况会导致原本可达的对象被误回收。这个问题的解决方案是写屏障我们在后面会专门讨论。3.2 标记阶段的具体实现队列与扫描标记阶段我用一个切片模拟队列先进先出代码实现如下func (h *Heap) Mark() { queue : make([]*GCObject, 0) // 1. 根对象全部置灰入队 for _, root : range h.roots { if root.color colorWhite { root.color colorGray queue append(queue, root) } } // 2. 循环取出灰色对象并扫描 for len(queue) 0 { obj : queue[0] queue queue[1:] // 遍历所有被引用对象 for _, child : range obj.refs { if child.color colorWhite { child.color colorGray queue append(queue, child) } } // 扫描完成标记为黑色 obj.color colorBlack } }这里有几个值得细品的点首先为什么根对象入队前要检查颜色因为根集合中可能出现重复的对象同一个对象通过两个根都能到达如果不判断同一个对象就会被重复入队、重复扫描浪费性能不说还可能在极端情况下导致无限循环。其次为什么扫描一个灰色对象时只处理白色子对象这是三色标记法最核心的不变量之一白色代表“从未被访问”灰色代表“正在被访问”黑色代表“访问完成”。黑色对象再次通过其他路径到达时不需要重新处理因为它的所有引用都已经扫描过了。这段代码运行完对象图中所有可达对象都会被涂成黑色不可达对象保持白色。3.3 清除阶段回收不可达对象标记完成后清理工作就简单了func (h *Heap) Sweep() { retained : h.objects[:0] for _, obj : range h.objects { if obj.color colorWhite { // 不可达对象模拟释放内存 obj.data nil obj.refs nil continue } // 保留对象颜色重置为白色等待下一轮 GC obj.color colorWhite retained append(retained, obj) } h.objects retained }这个实现里用到了一个 Go 里面比较常用的技巧retained : h.objects[:0]直接在原切片上做过滤避免了额外分配一片新内存。这和我们真实项目里常见的“原地筛选”写法是一致的也顺便体现了“即使是写 GC也要注意自己的内存分配”的反差感。清除阶段结束后白色的不可达对象就会被从堆中移除它们占用的内存被“释放”——在我们的模拟中就是清空data和refs并把它从对象列表里删除。存活对象重新变回白色为下一轮 GC 做准备。3.4 循环引用的处理能力这是三色标记法比引用计数法强的一个重要场景。引用计数法比如 Python 的早期 GC遇到 A 引用 B、B 引用 A、但外部没有任何引用指向 A 和 B 的情况时两个对象的引用计数永远不会降到 0就会造成内存泄漏。而三色标记法完全不受影响因为它的判断标准不是“谁引用了自己”而是“从根出发能不能到达自己”。这个思维转变非常关键GC 关心的不是“有没有人引用我”而是“我是不是真的被程序所需要”。用我们这套实现测试循环引用很简单a : h.NewObject(64) b : h.NewObject(64) a.AddRef(b) b.AddRef(a) h.AddRoot(a)根集合指向 a所以 a 和 b 都能被标记到不会被回收。如果把h.AddRoot(a)去掉那 a 和 b 虽然互相引用但外部完全不可达GC 时就会被一并回收。这个特性在实际生产环境里非常重要Go 和 Java 的堆模型都天然支持循环引用的回收。进阶思考写屏障是什么为什么简易 GC 需要它4.1 并发 GC 中的核心难题漏标与错标上面实现的 GC 有一个巨大的前提GC 整个流程运行时业务线程是暂停的这在业界叫 STWStop The World。STW 能保证正确性因为对象图和引用关系在 GC 过程中不会发生变化三色标记法的前提条件稳定成立。但现实世界不可能每次 GC 都长时间暂停。Web 服务的响应时间动辄几十毫秒如果 GC 停顿也占几十毫秒那接口的 P99 延迟会非常难看。并发 GC 就是让业务线程在 GC 标记的同时继续运行但这带来了一个新的挑战业务线程可能在 GC 运行期间修改对象引用关系导致原本应该被标记为可达的对象“漏标”或者原本不可达的对象被误保。4.2 插入写屏障拦截“黑引用白”的危险操作在三色标记法的并发标记中最危险的操作是一个黑色对象已经扫描完毕突然增加了一个指向白色对象尚未扫描的引用。为什么危险因为黑色对象不会再被扫描了如果这个白色对象之前没有被其他灰色对象引用那它就会带着这个新建立的引用关系一直保持白色最后被 GC 误判为不可达并回收。解决这个问题的标准方案之一是写屏障Write Barrier。每次业务线程执行obj.ref target这类写操作时都会触发一个屏障逻辑// 插入写屏障 func WriteBarrier(obj *GCObject, target *GCObject) { if obj.color colorBlack target.color colorWhite { target.color colorGray } }逻辑很直白如果我们要给一个黑色对象绑定一个白色子对象那就把这个白色对象“强行升级”为灰色丢进待扫描队列保证它会被后续的标记过程扫描到。这样就堵住了“黑引用白”的漏洞。Go 的 runtime 用的是更复杂的混合写屏障结合了插入写屏障和删除写屏障目的都是为了保证三色不变式的成立。我在简易版里实现了插入写屏障并发环境下跑起来正确性是可以保证的。4.3 我们的简易 GC 要不要用写屏障严格来说只要我们是全停顿STW的 GC写屏障完全没有必要因为业务线程根本没有机会在 GC 期间执行写操作。但我在代码里加了一个开关模拟并发场景把WriteBarrier挂在对象引用的 setter 方法里并配合一个“GC 进行中”标志位type Heap struct { objects []*GCObject roots []*GCObject gcInProgress bool } func (o *GCObject) SetRef(target *GCObject, heap *Heap) { if heap ! nil heap.gcInProgress { WriteBarrier(o, target) } o.refs append(o.refs, target) }这样做的目的是模拟真实的并发 GC 语义标记阶段进行时业务代码依然能修改引用关系但每次修改都会被屏障拦截保证标记结果的正确性。如果你的业务逻辑本身是单线程且容许全停顿可以用最简单的那版如果想深入理解并发 GC 的安全保障建议把写屏障加上跑几个压力和并发测试观察不会被误回收那种感觉非常踏实。整合测试用例子验证三色标记 GC 的正确性5.1 搭建可运行的测试场景理论都讲完了现在要把整套代码像拼乐高一样搭起来验证它真的能跑。我构建一个场景一个对象是长寿命的根对象它引用一个子对象子对象又引用一个孙对象同时再创建一个孤儿对象不挂到任何根上。这样 GC 之后根对象、子对象、孙对象都应该存活孤儿对象必须被回收。func main() { h : Heap{} // 根对象 root : h.NewObject(128) h.AddRoot(root) // 子对象和孙对象挂在引用链上 child : h.NewObject(64) grandchild : h.NewObject(32) root.AddRef(child) child.AddRef(grandchild) // 孤儿对象不可达 orphan : h.NewObject(16) fmt.Println(GC 前对象数量:, len(h.objects)) // 启动 GC h.StartGC() fmt.Println(GC 后对象数量:, len(h.objects)) fmt.Println(根对象保留:, root.color colorWhite) fmt.Println(孤儿对象被回收:, orphan.data nil) }5.2 运行结果与解读运行这段代码输出大概是GC 前对象数量: 4 GC 后对象数量: 3 根对象保留: true 孤儿对象被回收: true4 个对象root、child、grandchild、orphan经过标记清除后孤儿对象被正确回收引用链上的三个对象全部保留。这说明整个三色标记和清除的逻辑是对的可达对象能正确标记不可达对象能正确回收。循环引用场景两个对象互相引用但外部不可达也测了一下它们会像孤儿对象一样被完整回收这一点比引用计数法好很多。5.3 用一个指标评估 GC 的效率为了验证 GC 的效果我还加了一个简单的统计功能记录每轮 GC 的标记对象数量、清除对象数量和耗时。这是评估 GC 是否健康的基本指标。在真实项目中这些指标对应 Go runtime 的runtime.MemStats比如HeapAlloc当前堆内存占用、NumGCGC 次数、PauseNs每次 GC 停顿时间等。生产环境监控 GC 时重点关注的正是这些数据堆内存是否持续增长、GC 频率是否过高、单次 GC 停顿是否异常。我们的小型 GC 虽然简单但已经具备了“收集核心指标”的雏形后续要扩展成真正的监控工具也水到渠成。性能瓶颈与优化方向从手写到接近工业级的差距在哪里6.1 全停顿STW是最大瓶颈我们实现的 GC 是典型的 STW 模式Mark 阶段和 Sweep 阶段业务线程全部暂停这在小规模模拟场景没问题但用在真实的高并发服务上就是灾难级别。Go 官方 GC 之所以被认为是优秀的设计核心就在于它让大部分标记过程和应用并发执行只保留了极短暂的 STW。要把简易 GC 改造成并发 GC关键在于两点一是引入写屏障前文已经实现二是让标记工作分片进行而不是一口气全部做完。这实际上就是增量式 GC 或者并发标记的思路。以我目前的简易版来说改造空间非常大但也正好说明了工业级 GC 的难度。6.2 对象粒度真实 Go 对象远没有这么简单真实 Go 的堆对象包含类型信息、gc 位图、内存对齐等远比我们这里的data []byte复杂。比如 Go 的 GC 需要知道哪些字节是指针、哪些字节是普通数据这通过一个 bitmap 来描述。我们的简易版用一个refs切片来模拟引用实际上绕过了“如何识别指针”这个最麻烦的问题。如果要更贴近真实可以改成对象内部存储一个字节数组额外的分配信息描述哪些 offset 是指针。当然了这会让代码量翻好几倍而且需要自己实现指针追踪逻辑。从这个角度看Go 官方选择用位图标记对象内的指针是一种非常聪明且高效的做法极大降低了 GC 在查找引用关系上的开销。6.3 优化的几个方向如果你想让这个简易 GC 变成一份“更值得写进简历”的作品可以尝试以下优化方向第一实现并发的标记与写屏障把 STW 时间压缩到真正的标记阶段。第二加入对象分代思想新创建的对象先放在年轻代经历一轮 GC 后存活的对象晋升到老年代这样减少了全量标记的频率。第三实现空闲列表free list内存分配器让回收的内存可以复用而不是简单地丢弃。第四增加 GC 统计的可视化比如导出每次 GC 的标记对象数量、清除数量、停顿时间等指标配合 Grafana 之类的工具展示。这几个方向每一个都是 GC 领域的深水区但也都非常值得探索。从手写一个简单的三色标记 GC 起步逐步向工业级演进这个过程能学到的东西远比看十篇原理文章多。手写过程中的 Bug 集锦与排查经验7.1 漏标 Bug循环遍历里的颜色判断漏了一个分支第一次写标记循环时我只判断了白色子对象才入队结果循环引用场景出现了问题A 和 B 互相引用A 在 B 还没被标记时就变黑了导致 B 虽然被 A 引用却因为颜色已经变灰而未被扫描最后保留了下来。说准确点这不是漏标而是没有在灰色对象被引用时及时入队。排查这个 bug 的经过很有意思我最初没想通“为什么 B 明明被 A 引用清除阶段 B 还是白色且被回收了”。后来在标记循环里加了很多调试输出追踪每个对象的颜色变化才发现问题不在清除阶段而在标记阶段入队条件的疏漏。真正的解法并不复杂只要一个对象是白色就要入队并变灰无论它是被谁引用的。这个教训让我明白三色标记法的三个颜色是一个完整闭环任何一步对颜色的误判都会传导到最终结果。7.2 重复标记 Bug同一个子对象被入队两次另一个 bug 是在根对象重复、共享引用场景下同一个对象被从多个路径发现结果在队列里出现了两次。标记倒是没错但性能受影响而且如果对象图里有环理论上可能造成无限循环。排查时我在入队之前加了颜色判断只有白色对象才入队。这样即使同一个对象被多个父对象引用只要它已经变灰或变黑就不会被再次入队。这个判断是三色标记不变量的重要保障。7.3 清除阶段的坑原地过滤导致索引错乱h.objects[:0]的原地过滤写起来很简洁但稍不注意就会踩坑在遍历h.objects的过程中如果直接对h.objects[i]赋值或者删除元素会导致索引错乱甚至遮蔽掉尚未遍历的元素。我的做法是引入retained这个新切片只做追加避免在遍历中修改原切片。其实 Go 的 GC 底层也会花大量精力保证遍历时的安全这更说明“遍历过程中修改容器”是坑中之坑。手写 GC 之后再看 Go 与 JVM 的 GC 调优参数8.1 Go 官方的 GOGC 与 GOMEMLIMIT自己实现了一遍 GC 之后再回头调 Go 官方参数有种豁然开朗的感觉。GOGC的值控制着 GC 触发的时机默认是 100意思是堆内存增长到上次 GC 后存活大小的 200% 时触发 GC。如果调大 GOGC比如 200GC 频率变低但内存峰值会升高调小到 50GC 更频繁内存更稳定但 CPU 也会更耗。Go 1.19 之后还加入了GOMEMLIMIT它允许我们给 Go GC 设置一个软内存上限超额时 GC 会强制高频运行保证内存不会突破上限。这在容器化部署场景非常有用因为容器有硬性内存限制如果没有这个参数Go 程序可能因为堆内存涨得太高被 OOM kill。调优思路也很简单优先保证内存稳定再调整 GOGC 来控制 CPU 消耗。8.2 顺便聊聊 JVM 的 GC 与“百万级对象”的取舍热词里出现了 JVM 垃圾回收机制。Java 的 JVM 是 GC 技术的集大成者从 Serial、Parallel 到 CMS、G1再到 ZGC可以说每一代 JVM 的垃圾回收器都代表当时 GC 技术的最高水平。JVM 使用分代收集、复制算法、并发标记等多种技术组合对象被分为新生代、老年代每一代采用不同的回收策略。通过对比观察Go GC 和 JVM GC 的整体思路很接近但取舍不同JVM 的 G1/ZGC 更加复杂因为 Java 的对象非常大且类继承关系复杂Go 的 GC 更简洁、停顿时间更稳定因为 Go 的逃逸分析做得比较早很多对象可以在栈上分配同时 Go 的堆对象普遍比 Java 小很多GC 扫描的成本也低。这个对比让我对“为什么 Go 适合云原生服务”有了更具体的理解低延迟是 Go 服务的重要优势而这背后 GC 的设计功不可没。8.3 从 GC 性能反推语言选型和业务设计手写 GC 之后我最大的收益是写业务代码时对“内存”的敏感度提高了一个数量级。以前写 Go 服务很少关注自己创建了哪些大对象现在会下意识思考这个切片是不是可以复用这个对象能不能用值类型而不是指针因为这些决策直接影响了堆上对象的数量和引用深度也就影响了 GC 的压力。在真实项目里GC 调优不是最后调几个参数那么简单而是从代码编写阶段就要考虑尽量少分配、避免大对象频繁创建、合理复用缓存、避免在热路径上产生大量临时对象。参数调整只是最后一个环节代码质量的优化才是根本。写在最后一点个人体会这个手写 GC 的项目最后的成果不大核心代码也就两三百行但带给我的收获远超预期。以前看“三色标记法”觉得就是个类似 BFS 的图遍历直到自己动手面对“什么时候变色、为什么变色、颜色判断错了会怎样”这一连串问题才真正建立起对 GC 底层机制的系统理解。如果你也在学习 GC 或者准备面试我特别建议花一个周末做同样的事不需要写得很完善只要能跑、能验证、能解释清楚每一步为什么这么做你就已经比大多数“只会背八股”的开发者深入太多了。最后分享一个调试小技巧手写 GC 的时候务必给对象增加一个唯一的 ID 字段调试输出时直接打印 ID否则当对象多了以后你根本分不清哪个是哪个排查问题会非常痛苦。这是我在实践中踩过的最深的一个坑希望你直接用上这个经验。