在上篇文章kube-scheduler 源碼分析中已經(jīng)介紹了 kube-scheduler 的設(shè)計(jì)以及從源碼角度分析了其執(zhí)行流程，這篇文章會(huì)專(zhuān)注介紹調(diào)度過(guò)程中 predicates 和 priorities 這兩個(gè)調(diào)度策略主要發(fā)生作用的階段。

kubernetes 版本: v1.16

predicates 調(diào)度算法源碼分析

predicates 算法主要是對(duì)集群中的 node 進(jìn)行過(guò)濾，選出符合當(dāng)前 pod 運(yùn)行的 nodes。

調(diào)度算法說(shuō)明

上節(jié)已經(jīng)提到默認(rèn)的調(diào)度算法在pkg/scheduler/algorithmprovider/defaults/defaults.go中定義了：

func defaultPredicates() sets.String {
    return sets.NewString(
        predicates.NoVolumeZoneConflictPred,
        predicates.MaxEBSVolumeCountPred,
        predicates.MaxGCEPDVolumeCountPred,
        predicates.MaxAzureDiskVolumeCountPred,
        predicates.MaxCSIVolumeCountPred,
        predicates.MatchInterPodAffinityPred,
        predicates.NoDiskConflictPred,
        predicates.GeneralPred,
        predicates.CheckNodeMemoryPressurePred,
        predicates.CheckNodeDiskPressurePred,
        predicates.CheckNodePIDPressurePred,
        predicates.CheckNodeConditionPred,
        predicates.PodToleratesNodeTaintsPred,
        predicates.CheckVolumeBindingPred,
    )
}

下面是對(duì)默認(rèn)調(diào)度算法的一些說(shuō)明：

默認(rèn)的 predicates 調(diào)度算法主要分為五種類(lèi)型：

1、第一種類(lèi)型叫作 GeneralPredicates，包含 PodFitsResources、PodFitsHost、PodFitsHostPorts、PodMatchNodeSelector 四種策略，其具體含義如下所示：

• PodFitsHost：檢查宿主機(jī)的名字是否跟 Pod 的 spec.nodeName 一致
• PodFitsHostPorts：檢查 Pod 申請(qǐng)的宿主機(jī)端口（spec.nodePort）是不是跟已經(jīng)被使用的端口有沖突
• PodMatchNodeSelector：檢查 Pod 的 nodeSelector 或者 nodeAffinity 指定的節(jié)點(diǎn)是否與節(jié)點(diǎn)匹配等
• PodFitsResources：檢查主機(jī)的資源是否滿(mǎn)足 Pod 的需求，根據(jù)實(shí)際已經(jīng)分配（Request）的資源量做調(diào)度

kubelet 在啟動(dòng) Pod 前，會(huì)執(zhí)行一個(gè) Admit 操作來(lái)進(jìn)行二次確認(rèn)，這里二次確認(rèn)的規(guī)則就是執(zhí)行一遍 GeneralPredicates。

2、第二種類(lèi)型是與 Volume 相關(guān)的過(guò)濾規(guī)則，主要有NoDiskConflictPred、MaxGCEPDVolumeCountPred、MaxAzureDiskVolumeCountPred、MaxCSIVolumeCountPred、MaxEBSVolumeCountPred、NoVolumeZoneConflictPred、CheckVolumeBindingPred。

3、第三種類(lèi)型是宿主機(jī)相關(guān)的過(guò)濾規(guī)則，主要是 PodToleratesNodeTaintsPred。

4、第四種類(lèi)型是 Pod 相關(guān)的過(guò)濾規(guī)則，主要是 MatchInterPodAffinityPred。

5、第五種類(lèi)型是新增的過(guò)濾規(guī)則，與宿主機(jī)的運(yùn)行狀況有關(guān)，主要有 CheckNodeCondition、 CheckNodeMemoryPressure、CheckNodePIDPressure、CheckNodeDiskPressure 四種。若啟用了 TaintNodesByCondition FeatureGates 則在 predicates 算法中會(huì)將該四種算法移除，TaintNodesByCondition 基于 node conditions 當(dāng) node 出現(xiàn) pressure 時(shí)自動(dòng)為 node 打上 taints 標(biāo)簽，該功能在 v1.8 引入，v1.12 成為 beta 版本，目前 v1.16 中也是 beta 版本，但在 v1.13 中該功能已默認(rèn)啟用。

predicates 調(diào)度算法也有一個(gè)順序，要不然在一臺(tái)資源已經(jīng)嚴(yán)重不足的宿主機(jī)上，上來(lái)就開(kāi)始計(jì)算 PodAffinityPredicate 是沒(méi)有實(shí)際意義的，其默認(rèn)順序如下所示：

k8s.io/kubernetes/pkg/scheduler/algorithm/predicates/predicates.go:146

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}
)

源碼分析

上節(jié)中已經(jīng)說(shuō)到調(diào)用預(yù)選以及優(yōu)選算法的邏輯在 k8s.io/kubernetes/pkg/scheduler/core/generic_scheduler.go:189中，

func (g *genericScheduler) Schedule(pod *v1.Pod, pluginContext *framework.PluginContext) (result ScheduleResult, err error) {
    ......
        
    // 執(zhí)行 predicates 策略
    filteredNodes, failedPredicateMap, filteredNodesStatuses, err := g.findNodesThatFit(pluginContext, pod)
    
    ......

    // 執(zhí)行 priorities 策略
    priorityList, err := PrioritizeNodes(pod, g.nodeInfoSnapshot.NodeInfoMap, metaPrioritiesInterface, g.prioritizers, filteredNodes, g.extenders, g.framework,        pluginContext)
    
    ......
    
    return
}

findNodesThatFit() 是 predicates 策略的實(shí)際調(diào)用方法，其基本流程如下：

• 設(shè)定最多需要檢查的節(jié)點(diǎn)數(shù)，作為預(yù)選節(jié)點(diǎn)數(shù)組的容量，避免總節(jié)點(diǎn)過(guò)多影響調(diào)度效率
• 通過(guò)NodeTree()不斷獲取下一個(gè)節(jié)點(diǎn)來(lái)判斷該節(jié)點(diǎn)是否滿(mǎn)足 pod 的調(diào)度條件
• 通過(guò)之前注冊(cè)的各種 predicates 函數(shù)來(lái)判斷當(dāng)前節(jié)點(diǎn)是否符合 pod 的調(diào)度條件
• 最后返回滿(mǎn)足調(diào)度條件的 node 列表，供下一步的優(yōu)選操作

checkNode()是一個(gè)校驗(yàn) node 是否符合要求的函數(shù)，其實(shí)際調(diào)用到的核心函數(shù)是podFitsOnNode()，再通過(guò)workqueue() 并發(fā)執(zhí)行checkNode() 函數(shù)，workqueue() 會(huì)啟動(dòng) 16 個(gè) goroutine 來(lái)并行計(jì)算需要篩選的 node 列表，其主要流程如下：

• 通過(guò) cache 中的 NodeTree() 不斷獲取下一個(gè) node
• 將當(dāng)前 node 和 pod 傳入podFitsOnNode() 方法中來(lái)判斷當(dāng)前 node 是否符合要求
• 如果當(dāng)前 node 符合要求就將當(dāng)前 node 加入預(yù)選節(jié)點(diǎn)的數(shù)組中filtered
• 如果當(dāng)前 node 不滿(mǎn)足要求，則加入到失敗的數(shù)組中，并記錄原因
• 通過(guò)workqueue.ParallelizeUntil()并發(fā)執(zhí)行checkNode()函數(shù)，一旦找到足夠的可行節(jié)點(diǎn)數(shù)后就停止篩選更多節(jié)點(diǎn)
• 若配置了 extender 則再次進(jìn)行過(guò)濾已篩選出的 node

k8s.io/kubernetes/pkg/scheduler/core/generic_scheduler.go:464

func (g *genericScheduler) findNodesThatFit(pluginContext *framework.PluginContext, pod *v1.Pod) ([]*v1.Node, FailedPredicateMap, framework.NodeToStatusMap, error) {
    var filtered []*v1.Node
    failedPredicateMap := FailedPredicateMap{}
    filteredNodesStatuses := framework.NodeToStatusMap{}

    if len(g.predicates) == 0 {
        filtered = g.cache.ListNodes()
    } else {
        allNodes := int32(g.cache.NodeTree().NumNodes())
        // 1.設(shè)定最多需要檢查的節(jié)點(diǎn)數(shù)
        numNodesToFind := g.numFeasibleNodesToFind(allNodes)

        filtered = make([]*v1.Node, numNodesToFind)
        ......
        
        // 2.獲取該 pod 的 meta 值 
        meta := g.predicateMetaProducer(pod, g.nodeInfoSnapshot.NodeInfoMap)

        // 3.checkNode 為執(zhí)行預(yù)選算法的函數(shù)
        checkNode := func(i int) {
            nodeName := g.cache.NodeTree().Next()

            // 4.podFitsOnNode 最終執(zhí)行預(yù)選算法的函數(shù) 
            fits, failedPredicates, status, err := g.podFitsOnNode(
                ......
            )
            if err != nil {
                ......
            }
            if fits {
                length := atomic.AddInt32(&filteredLen, 1)
                if length > numNodesToFind {
                    cancel()
                    atomic.AddInt32(&filteredLen, -1)
                } else {
                    filtered[length-1] = g.nodeInfoSnapshot.NodeInfoMap[nodeName].Node()
                }
            } else {
                ......
            }
        }

        // 5.啟動(dòng) 16 個(gè) goroutine 并發(fā)執(zhí)行 checkNode 函數(shù)
        workqueue.ParallelizeUntil(ctx, 16, int(allNodes), checkNode)

        filtered = filtered[:filteredLen]
        if len(errs) > 0 {
            ......
        }
    }

    // 6.若配置了 extender 則再次進(jìn)行過(guò)濾
    if len(filtered) > 0 && len(g.extenders) != 0 {
        ......
    }
    return filtered, failedPredicateMap, filteredNodesStatuses, nil
}

然后繼續(xù)看如何設(shè)定最多需要檢查的節(jié)點(diǎn)數(shù)，此過(guò)程由numFeasibleNodesToFind()進(jìn)行處理，基本流程如下：

• 如果總的 node 節(jié)點(diǎn)小于minFeasibleNodesToFind(默認(rèn)為100)則直接返回總節(jié)點(diǎn)數(shù)
• 如果節(jié)點(diǎn)數(shù)超過(guò) 100，則取指定百分比 percentageOfNodesToScore(默認(rèn)值為 50)的節(jié)點(diǎn)數(shù) ，當(dāng)該百分比后的數(shù)目仍小于minFeasibleNodesToFind，則返回minFeasibleNodesToFind
• 如果百分比后的數(shù)目大于minFeasibleNodesToFind，則返回該百分比的節(jié)點(diǎn)數(shù)

所以當(dāng)節(jié)點(diǎn)數(shù)小于 100 時(shí)直接返回，大于 100 時(shí)只返回其總數(shù)的 50%。percentageOfNodesToScore 參數(shù)在 v1.12 引入，默認(rèn)值為 50，kube-scheduler 在啟動(dòng)時(shí)可以設(shè)定該參數(shù)的值。

k8s.io/kubernetes/pkg/scheduler/core/generic_scheduler.go:441

func (g *genericScheduler) numFeasibleNodesToFind(numAllNodes int32) (numNodes int32) {
    if numAllNodes < minFeasibleNodesToFind || g.percentageOfNodesToScore >= 100 {
        return numAllNodes
    }

    adaptivePercentage := g.percentageOfNodesToScore
    if adaptivePercentage <= 0 {
        adaptivePercentage = schedulerapi.DefaultPercentageOfNodesToScore - numAllNodes/125
        if adaptivePercentage < minFeasibleNodesPercentageToFind {
            adaptivePercentage = minFeasibleNodesPercentageToFind
        }
    }

    numNodes = numAllNodes * adaptivePercentage / 100
    if numNodes < minFeasibleNodesToFind {
        return minFeasibleNodesToFind
    }

    return numNodes
}

pridicates 調(diào)度算法的核心是 podFitsOnNode() ，scheduler 的搶占機(jī)制也會(huì)執(zhí)行該函數(shù)，podFitsOnNode()基本流程如下：

• 遍歷已經(jīng)注冊(cè)好的預(yù)選策略predicates.Ordering()，按順序執(zhí)行對(duì)應(yīng)的策略函數(shù)
• 遍歷執(zhí)行每個(gè)策略函數(shù)，并返回是否合適，預(yù)選失敗的原因和錯(cuò)誤
• 如果預(yù)選函數(shù)執(zhí)行失敗，則加入預(yù)選失敗的數(shù)組中，直接返回，后面的預(yù)選函數(shù)不會(huì)再執(zhí)行
• 如果該 node 上存在 nominated pod 則執(zhí)行兩次預(yù)選函數(shù)

因?yàn)橐肓藫屨紮C(jī)制，此處主要說(shuō)明一下執(zhí)行兩次預(yù)選函數(shù)的原因：

第一次循環(huán)，若該 pod 為搶占者(nominatedPods)，調(diào)度器會(huì)假設(shè)該 pod 已經(jīng)運(yùn)行在這個(gè)節(jié)點(diǎn)上，然后更新meta和nodeInfo，nominatedPods是指執(zhí)行了搶占機(jī)制且已經(jīng)分配到了 node(pod.Status.NominatedNodeName 已被設(shè)定) 但是還沒(méi)有真正運(yùn)行起來(lái)的 pod，然后再執(zhí)行所有的預(yù)選函數(shù)。

第二次循環(huán)，不將nominatedPods加入到 node 內(nèi)。

而只有這兩遍 predicates 算法都能通過(guò)時(shí)，這個(gè) pod 和 node 才會(huì)被認(rèn)為是可以綁定(bind)的。這樣做是因?yàn)榭紤]到 pod affinity 等策略的執(zhí)行，如果當(dāng)前的 pod 與nominatedPods有依賴(lài)關(guān)系就會(huì)有問(wèn)題，因?yàn)?code>nominatedPods不能保證一定可以調(diào)度且在已指定的 node 運(yùn)行成功，也可能出現(xiàn)被其他高優(yōu)先級(jí)的 pod 搶占等問(wèn)題，關(guān)于搶占問(wèn)題下篇會(huì)詳細(xì)介紹。

func (g *genericScheduler) podFitsOnNode(......) (bool, []predicates.PredicateFailureReason, *framework.Status, error) {
    var failedPredicates []predicates.PredicateFailureReason
    var status *framework.Status

    podsAdded := false

    for i := 0; i < 2; i++ {
        metaToUse := meta
        nodeInfoToUse := info
        if i == 0 {
            // 1.第一次循環(huán)加入 NominatedPods，計(jì)算 meta, nodeInfo
            podsAdded, metaToUse, nodeInfoToUse = addNominatedPods(pod, meta, info, queue)
        } else if !podsAdded || len(failedPredicates) != 0 {
            break
        }
        // 2.按順序執(zhí)行所有預(yù)選函數(shù)
        for _, predicateKey := range predicates.Ordering() {
            var (
                fit     bool
                reasons []predicates.PredicateFailureReason
                err     error
            )
            if predicate, exist := predicateFuncs[predicateKey]; exist {
                fit, reasons, err = predicate(pod, metaToUse, nodeInfoToUse)
                if err != nil {
                    return false, []predicates.PredicateFailureReason{}, nil, err
                }
                                
                // 3.任何一個(gè)預(yù)選函數(shù)執(zhí)行失敗則直接返回
                if !fit {
                    failedPredicates = append(failedPredicates, reasons...)                   
                    if !alwaysCheckAllPredicates {
                        klog.V(5).Infoln("since alwaysCheckAllPredicates has not been set, the predicate " +
                            "evaluation is short circuited and there are chances " +
                            "of other predicates failing as well.")
                        break
                    }
                }
            }
        }
        // 4.執(zhí)行 Filter Plugin
        status = g.framework.RunFilterPlugins(pluginContext, pod, info.Node().Name)
        if !status.IsSuccess() && !status.IsUnschedulable() {
            return false, failedPredicates, status, status.AsError()
        }
    }

    return len(failedPredicates) == 0 && status.IsSuccess(), failedPredicates, status, nil
}

至此，關(guān)于 predicates 調(diào)度算法的執(zhí)行過(guò)程已經(jīng)分析完。

priorities 調(diào)度算法源碼分析

priorities 調(diào)度算法是在 pridicates 算法后執(zhí)行的，主要功能是對(duì)已經(jīng)過(guò)濾出的 nodes 進(jìn)行打分并選出最佳的一個(gè) node。

調(diào)度算法說(shuō)明

默認(rèn)的調(diào)度算法在pkg/scheduler/algorithmprovider/defaults/defaults.go中定義了：

func defaultPriorities() sets.String {
    return sets.NewString(
        priorities.SelectorSpreadPriority,
        priorities.InterPodAffinityPriority,
        priorities.LeastRequestedPriority,
        priorities.BalancedResourceAllocation,
        priorities.NodePreferAvoidPodsPriority,
        priorities.NodeAffinityPriority,
        priorities.TaintTolerationPriority,
        priorities.ImageLocalityPriority,
    )
}

默認(rèn)調(diào)度算法的一些說(shuō)明：

源碼分析

執(zhí)行 priorities 調(diào)度算法的邏輯是在 PrioritizeNodes()函數(shù)中，其目的是執(zhí)行每個(gè) priority 函數(shù)為 node 打分，分?jǐn)?shù)為 0-10，其功能主要有：

• PrioritizeNodes() 通過(guò)并行運(yùn)行各個(gè)優(yōu)先級(jí)函數(shù)來(lái)對(duì)節(jié)點(diǎn)進(jìn)行打分
• 每個(gè)優(yōu)先級(jí)函數(shù)會(huì)給節(jié)點(diǎn)打分，打分范圍為 0-10 分，0 表示優(yōu)先級(jí)最低的節(jié)點(diǎn)，10表示優(yōu)先級(jí)最高的節(jié)點(diǎn)
• 每個(gè)優(yōu)先級(jí)函數(shù)有各自的權(quán)重
• 優(yōu)先級(jí)函數(shù)返回的節(jié)點(diǎn)分?jǐn)?shù)乘以權(quán)重以獲得加權(quán)分?jǐn)?shù)
• 最后計(jì)算所有節(jié)點(diǎn)的總加權(quán)分?jǐn)?shù)

k8s.io/kubernetes/pkg/scheduler/core/generic_scheduler.go:691

func PrioritizeNodes(......) (schedulerapi.HostPriorityList, error) {
    // 1.檢查是否有自定義配置
    if len(priorityConfigs) == 0 && len(extenders) == 0 {
        result := make(schedulerapi.HostPriorityList, 0, len(nodes))
        for i := range nodes {
            hostPriority, err := EqualPriorityMap(pod, meta, nodeNameToInfo[nodes[i].Name])
            if err != nil {
                return nil, err
            }
            result = append(result, hostPriority)
        }
        return result, nil
    }
    ......

    results := make([]schedulerapi.HostPriorityList, len(priorityConfigs), len(priorityConfigs))

    ......
    // 2.使用 workqueue 啟動(dòng) 16 個(gè) goroutine 并發(fā)為 node 打分
    workqueue.ParallelizeUntil(context.TODO(), 16, len(nodes), func(index int) {
        nodeInfo := nodeNameToInfo[nodes[index].Name]
        for i := range priorityConfigs {
            if priorityConfigs[i].Function != nil {
                continue
            }

            var err error
            results[i][index], err = priorityConfigs[i].Map(pod, meta, nodeInfo)
            if err != nil {
                appendError(err)
                results[i][index].Host = nodes[index].Name
            }
        }
    })

    // 3.執(zhí)行自定義配置
    for i := range priorityConfigs {
                ......
    }
    
    wg.Wait()
    if len(errs) != 0 {
        return schedulerapi.HostPriorityList{}, errors.NewAggregate(errs)
    }

    // 4.運(yùn)行 Score plugins
    scoresMap, scoreStatus := framework.RunScorePlugins(pluginContext, pod, nodes)
    if !scoreStatus.IsSuccess() {
        return schedulerapi.HostPriorityList{}, scoreStatus.AsError()
    }
    
    result := make(schedulerapi.HostPriorityList, 0, len(nodes))
    // 5.為每個(gè) node 匯總分?jǐn)?shù)
    for i := range nodes {
        result = append(result, schedulerapi.HostPriority{Host: nodes[i].Name, Score: 0})
        for j := range priorityConfigs {
            result[i].Score += results[j][i].Score * priorityConfigs[j].Weight
        }

        for j := range scoresMap {
            result[i].Score += scoresMap[j][i].Score
        }
    }
    
    // 6.執(zhí)行 extender 
    if len(extenders) != 0 && nodes != nil {
        ......
    }
        ......
    return result, nil
}

總結(jié)

本文主要講述了 kube-scheduler 中的 predicates 調(diào)度算法與 priorities 調(diào)度算法的執(zhí)行流程，可以看到 kube-scheduler 中有許多的調(diào)度策略，但是想要添加自己的策略并不容易，scheduler 目前已經(jīng)朝著提升性能與擴(kuò)展性的方向演進(jìn)了，其調(diào)度部分進(jìn)行性能優(yōu)化的一個(gè)最根本原則就是盡最大可能將集群信息 cache 化，以便從根本上提高 predicates 和 priorities 調(diào)度算法的執(zhí)行效率。第二個(gè)就是在 bind 階段進(jìn)行異步處理，只會(huì)更新其 cache 里的 pod 和 node 的信息，這種基于“樂(lè)觀”假設(shè)的 API 對(duì)象更新方式，在 kubernetes 里被稱(chēng)作 assume，如果這次異步的 bind 過(guò)程失敗了，其實(shí)也沒(méi)有太大關(guān)系，等 scheduler cache 同步之后一切又恢復(fù)正常了。除了上述的“cache 化”和“樂(lè)觀綁定”，還有一個(gè)重要的設(shè)計(jì)，那就是“無(wú)鎖化”，predicates 調(diào)度算法與 priorities 調(diào)度算法的執(zhí)行都是并行的，只有在調(diào)度隊(duì)列和 scheduler cache 進(jìn)行操作時(shí)，才需要加鎖，而對(duì)調(diào)度隊(duì)列的操作并不影響主流程。

參考：

https://kubernetes.io/docs/concepts/configuration/scheduling-framework/

predicates-ordering.md