K8s 源码剖析及debug实战之 Kube-Scheduler（四）：预选算法详解

---

0. 引言

欢迎关注本专栏，本专栏主要从 K8s 源码出发，深入理解 K8s 一些组件底层的代码逻辑，同时借助 debug Minikube 来进一步了解 K8s 底层的代码运行逻辑细节，帮助我们更好的了解不为人知的运行机制，让自己学会如何调试源码，玩转 K8s。

本专栏适合于运维、开发以及希望精进 K8s 细节的同学。同时本人水平有限，尽量将本人理解的内容最大程度的展现给大家～

前情提要：
《K8s 源码剖析及debug实战（一）：Minikube 安装及源码准备》
《K8s 源码剖析及debug实战（二）：debug K8s 源码》
《K8s 源码剖析及debug实战之 Kube-Scheduler（一）：启动流程详解》
《K8s 源码剖析及debug实战之 Kube-Scheduler（二）：终于找到了调度算法的代码入口》
《K8s 源码剖析及debug实战之 Kube-Scheduler（三）：debug 到预选算法门口了》

文中采用的 K8s 版本是 v1.16。紧接上篇，本文主要介绍 K8s 的 Kube-Scheduler 源码的预选算法的具体逻辑。

1. 回顾

上节我们说到，调度里最关键的是 predicate 和 priority 这两个步骤，下面是进一步省略后的主要的调度逻辑：

func (g *genericScheduler) Schedule(pod *v1.Pod, pluginContext *framework.PluginContext) (result ScheduleResult, err error) {
	
	...
	// 4. 重要！！！关键方法，调度预选，predicate过滤不符合的node
	filteredNodes, failedPredicateMap, filteredNodesStatuses, err := g.findNodesThatFit(pluginContext, pod)

	...
	// 8. 重要！！！上面如果找到多个node，那需要按照priority策略筛选
	priorityList, err := PrioritizeNodes(pod, g.nodeInfoSnapshot.NodeInfoMap, metaPrioritiesInterface, g.prioritizers, filteredNodes, g.extenders, g.framework, pluginContext)

	// 9. 好了，最终选一个node吧！
	host, err := g.selectHost(priorityList)
}

上节我们分析了 predicate 的 findNodesThatFit 方法的大体流程，如下：

func (g *genericScheduler) podFitsOnNode(pluginContext *framework.PluginContext, pod *v1.Pod, meta predicates.PredicateMetadata, info *schedulernodeinfo.NodeInfo, predicateFuncs map[string]predicates.FitPredicate, queue internalqueue.SchedulingQueue, alwaysCheckAllPredicates bool) (bool, []predicates.PredicateFailureReason, *framework.Status, error) {
    // 执行两次
	for i := 0; i < 2; i++ {
		if i == 0 {
			// 第一次，特殊处理
			podsAdded, metaToUse, nodeInfoToUse = addNominatedPods(pod, meta, info, queue)
		} else if !podsAdded || len(failedPredicates) != 0 {
			break
		}
		// 按照预设的predicate表依次执行
		for _, predicateKey := range predicates.Ordering() {
			// 真正执行 predicate 
			if predicate, exist := predicateFuncs[predicateKey]; exist {
				fit, reasons, err = predicate(pod, metaToUse, nodeInfoToUse)
			}
		}
		...
	}
}

这篇文章我们来具体分析 podFitsOnNode 的逻辑

2. podFitsOnNode 为什么执行两次预选

看代码的时候，可以看到有一个 for 循环，循环里执行了两次，那么为什么要执行两次呢？先来看下源码里的注解：

	// We run predicates twice in some cases. If the node has greater or equal priority
	// nominated pods, we run them when those pods are added to meta and nodeInfo.
	// If all predicates succeed in this pass, we run them again when these
	// nominated pods are not added. This second pass is necessary because some
	// predicates such as inter-pod affinity may not pass without the nominated pods.
	// If there are no nominated pods for the node or if the first run of the
	// predicates fail, we don't run the second pass.
	// We consider only equal or higher priority pods in the first pass, because
	// those are the current "pod" must yield to them and not take a space opened
	// for running them. It is ok if the current "pod" take resources freed for
	// lower priority pods.
	// Requiring that the new pod is schedulable in both circumstances ensures that
	// we are making a conservative decision: predicates like resources and inter-pod
	// anti-affinity are more likely to fail when the nominated pods are treated
	// as running, while predicates like pod affinity are more likely to fail when
	// the nominated pods are treated as not running. We can't just assume the
	// nominated pods are running because they are not running right now and in fact,
	// they may end up getting scheduled to a different node.
	for i := 0; i < 2; i++ {...}

好了，仔细看上面的注解之后，我们可以得出结论，在 Kubernetes 调度器的执行流程中，调度器会对这些预选函数执行两次的原因在于：

1. 考虑已提名（nominated）Pod的影响：当集群中存在优先级较高的待调度但尚未运行的 Pod，并且它们被提名到某个节点上时，调度器需要考虑到这些“假定”已经运行在节点上的高优先级 Pod 对当前待调度 Pod 的影响。第一次预选会包含这些已提名的 Pod 信息，以模拟如果它们实际运行时的情况。

2. 确保调度决策的保守性和正确性：由于一些预选条件（如资源限制和 Pod 间的亲和性/反亲和性）在不同的场景下可能有不同的结果，比如：

   • 当已提名 Pods 被视为正在运行时，资源限制检查和 Pod 反亲和性检查更有可能失败。
   • 当已提名 Pods 被视为未运行时，Pod 亲和性检查则可能更容易失败。

因此，调度器在这两次的预选差异在于：
3. 第一次预选时，包含了所有优先级相同或更高的已提名 Pods，如果此时预选成功，还需进行第二次预选
4. 第二次预选时，不包含这些已提名的 Pods，再次检查待调度 Pod 是否仍满足调度条件。

这样可以保证无论已提名的 Pod 最终是否会被调度到该节点上，当前待调度的 Pod 都能够适应两种情况下的调度环境。只有在这两次预选都通过的情况下，调度器才会将 Pod 分配给该节点。

3. 预选算法有哪些

实现在 pkg/scheduler/algorithm/predicates/predicates.go 文件下

var (
	predicatesOrdering = []string{CheckNodeConditionPred, CheckNodeUnschedulablePred,
		GeneralPred, HostNamePred, PodFitsHostPortsPred,
		MatchNodeSelectorPred, PodFitsResourcesPred, NoDiskConflictPred,
		PodToleratesNodeTaintsPred, PodToleratesNodeNoExecuteTaintsPred, CheckNodeLabelPresencePred,
		CheckServiceAffinityPred, MaxEBSVolumeCountPred, MaxGCEPDVolumeCountPred, MaxCSIVolumeCountPred,
		MaxAzureDiskVolumeCountPred, MaxCinderVolumeCountPred, CheckVolumeBindingPred, NoVolumeZoneConflictPred,
		CheckNodeMemoryPressurePred, CheckNodePIDPressurePred, CheckNodeDiskPressurePred, EvenPodsSpreadPred, MatchInterPodAffinityPred}
)

...

func CheckNodeMemoryPressurePredicate(pod *v1.Pod, meta PredicateMetadata, nodeInfo *schedulernodeinfo.NodeInfo) (bool, []PredicateFailureReason, error) {
	...
}

// CheckNodeDiskPressurePredicate checks if a pod can be scheduled on a node
// reporting disk pressure condition.
func CheckNodeDiskPressurePredicate(pod *v1.Pod, meta PredicateMetadata, nodeInfo *schedulernodeinfo.NodeInfo) (bool, []PredicateFailureReason, error) {
	...
}

// CheckNodePIDPressurePredicate checks if a pod can be scheduled on a node
// reporting pid pressure condition.
func CheckNodePIDPressurePredicate(pod *v1.Pod, meta PredicateMetadata, nodeInfo *schedulernodeinfo.NodeInfo) (bool, []PredicateFailureReason, error) {
	...
}

// CheckNodeConditionPredicate checks if a pod can be scheduled on a node reporting
// network unavailable and not ready condition. Only node conditions are accounted in this predicate.
func CheckNodeConditionPredicate(pod *v1.Pod, meta PredicateMetadata, nodeInfo *schedulernodeinfo.NodeInfo) (bool, []PredicateFailureReason, error) {
	...
}

...

一些预选算法的解释：

NoVolumeZoneConflict：pod 请求的 volume 是否能在节点所在的 Zone 使用。通过匹配 node 和 PV 的 failure-domain.beta.kubernetes.io/zone 和 failure-domain.beta.kubernetes.io/region 来决定
MaxEBSVolumeCount：请求的 volumes 是否超过 EBS（Elastic Block Store） 支持的最大值，默认是 39
MaxGCEPDVolumeCount：请求的 volumes 是否超过 GCE 支持的最大值，默认是 16
MatchInterPodAffinity：根据 inter-pod affinity 来决定 pod 是否能调度到节点上。这个过滤方法会看 pod 是否和当前节点的某个 pod 互斥。
NoDiskConflict：检查 pod 请求的 volume 是否就绪和冲突。如果主机上已经挂载了某个卷，则使用相同卷的 pod 不能调度到这个主机上。kubernetes 使用的 volume 类型不同，过滤逻辑也不同。比如不同云主机的 volume 使用限制不同：GCE 允许多个 pods 使用同时使用 volume，前提是它们是只读的；AWS 不允许 pods 使用同一个 volume；Ceph RBD 不允许 pods 共享同一个 monitor
GeneralPredicates：普通过滤函数，主要考虑 kubernetes 资源是否能够满足，比如 CPU 和 Memory 是否足够，端口是否冲突、selector 是否匹配
PodFitsResources：检查主机上的资源是否满足 pod 的需求。资源的计算是根据主机上运行 pod 请求的资源作为参考的，而不是以实际运行的资源数量
PodFitsHost：如果 pod 指定了 spec.NodeName，看节点的名字是否何它匹配，只有匹配的节点才能运行 pod
PodFitsHostPorts：检查 pod 申请的主机端口是否已经被其他 pod 占用，如果是，则不能调度
PodSelectorMatches：检查主机的标签是否满足 pod 的 selector。包括 NodeAffinity 和 nodeSelector 中定义的标签。
PodToleratesNodeTaints：根据 taints 和 toleration 的关系判断 pod 是否可以调度到节点上
CheckNodeMemoryPressure：检查 pod 能否调度到内存有压力的节点上。
CheckNodeDiskPressure：检查 pod 能否调度到磁盘有压力的节点上，目前所有的 pod 都不能调度到磁盘有压力的节点上

下面的 predicates.Ordering() 就是按照列表把所有的默认预选算法依次执行一遍！

func (g *genericScheduler) podFitsOnNode(pluginContext *framework.PluginContext, pod *v1.Pod, meta predicates.PredicateMetadata, info *schedulernodeinfo.NodeInfo, predicateFuncs map[string]predicates.FitPredicate, queue internalqueue.SchedulingQueue, alwaysCheckAllPredicates bool) (bool, []predicates.PredicateFailureReason, *framework.Status, error) {
    // 执行两次
	for i := 0; i < 2; i++ {
		...
		for _, predicateKey := range predicates.Ordering() {
			// 真正执行 predicate 
			if predicate, exist := predicateFuncs[predicateKey]; exist {
				fit, reasons, err = predicate(pod, metaToUse, nodeInfoToUse)
			}
		}
		...
	}
}

到目前为止就讲完了调度的预选主要流程了！后续继续讲解 priority 流程

4. 参考

《K8s 源码剖析及debug实战（一）：Minikube 安装及源码准备》
《K8s 源码剖析及debug实战（二）：debug K8s 源码》
《K8s 源码剖析及debug实战之 Kube-Scheduler（一）：启动流程详解》
《K8s 源码剖析及debug实战之 Kube-Scheduler（二）：终于找到了调度算法的代码入口》
《K8s 源码剖析及debug实战之 Kube-Scheduler（三）：debug 到预选算法门口了》

欢迎关注本人，我是喜欢搞事的程序猿； 一起进步，一起学习；

也欢迎关注我的wx公众号：一个比特定乾坤