Kubernetes学习——调度策略

Veröffentlicht am

In Kubernetes, scheduling refers to making sure that Pods are matched to Nodes so that Kubelet can run them.

首先学习Linux调度器的演化，然后Go语言调度器实现的发展，最后再看K8S调度器的演进以及如何自定义调度器。

1. Linux系统调度器演进

最初的进程调度

仅有sched.h sched.c两个文件构成，只有几十行代码就负责了操作系统进程的调度。所有的调度进程都存储在上限为64的数组中，调度器能处理的进程上限只有64.

先唤醒获得信号的可中断进程，从队列倒序查找计数器counter最大的可执行进程，counter是进程能够占用的时间切片数量：

  • 如果最大的counter > 0，调用汇编实现的switch_to切换进程
  • 如果最大的counter = 0，所有进程的可执行时间都为0，那么所有进程都会获得新的时间切片

Linux系统计时器每隔10ms触发一次do_timer将当前运行进程的counter-1，当前进程计数器归0时重新触发调度。

O(n)调度器

Linux v2.4-2.6版本使用的，在最坏情况下会遍历所有任务，所以调度时间复杂度为O(n)。调度器将CPU时间分割成不同的时期Epoch，即每个任务能使用的时间切片。

其实现比最初的复杂很多，在schedule函数中遍历运行队列的所有任务，并调用goodness函数计算它们的权重，获得下一个运行的进程。

默认情况下每个任务在一个周期内都会分配200ms左右的时间片，当系统包含100个进程时，同一个进程被运行两次的间隔是21s，严重影响了可用性。每轮调度完成后就会陷入没有任务需要调度的情况，对于需要实时交互的场景不适合。

O(1)调度器

Linux在v2.6.0-v2.6.22用了4年该调度器，支持在常数时间内完成调度。调度代码从2100行增加到了5000行。

  • 支持O(1)时间复杂度， 通过运行队列runqueue和优先数组prio_array，每个运行队列都持有两个优先数组，分别存储活跃和过期的进程数组。
  • 支持对称多处理器SMP扩展性，引入本地队列解决降低多处理器下锁的粒度和冲突的可能性。引入工作窃取保证多个运行队列任务的平衡
  • 优化了对称多处理器的亲和性

完全公平调度器

CFS是在v2.6.23被合并进内核的调度器，目的是最大化CPU利用率和交互性能。

  • 调度器查找运行队列中受到不公平待遇的进程，并为其分配计算资源，分配的计算资源是与其他资源运行时间的差值+最小能够运行的时间单位；
  • 进程运行结束后发现队列中又有其他进程受到不公平待遇，调度器又运行新的进程
  • …循环往复保证各个进程的运行时间差不会大于最小运行时间单位

运行队列通过红黑树来替代之前的链表，增删改查最坏时间复杂度为O(logN)，树的最左侧节点运行时间最短，也就是下个待运行的进程。
调度过程和O(1)类似，只是增加了可选的工作窃取机制并改变了底层数据结构。通过调度类实现不同任务类型的不同调度策略。

2. Go语言调度器的演进

Go语言高并发支持依靠的就是运行时的调度器。

单线程调度器

0.x版本调度器只包含表示Goroutine的G和表示线程的M两种结构，全局只有一个线程。 此时调度器还是由C语言实现，调度函数只包含40行代码。

获取调度器的全局锁；调用gosave保存栈寄存器和pc；调用nextgandunlock获取下一个需要运行的goroutine并解锁调度器；修改全局线程m上要执行的G，调用gogo函数运行最新的G。

多线程调度器

在1.0版本正式支持了多线程的调度器，实现了从不可用到可用的跨越。调度函数包含70行代码，引入了GOMAXPROCS变量帮助控制程序中的最大处理器数，即活跃线程数。

多线程调度器的主要问题是调度时锁竞争会严重浪费资源，14%的时间都花费在futex上。因此该调度器有以下问题需要解决：

  • 调度器和锁是全局资源，所有调度状态中心化存储，竞争严重
  • 线程需要经常互相传递可运行的G，引入大量延迟
  • 每个线程都需要处理内存缓存，导致大量的内存占用并影响数据局部性
  • 系统调用频繁阻塞和解除阻塞正在运行的线程，增加了额外开销

任务窃取调度器

在GM模型中引入P，增加中间层；在处理器P的基础上实现基于工作窃取的调度器。

  • 如果当前运行时在等待垃圾回收，调用gcstopm函数
  • 调用runqget和findrunnable函数从本地或全局的运行队列中获取待执行的G
  • 调用execute在当前M上运行该G

处理器P持有一个由可运行的G组成的运行队列runq，并且反向持有一个线程M。

存在的问题：1)某些G可以长时间占用线程，造成饥饿问题；2)垃圾回收需要暂停整个程序

抢占式调度器

1.1版本的调度器不支持抢占，程序只能依靠G主动让出CPU资源才能触发调度。因此在1.2版本中引入了基于协作的抢占调度，能缓解上述问题。但是存在一些无法被抢占的边缘情况，如for循环或垃圾回收STW，这些问题直到1.14基于信号的抢占式调度才解决。

基于协作抢占

编译器会在调用函数前插入morestack；Go语言运行时会在垃圾回收暂停程序、系统监控发现G运行超过10ms时发出抢占请求StackPreempt；当发生函数调用时，可能会执行编译器插入的morestack函数，它调用的newstack会检查G的stackguard0字段是否为StackPreempt；如果是则触发抢占让出该线程；

这里的抢占是通过编译器插入函数实现，需要函数调用作为入口才能触发，因此是一种协作式的抢占式调度。

基于信号抢占

程序启动时，在sighandler函数中注册SIGURG信号的处理函数doSigPreempt；在触发垃圾回收的栈扫描时调动suspendG挂起G，该函数会将_Grunning状态的G标记成可以被抢占，即将preemptStop设置为true，然后调用preemptM触发抢占；preemptM会调用singnalM向线程发送SIGURG信号；系统会中断正在运行的线程并执行doSigPreempt函数；该函数会处理抢占信号，获取当前SP和PC寄存器并调用sigctxt.pushCall；pushCall会修改寄存器并在程序回到用户态时执行asyncPreempt->asyncPreempt2->preemptPark；后者会将当前G状态改为_GPreempted并调用schedule函数让当前函数休眠并让出线程，调度器选择其他G执行。

选择SIGURG的原因：1)信号需要被调试器透传 2)信号不会被内部libc库使用并拦截 3)信号可以随意出现并不触发任何后果 4)需要处理多平台不通信号

NUMA调度器

目前只是提案，因为过于复杂且目前调度性能足够优异，因此暂时没有实现。其原理是通过拆分全局资源，让各个处理器能够就近获取，减少锁竞争并增加数据局部性。堆栈、全局运行队列、线程池会按照NUMA节点分区，网络轮询器和计时器由单独处理器持有。

3. Kubernetes调度器演进

基于谓词和优先级的调度器

Predicates和Priorities调度器是从v1.0.0发布时就存在的模式，v1.14.0最后实现和最初设计也没太多区别。不过其中引入了多次改进：

  • 调度器扩展，v1.2.0，通过外部调度器扩展的方式改变调度器策略
  • Map-Reduce优先级算法，v1.5.0，为调度器优先级算法支持MapReduce计算方式，引入可并行的Map阶段优化调度器计算性能
  • 调度器迁移，v1.10.0,从plugin/pkg/scheduler -> pkg/scheduler，kube-scheduler成为对外直接提供的可执行文件

谓词算法使用FitPredicate类型，优先级算法使用PriorityMapFunction和PriorityReduceFunction两种类型。

  • 从NodeLister中获取当前系统中存在的全部节点；
  • 调用genericScheduler.findNodesThatFit方法执行全部的谓词过滤节点
    • 根据传入pod和node对节点进行过滤，过滤掉端口号冲突，资源不足的节点
    • 调用所有调度器扩展的Filter方法辅助过滤
  • 调用PrioritizeNodes函数为所有节点打分
    • 以Pod和Node作为参数并执行同一优先级的PriorityMapFunction
    • 以Pod和优先级返回的NOde到分数的映射为参数调用PriorityReduceFunction函数
    • 调用所有调度器扩展的Prioritize方法
    • 将所有分数按照权重相加后返回从Node到分数的映射
  • 调用genericScheduler.selectHost方法选择得分最高的节点

    基于调度框架的调度器

    2018年提出的最新调度器设计，明确了K8S中各个调度阶段，提供设计良好的基于插件的接口。调度框架认为K8S目前存在Scheduling和Binding两个循环：
  • 调度循环在多个Node中为Pod选取最合适的Node
  • 绑定循环将调度决策应用到集群中，包括绑定pod和node，绑定持久存储等

除了两大循环外，调度器还包含QueueSort、PreFilter、Filter、PostFilter、Score、Reserve、Permit、PreBind、Bind、PostBind和Unreserve11个扩展点。

通过调度器中的Scheduler.schedulerOne方法作为入口分析其实现：

  • 调度阶段
    • 调用内部优先队列的MakeNextPodFunc从队列中获取下一个等待调度的Pod，用于维护等待Pod的队列会执行QueueSort插件
    • 调用genericScheduler.Schedule函数选择节点，该过程会执行PreFilter，Filter，PostFilter，Score四个扩展点的插件
    • 调用framework.RunReservePlugins函数运行Reserve插件，用于保留资源并进入绑定阶段。如果运行失败会调用Unreserve插件

因为每一次调度策略都会改变上下文，所以该阶段需要串行执行。

  • 绑定阶段
    • 启动一个G并调用framework.RunPermitPlugin异步运行Permit插件，该阶段可以实现批调度
    • 调用Scheduler.bindVolume将卷先绑定在Node上
    • 调用Scheduler.bind函数将Pod绑定到Node上完成调度，绑定过程会执行PreBind、Bind、PostBind三个扩展点的插件

自定义K8S调度器

自定义K8S调度器
默认情况下，kube-scheduler提供的默认调度器能满足绝大多数需求，在实际项目中，因为开发者相比K8S更了解自己的应用，需要定制化调度。

kube-scheduler是一个独立的二进制程序，启动之后会一直监听API Server，获取到PodSpec.NodeName为空的pod，对每个pod创建一个binding。看起来流程非常简单，但在实际生产环境中，需要考虑：

  • 如何保证全部的节点调度公平性？并不是所有节点资源配置都相同
  • 如何保证每个节点都能被分配资源？
  • 集群资源如何能够被高效利用？
  • 集群资源如何能够被最大化利用？
  • 如何保证Pod调度的性能和效率？
  • 用户是否可以根据自己的实际需求定制自己的调度策略？

考虑到实际环境中的复杂情况，K8S调度器采用插件化的形式实现，可以方便用户进行定制或者二次开发。

  • 直接clone kube-scheduler源码修改重新编译后运行， 不推荐，因为需要花费额外精力来和上游的调度程序保持一致；
  • 和默认的调度程序一起运行独立的调度程序，默认的调度器和我们自定义的调度器可以通过pod的spec.schedulerName来覆盖各自的pod。但是多个调度器同时存在比较麻烦，比如多个调度器将pod调度到同一节点时，节点资源如果不能同时满足的话会出问题。而且维护一个高质量的自定义调度程序也不容易，需要全面了解默认的调度程序，k8s架构以及各种kubernetes api对象的关系和限制等。
  • 调度器扩展程序，可以和上游调度程序兼容，本质就是一个可配置的webhook，包含过滤器和优先级两个端点。1.16中废弃
  • 调度框架，1.15版本之后引入可插拔架构的调度框架，使得定制调度器变得容易。调度框架向现有调度器添加了一组插件化的API，该API在保持调度程序核心简单且易于维护的同时，使得大部分调度功能以插件的形式存在。