• kubernetes调度器概述
• kubernetes源码分析
  • 命令行入口
  • NewConfigFactory
  • CreateFromKeys
  • scheduler框架
  • generic scheduler实例
• predicates算法
• priorities算法

kubernetes调度器概述

kubernetes调度器kube-scheduler在集群中体现为一个kube-scheduler进程。kube-scheduler的主要任务是将k8s集群上新创建的的pod，丢到合适的node上去。具体的，kube-scheduler监听apiserver的/api/pod/，当发现集群中有未得到调度的pod(即PodSpec.NodeName为空)时，会查询集群各node的信息，经过Predicates(过滤)、Priorities(优选器)，得到最适合该pod运行的node后，再向apiserver发送请求，将该容器绑定到选中的node上。

    +------------Schedulable nodes----------------+
    | +--------+    +--------+      +--------+    |
    | | node 1 |    | node 2 |      | node 3 |    |
    | +--------+    +--------+      +--------+    |
    +-------------------+-------------------------+
                        |
                        v
    +-------------------+-------------------------+
    Pred. filters: node 3 doesn't have enough resource
    +-------------------+-------------------------+
                        |
                        v
    +-------------remaining nodes:----------------+
    |   +--------+                 +--------+     |
    |   | node 1 |                 | node 2 |     |
    |   +--------+                 +--------+     |
    +-------------------+-------------------------+
                        |
                        v
    +-------------------+-------------------------+
    Priority function:    node 1: p=2
                          node 2: p=5
    +-------------------+-------------------------+
                        |
                        v
            select max{node priority} = node 2

新版本kube-scheduler通常为容器形式(或多个容器组成集群)。

kubernetes源码分析

以下分析基于1.5.4版本的k8s源码。kube-scheduler是k8s的插件，其代码均在plugin目录里。几个主要的文件：

• plugin/cmd/kube-scheduler/scheduler.go，调度器进程的入口
• plugin/cmd/kube-scheduler/app/server.go，调度器出厂、上线
• plugin/pkg/scheduler/factory/factory.go，工厂:1, NewConfigFactory先开厂，CreateFromKeys出货；2, 启动监听apiserver，将新创建的Pod加入到PodQueue
• plugin/pkg/scheduler/scheduler.go，调度框架：从PodQueue获取下一个待调度的Pod，调用调度算法选择Pod的驸马Node，并异步向apiserver发送请求，将Pod绑定到对应的Node。
• plugin/pkg/scheduler/generic_scheduler.go，通用调度算法，主要实现了Schedule函数，完成了Predicates/Priorities过程
• plugin/pkg/scheduler/algorithmprovider/defaults/defaults.go，通用调度算法默认采用了哪些Predicates/Priorities策略(菜谱)
• plugin/pkg/scheduler/algorithm/predicates，当前支持的所有Predicates过滤器(食材)
• plugin/pkg/scheduler/algorithm/priorities，当前支持的所有Priorities优选器(食材)

由于k8s代码变化比较快，另外代码贴多了读起来也很累，我尽量减少贴代码，感兴趣直接去查k8s源码就好。

命令行入口

在命令行main入口之前，会先初始化3个Map:

• fitPredicateMap：包含了所有支持的Predicate函数，类型为map[string]FitPredicateFactory
• priorityFunctionMap：包含了所有支持的Priority函数，类型为[string]PriorityConfigFactory
• algorithmProviderMap：包含了所有支持的调度算法，类型为map[string]AlgorithmProviderConfig。当前只有DefaultProvider和ClusterAutoscalerProvider。

plugin/cmd/kube-scheduler/scheduler.go会在main()之前调用init函数，在init中初始化上述3个Map，供后续Factory使用。

命令行总入口使用pflag包解析参数后，就进入到server.go去~~浪~~Run了:先创建ConfigFactory，然后根据入参，生成config，之后根据config再生成调度器实例，并启动调度器实例。

createConfig中，若用户未指定policy，则走CreateFromProvider，即根据用户指定的algorithm-provider参数(默认为DefaultProvider)去绘制。否则走CreateFromConfig根据用户指定的policy文件去解析policy。

NewConfigFactory

NewConfigFactory初始化ConfigFactory，依次做了几件事：

1. 创建schedulerCache，用以缓存Pod和Node。
2. 创建PodQueue，FIFO，scheduler每次从PodQueue上来获取待调度的Pod
3. 创建ScheduledPodLister、NodeLister、PVLister、PVCLister、pvcPopulator、ServiceLister、ControllerLister、ReplicaSetLister等Informer
4. 创建chan stopEverything

ConfigFactory的各个lister用来获取kubernetes的资源信息，用来提高scheduler的查询速度，避免每次都去apiserver查询，kube-scheduler使用schedulerCache来保存Pod和Node的缓存信息。

NewConfigFactory只会做初始化(开厂)，工厂真正开始生产是在CreateFromKeys进行的(Run起来!)。

CreateFromKeys

CreateFromKeys会在Run中启动上面初始化的LIST&WATCH。LW使用的Informer会去ListWatch apiPod{}，并反射调用对应HandlerFuncs。

scheduler框架

虽然1.5.4版本的scheduler只有generic_scheduler，但为了将来的扩展，还是抽象了一个Scheduler出来。scheduler会一直在循环，依次如下：

1. 从PodQueue上获取下一个待调度的pod
2. 调用Generic_scheduler(或其他实现了Scheduler的调度器)在NodeLister上寻找适合运行该pod的node
3. 标记该pod为已调度状态(assume)
4. 异步向api server绑定pod到选中的node上

// Run begins watching and scheduling. It starts a goroutine and returns immediately.
func (s *Scheduler) Run() {
	go wait.Until(s.scheduleOne, 0, s.config.StopEverything)
}

func (s *Scheduler) scheduleOne() {
	pod := s.config.NextPod()

	dest, err := s.config.Algorithm.Schedule(pod, s.config.NodeLister)

	assumed := *pod
	assumed.Spec.NodeName = dest
	if err := s.config.SchedulerCache.AssumePod(&assumed); err != nil {
		return
	}

	go func() {
		b := &api.Binding{
			ObjectMeta: api.ObjectMeta{Namespace: pod.Namespace, Name: pod.Name},
			Target: api.ObjectReference{
				Kind: "Node",
				Name: dest,
			},
		}
		err := s.config.Binder.Bind(b)
	}()
}

可以看到，调度过程虽然异步调用apiserver，但node的选择还是串行的，当作为PAAS时，待调度的Pod过多，可能会成瓶颈。

generic scheduler实例

Generic_scheduler是一个实现了ScheduleAlgorithm interface 的调度器。其调度的步骤依次如下。

type HostPriority struct {
	// Name of the host
	Host string `json:"host"`
	// Score associated with the host
	Score int `json:"score"`
}
func (g *genericScheduler) Schedule(pod *api.Pod, nodeLister algorithm.NodeLister) (string, error) {
	nodes, err := nodeLister.List()

	filteredNodes, failedPredicateMap, err := findNodesThatFit(pod, g.cachedNodeInfoMap, nodes, g.predicates, g.extenders, g.predicateMetaProducer)

	metaPrioritiesInterface := g.priorityMetaProducer(pod, g.cachedNodeInfoMap)
	priorityList, err := PrioritizeNodes(pod, g.cachedNodeInfoMap, metaPrioritiesInterface, g.prioritizers, filteredNodes, g.extenders)

	return g.selectHost(priorityList)
}

1. Predicates(过滤)：findNodesThatFit中并发16 goroutine(如果node数不到16则并发数为node数)，在每个goroutine中依次判断pod是否能够运行在该node上(即是否能通过predicateFuncs)，不通过则直接返回。为了防止并发写filtered数组时出现冲突，数组index递增使用了atomic.AddInt32(&filteredLen, 1)
2. Priority(优先级)：PrioritizeNodes中并发16 goroutine(如果node数不到16则并发数为node数)，在每个goroutine中依次计算若pod运行在该node上的得分，结果记录到results(type为[]schedulerapi.HostPriorityList，长度为优先级算法的个数)；然后计算node在各优先级算法上的加权和，返回HostPriorityList(即[]HostPriority，长度为node个数)；
3. selectHost(最终选)：Priority中为各个node做了打分，但最终scheduler只会选择一个。selectHost会将第二步得到的HostPriorityList做一个排序，选出得分最高的节点。如果仍然有多个节点得分一致，则走round-robin选择一个。不过这里可能是个bug：由于lastNodeIndex是属于Generic_scheduler的，所以有可能针对某一个类型的pod，可能由于中间夹杂了其他类型的pod影响了lastNodeIndex的值，导致不能完全按照round-robin来选择node。

优先级这里稍微复杂一点，博主cizixs画了个图，借用下。

predicates算法

1.5.4版本支持的部分过滤算法。

• NoDiskConflict: 评估是否存在volume冲突。如果该volume已经mount过了，k8s可能会不允许重复mount(取决于volume类型)
• NoVolumeZoneConflict: 评估该节点上是否存在pod请求的volume
• PodFitsResources: 检查节点剩余资源(CPU内存)是否能满足pod的需求。剩余资源=总容量-所有Pod请求的资源。
• PodFitsHostPorts: 检查Pod请求的HostPort在该node上是否已经用过了
• HostName: 根据Pod指定的NodeName过滤不满足的node
• MatchNodeSelector: 判断是否满足Pod设置的NodeSelector
• CheckNodeMemoryPressure: 检查Pod是否可以调度到报告内存压力的节点
• CheckNodeDiskPressure: 检查Pod是否可以调度到报告硬盘压力的节点

priorities算法

1.5.4版本支持的部分优先级算法。

• LeastRequestedPriority: 最低请求优先级，即node使用率越低，得分越高。注意使用率的计算不是根据node当前运行情况，而是根据运行在该node的所有Pod请求的结果来的。所以，Pod应该准确的指明其需要的资源(是胖子就要说出来)，否则对k8s的调度会很不友好，特别是如果没有设置limit的话，可能会出现某个节点上碰巧全是胖子。
• BalancedResourceAllocation: 资源平衡分配，即CPU/内存配比合适的node得分更高
• SelectorSpreadPriority: 尽量将同一rc/replica的多个pod分配到不同的node上
• CalculateAntiAffinityPriority: 尽量将同一service下的多个相同label的pod分配到不同的node
• ImageLocalityPriority: image本地优先，node上如果已经存在pod需要的镜像，并且镜像越大，得分越高，从而减少Pod拉取镜像的开销(时间)
• NodeAffinityPriority: Node Affinity

---

ref:

• kubelet scheduler 源码分析：调度器的工作原理
• Advanced Scheduling in Kubernetes

---