Kubernetes是一个容器编排引擎，它被设计为在被称为集群的节点上运行容器化应用。通过系统建模的方法，本系列文章的目的是为了能够深入了解Kubernetes以及它的深层概念。
Kubernetes Scheduler是Kubernetes的一个核心组件：在用户或者控制器创建一个Pod后，Scheduler在对象存储数据里监控未被分配的Pod，并将Pod分配到某个节点。然后Kubelet在对象存储数据里监控已分配的Pod，并运行该Pod。
本文提供了一个Kubernetes Scheduler的更简洁、更详细的模型表述。该模型部分基于TLA+规范。
图 1. Pod处理流程
调度
Kubernetes Scheduler的任务是选择一个placement(位置)。一个placement是一个部分的，非内射的Pod集合到节点集合的分配。
图 2. 调度示例
调度是一个最优化问题：首先，Scheduler确定feasible placements(可用的位置)，这些是满足给定约束的placement集合。然后，Scheduler确定viable placements(可行的位置)，这些是得分最高的feasible placements集合。
图 3. Possible(可能), Feasible(可用)和Viable(可行)的调度
Kubernetes Scheduler是一个保证局部最优解的多步调度器，而不是一个保证全局最优解的单步调度器。
图 4. 多步 vs. 单步
Kubernetes Scheduler
图 5. Kubernetes Pod对象和Node对象
图5描述了Kubernetes Scheduler所感兴趣的Kubernetes对象和属性。在Kubernetes里： * 一个Pod表示为一个Kubernetes Pod对象 * 一个Node表示为一个Kubernetes Node对象 * 一个Pod分配给一个Node表示为Pod的Spec.NodeName属性
BoundTo(Pod, Node, Snapshot)≝ ∧ Pod ∈Snapshot ∧Pod.Kind = "Pod" ∧ Node∈ Snapshot ∧Node.Kind = "Node" ∧Pod.Spec.NodeName = Node.Name Bound(Pod, Snapshot) ≝ ∃ Node∈ Snapshot: BoundTo(Pod, Node, Snapshot)
如果一个Pod的Spec.NodeName等于一个Node的Name，则表示这个Pod对象绑定到了这个Node对象。
Kubernetes Scheduler的任务现在可以更规范地表述为：对于一个Pod p，Kubernetes Scheduler选择一个Node n，且更新(*)这个Pod的Spec.NodeName使得BoundTo(p, n)为true。
控制循环逻辑
Scheduler ≝
LETUnbound ≝ {Pod in Objects : Pod.Kind = "Pod" ∧ ~ Bound(Pod,Objects)} IN
∃ Pod∈ { Pod ∈ Unbound : ∀ Other ∈ Unbound : Other.Spec.Priority ≤ Pod.Spec.Priority}:
CASE SchedulingEnabled(Pod) ⟶ Scheduling(Pod)
[] PreemptionEnabled(Pod) ⟶ Preemption(Pod)
[] OTHER ⟶ UNCHANGED(Objects)
Kubernetes Scheduler监控Kubernetes对象存储并且选择一个未绑定的最高优先级的Pod来执行调度流程或者抢占流程。
调度流程
SchedulingEnabled(Pod) ≝
∃ Node∈ {Node ∈ Objects : Node.Kind = "Node"}:
Feasibility(Pod, Node, Objects)
Scheduling(Pod) ≝
LETFeasibile ≝ {Node ∈ Objects : n.Kind = "Node" ∧ Feasibility(Pod, n,Objects)} IN
∃Node ∈ Feasibile :
∧ ∀Other ∈ Feasibile : Viability(Pod, Other, Objects) ≤ Viability(Pod, Node,Objects)
∧Objects' = {
IF Pod = Object THEN
[Pod EXCEPT !["Spec"] = [Pod.Spec EXCEPT!["NodeName"] = Node.Name]]
ELSE
Object : Object ∈ Objects}
对于一个给定的Pod，如果存在至少一个Node可以运行该Pod，则启用调度流程。
如果调度流程启用，Scheduler将绑定该Pod到一个可选的Node，使得绑定能达到最优的可行性。
如果调度流程未启用，则Sheduler将尝试执行抢占流程。
抢占流程
PreemptionEnabled(Pod) ≝
∃ Node∈ {Node in Objects : Node.Kind = "Node"}:
∃Pods ∈ SUBSET(Jeopardy(Pod, Node, Objects)):
Feasibility(Pod, Node, Objects Pods)
Preemption(Pod) ==
LETPreemptable == {Node ∈ Objects : Node.Kind = "Node" ∧ ∃ Pods ∈SUBSET(Jeopardy(p, Node, Objects)): Feasibility(Pod, Node, Objects Pods)} IN
∃Node ∈ Preemptable:
∃Pods ∈ SUBSET(Jeopardy(Pod, Node, Objects)):
∀OtherNode ∈ qualified:
∀ OtherPods ∈ SUBSET(Jeopardy(Pod, OtherNode, Objects)):
∧ Casualty(Pods) ≤ Casualty(OtherPods)
∧ Objects' = (Objects Pods)
对于一个给定的Pod，如果存在至少一个Node，在删除绑定到该Node的较低优先级Pod子集后可以运行该Pod，则启用抢占流程。
如果抢占流程启用，Scheduler将触发绑定到Node的低优先级Pod子集的删除操作，使得抢占流程造成的损害最小。
(抢占损害是用Pod Disruption Budget来评估的，超出了本文的主题)
注意的是Scheduler不保证触发抢占流程的Pod在后续的调度流程中能绑定到Node。
1. 可用性(Feaisbility)
对于每一个Pod，Kubernetes Scheduler确定可用的Node集合，这些Node满足了该Pod的约束。
从概念上讲，Kubernetes Scheduler定义了一个过滤函数集合。给定一个Pod和一个Node，过滤函数决定该Node是否满足该Pod的约束。所有过滤函数都必须返回true才表示该Node可以运行该Pod。
Feasibility(Pod, Node,Snapshot) == (Filter_1(Pod, Node, Snapshot) ∧ Filter_2(Pod, Node, Snapshot) ∧ ...)
下面小节详细描述了目前一些可用的过滤函数：
1.1 可调度性和生命周期阶段（Schedulability and LifecyclePhase）
该过滤函数基于Node的可调度性和生命周期阶段来确定Node的可用。Nodeconditions通过taints和tolerations来说明(如下所示)。
图 1.1 可调度性和生命周期阶段
Filter(Pod, Node) ≝ * Onlyconsider Nodes that accept new Pods ∧Node.Spec.Unschedulable = False * Onlyconsider Nodes that are ready to accept new Pods (Lifecycle Phase) ∧Node.Status.Phase = "Running"
1.2 资源需求和资源可用性
该过滤函数基于Pod的资源需求和Node的资源可用性来确定Node的可用。
图 1.2 资源需求和资源可用性
Resources(Pod, Node) ≝
∧ 1 ≤Node.Status.Allocatable["pods"]
* Usethe maximum resource requirements of init containers
∧ Max({i in DOMAIN p.Spec.InitContainer :p.Spec.InitContainer[i].Resources.Required["cpu"] }) ≤Node.Status.Allocatable["cpu"]
∧ Max({i in DOMAIN p.Spec.InitContainer :p.Spec.InitContainer[i].Resources.Required["mem"] }) ≤Node.Status.Allocatable["mem"]
∧ ...
* Usethe sum of resource requirements of main containers
∧ Sum({i in DOMAIN p.Spec.Container :p.Spec.Container[i].Resources.Required["cpu"] }) ≤Node.Status.Allocatable["cpu"]
∧ Sum({i in DOMAIN p.Spec.Container :p.Spec.Container[i].Resources.Required["mem"] }) ≤Node.Status.Allocatable["mem"]
∧ ...
1.3 Node Selector
该过滤函数基于Pod的node selector值和Node的label值来确定Node的可用。
图 1.3 Node Selector
Filter(Pod, Node) == ∀ Label∈ DOMAIN(Pod.Spec.NodeSelector): ∧Label ∈ DOMAIN(Node.Labels) ∧Pod.Spec.NodeSelector[Label] = Node.Labels[Label]
1.4 Node Taints和Pod Tolerations
该过滤函数基于Pod的taints键值对和Node的tolerations键值对来确定Node的可用。
图 1.4 Node Taints和Pod Tolerations
Filter(Pod, Node) == ∀Taint ∈ Node.Spec.Taints: ∃Toleration ∈ Pod.Spec.Tolerations: Match(Toleration, Taint) Match(Toleration, Taint) == ∧CASE Toleration.Operator = "Exists" ⟶ Toleration.key = Taint.key [] Toleration.Operator = "Equal" ⟶ Toleration.key = Taint.key ∧ Toleration.value = Taint.value [] OTHER ⟶ FALSE ∧Toleration.Effect = Taint.Effect
如果某个Node的taints匹配Pod的tolerations, 一个Pod可能被绑定到该Node。如果某个Node的taints不匹配Pod的tolerations, 一个Pod不能被绑定该Node。
1.5 亲和性
该过滤函数基于Pod需要的Node亲和项，Pod亲和项和Pod反亲和项来确定Node的可用。
图 1.4 Node Taints和Pod Tolerations
Filter(Pod, Node) ≝ *Node, Affinity ∧ ∃NodeSelectorTerm ∈ Pod.Spec.Affinity.NodeAffinity.Required.NodeSelectorTerms : Match_NS(NodeSelectorTerm, Node) *Pod, Affinity ∧ ∀PodAffinityTerm ∈ Pod.Spec.Affinity.PodAffinity.Required : P_Affinity(PodAffinityTerm, Node) *Pod, Anit-Affinity ∧ ∀PodAffinityTerm ∈ Pod.Spec.Affinity.AntiPodAffinity.Required : ¬ P_Affinity(PodAffinityTerm, Node) * Node, Affinity, Match Node Selector Term Match_NS(NodeSelectorRequirement, Node) ≝ CASENodeSelectorRequirement.Operator = "In" ⟶ (NodeSelectorRequirement.Key ∈DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈NodeSelectorRequirement.Value) []NodeSelectorRequirement.Operator = "NotIn" ⟶¬ (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels) ∧Node.Labels[NodeSelectorRequirement.Key] ∈ NodeSelectorRequirement.Value) []NodeSelectorRequirement.Operator = "Exits" ⟶ (NodeSelectorRequirement.Key ∈DOMAIN(Node.Labels)) []NodeSelectorRequirement.Operator = "DoesNotExist" ⟶¬ (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels)) []_NodeSelectorRequirement.Operator = "Gt" ∧ ∀ Value ∈NodeSelectorRequirement.Value: Value ∈ Int ⟶ (NodeSelectorRequirement.Key ∈DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈ Int ∧Node.Labels[NodeSelectorRequirement.Key] >Max(NodeSelectorRequirement.Value)) []_NodeSelectorRequirement.Operator = "Lt" ∧ ∀ Value ∈NodeSelectorRequirement.Value: Value ∈ Int ⟶ (NodeSelectorRequirement.Key ∈DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈ Int ∧Node.Labels[NodeSelectorRequirement.Key] )
最终评分是下列项的总和： * 对于每一个匹配的Node Selector项的权重的总和 * 对于每一个匹配的Pod亲和项的权重的总和 * 对于每一个匹配的Pod反亲和项的权重的总和
用例分析
图6描述了包含2个不同类型的节点和2个不同类型的Pod的例子： * 没有GPU资源的9个节点 * 有GPU资源的6个节点
这个用例的目标是保证： *不需要GPU的Pod被分配到没有GPU的节点 * 需要GPU的Pod被分配到有GPU的节点
