這篇文章是基於 Kubernetes 的 master commitid: 8e8b6a01cf6bf55dea5e2e4f554597a95c82988a 寫下的源碼分析文檔。
Kubernetes 作為一個資源管理平臺，其中一個關鍵的組件是調度器，而調度的核心，是要將有限的資源利用最大化。調度在 Kubernetes 裡面是 Kube-scheduler 組件實現的。Kube-scheduler 的主要邏輯在於，如何為集群中的每一個新創建的 Pod 或者沒有被調度的 Pod 找到合適的節點。
帶著問題出發問題 1：
調度器如何平衡準確性和效率性？
準確性的話一般在業務處理裡面會用到串行調度，對每一個 Pod 對象進行串行調度，等該對象調度完成再動下一個，但眾所周知，一個 Pod 需要在節點上啟動，綁定 IP 和磁碟等資源，如果單純串行調度，是很難提高效率，符合業務需求，假設是並行調度的話，如何保證每一次調度決策的準確性？例如調度決策將同一個 Node 資源同時分配給兩個不同的 Pod，可能會出現在綁定階段的另外一個 Pod 會因為資源不足而無法創建該 Pod。
問題 2：
當出現 Kubernetes 集群 Node 節點數量非常大，例如 5000 個節點，調度器為一個 Pod 對象選擇 Node 節點時候，是如何從這 5000 個節點中選出最優解？如若每一個 Pod 對象都輪詢 5000 個節點，調度器在進行調度的時候如何提高做出決策的時間（優化）？
問題 3：
作為調度器，Kubernetes 的調度器應該提供一些比較公共的調度算法，但每個公司都有特定的調度需求，雲廠商會有希望進行資源超賣之類的調度需求，作為使用者的企業或者個人應該如何擴展調度器實現定製化調度需求？
流程概述Kubernetes 的調度器的一個總的調度流程：
Pod 對象被加入到調度器的隊列裡面， 調度器從「調度器隊列」中獲取 Pod 對象。首先在調度器經過一輪預選，選出符合該 Pod 對象資源要求的一組 Node 節點列表。將符合 Pod 對象的 Node 節點列表再篩選一遍，在篩選環節根據親和性或者資源均衡性等對 Node 節點列表進行打分，返回 Node 節點以及對應的分數。選出最高分的節點 Node，異步進行綁定Volume，如果綁定環節失敗，那麼將解綁 Node 節點以及資源。如果在 4 或者 5 失敗，也就是無法選出符合 Pod 對象的 Node，那麼進入搶佔環節，擠兌低優先級的 Pod 對象去搶佔 Node 節點。實際上，圍繞著整個調度過程，在目前的 Kubernetes 版本中，Scheduler framework 在每一個調度階段發揮著緊密的作用，Scheduler framework 把每一個階段都做成一組插件。每一組插件都可以 Enabled 或者 Disabled。
在 Kubernetes v1.18 以及之後的版本裡面，大部分的調度 plugins 都是默認 Enabled，用戶也可以配置 Disable 某組插件，Plugin 都有一個名字和對應的權重。在每一個調度階段提供了基於插件式的接口，這些插件實現了絕大部分的調度功能。
調度框架通過插件的機制去接受插件的結果，根據插件結果去繼續下一個步驟或者停止調度，這種機制允許我們處理錯誤並且也可以與插件通信。
從下圖可以看出，Scheduler framework 實現了兩個階段：調度周期和綁定周期。綠色所在箭頭，Scheduler framework 都提供了擴展接口供用戶擴展調度需求。接下來，我們會跟著一個 Pod 被調度的流程概述，詳細分析在每一個階段裡面調度器的操作。
當我們往集群裡面新增一個 Pod 對象的時候，Informer的EventHandler會觸發將該 Pod 對象加入到調度器的 activeQ 調度隊列中進行入隊操作。
func addAllEventHandlers(...) {
podInformer.Informer().AddEventHandler(
cache.FilteringResourceEventHandler{
Handler: cache.ResourceEventHandlerFuncs{
AddFunc: sched.addPodToSchedulingQueue,
UpdateFunc: sched.updatePodInSchedulingQueue,
DeleteFunc: sched.deletePodFromSchedulingQueue,
},
},
)
...
}
func (sched *Scheduler) addPodToSchedulingQueue(obj interface{}) {
pod := obj.(*v1.Pod)
if err := sched.SchedulingQueue.Add(pod); err != nil {...}
}
func (p *PriorityQueue) Add(pod *v1.Pod) error {
pInfo := p.newQueuedPodInfo(pod)
// 當新增一個Pod對象的時候，Eventhandler會將該Pod對象執行Add的操作，然後調用了activeQ.Add去把該Pod對象加到activeQ裡面
if err := p.activeQ.Add(pInfo); err != nil {
return err
}
...
}
Step2: 入隊調度器是定時的從調度隊列裡面獲取隊頭的一個 Pod 對象podInfo := sched.NextPod()，也就是，每次只獲取一個 Pod 對象，這個過程是阻塞的，當隊列中不存在 Pod 對象的時候，sched.NextPod()會處於等待狀態。
在沒有看源碼之前，我個人想像中存放 Pod 的調度隊列是使用 Channel 實現的，然後是直接就可以使用先進先出的功能，看了代碼之後發現如果使用 Channel 的話是無法對已經進入隊列裡面的 Pod 對象進行排序，Kubernetes 設計的調度隊列是讓高優先級的排在隊列的對頭，低優先級的被排在隊尾，設計成需要在隊列裡面排隊是為了符合業務需求高優先級的 Pod 應用需要優先被得到調度處理。
在隊列的最前面是最高優先級的 pod，隊列裡面是有使用對 Pod 進行排序的，那就是 Less 方法（見下方的代碼）， Less 是根據 Pod 的優先級來進行比較，也就是說，每次進入調度周期的時候，每取出一個 Pod，實際上都是取優先級最高的 Pod 先進行調度 （當優先級相等時，它使用 PodQueueInfo.timestamp）
這裡使用了 Scheduler framework 的隊列插件中提供的"Less(Pod1, Pod2)" 方法來實現。
func (pl *PrioritySort) Less(pInfo1, pInfo2 *framework.QueuedPodInfo) bool {
p1 := pod.GetPodPriority(pInfo1.Pod)
p2 := pod.GetPodPriority(pInfo2.Pod)
return (p1 > p2) || (p1 == p2 && pInfo1.Timestamp.Before(pInfo2.Timestamp))
}
而這個時候，調度器只是在操作一個 Pod 對象，讓我們接下來繼續看看，調度器是如何提高調度效率呢？
Step3: 預選在預選裡面，調用了numFeasibleNodesToFind去尋找 Node 節點數量的函數，如果記得我們問題 2 裡面，如果我們有 5000 個節點，那麼調度器是查詢所有節點嗎？
答案是有一個叫percentageOfNodesToScore 的變量，接收從 0 到 100 之間的整數值，而且其默認值是通過集群的規模計算得來的。該變量是用來設置調度集群中節點的閾值。調優的時候我們應該根據我們的節點數量對這個值進行一個合理的設置。如果我們不指定，那麼 Kubernetes 會使用公式計算一個比例：在 100 左右的節點數量取 50%，在 5000 左右的節點數量取 10%。
也就是說Kubernetes 調度是存在全局最優解和局部最優解兩種解法，這取決於集群 Node 節點大小與percentageOfNodesToScore 值的設置。
func (g *genericScheduler) findNodesThatPassFilters(...) {
allNodes, err := g.nodeInfoSnapshot.NodeInfos().List()
numNodesToFind := g.numFeasibleNodesToFind(int32(len(allNodes)))
feasibleNodes := make([]*v1.Node, numNodesToFind)
checkNode := func(i int) {
// 我們從上一個調度周期中停止的地方開始檢查節點
nodeInfo := allNodes[(g.nextStartNodeIndex+i)%len(allNodes)]
fits, status, err := PodPassesFiltersOnNode(ctx, prof.PreemptHandle(), state, pod, nodeInfo
...
}
// 並行對所有的Node進行檢查
parallelize.Until(ctx, len(allNodes), checkNode)
processedNodes := int(feasibleNodesLen) + len(statuses)
g.nextStartNodeIndex = (g.nextStartNodeIndex + processedNodes) % len(allNodes)
// 一旦配置的可行節點數量達到，就停止搜索更多的節點
feasibleNodes = feasibleNodes[:feasibleNodesLen]
if err := errCh.ReceiveError(); err != nil {
statusCode = framework.Error
return nil, err
}
return feasibleNodes, nil
}
代碼裡面的g.nextStartNodeIndex值得大家注意，打個比喻來說第一個 Pod 如果是使用了 1000 個節點（Node[0] 到 Node[999] ）進行過濾，那麼下一個 Pod 是從 Node[1000]開始取，這是從公平性出發去確保所有節點都有相同的機會跨 pods 進行檢查。如果在一定比例的節點數量中，仍然沒有找到符合條件的節點，那麼進入搶佔環節。
現在讓我們看看在預選階段，Scheduler framework 使用的預選插件檢查匯總：
預選算法描述nodeunschedulable檢查 Node 是否可調度noderesources檢查 Node 資源是否符合 Pod 的需求nodename檢查 Pod.Spec.NodeName 是否符合目前的 Node 節點nodeports檢查 Node 是否跟 Pod 需要暴露的埠有衝突nodeaffinity檢查節點親和性tainttoleration檢查汙點容忍性，例如節點 Node 帶上某些汙點標籤，Pod 是否可以容忍nodevolumelimits檢查 Node 的卷是否達到限制volumebinding檢查卷的綁定情況volumezone檢查卷所在的 ZoneinterpodaffinityPod 的親和性檢查，例如需要調度的 Pod 跟節點上的 Pod 是否有 prefer 親和性需要被調度的 Pod 在經過預選環節，會返回一個經過過濾篩選符合需求的 Node 列表，
當列表長度<=0 意味著沒有 Node 節點符合 Pod 的需求，不再進入打分環節，直接認為調度失敗，進入 Step6
當列表長度=1 意味著只有一個 Node 節點符合 Pod 的需求，不再進入打分環節，把該 Node 進行 Step5 的綁定環節
當列表長度大於 2 會進入下方的打分環節。
Step4: 打分在打分環節，仍然是使用了 Scheduler framework 的一組插件：評分插件。
評分插件用於對通過預選的階段的所有 Node 進行排名，調度器將為每個節點都調用所有評分插件。對於每一個評分插件，Scheduler framework 都給與他們對應的權重 Weight，如下方代碼所示。
當評分完成之後，調度器使用了數學公式：乘積，也就是節點在每一個評分插件得出的分數*權重，再把所有分數合併才是節點的最後分數。
// 代碼位置`pkg/scheduler/algorithmprovider/registry.go`
Score: &schedulerapi.PluginSet{
Enabled: []schedulerapi.Plugin{
// 尋找資源使用率平衡的節點
{Name: noderesources.BalancedAllocationName, Weight: 1},
// 基於節點上是否下拉了運行Pod對象的鏡像計算分數
{Name: imagelocality.Name, Weight: 1},
// 基於親和性和反親和性計算分數
{Name: interpodaffinity.Name, Weight: 1},
// 基於節點親和性計算分數
{Name: nodeaffinity.Name, Weight: 1},
{Name: nodepreferavoidpods.Name, Weight: 10000},
// 基於汙點和容忍度是否匹配分數
{Name: tainttoleration.Name, Weight: 1},
...
},
},
在打分環節完成之後會返回 NodeScoreList 的列表，調度器會selectHost方法從返回結果中為 Pod 對象綁定一個 Node 節點。
至此調度周期完成，調度器進入下一個周期：綁定周期。
Step5: 綁定現在調度器進入了綁定周期，使用了 go rountine 異步去執行 bind 去把 Pod 對象與節點 Node 進行綁定，不需要等待 bind 完成就可以進行下一個 Pod 對象的調度。這也就是理解了，Kubernetes Scheduler 是選擇串行調度去保證準確性的同時，然後以異步的方式去做綁定去提高效率。
如果綁定失敗，調度器會自動執行回滾操作。
在綁定周期，實際上是為 Pod 對象進行綁定 Volume 的操作。而綁定周期裡面，是可以細分成三個階段的：
預綁定預綁定插件用於執行 Pod 綁定前所需的任何工作。例如，一個預綁定插件可能需要提供卷並且在允許 Pod 運行在該節點之前將其掛載到目標節點上。
如果任何 PreBind 插件返回錯誤，則 Pod 將被拒絕並且返回到調度隊列中被重新等待下一次調度。
綁定綁定插件用於將 Pod 綁定到節點上。直到所有的 PreBind 插件都完成，綁定插件才會被調用。每個綁定插件按照配置順序被調用。綁定插件可以選擇是否處理指定的 Pod。如果綁定插件選擇處理 Pod，剩餘的綁定插件將被跳過。
func (b DefaultBinder) Bind(ctx context.Context, state *framework.CycleState, p *v1.Pod, nodeName string) *framework.Status {
binding := &v1.Binding{
ObjectMeta: metav1.ObjectMeta{Namespace: p.Namespace, Name: p.Name, UID: p.UID},
Target: v1.ObjectReference{Kind: "Node", Name: nodeName},
}
err := b.handle.ClientSet().CoreV1().Pods(binding.Namespace).Bind(ctx, binding, metav1.CreateOptions{})
return nil
}
從代碼裡面我們可以看出，Bind綁定實際上是通過調 ClientSet 去調 API Server 把 Pod 對象的 Node 信息加到 Pod 的 ObjectMeta， 如果在此刻發生 API Server 故障等，是會綁定失敗的，一旦綁定失敗，就會觸發運行un-reserve插件，去把之前預留給該 Pod 對象的資源釋放。
綁定後綁定插件用於將 Pod 綁定到節點上。直到所有的 PreBind 插件都完成，綁定插件才會被調用。每個綁定插件按照配置順序被調用。綁定插件可以選擇是否處理指定的 Pod。如果綁定插件選擇處理 Pod，剩餘的綁定插件將被跳過。
至此綁定周期完成。
Step6: 搶佔在上方我們提起到，當 Pod 對象在預選環節失敗的時候，會進入搶佔環節，企圖搶佔其他 Pod 對象的資源。這是從業務需求出發，我們希望我們優先級高的應用需要被調度成功。而搶佔，仍然是作為 Scheduler framework 的一組插件：PostFilter
PostFilter: &schedulerapi.PluginSet{
Enabled: []schedulerapi.Plugin{
{Name: defaultpreemption.Name},
},
},
搶佔算法流程：
判斷當前的 Pod 對象是否優先級比節點裡面其他 Pod 對象優先級高，從而判斷是否有資格搶佔
從經過 3 完成的節點裡面中選擇一個階段用於最終被搶佔，也就是被搶佔節點
獲取被搶佔節點的所有 NominatedPods 列表
附：擴展調度器Kubernetes 調度器有三個擴展點：
Multiple scheduler: 需要用戶自己實現一個調度器，開發成本比較大，允許與默認的調度器一起運行在 Kubernetes 集群中Extender: 只有 Filter、Proritize、Preempt 和 Bind 這幾個擴展點，是基於 HTTP/HTTPS 通過網絡調用，會有一定的網絡延時，並且由於 Extender 是獨立運行的，不能使用 Scheduler Cache從上方整個流程可以看出，Scheduler framework 貫穿了調度器的每一個調度階段， 他設計很多都值得我們參考，基於插件式的調度框架分層的將過濾和打分和搶佔都做成不同層級別的插件，被編譯進調度器中，我們可以擴展某個插件，並且不影響與上下遊插件的通信。