Go GC原理

Go内存分配

• Go要使用内存时不是直接去系统取，而是分成了四步依次取，当后者内存不足时就向前一步申请内存

• 每个线程都有自己的初始内存空间mcache，这个内存空间只有当前线程才能访问，当Go需要内存时首先会从该空间中获取 (因为前面三步的空间都是多个线程可以访问，获取时会加锁，大大增加了获取内存的时间)

• 如果mcache中内存不够用再去mcentral(多个线程共享)中取，而且一次取就取一大块，防止多个线程大量反复取内存加锁而延长获取时间

​

内存图介绍

• mcache

  • 小对象的内存分配直接走

  • size class 从 1 到 66，每个 class 两个 span（因为一个span存object，一个span存指针）

  • Span 大小是 8KB，按 span class 大小切分

    每一个span都有一个描述者mspan

    

    • npages：分成多少页
    • allocBits：记录了每块内存分配的情况
    • gcmarkBits：记录了每块内存的引用情况，标记阶段对每块内存进行标记，有对象引用的内存标记为1，没有的标 记为 0
    • 这两个位图的数据结构是完全一致的，标记结束则进行内存回收，回收的时候，将 allocBits 指 向 gcmarkBits，标记过的则存在，未进行标记的则进行回收

• mcentral

  • Span 内的所有内存块都被占用时，没有剩余空间继续分配对象，mcache 会向 mcentral 申请1个 span，mcache 拿到 span 后继续分配对象
  • 当 mcentral 向 mcache 提供 span 时，如果没有符合条件的 span，mcentral 会向 mheap 申请 span

• mheap

  • 当 mheap 没有足够的内存时，mheap 会向 OS (系统) 申请内存
  • Mheap 把 Span 组织成了树结构，而不是链表
  • 然后把 Span 分配到 heapArena 进行管理，它包含地址映射和 span 是否包含指针等位图
    • 为了更高效的分配、回收和再利用内存

GC

Garbage Collection

内存回收的类型

• 引用计数（Python，PHP，Swift）
  • 对每一个对象维护一个引用计数，当引用该对象的对象被销毁的时候，引用计数减 1，当引用计数为 0 的时候，回 收该对象
  • 优点：对象可以很快的被回收，不会出现内存耗尽或达到某个阀值时才回收
  • 缺点：不能很好的处理循环引用，而且实时维护引用计数，有也一定的代价
• 标记-清除（Golang）
  • 从根变量开始遍历所有引用的对象，引用的对象标记为”被引用”，没有被标记的进行回收
  • 优点：解决引用计数的缺点
  • 缺点：需要 STW（stop the word），即要暂停程序运行
• 分代收集（Java）
  • 按照生命周期进行划分不同的代空间，生命周期长的放入老年代，短的放入新生代，新生代的回收频率高于老年代的频率

标记清除法

STW

Stop The World

在垃圾回收机制 (GC) 中，Stop The World是一个重要阶段。顾名思义，当前运行的所有程序将被暂停（以确定当前内存的引用关系：知道哪些被引用，因为如果不暂停引用可能会发生变化），扫描内存的 Root 节点和添加 写屏障

这个阶段的第一步，是抢占所有正在运行的goroutine，被抢占之后，这些goroutine会被悬停在一个相对安全的状态

处理器P(无论是正在运行的处理器还是已在idle列表中的处理器)，都会被标记成停止状态(stopped)，不再运行任何代码。调度器把每个处理的M从各自对应的处理器P分离出来，放到idle(M的休闲列表)列表中去

对于Goroutine本身，它们会被放到一个全局队列中等待

​

Root

根对象是mutator (应用程序) 不需要通过其他对象就可以直接访问到的对象。比如全局对象、局部对象，栈对象中的数据等。通过Root对象。可以追踪到其他存活的对象，进而进行标记

这个算法就是严格按照追踪式算法的思路来实现的

• Stop the Wrold
• Mark：通过Root和Root直接间接访问到的对象，来寻找所有可达的对象，并进行标记
• Sweep：对堆对象迭代，已标记的对象置位标记。所有未标记的对象加入freelist，可用于再分配
• Start the Wrold

这个算法最大的问是GC执行期间需要把整个程序完全暂停，朴素的Mark Sweep是整体STW，并且分配速度慢，内存碎片高

​

在Go1.1是全局阶段STW，可能是秒级，Go1.3是标记过程要STW，因为对象引用关系如个人在标记阶段做了修改，会影响标记结果的正确性

并发GC分为两层含义：

• 每个mark或sweep本身是多个线程(协程)执行的 (concurrent)
• mutator (应用程序) 和 collector 同时运行 (background)

concurrent这一层是比较好实现的，GC时整体进行STW，那么对象引用关系不会再改变，对mark或者sweep任务进行分块，就能多个线程(协程)concurrent执行任务mark或sweep

对于backgroud这一层，也就是说mutator和mark、sweep同时运行，则相对复杂

• 1.3以前的版本使用标记-清除的方式，整个过程都需STW
• 1.3版本分离了标记和清除的操作，标记过程STW，清除过程并发执行

background sweep是比较容易实现的，因为mark后，哪些对象是存活，哪些是要被sweep是已知的，sweep的是不再引用的独享。sweep结束前，这些对象不会再分配到，所以sweep和mutator运行共存。无论全局还是栈不可能能访问的到这些对象，可以安全清理

1.5版本后在标记过程中使用三色标记法。标记和清扫都并发执行的，但标记阶段的前后需要STW一定时间来做GC的准备工作和栈的re-scan

三色标记清除法

Tri-color Mark & Sweep

三色标记清除法是对标记清除法的改进，标记清除法在整个执行时要求长时间 STW，Go从1.5版本开始改为三色标记法：初始将所有内存标记为白色，然后将roots加入待扫描队列(进入队列即被视为变为灰色)，然后并发goroutine扫描队列中的指针，如果指针还引用了其他指针，那么被引用的也进入队列(变为灰色)，被扫描的对象视为黑色(由灰色变为黑色)

• 白色对象：潜在的垃圾，其内存可能会被垃圾回收器回收
• 黑色对象：活跃对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象，垃圾回收器不会扫描这些对象的子对象
• 灰色对象：潜在活跃对象，因为可能存在指向白色对象的外部指针，垃圾回收器会扫描这些对象的子对象

​

工作流程

Golang GC 的大部分处理是和用户代码并行的

• Mark：
  • Mark Prepare: 初始化 GC 任务，包括开启写屏障 (write barrier) 和辅助 GC (mutator assist)，统计root对象的任 务数量等。这个过程需要STW
  • GC Drains: 扫描所有 root 对象，包括全局指针和 goroutine(G) 栈上的指针（扫描对应 G 栈时需停止该 G)，将其 加入标记队列(灰色队列)，并循环处理灰色队列的对象，直到灰色队列为空。该过程后台并行执行
• Mark Termination：完成标记工作，重新扫描(re-scan)全局指针和栈。因为 Mark 和用户程序是并行的，所以在 Mark 过 程中可能会有新的对象分配和指针赋值，这个时候就需要通过写屏障（write barrier）记录下来，re-scan 再检查一下，这 个过程也是会 STW 的
• Sweep：按照标记结果回收所有的白色对象，该过程后台并行执行
• Sweep Termination：对未清扫的 span 进行清扫, 只有上一轮的 GC 的清扫工作完成才可以开始新一轮的 GC

​

三色标记

• GC 开始时，认为所有 object 都是白色，即垃圾
• 从 root 区开始遍历，被触达的 object 置成灰色
• 遍历所有灰色 object，将他们内部的引用变量置成灰色，自身置成黑色
• 循环第 3 步，直到没有灰色object 了，只剩下了黑白两种，白色的都是垃圾，可以被清除
• 对于黑色 object，如果在标记期间发生了写操作，写屏障会在真正赋值前将新对象标记为灰色
• 标记过程中，mallocgc 新分配的 object，会先被标记成黑色再返回 (本次就不清理了，留给下一轮GC)
• 颜色内部实现的原理：每个span中有一个名为gcmarkBits的位图属性，该属性跟踪扫描，并将相应的位设置为1

Write Barrier

1.5版本在标记过程中使用三色标记法。回收过程主要有四个阶段，其中，标记和清扫都并发执行的，但标记阶段的前后都需要STW一定时间来做GC的准备工作和re-scan (重新扫描，查询是否在标记过程中发生了内存引用的改变)

使用并发的垃圾回收，也就是多个Mutator (应用程序) 与Mark并发执行，想要在并发或者增量的标记算法中保证正确性，需要达成以下两种三色不变性(Tri-color invariant)中的任意一种

• 强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象
• 弱三色不变性：黑色对象指向的白色对象必须包含一条灰色对象经由多个白色对象的可达路经(因黑色对象不会被扫描了，而有灰色对象指向白色，则白色对象还有机会被扫描)

如图，如果e被或破坏了(B.e=nil)，则白色对象c必然会被视为垃圾，出现对象丢失的现象。如果这个白色对象下游还引用了其他对象，并且这条路径还是指向下游的唯一路径，那么他们也是必死无疑的

为了防止这种现象的产生，最简单的方法就是STW，直接禁止其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费现象，对所有的用户程序都有很大的影响，则如何在保证对象不丢失的情况下尽可能的提高GC效率，减少STW时间呢？

​

Write Barrier - Dijkstra 插入写屏障

插入屏障拦截将白色指针插入黑色对象的操作，标记其对应对象为灰色状态，这样就不存在黑色对象引用白色对象的情况了。满足强三色不变式，在插入指针f时将C对象标记为灰色

如果对栈上的写作拦截，那么流程代码会非常复杂，并且性能下降会非常大，得不偿失。根据局部性的原理来说，其实我们程序跑起来，大部分的其实都是操作在栈上，函数参数啊、函数调用导致的入栈和出栈、局部变量啊，协程栈，这些如果也弄起了写屏障，那么可想而知了，根本不现实，复杂度和性能就是越不过去的坎

• 初始化GC任务，包括开启写屏障和辅助GC，统计root对象的任务数量，这个过程需要STW(但是非常快)
• 扫描所有对象，包括全局指针和goroutine栈上的指针(扫描对应G栈是需停止该G)，将其加入标记队列(灰色队列)，并循环处理灰色队列的对象，知道灰色队列为空，该过程后台并发执行
• 完成标记过程后，重新扫描(re-scan)全局指针和栈。因为Mark和mutator是并行的。所以在Mark过程中可能会有新的对象分配和指针赋值，这个时候需要通过写屏障记录下来，re-scan再检查下，这个过程也是会STW的
• 按照标记结果回收所有白色对象，该过程后台并发执行

​

Write Barrier - Yuasa 删除写屏障

删除屏障也是拦截写操作的，但是是通过保护灰色对象到白色独享的路径不会断实现的，如果发生路径断裂则将白色对象标记为灰色对象。如上图中，删除指针e时将对象C标记为灰色，这样C下游的所有白色对象，即使会被黑色对象引用，最终也还是会被扫描标记的，满足了弱三色不变式。这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，只能在下一轮GC中被清理掉

​

Write Barrier - 混合写屏障

Go1.8 混合写屏障结合了Yuasa的删除写屏障和Dijkstra的插入写屏障

插入屏障和删除屏障各有优缺点，Djkstra的插入写屏障在标记开始时无需STW，可直接开始，并发执行，但是结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW

Golang的混合写屏障满足的是变形的弱三色不变式，同样允许黑色对象引用白色对象，白色对象处于灰色保护状态，但是只由堆上的灰色对象保护

由于结合了 Yuasa 的删除写屏障和 Dijksra 的插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再近些re-scan操作了，减少了STW的时间

为了移除占上的重扫描过程，除了引入混合屏障之外，在垃圾收集的标记阶段，我们还需要将创建的所有新对象都标记成黑色（留给下一轮GC），防止新分配的栈内存和堆内存中的对象被错误的回收，因为栈内存在标记阶段最终都会变为黑色，所以不需要重新扫描空间

Sweep

Sweep让Go知道哪些内存可以重新分配使用，然而，Sweep过程不会处理释放的对象内存置为0，而是在分配重新使用的时候，重新reset bit (取的时候才reset)

每一个span内有一个bitmap allocBits，它表示上一次GC之后每一个object的分配情况，1表示已分配，0表示未使用或释放

​

GC将会启动去释放不再被使用的内存。在标记期间，GC会用一个位图gcmarkBits来跟踪在使用中的内存(黑色标记为0，白色标记为1)

正在被使用的内存被标记为黑色，然后当前执行并不能够达到的那些内存会被保持为白色

现在，我们可以使用gcmarkBits精确查看可用于分配的内存。Go使用gcmarkBits赋值allocBits(覆盖)，这个操作就是内存清理

然而必须每个span都来一次类似的处理，需要耗费大量时间。Go的目标是在清理内存时不阻碍执行，并依次提供了两种策略

• 在后台启动一个worker等待清理内存，一个一个mspan处理

  当开始运行程序时，Go将设置一个后台运行的worker(唯一的任务就是去清理内存)，它将进入睡眠状态并等待内存阶段扫描

• 当申请分配内存时候lazy触发

  当应用程序goroutine尝试在堆内存中分配新内存时，会触发该操作。清理导致的延迟和吞吐量降低被分散到每次内存分配时

​

清理内存阶段的第二种方式是即时执行，但是，由于这些内存已经被分发到每一个处理器P的本地缓存mcache中，因此很难追踪首先清理哪些内存。这就是为什么Go首先将所有内存段移动到mcentral的原因。然后，它会让本地缓存mcache再次请求它们，去即时清理

即时扫描确保所有内存段都会得到清理(节省资源)，同时不会阻塞程序执行

由于后台只有一个 worker 在清理内存块，清理过程可能会花费一些时间。但是，我们可能想知道如果另一个 GC 周期在一次清理过程中启动会发生什么。在这种情况下，这个运行 GC 的 Goroutine 就会在开始标记阶段前去协助完成剩余的清理工作。

GC触发机制

• 内存分配量达到阀值触发 GC
  • 每次内存分配时都会检查当前内存分配量是否已达到阀值，如果达到阀值则立即启动 GC
    • 阀值 = 上次 GC 内存分配量 * 内存增长率
    • 内存增长率由环境变量 GOGC 控制，默认为 100，即每当内存扩大一倍时启动 GC
• 定期触发 GC
  • 默认情况下，最长 2 分钟触发一次 GC，这个间隔在 src/runtime/proc.go:forcegcperiod 变量中被声明
• 手动触发
  • 程序代码中也可以使用 runtime.GC( ) 来手动触发 GC。这主要用于 GC 性能测试和统计