Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Golang GC流程(为什么/为什么不) #46

Open
Petelin opened this issue Nov 9, 2019 · 4 comments
Open

Golang GC流程(为什么/为什么不) #46

Petelin opened this issue Nov 9, 2019 · 4 comments
Assignees

Comments

@Petelin
Copy link
Owner

Petelin commented Nov 9, 2019

Golang GC流程(为什么/为什么不)

介绍

中文最好的解释

什么时候触发GC

  • gcTriggerAlways: 强制触发GC
  • gcTriggerHeap: 当前分配的内存达到一定阈值时触发,这个阈值在每次GC过后都会根据堆内存的增长情况和CPU占用率来调整
  • gcTriggerTime: 当一定时间没有执行过GC就触发GC(2分钟)
  • gcTriggerCycle: runtime.GC()调用

什么是根

是一个有限的指针集合,程序可不经过其他对象直接访问这些指针,堆中的对象被加载时,需要先加载根中的指针。在Go中,一般为goroutine自己的栈空间和全局栈空间。

屏障

image

本来是灰色的B指向C, 但是我们还没有扫描B的时候, C被改指向A, 但是A已经是黑色的了, 那么现在黑色的指向一个白色的对象且没有任何灰色的对象指向白色的对象. 这时白色的对象无论如何都不会被访问到.

当回收器满足下面两种情况之一时,即可保证不会出现对象丢失问题。

弱三色不变式:所有被黑色对象引用的白色对象都处于灰色保护状态(直接或间接从灰色对象可达)。 强三色不变式:不存在黑色对象到白色对象的指针。

强三色不变式很好理解,强制性的不允许黑色对象引用白色对象即可。而弱三色不变式中,黑色对象可以引用白色对象,但是这个白色对象仍然存在其他灰色对象对它的引用,或者可达它的链路上游存在灰色对象。

  • 插入屏障拦截将白色指针插入黑色对象的操作,标记其对应对象为灰色状态,这样就不存在黑色对象引用白色对象的情况了,满足强三色不变式
  • 删除屏障也是拦截写操作的,但是是通过保护灰色对象到白色对象的路径不会断来实现的。如上图例中,在删除指针e时将对象C标记为灰色,这样C下游的所有白色对象,即使会被黑色对象引用,最终也还是会被扫描标记的,满足了弱三色不变式

实现

  • [go 1.5]插入屏障: Dijkstra的插入写屏障在标记开始时无需STW,可直接开始,并发进行,但结束时需要STW来重新扫描栈,标记栈上引用的白色对象的存活. 对栈上指针的写入添加写屏障的成本很高, 所以Go选择仅对堆上的指针插入增加写屏障, 总是认为栈是灰色的.
  • 删除屏障: Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象,但结束时无需STW. 但是快照会让一些对象多活过这一轮, 回收精度差.
  • [go 1.12]混合屏障: 只需要在开始时并发扫描各个goroutine的栈,使其变黑并一直保持,这个过程不需要STW,而标记结束后,因为栈在扫描后始终是黑色的,也无需再进行re-scan操作了,减少了STW的时间。

知乎R大对go GC的评价

R大的文章解决了三个认知问题

  • GO的GC算什么系列的, 其他语言有类似的实现吗?

    跟Java的CMS GC很像. 都是基于增量的写屏障的保证下的并发标记清楚机制.

  • 如果有那么他们的流程是什么样子的, 各自有哪些优化?

    核心流程一样,GO还有很多优化(比如不需要全部扫描栈), 但是也少了在re-marking之前试图重新标记的优化

  • GO GC优势是什么, 劣势是什么?

    最大限度的减少了STW, 但是会长时间占用CPU, 吞吐量上不去. 同时因为Go大量的struct都是创建在goroutine的栈上的, 所以创建新对象的数量是没有Java那么多的.

Go的CMS GC其实与HotSpot VMCMS GC相比是非常相似的。都是只基于incremental updatewrite-barrierMostly-Concurrent Mark-Sweep。两者的工作流程中最核心的步骤都是:

  1. Initial marking:扫描根集合
  2. Concurrent marking:并发扫描整个堆
  3. Re-marking:重新扫描在(2)的过程中发生了变化/可能遗漏了的引用
  4. Concurrent sweeping 具体到实现,两者在上述核心工作流程上有各自不同的扩展/优化。

两者的(1)都是stop-the-world的,这是两者的GC暂停的主要来源之一。 HotSpot VM的CMS GC的(3)也是stop-the-world的,而且这个暂停还经常比(1)的暂停时间要更长;Go 1.6 CMS GC则在此处做了比较细致的实现,尽可能只一个个goroutine暂停而不全局暂停----只要不是全局暂停都不算在用户关心的"暂停时间"里,这样Go版就比HotSpot版要做得好了。

HotSpot版CMS对(3)的细化优化是,在真正进入stop-the-world的re-marking之前,先尝试做一段时间的所谓并发的"abortable concurrent pre-cleaning",尝试并发的追赶应用程序对引用关系的改变,以便缩短re-marking的暂停时间。不过这里实现得感觉还不够好,还可以继续改进的。

有个有趣的细节,Go版CMS在(3)中重新扫描goroutine的栈时,只需要扫描靠近栈顶的部分栈帧,而不需要扫描整个栈----因为远离栈顶的栈帧可能在(2)的过程中根本没改变过,所以可以做特殊处理;HotSpot版CMS在(3)中扫描栈时则需要重新扫描整个栈,没抓住机会减少扫描开销。Go版CMS就是在众多这样的细节上比HotSpot版的更细致。

再举个反过来的细节。目前HotSpot VM里所有GC都是分代式的,CMS GC在这之中属于一个old gen GC,只收集old gen;与其配套使用的还有专门负责收集young gen的Parallel New GC(ParNew),以及当CMS跟不上节奏时备份用的full GC。分代式GC很自然的需要使用write barrier,而CMS GC的concurrent marking也需要write barrier。HotSpot VM就很巧妙的把这两种需求的write barrier做在了一起,共享一个非常简单而高效的write barrier实现。 Go版CMS则需要在不同阶段开启或关闭write barrier,实现机制就会稍微复杂一点点,write barrier的形式也稍微慢一点点。

从效果看Go 1.6的CMS GC做得更好,但HotSpot VM的CMS GC如果有更多投入的话也完全可以达到一样的效果;并且,得益于分代式GC,HotSpot VM的CMS GC目前能承受的对象分配速度比Go的更高,这算是个优势。

@rick-max
Copy link

rick-max commented Apr 3, 2020

Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象
这个详细过程是怎样的

@Petelin
Copy link
Owner Author

Petelin commented Apr 4, 2020

Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象
这个详细过程是怎样的

这个地方我也是找了很多资料也没看懂,只能人云亦云

@Petelin
Copy link
Owner Author

Petelin commented Apr 22, 2020

Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象
这个详细过程是怎样的

@rick-max
删除屏障不再需要在结束时 STW ,但需要在开始前 STW 记录初始快照,因为删除屏障同样不被应用与对栈指针的写入操作上,故初始栈指针指向的堆节点不能被 *slot 保护到,需要被提前保护。

之前有说过Dijkstra的实现是不对栈上的指针做操作(防止灰色对象大量膨胀),所以Yuasa的实现也是不对栈上的对象做操作,所以嘛要在开始的时候保护栈,而dijkstra是结束的时候保护。。。这个是我同事告诉我的

@Petelin
Copy link
Owner Author

Petelin commented Jul 22, 2020

Go Garbage Collection
GC实现的几种方式
目前比较常见的 GC 实现方式包括:

  • 标记清扫:从根对象出发,将确定存活的对象进行标记,并清扫可以回收的对象。
  • 标记整理:为了解决内存碎片问题而提出,在标记过程中,将对象尽可能整理到一块连续的内存上。
  • 分代式:将对象根据存活时间的长短进行分类,存活时间小于某个值的为年轻代,存活时间大于某个值的为老年代,永远不会参与回收的对象为永久代。并根据分代假设(如果一个对象存活时间不长则倾向于被回收,如果一个对象已经存活很长时间则倾向于存活更长时间)对对象进行回收。
  • 引用计数:根据对象自身的引用计数来回收,当引用计数归零时立即回收。
  • 面向请求的GC: 通过区分本地对象和共享对象

Go语言的选择,优势缺点
对于 Go 而言,Go 的 GC 目前使用的是无分代(对象没有代际之分)、不整理(回收过程中不对对象进行移动与整理)、并发(与用户代码并发执行)的三色标记清扫算法

  1. 无分代: Go 的编译器会通过逃逸分析将大部分新生对象存储在栈上(当 goroutine 死亡后栈也会被直接回收),只有那些需要长期存在的对象才会被分配到需要进行垃圾回收的堆中。分代会消耗额外的赋值器时间,Go团队认为下一个10年内存会比CPU增长快的多,所以不允许消耗一点CPU。
  2. 不整理:整理是为了解决内存碎片问题以及“允许”使用顺序内存分配器。但 Go 运行时的分配算法基于 tcmalloc,基本上没有碎片问题。这个问题对于Go来讲一点都不需要担心

Go GC 流程(基于go1.13)

无法复制加载中的内容

  1. Trigger type
  • gcTriggerHeap: 当前分配的内存达到一定阈值时触发,这个阈值在每次GC过后都会根据堆内存的增长情况和CPU占用率来调整(目前唯一可以调整的参数GCPercent, 以后可能会有MaxHeap)
  • gcTriggerTime: 当一定时间没有执行过GC就触发GC(2分钟)
  • gcTriggerCycle: runtime.GC()调用
  1. SweepTermination - STW (10-30 μs avg)
  2. 启用写屏障,在所有P都启用写屏障之前,不会扫描任何对象,这是使用STW完成的。
  3. 做一些准备工作,比如给每个P都创建一个新的G用做GC调度,root任务数计算
  4. 启用写屏障,启用mutator assist,并对根标记作业进行排队。

以下程序go1.14之前会退出吗?

func main() {
   go func() {
      for {
      }
   }()
   time.Sleep(time.Second * 1) //BAD CODE
   runtime.GC()
   println("OK")
}

答案是不会, 因为要先暂停所有的goroutine。 但是go1.14就可以解决(异步抢占)
3. Mark
收缩栈,释放掉dead G占用的栈空间
并发标记
分配mark
三色标记
|

写屏障
没有写屏障会出现漏标记的情况:
|
但是只要保证强三色不变式:不存在黑色对象到白色对象的指针。就可以保证不漏标记了
或者满足弱三色不变式,黑色对象可以引用白色对象,但是这个白色对象仍然存在其他灰色对象对它的引用,或者可达它的链路上游存在灰色对象。

go1.5 Dijkstra 插入写屏障
插入屏障拦截将白色指针插入黑色对象的操作,标记其对应对象为灰色状态,这样就不存在黑色对象引用白色对象的情况了,满足强三色不变式,如上图例中,在插入指针f时将C对象标记为灰色。Go1.5版本使用的Dijkstra写屏障就是这个原理,伪代码如下:

writePointer(slot, ptr):
    shade(ptr) // if prt is white
    *slot = ptr

优点:

  1. 不需要对读操作做特殊处理
  2. 保证波面始终向前推进
    缺点:
    在Golang中,对栈上指针的写入添加写屏障的成本很高,所以Go选择仅对堆上的指针插入增加写屏障,这样就会出现在扫描结束后,栈上仍存在引用白色对象的情况,这时的栈是灰色的,不满足三色不变式,所以需要对栈进行重新扫描使其变黑,完成剩余对象的标记,这个过程需要STW。这期间会将所有goroutine挂起,当有大量应用程序时,时间可能会达到10~100ms。
    go1.8版本引入了混合新屏障
writePointer(slot, ptr):
    shade(*slot) // 悲观假设所有被删除的指针都会被黑色隐藏, 单独使用需要提前dump对象引用保证正确性
    if current stack is grey:
        shade(ptr)
    *slot = ptr

插入写屏障需要重新扫描栈,删除写屏障不能防止指针从栈里被隐藏到黑色的堆区对象里,需要一开始stw扫描栈

Golang中的混合写屏障满足的是变形的弱三色不变式,同样允许黑色对象引用白色对象,白色对象处于灰色保护状态,但是只由堆上的灰色对象保护。由于结合了Yuasa的删除写屏障和Dijkstra的插入写屏障的优点,只需要在开始时并发扫描各个goroutine的栈,使其变黑并一直保持,这个过程不需要STW,而标记结束后,因为栈在扫描后始终是黑色的,也无需再进行re-scan操作了,减少了STW的时间。
4. Mark Termination - STW
记录一些统计信息,下次trigger的数据,开启sweeper, gctrace的打印
0. Go pacing 算法
1)一个GC周期将需要的扫描工作量的估算器;
2)一种让mutator在堆分配达到堆目标时执行估计的扫描工作量的机制;
3)一个在mutator协助时进行后台扫描的调度程序未充分利用CPU预算
4)用于GC触发的比例控制器

GC 调试

  • 程序内通过读 runtime.MemStats 然后打出来日志或者上报监控
  • GODEBUG=gctrace=1
    gc 2 @0.001s 2%: 0.018+1.1+0.029 ms clock, 0.22+0.047/0.074/0.048+0.34 ms cpu, 4->7->3 MB, 5 MB goal, 12 P
  • pprof + go tool trace trace.out
    |

演进和总结

  • Go 1:串行三色标记清扫
  • Go 1.3:并行清扫,标记过程需要 STW,停顿时间在约几百毫秒
  • Go 1.5:并发标记和清扫,停顿时间在一百毫秒以内
  • Go 1.6:使用 bitmap 来记录回收内存的位置,大幅优化垃圾回收器自身消耗的内存,停顿时间在十毫秒以内
  • Go 1.7:将栈收缩放到了mark阶段,停顿时间控制在两毫秒以内
  • Go 1.8:混合写屏障,停顿时间在半个毫秒左右
  • Go 1.9:彻底移除了栈的重扫描过程
  • Go 1.12:整合了两个阶段的 Mark Termination,但引入了一个严重的 GC Bug 至今未修(见问题 20),尚无该 Bug 对 GC 性能影响的报告
  • Go 1.14:替代了仅存活了一个版本的 scavenger,全新的页分配器,优化分配内存过程的速率与现有的扩展性问题,并引入了异步抢占,解决了由于密集循环导致的 STW 时间过长的问题

Ref:
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html
https://mp.weixin.qq.com/s/o2oMMh0PF5ZSoYD0XOBY2Q
https://zhuanlan.zhihu.com/p/74853110
https://medium.com/a-journey-with-go/go-how-does-the-garbage-collector-watch-your-application-dbef99be2c35
https://blog.golang.org/ismmkeynote
https://medium.com/a-journey-with-go/go-how-does-the-garbage-collector-watch-your-application-dbef99be2c35
https://github.com/golang/proposal/blob/master/design/17503-eliminate-rescan.md

@Petelin Petelin closed this as completed Jul 22, 2020
@Petelin Petelin reopened this Jul 22, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants