kubernetes scheduler抢占调度和优先级队列

2018-08-01 本文已影响0人午时已呃啊

本文重点分析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，具体规则如下。
1. node上numViolatingVictim数最低的那个，也就是尽量较少的影响PDB
2. 选择victims中最高pod优先级最低的那个Node
3. 选择优先级之和最小的node
4. 选择victims pod数最少的Node
5. 如果这个时候还有不止一个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