從零開始入門 K8s | 排程器的排程流程和算法介紹

作者 | 汪萌海（木蘇）  阿裡巴巴技術專家

關注“阿裡巴巴雲原生”公衆号，回複關鍵詞“入門”，即可下載下傳從零入門 K8s 系列文章 PPT。

導讀：Kubernetes 作為當下最流行的容器自動化運維平台，以聲明式實作了靈活的容器編排，本文以 v1.16 版本為基礎詳細介紹了 K8s 的基本排程架構、流程，以及主要的過濾器、Score 算法實作等，并介紹了兩種方式用于實作自定義排程能力。

排程流程

排程流程概覽

Kubernetes 作為當下最主流的容器自動化運維平台，作為 K8s 的容器編排的核心元件 kube-scheduler 将是我今天介紹的主角，如下介紹的版本都是以 release-1.16 為基礎，下圖是 kube-scheduler 的主要幾大元件：

Policy

Scheduler 的排程政策啟動配置目前支援三種方式，配置檔案 / 指令行參數 / ConfigMap。排程政策可以配置指定排程主流程中要用哪些過濾器 (Predicates)、打分器 (Priorities) 、外部擴充的排程器 (Extenders)，以及最新支援的 SchedulerFramwork 的自定義擴充點 (Plugins)。

Informer

Scheduler 在啟動的時候通過 K8s 的 informer 機制以 List+Watch 從 kube-apiserver 擷取排程需要的資料例如：Pods、Nodes、Persistant Volume(PV), Persistant Volume Claim(PVC) 等等，并将這些資料做一定的預處理作為排程器的的 Cache。

排程流水線

通過 Informer 将需要排程的 Pod 插入 Queue 中，Pipeline 會循環從 Queue Pop 等待排程的 Pod 放入 Pipeline 執行。

排程流水線 (Schedule Pipeline) 主要有三個階段：Scheduler Thread，Wait Thread，Bind Thread。

• Scheduler Thread 階段: 從如上的架構圖可以看到 Schduler Thread 會經曆 Pre Filter -> Filter -> Post Filter-> Score -> Reserve，可以簡單了解為 Filter -> Score -> Reserve。

Filter 階段用于選擇符合 Pod Spec 描述的 Nodes；Score 階段用于從 Filter 過後的 Nodes 進行打分和排序；Reserve 階段将 Pod 跟排序後的最優 Node 的 NodeCache 中，表示這個 Pod 已經配置設定到這個 Node 上, 讓下一個等待排程的 Pod 對這個 Node 進行 Filter 和 Score 的時候能看到剛才配置設定的 Pod。

• Wait Thread 階段: 這個階段可以用來等待 Pod 關聯的資源的 Ready 等待，例如等待 PVC 的 PV 建立成功，或者 Gang 排程中等待關聯的 Pod 排程成功等等；
• Bind Thread 階段: 用于将 Pod 和 Node 的關聯持久化 Kube APIServer。

整個排程流水線隻有在 Scheduler Thread 階段是串行的一個 Pod 一個 Pod 的進行排程，在 Wait 和 Bind 階段 Pod 都是異步并行執行。

排程詳細流程

解說完 kube-scheduler 的幾大部件的作用和關聯關系之後，接下來深入了解下 Scheduler Pipeline 的具體工作原理，如下是 kube-scheduler 的詳細流程圖，先解說排程隊列：

SchedulingQueue 有三個子隊列 activeQ、backoffQ、unschedulableQ。

Scheduler 啟動的時候所有等待被排程的 Pod 都會進入 activieQ，activeQ 會按照 Pod 的 priority 進行排序，Scheduler Pipepline 會從 activeQ 擷取一個 Pod 進行 Pipeline 執行排程流程，當排程失敗之後會直接根據情況選擇進入 unschedulableQ 或者 backoffQ，如果在目前 Pod 排程期間 Node Cache、Pod Cache 等 Scheduler Cache 有變化就進入 backoffQ，否則進入 unschedulableQ。

unschedulableQ 會定期較長時間（例如 60 秒）刷入 activeQ 或者 backoffQ，或者在 Scheduler Cache 發生變化的時候觸發關聯的 Pod 刷入 activeQ 或者 backoffQ；backoffQ 會以 backoff 機制相比 unschedulableQ 比較快地讓待排程的 Pod 進入 activeQ 進行重新排程。

接着詳細介紹 Scheduler Thread 階段，在 Scheduler Pipeline 拿到一個等待排程的 Pod，會從 NodeCache 裡面拿到相關的 Node 執行 Filter 邏輯比對，這從 NodeCache 周遊 Node 的過程有一個空間算法上的優化，簡單可以概括為在避免過濾所有節點的同時考慮了排程的容災取樣排程。

具體的優化算法邏輯（有興趣的同學可以看 node_tree.go 的 Next 方法）：在 NodeCache 中，Node 是按照 zone 進行分堆。在 filter 階段的時候，為會 NodeCache 維護一個 zondeIndex，每 Pop 一個 Node 進行過濾，zoneIndex 往後挪一個位置，然後從該 zone 的 node 清單中取一個 node 出來。

可以看到上圖縱軸有一個 nodeIndex，每次也會自增。如果目前 zone 的節點無資料，那就會從下一個 zone 中拿資料。大概的流程就是 zoneIndex 從左向右，nodeIndex 從上到下，保證拿到的 Node 節點是按照 zone 打散，進而實作避免過濾所有節點的同時考慮了節點的 az 均衡部署。（最新 release-v.1.17 的版本已經取消這種算法，為什麼取消應該是沒有考慮 Pod 的 prefer 和 node 的 prefer，沒有實作 Pod 的 Spec 要求）

取樣排程裡面的取樣規模這裡簡單介紹一下，預設的取樣比率公式 = Max (5, 50 - 叢集的 node 數 / 125),取樣規模 = Max (100, 叢集 Node 數*取樣比率)。

這裡舉個例子：節點規模為 3000 個節點，那麼取樣比例 = Max (5, 50 - 3000/125) = 26%，那麼取樣規模 = Max (100, 3000* 0.26) = 780，在排程流水線裡面，Filter 隻要比對到 780 個候選節點，就可以停止 Filter 流程，走到 Score 階段。

Score 階段依據 Policy 配置的算分插件，進行排序，分數最高的節點作為 SelectHost。接着将這個 Pod 配置設定到這個 Node 上，這個過程叫做 Reserver 階段可以稱為賬本預占。預占的過程修改 Pod 在 PodCache 的狀态為 Assumed 的狀态(處于記憶體态)。

排程過程涉及到 Pod 狀态機的生命周期，這裡簡單介紹下 Pod 的幾個主要狀态: Initial（虛拟狀态）->Assumed（Reserver)->Added->Deleted(虛拟狀态）; 當通過 Informer watch 到 Pod 資料已經确定配置設定到這個節點的時候，才會把 Pod 的狀态變成 Added。選中完節點在 Bind 的時候，有可能會 Bind 失敗，在 Bind 失敗的時候會做回退，就是把預占用的賬本做 Assumed 的資料退回 Initial，也就是把 Assumed 狀态擦除，從 Node 裡面把 Pod 賬本清除。

如果 Bind 失敗，會把 Pod 重新丢回到 unschedulableQ 隊列裡面。在排程隊列中，什麼情況下 Pod 會到 backoffQ 中呢？這是一個很細節的點。如果在這麼一個排程周期裡面，Cache 發生了變化，會把 Pod 放到 backoffQ 裡面。在 backoffQ 裡面等待的時間會比在 unschedulableQ 裡面時間更短，backoffQ 裡有一個降級政策，是 2 的指數次幂降級。假設重試第一次為 1s，那第二次就是 2s，第三次就是 4s，第四次就是 8s，最大到 10s。

排程算法實作

Predicates (過濾器)

Filter 根據功能用途可以把它們分為四類：

• 存儲比對相關
• Pode 和 Node 比對相關
• Pod 和 Pod 比對相關
• Pod 打散相關

存儲相關

存儲相關的幾個過濾器的功能：

• NoVolumeZoneConflict，pvc 關聯的 pv 的 label 上設定 zoneaz 限制待比對的節點要跟 pv；
• MaxCSIVolumeCountPred，是用來校驗 pvc 上指定的 Provision 在 CSI plugin 上的單機最大 pv 數限制；
• CheckVolumeBindingPred，在 pvc 和 pv 的 binding 過程中對其進行邏輯校驗，裡頭的邏輯寫的比較複雜，主要都是如何複用 pv；
• NoDiskConfict，SCSI 存儲不會被重複的 volume。

Pod 和 Node 比對相關

• CheckNodeCondition：校驗節點是否準備好被排程，校驗node.condition的condition type ：Ready為true和NetworkUnavailable為false以及Node.Spec.Unschedulable為false；
• CheckNodeUnschedulable：在 node 節點上有一個 NodeUnschedulable 的标記，我們可以通過 kube-controller 對這個節點直接标記為不可排程，那這個節點就不會被排程了。在 1.16 的版本裡，這個 Unschedulable 已經變成了一個 Taints。也就是說需要校驗一下 Pod 上打上的 Tolerates 是不是可以容忍這個 Taints；
• PodToleratesNodeTaints：校驗 Node 的 Taints 是否被 Pod Tolerates 包含；
• PodFitsHostPorts：校驗 Pod 上的 Container 聲明的 Ports 是否正在被 Node 上已經配置設定的 Pod 使用；
• MatchNodeSelector: 校驗 Pod.Spec.Affinity.NodeAffinity 和 Pod.Spec.NodeSelector 是否與 Node 的 Labels 比對。

MatchinterPodAffinity：主要是 PodAffinity 和 PodAntiAffinity 的校驗邏輯，這裡面最大的複雜度是在于 Affinity 裡面的 PodAffinityTerm 描述支援的 TopologyKey（可以表示在 node/zone/az 等拓撲結構上），這個其實是一個性能殺手。

• EvenPodsSpread
• CheckServiceAffinity

這是一個新的功能特性，首先來看一下 EvenPodsSpread 中 Spec 描述：

-- 描述符合條件的一組 Pod 在指定 TopologyKey 上的打散要求。

下面我們來看一下怎麼描述一組 Pod，如下圖所示：

spec:
  topologySpreadConstraints:
  - maxSkew: 1
    whenUnsatisfiable: DoNotSchedule
    topologyKey: k8s.io/hostname
    selector:
      matchLabels:
        app: foo
      matchExpressions:
      - key: app
        operator: In
        values: ['foo', 'foo2']           

topologySpreadConstraints: 用于描述 Pod 要在什麼拓撲結構上進行均衡打散，多個 topologySpreadConstraint 之間是 and 關系；

selector：用于描述需要滿足的拓撲打散的一組 Pod 的清單

topologyKey: 作用在什麼拓撲結構上；

maxSkew: 最大允許的不均衡數量；

whenUnsatisfiable: 當不滿足 topologySpreadConstraint 的時候的政策，DoNotSchedule：表示作用于 filter 階段，ScheduleAnyway：作用于 score 階段。

下面舉例描述下：

selector 選擇的是所有 lable 符合 app=foo 的 pod，必須在 zone 級别是打散的，允許最大不均衡數為 1。

叢集中有三個 zone，上圖中 label 的值 app=foo 的 Pod 在 zone1 和 zone2 中都配置設定了一個 pod。

計算不均衡數量公式為：ActualSkew = count[topo] - min(count[topo])

首先，依據 selector 擷取到符合條件的 Pod 清單

其次，會按照 topologyKey 去分組得到 count[topo]

如上圖所示：

假設 maxSkew 為 1，如果配置設定到 zone1/zone2，skew 的值為2，大于前面設定的 maxSkew。這是不比對的，是以隻能配置設定到 zone3。如果配置設定到 zone3 的話，min(count[topo]) 為1，count[topo]為 1，那 skew 就等于 0，是以隻能配置設定到 zone2。

假設 maxSkew 為 2，配置設定到 z1(z2)，skew 的值為 2/1/0(1/2/0)，最大值為 2，滿足 <=maxSkew。那 z1/z2/z3 都是允許被選擇的。

通過 EvenPodsSpread 可以實作一組 Pod 在某個 TopologyKey 上的均衡打散需求，如果必須要求每個 topo 上都均衡可以設 maxSkew 為1，當然這個描述缺乏了一些控制，例如必須配置設定在多少個 topologyValue 上的限制。

Priorities

接下來看一下打分算法，打分算法主要解決的問題就是叢集的碎片、容災、水位、親和、反親和等。

按照類别可以分為四大類：

• Node 水位
• Pod 打散 (topp,service,controller)
• Node 親和&反親和
• Pod 親和&反親和

資源水位

接下來介紹打分器相關的第一個資源水位。

節點打分算法跟資源水位相關的主要有四個，如上圖所示。

• 資源水位公式的概念

Request：Node 已經配置設定的資源；Allocatable：Node 的可排程的資源

• 優先打散

把 Pod 分到資源空閑率最高的節點上，而非空閑資源最大的節點，公式：資源空閑率=(Allocatable - Request) / Allocatable，當這個值越大，表示分數越高，優先配置設定到高分數的節點。其中(Allocatable - Request)表示為Pod配置設定到這個節點之後空閑的資源數。

• 優先堆疊

把 Pod 配置設定到資源使用率最高的節點上，公式:資源使用率 = Request / Allocatable ，資源使用率越高，表示得分越高，會優先配置設定到高分數的節點。 

• 碎片率

是指 Node 上的多種資源之間的資源使用率的內插補點，目前支援 CPU/Mem/Disk 三類資源, 假如僅考慮 CPU/Mem，那麼碎片率的公式 = Abs[CPU(Request / Allocatable) - Mem(Request / Allocatable)] 。舉一個例子，當 CPU 的配置設定率是 99%，記憶體的配置設定率是 50%，那麼碎片率 = 99% - 50% = 50%，那麼這個例子中剩餘 1% CPU, 50% Mem，很難有這類規格的容器能用完 Mem。得分 = 1 - 碎片率，碎片率越高得分低。

• 指定比率

可以在 Scheduler 啟動的時候，為每一個資源使用率設定得分，進而實作控制叢集上 node 資源配置設定分布曲線。

Pod 打散

Pod 打散為了解決的問題為：支援符合條件的一組 Pod 在不同 topology 上部署的 spread 需求。

• SelectorSpreadPriority

用于實作 Pod 所屬的 Controller 下所有的 Pod 在 Node 上打散的要求。實作方式是這樣的：它會依據待配置設定的 Pod 所屬的 controller，計算該 controller 下的所有 Pod,假設總數為 T，對這些 Pod 按照所在的 Node 分組統計；假設為 N (表示為某個 Node 上的統計值)，那麼對 Node上的分數統計為  (T-N)/T 的分數，值越大表示這個節點的 controller 部署的越少，分數越高，進而達到 workload 的 pod 打散需求。

• ServiceSpreadingPriority

官方注釋上說大機率會用來替換 SelectorSpreadPriority，為什麼呢？我個人了解：Service 代表一組服務，我們隻要能做到服務的打散配置設定就足夠了。

• EvenPodsSpreadPriority

用來指定一組符合條件的 Pod 在某個拓撲結構上的打散需求，這樣是比較靈活、比較定制化的一種方式，使用起來也是比較複雜的一種方式。

因為這個使用方式可能會一直變化，我們假設這個拓撲結構是這樣的：Spec 是要求在 node 上進行分布的，我們就可以按照上圖中的計算公式，計算一下在這個 node 上滿足 Spec 指定 labelSelector 條件的 pod 數量，然後計算一下最大的內插補點，接着計算一下 Node 配置設定的權重，如果說這個值越大，表示這個值越優先。

• NodeAffinityPriority，這個是為了滿足 Pod 和 Node 的親和 & 反親和；

• ServiceAntiAffinity，是為了支援 Service 下的 Pod 的分布要按照 Node 的某個 label 的值進行均衡。比如：叢集的節點有雲上也有雲下兩組節點，我們要求服務在雲上雲下均衡去分布，假設 Node 上有某個 label，那我們就可以用這個 ServiceAntiAffinity 進行打散分布；

• NodeLabelPrioritizer，主要是為了實作對某些特定 label 的 Node 優先配置設定，算法很簡單，啟動時候依據排程政策 (SchedulerPolicy）配置的 label 值，判斷 Node 上是否滿足這個label條件，如果滿足條件的節點優先配置設定;

• ImageLocalityPriority，節點親和主要考慮的是鏡像下載下傳的速度。如果節點裡面存在鏡像的話，優先把 Pod 排程到這個節點上，這裡還會去考慮鏡像的大小，比如這個 Pod 有好幾個鏡像，鏡像越大下載下傳速度越慢，它會按照節點上已經存在的鏡像大小優先級親和。

InterPodAffinityPriority

先介紹一下使用場景：

• 第一個例子，比如說應用 A 提供資料，應用 B 提供服務，A 和 B 部署在一起可以走本地網絡，優化網絡傳輸；
• 第二個例子，如果應用 A 和應用 B 之間都是 CPU 密集型應用，而且證明它們之間是會互相幹擾的，那麼可以通過這個規則設定盡量讓它們不在一個節點上。

NodePreferAvoidPodsPriority

用于實作某些 controller 盡量不配置設定到某些節點上的能力；通過在 node 上加 annotation 聲明哪些 controller 不要配置設定到 Node 上，如果不滿足就優先。

如何配置排程器

配置排程器介紹

怎麼啟動一個排程器，這裡有兩種情況：

• 第一種我們可以通過預設配置啟動排程器，什麼參數都不指定；
• 第二種我們可以通過指定配置的排程檔案。

如果我們通過預設的方式啟動的話，想知道預設配置啟動的參數是哪些？可以用 --write-config-to 可以把預設配置寫到一個指定檔案裡面。

下面來看一下預設配置檔案，如下圖所示：

• algorithmSource :算法提供者，目前提供三種方式：Provider、file、configMap，後面會介紹這塊；
• percentageOfNodesToscore : 排程器提供的一個擴充能力，能夠減少 Node 節點的取樣規模；
• schedulerName :用來表示排程器啟動的時候，負責哪些 Pod 的排程；如果沒有指定的話，預設名稱就是 default-scheduler；
• bindTimeoutSeconds :用來指定 bind 階段的操作時間，機關是秒；
• clientConnection: 用來配置跟 kube-apiserver 互動的一些參數配置。比如 contentType，是用來跟 kube-apiserver 互動的序列化協定，這裡指定為 protobuf；
• disablePreemption :關閉搶占排程；
• hardPodAffinitySymnetricweight :配置 PodAffinity 和 NodeAffinity 的權重是多少。

algorithmSource

這裡介紹一下過濾器、打分器等一些配置檔案的格式，目前提供三種方式：

• Provider
• file
• configMap

如果指定的是 Provider，有兩種實作方式：

• 一種是 DefaultPrivider；
• 一種是 ClusterAutoscalerProvider。

ClusterAutoscalerProvider 是優先堆疊的，DefaultPrivider 是優先打散的。關于這個政策，當你的節點開啟了自動擴容，盡量使用 ClusterAutoscalerProvider 會比較符合你的需求。

這裡看一下政策檔案的配置内容，如下圖所示：

這裡可以看到配置的過濾器 predicates，配置的打分器 priorities，以及我們配置的擴充排程器。這裡有一個比較有意思的參數就是：alwaysCheckAllPredicates。它是用來控制當過濾清單有個傳回 false 時，是否繼續往下執行？預設的肯定是 false；如果配置成 true，它會把每個插件都走一遍。

如何擴充排程器

Scheduler Extender

首先來看一下 Schedule Extender 能做什麼？在啟動官方排程器之後，可以再啟動一個擴充排程器。

通過配置檔案，如上文提到的 Polic 檔案中 extender 的配置，包括 extender 服務的 URL 位址、是否 https 服務，以及服務是否已經有 NodeCache。如果有 NodeCache，那排程器隻會傳給 nodenames 清單。如果沒有開啟，那排程器會把所有 nodeinfo 完整結構都傳遞過來。

ignorable 這個參數表示排程器在網絡不可達或者是服務報錯，是否可以忽略擴充排程器。managedResources，官方排程器在遇到這個 Resource 時會用擴充排程器，如果不指定表示所有的都會使用擴充排程器。

這裡舉個 GPU share 的例子。在擴充排程器裡面會記錄每個卡上配置設定的記憶體大小，官方排程器隻負責 Node 節點上總的顯示卡記憶體是否足夠。這裡擴充資源叫 example/gpu-men: 200g，假設有個 Pod 要排程，通過 kube-scheduler 會看到我們的擴充資源，這個擴充資源配置要走擴充排程器，在排程階段就會通過配置的 url 位址來調用擴充排程器，進而能夠達到排程器能夠實作 gpu-share 的能力。

Scheduler Framework

這裡分成兩點來說，從擴充點用途和并發模型分别介紹。

擴充點的主要用途

擴充點的主要用途主要有以下幾個：

• QueueSort：用來支援自定義 Pod 的排序。如果指定 QueueSort 的排序算法，在排程隊列裡面就會按照指定的排序算法來進行排序；
• Prefilter：對 Pod 的請求做預處理，比如 Pod 的緩存，可以在這個階段設定；
• Filter：就是對 Filter 做擴充，可以加一些自己想要的 Filter，比如說剛才提到的 gpu-shared 可以在這裡面實作；
• PostFilter：可以用于 logs/metircs，或者是對 Score 之前做資料預處理。比如說自定義的緩存插件，可以在這裡面做；
• Score：就是打分插件，通過這個接口來實作增強；
• Reserver：對有狀态的 plugin 可以對資源做記憶體記賬；
• Permit：wait、deny、approve，可以作為 gang 的插入點。這個可以對每個 pod 做等待，等所有 Pod 都排程成功、都達到可用狀态時再去做通行，假如一個 pod 失敗了，這裡可以 deny 掉；
• PreBind：在真正 bind node 之前，執行一些操作，例如：雲盤挂載盤到 Node 上；
• Bind：一個 Pod 隻會被一個 BindPlugin 處理；
• PostBind：bind 成功之後執行的邏輯，比如可以用于 logs/metircs；
• Unreserve：在 Permit 到 Bind 這幾個階段隻要報錯就回退。比如說在前面的階段 Permit 失敗、PreBind 失敗， 都會去做資源回退。

并發模型

并發模型意思是主排程流程是在 Pre Filter 到 Reserve，如上圖淺藍色部分所示。從 Queue 拿到一個 Pod 排程完到 Reserve 就結束了，接着會把這個 Pod 異步交給 Wait Thread，Wait Thread 如果等待成功了，就會交給 Bind Thread，就是這樣一個線程模型。

自定義 Plugin

如何編寫注冊自定義 Plugin？

這裡是一個官方的例子，在 Bind 階段，要将 Pod 綁定到某個 Node 上，對 Kube-apiserver 做 Bind。這裡可以看到主要有兩個接口，bind 的接口是聲明排程器的名稱，以及 bind 的邏輯是什麼。最後還要實作一個構造方法，告訴它的構造方法是怎樣的邏輯。

啟動自定義 Plugin 的排程器：

• vendor
• fork

在啟動的時候可以通過兩種方式去注冊：

• 第一種方式是通過自己編寫一個腳本，通過 vendor 把排程器的代碼 vendor 進來。在啟動 scheduler.NewSchedulerCommand 的時候把 defaultbinder 注冊進去，這樣就可以啟動一個排程器；

• 第二種方式是可以 fork kube-scheduler 的源代碼，然後把排程器的 defaultbinder 通過 register 插件注冊進去。注冊完這個插件，去 build 一個腳本、build 一個鏡像，然後啟動的時候，在配置檔案的 plugins.bind.enable 啟動起來。

本文總結

本文内容到此就結束了，這裡為大家簡單總結一下：

• 第一部分跟大家介紹了下排程器的整體工作流程，以及一些計算的算法優化；
• 第二部分詳細介紹排程的主要幾個工作元件過濾器元件、score 元件的實作，并列舉幾個 score 的使用場景；
• 第三部分介紹排程器的配置檔案的用法說明，讓大家可以通過這些配置來實作自己期望的排程行為；
• 第四部分介紹了一些進階用法，怎麼通過 extender/framework 擴充排程能力，來滿足特殊業務場景的排程需求。

“ 阿裡巴巴雲原生 關注微服務、Serverless、容器、Service Mesh 等技術領域、聚焦雲原生流行技術趨勢、雲原生大規模的落地實踐，做最懂雲原生開發者的技術圈。”