一、什么是GC
垃圾回收(Garbage Collection，简称GC)是编程语言中提供的自动的内存管理机制，自动释放不需要的对象，让出存储器资源，无需程序员手动执行。
Golang中的垃圾回收主要应用三色标记法，GC过程和其他用户goroutine可并发运行，但需要一定时间的STW(stop the world)，STW的过程中，CPU不执行用户代码，全部用于垃圾回收，这个过程的影响很大，Golang进行了多次的迭代优化来解决这个问题。
1.1 Golang GC 发展史：
- go1.1，提高效率和垃圾回收精确度。
标记-清除(mark and sweep)算法
- go1.3，提高了垃圾回收的精确度。
- go1.4，之前版本的runtime大部分是使用C写的，这个版本大量使用Go进行了重写，让GC有了扫描stack的能力，进一步提高了垃圾回收的精确度。
- go1.5，目标是降低GC延迟，采用了并发标记和并发清除，三色标记，write barrier，以及实现了更好的回收器调度，设计文档1，文档2，以及2015 版的Go talk。
三色标记——“强-弱” 三色不变式、插入屏障、删除屏障
- go1.6，小优化，当程序使用大量内存时，GC暂停时间有所降低。
- go1.7，小优化，当程序有大量空闲goroutine，stack大小波动比较大时，GC暂停时间有显著降低。
- go1.8，write barrier切换到hybrid write barrier，以消除STW中的re-scan，把STW的最差情况降低到50us，设计文档。
三色标记——混合屏障
-
go1.9，提升指标比较多，（1）过去
runtime.GC,debug.SetGCPercent, 和debug.FreeOSMemory都不能触发并发GC，他们触发的GC都是阻塞的，go1.9可以了，变成了在垃圾回收之前只阻塞调用GC的goroutine。（2）debug.SetGCPercent只在有必要的情况下才会触发GC。 - go.1.10，小优化，加速了GC，程序应当运行更快一点点。
- go1.12，显著提高了堆内存存在大碎片情况下的sweeping性能，能够降低GC后立即分配内存的延迟。
- go1.13，着手解决向操作系统归还内存的，提出了新的 Scavenger
- go1.14，替代了仅存活了一个版本的 Scavenger，全新的页分配器，优化分配内存过程的速率与现有的扩展性问题，并引入了异步抢占，解决了由于密集循环导致的 STW 时间过长的问题
- ......
二、常见的GC算法
- 引用计数法
根据对象自身的引用计数来回收，当引用计数归零时进行回收，但是计数频繁更新会带来更多开销，且无法解决循环引用的问题。
- 优点：简单直接，回收速度快
- 缺点：需要额外的空间存放计数，无法处理循环引用的情况；
- 标记清除法
标记出所有不需要回收的对象，在标记完成后统一回收掉所有未被标记的对象。
- 优点：简单直接，速度快，适合可回收对象不多的场景
- 缺点：会造成不连续的内存空间（内存碎片），导致有大的对象创建的时候，明明内存中总内存是够的，但是空间不是连续的造成对象无法分配；
- 复制法
复制法将内存分为大小相同的两块，每次使用其中的一块，当这一块的内存使用完后，将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉。
- 优点：解决了内存碎片的问题，每次清除针对的都是整块内存，但是因为移动对象需要耗费时间，效率低于标记清除法；
- 缺点：有部分内存总是利用不到，资源浪费，移动存活对象比较耗时，并且如果存活对象较多的时候，需要担保机制确保复制区有足够的空间可完成复制；
- 标记整理
标记过程同标记清除法，结束后将存活对象压缩至一端，然后清除边界外的内容。
- 优点：解决了内存碎片的问题，也不像标记复制法那样需要担保机制，存活对象较多的场景也使适用；
- 缺点：性能低，因为在移动对象的时候不仅需要移动对象还要维护对象的引用地址，可能需要对内存经过几次扫描才能完成；
- 分代式
将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。
三、go 1.3之前的标记-清除(mark and sweep)算法
此算法主要有两个主要的步骤：
- 标记(Mark phase)
- 清除(Sweep phase)
第一步，暂停程序业务逻辑, 找出不可达的对象，然后做上标记。第二步，回收标记好的对象。
操作非常简单，但是有一点需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即 STW(stop the world)。也就是说，这段时间程序会卡在哪儿。
第二步, 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示：
第三步, 标记完了之后，然后开始清除未标记的对象. 结果如下.
第四步, 停止暂停，让程序继续跑。然后循环重复这个过程，直到process程序生命周期结束。
3.1 标记-清扫(mark and sweep)的缺点
- STW，stop the world；让程序暂停，程序出现卡顿 (重要问题)。
- 标记需要扫描整个heap
- 清除数据会产生heap碎片
所以Go V1.3版本之前就是以上来实施的, 流程是
Go V1.3 做了简单的优化,将STW提前, 减少STW暂停的时间范围.如下所示
这里面最重要的问题就是：mark-and-sweep 算法会暂停整个程序 。
Go是如何面对并这个问题的呢？接下来G V1.5版本 就用三色并发标记法来优化这个问题.
四、go 1.5的三色并发标记法
三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些. 我们来看一下具体的过程.
第一步 , 就是只要是新创建的对象,默认的颜色都是标记为“白色”.
这里面需要注意的是, 所谓“程序”, 则是一些对象的跟节点集合.
所以上图,可以转换如下的方式来表示.
第二步, 每次GC回收开始, 然后从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合。
第三步, 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合
第四步, 重复第三步, 直到灰色中无任何对象.
第五步: 回收所有的白色标记表的对象. 也就是回收垃圾.
以上便是三色并发标记法, 不难看出,我们上面已经清楚的体现三色的特性, 那么又是如何实现并行的呢?
Go是如何解决标记-清除(mark and sweep)算法中的卡顿(stw，stop the world)问题的呢？
4.1 没有STW的三色标记法
我们还是基于上述的三色并发标记法来说, 他是一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。我们举一个场景.
如果三色标记法, 标记过程不使用STW将会发生什么事情?
可以看出，有两个问题, 在三色标记法中,是不希望被发生的
- 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
当以上两个条件同时满足时, 就会出现对象丢失现象!
当然, 如果上述中的白色对象3, 如果他还有很多下游对象的话, 也会一并都清理掉.
为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？
答案就是, 那么我们只要使用一个机制,来破坏上面的两个条件就可以了.
4.2 屏障机制
我们让GC回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式.
4.2.1 “强-弱” 三色不变式
- 强三色不变式
不存在黑色对象引用到白色对象的指针。
- 弱三色不变式
所有被黑色对象引用的白色对象都处于灰色保护状态.
为了遵循上述的两个方式,Golang团队初步得到了如下具体的两种屏障方式“插入屏障”, “删除屏障”.
4.2.2 插入屏障
具体操作: 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)
满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)
伪码如下:
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(新下游对象ptr)
//2
当前下游对象slot = 新下游对象ptr
}
场景：
A.添加下游对象(nil, B) //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B) //A 将下游对象C 更换为B， B被标记为灰色
这段伪码逻辑就是写屏障,. 我们知道,黑色对象的内存槽有两种位置, 栈和堆. 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中.
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
但是如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况(如上图的对象9). 所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束.
最后将栈和堆空间 扫描剩余的全部 白色节点清除. 这次STW大约的时间在10~100ms间.
4.2.3 删除屏障
具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)
伪代码：
添加下游对象(当前下游对象slot， 新下游对象ptr) {
//1
if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
标记灰色(当前下游对象slot) //slot为被删除对象， 标记为灰色
}
//2
当前下游对象slot = 新下游对象ptr
}
场景：
A.添加下游对象(B, nil) //A对象，删除B对象的引用。 B被A删除，被标记为灰(如果B之前为白)
A.添加下游对象(B, C) //A对象，更换下游B变成C。 B被A删除，被标记为灰(如果B之前为白)
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。
五、go 1.8的混合写屏障(hybrid write barrier)机制
插入写屏障和删除写屏障的短板：
- 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
- 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。
5.1 混合写屏障规则
具体操作:
1、GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，
2、GC期间，任何在栈上创建的新对象，均为黑色。
3、被删除的对象标记为灰色。
4、被添加的对象标记为灰色。
满足: 变形的弱三色不变式.
伪代码：
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(当前下游对象slot) //只要当前下游对象被移走，就标记灰色
//2
标记灰色(新下游对象ptr)
//3
当前下游对象slot = 新下游对象ptr
}
这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。
5.2 混合写屏障的具体场景分析
接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。
注意混合写屏障是Gc的一种屏障机制，所以只是当程序执行GC的时候，才会触发这种机制。
GC开始：扫描栈区，将可达对象全部标记为黑
5.2.1 场景一： 对象被一个堆对象删除引用，成为栈对象的下游
伪代码
//前提：堆对象4->对象7 = 对象7； //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7； //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
5.2.2 场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游
伪代码
new 栈对象9；
对象8->对象3 = 对象3； //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null； //对象2 删除引用 对象3
5.2.3 场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
5.2.4 场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7； //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null； //对象4 删除引用 对象7
Golang中的混合写屏障满足弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间。
六、垃圾回收过程
6.1 Marking setup
为了打开写屏障，必须停止每个goroutine，让垃圾收集器观察并等待每个goroutine进行函数调用， 等待函数调用是为了保证goroutine停止时处于安全点。
// 如果goroutine4 处于如下循环中，运行时间取决于slice numbers的大小
func add(numbers []int) int {
var v int
for _, n := range numbers {
v += n
}
return v
}
下面的代码中，由于for{} 循环所在的goroutine 永远不会中断，导致始终无法进入STW阶段，资源浪费；Go 1.14 之后，此类goroutine 能被异步抢占，使得进入STW的时间不会超过抢占信号触发的周期，程序也不会因为仅仅等待一个goroutine的停止而停顿在进入STW之前的操作上。
func main() {
go func() {
for {
}
}()
time.Sleep(time.Milliecond)
runtime.GC()
println("done")
}
6.2 Marking
一旦写屏障打开，垃圾收集器就开始标记阶段，垃圾收集器所做的第一件事是占用25%CPU。
标记阶段需要标记在堆内存中仍然在使用中的值。首先检查所有现goroutine的堆栈，以找到堆内存的根指针。然后收集器必须从那些根指针遍历堆内存图，标记可以回收的内存。
当存在新的内存分配时，会暂停分配内存过快的那些 goroutine，并将其转去执行一些辅助标记（Mark Assist）的工作，从而达到放缓继续分配、辅助 GC 的标记工作的目的。
6.3 Mark终止
关闭写屏障，执行各种清理任务（STW - optional ）
6.4 Sweep (清理)
清理阶段用于回收标记阶段中标记出来的可回收内存。当应用程序goroutine尝试在堆内存中分配新内存时，会触发该操作，清理导致的延迟和吞吐量降低被分散到每次内存分配时。
清除阶段出现新对象：
清除阶段是扫描整个堆内存，可以知道当前清除到什么位置，创建的新对象判定下，如果新对象的指针位置已经被扫描过了，那么就不用作任何操作，不会被误清除，如果在当前扫描的位置的后面，把该对象的颜色标记为黑色，这样就不会被误清除了
什么时候进行清理？
主动触发（runtime.GC()） 被动触发 （GC百分比、定时）
七、关注指标与调优示例
7.1 关注指标
Go 的 GC 被设计为成比例触发、大部分工作与赋值器并发、不分代、无内存移动且会主动向操作系统归还申请的内存。因此最主要关注的、能够影响赋值器的性能指标有：
- CPU 利用率：回收算法会在多大程度上拖慢程序？有时候，这个是通过回收占用的 CPU 时间与其它 CPU 时间的百分比来描述的。
- GC 停顿时间：回收器会造成多长时间的停顿？目前的 GC 中需要考虑 STW 和 Mark Assist 两个部分可能造成的停顿。
- GC 停顿频率：回收器造成的停顿频率是怎样的？目前的 GC 中需要考虑 STW 和 Mark Assist 两个部分可能造成的停顿。
- GC 可扩展性：当堆内存变大时，垃圾回收器的性能如何？但大部分的程序可能并不一定关心这个问题。
7.2 调优示例
7.2.1 合理化内存分配的速度、提高赋值器的 CPU 利用率
goroutine 的执行时间占其生命周期总时间非常短的一部分，但大部分时间都花费在调度器的等待上了，说明同时创建大量 goroutine 对调度器产生的压力确实不小，我们不妨将这一产生速率减慢，一批一批地创建 goroutine。
func concat() {
for n := 0; n < 800; n++ {
go func() {
s := "Go GC"
s += " " + "Hello"
s += " " + "World"
_ = s
}()
}
}
//改进
func concat() {
wg := sync.WaitGroup{}
for n := 0; n < 100; n++ {
wg.Add(8)
for i := 0; i < 8; i++ {
go func() {
s := "Go GC"
s += " " + "Hello"
s += " " + "World"
_ = s
wg.Done()
}()
}
wg.Wait()
}
}
7.2.2 降低并复用已经申请的内存
newBuf()产生的申请的内存过多, sync.Pool 是内存复用的一个最为显著的例子
func newBuf() []byte {
return make([]byte, 10<<20)
}
b := newBuf()
//改进
var bufPool = sync.Pool{
New: func() interface{} {
return make([]byte, 10<<20)
},
}
b := bufPool.Get().([]byte)
7.2.3 调整 GOGC
降低收集器的启动频率（提高GC百分比）无法帮助垃圾收集器更快完成收集工作。降低频率会导致垃圾收集器在收集期间完成更多的工作。 可以通过减少新分配对象数量来帮助垃圾收集器更快完成收集工作。
7.3 小结
控制内存分配的速度，限制 goroutine 的数量，从而提高赋值器对 CPU 的利用率。
减少并复用内存，例如使用 sync.Pool 来复用需要频繁创建临时对象，例如提前分配足够的内存来降低多余的拷贝。
需要时，增大 GOGC 的值，降低 GC 的运行频率。
