第 19 课时：调度器的调度流程和算法介绍（木苏）
本文將主要分享以下四個部分的內容：
調度流程
調度流程概覽
首先來看一下調度器流程概覽圖：
調度器啟動時會通過配置文件 File，或者是命令行參數，或者是配置好的 ConfigMap，來指定調度策略。指定要用哪些過濾器 (Predicates)、打分器 (Priorities) 以及要外掛哪些外部擴展的調度器 (Extenders)，和要使用的哪些 Schedule 的擴展點 (Plugins)。
啟動的時候會通過 kube-apiserver 去 watch 相關的數據，通過 Informer 機制將調度需要的數據 ：Pod 數據、Node 數據、存儲相關的數據，以及在搶占流程中需要的 PDB 數據，和打散算法需要的 Controller-Workload 數據。
調度算法的流程大概是這樣的：通過 Informer 去 watch 到需要等待的 Pod 數據，放到隊列里面，通過調度算法流程里面，會一直循環從隊列里面拿數據，然后經過調度流水線。
調度流水線 (Schedule Pipeline) 主要有三個組成部分：
在整個循環過程中，會有一個串行化的過程：從調度隊列里面拿到一個 Pod 進入到 Schedule Theread 流程中，通過 Pre Filter--Filter--Post Filter--Score(打分)-Reserve，最后 Reserve 對賬本做預占用。
基本調度流程結束后，會把這個任務提交給 Wait Thread 以及 Bind Thread，然后 Schedule Theread 繼續執行流程，會從調度隊列中拿到下一個 Pod 進行調度。
調度完成后，會去更新調度緩存 (Schedule Cache)，如更新 Pod 數據的緩存，也會更新 Node 數據。以上就是大概的調度流程。
調度詳細流程
接下來講解一下調度的詳細流程。
調度的詳細流程中，調度隊列分成三個隊列：activeQ、backoffQ、unschedulableQ。
首先都會從 activeQ 里面 pop 一個 Pod 出來，然后經過調度流水線去調度。拿到一個等待調度的 Pod，會從 NodeCache 里面拿到相關的 Node 數據，這里有一個非常有意思的算法，就是 NodeCache 這里，在過濾階段，調度器提供一種能力：可以不用過濾所有節點，取到最優節點。可通過調度器提供的取樣能力，通過配置這個比例來拿到部分節點進行過濾及打分，然后選中節點進行 bind 流程。
提供這種能力需要在 NodeCache 里面注意一點，NodeCache 選中的節點需要足夠分散，也就意味著容災能力的增強。
在 NodeCache 中，Node 是按照 zone 進行分堆。在 filter 階段的時候，為會 NodeCache 維護一個 zondeIndex，每 Pop 一個 Node 進行過濾，zoneIndex 往后挪一個位置，然后從該 zone 的 node 列表中取一個 node 出來。可以看到上圖縱軸有一個 nodeIndex，每次也會自增。如果當前 zone 的節點無數據，那就會從下一個 zone 中拿數據。大概的流程就是 zoneIndex 從左向右，nodeIndex 從上到下，從而保證拿到的 Node 節點是按照 zone 打散，從而保證了在優化開啟之后的容災。
看一下過濾中的 Filter 和 Score 之間的 isEnough，就是剛才說過的取樣比例。如果取樣的規模已經達到了我們設置的取樣比例，那 Filter 就會結束，不會再去過濾下一個節點。 然后過濾到的節點會經過打分器，打完分后會選擇最優節點作為 pod 的分配位置。
分配 Pod 到 Node 的時候，需要對 Node 的內存做處理，將這個 Pod 分配到這個 Node 上，這個過程可以稱呼為賬本預占。 預占的過程會把 Pod 的狀態標記為 Assumed 的狀態(處于內存態)，緊接著就進入 bind 階段，調用 kube-apiserver 將 Pod 的 NodeName 持久化到 etcd，這個時候 Pod 的狀態還是 Assumed。只有在通過 Informer watch 到 Pod 數據已經確定分配到這個節點的時候，才會把狀態變成 Added，Pod 調度生命周期大概是這樣。
選中完節點在 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，大概是這么一個機制。
unschedulableQ 里面的機制是：如果這個 Pod 一分鐘沒調度過，到一分鐘的時候，它會把這個 Pod 重新丟回 activeQ。它的輪訓周期是 30s，調度詳細流程大概是這樣。
取樣規模這里大概介紹一下，它是怎么判斷調度器的節點是足夠的呢？按照默認值來說，默認的是在 [5-50%] 之間，公式為 Max (5,50 - 集群的 node 數 / 125)。為什么公式是這樣的呢？大家有興趣的可以自己查一下。
這里舉個例子：假如配置比率是 10%，節點規模為 3000 個節點，需要待選的節點數 Max(3000 * 10/100,100)，最后得到的值是 300，跟 100 進行比較，100 默認是得到節點最小需要值。300 大于 100，那就按照 300 節點。在調度流水線里面，Filter 只要過濾到 300 個候選節點，就可以停止 Filter 流程了。
調度算法實現
Predicates (過濾器)
首先介紹一下過濾器，它可以分為四類：
存儲相關
簡單介紹下存儲相關的幾個過濾器的功能：
Pod 和 Node 匹配相關
Pod 和 Pod 匹配相關
MatchinterPodAffinity：主要是 PodAffinity 和 PodAntiAffinity 的校驗邏輯。
Pod 打散相關
EvenPodsSpread
這是一個新的功能特性，首先來看一下 EvenPodsSpread 中 Spec 描述： -- 描述符合條件的一組 Pod 在指定 TopologyKey 上的打散要求。
下面我們來看一下怎么描述一組 Pod，如下圖所示：
描述一組 Pod 的方式是可以通過 matchLabels 和 matchExpressions 來進行描述是否符合條件。
接下來可以描述在這一組 pod，是在哪個 topologyKey 上，比如說可以在一個 zone 級別上，也可以在一個 Node 級別上，然后可以設置 maxSkew：最大允許不均衡的數量。在不均衡的情況下可以設置 whenUnsatisfiable： DoNotSchedule，也就是不允許被調度，也可以選擇隨便調度。在過濾階段，我們只關注 DoNotSchedule (不允許被調度)。
接下來我們看一下它的使用方式：
以上圖中為例子：
假設 matchLabels 過濾的 app 是 foo，在 zone 級別是打散的，最大允許不均衡數為 1。
假設集群中有三個 zone，上圖中 label的值app=foo 的 Pod 在 zone1 和 zone2 中都分配了一個 pod。
計算不均衡數量公式為：ActualSkew = count[topo] - min(count[topo])
首先我們會按照 topo 去分組，然后拿到符合條件的應用數量，最后減去最小的 zone 應用個數，就能算出來不均衡數是多少了。
如上圖所示，假設 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 都是允許被選擇的。
通過這種描述，它最大的用處就是當我們對自己的應用有容災要求的，必須在每一個 zone 上是均衡部署的，這時就可以用這個規則去限定。比如所有的 app 為 foo 的應用 maxSkew 數量為1，那它在每個 zone 上都是均衡的。
Priorities
接下來看一下打分算法，打分算法主要解決的問題就是集群的碎片、容災、水位、親和、反親和等。
按照類別可以分為四大類：
- Node 水位
- Pod 打散 (topp,service,controller)
- Node 親和&反親和
- Pod 親和&反親和
資源水位
接下來介紹打分器相關的第一個資源水位。
節點打分算法跟資源水位相關的主要有四個，如上圖所示。
資源水位公式的概念：
- Request：Node 已經分配的資源
- Allocatable：Node 的可調度的資源
優先打散：
顧名思義，我們應該把 Pod 分到可用資源最大比例的節點上。可用資源最大的公式就是 (Allocatable - Request) / Allocatable * Score。
這個比例就是表示如果這個 Pod 分配到這個 Node 上，還剩余的資源比例越大的話，越優先分配到這個節點上，從而達到打散的要求。
優先堆疊：
Request / Allocatable * Score。考慮的是如果 Pod 分配到 Request 的節點上，使用的資源比例越大，它應該越優先，從而達到優先堆疊。
碎片率：{ 1 - Abs[CPU(Request / Allocatable) - Mem(Request / Allocatable)] } * Score。是用來考慮 CPU 的使用比例和內存使用比例的差值，這個差值就叫做碎片率。如果這個差值越大，就表示碎片越大，優先不分配到這個節點上。如果這個差值越小，就表示這個碎片率越小，那應該優先分配到這個節點上。
指定比率：
我們可以通過打分器，當資源使用的比率達到某個值時，用戶指定配置參數可以指定不同比率的分數，從而達到控制集群上每個節點 node 的分布。
Pod 打散
Pod 打散為了解決的問題為：支持符合條件的一組 Pod 在不同 topology 上部署的 spread 需求。
SelectorSpreadPriority
首先來介紹 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 分配的權重，如果說這個值越大，表示這個值越優先。
Node 親和&反親和
NodeAffinityPriority，這個是為了滿足 Pod 和 Node 的親和 & 反親和；
ServiceAntiAffinity，是為了支持 Service 下的 Pod 的分布要按照 Node 的某個 label 的值進行均衡。比如：集群的節點有云上也有云下兩組節點，我們要求服務在云上云下均衡去分布，假設 Node 上有某個 label，那我們就可以用這個 ServiceAntiAffinity 進行打散分布；
NodeLabelPrioritizer，主要是為了實現對某些特定 label 的 Node 優先分配，算法很簡單，啟動時候依據調度策略 (SchedulerPolicy）配置的 label 值，判斷 Node 上是否滿足這個label條件，如果滿足條件的節點優先分配;
ImageLocalityPriority，節點親和主要考慮的是鏡像下載的速度。如果節點里面存在鏡像的話，優先把 Pod 調度到這個節點上，這里還會去考慮鏡像的大小，比如這個 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 啟動起來。
本節總結
本節課的主要內容就到此為止了，謝謝大家觀看。這里為大家簡單總結一下：
總結
以上是生活随笔為你收集整理的第 19 课时：调度器的调度流程和算法介绍（木苏）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 课时 18-Kubernetes 调度和
- 下一篇： 课时 18 自测题