【Golang】有关垃圾收集器的笔记

前言

  在现在的编程语言中通常会使用手动或者是自动来管理内存，如C，C++等编程语言采用的是手动的方式管理内存，人们需要主动申请空间和释放空间；在Java、Python和Go等语言使用的是自动的内存管理系统，一般都是垃圾收集机制（也有使用引用计数或者其他方式的）。这里主要介绍Golang中的垃圾收集的相关机制。
  在Golang早期，垃圾收集采用的是STW（Stop the world）策略：随着用户程序申请的空间越来越多，系统中的垃圾逐渐增多，当程序占用的内存空间达到一定阈值的时候，整个程序直接全部暂停，此时垃圾收集器会扫描已经分配的空间的对象（比如指针）并回收不再继续使用的内存空间。垃圾收集器工作完毕之后，用户程序才继续执行。这个方法的弊端很明显：暂停时间是不可预测的，如果时间比较长的话，相当于整个程序直接“卡”住了，这点对于响应速度高的程序是非常致命的。
  不过好在Golang在之后的发展中，垃圾收集的机制也变得更加高效，这篇博客就是介绍我了解到的垃圾收集器的相关机制（如果有不对的地方欢迎指正）

标记清除

  标记清除算法可以说是最为常见的垃圾收集算法，其执行过程可以分为“标记”和“清除”两个阶段

1. 标记阶段：垃圾收集器从一系列“根对象”开始，递归遍历通过这些“跟对象”所能访问到的所有对象，并将其标记为“存活状态”
2. 清除阶段：回收期遍历堆中的全部对象，回收那些在标记阶段没有被标记为“存活状态”的对象，并将回收之后的空间加入空闲列表中，以供下次内存分配时使用

哪些属于根对象？
1、全局变量：因为全局变量的生命周期和整个程序的生命周期是一致的，所以必须标记为存活
2、当前执行栈上的变量：每个正在运行的 ​​Goroutine 都有自己的执行栈​​。栈上存储了函数的参数、局部变量（指针）以及临时变量。这些栈上的变量直接活跃地正在被使用，因此它们所引用的对象必须被保护
3、寄存器：寄存器可能存有当前执行上下文的相关数据，所以也需要保留

三色标记法

  三色标记法是为了解决原始的标记清除标记算法带来的长时间的STW而设计的、该算法将程序中的对象抽象为三类

1. 白色对象：尚未被垃圾收集器访问到的对象（白色对象可以是作为“潜在的可以回收的垃圾”，如果在标记阶段介绍之后一个对象仍然是白色的，那就意味着这个对象不会再被任何跟对象或存活对象所引用，将在清除阶段被回收）
2. 灰色对象：已经被垃圾收集器访问到了，但是它的引用（它指向的对象）还没有被完全扫描到
3. 黑色对象：标识对象被标记为存活，并且其所引用的子对象也被扫描完毕了

工作的流程

三色标记垃圾收集器的标记阶段工作步骤如下

1. 将所有的根对象视做灰色对象
2. 从灰色对象集合中取出一个灰色对象并将其标记为黑色
3. 将该黑色对象指向的所有的对象都标记为灰色，保证这个对象和其指向的对象都不会被回收
4. 重复2、3步骤直到没有灰色变量
     当标记阶段结束之后，程序中就只有黑色对象和白色的垃圾对象，此时垃圾收集器就可以回收这些白色对象（这个过程个人感觉类似于BFS）
     由于标记阶段和用户程序是并发执行的（上述过程并不是并发安全的），所以会导致这样一个现象：用户程序在和标记阶段并发执行过程中，用户程序建立了一个从黑色对象到白色对象的引用，但是这个白色对象的颜色并不会改变（回顾一下黑色对象的定义：“标识对象被标记为存活，并且其所引用的子对象也被扫描完毕了”，也就是说标记阶段垃圾收集器不会再去检查黑色对象以及它的引用了），所以这个白色对象还是会被回收，从而导致这个黑色对象指向了一块已经被回收的空间（野指针）

屏障技术

内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作

  如果要在并发的情况下保证标记算法的正确性，需要达成以下两种三色不变性的其中一种

• 强三色不变性：不允许黑色对象直接指向白色对象。这条规则非常严格和直接。一旦一个对象被标记为黑色（已处理完毕），它就绝对不能再与任何白色对象（潜在垃圾）产生任何直接的联系。
• 弱三色不变性：所有被黑色对象引用的白色对象，必须存在一条从灰色对象最终到达它的路径（被灰色对象间接引用）。也就是说黑色对象要指向白色对象，可以，但是这个白色对象必须可以被另外一个灰色对象直接或者间接的指向，这样才能保证这个白色对象可以被垃圾收集器所发现。
    强三色不变性​​和​​弱三色不变性​​是两种​​约束条件​​或​​契约​​。它们规定了在垃圾回收器（GC）并发标记的过程中，用户程序（Mutator）如何修改对象指针才是“安全”的，从而保证不会错误地回收仍在使用中的对象（即存活对象）。它们都建立在​​白、灰、黑​​三色抽象模型之上

插入写屏障

Dijkstra 在 1978 年提出了插入写屏障，通过如下所示的写屏障，用户程序和垃圾收集器可以在交替工作的情况下保证程序执行的正确性

writePointer(slot, ptr):shade(ptr)*slot = ptr

  简单来说，就是当用户程序试图建立一个黑色对象指向白色对象的引用的时候（试图破坏强三色不变性），插入写屏障会拦截这个操作，并强制将白色对象标记为灰色，从而破坏这种“非法”引用，满足“强三色不变性”约束
  这种插入写屏障的做法是一种比较保守的屏障技术，它将“所有可能存活的对象都标记为黑色。当一个黑色对象重新指向一个白色对象的时候，这个黑色对象原先指向的对象可能没有其他对象指向它了（没有存活的必要了），但还是保留了下来。这些错误标记的对象会在下一轮垃圾回收中才会被回收
  Dijkstra提出的插入式写屏障虽然实现了强三色不变性，逻辑清晰且易于实现，但它存在一个显著的性能瓶颈：​​对栈上指针写入的处理​​。
  在垃圾回收中，栈上的变量被视为“根对象”，是标记过程的起点。为了保证绝对的正确性，如果不对栈上的指针写入施加同样的屏障规则，就可能违反“禁止黑色引用白色”的原则（因为栈可能被标记为黑色后继续写入白色对象）。
  这就给语言设计者带来了一个两难的选择：

1. 为栈操作也启用写屏障​​：这会导致​​巨大的性能开销​​。因为栈上的指针写入操作极其频繁，为每一次这样的操作都加入一个额外的屏障函数调用，会严重拖慢程序的整体运行速度。
2. 在标记结束时STW并重新扫描栈​​：这种做法避免了在程序运行时对栈操作的开销，但代价是​​引入了一次短暂的“Stop-The-World”停顿​​。虽然这次停顿比传统的STW GC短得多，但仍然违背了追求极致低延迟的初衷。

删除写屏障

Yuasa 在 1990 年的论文 Real-time garbage collection on general-purpose machines 中提出了删除写屏障，因为一旦该写屏障开始工作，它会保证开启写屏障时堆上所有对象的可达，所以也被称作快照垃圾收集（Snapshot GC）

  删除写屏障旨在维护弱三色不变性，防止因指针删除而导致对象丢失。其核心机制是：​​当一个指针被重新赋值（其指向发生改变）时，写屏障会捕获这个指针原先指向的旧对象。如果该旧对象是白色的，则立即将其标记为灰色​​，从而确保它不会被本轮垃圾回收错误地清除。
  删除写屏障是主要用在一下场景：

Yuasa 删除写屏障通过对 C 对象的着色，保证了 C 对象和下游的 D 对象能够在这一次垃圾收集的循环中存活，避免发生悬挂指针以保证用户程序的正确性

增量和并发

  增量和并发垃圾收集机制都允许垃圾收集器与用户程序交替或同时运行，但这引入了对象引用关系在收集中途被修改的风险。因此，必须引入​​屏障技术​​（如写屏障）来监控内存写入操作，保障标记过程的正确性。
  此外，触发垃圾收集的时机也至关重要。应用程序​​不能​​等到内存完全耗尽、分配失败时才启动收集。若在内存不足时触发，系统已无法满足新的内存分配请求，此时的垃圾收集实质上仍会导致程序暂停，与传统的“停止世界”（STW）无异。真正高效的增量和并发收集器必须​​提前触发​​，在内存尚有余量时完成收集循环，从而避免因内存压力造成的长时间暂停，确保应用的流畅运行

增量收集器

  增量收集器的核心思想非常直观：​​将原本需要一次性、长时间完成的垃圾回收过程，分解成一系列小的、离散的任务单元。​​这些小的任务单元与用户程序的执行​​交替运行​​。每次只执行一小段时间的垃圾回收工作，然后就立即将 CPU 控制权交还给用户程序，让应用程序运行一小段时间，如此反复循环，直到整个垃圾回收周期完成。虽然说一轮垃圾回收的周期变长了，但是应用程序暂停的时间也大大减少了
  另外，增量收集器需要和三色标记法一起使用。为确保垃圾收集的正确性，需要在垃圾收集之前就打开开写屏障，这样用户程序修改内存都会先经过写屏障的处理（写屏障也会让用户程序的承担额外的计算开销，但总体来讲是利大于弊的），保证了堆内存中对象关系的强三色不变性或者弱三色不变性。

并发收集器

  并发收集器与增量收集器最大的不同就在于：增量收集器需要和用户程序抢占CPU资源，并发收集器会利用多核优势与用户程序并行执行，从而减轻对于用户程序的影响，垃圾收集阶段的耗时也减少了
  虽然并发收集器能够与用户程序一起运行，但是并不是所有阶段都可以与用户程序一起运行，部分阶段还是需要暂停用户程序的，不过与传统的算法相比，并发的垃圾收集可以将能够并发执行的工作尽量并发执行；当然，因为读写屏障的引入，并发的垃圾收集器也一定会带来额外开销，不仅会增加垃圾收集的总时间，还会影响用户程序，这是我们在设计垃圾收集策略时必须要注意的。

什么时候需要暂停用户程序？

1. 重新扫描栈空间（Stack Rescanning​​：
     在并发标记期间，成千上万个Goroutine的栈是持续变化的。尽管写屏障能处理堆上的指针写入，但为了极致性能，通常不会对每个栈上的指针写入都启用写屏障。因此，收集器需要短暂暂停所有Goroutine，​​最后一次快速扫描所有Goroutine的栈​​，以确保在并发标记期间栈上新产生的指针和它们引用的对象不会被遗漏。
2. 处理写屏障缓冲区（Draining Write Barrier Buffers​​：
     在并发标记期间，写屏障并不会立即处理每一个指针写入，而是常常将这些操作记录到每个P（处理器）的​​写屏障缓冲区​​中，以批处理方式提升效率。所以在标记终止时，收集器必须清空（Drain）所有这些缓冲区，并重新处理其中的指针写入记录，确保这些最后被记录下的引用也被正确标记。
3. 状态切换与清理准备​​：
     收集器需要原子性地将整个系统的状态从“正在标记”切换到“标记完成”，并为下一个阶段（通常是并发清理）做准备。关闭写屏障（因为标记已经结束），计算清理阶段需要的统计信息，并正式启动内存回收流程。

混合写屏障

  在Go语言的垃圾收集机制中，写屏障（Write Barrier）确实只针对堆内存上的指针写入操作，这是出于性能考虑。因为栈上的操作非常频繁，如果在此处启用写屏障，会带来巨大的开销。所以后面引入了混合写屏障。
首先要知道为什么在Go v1.7之前需要栈的重扫描？
  在Go v1.7及之前，运行时使用Dijkstra插入写屏障（Insertion Write Barrier）来保证强三色不变性。这种写屏障只在堆指针写入时触发：当将一个指针写入堆内存时，会将新指针指向的对象标记为灰色。
  然而，运行时并没有在所有的垃圾收集根对象（如Goroutine栈）上开启写屏障。因为应用程序可能有很多Goroutine（成百上千），在每个栈上开启写屏障会导致巨额开销（栈操作太频繁）。
  这就带来了一个问题：在并发标记阶段，一个Goroutine的栈可能从堆上读取一个指针，指向一个白色对象（即未被标记的对象）。随后，堆上的指针可能被删除或覆盖，而栈上的这个引用对垃圾收集器是“隐藏”的（因为栈没有写屏障）。如果垃圾收集器不知道栈上的这个引用，它可能会错误地将白色对象回收。
  为了解决这个问题，Go在标记阶段结束时需要暂停程序（STW），将所有栈对象标记为灰色并重新扫描。这个重新扫描过程在Goroutine多的程序中可能需要10~100ms，导致明显的延迟。
为什么说混合写屏障能够避免栈的重扫描？
  首先需要明确一个点：混合写屏障包含了插入写屏障和删除写屏障，且对于标记阶段中所有新分配的对象（无论是在堆上还是栈上）都立即被标记为黑色，防止被错误回收。对于混合写屏障，有以下场景

1. 假设堆上有一个黑色对象A指向一个白色对象C。
2. 一个Goroutine的栈从对象A读取指针，使得栈上的局部变量localVar也指向白色对象C。由于栈上没有写屏障，这个操作不会被垃圾收集器察觉。
3. 随后，堆上的对象A覆盖或删除了对C的引用（例如A.ptr = nil）。这是一个堆指针写入操作，因此​​混合写屏障会被触发​​：在写入前，写屏障会将旧指针指向的对象（即C）标记为灰色。
4. 现在，对象C被标记为灰色，即使栈上的localVar是它的唯一引用，垃圾收集器也会在后续标记中从灰色对象C开始遍历，确保C被正确保留
     通过这种方式，混合写屏障确保了任何曾经被堆引用过的对象（即使现在只有栈引用）都不会被错误回收。因为当堆引用被删除时，对象会被标记为灰色。因此，垃圾收集器不再需要担心栈上隐藏的引用——这些引用所指向的对象已经被混合写屏障保护