Go 语言实践 runtime

Go 语言实践 runtime

goroutine 原理

goroutine

goroutine 在 go 里面叫协程。区别与线程,由 go runtime 自身实现的强大的调度器和内存管理实现。针对于一些高并发厂家。相较于每个线程固定 2M 的内存模式，goroutine 初始只有 2K，随着任务增长按需增长

goroutine 和 thread 区别

内存占用，goroutine 初始栈内存只有 2KB，运行过程中，如果栈空间不够用，可以动态扩容
创建、销毁线程的创建和销毁将是巨大的开销，是内核级的交互。goroutine 是用户态线程，由 runtime 管理，创建和销毁消耗都非常小
调度切换
抛开陷入内核，线程切换会消耗 1000-1500 纳秒(上下文保存成本高，较多寄存器，公平性，复杂时间计算统计)，一个纳秒平均可以执行 12-18 条指令。
所以由于线程切换，执行指令的条数会减少 12000-18000。goroutine 的切换约为 200 ns(用户态、3 个寄存器)，相当于 2400-3600 条指令。因此，goroutines 切换成本比 threads 要小得多。
复杂性
线程的创建和退出复杂，多个 thread 间通讯复杂(share memory)。
不能大量创建线程(参考早期的 httpd)，成本高，使用网络多路复用，存在大量 callback(参考 twemproxy、nginx 的代码)。对于应用服务线程门槛高，例如需要做第三方库隔离，需要考虑引入线程池等。

M:N 模型

Go 创建 M 个线程(CPU 执行调度的单元，内核的 task_struct)，之后创建的 N 个 goroutine 都会依附在这 M 个线程上执行，即 M:N 模型。它们能够同时运行，与线程类似，但相比之下非常轻量。因此，程序运行时，Goroutines 的个数应该是远大于线程的个数的（phread 是内核线程？）。
同一个时刻，一个线程只能跑一个 goroutine。当 goroutine 发生阻塞 (chan 阻塞、mutex、syscall 等等) 时，Go 会把当前的 goroutine 调度走，让其他 goroutine 来继续执行，而不是让线程阻塞休眠，尽可能多的分发任务出去，让 CPU 忙。

M:N 模型 N 个 goroutine 依附于 M 个线程上执行。通常 goroutine 阻塞时，go 会把当前 goroutine 调度走，让其它的 goroutine 来执行

GMP 调度模型

G - goroutine ,无限制。使用 struct runtime.g 包含了当前 goroutine 状态，堆栈，上下文
M - 工作线程（os thread）也被称为 machine。使用 struct runtimw.m 所有 M 是有线程栈的
P - “Processor”是一个抽象的概念，并不是真正的物理 CPU。
Processor 指处理器。它负载衔接 G 和 M 的调度上下文，将等待执行的 G 和 M 对接。当 P 有任务时就会创建或唤醒一个 M 来执行它队列的任务维护一个全局队列和 gFree 空闲协程列表。P 的数量=GOMAXPROCS 环境变量默认是 CPU 核心数。

GM 调度器， go1.2 版本的调度器实现，维护一个全局队列，M 每次都是从全局队列里面捞任务
GM 调度器带来的问题

单一全局互斥锁(Sched.Lock)和集中状态存储
导致所有 goroutine 相关操作，比如：创建、结束、重新调度等都要上锁。
Goroutine 传递问题
M 经常在 M 之间“可运行的”goroutine 。刚创建又被丢入全局队列。而不是本地执行，不必要的开销
Per-M 持有内存缓存。
每个 M 只有需要在运行的这个 goroutine 才会需要这个 goroutine 的内存，当进行系统调用时，这个内存时不需要的。造成很大的内存浪费。内存亲缘性也较差，G 在 M 运行后对内存数据进行预热。下次可能切换到别的 M，又需要预热一边。开销较大
严重的线程阻塞/解锁
在系统调用情况下，工作线程通常被阻塞和取消阻塞。比如 M 找不到 G 时，M 需要频繁进行阻塞，唤醒来检查是否有新 G 进来

GMP 调度器
引入了 local queue，因为 P 的存在，runtime 并不需要做一个集中式的 goroutine 调度，每一个 M 都会在 P’s local queue、global queue 或者其他 P 队列中找 G 执行，减少全局锁对性能的影响。
这也是 GMP Work-stealing 调度算法的核心。注意 P 的本地 G 队列还是可能面临一个并发访问的场景，为了避免加锁，这里 P 的本地队列是一个 LockFree 的队列，窃取 G 时使用 CAS 原子操作来完成。关于 LockFree 和 CAS 的知识参见 Lock-Free。

Work-stealing 调度算法

当一个 P 执行完本地所有 G 时，并且全局队列为空的时候，会尝试挑选一个受害者 P，从它的 G 队列中窃取一般的 G。或者从全局队列获取（当前个数/gomaxprocs）个 G。并为了保证公平性。使用随机算法找一个 P 来作为受害者
光窃取失败是不够的，可能导致全局队列饥饿。P 的调度算法还会在每个 N 轮调度之后去全局获取一个 G
谁放入全局队列。新建 G 时 P 的本地队列已经超过 256 个，会放半数的 G 到全局队列去。阻塞系统找不到空闲的 P 也会放到全局队列

syscall 系统调用调用 syscall 会解绑 P，然后 M 和 G 进入阻塞。而 P 此时的状态就是 syscall，这时的 P 不能绑定别的 M。如果短时间 M 就唤醒了，那么 M 会优选重新获取这个 P。有利息数据的局部性。这个工作是 system monitor 被称为 sysmon，会定时扫描。
P1 和 M 脱离后在 idle list 等待被绑定（处于 syscall）。syscall 结束后按如下规则执行

尝试获取同一个 P
尝试获取 idle list 的其它空闲 P
找不到空闲 P,把 G 放回全局队列，M 放回 idle list

spinning thread 线程自旋（目标是不停的找 G）。好处时 G 能实时执行，缺点 G 迟迟不来，浪费 CPU。需要设计一个算法，来合理自旋

M 不带 P 的找 P 挂载（相当于有 P 释放就立马结合）
M 带 P 找 G 运行（有可运行的控制器（MP）一有 G 立马执行）
为避免过多自旋，最多允许 GOMAXPROCS 个自旋。类型 1 自旋了，类型 2 就不自旋了

GMP 问题总结

单一全局互斥锁和集中状态存储
G 被分为全局队列和本地队列。全局队列依然有锁，但是使用场景明显变少。P 的本地队列是无锁队列效率更高
goroutine 传递问题
G 在创建就在 P 的本地队列。可以避免在 G 之间传递（窃取除外），G 对 P 的数据局部性好。系统调用后 M 会优先获取阻塞之前的 P。所有 G 对 M 数据局部性好，G 对 P 的数据局部性好
Per-M 持有内存缓存
内存只存在 P 的结构之中，P 最多有个 GOMAXPROCS 个，远小于 M 的个数，所有内存没有过度消耗
严重的线程阻塞和解锁
通过引入自旋，保证任何时候都有处于等待状态的自旋 M。避免在等大可用的 P 和 G 时频繁的阻塞和唤醒

sysmon
sysmon 监控线程，它无需 P 也可以运行。它是一个死循环。做一些全局补偿逻辑

释放闲置内存
长时间没有垃圾回收，回收一波
长时间未处理的 netpoll，加入全局队列
长时间运行的 G 任务发出抢占调度
收回因长时间系统调用阻塞的 P

Goroutine Lifecycle

G 很容易创建，栈很小以及快速的上下文切换。基于这些原因，开发人员非常喜欢并使用它们。然而，一个产生许多 shortlive 的 G 的程序将花费相当长的时间来创建和销毁它们。
每个 P 维护一个 freeList G，保持这个列表是本地的，这样做的好处是不使用任何锁来 push/get 一个空闲的 G。当 G 退出当前工作时，它将被 push 到这个空闲列表中。

为了更好地分发空闲的 G ，调度器也有自己的列表。它实际上有两个列表：一个包含已分配栈的 G，另一个包含释放过堆栈的 G（无栈）。

内存分配原理

堆栈&逃逸分析

堆和栈的定义：
Go 有两个地方可以分配内存，一个全局堆空间用来动态分配内存，另一个是每个 goroutine 都有自身的栈空间
堆和栈都是编程语言里的虚拟概念，并不是说在物理内存上有堆和栈之分，两者的主要区别是栈是每个线程或者协程独立拥有的，从栈上分配内存时不需要加锁。而整个程序在运行时只有一个堆，从堆中分配内存时需要加锁防止多个线程造成冲突，同时回收堆上的内存块时还需要运行可达性分析、引用计数等算法来决定内存块是否能被回收，所以从分配和回收内存的方面来看栈内存效率更高。

栈栈区的内存一般由编译器自动进行分配和释放。其中存储的函数的入参以及局部变量。这些参数随站函数的创建而创建，函数的返回而销毁
堆堆区的内存一般由编译器和工程师共同进行管理分配，交给 runtime GC 来释放。堆上分配必须找到一块足够大的内存来存放新的变量数据。后续释放时，垃圾回收器扫描堆空间不在被引用的对象
栈分配廉价。堆分配昂贵

逃逸分析：
通过检查变量的作用域是否超出它所在的栈来决定是否将它分配在堆上的技术，其中变量的作用域超出它所在的栈，这种行为称为逃逸。逃逸分析在大多数语言里属于静态分析：在编译期由静态代码分析来决定一个值是否能被分配到栈帧上，还是需要“逃逸”到堆上

减少 GC 压力，栈上的变量，随着函数退出后系统直接回收，不需要标记后在清除
减少内存碎片的产生
减轻分配堆内存的开销，提高程序的运行速度

当一个函数被调用时，会在两个相关的栈帧边界进行上下文切换。从调用函数切换到被调用函数，如果被调用函数需要传递参数，那么这些参数值也将传递到调用函数的帧边界。GO 语言中帧边解的数据传递是值传递的。Go 查找所有变量超过当前当前函数帧的，将他们分配堆上。

逃逸案例：

多级间接赋值容易导致逃逸，Date.Filed=value,data.file 如果都是引用类型，则会导致 value 逃逸。这里的等号=不单单是赋值，也表示参数传递。Go 的引用数据类型有 func,interface,slice,map,chan,*Type
一个值被分享到函数栈帧范围之外
在 for 循环外声明，在 for 循环内分配，同理闭包
发送指针或者带有指针的值到 channel 中
在一个切片上存储指针或带有指针的值
slice 的背后的数组重新分配了
在 interface 类型上调用方法

连续栈

分段栈：
Go 应用程序运行时，每个 goroutine 都维护着一个自己的栈区，这个栈区只能自己使用不能被其它 goroutine 使用，栈区 初始大小是 2KB(比 X86_64架构下线程的默认栈区2M要小很多)在 goroutine 运行的时候栈区会按照需要增长和收缩，占用的内存最大限制的默认值在 64 位系统上是 1GB
分段栈的实现方式存在hot split问题，如果栈快满了，那么下一次函数调用会强制触发栈扩容。但函数返回时，新分配的stack chunk会被清理掉。如果这个函数调用产生的范围是在一个循环中，会导致严重的性能问题，频发的 alloc/free

连续栈：
采用复制栈的实现方式，在热分裂场景中不会频发释放内存。即不像分配一个新的内存块并链接到老的栈内存块，而是分配一个两倍大的内存块并把老的内存块容复制到新的内存块处理，当栈缩减回之前大小时，我们不需要做任何事情

内存结构

内存管理

TCMalloc 是 Thread Cache Malloc 的简称,是 Go 内存管理的起源，Go 的内存管理是借鉴了 TCMalloc

内存碎片：
随着内存不断的申请和释放，内存上会存在大量的碎片，降低内存的使用率，为了解决内存碎片，可以将 2 个连续的未使用的内存块合并，减少碎片
大锁:
同一进程下所有线程共享相同的内存空间，他们申请内存时都需要加锁，如果不加锁就存在同一块内存被 2 个线程同事访问的问题

内存布局

我们需要先知道几个重要的概念：

page: 内存页，一块 8K 大小的内存空间。Go 与操作系统之间内存申请和释放，都是以 Page 为单位的
span：内存块，一个或多个连续的 page 组成一个 span 。
sizeclass: 空间规格，每个 span 都带有一个 sizeclass,标记着该 span 中的 page 应该如何使用
object: 对象，用来存储一个变量数据内存空间，一个 span 在初始化时，会被切割成一堆等大的 Object。假设 object 的大小是 16B，span 大小是 8K，那么就会把 span 中的 page 就会初始化 8k/16B =512 个 object

小于 32kb 内存分配：
当程序发生了 32Kb 以下的小块内存申请时，Go 会从一个叫做 mcahce的本地缓存给程序分配内存。这样一个内存块叫做 span ，它是要给程序分配内存时的分配单元
在 GMP 模型下，每个 P 处理器都会绑定一个本地缓存即 mcache,用于本地缓存，在当前 P 下，不需要加锁，避免锁过热。同时 mcahe 会被分割成多个 mspan。有 8b,16b,32b 等 67*2 中规格大小的 mspan，有助于减少内存碎片

mcentral:
mcentral 的作用为所有 mache 提供切分号的 msapn 资源。即是 mcache 的上级，不在被 P 处理器单独享有，被所有线共享着，是上一级缓存。mcentral 数据结构是一个双向链表，记录着分配的 mspan 和未被分配的 msapn。

mheap:
mcache 没有空闲的 mspan 会找 mcentral 去要，mcentral 没有合适的 mspan,会去找 mheap 去申请。而 mheap 没有合适资源时，会像操作系统去申请新内存了。mheap 做 go 顶级内存管理主要用于大对象的内存分配，以及管理未切割的 mspan，服务于 mcentral.存储结构式堆区，运行时将*KB 看作一页。

小于 16b 内存分配
对于小于 16 字节的对象（无指针）,Go 语言将其划分了 tiny 对象，划分 tiny 对象主要是为了极小的字符串和独立的转义变量。tiny 分配第一步就是尝试利用分配过的前一个元素空间，达到节约内存的目的

大于 32kb 内存分配
Go 没法使用工作线程的本地缓存 mcahce 和全局中心缓存 mcentral 上管理超过 32KB 的内存分配，只能去堆上 mheap 上分配对应数量的内存页给程序。

内存分配：
一般小对象都是 mspan 分配内存，大对象 mheap 分配内存
Go 在程序启动时，会像操作系统申请一大块内存，由 mheap 统一管理
Go 内存管理的基本单元都是 mspan,每种 mspan 可以分配特定大小的 object
mcache,mcentral,mheap 是 Go 内存管理的三大组件

GC 原理

Mark & Sweep

现在高级编程语言管理内存的方式分为两种：自动和手动，像 C，C++等编程语言使用手动管理内存的方式，工程师编写需要主动申请或释放内存，而 PHP，java 和 Go 等语言使用自动释放内存管理系统，由内存分配器和垃圾回收器就是我们常说的 GC。主流的垃圾回收算法：

引用计数
追踪式垃圾回收
Go 现在用的三色标记法就属于追踪式垃圾回收算法的一种

STW
stop the world ,GC 的一些阶段需要停止所有的 mutator 以确定当前的引用关系，这便是很多人对 GC 担心的来源，这也是 GC 算法优化的重点

Root
根对象是 mutator 不需要通过其它对象就可以直接访问到的对象。比如全局对象，栈对象中的数据等，通过 Root 对象，可以追踪到其它存活的对象

Mark Sweep 两个阶段：标记（Mark）和清除（Sweep）两个阶段，所以也叫标记-清扫垃圾回收算法

Stop the world

Mark: 通过 root 和 Root 直接间接访问到的对象，来寻找所有可达的对象，并进行标记

Sweep：对堆对象迭代，已标记的对象置位标记。所有未标记的对象加入 freelist，可用于再分配

Start the world

并发 GC 分为两层含义：
每个 mark 或 sweep 本身是多个线程（协程）执行的
mutator 和 collector 同时运行 background

Tri-color Mark & Sweep

三色标记是对标记清楚法的改进，标记清除法在整个执行时要求长时间 STW。Go 在 1.5 版本开始改为三色标记法，初始将所有内存标记为白色，然后将 roots 加入待扫描队列，进入队列即被视为变为灰色，然后使用并发的 goroutine 扫描队列中的指针，如果指针还引用了其它指针，那么被引用的也引入队列，被扫描的对象视为黑色

白色对象：潜在的垃圾，其内存可能会被垃圾收集器回收
黑色对象：活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象，垃圾回收器不会扫描这些对象的子对象
灰色对象：活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象

染色流程：

一开始所有对象被认为白色
一次遍历 root set 根节点放入灰色
选一个灰色对象，放入黑色，
遍历这个灰色对象的所有指针，标记为灰色
重复 3-4 操作，直至灰色对象没有需要遍历的。染色结束
剩下的白色的对象就是垃圾，需要被回收

Write Barrier

读屏障和写屏障
三色标记法标记和清扫虽然都并发的执行，但是标记阶段的前后需要 STW 一定时间来做 GC 的准备工作。引入强三色不变式，弱三色不变式，插入屏障和删除屏障来解决这些问题
强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象
弱三色不变性：黑色对象指向白色对象必须包含一条灰色对象经由多个白色对象可达路径

内存屏障只是对应一段特殊的代码，内存屏障代码在编译期间生成，本质就是运行期间对内存写操作进行拦截，想当于一个 hook 调用

Sweep
Sweep 过程并不会处理释放的对象内存置为 0。而是在分配重新使用的时候，重新 reset bit
Go 提供两种方式清理内存：

在后台启动一个 worker 等待清理内存，一个一个 mspan 处理
当申请分配内存时候 lazy 触发。

Stop The World

当前运行的所有程序都将被暂停
处理器 P，都会标记成停止状态，不在调度任何代码，调度器会把每个处理器的 M 分离出来，放入 idle 列表中去

channel

channel 对象结构
{
buf： circular queue 环形队列
sendx: send index 发送偏移量
recvx: receive index 取值偏移量
lock: mutex
}

内部也是维护了一把锁，保证各个 goroutine 数据安全
当发送或者取值发送一达到缓存上限，GMP 模型会将这个 goroutine 分离出 G1。让 G1 变成 waiting ,让其阻塞到这里

References

13.Go语言实践runtime