Golang 内存管理

本文主题是Golang的内存管理，主要包括了内存分配和内存回收，这文章本身也是我自己的学习记录。当然为了各位看官能更好的理解，我会尽量写的由浅入深。本文的目标是介绍Golang内存管理的基本原理及一些实践经验，所以一些过于复杂和细节的知识点文中不会深究，我会贴上原文链接，方便大家扩展阅读。

本文在写作的过程中参考了大量网上、公司Tech平台上的前人智慧，在此表示感谢，大家有兴趣可以看看参考文档。由于本人才疏学浅，有错漏之处欢迎指正。

首先，我们都知道，我们的程序是跑在操作系统上的，不管你是Go程序还是C++程序，都只是操作系统下的一个进程罢了。操作系统会负责给我们的程序分配内存资源。而操作系统会从逻辑层面将进程数据分为5个段。

代码段（text segment）: 通常指存放程序执行代码的区域，这部分区域大小在程序运行前就已经确定，并且通常属于只读。代码段中也可能包含一些只读常数变量，例如字符串常量等。

bss段（bss segment）: 存放未初始化的全局变量和静态变量，可读写。

数据段（data segment）:存储初始化的全局变量和初始化的静态变量，可读写。

堆（heap）：用于存放进程运行中动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）。

**栈（stack）：**存放的是函数中的局部变量及调用数据。操作方式与数据结构中的栈类似。当函数执行完成后，该函数的栈帧由操作系统自动从栈区移除。通常栈的大小是固定的，当我们局部变量申请过大，或函数调用太深，就有可能导致栈溢出（StackOverflow）

由于栈内存是由操作系统自动管理，在函数执行完成后释放，因此大多数情况下我们并不需要关心栈的内存占用及回收。而堆内存由系统和程序员按需分配，动态分配，生命周期与进程一致。这就需要聪明的程序员们考虑很多问题：

当我的应用程序需要一块内存时，我怎么从堆中分配这一块内存？该分配多少内存？

堆空间并非无限大，当我的应用程序累计申请的内存超过了堆空间怎么办？我是否应该把不再使用的堆内存释放掉？

我该怎么分辨出来哪些内存是有用的，哪些内存可以被回收？

.....

堆内存管理是个很复杂的问题，而随着技术发展，各个编程语言都给出了自己的答卷，降低了应用开发的门槛，促进了信息科技的发展。

从参与内存管理过程的角色来看，我们可以拆成三个不同部分，用户程序（Mutator）、分配器（Allocator）及回收器（Collector）。当用户程序申请内存时，它会通过内存分配器申请新内存，而分配器会负责从堆中初始化相应的内存区域。而回收器会负责回收内存。

但其实，并非所有的编程语言都将这三种不同角色区分处理。以C语言为例，C语言的用户程序开发者需要自己手动释放申请的堆内存，因此用户程序同时也承担了回收器的角色。开发者们需要小心的释放数据内存，如果内存使用完后没有释放，就会有内存泄露问题。而高级编程语言如java，go等，都将分配器与回收器在语言层面进行了实现，应用程序开发者无需手动管理堆内存，回收器会适时回收不再使用的内存。

编程语言的内存分配器一般包含两种分配器，一种是线性分配器（Sequential Allocator），一种是空闲链表分配器（Free-List Allocator）。

线性分配是指申请顺序从前至后分配堆内存。我们只需要维护一个指向内存当前分配位置的指针，如果用户程序向分配器申请内存，分配器只需要检查剩余空间内存，返回分配的内存区域后，修改指针为分配后的位置。如图所示，当分配了Object C后，指针也对应移动。

大家可以看到，线性分配的逻辑非常简单，但是也带来了很多问题：

当已分配的内存被回收后，无法重用这部分内存。例如图中Object A被释放后，指针无法找到Object A 所在的位置。

所有线程都在向堆申请内存，需要加锁避免冲突，性能是个大问题。

需要频繁整理内存。因为线性分配是线性扩张，内存很容易就被分配到末端，这时就需要整理内存空间。我们需要通过标记-整理（Mark-Compact）、复制（Coping）或分代回收（Generational Collection）等回收算法，将存活对象整理至一端。

因为标记-压缩、复制等回收算法会直接修改对象的内存地址，因此对于C、C++这种可以直接操作指针的语言不太适用。毕竟谁也不想回收一次后，自己对象的地址就全变了吧，哈哈。

相比线性分配器的高局限性，现在使用更为广泛的是空闲链表分配器。空闲链表的思想也很朴素，前面我们讲到，线性分配只有一个指针，没办法维护空闲的内存。那么好办，一个指针解决不了，那就X个（狗头）。空闲链表分配会在内部维护一个空闲内存块的链表。当用户申请内存的时候，只需要从链表中找到合适的内存块即可。

当然，我们可以有多种策略来从链表中找到合适的内存块。

首次适应：从链表头开始遍历，选择第一个大小大于申请内存的内存块；

循环首次适应：从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块；

最优适应：从链表头遍历整个链表，选择最合适的内存块；

空闲链表分配器成功解决了线性分配器的问题。我们可以重用空闲内存，也无需频繁压缩空间。那么是不是这样就够了呢？

追求极致的程序员们肯定不会满足于此。上面的三种查询策略都需要遍历链表，时间复杂度为O(n)。根据通用的“分而治之”思想，我们可以更进一步，这就是隔离适应策略。

隔离适应策略是将内存分割为多个链表，称之为分箱(bins)，每个分箱的内存块大小相同，申请内存时先找到满足条件的分箱，再从分箱中找到空闲内存块。

目前大多数的编程语言都采用了空闲链表分配器+隔离适应策略来管理内存分配。我这里列举一些常用分配器的实现：

dlmalloc：第一个被广泛使用的通用动态内存分配器，最早由Doug Lea在1980s年代编写，出现后即得到了广泛应用，同时也启发了后代很多优秀分配器如google的tcmaclloc，freeBSD的jemalloc。dlmalloc将小于256字节的内存分为32个分箱，将256字节以上的用树级分箱来管理。有兴趣的同学可以看下 dlmalloc。

ptmalloc/ptmallocX：起源于dlmalloc，由Wolfram Gloger改进得可以支持多线程。是glibc 内置分配器的原型（也就是Linux系统默认分配器）。ptmalloc一共维护了128个分箱，分为四种方式来进行管理。可参考 ptmalloc

tcmalloc：出自google，使用于WebKit/Chrome之中，同时也是Golang分配器的原型。

jemalloc：出自facebook推出的，使用于firefox/android 5.0/FreeBSD等。jemalloc使用了三种分类来管理他的分箱。参考 jemalloc

pymalloc：python语言分配器，大于256k对象调用C标准库分配器分配，小于256k对象再自行通过分箱等进行分配。参考 pymalloc

Golang分配器基于tcmalloc，我们后面会详细介绍golang分配器的设计。

内存回收，也有另一个名字叫垃圾收集（Garbage Collection，GC）。前面我们提到了，内存分配是在堆上进行，堆内存又并非是无穷尽的，那么就需要合理的使用堆内存。主要涉及到几个点：

合理的申请内存，尽量少浪费。

及时清理掉不再使用的内存。

当然第一点是由用户程序控制的，语言层面没办法干预。语言层面可以在第二点上多做些工作，使得无效内存识别更准确，清理更及时，对应用程序影响最小。

不同编程语言对内存回收的处理也不太一样。目前分为两种流派，一种以C/C++/Rust为代表，主张把内存回收的方式交给用户程序，由用户自行决定哪些内存需要回收。另一种则是以Lisp/Java/Go为代表，从语言层面实现了垃圾收集器，通过精心设计的算法自动收集及回收垃圾，将用户程序从繁重的垃圾管理工作中解脱出来。

可能有些同学会说，看起来垃圾收集是个很有必要的功能啊，为什么C/C++这类语言不提供支持呢？这里引用C++设计者Bjarne Stroustrup的一段话

“我有意这样设计C++，使它不依赖于自动垃圾回收(通常就直接说垃圾回收)。这是基于自己对垃圾回收系统的经验，我很害怕那种严重的空间和时间开销，也害怕由于实现和移植垃圾回收系统而带来的复杂性。”

“并不是每个程序都需要永远无休止的运行下去；并不是所有的代码都是基础性的库代码；对于许多应用而言，出现一点存储流失是可以接受的；许多应用可以管理自己的存储，而不需要垃圾回收或者其他与之相关的技术，如引用计数等。”

我们后面主要讨论第二种类型，即垃圾收集器的原理。

垃圾收集器首先需要判断出来，哪些数据还存活着，而哪些数据是不再被需要的，也就是垃圾。这里又存在两种方式。

简单来说就是：

所有对象都存在一个记录引用计数的计数器。

所有对象在创建的时候或被其他对象引用的时候，引用计数为1。

当别的对象进行引用变更时，原先被引用的对象引用计数-1。

当引用计数为0的时候，回收对象所占用的内存空间

当然，引用计数很容易遇到循环引用的问题。例如A引用B，B引用A，除此之外没有任何别的对象指向他们俩，而他俩却因为计数不为0一直无法被回收。

循环引用的解法：

利用垃圾收集算法，如python中利用标记-清除算法解决循环引用问题。

在程序设计语言层面提供一些办法，由程序员来解决。如C++智能指针中的weak_ptr（引用时不+1）

借助Tracing GC，找到没有被环以外的对象引用的环，把它们回收掉

Tracing** **GC：将程序的内存占用分为GC root和GC head两部分。以roots集合作为起始点进行图的遍历(顺着指针递归去找)，如果从roots到某个对象是可达的，则该对象称为“可达对象”。否则就是不可达对象，其内存空间可以被回收。

目前java，go等主流编程语言都全部或部分使用了Tracing GC的方式。

基于Tracing GC的垃圾识别方法，常见的垃圾收集算法有标记-清除算法（Mark-Sweep），复制算法（Coping），标记-整理算法（Mark-Compact），分代清理（Generational Collection）。

标记-清除算法

首先标记出所有需要回收的对象，在标记完成后统一回收掉所有被标记的对象。它是最基础的收集算法，后续的收集算法都是基于这种思路并对其缺点进行改进而得到的。

缺点：会产生内存碎片问题，可能导致大内存对象无法分配。

复制算法

将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。

复制算法解决了标记-清除的内存碎片问题，缺点是可用内存变为一半，经常搬运长生命周期的对象导致效率下降。

标记-整理算法

标记过程仍然与"标记-清除"算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。这样就解决了复制算法中可用内存只有一半的问题。

分代算法

GC分代的基本假设：绝大部分对象的生命周期都非常短暂，存活时间短。

分代算法将堆内存分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用"标记-清理"或"标记-整理"算法来进行回收。

Golang采用的是标记-清除算法，内存碎片的问题主要是通过分配器分配方式来解决。

Tcmalloc算法，全称Thread-Caching Malloc，是google推出的内存分配器，用来替代传统的malloc内存分配函数。它有减少内存碎片，适用于多核，更好的并行性支持等特性。

Golang的分配器就借鉴了 TCMalloc 的设计实现高速的内存分配，它的核心理念是使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略。

我们这里先介绍下Golang内存分配的基本单位。

Page：与操作系统管理内存的方式类似，Golang将虚拟内存空间以page作为单位进行划分，每个page默认8k。

Span：连续的N个Page称为一个Span。

Object：应用程序以Object作为整体在Page上分配内存。大对象甚至会横跨多个Page。

Golang以Span为单位向系统申请内存，申请到的Span可能只有一个Page，也可能有N个Page。Span中的Page可以被划分为一系列小对象，也可以整体当做中对象或者大对象分配。

因此三者的关系，可以用下面的图来描述。

对于不同大小的Object，Golang也按大小进行了分级，根据分级来制定不同的分配策略。因为程序中绝大多数都是小对象，分级处理有利于提升效率。

微对象：小于16B。

小对象：大于16B，小于32KB。

大对象：大于32KB。

针对小对象，Golang还更细致的将对象大小分成了68级，称为Size Class。每个待分配的对象都会向上取整到一个更大的Size Class。例如我们要分配一个9B的对象，他就会被取整为16B，浪费率为43.75%。

更详细的分类见 sizeclasses.go，我这里省略了0的情况。一个Page大小为8192。

Size Class在Golang中的体现是SpanClass，定义在mheap.go/spanClass。spanClass是一个int8，前面7位存储size class的级数信息，最后一位存储noscan，用于记录有无指针，1为无指针，0为有指针，有指针的时候需要参与到内存回收扫描过程。