从垃圾回收解开Golang内存管理的面纱之三垃圾回收

四、垃圾回收

终于说到垃圾回收了，我的初衷就是要搞明白垃圾回收的算法，谁知道衍生出来那么多东西，哈哈。

5.1 常见垃圾回收策略

所谓垃圾回收，即为释放我们不再使用的对象的内存，话不多说，我们一一分析目前的垃圾回收的算法，并且我们会重点说下Golang目前的三色标记算法。要了解垃圾回收，首先我们先了解三个基本的概念，首先是mutator和collector，这两个名词经常在垃圾收集算法中出现，collector指的就是垃圾收集器，而mutator是指除了垃圾收集器之外的部分，比如说我们应用程序本身。其次就是根对象roots，我们一般有一个认知，垃圾回收都是回收堆上的内存，那么我们的根对象就是堆之外的并且是被我们的程序访问得到的，比如C++的静态变量，栈上的对象等等。这里说一句，golang的根对象就是协程栈上的指针对象。

5.2 标记-清除

标记清除是最简单的也是最古老的垃圾回收算法。它的思想很简单：

1.先从根对象开始扫描，当我们的根对象指向了某个堆上的对象，我们就认为这个对象是可达的。

2.可达对象指向的对象也是可达对象。

3.从根对象开始遍历，采用深度遍历或者广度遍历（二者的方式网上都有说法，但是我认为都行，个人更偏向于广度遍历，这种事一种解决的思路，具体怎么实现看个人）我们画个图看看

如上图，根对象指向了A、B，说明A、B是可达的，同理F、G、D都是可达的对象，但是C、E就是不可达的对象，它们是要被清理的。我们再来看看它的整个流程：

1.触发垃圾回收事件发生，一般是当申请堆内存的时候，做一个检测机制，或者定时回收 2.STW（Stop The World），挂起整个程序，等待GC

3.从根对象开始扫描，在每个可达的对象的header做一个标记

4.清除阶段，扫描整个堆，发现是活跃对象的话（根据header的标志），则清除掉它的标志位即可。如果发现是非活跃对象即不可达对象，则把对象作为分块，连接到被称为“空闲链表”的单向链表。在之后进行分配时只要遍历这个空闲链表，就可以找到分块了。

5.清除完成，继续程序。分析算法的优缺点：

1.这个算法的优点就是思想简单，很好实现

2.算法有一个缺点是会容易产生要多的碎片

3.分配的时候速度较低，我们刚才说过分配的是遍历空闲链表，最坏的情况是遍历到最后也没有找到合适的

4.以上的问题我们都可以用其一些方法缓解，比如合并连续的区域，比如多个空闲链表等，但是我认为标记清楚最大的一个缺点就是STW，这个很多场景下不能容忍的，我们先来分析下为什么要STW，想象一下，当你的标记阶段正在进行中，而你的程序也在跑，突然创建了一个新对象，也是可达的，比如如下图所示

当我已经标记完D之后，认为到它这就完事了，但是我们创建的新对象H就会在清除节点被认为是不可达的，最终被清理掉。在清除阶段也会遇到同样的问题。

5.3 引用计数

对引用计数比较深刻，记得刚开始写C++的时候，所有申请的内存都需要自己去释放，后来C++出了智能指针，解放了程序员释放内存的操作，其实它的原理就是引用计数。其实它的思想也很简答：

1.我们给每个对象都分配一个计数器，代表有多少其他的对象引用我

2.当没有对象再引用我的时候，就代表我没用了，就是垃圾可以被回收了我们来张图看看

如上图所示，我们的节点内的括号代表的是有多少对象引用自己，这里注意以下几个细节：

1.当对象刚被创建的时候，它就代表肯定有一个指针指向自己，所以我们对创建的对象设置计数器为1

2.当我们要更新一个指针的时候，比如A原先指向B，现在我们更改A的指向为C，此时我们会做如下的操作，首先给C的计数器加1，然后再给B的计数器减1。注意，这里为什么要先增加C的计数器而不是先减少B的计数器呢？假设我们的B对象与C对象是同一个对象的时候就会出现问题，假设原先B只有被A指向，所以其计数器为1，当我们先减少B的计数器的时候，发现计数器为0，此时我们就要清理掉它，那么接下来我们再去增加C的计数器的时候（跟B是同一个对象）就会发现该对象已经被清理了。

3.ok，我们继续，看起来我们的挥手操作是发生在引用计数为0的时候,那么当我们遇到某个对象的引用计数为0的时候，就直接回收就完事了吗？不是的，想象一下，当我们要回收对象B时，虽然指向B的引用没有了，但是B指向的对象还是可能存在的，如果我们就直接简单的回收掉，会出现B引用的那些对象的计数永远不会为0，所以我们要把B所有引用的对象给减1，同样的道理如果B引用的对象被减1了后正好也变为0了，我们需要继续递归的更新计数器。

我们来总结下过程：

1.当对象被创建的时候，初始化计数器为1

2.当更新指针的时候，需要检测引用计数是否为0，如果为0则回收掉，放入空闲队列中，并且递归的更新

我们来分析下它的优缺点：

1.首先，我们不难发现，引用计数方法的垃圾回收不会像标记清除那样，专门的去做触发的操作，或者是定时的清除。而且完全不用专门STW，因为它的回收操作完全分布在应用程序运行过程中，这是它最大的优点

2.垃圾会立刻被回收，相比较其他的垃圾回收算法，我们一旦发现引用计数为0就会被立即回收。

3.它的一个缺点就是，指针的更新需要我们去开发人员去手动的操作，如果漏了一个，就可能会出现很多无法回收的对象，造成内存泄露。

4.还有一个重大的bug，就是无法回收循环引用的对象

如上图所示，当我们的A、B对象的情况由左边转换为右边时，就会出现A、B永远不会再被回收的情况

5.在程序中更新指针应该是一个很频发的操作，我们相应的要频繁的更新计数器

6.我们之前说过，当发现一个对象的引用为0的时候，我们需要继续递归的去更新计数器，如果出现极坏的情况，这个递归会非常的深，可能会造成系统的颠簸。

7.还有一个缺点，想象一下，一个对象最多会被多少个指针指向，极端事情是机器所有的对象都会指向该对象，比如32位的机器，它的对象个数最大可达到 2^{32} 个，那么我们的计数器就要是一个32位的数据，这可能会造成极大的空间浪费。以上的一些缺点，很多都有相应的优化的方法，我们这里就不细说了，感兴趣的同学请自行谷歌。

5.4 节点复制

节点复制的想法比较的奇特，我们想想，标记清除算法中有两个阶段，第一步找到活跃的对象给它标记上，第二步扫描整个堆，把其余未标记的对象清除掉，这两个步骤能不能节省一个步骤呢？再有就是我们的对象申请的时候，都是从空闲链表上获取的，找到一个合适大小的内存块这个速度是比较慢的，我们知道栈内存的申请是很快，为什么呢？因为栈是一块连续的空间，申请的时候只需要按照地址增长的申请即可，是O(1)的，堆我觉得至少得O(logN)。 ok，节点复制其实就是为了解决我们提到的以上两个问题。先来看看它是怎么做的吧:

1.首先它是把堆的内存分为两个部分，并且是均分。一个叫From，一个To。

2.From内存块就是我们内存分配的时候用的。

3.当我们要进行GC的时候，我们把活跃的对象直接复制到To内存空间中去，然后直接把To空间换做我们的程序使用的空间，再把From整体清空，然后再把From作为To。思路看起来很简单，但是操作起来还是稍微有些复杂的，我们先给出一个伪代码，该伪代码来自《垃圾回收的算法与实现》：

我们先看第一个函数copying()其实就是我们整体的GC：

1.首先我们把free指针指向To空间的start位置

2.然后我们遍历根对象，调用copy函数把根对象copy到To空间去，注意copy函数返回的是对象在新的空间的位置，而且copy函数是递归的把所有的r对象指向的对象都复制到新的空间去，我们来详细的看下copy函数：

a.首先判断下这个对象是否已经被复制过了，如果复制过，则直接返回它的新空间的指针。 b.如果未被复制过，则先把对象拷贝到新空间的$free处，然后把其标志位设置为已复制，把forwarding设置为其刚才复制的地址（即为新空间的地址）

c.当复制完对象后，再递归的把对象指向的所有的对象都复制到新空间，并且把指向这些指针指向新的空间地址。

3.最后我们再交换两个空间可能在第二步的时候有些绕，我们给出图例就清晰很多，同样引用《垃圾回收的算法与实现》：

来分析下上图，我们第一步先把A复制到新的空间，注意这里我们没有更改A对象中的指针指向，所以A'还是指向老空间的C和D，然后更新A的标志位,如图所示

这样我们就知道A已经被复制过了，然后我们进入循环递归，把C和D复制到了新的空间，最后我们返回的是A的新空间的地址（看到返回的就是forwarding指针，用处在这呢），赋值给了根对象的指针

剩余的就是B了，垃圾，直接清空From空间即可。关于其优缺点，其实就是我们之前说的几个问题：

1.分配速度快，既然它没有空闲链表的概念，直接当成一个栈内存分配即可，速度飞起，相应的就没有碎片化的苦恼了。

2.吞吐量高，其实就是GC速度快，如同我们之前所说，它不像标记清除那样进行第二个阶段去扫描所有的堆。

3.还有一个比较有意思的地方，通过老空间的内容复制到新空间之后，相互有引用的对象会被分配在距离较近的地方，还记得程序的局部性原理吗？这会提升我们的缓存命中率

4.优点那么好，肯定优缺点，第一个就是太浪费内存了，我们只能用一半！！！

5.这里面也有递归的操作，效率可能会降低，或者有可能引起栈溢出的问题。

6.同样的，它也有STW的时间，复制清除的过程需要暂停程序。

5.5 分代收集

分代收集只是一种思想，并非一个专门的垃圾回收算法，不过这个想法真妙，值得学习，在平常的性能优化过程中应该很有用。所谓分代，谜底就在字面上，就是把我们堆分配的对象，给他分代（上一代，下一代的意思），我们这里只说分成新旧两代的算法，那么分代按照什么分呢？按照我们的垃圾的生命周期来分，意思就是很快编程垃圾的那种对象被分为年轻的一代，相应的很长时间才变成垃圾的对象被称为老的一代，我们每次只对年轻一代的对象进行GC即可，每次GC都会给对象增加一个年龄，当到达老一代的对象的年龄的限制的时候，再把它升级为老对象，放到老对象的空间中，当老对象的空间满的时候，我们再去GC老对象即可。

分析下：

这种算法基于这样的认知，大部分对象创建后很快就变成垃圾，其余的就是很长时间才会变成垃圾，那么我们没必要对这种长时间才变成垃圾的对象进行GC，浪费时间。 ok，我们来看下David Ungar研究的分代GC算法：

1.该算法把堆空间划分为四个部分，分别是生成空间，幸存空间1，幸存空间2，老年代空间。并且我们把前三者合并成为新生代空间。

2.当对象刚创建的时候，分配的空间就是在生成空间。

3.当生成空间满的时候，我们就对新生代空间进行GC，这里是是对整个新生代空间进行GC，采用的GC的算法就是节点复制。我们看图说话

看上图，我们把幸存空间其中一个作为一个To空间。

4.另外，我们每次GC的时候，都会对对象的“年龄”加1，当判断对象的年龄到达一定阈值的时候，就把对象移动到老年代空间。

5.当我们对新生代对象进行GC的时候，我们注意一点，之前看节点复制的时候，我们知道是从根节点开始扫描，但是注意一有可能我们的老年代的对象也会指向新生代，所以如果我们把这点漏掉了，会多清除一些活跃的对象（至于为什么我们稍后解释）。为了解决这个问题，我们需要把老年代的对象扫描一遍，但是想想如果这样做的话我们岂不是每次要GC新生代对象的时候，都要把新、老都扫描了？这样的话我们的分代GC就没有优点了，如下图。

6.为了解决第5步的问题，David Ungar想到了一个方法，用一个记录集来记录那些老年代的对象指向新生代的情况。这样的话，当我们的GC新生代的时候，从根对象与记录集中就行，那么这个记录怎么做到呢，采用的写入屏障（write barrier）的方法。

7.那么我们什么时候GC老年代对象的呢？当我们发现新生代的对象的年龄到了之后，要晋升为老年代对象的时候，会先检查老年代空间是否满了，满的话我们就开始老年代GC，老年代对象GC采用的就是标记清除的方法，注意这里应该是把整个堆都进行了GC。

在看具体步骤前，先来看下每个对象标志都有哪些，在对象的头部包含对象的种类、大小还有如下三个标志:

1.对象的年龄（age），之前已经说过，用于新生代晋升老年代使用

2.已经复制完的标志（forwarded），这是我们使用节点复制GC的时候用

3.已经向记录集记录完毕的标志（remembered），这是我们对新生代进行GC的时候找根节点使用

最后我们来看下具体的步骤：

1.新生代的GC过程：先看下伪代码

（1）当我们的生成空间满的时候，触发了新生代的GC，执行minor_gc()函数，minor_gc()的如上

（2）我们来看下首先判断forwarded是否已经复制，如果已经复制过了则不用再复制了，防止重复复制

（3）如果还我复制，接着判断它的年龄，如果超过一定年龄则判定为老年代对象，然后调用promote进行晋升。

（4）如果还是年轻的对象，则更新更新forwarded和forwarding，跟我们之前看的节点复制没什么区别

（5）接着我们来看看promote函数

注意：

我们仔细想一下，有没有可能新生代对象指向老年代对象的情况呢，那么我们在copy函数中，如果某个对象的子对象指向了老对象，岂不是又调用了一次promote函数，所以我认为这里有点问题，需要在promote给new_obj更新下forwarded为true，这样的话如果以后发现某个对象已经是老对象，copy函数中判断

就会被过滤了。

看一下整体的过程

2.老年代的GC 当我们把新年代的对象复制到老年代的时候，老年代可能会满，所以我们需要对老年代进行GC，采用的是普通的标记清除，这里注意一点，如果我们只是清除老年代，同样的，如果有新年代的对象指向老年代的怎么办呢？所以这里的标记清除，是对整个堆进行标记清除GC。

我们最后来分析下它的优缺点：

1.优点是速度快，每次都扫描的少嘛，这就是所谓吞吐量快

2.大部分年轻对象很快就成为垃圾了，这个也不是完全确定的，如果不是这个规律，那就出问题了，新生代GC时间就会多？为什么呢，因为记录集可能会很多。老年代GC也会频繁运行，为什么呢，大部分都不是垃圾了，全都复制到老年代空间了，那么老年代空间就会很快满了。

5.6 三色标记法

在golang1.5之前，golang主要是采用标记清除的方法，这样的话STW时间会很长，1.5出来后采用了三色标记法，也是我们今天主要说的。 golang为何要选择三色标记算法呢？我们知道golang比较适合网络高并发的服务场景，那么如果使用STW时间较长的GC算法，对服务来说是致命的，故而要选用STW时间较少的算法，在标记清除的基础上发展来的三色标记出现了。三色标记的思想其实是尽量把标记阶段、清除阶段与程序同时跑，它其实是一种增量式GC算法，所谓增量式其实就是把GC过程拆分出来的意思，跟我们要把最大的STW时间减少的思想吻合。

在看整个过程之前，我们先同步几件事情：

1.在三色标记算法中，我们给对象进行了标记颜色，分别是白色、灰色、黑色，在GC开始的时候，所有的对象默认都是白色，标记完成之后，所有的可达的对象都会被标记为黑色，而灰色就是我们的中间状态

2.我们Golang的GC的根对象，都在栈上，所谓栈其实就是协程栈。

我们来看下其整个过程：

1.首先，当要GC触发的时候，首先，我们会初始化写屏障（Write barrier），我们的垃圾回收器从根对象开始扫描，把所有的垃圾根对象压入一个栈当中，并且把对象都会标记为灰色

2.从栈中pop出一个对象，把该对象所有指向的子对象都入栈，并且标记为灰色，并且把该对象标记为黑色，然后放入黑色的对象集合中

3.无限的重复第二个步骤，直到栈为空。

4.在第一步骤中我们看到有写屏障，这个写屏障其实就是记录我们进行第一次扫描的时候漏掉的那些对内存的操作，我们会再次遍历这些记录（稍后细说），注意这个过程会进行STW，但是时间会很短。

5.最后扫描所有的堆，把白色对象清除即可。

注意：

1.还记得我们在说golang的堆内存管理与协程栈管理吗？首先栈的管理中有一个stackmap可以帮助我们寻找到到协程栈上的指针，这其实就是我们的根对象

2.Edsger W. Dijkstra提出的三色标记法中，有一个地方需要注意，在标记阶段如果出现以下情况我们是要进行特殊处理的：

a.如果有新创建的对象，而指向该对象的是黑色的对象，或者指向该对象的恰好也是刚创建的根对象，这样这个刚创建的对象会被漏标记

b.如果有如下图的情况，某个白色对象在被灰色对象引用的情况下，被改为被黑色对象引用了，而我们知道黑色的对象其实已经被扫描过了，这样这个白色的对象就不会被标记到。

这个时候我们就要用到写屏障了，看下Edsger W. Dijkstra提出的写屏障算法。

这里看到，只要我们指向的对象是白色的，我们就把它标记为灰色的，这样的话，新创建的对象以及黑色对象指向白色对象的情况就能被解决，如下图所示。

3.我们说过三色标记是增量式的，具体体现在哪呢？看下它的伪代码

注意看上面的代码的MARK_MAX，这里的意思是从灰色的栈集合中，每次最多扫描MARK_MAX个灰色对象。也就是说把扫描阶段拆开了，一次一部分，所以叫增量式。

4.我们再来看下，如果在清除阶段很应用程序同时跑会有问题吗？

(1)想象下，如果引用变化会引起清除掉活跃的对象吗？其实是不会的，想象下什么情况下可能会出现清除活跃对象呢，白色的对象又重新被引用了才可能会出问题，但是其实不会的，如果它原本是白色对象，就不可能被黑色对象找到了，如果它能通过某个方式找到这个白色对象，那么在之前扫描的时候一定会把它最后标记为黑色的。

(2)如果在清除阶段出现新的对象呢？我们知道新创建的对象默认是白色的，确实有可能是被清除的，那么我们怎么做呢，很简单，我们知道清除阶段是扫描整个堆内存，其实我们是可以知道当前清除到什么位置，那么我们创建的新对象判定下，如果新对象的指针位置已经被扫描过了，那么就不用作任何操作，不会被误清除，如果在当前扫描的位置的后面，那就要注意了，我们直接把该对象的颜色标记为黑色，这样就不会被误清除了。如下图所示

5.我们来分析下优缺点:

(1)最大的优点是STW时间很短

(2)缺点就是吞吐量低，原因就是有写入屏障

6.不同的写入屏障策略为了防止在扫描阶段，与程序同时跑的话，出现白色的活跃的对象（被灰色）在还未被标记的时候，从被会被灰色对象指向改为被黑色对象指向，我们上面说过一种写入屏障的策略是记录黑色直线白色的引用，其实还有其他几种方式，我们来说一下。 (1)Steele算法该算法不同的地方就在于，当发现黑色对象指向白色对象的时候，就把黑色对象标记为灰色即可。这样的话，该对象就会被再次扫描，相应的那个白色对象也会被扫描到，如图所示

(2)汤浅算法该算法在mark的时候，不会再次扫描根对象，同样我们需要注意两个问题，新生成的对象，以及引用的变更，对于新生成的对象就直接标记为黑色，对于引用的变更，该算法的写入屏障是记录指针删除的操作，记录的条件是，当有指针删除的操作的时候，并且被删除的指引指向的是白色的对象，那么我们就把这个白色的对象给标记成灰色就行了，如图所示

六、Golang的内存逃逸

6.1 何为内存逃逸

我们在写C++或者C的时候都知道一个事实，你自己申请的堆内存需要自己释放，因为它们存储在堆上，而且一般自己malloc或者new出来的内存，都是在堆上的，那么golang是否也这样呢？

答案不是的，之前我们也说到过一些，就是程序开发人员在程序中申请的变量或者说内存，是存储在堆上还是栈上，是golang的编译器来决定的，那么何谓内存逃逸呢，举一个最简单的例子，看如下的代码

如果这段代码在C++程序中，该函数返回的b的地址，由于b是局部变量，存储在栈上，当函数执行完成后栈上的资源释放那么如果其他地方再用b的地址去访问b的话，就会出现访问空指针，或者访问到错误内容。但是，如上的代码它是golang的，就不会出现这样的问题，为何呢？其实golang编译器在编译这段代码的时候，发现该函数返回了局部变量的地址，它就认为该变量不太适合存储在栈上，于是它命令申请该变量的时候存储到堆上，这样的话函数执行完，也不会释放掉b的内容，我们就可以在其他地方开心的使用b的内容了。明白了如上的原因，我们来再次说明下编译器的作用：编译器来决定变量是存储在堆上还是栈上。比如，你在golang中New一个对象或者make一个对象，对象不一定会存储在堆上。那么我们再解释下内存逃逸的定义：变量突破了自己的作用范围，在作用范围外能被访问的现象就叫内存逃逸，即为通过逃逸把栈上的内存分配到堆上了。

优缺点：

1.这样做的好处是，不用程序开发人员太多的关注局部变量作用范围的问题，尤其是如上的问题。

2.那么它有坏处吗，必然是有的，想象下，如上这种情况，本应该在栈存储的变量最后都跑到堆上了，这势必会使得堆上的内存变多，带来的就是GC的压力，另外，申请堆上的内存与申请栈内存的速度是没发比的，那么我们怎么解决呢？这就是逃逸分析。