kube-apiserver调度器核心实现

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

调度器总览

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

获取待调度Pod对象：通过sched.NextPod()从优先级队列中获取一个优先级最高的待调度Pod资源对象，该过程是阻塞模式的，当优先级队列中不存在任何Pod资源对象时，sched.config.NextPod函数处于等待状态。
调度阶段：通过sched.Algorithm.Schedule(schedulingCycleCtx, sched.Extenders, fwk, state, pod)调度函数执行预选调度算法和优选调度算法，为Pod资源对象选择一个合适的节点。
抢占阶段：当高优先级的Pod资源对象没有找到合适的节点时，调度器会通过sched.preempt函数尝试抢占低优先级的Pod资源对象的节点。
绑定阶段：当调度器为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)，官方主要定义了：

InterPodAffinity: 实现Pod之间的亲和性和反亲和性，InterPodAffinity实现了PreFilterExtensions，因为抢占调度的Pod可能与当前的Pod具有亲和性或者反亲和性；
NodePorts: 检查Pod请求的端口在Node是否可用，NodePorts未实现PreFilterExtensions;
NodeResourcesFit: 检查Node是否拥有Pod请求的所有资源，NodeResourcesFit未实现PreFilterEtensions;
PodTopologySpread: 实现Pod拓扑分布；
ServiceAffinity: 检查属于某个服务(Service)的Pod与配置的标签所定义的Node集合是否适配，这个插件还支持将属于某个服务的Pod分散到各个Node，ServiceAffinity实现了PreFilterExtensions接口；
VolumeBinding: 检查Node是否有请求的卷，是否可以绑定请求的卷，VolumeBinding未实现PreFilterExtensions接口；
过滤插件在早期版本叫做预选算法，但在较新的版本已经删除了/pkg/scheduler/algorithem这个包，因为用过滤更贴切一点。在这个目录下可以找到所有的插件实现：

基本上通过名字就知道是做什么的,不赘述，如
InterPodAffinity: 实现Pod之间的亲和性和反亲和性；
NodeAffinity: 实现了Node选择器和节点亲和性
NodeLabel: 根据配置的标签过滤Node；
NodeName: 检查Pod指定的Node名称与当前Node是否匹配；
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
}

实现该接口的插件有：

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

Mr.Shentu