标签：

chedulingQueue是kubernetes scheduler中卖力进行期待调理pod存储的对，Scheduler通过SchedulingQueue来获取当前系统中期待调理的Pod，本文主要讨论SchedulingQueue的设计与实现的各类实现, 了解探究其内部实现与底层源码,本系列代码基于kubernets1.1.6分析而来

SchedulingQueue设计 行列队伍与优先级 行列队伍与场景 类型 描述 凡是实现
行列队伍   普通行列队伍是一个FIFO的数据布局，按照元素入队的序次依次出队   数组或者链表  
优先级行列队伍   优先级行列队伍凡是是指按照某些优先级计谋，高优先级会优先被获取   数组或者树  

其实在大大都的调理场景中，大多都是给与优先级行列队伍来实现，优先满足优先级对照高的任务或者需求，从而减少后续高优先级对低优先级的抢占，scheduler中也是如此

优先级的选择

k8s中调理的单元是Pod，scheduler中按照pod的优先级的凹凸来进行优先级行列队伍的构建, 这个其实是在kubernets的adminission准入插件中，会为用户创建的pod按照用户的设置，进行优先级字段的计算

三级行列队伍 勾当行列队伍

勾当行列队伍存储当前系统中所有正在期待调理的行列队伍

不成调理行列队伍

当pod的资源在当前集群中不能被满足时，则会被插手到一个不成调理行列队伍中，然后期待稍后再进行测验考试

backoff行列队伍

backoff机制是并发编程中常见的一种机制，即如果任务重复执行依旧掉败，则会递次增长期待调理时间，降低重试效率，从而制止重复掉败浪费调理资源

针对调理掉败的pod会优先存储在backoff行列队伍中，期待后续重试

梗阻与抢占 梗阻设计

当行列队伍中不存在期待调理的pod的时候，会梗阻scheduler期待有需要调理的pod的时候再唤醒调理器，获取pod进行调理

抢占相关

nominatedPods存储pod被提议运行的node,主要用于抢占调理流程中使用，本节先不分析

源码分析 数据布局

kubernetes中默认的schedulingQueue实现是PriorityQueue，本章就以该数据布局来分析

type PriorityQueue struct { stop <-chan struct{} clock util.Clock // 存储backoff的pod计时器 podBackoff *PodBackoffMap lock sync.RWMutex // 用于协调通知因为获取不到调理pod而梗阻的cond cond sync.Cond // 勾当行列队伍 activeQ *util.Heap // backoff行列队伍 podBackoffQ *util.Heap // 不成调理行列队伍 unschedulableQ *UnschedulablePodsMap // 存储pod和被提名的node, 实际上就是存储pod和建议的node节点 nominatedPods *nominatedPodMap // schedulingCycle是一个调理周期的递增序号，当pod pop的时候会递增 schedulingCycle int64 // moveRequestCycle缓存schedulingCycle, 当未调理的pod从头被添加到activeQueue中 // 会生存schedulingCycle到moveRequestCycle中 moveRequestCycle int64 closed bool }

PriorityQueue作为实现SchedulingQueue的实现，其核心数据布局主要包罗三个行列队伍:activeQ、podBackoffQ、unscheduleQ内部通过cond来实现Pop操纵的梗阻与通知，接下来先分析核心的调理流程，最后再分析util.Heap里面的具体实现

activeQ

存储所有期待调理的Pod的行列队伍，默认是基于堆来实现，此中元素的优先级则通过比拟pod的创建时间和pod的优先级来进行排序

// activeQ is heap structure that scheduler actively looks at to find pods to // schedule. Head of heap is the highest priority pod. activeQ *util.Heap

优先级对照函数

// activeQComp is the function used by the activeQ heap algorithm to sort pods. // It sorts pods based on their priority. When priorities are equal, it uses // PodInfo.timestamp. func activeQComp(podInfo1, podInfo2 interface{}) bool { pInfo1 := podInfo1.(*framework.PodInfo) pInfo2 := podInfo2.(*framework.PodInfo) prio1 := util.GetPodPriority(pInfo1.Pod) prio2 := util.GetPodPriority(pInfo2.Pod) // 首先按照优先级的凹凸进行对照，然后按照pod的创建时间，越高优先级的Pod越被优先调理 // 越早创建的pod越优先 return (prio1 > prio2) || (prio1 == prio2 && pInfo1.Timestamp.Before(pInfo2.Timestamp)) } podbackOffQ

podBackOffQ主要存储那些在多个schedulingCycle中依旧调理掉败的情况下，则会通过之前说的backOff机制，延迟期待调理的时间

// podBackoffQ is a heap ordered by backoff expiry. Pods which have completed backoff // are popped from this heap before the scheduler looks at activeQ podBackoffQ *util.Heap podBackOff

上面提到podBackOffQ行列队伍中并没有存储pod的backOff的具体信息，好比backoff的计数器，最后一次更新的时间等，podBackOff则类似一个记分板，记录这些信息，供podBackOffQ使用

// podBackoff tracks backoff for pods attempting to be rescheduled podBackoff *PodBackoffMap // PodBackoffMap is a structure that stores backoff related information for pods type PodBackoffMap struct { // lock for performing actions on this PodBackoffMap lock sync.RWMutex // initial backoff duration initialDuration time.Duration // 当前值是1秒 // maximal backoff duration maxDuration time.Duration // 当前值是1分钟 // map for pod -> number of attempts for this pod podAttempts map[ktypes.NamespacedName]int // map for pod -> lastUpdateTime pod of this pod podLastUpdateTime map[ktypes.NamespacedName]time.Time } unschedulableQ

存储已经测验考试调理但是当前集群资源不满足的pod的行列队伍

moveRequestCycle