Golang Garbage Collection

前言

内存管理是程序员开发应用的一大难题。传统的系统级编程语言（主要指C/C++）中，程序员必须对内存小心的进行管理操作，控制内存的申请及释放。稍有不慎，就可能产生内存泄露问题，这种问题不易发现并且难以定位，一直成为困扰开发者的噩梦

如何解决这个头疼的问题呢？过去一般采用两种办法：

• 内存泄露检测工具。这种工具的原理一般是静态代码扫描，通过扫描程序检测可能出现内存泄露的代码段。然而检测工具难免有疏漏和不足，只能起到辅助作用
• 智能指针。这是 c++ 中引入的自动内存管理方法，通过拥有自动内存管理功能的指针对象来引用对象，是程序员不用太关注内存的释放，而达到内存自动释放的目的。这种方法是采用最广泛的做法，但是对程序员有一定的学习成本（并非语言层面的原生支持），而且一旦有忘记使用的场景依然无法避免内存泄露

为了解决这个问题，后来开发出来的几乎所有新语言（java，python，php等等）都引入了语言层面的自动内存管理 – 也就是语言的使用者只用关注内存的申请而不必关心内存的释放，内存释放由虚拟机（virtual machine）或运行时（runtime）来自动进行管理。而这种对不再使用的内存资源进行自动回收的行为就被称为垃圾回收

常见的垃圾回收方法

引用计数（reference counting）

这是最简单的一种垃圾回收算法，和智能指针异曲同工。对每个对象维护一个引用计数，当引用该对象的对象被销毁或更新时被引用对象的引用计数自动减一，当被引用对象被创建或被赋值给其他对象时引用计数自动加一。当引用计数为0时则立即回收对象。这种方法的优点是实现简单，并且内存的回收很及时。这种算法在内存比较紧张和实时性比较高的系统中使用的比较广泛，如ios cocoa框架，php，python等。简单引用计数算法也有明显的缺点：

• 频繁更新引用计数降低了性能。一种简单的解决方法就是编译器将相邻的引用计数更新操作合并到一次更新；还有一种方法是针对频繁发生的临时变量引用不进行计数，而是在引用达到0时通过扫描堆栈确认是否还有临时对象引用而决定是否释放等
• 循环引用问题。当对象间发生循环引用时引用链中的对象都无法得到释放。最明显的解决办法是避免产生循环引用，如cocoa引入了strong指针和weak指针两种指针类型。或者系统检测循环引用并主动打破循环链。当然这也增加了垃圾回收的复杂度

标记-清除（mark and sweep）

该方法分为两步，标记从根变量开始迭代遍历所有被引用的对象，对能够通过应用遍历访问到的对象都标记为“被引用”；标记完成后进行清除操作，对没有标记过的内存进行回收（回收同时可能伴有碎片整理操作）。这种方法解决了引用计数的不足，但是也有比较明显的问题：每次启动垃圾回收都会暂停当前所有的正常代码执行，回收使系统响应能力大大降低！当然后续也出现了很多mark&sweep算法的变种（如三色标记法）优化了这个问题

标记-清除可视化如下：

分代收集（generation）

经过大量实际观察得知，在面向对象编程语言中，绝大多数对象的生命周期都非常短。分代收集的基本思想是，将堆划分为两个或多个称为 代（generation）的空间。新创建的对象存放在称为 新生代（young generation）中（一般来说，新生代的大小会比 老年代小很多），随着垃圾回收的重复执行，生命周期较长的对象会被 提升（promotion）到老年代中。因此，新生代垃圾回收和老年代垃圾回收两种不同的垃圾回收方式应运而生，分别用于对各自空间中的对象执行垃圾回收。新生代垃圾回收的速度非常快，比老年代快几个数量级，即使新生代垃圾回收的频率更高，执行效率也仍然比老年代垃圾回收强，这是因为大多数对象的生命周期都很短，根本无需提升到老年代

Golang各版本GC延迟及主要优化点

数据来源自Twitter，参考这里

• 1.4-1.5——300~400ms

Prior to Go 1.5, Go has used a parallel stop-the-world (STW) collector.  While STW collection has many downsides, it does at least have predictable and controllable heap growth behavior

• 1.5——30~40ms

Go 1.5 introduces a concurrent collector. Go’s new garbage collector is a concurrent, tri-color, mark-sweep collector

• 1.6——0~50ms

The improvement was largely due to systematically eliminating all the O(heap) things we were doing during the stop the world time

• 1.7——0~5ms

Again we kept knocking off these O(heap size) stop the world processes. We had much larger heaps and as we knocked off these O(heap size) stop the world pauses, the size of the heap could obviously grow considerable without impacting latency. So this was a bit of a help in 1.7

• 1.8-1.9——0~1.5ms

We had the last of our large latency drops which was due to figuring out how to avoid the stop the world stack scanning at the end of the GC cycle. That dropped us into the sub-millisecond range. 

Golang Garbage Collection Process

Go uses a concurrent collector. Go’s new garbage collector is a concurrent, tri-color, mark-sweep collector

In a tri-color collector, every object is either white, grey, or black and we view the heap as a graph of connected objects. At the start of a GC cycle all objects are white. The GC visits all roots, which are objects directly accessible by the application such as globals and things on the stack, and colors these grey. The GC then chooses a grey object, blackens it, and then scans it for pointers to other objects. When this scan finds a pointer to a white object, it turns that object grey. This process repeats until there are no more grey objects. At this point, white objects are known to be unreachable and can be reused.

也即：

• 起初所有对象都是白色
• 从根出发扫描所有可达对象，标记为灰色，放入待处理队列
• 从队列取出灰色对象，将其引用对象标记为灰色放入队列，自身标记为黑色
• 重复 3，直到灰色对象队列为空。此时白色对象即为垃圾，进行回收

And this figure will show below the Process of Golang Garbage Collection

可视化如下：

Golang GC Write barrier(写屏障)

如上图可知，Write barrier(写屏障)在第一次扫描完，标记入队后，反复标记时开启，sweep前关闭，这里举一个例子来说明一下Write barrier作用：

• Stack scan

stack->a->b——a为栈中申请的对象，b为堆中申请的对象，a对象中存在对b的引用

stack->c——c也是栈中申请的对象

• Mark

这里a，c都会被标记为灰色；b为白色

由于是并发的mark，我们假设c先被处理，c没有引用其他对象，所以直接置黑，从队列中取出；此时c为黑色，a为灰色，b为白色

假设这时用户做了如下操作：

a=nil
new(d)
c->b

也即，将a中对b的引用置为空（你也可以理解为将a中对其他任何内存对象的引用都清空），随即申请d对象，然后在c中增加对b的引用

由于c已经是黑色，所以不会再去扫描他，那么本次内存扫描就不可能找得到b；而d对象由于刚申请出来，还没有被引用，所以这里只对a进行了mark：a：黑色，b：白色；c:黑色；d：白色

这时用户又做了如下操作：

b->d

由于b无法被扫描到，这里显然d也不会被扫描到。 这样的状况会一直持续到这轮反复mark结束（即灰色队列为空）

stop the world， mark termination and sweep。 整个GC结束， b，d的内存空间都是白色，所以在sweep时会被清理掉。如何避免这种误清理呢？

写屏障(Write barrier)的功能就是在c->b发生时，对b标记为灰色，入队， 以及在b->d发生时，对d标记为灰色，入队，这样，在整个反复mark阶段结束时，我们能确保这段时间新发生的对白色对象的内存引用操作都被处理到（变黑），b和d就不会被误清理

简而言之，写屏障的作用是：可以确保不会有对象A直接引用白色对象B（发生时将白色对象置灰）

Refs

• Go的三色标记GC
• Why do garbage collection? Won’t it be too expensive?
• Getting to Go: The Journey of Go’s Garbage Collector
• Golang GC 垃圾回收机制详解
• Go 1.5 concurrent garbage collector pacing
• What kind of Garbage Collection does Go use?
• golang分享.pptx
• Golang 垃圾回收剖析