Golang垃圾回收

Golang内存管理

Golang运行调度三个基本概念: G、M、P;

• G: Goroutine执行的上下文环境;
• M: 操作系统进程;
• P: Processer; 调度器的关键, 调度器, 也可以认为约等于CPU;

Go内存管理

TCMalloc

Go将内存划分和分组为页(Page), 这和Java的内存结构完全不同, 没有分代内存, 这样的原因是Go的内存分配器采用了TCMalloc的设计思想:

Page

与TCMalloc中的Page相同, x64下1个Page的大小是8KB; 上图的最下方, 1个浅蓝色长方形代表1个Page;

Span

与TCMalloc中的Span相同, Span是内存管理的基本单位; 代码中为mspan, 一组连续的Page组成1个Span, 所以上图一组连续的浅蓝色长方形代表的是一组Page组成的1个Span, 另外1个淡紫色长方形为1个Span;

mcache

mcache是提供给P(逻辑处理器)的高速缓存, 用于存储小对象(对象大小<=32Kb); 尽管这类似于线程堆栈, 但它是堆的一部分, 用于动态数据; 所有类大小的mcache包含scan和noscan类型的mspan。Goroutine可以从mcache没有任何锁的情况下获取内存, 因为一次P只能有一个锁G。因此, 这更有效。mcache从mcentral需要时请求新的span;

mcentral

mcentral与TCMalloc中的CentralCache类似, 是所有线程共享的缓存, 需要加锁访问, 它按Span class对Span分类, 串联成链表, 当mcache的某个级别的内存被分配光时, 它会像mcentral申请1个当前级别的Span。每个mcentral包含两个mspanList:

• empty: 双向span链表, 包括没有空闲对象的span或缓存mcache中的span。当此处的span被释放时, 它将被移至non-empty span链表;
• non-empty: 有空闲对象的span双向链表。当从mcentral请求新的span, mcentral将从该链表中获取span并将其移入empty span链表;

mheap

mheap与TCMalloc中的PageHeap类似, 它是堆内存的抽象, 也是垃圾回收的重点区域, 把从OS申请出的内存页组织成Span, 并保存起来。当mcentral的Span不够用时会向mheap申请, mheap的Span不够用时会向OS申请, 向OS的内存申请是按页来的, 然后把申请来的内存页生成Span组织起来, 同样也是需要加锁访问的;

栈

这是栈存储区, 每个Goroutine(G)有一个栈。在这里存储了静态数据, 包括函数栈帧, 静态结构, 原生类型值和指向动态结构的指针。这与分配给每个P的mcache不是一回事;

内存分配

Go中的内存分类并不像TCMalloc分成小、中、大对象, 但是它的小对象里又细分了一个Tiny对象, Tiny对象指大小在1Byte到16Byte之间并且不包含指针的对象。小对象和大对象只用大小划定, 无其他区分;

核心思想: 把内存分为多级管理, 降低锁的粒度(只是去mcentral和mheap会申请锁), 以及多种对象大小类型, 减少分配产生的内存碎片;

微小对象(Tiny)（size < 16B）

使用mcache的微小分配器分配小于16个字节的对象, 并且在单个16字节块上可完成多个微小分配;

小对象（size 16B ~ 32KB）

大小在16个字节和32k字节之间的对象被分配在G运行所在的P的mcache对应的mspan size class上;

大对象（size > 32KB）

大于32 KB的对象直接分配在mheap的相应大小类上(span class);

• 如果mheap为空或没有足够大的页面满足分配请求, 则它将从操作系统中分配一组新的页(至少1MB);
• 如果对应的大下规格在mcache中没有可用的块, 则向mcentral申请;
• 如果mcentral中没有可用的块, 则向mheap中申请, 并根据BestFit算法找到最合适的mspan。如果申请到的mspan超出申请大小, 将会根据需求进行切分, 以返回用户所需的页数。剩余的页构成一个新的mspan放回mheap的空闲列表;
• 如果mheap中没有可用的span, 则向操作系统申请一系列新的页(最小1MB)。Go会在操作系统分配超大的页(称作arena)。分配一大批页会减少和操作系统通信的成本;

内存回收

go内存会分成堆区(Heap)和栈区(Stack)两个部分, 程序在运行期间可用主动从堆区申请内存空间, 这些内存由内存分配器分配并由垃圾收集器回收。栈区内存由编译器自动进行分配和释放, 栈区中存储的参数以及局部变量, 它们会随着函数的创建而创建, 函数的返回而销毁。如果只申请和分配内存, 内存终将枯竭, Go使用垃圾回收收集不再使用的span, 把span释放交给mheap, mheap对span进行span的合并, 把合并后的span加入到scav树中, 等待再分配内存时, 由mheap进行内存再分配。因此, Go堆是Go垃圾收集器管理主要区域;

标记清除算法

当成功区分出Go垃圾收集器管理区域的存活对象和死亡对象后, Go垃圾收集器接下来的任务就是执行GC, 释放无用对象占用的内存空间, 以便有足够的可用内存空间为新对象分配内存。

当堆空间被耗尽时, 就会STW(stop the world), 其执行过程可以分成标记和清除两个阶段。Go垃圾收集器从根节点开始遍历, 执行可达性分析算法, 递归标记所有被引用的对象为存活状态; 标记阶段结束后, 垃圾收集器会依次遍历堆中的对象并清除其中的未被标记为存活的对象;

由于用户程序在垃圾收集的过程中也不能执行(STW)。在可达性分析算法, Go的GC Roots一般为全局变量和G Stack中的引用指针, 和整堆的对象相比只是极少数, 因此它带来的停顿是非常短暂且相对固定的, 不随堆容量增长。在从GC Roots往下遍历对象的过程, 堆越大, 存储对象越多, 递归遍历越复杂, 要标记更多对象而产生的停顿时间自然就更长。因此我们需要用到更复杂的机制来解决STW的问题;

三色可达性分析

为了解决标记清除算法带来的STW问题, Go和Java都会实现三色可达性分析标记算法的变种以缩短STW的时间。三色可达性分析标记算法按”是否被访问过”将程序中的对象分成白色、黑色和灰色:

• 白色对象 - 对象尚未被垃圾收集器访问过, 在可达性分析刚开始的阶段, 所有的对象都是白色的, 若在分析结束阶段, 仍然是白色的对象, 即代表不可达;
• 黑色对象 - 表示对象已经被垃圾收集器访问过, 且这个对象的所有引用都已经被扫描过, 黑色的对象代表已经被扫描过而且是安全存活的, 如果有其他对象指向黑色对象无需再扫描一遍, 黑色对象不可能直接(不经过灰色对象)指向某个白色对象;
• 灰色对象 - 表示对象已经被垃圾收集器访问过, 但是这个对象上至少存在一个引用还没有被扫描过, 因此存在指向白色对象的外部指针, 垃圾收集器会扫描这些对象的子对象;

三色可达性分析算法大致流程是(初始状态所有对象都是白色):

1. 从GC Roots开始枚举, 它们所有的直接引用变成灰色(移入灰色集合), GC Roots变为黑色;
2. 从灰色集合中取出一个灰色对象进行分析:
   • 将这个对象所有的直接引用变为灰色, 放入灰色集合中;
   • 将这个对象变为黑色;
3. 重复步骤2, 一直重复直到灰色集合为空;
4. 分析完成, 仍然是白色的对象就是GC Roots不可达的对象, 可以作为垃圾被清理;

具体例子如下图所示, 经过三色可达性分析, 最后白色H为不可达的对象, 是需要垃圾回收的对象;

三色可达性分析

三色标记清除算法本身是不可以并发或者增量执行的, 它需要STW, 而如果并发执行, 用户程序可能在标记执行的过程中修改对象的指针;

三色标记清除算法(增量执行)

这种情况一般会有2种:

1. 一种是把原来应该垃圾回收的死亡对象错误的标记为存活。虽然这不好，但是不会导致严重后果, 只不过产生了一点逃过本次回收的浮动垃圾而已, 下次清理即可, 比如上图所示的三色标记过程种, 用户取消了从B对象到E对象的引用, 但是因为B到E已经被标记完成不会继续执行步骤2, 所以E对象最终会被错误的标记成黑色, 不会被回收, 这个D就是浮动垃圾, 会在下次垃圾收集中清理;
2. 一种是把原本存活的对象错误的标记为死亡, 导致”对象消失”, 这在内存管理种是非常严重的错误。比如上图所示的三色标记过程种, 用户程序建立了从B对象到H对象的引用(例如B.next=H), 接着执行D.next=nil, 但是因为B到H中不存在灰色对象, 因为在这之间不会继续执行三色并发标记中的步骤2, D到H之间的链接被断开, 所以H对象最终会被标记成白色, 会被垃圾收集器错误的回收。我们将这种错误称为悬挂指针, 即指针没有指向特定类型的合法对象, 影响了内存的安全性;

屏障技术

为了解决上述的”对象消失”的现象, Wilson于1994年在理论上证明了, 当且仅当以下两个条件同时满足时, 会产生”对象消失”的问题, 即原本应该是黑色的对象被误标为白色:

• 赋值器插入了一条或多条从黑色对象到白色对象的新引用;
• 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用;

因此为了要解决并发扫描时的对象消失问题, 保证垃圾收集算法的正确性, 只需破坏这两个条件的任意一个即可, 屏障技术就是在并发或增量标记过程中保证三色不变性的重要技术;

内存屏障技术是一种屏障指令, 它可以让CPU或者编译器在执行内存相关操作时遵循特定的约束, 目前多数的现代处理器都会乱序执行指令以最大化性能, 但是该技术能够保证内存操作的顺序性, 在内存屏障前执行的操作一定会先于内存屏障后执行的操作。垃圾收集中的屏障技术更像是一个钩子方法, 它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码, 根据操作类型不同, 我们可以将它们分成读屏障(Read barrier)和写屏障(Write barrier)两种, 因此读屏障需要在读操作中加入代码片段, 对用户程序的性能影响很大, 所以编程语言往往都会采用写屏障保证三色不变性;

插入写屏障

Dijksrea在1978年提出了插入写屏障, 也被叫做增量更新, 通过如下所示的写屏障, 破坏上述第一个条件(赋值器插入了一条或多条从黑色对象到白色对象的新引用):

1
2
3
4
5
6
7
8

func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)          //先将新下游对象 ptr 标记为灰色     
    *slot = ptr
}
//说明：添加下游对象(当前下游对象slot, 新下游对象ptr) {  
    //step 1 标记灰色(新下游对象ptr)   
    //step 2 当前下游对象slot = 新下游对象ptr }
//场景：A.添加下游对象(nil, B) //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色A.添加下游对象(C, B) //A 将下游对象C 更换为B， B被标记为灰色

上述伪代码非常好理解, 当黑色对象(slot)插入新的指向白色对象(ptr)的引用关系时, 就尝试使用shade函数将这个新插入的引用(ptr)标记为灰色;

插入写屏障

假设我们上图的例子并发可达性分析中使用了插入写屏障:

1. GC将根对象Root2指向的B对象标记成黑色并将B对象指向的对象D标记成灰色;
2. 用户程序修改指针, B.next=H这时触发写屏障将H对象标记成灰色;
3. 用户程序修改D.next=nil;
4. GC依次遍历程序中的H和D将它们分别标记成黑色;

由于栈上的对象在垃圾回收中被认为是根对象, 并没有写屏障, 那么导致黑色的栈对象可能指向白色的堆对象, 例如上图1中Root2指向H, 且删除了由D指向H的引用, 由于没有写屏障, 那么H将会被删除。为了保障内存安全, Dijkstra必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描, 这两种方法各有各的缺点, 前者会大幅度增加写入指针的额外开销, 后者重新扫描栈对象时需要暂停对象, 垃圾收集算法的设计者需要在这两者之间做出权衡;

删除写屏障

Yuasa在1990年提出了删除写屏障, 因为一旦该写屏障开始工作, 它会保证开启写屏障时堆上所有对象的可达, 起始时STW扫描所有的goroutine栈, 保证所有堆上在用的对象都处于灰色保护下, 所以也被称为快照垃圾收集(Snapshot GC), 这是破坏了”对象消失”的第二个条件(赋值器在删除了全部从灰色对象到该白色对象的直接或间接引用);

1
2
3
4
5
6
7
8
9
10

// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {    
    shade(*slot) // 先将*slot标记为灰色    
    *slot = ptr
    }
//说明：添加下游对象(当前下游对象slot， 新下游对象ptr) {  //step 1  if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
    标记灰色(当前下游对象slot)     
    //slot为被删除对象， 标记为灰色  }    
    //step 2  当前下游对象slot = 新下游对象ptr}
//场景A.添加下游对象(B, nil)   //A对象，删除B对象的引用。B被A删除，被标记为灰(如果B之前为白)A.添加下游对象(B, C)     //A对象，更换下游B变成C。B被A删除，被标记为灰(如果B之前为白)

上述代码会在老对象的引用被删除时, 将白色的老对象涂成灰色, 这样删除写屏障就可以保证三色不变性, 老对象引用的下游对象一定可以被灰色对象引用;

但是这样也会导致一个问题, 由于会将有存活可能的对象都标记成灰色, 因此最后可能会导致应该回收的对象未被回收, 这个对象只有在下一个循环才会被回收, 比如下图的D对象

此处有图片

由于原始快照的原因, 起始也是执行STW, 删除写屏障不适用于栈特别大的场景, 栈越大, STW扫描时间越长;

混合写屏障

在Go语言v1.7版本之前, 运行时会使用Dijkstra插入写屏障保证三色不变性, 但是运行时并没有在所有垃圾收集根对象上开启插入写屏障。因为应用程序可能包含成百上千的Goroutine, 而垃圾收集的根对象一般包括全局变量和栈对象, 如果运行时需要在几百个Goroutine的栈上都开启写屏障, 会带来巨大的额外开销, 所以Go团队在v1.8结合上述2种写屏障构成了混合写屏障, 实现上选择了在标记阶段完成时暂停程序、将所有栈对象标记成灰色并重新扫描;

Go语言在v1.8组合Dijkstra插入写屏障和Yuasa删除写屏障构成了如下所示的混合写屏障, 该写屏障会将覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色;

1
2
3
4
5
6
7

func writePointer(slot, ptr) {
    shade(*slot)    
    if current stack is grey {
        shade(ptr)  
    }
    *slot = ptr
}

为了移除栈的重新扫描过程, 除了引入混合写屏障之外, 在垃圾收集的标记阶段, 我们还需要将创建的所有新对象都标记成黑色, 防止新分配的栈内存和堆内存中的对象被错误地回收, 以为栈内存在标记阶段最终都会变为黑色, 所以不再需要重新扫描栈空间。总结来说主要有这几点:

1. GC开始将栈上地对象全部扫描并标记为黑色;
2. GC期间, 任何在栈上创建地新对象, 均为黑色;
3. 被删除的堆对象标记成灰色;
4. 被添加的堆对象标记成灰色;

模拟面试

STW（Stop-The-World）

• STW问题: 在垃圾回收期间, 所有的程序操作都被暂停, 直到垃圾回收过程完成。这对高并发应用特别有害, 因为它会导致显著的响应时间和系统吞吐量下降。

STW的具体影响有哪些？例如在响应时间和吞吐量方面

• 响应时间: STW会导致所有Goroutine暂停, 用户请求无法得到及时响应, 导致应用程序的响应时间增加。
• 吞吐量: 在STW期间, 整个系统的处理能力会下降, 因为没有任何工作在进行。这会降低系统的吞吐量, 使得单位时间内处理的请求数量减少。

屏障技术

• 屏障技术: 通过在程序的某些操作上设置”屏障”, 来减少STW的时间。屏障主要有三种类型: 写屏障, 读屏障和删除屏障。

具体屏障类型

1. 写屏障: 写屏障在对象引用被写入时触发, 通过记录这些修改, 确保垃圾回收器能够跟踪到所有引用的变化。
   • 插入写屏障: 在对象引用被插入时触发。当一个新引用被写入某个对象字段时, 写屏障会记录这个操作。它确保在GC过程中, 这个新的引用被正确地标记和处理;
   • 删除写屏障: 在对象引用被删除时触发, 当一个引用从某个对象字段中被删除时, 写屏障会记录下这个操作, 确保GC能够正确处理引用的删除;
   • 混合写屏障: 结合了插入和删除写屏障的特性, 确保在对象引用被修改时正确记录, 结合插入和删除写屏障的功能, 确保任何引用的变化都能被追踪到。

具体实现:

1. 插入写屏障: 在对象赋值操作前, 插入写屏障逻辑, 记录新引用的对象;
2. 删除写屏障: 在对象字段被清空或重新赋值前, 记录旧引用的对象;
3. 混合写屏障: 综合上述两种操作, 确保所有引用变化都被记录;

三色标记清除算法的每一步是什么, 以及每一种颜色在个步中的作用？

步骤:

1. 初始化: 所有对象开始都是白色;
2. 标记根对象: 从根对象（Roots）开始扫描, 将根对象标记为灰色, 并将其放入待处理队列;
3. 处理灰色对象:
   • 取出一个灰色对象, 将它标记为黑色;
   • 扫描该对象引用的所有子对象, 将未标记的子对象标记为灰色, 并放入待处理队列;
4. 重复: 重复上一步, 直到待处理队列为空;
5. 清除白色对象: 所有未被标记为黑色对象（即白色对象）被认为是垃圾并清除;

颜色含义:

• 黑色: 已访问并处理完毕的对象, 不再需要扫描;
• 灰色: 已访问但其引用的对象还未全部处理的对象, 需要进一步扫描;
• 白色: 未访问的对象, 被认为是垃圾;

Slice

在Go语言中, Slice是一个动态数组的封装, 它由三个部分组成: 指向底层数组的指针、长度（len）和容量（cap）。

1
2
3
4
5

type slice struct {
    ptr *ElementType // 指向底层数组的指针
    len int          // 当前slice中元素的个数
    cap int          // slice的容量, 即底层数组中的元素个数
}

slice扩容策略

1. 每次扩容会使得新的容量变为原来的2倍(cap*2);
2. 如果当前slice的容量小于1024, 则每次扩容时新容量会变为原来的1.25倍(cap*1.25)。这种情况下, 对于小型slice, 扩容增长速度会慢一些, 以节省空间;
3. 如果slice的长度小于1024, 则新的容量会按照上述规则进行计算。否则, 新的容量会增加与当前slice长度的一半;

当slice进行扩容时, Go语言会进行以下操作:

• 分配一个新的底层数组, 并将原有的元素拷贝到新数组中;
• 将slice的指针指向新的底层数组, 同时更新slice的长度和容量;