高伸缩性Go调度器设计(译)

阅读该文档前假设你已经对go语言及其当前调度实现的有所了解

当前调度器所存在的问题

当前的调度器限制了go并发的伸缩性,特别是在高吞吐量和并行计算方面.在一台8核的机器中跑 Vtocc 服务, cpu占用率高达70%, 性能分析数据显示14%cpu占用用在runtime.futex()上.通常,调度器可能会禁止用户在性能至关重要的地方使用惯用的细粒度并发。

当前调度器的不足:

全局锁和中心化状态, 协程相关的操作(创建、执行完成、重新调度等等) 都需要依赖锁的保护.
协程迁移, 协程在各个工作线程M之间频繁迁移,这可能会增加延迟和额外的开销.每个M必须能够执行任何可运行的协程，特别是刚刚创建协程的M.
线程存在本地缓存(M.cache),所有的M中都会有内存缓存和堆栈缓存, 然而只有当M在运行协程的时候才需要用到它们(处于系统调用中的线程M由于被阻塞而不要使用本地缓存). 真正在执行协程的线程M和所有的线程M比例高达1:100.这会导致过度资源消耗(每个MCache占用2MB的内存）和非常差的内存亲和性.
线程频繁的阻塞唤醒,处于系统调用中的线程会频繁阻塞和唤醒,这会增加很多性能开销.

新的调度器设计

Processors

总得来说就是在运行时引入P（处理器）的概念，并在处理器之上实现窃取工作的调度机制.

M是表操作系统线程, P提供所有G执行所需的资源环境, 当M执行G时, M会绑定一个P,当M处于空闲或者系统调用时(这种情况下, M 和 P解绑了),M需要一个P.

有一个跟P数量的相关的变量GOMAXPROCS, 所有的P会放到一个数组中, work-stealing(工作窃取)机制会用到这个变量.GOMAXPROCS的修改会调整运行时P的数量.

全局sched中的一些变量现在移到了P中, M中的一些变量(与协程执行相关的)也移到了P中.

struct P
{
Lock;
G *gfree; // freelist, moved from sched
G *ghead; // runnable, moved from sched
G *gtail;
MCache *mcache; // moved from M
FixAlloc *stackalloc; // moved from M
uint64 ncgocall;
GCStats gcstats;
// etc
...
};

P *allp; // [GOMAXPROCS]

还有一个空闲p列表

P *idlep; // lock-free list

当M将要执行G时, 它从p的空闲列表中取出一个p. 当M结束G的执行时, 把P放回空闲列表中,因此当M要执行G时, M一定要绑定一个P, 这种机制代替了之前全局 sched的原子操作 (mcpu/mcpumax ).

调度

当一个新创建的G或者旧的G变成runnable状态时, 这个G会被放到P的本地队列中,当P执行完一个G后,会从自己的本地队列中取出下一个G继续执行, 如果本地队列为空, 则随机从其他P的本地队列中窃取一半G过来执行.

系统调用(M 挂起/唤醒)

当M创建一个G时,M必须确保有其他的M来执行这个G(如果有空闲的M),同样的,当M进入系统调用时,确保有其他M来执行G.

有两种选择, 我们可以迅速挂起和唤醒M, 或者使M自旋.这是在性能和消耗不必要的CPU周期之间做的选择,其思想是使M空转并消耗CPU周期.但是,当我们把GOMAXPROCS 设置成1时, 这种方式不能影响命令行等程序的运行.

自旋有两种: 1.一个绑定了P的空闲M在自旋,目的是寻找G来执行 2. 没有绑定P的M自旋等待可用的P.最多有GOMAXPROCS 个M自旋（包括第一种和第二种）.当存在第二种空闲M时，第一种的空闲M不会被阻塞.

当有一个新的G创建时,或者M进入系统调用时,或者M从空闲便成繁忙时,确保至少有一个处于自旋的M(所有的p都处于忙碌中).这确保了没有任何可以运行的G;同时避免了过多的M在频繁阻塞唤醒.

cpu空转是没有意义的

终止/死锁检测

在分布式系统中,终止/死锁检测问题更大,通用的做法是仅在所有P空闲时进行检查（空闲P的全局原子计数器）,这允许执行更昂贵的检查，包括每P状态的聚合。

锁定操作系统线程

此功能不是性能关键.

当M锁定的G会变成非运行态(Gwaiting). M会立刻把P放到空闲列表中, 唤醒其他的M,然后阻塞住.
当M锁定的G变成可运行状态(G在runq的头部),当前M将自己的P和锁定的G交给与G关联的M，并唤醒M,当前M变为空闲。

空闲G

此功能不是性能关键.

有一个全局G队列,M在多次窃取G失败后会检查这个队列

实现计划

我们的目标是将整个事情分解成可以独立审查和提交的最小部分.

定义P结构体;实现 allp/idlep 队列(idlep 需要使用互斥锁保护);M执行G的的代码时要绑定一个P,全局互斥锁和原子状态仍然保留.
把G的freelist 移到P中.
把mcache移到P中.
把stackalloc移到P中
把ncgocall/gcstats移到P中
分散运行队列,实现工作窃取.取消G在M之间的轮转.仍然使用全局互斥
移除全局锁,实现分散终止检测, 锁定操作系统线程
实现自旋代替立即阻塞/唤醒.

这项计划可能行不通，因为还有很多未经探索的细节。

潜在的进一步改进

尝试后进先出的调度, 这将改善局部性.然而,它必须提供一定程度的公平性，并优雅地处理让出cpu的goroutine。
G和栈的内存分配应该等到它即将执行时来进行, 对于一个新创建的G,只需要callerpc, fn, narg, nret 和 args 参数, 占用大约6个机器字的内.这将允许创建大量从运行到完成的goroutine，并显著降低内存开销。
G和P更好的亲和性,尝试将未阻塞的G排队到它上次运行的P.
P和M更好的亲和性,尝试在上次运行的M上执行P
创建M的限制,调度器可以很容易地每秒创建数千个M,直到操作系统拒绝创建更多线程. 在达到k*GOMAXPROCS个M之前,M可以快速创建，之后可以通过计时器添加新的M。

其他事项

GOMAXPROCS不会因为这项改进而消失