随着k8s的发展,调度器的实现也在变化,本文将从1.23版本源码角度解析k8s调度器的核心实现。

调度器总览

整个调度过程由kubernetes/pkg/scheduler/scheduler.go#L421func (sched *Scheduler) scheduleOne(ctx context.Context)完成。这个函数有两百多行,可以分为四个部分:

  1. 获取待调度Pod对象:通过sched.NextPod()从优先级队列中获取一个优先级最高的待调度Pod资源对象,该过程是阻塞模式的,当优先级队列中不存在任何Pod资源对象时,sched.config.NextPod函数处于等待状态。
  2. 调度阶段:通过sched.Algorithm.Schedule(schedulingCycleCtx, sched.Extenders, fwk, state, pod)调度函数执行预选调度算法和优选调度算法,为Pod资源对象选择一个合适的节点。
  3. 抢占阶段:当高优先级的Pod资源对象没有找到合适的节点时,调度器会通过sched.preempt函数尝试抢占低优先级的Pod资源对象的节点。
  4. 绑定阶段:当调度器为Pod资源对象选择了一个合适的节点时,通过sched.bind函数将合适的节点与Pod资源对象绑定在一起。

调度过程

进入过滤阶段前的节点数量计算

在初始化调度器的时候,kube-scheduler会对节点数量进行优化。如下图:
路径:

其中红框是调度器的一个性能优化,通过PercentageOfNodesToScore机制,在集群节点数量很多的时候,只加载指定百分比的节点,这样在大集群中,可以显著优化调度性能;这个百分比数值可以调整,默认为50,即加载一半的节点;具体的节点数量由一个不复杂的计算过程得出:

其中,minFeasibleNodesToFind为预设的参与预选的最小可用节点数,现在的值为100。见上图172行,当集群节点数量小于该值或percentageOfNodesToScore百分比大于等于100时候,直接返回所有节点。当大于100个节点的时候,使用了一个公式,adaptivePercentage = basePercentageOfNodesToScore - numAllNodes/125,翻译一下的话就是自适应百分比数=默认百分比数-所有节点数/125,见178行,默认百分比为50,假设有1000个节点,那么自适应百分比数=50-1000/125=42;180和181行则是指定了一个百分比下限minFeasibleNodesPercentageToFind,现在的值为5。即前面算出来的百分比如果小于5,则取下限5。按照这个机制,那么参与过滤的节点数=1000*42%=420个。当这个节点数小于minFeasibleNodesToFind的时候,则返回minFeasibleNodesToFind。因此,1000个节点的集群最终参与预选的是420个;同理可以计算,5000个节点的集群,参与预选的是5000*(50-5000/125)%=500个。可以看到,尽管节点数量从1000增加到了5000,但参与预选的只从420增加到了500。

过滤阶段

通过PercentageOfNodesToScore得到参与预选调度的节点数量之后,scheduler会通过podInfo := sched.NextPod()从调度队列中获取pod信息;然后进入Schedule,这是一个定义了schedule的接口,k8s实现了一个genericScheduler,如果要自定义自己的调度器,实现该接口,然后在deployment中指定用该调度器就行

type ScheduleAlgorithm interface {
	Schedule(context.Context, []framework.Extender, framework.Framework, *framework.CycleState, *v1.Pod) (scheduleResult ScheduleResult, err error)
}

进入genericScheduler后,首先就进入预选阶段findNodesThatFitPod,或者称为过滤阶段,此阶段会获得过滤之后可用的所有节点,供下一阶段使用,即feasibleNodes

findNodesThatFitPod供包含以下四部分:

  • fwk.RunPreFilterPlugins:运行过滤前的处理插件。RunPreFilterPlugins 负责运行一组框架已配置的 PreFilter 插件。如果任何插件返回除 Success 之外的任何内容,它将设置返回的*Status::code为non-success 。则调度周期中止。
  • g.evaluateNominatedNode:将某个节点单独执行过滤。如果Pod指定了某个Node上运行,这个节点很可能是唯一适合Pod的候选节点,那么会在过滤所有节点之前,检查该Node,具体条件为:len(pod.Status.NominatedNodeName) > 0 && feature.DefaultFeatureGate.Enabled(features.PreferNominatedNode),这个机制也叫“提名节点”。
  • g.findNodesThatPassFilters:将所有节点进行预选过滤。这个函数会创建一个可用node的节点feasibleNodes := make([]*v1.Node, numNodesToFind),然后通过checkNode遍历node,检查node是否符合运行Pod的条件,即运行所有的预选调度算法(如下所示),如果符合则加入feasibelNodes列表。
for _, pl := range f.filterPlugins {
		pluginStatus := f.runFilterPlugin(ctx, pl, state, pod, nodeInfo)
		if !pluginStatus.IsSuccess() {
			if !pluginStatus.IsUnschedulable() {
				// Filter plugins are not supposed to return any status other than
				// Success or Unschedulable.
				errStatus := framework.AsStatus(fmt.Errorf("running %q filter plugin: %w", pl.Name(), pluginStatus.AsError())).WithFailedPlugin(pl.Name())
				return map[string]*framework.Status{pl.Name(): errStatus}
			}
			pluginStatus.SetFailedPlugin(pl.Name())
			statuses[pl.Name()] = pluginStatus
			if !f.runAllFilters {
				// Exit early if we don't need to run all filters.
				return statuses
			}
		}
	}
  • findNodesThatPassExtenders:将上一步经过预选的Node再通过扩展过滤器过滤一遍。这个其实是k8s留给用户的自定义过滤器。它遍历所有的extender来确定是否关心对应的资源,如果关心就会调用Filter接口来进行远程调用feasibleList, failedMap, failedAndUnresolvableMap, err := extender.Filter(pod, feasibleNodes),并将筛选结果传递给下一个extender,逐步缩小筛选集合。远程调用是一个http的实现,如下图:

    至此,预选阶段结束。整个预选过程逻辑上很自然,预处理->过滤->用户自定义过滤->结束。
    在预处理阶段(PreFilterPlugin),官方主要定义了:
  1. InterPodAffinity: 实现Pod之间的亲和性和反亲和性,InterPodAffinity实现了PreFilterExtensions,因为抢占调度的Pod可能与当前的Pod具有亲和性或者反亲和性;
  2. NodePorts: 检查Pod请求的端口在Node是否可用,NodePorts未实现PreFilterExtensions;
  3. NodeResourcesFit: 检查Node是否拥有Pod请求的所有资源,NodeResourcesFit未实现PreFilterEtensions;
  4. PodTopologySpread: 实现Pod拓扑分布;
  5. ServiceAffinity: 检查属于某个服务(Service)的Pod与配置的标签所定义的Node集合是否适配,这个插件还支持将属于某个服务的Pod分散到各个Node,ServiceAffinity实现了PreFilterExtensions接口;
  6. VolumeBinding: 检查Node是否有请求的卷,是否可以绑定请求的卷,VolumeBinding未实现PreFilterExtensions接口;
    过滤插件在早期版本叫做预选算法,但在较新的版本已经删除了/pkg/scheduler/algorithem这个包,因为用过滤更贴切一点。在这个目录下可以找到所有的插件实现:

    基本上通过名字就知道是做什么的,不赘述,如
  7. InterPodAffinity: 实现Pod之间的亲和性和反亲和性;
  8. NodeAffinity: 实现了Node选择器和节点亲和性
  9. NodeLabel: 根据配置的标签过滤Node;
  10. NodeName: 检查Pod指定的Node名称与当前Node是否匹配;
  11. NodePorts: 检查Pod请求的端口在Node是否可用;
    ...

优选阶段

预选的结果是true或false,意味着一个节点要么满足Pod的运行要求,要么不满足;得到众多满足的节点后,最终决定Pod调度到哪个节点。

在调度器中,优选的过程由prioritizeNodes负责,它会返回一个带分数的节点列表,定义如下:

// NodeScore is a struct with node name and score.
type NodeScore struct {
	Name  string
	Score int64
}

最终由selectHost返回一个node名字,作为最终的ScheduleResult.下面进行具体分析。
prioritizeNodes分为三部分,运行打分前处理插件,运行所有的打分插件,将所有分数相加

优选阶段最主要的就是运行各种打分插件,kube-scheduler会调用ScorePlugin对通过FilterPlugin的Node评分,所有ScorePlugin的评分都有一个明确的整数范围,比如[0, 100],这个过程称之为标准化评分。在标准化评分之后,kube-scheduler将根据配置的插件权重合并所有插件的Node评分得出Node的最终评分。根据Node的最终评分对Node进行排序,得分最高者就是最合适Pod的Node。

type ScorePlugin interface {
    Plugin
    // 计算节点的评分,此时需要注意的是参数Node名字,而不是Node对象。
    // 如果实现了PreScorePlugin就从CycleState获取状态, 如果没实现,调度框架在创建插件的时候传入了句柄,可以获取指定的Node。
    // 返回值的评分是一个64位整数,是一个由插件自定义实现取值范围的分数。
    Score(ctx context.Context, state *CycleState, p *v1.Pod, nodeName string) (int64, *Status)
    // 返回ScoreExtensions接口,此类设计与PreFilterPlugin相似
    ScoreExtensions() ScoreExtensions
}

// ScorePlugin的扩展接口
type ScoreExtensions interface {
    // ScorePlugin().Score()返回的分数没有任何约束,但是多个ScorePlugin之间需要标准化分数范围,否则无法合并分数。
    // 比如ScorePluginA的分数范围是[0, 10],ScorePluginB的分数范围是[0, 100],那么ScorePluginA的分数再高对于ScorePluginB的影响也是非常有限的。
    NormalizeScore(ctx context.Context, state *CycleState, p *v1.Pod, scores NodeScoreList) *Status
}

实现该接口的插件有:

  1. ImageLocality: 选择已经存在Pod运行所需容器镜像的Node,这样可以省去下载镜像的过程,对于镜像非常大的容器是一个非常有价值的特性,因为启动时间可以节约几秒甚至是几十秒;
  2. InterPodAffinity: 实现Pod之间的亲和性和反亲和性;
  3. NodeAffinity: 实现了Node选择器和节点亲和性
  4. NodeLabel: 根据配置的标签过滤Node;
  5. NodePreferAvoidPods: 基于Node的注解 scheduler.alpha.kubernetes.io/preferAvoidPods打分;
  6. NodeResourcesBalancedAllocation: 调度Pod时,选择资源分配更为均匀的Node;
  7. NodeResourcesLeastAllocation: 调度Pod时,选择资源分配较少的Node;
  8. NodeResourcesMostAllocation: 调度Pod时,选择资源分配较多的Node;
  9. RequestedToCapacityRatio: 根据已分配资源的配置函数选择偏爱Node;
  10. PodTopologySpread: 实现Pod拓扑分布;
  11. SelectorSpread: 对于属于Services、ReplicaSets和StatefulSets的Pod,偏好跨多节点部署;
  12. ServiceAffinity: 检查属于某个服务(Service)的Pod与配置的标签所定义的Node集合是否适配,这个插件还支持将属于某个服务的Pod分散到各个Node;
  13. TaintToleration: 实现了污点和容忍度;

打分之后通过selectHost选择最终pod将被调度的节点:

func (g *genericScheduler) selectHost(nodeScoreList framework.NodeScoreList) (string, error) {
	if len(nodeScoreList) == 0 {
		return "", fmt.Errorf("empty priorityList")
	}
	maxScore := nodeScoreList[0].Score
	selected := nodeScoreList[0].Name
	cntOfMaxScore := 1
	for _, ns := range nodeScoreList[1:] {
		if ns.Score > maxScore {
			maxScore = ns.Score
			selected = ns.Name
			cntOfMaxScore = 1
		} else if ns.Score == maxScore {
			cntOfMaxScore++
			if rand.Intn(cntOfMaxScore) == 0 {
				// Replace the candidate with probability of 1/cntOfMaxScore
				selected = ns.Name
			}
		}
	}
	return selected, nil
}

至此,优选阶段结束。

总结

总结,k8s定义了调度的接口,并实现了genericScheduler(也是k8s中唯一的官方调度器)以及众多的插件,这层抽象其实为开发人员自定义调度器提供了很大的便利。往小的说,各类插件以及扩展插件也提供了丰富的细粒度控制。当然,最简单的还是去根据实际需要调整优选的打分逻辑,使得Pod的调度满足生产需要。