Go的垃圾回收
什么是 Garbage Collection
现代编程语言的内存管理分为 自动 和 手动。C、C++语言需要工程师主动申请或者释放内存，而 PHP、Java 和 Go 等语言则使用 自动内存管理系统 和 垃圾收集器，这样可以实现内存分配和回收。垃圾收集器是常见的一种 GC (垃圾回收) 方式，目前主流的垃圾回收算法有 引用计数 和 追踪式垃圾回收，Go 现在采用的就是追踪式垃圾回收算法中的 三色标记法。
Mark-and-Sweep
STW：stop the world, GC 的一些阶段需要停止所有的 mutator 以确定当前的引用关系。这便是很多人对 GC 担心的来源，这也是 GC 算法优化的重点。
Root：根对象是 mutator 不需要通过其他对象就可以直接访问到的对象。比如全局对象，栈对象中的数据等。通过 Root 对象，可以追踪到其他存活的对象。
Mark Sweep 两个阶段：标记(Mark)和 清除(Sweep)两个阶段，所以也叫 Mark-Sweep 垃圾回收算法。
Go v1.1 STW 这个过程可能达到秒级
这个算法就是严格按照追踪式算法的思路来实现的：
- Stop the World
- Mark：通过 Root 和 Root 直接间接访问到的对象， 来寻找所有可达的对象，并进行标记。
- Sweep：对堆对象迭代，已标记的对象置位标记。所有未标记的对象加入 freelist， 可用于再分配。
- Start the Wrold
这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，Mark Sweep 是整体 STW，并且分配速度慢，内存碎片率高。
Go v1.3 标记 STW，并发 Sweep
标记过程需的要 STW，因为对象引用关系如果在标记阶段做了修改，会影响标记结果的正确性。
并发 GC 分为两层含义：
- 每个 mark 或 sweep 本身是多个线程(协程)执行的（concurrent）
- mutator 和 collector 同时运行（background）
concurrent
concurrent 这一层是比较好实现的, GC 时整体进行 STW，那么对象引用关系不会再改变，对 mark 或者 sweep 任务进行分块，就能多个线程(协程) conncurrent 执行任务 mark 或 sweep。
backgroud
而对于 backgroud 这一层, 也就是说 mutator 和 mark，sweep 同时运行，则相对复杂。
- 1.3 以前的版本使用标记-清扫的方式，整个过程都需要 STW。
- 1.3 版本分离了标记和清扫的操作，标记过程 STW，清扫过程并发执行。
backgroup sweep 是比较容易实现的，因为 mark 后，哪些对象是存活，哪些是要被 sweep 是已知的，sweep 的是不再引用的对象。sweep 结束前，这些对象不会再被分配到，所以 sweep 和 mutator 运行共存。无论全局还是栈不可能能访问的到这些对象，可以安全清理。
Tri-color Mark & Sweep
Go v1.5 并行 Mark & Sweep
1.5 版本在标记过程中使用三色标记法。标记和清扫都并发执行的，但标记阶段的前后需要 STW 一定时间来做 GC 的准备工作和栈的 re-scan。
三色标记是对标记清除法的改进，标记清除法在整个执行时要求长时间 STW，Go 从 1.5 版本开始改为三色标记法，初始将所有内存标记为白色，然后将 roots 加入待扫描队列(进入队列即被视为变成灰色)，然后使用并发 goroutine 扫描队列中的指针，如果指针还引用了其他指针，那么被引用的也进入队列，被扫描的对象视为黑色。
- 白色对象：潜在的垃圾，其内存可能会被垃圾收集器回收。
- 黑色对象：活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象，垃圾回收器不会扫描这些对象的子对象。
- 灰色对象 ：活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象。
Tri-color Marking
垃圾收集器从 root 开始然后跟随指针递归整个内存空间。分配于 noscan 的 span 的对象, 不会进行扫描。然而，此过程不是由同一个 goroutine 完成的，每个指针都排队在工作池中 然后，先看到的被标记为工作协程的后台协程从该池中出队，扫描对象，然后将在其中找到的指针排入队列。
染色流程
- 只要新创建的对象，默认都标记为
白色。 - GC 回收开启，从 Root Set(stacks，heap，global variables)遍历所有对象，把遍历到的对象从
白色集合放入到灰色集合中。 - 遍历
灰色集合，将灰色对象引用的对象从白色放入灰色集合，之后将此灰色对象放入黑色集合中 。 - 重复第三步，直到
灰色集合中没有任何对象。 - 直到只有
黑色和白色集合，清除白色集合中的对象。
颜色在内部实现原理：每个 span 中有一个名为 gcmarkBits 的位图属性，该属性跟踪扫描，并将相应的位设置为 1。
对象丢失问题
1.5 版本在标记过程中使用三色标记法。回收过程主要有四个阶段，其中，标记和清扫都并发执行的，但标记阶段的前后需要 STW 一定时间来做 GC 的准备工作和栈的 re-scan。
如果下面两个条件同时满足，就会出现对象丢失情况。
- 一个白色对象被黑色对象引用，是注定无法通过这个黑色对象来保证自身存活的
- 如果所有能到达它的灰色对象与白色对象之间的可达关系全部遭到破坏，那么这个白色对象必然会被视为垃圾清除掉。
屏障机制（Barrier Mechanism）
屏障机制是一种通过一定的同步手段来确保在多线程（或分布式）环境中对数据进行读写操作时，对数据保持一致性的机制。它可以确保几个处于不同步骤中的线程之间可以正确地读取和保存数据。
有了屏障机制，GC 就可以避免 STW，而只对与垃圾回收相关的 goroutine 进行暂停。具体来说，当有新的对象分配或指针写入时，写入屏障会被触发，标记该对象或指针需要被扫描，并将它们添加到待处理的工作队列中。因此，GC 不需要 STW 扫描整个堆，而只需要扫描被标记的对象和待处理的工作队列。
为什么不在栈上使用屏障？
如果对栈上的写做拦截，那么流程代码会非常复杂，并且性能下降会非常大，得不偿失。根据局部性的原理来说，其实我们程序跑起来，大部分的其实都是操作在栈上，函数参数啊、函数调用导致的压栈出栈、局部变量啊，协程栈，这些如果也弄起写屏障，那么可想而知了，根本就不现实，复杂度和性能就是越不过去的坎。
Write Barrier
使用并发的垃圾回收，也就是多个 Mutator 与 Mark 并发执行，想要在并发或者增量的标记算法中保证正确性（对象不丢失），我们需要达成以下两种三色不变性（Tri-color invariant）中的任意一种：
- 强三色不变式：强制性的不允许
黑色对象引用白色对象。 - 弱三色不变式：
黑色对象可以引用白色对象，白色对象存在其他灰色对象的引用（可达它的链路上游存在灰色对象）。
为了防止这种现象的发生，最简单的方式就是 STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是 STW 的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高 GC 效率，减少 STW 时间呢？
Dijkstra 写屏障：新对象变灰
写入屏障（write barrier）使指向共享变量的引用得到更新，在将新的对象引用传递给共享变量之前它必须执行，以确保动作的原子性。
具体操作：在A黑色对象引用B白色对象的时候，B白色对象被标记为灰色。
满足：强三色不变式。（不存在黑色对象引用白色对象的情况，因为白色会强制变成灰色）。
执行过程：
-
初始化 GC 任务，包括开启写屏障(write barrier)和开启辅助 GC(mutator assist)，统计 root 对象的任务数量等，这个过程需要 STW。
-
扫描所有 root 对象，包括全局指针和 goroutine(G) 栈上的指针(扫描对应 G 栈时需停止该 G)，将其加入标记队列(灰色队列)，并循环处理灰色队列的对象，直到灰色队列为空，该过程后台并行执行。
- A 黑色对象（堆上），B 黑色对象（栈上）。
- A 指向新的对象会变成
灰色，B 指向新创建指向的对象颜色不变还是白色。
-
完成标记工作，重新扫描(re-scan)全局指针和栈。因为 Mark 和 mutator 是并行的，所以在 Mark 过程中可能会有新的对象分配和指针赋值，这个时候就需要通过写屏障(write barrier)记录下来，re-scan 再检查一下（栈上有
白色对象），这个过程也是会 STW 的。按照标记结果回收所有的白色对象，该过程后台并行执行。
不足：结束时需要 STW 来重新扫描栈，大约需要 10~100ms
Yuasa 删屏障：老对象变灰色
删除屏障（delete barrier）简单而言，就是把旧的对象引用从共享变量中删除，但也要保证动作的原子性。这样可以确保当一条线程使用旧的对象引用时，它其实不会意外地改变其他线程可以访问的共享变量中的内容。
具体操作：被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足：弱三色不变式。（保护灰色对象到白色对象的路径不会断）。
不足：回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活这一轮，在下一轮 GC 中被清理掉。
总结
插入屏障和删除屏障各有优缺点
- Dijkstra 的插入写屏障在标记开始时无需 STW，可直接开始，并发进行，但结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；
- Yuasa 的删除写屏障则需要在 GC 开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需 STW。
Go v1.8 Hybrid Write Barrier
Golang 中的混合写屏障满足的是变形的弱三色不变式，同样允许黑色对象引用白色对象，白色对象处于灰色保护状态，但是只由堆上的灰色对象保护。
由于结合了 Yuasa 的删除写屏障和 Dijkstra 的插入写屏障的优点，只需要在开始时并发扫描各个 goroutine 的栈，使其变黑并一直保持，这个过程不需要 STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行 re-scan 操作了，减少了 STW 的时间。
为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，我们还需要将创建的所有堆上新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。
具体操作
- GC 开始将栈上的对象全部扫描并标记为
黑色（之后不再进行第二次重复扫描，无需 STW）。 - GC 期间，任何在栈上创建的新对象，均为
黑色。 - 被删除的对象标记为
灰色。 - 被添加的对象标记为
灰色。
满足：变形的弱三色不变式。（结合了插入、删除写屏障两者的优点）。
场景一：对象被一个堆对象删除引用，成为 另一个栈对象的下游。
场景二：对象被一个栈对象删除引用，成为另一个栈对象的下游。
场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游。
场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游。
Sweep
Sweep 让 Go 知道哪些内存可以重新分配使用，然而，Sweep 过程并不会处理释放的对象内存置为 0(zeroing the memory)。而是在分配重新使用的时候，重新 reset bit。
每个 span 内有一个 bitmap allocBits，他表示上一次 GC 之后每一个 object 的分配情况，
- 1：表示已分配，
- 0：表示未使用或释放。
内部还使用了 uint64 allocCache(deBruijn)，加速寻找 freeobject。
GC 将会启动去释放不再被使用的内存。在标记期间，GC 会用一个位图 gcmarkBits 来跟踪在使用中的内存。
正在被使用的内存被标记为黑色，然而当前执行并不能够到达的那些内存会保持为白色。 现在，我们可以使用 gcmarkBits 精确查看可用于分配的内存。Go 使用 gcmarkBits 赋值了 allocBits，这个操作就是内存清理。
然而必须每个 span 都来一次类似的处理，需要耗费大量时间。Go 的目标是在清理内存时不阻碍执行，并为此提供了两种策略。
Go 提供两种方式来清理内存：
- 在后台启动一个 worker 等待清理内存，一个一个 mspan 处理：当开始运行程序时，Go 将设置一个后台运行的 Worker(唯一的任务就是去清理内存)，它将进入睡眠状态并等待内存段扫描。
- 当申请分配内存时候 lazy 触发：当应用程序 goroutine 尝试在堆内存中分配新内存时，会触发该操作。清理导致的延迟和吞吐量降低被分散到每次内存分配时。
当申请分配内存时候 lazy 触发
清理内存段的第二种方式是即时执行。但是，由于这些内存段已经被分发到每一个处理器 P 的本地缓存 mcache 中，因此很难追踪首先清理哪些内存。这就是为什么 Go 首先将所有内存段移动到 mcentral 的原因。然后，它将会让本地缓存 mcache 再次请求它们，去即时清理。
即时扫描确保所有内存段都会得到清理（节省资源），同时不会阻塞程序执行。
由于后台只有一个 worker 在清理内存块，清理过程可能会花费一些时间。但是，我们可能想知道如果另一个 GC 周期在一次清理过程中启动会发生什么。在这种情况下，这个运行 GC 的 Goroutine 就会在开始标记阶段前去协助完成剩余的清理工作。
Stop The World
在垃圾回收机制 (GC) 中，“Stop the World” (STW) 是一个重要阶段。顾名思义， 在 “Stop the World” 阶段， 当前运行的所有程序将被暂停， 扫描内存的 root 节点和添加写屏障 (write barrier) 。
这个阶段的第一步， 是抢占所有正在运行的 goroutine，被抢占之后， 这些 goroutine 会被悬停在一个相对安全的状态。
处理器 P (无论是正在运行代码的处理器还是已在 idle 列表中的处理器)， 都会被被标记成停止状态 (stopped)， 不再运行任何代码。 调度器把每个处理器的 M 从各自对应的处理器 P 分离出来， 放到 idle 列表中去。
对于 Goroutine 本身， 他们会被放到一个全局队列中等待。