本文重点分析Kubernetes 1.10版本抢占式调度和优先级队列。在Kubernetes 1.8 以前，scheduler中是没有抢占式调度的，调度流程也很简单，从FIFO queue中Pop出一个pod，进行调度，失败了就重新加入queue（为了减轻scheduler的压力，有back off的机制），等待下次调度。
这样就导致一下几个问题：
即使有back off的机制，但是在大规模集群中，Pending容器较多的时候，会影响新容器的调度速度。并且pod重新加入queue的逻辑过于简单，试想当集群资源已经满负荷时，是否有必要再调度失败后反复的重新加入queue
没有抢占调度会导致集群满负荷时，重要的高优先级的应用无法调度成功，只能人工去释放资源。
调度流程
调度的主要流程在kubernetes\cmd\kube-scheduler\scheduler.go中
- 从FIFO queue或者priority queue中Pop出一个pod
pod := sched.config.NextPod()
-
调度该pod
suggestedHost, err := sched.schedule(pod) -
如果调度失败，进入抢占式调度流程
if err != nil { **** if fitError, ok := err.(*core.FitError); ok { preemptionStartTime := time.Now() sched.preempt(pod, fitError) **** } return } -
假定调度，scheduler加速调度速度的机制，这里不再赘述
err = sched.assume(assumedPod, suggestedHost) -
将该pod和选定的node绑定
err := sched.bind(assumedPod, &v1.Binding{ ObjectMeta: metav1.ObjectMeta{Namespace: assumedPod.Namespace, Name: assumedPod.Name, UID: assumedPod.UID}, Target: v1.ObjectReference{ Kind: "Node", Name: suggestedHost, }, })
抢占调度关键流程
在上面的调度流程中，如果调度失败，进入抢占流程
-
首先判断该pod有资格进行抢占
func podEligibleToPreemptOthers()如果该pod已经有NominatedNodeName 了，并且这个Node上有比该pod优先级更低的pod正在Terminating，则流程结束。
-
筛选出可能可以进行抢占的node节点
for _, failedPredicate := range failedPredicates { switch failedPredicate { case predicates.ErrNodeSelectorNotMatch, predicates.ErrPodNotMatchHostName, predicates.ErrTaintsTolerationsNotMatch, predicates.ErrNodeLabelPresenceViolated, predicates.ErrNodeNotReady, predicates.ErrNodeNetworkUnavailable, predicates.ErrNodeUnschedulable, predicates.ErrNodeUnknownCondition, predicates.ErrVolumeZoneConflict, predicates.ErrVolumeNodeConflict, predicates.ErrVolumeBindConflict: unresolvableReasonExist = true break // TODO(bsalamat): Please add affinity failure cases once we have specific affinity failure errors. } }只要不是以上这些情况的node，均可以
-
计算出每台node上的victims
- 遍历每台node节点上比改pod优先级低的pod，加入potentialVictims，并且移除他们所占用的资源（仅在内存中移除）
- 将potentialVictims按优先级从高到低排序
- 在这种状态下对pod进行podFitsOnNode，如果不通过，说明即使把所有低优先级的pod都驱逐掉，该pod也调度不上来，那么说明该node不适合，返回，否则继续。
- 将potentialVictims根据PDB筛选成violatingVictims和nonViolatingVictims（PDB是kubernetes中保证应用高可用的一种资源）
- 分别遍历violatingVictims和nonViolatingVictims（其中要记录numViolatingVictim，下一步选择最终node时会作为依据）。因为之前的排序，所以从高优先级pod开始，将victim占用的资源加回去，然后用podFitsOnNode检查该pod是否可以调度上来，如果不可调度了，就将该pod正式加入victims。因为排序，也尽量保留了高优先级的pod
-
从上一步的nodes中选出一个node，具体规则如下。
- node上numViolatingVictim数最低的那个，也就是尽量较少的影响PDB
- 选择victims中最高pod优先级最低的那个Node
- 选择优先级之和最小的node
- 选择victims pod数最少的Node
- 如果这个时候还有不止一个node满足，那么random大法
获取该node的nominatedPods中比该pod低优先级的pods作为nominatedPodsToClear，设置该pod的NominatedNodeName，删除victims，清除nominatedPodsToClear中pod的NominatedNodeName字段，更新到etcd，因为这些之前抢占的pod已经不适合在调到该node上了
优先级队列
在1.10版本中，初始化podQueue的时候会根据配置选择创建FIFO queue还是PriorityQueue
func NewSchedulingQueue() SchedulingQueue {
if util.PodPriorityEnabled() {
return NewPriorityQueue()
}
return NewFIFO()
}
我们这里只介绍PriorityQueue，下面是PriorityQueue的数据结构
type PriorityQueue struct {
lock sync.RWMutex
cond sync.Cond
// activeQ is heap structure that scheduler actively looks at to find pods to
// schedule. Head of heap is the highest priority pod.
activeQ *Heap
// unschedulableQ holds pods that have been tried and determined unschedulable.
unschedulableQ *UnschedulablePodsMap
// nominatedPods is a map keyed by a node name and the value is a list of
// pods which are nominated to run on the node. These are pods which can be in
// the activeQ or unschedulableQ.
nominatedPods map[string][]*v1.Pod
// receivedMoveRequest is set to true whenever we receive a request to move a
// pod from the unschedulableQ to the activeQ, and is set to false, when we pop
// a pod from the activeQ. It indicates if we received a move request when a
// pod was in flight (we were trying to schedule it). In such a case, we put
// the pod back into the activeQ if it is determined unschedulable.
receivedMoveRequest bool
}
type UnschedulablePodsMap struct {
// pods is a map key by a pod's full-name and the value is a pointer to the pod.
pods map[string]*v1.Pod
keyFunc func(*v1.Pod) string
}
activeQ
activeQ是一个有序的Heap结构，Pop时会弹出最高优先级的Pending Pod。
unscheduableQ
主要是一个Map，key为pod.Name + "_" + pod.Namespace，value为那些已经尝试调度并且调度失败的UnSchedulable的Pod。
nominatedPods
nominatedPods表示已经被该node提名的，期望调度在该node上的，但是又还没最终成功调度过来的Pods。
nominatedPods的作用是防止高优先级的Pods进行抢占调度时删除了低优先级Pods--->再次调度，在这段时间内，抢占的资源又被低优先级的Pods占用了。
- podFitsOnNode的时候，会有2次predicate。
- 第一次的时候，如果发现该node上有nominatedPods，则将nominatedPods中大于等于该pod优先级的pod的资源加入node上，使用修改过的nodeinfo进行一次predicate，作用就是保证高优先级的pod在上面所述的这段时间里资源不被占用
- 第二次的时候，会用原始的nodeinfo进行一次predicate。
receivedMoveRequest
从activeQ中Pop出pod时，会将receivedMoveRequest置为false。
-
某些事件发生时，会将pod从unschedulableQ -> activeQ，此时会将receivedMoveRequest置为true。
当调度发生Error时，会尝试将UnSchedulable Pod重新加入unSchedulableQ 或者activeQ中。判断的依据就是receivedMoveRequest 。
当receivedMoveRequest为false并且该Pod Condition Status为False或者Unschedulable时，会将该Pod Add或者Update到unschedulableQ。否则加到activeQ中。
if !p.receivedMoveRequest && isPodUnschedulable(pod) {
p.unschedulableQ.addOrUpdate(pod)
p.addNominatedPodIfNeeded(pod)
return nil
}
err := p.activeQ.Add(pod)
if err == nil {
p.addNominatedPodIfNeeded(pod)
p.cond.Broadcast()
}
其实目的就是当pod从unschedulableQ -> activeQ时，意味着集群可能有资源了，然后就直接加入activeQ，不用先进unSchedulableQ 了，算是一个优化
各类event涉及的queue操作
scheduled pod cache
-
add pod
将unschedulableQ中和该pod有affinity的pods加入activeQ
-
update pod
和add pod类似
-
delete pod
将unschedulableQ中的pod全部加到activeQ中
unscheduled pod queue
-
add pod
将pod加入activeQ
-
update pod
首先判断是否需要更新：
pod已经assumed
pod只有ResourceVersion, Spec.NodeName， Annotations发生了更新
以上情况下都不需要更新。
如果需要更新：
- 如果pod已经在activeQ里了，更新。
- 如果pod在unschedulableQ中，首先查看该pod是不是做了“有效的”更新，如果是，加入activeQ。（这种pod加入activeQ中还有希望被调度成功）。如果不是，直接更新unschedulableQ中的pod。
- 如果这两个队列里都没有，加入activeQ
-
delete pod
NominatedPod删除
从activeQ和unschedulableQ中找到，删除。
node event
-
add node
说明有资源加进来了，将所有unschedulableQ中的pod加入activeQ
-
update node
和上面一样
-
delete node
没操作
service event
- service的所有事件都会触发所有unschedulableQ中的pod加入activeQ
pvc event
- pvc的add和update事件都会触发所有unschedulableQ中的pod加入activeQ
