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] <Min(NodeSelectorRequirement.Value))
  []OTHER 
     ⟶FALSE

* Pod, (Anti)Affinity, Match Pod Affinity Term
P_Affinity(PodAffinityTerm, Node) ==
IFPodAffinityTerm.TopoLOGyKey in DOMAIN(Node.Labels) THEN
    ∃Other ∈ {Other ∈ Objects : Other.Kind = "Node" ∧PodAffinityTerm.TopologyKey ∈ DOMAIN(Other.Labels) ∧Other.Labels[PodAffinityTerm.TopologyKey] =Node.Labels[PodAffinityTerm.TopologyKey]}: 
       ∃ Pod ∈ {Pod ∈ objects : Pod.kind = "Pod" ∧ BoundTo(Pod, Node)∧ Pod.namespace ∈ PodAffinityTerm.Namespaces}:
           Match_LS(PodAffinityTerm.LabelSelector, Pod.Labels)
ELSE
   FALSE

* Pod, (Anti)Affinity, Match Label Selector
Match_LS(LabelSelector, Labels) ≝
∧ ∀Key ∈ DOMAIN(LabelSelector) : Key ∈ DOMAIN(Labels) ∧ LabelSelector[Key] =Labels[Key]
∧ ∀LabelSelectorRequirement ∈ LabelSelector.MatchExPression:
     CASE LabelSelectorRequirement.Operator = "In"
          ⟶   (LabelSelectorRequirement.Key∈ DOMAIN(Labels) ∧ Labels[LabelSelectorRequirement.Key] ∈LabelSelectorRequirement.Values)
       [] _LabelSelectorRequirement.Operator = "NotIn"
          ⟶ ¬ (LabelSelectorRequirement.Key ∈ DOMAIN(Labels) ∧Labels[LabelSelectorRequirement.key] ∈ LabelSelectorRequirement.Values)
       [] _LabelSelectorRequirement.Operator = "Exists"
          ⟶   (LabelSelectorRequirement.Key∈ DOMAIN(Labels))
       [] _LabelSelectorRequirement.Operator = "DoesNotExist"
          ⟶ ¬ (LabelSelectorRequirement.Key ∈ DOMAIN(Labels))

Node亲和
一个Pod必须分配给label匹配Pod的Node亲和需求的Node。另外，一个Pod不能分配给label不匹配Pod的Node亲和需求的Node。

Pod亲和
一个Pod必须分配给匹配TopologyKey的Node, 且该Node上至少有一个Pod匹配Pod的亲和需求。

Pod反亲和
一个Pod必须分配给匹配TopologyKey的Node, 且该Node上没有Pod匹配Pod的反亲和需求。
可行性(Viability)

对于每一个Pod，Kubernetes Scheduler确定可用的Node集合，这些Node满足了该Pod的约束。然后，Kubernetes Scheduler从可用Node集合中确定最高可行性的Node。

从概念上讲，Kubernetes Scheduler定义了一个评分函数集合。给定一个Pod和一个Node，评分函数确定Pod和Node配对的可行性。这些结果最后相加。
Viability(Pod, Node,Snapshot) ==
Sum(<<Rating_1(Pod, Node, Snapshot), Rating_2(Pod, Node,Snapshot), ...>>)

下面小节详细描述了目前一些可用的过滤函数：

2.1 亲和偏好

这些过滤函数基于Pod的偏好Node亲和项，Pod亲和项和Pod反亲和项，对Node的可行性进行评分。

图 1.4 Node Taints和Pod Tolerations

Rating(Pod, Node) ≝
Sum(<<
Sum(LAMBDA Term: Term.Weight, {NodeSelectorTerm ∈Pod.Spec.Affinity.NodeAffinity.Preferred.NodeSelectorTerms :Match_NS(NodeSelectorTerm, Node) }),
Sum(LAMBDA Term: Term.Weight, {PodAffinityTerm ∈Pod.Spec.Affinity.PodAffinity.Preferred : P_Affinity(PodAffinityTerm, Node) }),
Sum(LAMBDA Term: Term.Weight, {PodAffinityTerm ∈Pod.Spec.Affinity.AntiPodAffinity.Preferred : ~ P_Affinity(PodAffinityTerm,Node)})
>>)

最终评分是下列项的总和： 对于每一个匹配的Node Selector项的权重的总和 对于每一个匹配的Pod亲和项的权重的总和 * 对于每一个匹配的Pod反亲和项的权重的总和

用例分析

图6描述了包含2个不同类型的节点和2个不同类型的Pod的例子： 没有GPU资源的9个节点 有GPU资源的6个节点

这个用例的目标是保证： 不需要GPU的Pod被分配到没有GPU的节点 需要GPU的Pod被分配到有GPU的节点