GC机制
Golang三色标记+GC混合写屏障机制
理解Golang中的GC垃圾回收机制
1、Go V1.3之前的标记清除（Mark and Sweep）
1. 标记-清除（Mark and Sweep）算法概述
标记-清除（Mark and Sweep）算法是垃圾回收中最基本的一种算法，它的核心思想是：
- 标记阶段：从根对象（通常是全局变量、栈上的局部变量、寄存器等）开始，递归遍历所有可达对象，将这些对象标记为活跃对象。
- 清除阶段：扫描堆中的所有对象，删除没有被标记为活跃对象的那些对象，回收它们所占用的内存。
标记-清除算法的基本步骤：
- 标记：从根对象开始，递归遍历所有活跃对象，并将这些对象标记为“存活”。
- 清除：遍历堆中的所有对象，删除没有被标记为“存活”的对象，将其内存回收。
2. Go 1.3 之前的 GC（基于标记-清除）工作流程
在 Go 1.3 之前，Go 使用了单线程的标记-清除垃圾回收算法。以下是详细的执行步骤：
2.1 GC 启动
- 当 Go 程序的堆内存增长到一定的阈值时，GC 会被触发。
- 触发的条件通常是堆内存的使用量（通过内存分配的次数、分配的内存大小等）超过了某个阈值，或者是系统空闲时。
2.2 标记阶段（Marking Phase）
- 标记阶段是垃圾回收的核心阶段，GC 会从根对象开始，递归地访问所有活跃的对象（即程序中仍然在使用的对象）。
- 在这个过程中，GC 会通过指针追踪所有可达的对象，并将它们标记为“活跃”的。这些对象包括栈上的局部变量、全局变量、以及通过指针引用的堆上的对象。
- 标记的方式通常是设置一个位图，标记每个对象的状态。如果对象被标记为存活，则它会被保留；如果没有被标记，则会在后续的清除阶段被回收。
2.3 清除阶段（Sweeping Phase）
- 在标记阶段完成后，所有不再活跃的对象就成为了垃圾对象，这些对象的内存会在清除阶段被回收。
- 清除阶段会遍历堆中所有对象，检查它们的标记。如果某个对象没有被标记为活跃，那么它就会被销毁，回收其占用的内存空间。
- 清除阶段是一个线性的过程，因为它需要扫描整个堆，清理掉未标记的对象。
2.4 暂停与恢复
- 标记-清除算法是一个“停止世界”的（stop-the-world）垃圾回收算法，即 GC 执行过程中，程序的所有 goroutine 都会被暂停（stop-the-world）。
- 在 Go 1.3 之前的标记-清除算法中，GC 的标记和清除阶段都是单线程执行的，可能导致较长的暂停时间。特别是当程序中的堆内存很大时，GC 可能会长时间阻塞应用程序的正常执行，影响响应性能。
2.5 单线程的标记-清除
- 在 Go 1.3 之前，标记和清除过程都是由一个单独的线程（即 GC 线程）完成的，意味着 GC 完全占用 CPU 资源进行内存回收。这也使得 GC 的效率较低，并且可能导致长时间的暂停。
- 由于垃圾回收是单线程的，堆内存的回收可能较慢，特别是在需要扫描大量对象时。GC 的单线程执行模式也可能在高并发的应用场景下，造成较长时间的“暂停世界”问题。
3. 标记-清除算法的优缺点
优点：
- 简单实现：标记-清除算法是最基础的垃圾回收算法，易于理解和实现。
- 不需要压缩内存：标记-清除算法不需要重新整理内存空间，因此实现起来相对简单。
缺点：
- 停顿时间长：由于 GC 是“停止世界”的，即在 GC 执行期间，程序中的所有 Goroutines 都会暂停，这会导致较长的暂停时间，影响程序的响应性。
- 内存碎片：标记-清除会导致内存中产生碎片，即虽然不再使用的对象被清除，但仍然会存在一些未使用的内存空间，这可能导致内存的浪费。
- 清理过程的效率低：标记和清除阶段都是单线程的，清理效率较低，特别是在堆内存较大时，GC 扫描整个堆的过程会比较慢。
4. 标记-清除算法在 Go 1.3 之前的表现
Go 1.3 之前，标记-清除算法的表现相对较差。因为 Go 采用了单线程的方式进行 GC 操作，在高并发和大内存使用的情况下，GC 会造成较大的停顿时间，影响程序的整体性能。为了解决这个问题，Go 语言在 Go 1.3 及之后版本对垃圾回收算法进行了改进，引入了 并发标记-清除算法 和 三色标记法，并优化了多线程并发处理，使得 GC 的效率大大提高，同时减少了停顿时间。
2、Go V1.5三色标记法
1. 三色标记法的基本概念
三色标记法的核心思想是将所有对象分为 三种颜色，通过这些颜色的标记来控制对象的状态并在垃圾回收过程中进行有效的跟踪。每个对象的颜色代表其在垃圾回收过程中的不同状态，具体包括以下三种颜色：
- 白色（White）：表示一个对象是 垃圾对象，还没有被标记为活跃对象（即不可达的对象）。这些对象是垃圾回收器的目标，会在 清除阶段 被回收。
- 灰色（Gray）：表示一个对象是 可达对象，但其引用的对象尚未被完全标记。灰色对象需要继续检查并标记它们引用的其他对象。
- 黑色（Black）：表示一个对象已经被完全标记，且所有它引用的对象都已经被标记。黑色对象是活跃的，不会被回收。
通过这种颜色标记法，GC 可以在不同的阶段追踪对象的状态，并确保不遗漏任何活跃对象。
2. 三色标记法的工作流程
三色标记法将垃圾回收过程分成 标记阶段 和 清除阶段，并在并发的情况下逐步推进。在 Go 1.5 之前，GC 是单线程的，并且没有并发标记的支持，这导致垃圾回收时会出现较长的停顿。Go 1.5 通过三色标记法引入了并发标记的机制，大大减少了 GC 的停顿时间。
三色标记法的具体工作流程如下：
2.1 初始阶段：将所有对象标记为白色
在垃圾回收开始时，所有的对象都被视为 白色，表示它们是垃圾对象。
- 此时，堆中的所有对象都是不可达的，垃圾回收器还没有扫描它们。
- 这个阶段是非常快速的，主要是将堆中所有对象的初始状态设置为白色。
2.2 标记阶段：从根对象开始，进行并发标记
在这个阶段，垃圾回收器会通过并发标记，逐步将对象标记为灰色和黑色。该阶段的目标是标记所有活跃对象，并且逐步探索它们引用的其他对象。
- 根对象：GC 首先从程序中的根对象开始，这些根对象可以是栈上的局部变量、全局变量等。它们是程序中直接可达的对象。
- 灰色标记：从根对象开始，垃圾回收器将根对象及其直接引用的对象标记为 灰色，表示这些对象是可达的，但是它们引用的其他对象还没有被完全检查。
- 灰色队列：所有标记为灰色的对象都会被放入一个 灰色队列。GC 会遍历这个队列，并检查每个灰色对象所引用的对象，将它们标记为灰色。如果某个对象已经被标记为灰色，就会继续将它所引用的对象标记为灰色。
- 黑色标记：当一个灰色对象的所有引用对象都被标记为灰色时，该对象就会被标记为 黑色，表示它已经被完全扫描并且它引用的对象也都被标记过了。此时，该对象不再被检查。
- 并发标记：在 Go 1.5 中，标记过程是 并发的，即多个 goroutine 可以同时参与标记过程。这意味着在标记过程中，程序的其他 goroutine 仍然可以运行，从而避免了 GC 停顿时间的增大。
2.3 清除阶段：回收白色对象
当标记阶段完成后，垃圾回收器会进行 清除阶段。这个阶段的目标是清理掉所有没有被标记为灰色或黑色的对象，也就是那些不再被引用的对象（即白色对象）。
- 白色对象表示这些对象是垃圾，不能被任何活跃对象引用。
- 回收：所有白色对象会被回收并释放内存。
2.4 增量标记：增量进行标记
Go 1.5 的三色标记法引入了 增量标记，即在标记过程中，可以暂停标记，并允许程序继续运行。标记过程会在多个小的增量阶段中完成，从而减少每个阶段的停顿时间。
- 在标记阶段，GC 会进行 增量标记，将标记过程分成多个小的部分，而不是一次性地完成标记。这样，GC 就不会一次性地占用所有 CPU 资源，可以将程序的执行和标记过程交替进行，从而减少停顿。
3. 三色标记法的优势
- 并发标记：Go 1.5 通过引入并发标记，显著降低了 GC 造成的停顿时间。通过并发标记，GC 可以在标记期间不停止其他 goroutine，从而避免了长时间的暂停。
- 增量标记：通过增量标记，GC 可以将标记过程分为多个小块，使得每次标记过程的停顿时间变短，从而减少了垃圾回收的延迟。
- 无全停顿：相比于 Go 1.3 之前的 GC，三色标记法的引入使得 GC 过程中的 全停顿（STW）时间得到了显著缩短，进而提升了程序的响应性。
4. 如果三色标记法不被STW保护
条件一：一个白色对象被黑色对象引用（白色挂在黑色下）
问题描述：
在垃圾回收的标记过程中，黑色对象表示已经被完全标记的对象，并且它引用的所有对象也都已被标记。然而，如果在并发标记过程中，一个 白色对象 被一个 黑色对象 引用，那么这个白色对象会被错误地认为是可达的。
具体来说，如果 GC 正在标记对象时，黑色对象的引用指向了一个白色对象，但此时标记过程没有同步，导致 GC 误认为这个白色对象是可达的，因此无法正确将其回收。
解决方法：
为了避免这个问题，Go 的 GC 在进行标记过程中会使用 STW（Stop-the-World） 机制保护标记的准确性。当垃圾回收器进行关键的标记操作时，会暂停所有的 goroutine 执行，确保在标记过程中没有新的引用被创建。只有在 STW 阶段，所有的黑色对象才能保证是完全标记过的，这样就能确保白色对象不会被错误地引用。
- STW 保护：STW 阶段确保在并发标记过程中，所有的对象引用不会发生变化，避免了标记过程中因并发修改导致的不一致。
- 引用关系的稳定性：通过 STW，我们可以确保黑色对象的引用始终指向正确的白色对象，不会在标记过程中造成混乱。
条件二：灰色对象与它之间的可达关系的白色对象遭到破坏（灰色同事丢了该白色）
问题描述：
在三色标记法中，灰色对象表示 可达对象，但这些对象引用的其他对象（即子对象）还没有被完全标记。灰色对象会被放入灰色队列，等待进一步标记。然而，如果在并发标记过程中，灰色对象引用的某个白色对象的引用关系被破坏（即该白色对象被丢弃或修改），那么会导致灰色对象丢失对该白色对象的引用，从而使垃圾回收器无法正确处理这些对象。
这种问题通常出现在并发标记期间，其中一些 goroutine 对对象的引用关系进行了修改。由于标记过程没有适当的同步机制，就可能导致灰色对象无法正确地完成标记，从而引发错误的标记结果。
解决方法：
为了避免这种问题，Go GC 使用了 灰色对象队列 和 STW 保护 来保证在标记过程中灰色对象的引用关系不会被破坏。
- 灰色对象队列：在三色标记法中，所有的灰色对象都会放入一个专门的队列中，等待标记。这个队列中的对象会被逐个遍历，并且只有当它们完全标记之后才会被移出队列。因此，即使在并发执行期间，灰色对象的引用关系不会被破坏。
- STW 保护：与条件一类似，STW 阶段确保在并发标记期间，没有 goroutine 会修改灰色对象引用的其他对象。通过暂停所有的 goroutine 来保证灰色对象的引用在标记期间不会丢失，避免了灰色对象对白色对象引用关系的破坏。
5. 强弱三色不变式
强弱三色不变式是为了保证垃圾回收过程的正确性和一致性，防止并发标记过程中出现错误。这个不变式用于描述在垃圾回收过程中，三种颜色的对象之间应该遵循的约束。
1. 强三色不变式（Strong Tri-color Invariant）
《破坏条件一》
强三色不变式要求在标记过程中，黑色对象必须是灰色对象的子集。也就是说，在垃圾回收的标记过程中，黑色对象的引用关系应该是稳定的，黑色对象的所有引用必须指向已经完全标记的对象（黑色对象）。如果黑色对象引用的对象是白色的，垃圾回收器就认为它引用了一个可达的对象，因此该对象应该被标记为黑色。
具体来说，强三色不变式保证了：
- 黑色对象引用的所有对象都必须是黑色。如果有任何黑色对象引用了一个灰色或白色对象，说明标记过程出了问题。这样就能保证垃圾回收的结果是准确的，避免了错误的对象被标记为可回收。
2. 弱三色不变式（Weak Tri-color Invariant）
《破坏条件二》
弱三色不变式要求 灰色对象必须是白色对象的子集，即所有的灰色对象都必须引用白色对象。因为灰色对象本身处于标记过程中，它们需要被进一步扫描并标记其引用的对象。因此，弱三色不变式保证了在标记过程中，灰色对象是有效的，并且它们应该继续处理和标记其引用的白色对象。
具体来说，弱三色不变式的含义是：
- 灰色对象必须引用白色对象。如果灰色对象引用的是黑色对象或者灰色对象，标记过程就不符合这个不变式，可能存在循环引用或者标记过程中的其他问题。
6. 屏障机制
强弱三色不变式保证了以下两点：
- 强三色不变式：黑色对象所引用的所有对象都必须是黑色的（即完全标记）。也就是说，黑色对象引用的对象不应当是白色或灰色对象。
- 弱三色不变式：灰色对象必须引用至少一个白色对象。灰色对象在被完全扫描并标记其引用的对象之前，至少应该引用一个未标记的对象。
为了确保三色标记法在并发环境下能够正确执行，并避免在标记过程中的破坏，我们需要引入屏障机制。
屏障机制的作用
在并发标记过程中，屏障机制保证了在垃圾回收标记过程中的对象引用不会发生不一致的变化。这种机制确保了标记过程中的三色不变式不被破坏。
屏障机制的主要作用是防止对象的状态（颜色）在标记过程中被不一致地修改，导致 GC 标记过程不准确。它的作用在于防止：
- 黑色对象引用白色对象：如果标记过程中某个黑色对象引用了一个白色对象，会违反强三色不变式。
- 灰色对象丢失对白色对象的引用：如果一个灰色对象的引用关系被修改，它可能会丢失对某些白色对象的引用，导致这些对象被错误地视为不可达对象。
通过引入屏障机制，可以确保对象的颜色状态在并发的标记过程中不会发生不一致。
问题背景
在 Go 中，GC 是并发执行的，意味着标记和清除操作可能在多个 Goroutine 中并行进行，这就需要一种机制来防止并发修改对象引用时，导致标记过程的不一致性。如果对象的引用在标记过程中被改变，可能会导致标记不完全或不正确的回收。
插入写屏障（Insert Write Barrier）
插入写屏障是一种保护机制，用来确保在并发标记过程中，当一个黑色对象引用一个白色对象时，能够及时发现并处理。具体来说，插入写屏障确保在对象引用被修改时，维持三色不变式，尤其是防止黑色对象引用到白色对象，从而破坏强三色不变式。
插入写屏障的工作原理：
当一个黑色对象修改其引用，并且该引用指向一个白色对象时，系统将通过插入写屏障触发以下操作：
- 及时标记白色对象为灰色，即白色对象变成了可达的，需要被标记。
- 这意味着，即使黑色对象的引用指向了白色对象，插入写屏障会将该白色对象标记为灰色，防止其在随后的标记过程中被回收。
插入写屏障的作用是：
- 防止黑色对象引用白色对象：如果黑色对象引用了白色对象，插入屏障会将白色对象转为灰色，以保证黑色对象的引用关系不会违反强三色不变式。
- 确保并发过程中的标记完整性：屏障确保即使在并发环境中，所有对象的标记过程都是一致的。
插入写屏障的示例：
假设我们有两个对象：objA 和 objB，objA 是黑色的，objB 是白色的。如果 objA 修改了对 objB 的引用，插入写屏障会保证 objB 在该修改后被及时标记为灰色。
删除写屏障（Delete Write Barrier）
删除写屏障是另一种保护机制，主要用于防止 灰色对象与它们引用的 白色对象 之间的引用关系被丢失，避免破坏 弱三色不变式。
删除写屏障的工作原理：
当一个灰色对象修改或删除它对白色对象的引用时，系统将通过 删除写屏障 来保护标记过程。删除写屏障确保，即使在并发环境下，灰色对象不会丢失它们对白色对象的引用，从而避免丢失正确的标记信息。
- 灰色对象的引用删除操作：当灰色对象删除它对一个白色对象的引用时，删除屏障会被触发。
- 保护引用关系：删除屏障确保在删除操作发生时，灰色对象不会丢失它对任何白色对象的引用。删除屏障可能会重新将这些对象标记为灰色，防止这些引用关系的丢失。
删除写屏障的作用是：
- 保护灰色对象的引用关系：当灰色对象删除或修改对白色对象的引用时，删除屏障保证该操作不会破坏垃圾回收的标记一致性。
- 避免丢失引用：通过删除屏障，灰色对象仍然保持对其他未标记对象的引用，避免错误回收。
3、Go V1.8混合写屏障机制
混合写屏障机制的提出
在 Go 1.8 中，垃圾回收的标记过程做了一些改进，特别是引入了混合写屏障机制。这是因为在并发垃圾回收的过程中，某些操作可能会修改对象的引用关系，导致标记过程中的不一致性，进而影响回收的准确性。
混合写屏障的设计目标是确保当并发线程修改对象的引用时，能够高效地保证 GC 的一致性，防止垃圾回收的并发标记阶段受到破坏。
混合写屏障的作用
混合写屏障机制的主要作用是帮助垃圾回收器在标记过程中，处理对对象引用的并发修改，确保三色标记法的不变式不被破坏。
具体来说，混合写屏障机制包括以下几种情形的处理：
- 防止黑色对象引用白色对象：这是三色标记法中的 强三色不变式，要求任何黑色对象引用的对象，必须是黑色的。如果黑色对象引用了一个白色对象，那么系统会及时标记白色对象为灰色，从而确保标记过程的一致性。
- 灰色对象的修改：当一个灰色对象修改了它的引用（尤其是指向白色对象），需要使用屏障机制来确保修改不会破坏标记的一致性。灰色对象的引用变化会及时更新标记，确保引用关系的正确性。
- 白色对象的引用更新：白色对象通常表示“不可达”的对象，但如果它被引用并且变成了灰色或黑色，标记过程会更新它的状态。
混合写屏障机制的工作原理
混合写屏障机制的工作原理，可以从以下几个方面进行理解：
1. 合并了两种不同的写屏障机制
在 Go 1.8 之前，GC 主要依靠 插入写屏障（Insert Write Barrier）和 删除写屏障（Delete Write Barrier）来保证并发标记的一致性。而在 Go 1.8 中，混合写屏障机制将这两种屏障合并成一种机制，能够在对对象引用进行修改时，自动触发对相关对象的标记，避免冗余的屏障操作。
- 插入写屏障：用于防止黑色对象引用白色对象，当黑色对象修改其引用时，插入写屏障会将引用的白色对象标记为灰色。
- 删除写屏障：用于防止灰色对象删除或修改对白色对象的引用时丢失标记信息，删除屏障会确保引用不被破坏。
通过 混合写屏障，这两种屏障机制被合并，以便更高效地处理并发的引用修改操作。
2. 提高并发性能
由于 Go 的垃圾回收需要在多核处理器上高效工作，混合写屏障机制设计旨在减少并发写入对 GC 的影响。混合写屏障机制通过更精细化的标记方式，在并发环境下减少了需要执行的屏障数量，从而提高了标记的效率和垃圾回收的总体性能。
3. 优化并发操作的内存访问
写屏障的作用不仅仅是避免 GC 中标记的破坏，还需要在并发环境中确保高效的内存访问。通过混合屏障的机制，GC 可以更灵活地处理并发修改，避免了阻塞或者不必要的同步操作，从而提高了 GC 的效率。
4. 减少 GC 的暂停时间
Go 的垃圾回收器设计旨在减少 STW（Stop-The-World）时间，也就是在 GC 执行过程中，暂停所有 Goroutine 进行垃圾回收的时间。混合写屏障机制能够减少 STW 时间，因为它在后台并发地处理写屏障，避免了过多的停顿。
混合写屏障机制的实现
Go 1.8 采用了 并发写屏障的方式实现混合写屏障。它通过在运行时维护一个 写屏障缓冲区，来记录和触发需要修改的引用。这些缓冲区用于存储那些发生了引用修改的对象，GC 会在后续的标记过程中，检查这些修改并及时更新标记。
写屏障缓冲区的内容会被定期检查，并在标记过程中进行合并，从而保证标记过程的一致性。通过这种机制，GC 在执行标记和清除阶段时，能够高效、并发地进行，而不会影响标记的正确性。